Logic as a bounded lattice

August 6, 2021

This post is about a very complex way of justifying a neat notation: in some texts, the authors write $\bot$ for the statement that's always false, and $\top$ for the statement that's always true. Here we'll write $p \equiv q $ if both $p\implies q$ and $q\implies p$ hold. The logical or is denoted $\lor$ and the and $\land$ when there's no risk of confusion.

Posets

A partially-ordered set (or poset) is a set $L$ over which a certain binary relation $\leq$ is defined. This relation must satisfy three conditions: let $a,b,c$ be three elements of $L$

reflexive: we always have $a \leq a$
antisymmetric: if both $a\leq b$ and $b\leq a$ hold, then $a = b$
transitive: if $a\leq b$ and $b\leq c$ then $a\leq c$

Logic as a poset

For two statements $p,q$, define $(p\leq q )\triangleq (p \implies q)$. This makes sense because the $\leq $ symbol can be read as “comes before” or “is a predecessor of”. Indeed an implication involves a statement that holds “before” and a conclusion that comes “after”. Then we have that $ p \leq p $ is defined as $ p \implies p$ which is logically equivalent to $\lnot p \lor p$ which always holds. By definition we have that $ p \leq q$ and $q \leq p$ means implication in both directions, that is $p \equiv q$, that's antisymmetry. Finally, if one has $p \leq q$ and $q\leq r$ then we have $p \implies q \implies r$ which gives transitivity.

Lattices

If one equips a poset with two specific binary operators, called join ($\lor$) and meet ($\land$), we obtain a lattice. The join $a \lor b$ of two elements $a,b$ is the least upper bound of the set ${a,b}$. The meet $a\land b$, on the other end, is the greatest lower bound of the same set.

Logic as a lattice

If we define the logical or (which we will denote “$\mathrm{or}$” to avoid confusion) as our join as the logical and (which we here denote “$\mathrm{and}$“) as our meet, we must check the basic properties of the two operators.

The join has to first satisfy both $p \leq p\lor q$ and $q \leq p\lor q$. This holds because we always have $p\implies p\lor q$ and by symmetry the other inequality holds. We also have to show our candidate join is a least upper bound, that is any upper bound $u$ of ${p,q}$ satisfies $p\lor q \leq u$. If $u$ is an upper bound in the sense of $\leq$, then $$p\;\mathrm{or}\; q \implies u \equiv \lnot (p\;\mathrm{or}\; q) \;\mathrm{or}\; u \equiv (\lnot p \;\mathrm{or}\; u) \;\mathrm{and}\; (\lnot q \;\mathrm{or}\; u) $$

this last expression exactly means that both $p\leq u$ and $q\leq u$ hold. Similar computations yields that the logical and is indeed a valid meet.

Bounded lattices

A bounded lattice is a lattice for which there is a bottom element $\bot$ such that $\bot \leq a$ for any $a$, and a top element which is greater than any other element.

Logic as a bounded lattice

Here's our final question: can the two symbols $\bot$ and $\top$ have both a “lattice interpretation” and a “logical interpretation” ?

For any proposition $p$, we have that the false statement $\bot$ satisfies $\bot \leq p$ because

$$ \bot \implies p \equiv \lnot\bot \;\mathrm{or}\; p \equiv \top \;\mathrm{or}\; p \equiv \top$$

since the logical or of a true statement and any statement is always true. The derivation for the top element is similar, as $p\leq \top$ means $\lnot p\;\mathrm{or}\;\top$ which always holds and is equivalent to $\top$.

We thus showed that logic can be thought as a bounded lattice, which justifies naming $\bot$ the “always false” statement and $\top$ the always true statement.