Boolean algebras

In mathematics, our understanding often progresses from more or less concrete examples to abstract concepts, from particular cases to the general one, from something we can understand using our everyday intuition and experience to something whose understanding requires rigorous assumptions and meticulous proofs. Thus, for example, our intuitive notion of change is captured in the definition of the derivative, which itself is a particular example of a linear operator. Similarly, we can immediately see that a square is ‘more symmetric’ than a parallelogram; it is then the task of mathematics to make this precise. One of the powers of abstraction lies in its generality, once a problem is solved on an abstract level, we are immediately freed from solving many individual problems. Perhaps more importantly for mathematics, abstraction simplifies many concepts by removing the irrelevant details, thus allowing us to see the essence of the concept. This movement from the concrete to the abstract will be the guiding principle in this blog post, as I will attempt to motivate Boolean algebras.

In the previous posts, we have discussed what is meant by classical first-order logic and how linear spaces can be used to break the distributivity law, demonstrating that ‘the logic of linear spaces’ does not form a classical logic. The linear spaces were in turn motivated by the fact that they form the state space for quantum mechanics. This time we will take a step back in some sense, we will ignore the fact that first-order logic has quantifiers, and consider only the logical propositions formed using ‘and’, ‘or’ and ‘not’¹, we will call it propositional logic.

Although the distributive law does not hold for linear spaces, it looks like whatever ‘the logic of linear spaces’ is, it is not too far from the propositional logic; for example, it still makes sense to ask whether something is not in a given linear space, or whether something is in a linear space $A$ or in a linear space $B$ . This is a typical example of a more general concept lurking behind the corner, we have two very similar things, which disagree in one or two properties, the task is to find what exactly are the similarities of the two.

We begin by defining a bounded lattice, if this feels too boring or too technical, just skip the axioms! Although I have used the symbols $\neg$ , $\land$ and $\lor$ before, for now let’s forget they had any meaning, the only properties they have are the ones derivable from the axioms we are about to introduce. Let $L$ be some set, we will denote the elements of the set by small letters $x, y, z, ...$ . Let $\land$ and $\lor$ be some operations on $L$ , that is, for any elements $x$ and $y$ in $L$ both $x \land y$ and $x \lor y$ are again elements of $L$ . We say that such set is a lattice if the following axioms hold.

(1) $x \lor x = x$ , $x \land x = x$

(2) $x \lor y = y \lor x$ , $x \land y = y \land x$

(3) $x \lor (y \lor z) = (x \lor y) \lor z$ , $x \land (y \land z) = (x \land y) \land z$

(4) $(x \lor y) \land y = y$ , $(x \land y) \lor y = y$

In short, the axioms are saying that the operations $\land$ and $\lor$ must be (1) redundant when the input on both sides is the same; (2) symmetric; and (3) associative (i.e. the order of the operations doesn’t matter). The axiom (4) is called absorption. A lattice $L$ is said to be bounded if there are elements $0$ and $1$ in $L$ so that for any element $x$ in $L$ the following holds.

(5) $x \lor 0 = x$ , $x \land 1 = x$

Note that from (4) and (5) it follows that $x \land 0 = 0$ and $x \lor 1 = 1$ . In this case $0$ is called the bottom element of $L$ and $1$ the top element of $L$ , the reason for this terminology will become clear via examples. We now observe that both propositional logic and linear spaces satisfy the axioms (1)-(5).²For propositional logic, the set $L$ is just the set of all logical propositions, $\land$ the logical ‘and’, $\lor$ the ‘or’, $0 = false$ is any sentence which is always false and $1 = true$ any sentence which is always true.

For the logic of linear spaces, $L$ is a linear space, continuing the example of the previous post, we can take this to be a plane. Recall that $\land$ is defined as the intersection of two spaces (which are mostly lines in our examples), and $\lor$ is ‘the smallest linear space containing the two spaces’ (entire plane in the case of two distinct lines). In this case $0 = \textrm{the zero vector space}$ , that is the origin, and $1 = L$ , that is the entire plane, so $0$ is the smallest space you can get and correspondingly $1$ is the largest one.

We have thus succeeded in the task of finding what is common for propositional logic and linear spaces, namely, they are both bounded lattices. What we should be asking next is whether the similarities end here. It turns out the answer is no, there is indeed one more axiom satisfied by both. However, before we go on with comparing propositional logic with linear spaces, it is useful to introduce the notion of a Boolean algebra. A bounded lattice $L$ is called a Boolean algebra if it has an operation $\neg$ and the following two axioms hold (I promise these are the last axioms to be introduced in this post).

(6) $x \land (y \lor z) = (x \land y) \lor (x \land z)$ , $x \lor (y \land z) = (x \lor y) \land (x \lor z)$

(7) $x \lor \neg x = 1$ , $x \land \neg x = 0$

