## Logic as a bounded lattice

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.