Week 3 [2023-04-20 Thu]

We saw that truth values and sets have a common abstract structure, on the basis of which a general meaning for and and or can be given.

But what about not? Intuitively, not gives us the opposite of what we started with—the opposite of truth is falsity,¹ the opposite of a set of entities is the set containing everything else, etc. But how can we make sense of the notion of an “opposite” element? We shall see that this can be formulated in terms of greatest lower and least upper bound operations—henceforth: glb and lub operators.

In the context of truth values, the opposite of 0 is 1 and of 1 is 0. 0 is also the smallest truth value, and 1 the biggest. Sets (i.e. the set of subsets of a given set) can be seen as a refinement of the set of truth values—they still have a smallest (the empty set) and a biggest (the universe) element, but also many other objects in between. With sets, we see here again that the opposite (complement) of the empty set is the universe, and vice versa. Having a least or greatest element is not necessary for a poset—the natural numbers are a poset, and while they have a least element (0) they famously have no greatest element. Similarly, the set of all integers is a poset, but here there is neither a least nor a greatest element. A poset that has a least and a greatest element is said to be bounded.

The glb of two objects x and y is the object that best captures what x and y have in common. It seems reasonable to demand that the opposite of an element x should have nothing in common with it—i.e. that \(x \wedge \neg x = 0\). However, there can be many objects that have nothing in common with any others—the set \(\{g\}\) has nothing in common with the set \(\{s\}\), nor with the sets \(\{c\}\), \(\{o\}\), or \(\{j\}\). We want the opposite of x to be something like the biggest element that has nothing in common with it. Together, an element and its complement should fill the sky: \(x \vee \neg x = 1\). A (necessarily bounded) lattice where every element has a complement is called complemented. If in a complemented lattice the glb and lub operations distribute over one another—if always \(x \wedge (y \vee z)) = (x \wedge y) \vee (x \wedge z)\)—then complements are unique. Distributive complemented lattices are called boolean. As it turns out, both the truth value lattice and the powerset lattice are boolean.

We can advance the further claim that:

• not denotes the complement operation.

Taken together, this analysis of the boolean words can be generalized in the following way:

The boolean hypothesis

Boolean words work on expressions iff those expressions denote in a boolean lattice. In this case, the boolean words denote the glb, lub, and complement operators in that lattice.

Readings

• MSL chapter 8