The first part of axiom (6) should look familiar, it is the distributive law discussed in most of the previous posts. Interestingly, the two parts of axiom (6) are equivalent, by assuming either one, the other can be derived using the first four axioms.³Axiom (7) is also, more dramatically, known as ‘The Law of Excluded Middle’, first stating that either the proposition itself or its negation must be true; and that both cannot be simultaneously true.

The easiest example of a Boolean algebra is given by propositional logic, it is indeed distributive, and since each proposition is either true or false, (7) holds. A Boolean algebra doesn’t need to be limited to two truth values though, an example of this is given by ‘the set of all subsets’ of any set (called, again more dramatically, the power set). For example, consider the subsets of the three element set $\{1, 2, 3\}$ , or to make it look less scary, let us call the elements knife, fork and spoon. Now imagine you are a student, consequently, your kitchen drawer only contains one knife, one fork and one spoon, the power set of this drawer is then all the combinations of cutlery you can possibly take out of the drawer. It turns out that there are eight possible combinations, as illustrated by the following graph.

diagram

The symbol $\varnothing$ stands for the empty set, that is, nothing is taken out from the drawer. An arrow between two sets in the graph indicates that the lower set is contained in the upper one. These sets form a Boolean algebra with the following operations; $\land$ is the intersection of two sets, that is, it chooses the elements that are contained in both sets, $\lor$ is the union of two sets, that is, it contains all the elements that are in either of the two sets, and finally, $\neg x$ is the complement of the set $x$ , defined by taking away all the elements of $x$ from {knife, fork, spoon}. The top and bottom elements are {knife, fork, spoon} and $\varnothing$ , respectively. As we can see, the Boolean algebra of the kitchen drawer doesn’t have much to do with truth values, or rather, it has more truth values than just true and false; thus the sentence ‘I took the cutlery from the drawer’ can be partially true if, say, you only took the fork.

Similarly, we can turn the algebra of linear spaces into a Boolean algebra by introducing a restriction on the allowed subspaces. We have already seen that it is a bounded lattice, now define the operation $\neg x = x^{\perp}$ as the orthogonal complement of $x$ , that is, all those spaces perpendicular to $x$ , in the plane this is just another line.

perp

If we now fix two orthogonal subspaces of a given linear space, and include the zero space, then they form a Boolean algebra under the operations as defined before. In two dimensions, this is just a choice of two orthogonal lines, and looks very much like the picture above.

So by requiring the subspaces to be orthogonal, the logic of linear spaces becomes a Boolean algebra, and consequently the distributive law holds. It therefore looks like the non-distributivity, as demonstrated in the previous post, arises because the lines are not orthogonal; and indeed, in the example we used the three lines were chosen so that they are not orthogonal. If we consider a three-dimensional space instead, and pick three lines which are all mutually orthogonal, we can easily see that the distributive law holds, take for example, the following picture.

3daxis

Now $x \land (y \lor z) = (x \land y) \lor (x \land z)$ , since intersection will always result in zero, no matter which lines or planes intersect.

In fact, the logic of linear spaces (without requirement of orthogonality) satisfies all the axioms except (6), distributivity. This answers the question about how close the linear spaces are to propositional logic, the answer is: ‘very close’, they only differ by one axiom. There is even a special name for a set which satisfies the axioms (1)-(5) and (7), but not necessarily (6), it is called an orthocomplemented lattice by analogy with orthogonal complements of linear spaces. This demonstrates the power of the abstract approach, the similarities between the two have hopefully become apparent.

To conclude, let me emphasize that in order to turn an algebra of linear spaces into a Boolean algebra (which we would like to do, since we have a good intuitive understanding for Boolean algebras) we had to make a choice of the orthogonal spaces. In general, there are infinitely many such choices. Very roughly speaking, each such choice corresponds to a set of quantum observables whose value can be known simultaneously with arbitrary precision. The internal logic of such set is therefore classical, as the observables form a Boolean algebra. Let us call such choice a Boolean frame; the interesting, and the important, question concerns the interactions of these frames, this is where logic ceases to be classical. One approach to this is to introduce a collection of all possible linear subspaces of a given space, together with some ‘choice maps’ corresponding to the Boolean frames. Now whenever there is a linear map between two Boolean frames, it induces a map between the ‘choice maps’, which hopefully tells us something about the relationship between the observables in different frames. More detailed discussion would unfortunately require us to first cover some topics from category theory, which could on its own be a subject for multiple series of blog posts.

This post concludes my exploration of quantum logic in the form of a blog, which was one part of my summer research project in 2017. It by no means concludes my fascination with the subject, neither my interest to learn more.

¹We do not include implication, although it can be constructed using the other operations, namely, $x \Rightarrow y \equiv \neg x \lor y$ .

²For propositional logic, this is pretty much its definition, for linear spaces one has to prove that each axiom holds.

³The proof of this is left for the interested and the inspired, or you can look it up, it is a standard result in lattice theory.

Share this:

Like this:

Leave a Reply Cancel reply