Last time in this series on Stone duality, we observed a perfect duality between finite Boolean algebras and finite sets, which we called “baby Stone duality”:

  1. Every finite Boolean algebra B is obtained from a finite set X by taking its power set (or set of functions \hom(X, \mathbf{2}) from X to \mathbf{2}, with the Boolean algebra structure it inherits “pointwise” from \mathbf{2} = \{0, 1\}). The set X may be defined to be \mbox{Bool}(B, \mathbf{2}), the set of Boolean algebra homomorphisms from B to \mathbf{2}.
  2. Conversely, every finite set X is obtained from the Boolean algebra B = \hom(X, \mathbf{2}) by taking its “hom-set” \mbox{Bool}(B, \mathbf{2}).

More precisely, there are natural isomorphisms

i_B: B \stackrel{\sim}{\to} \hom(\mbox{Bool}(B, \mathbf{2}), \mathbf{2}),

j_X: X \stackrel{\sim}{\to} \mbox{Bool}(\hom(X, \mathbf{2}), \mathbf{2})

in the categories of finite Boolean algebras and of finite sets, respectively. In the language of category theory, this says that these categories are (equivalent to) one another’s opposite — something I’ve been meaning to explain in more detail, and I promise to get to that, soon! In any case, this duality says (among other things) that finite Boolean algebras, no matter how abstractly presented, can be represented concretely as power sets.

Today I’d like to apply this representation to free Boolean algebras (on finitely many generators). What is a free Boolean algebra? Again, the proper context for discussing this is category theory, but we can at least convey the idea: given a finite set S of letters x, y, z, \ldots, consider the Boolean algebra \mathbf{B}(S) whose elements are logical equivalence classes of formulas you can build up from the letters using the Boolean connectives \wedge, \vee, \neg (and the Boolean constants 0, 1), where two formulas \phi, \phi' are defined to be logically equivalent if \phi \leq \phi' and \phi' \leq \phi can be inferred purely on the basis of the Boolean algebra axioms. This is an excellent example of a very abstract description of a Boolean algebra: syntactically, there are infinitely many formulas you can build up, and the logical equivalence classes are also infinite and somewhat hard to visualize, but the mess can be brought under control using Stone duality, as we now show.

First let me cut to the chase, and describe the key property of free Boolean algebras. Let A be any Boolean algebra; it could be a power set, the lattice of regular open sets in a topology, or whatever, and think of a function f: S \to A from the set of letters to A as modeling or interpreting the atomic formulas x, y, z, \ldots as elements f(x), f(y), f(z), \ldots of A. The essential property of the free Boolean algebra is that we can extend this interpretation f in a unique way to a Boolean algebra map \mathbf{B}(S) \to A. The way this works is that we map a formula like (x \wedge \neg y) \vee z to the obvious formula (f(x) \wedge \neg f(y)) \vee f(z). This is well-defined on logical equivalence classes of formulas because if p = q in \mathbf{B}(S), i.e., if the equality is derivable just from the Boolean algebra axioms, then of course f(p) = f(q) holds in A as the Boolean algebra axioms hold in A. Thus, there is a natural bijective correspondence between functions S \to A and Boolean algebra maps \mathbf{B}(S) \to A; to get back from a Boolean algebra map \mathbf{B}(S) \to A to the function S \to A, simply compose the Boolean algebra map with the function S \to \mathbf{B}(S) which interprets elements of S as equivalence classes of atomic formulas in \mathbf{B}(S).

To get a better grip on \mathbf{B}(S), let me pass to the Boolean ring picture (which, as we saw last time, is equivalent to the Boolean algebra picture). Here the primitive operations are addition and multiplication, so in this picture we build up “formulas” from letters using these operations (e.g., (x + y) \cdot z and the like). In other words, the elements of \mathbf{B}(S) can be considered as “polynomials” in the variables x, y, z, \ldots. Actually, there are some simplifying features of this polynomial algebra; for one thing, in Boolean rings we have idempotence. This means that p^n = p for n \geq 1, and so a monomial term like x^3 y^2 reduces to its support x y. Since each letter appears in a support with exponent 0 or 1, it follows that there are 2^{|S|} possible supports or Boolean monomials, where |S| denotes the cardinality of S.

Idempotence also implies, as we saw last time, that b + b = 0 for all elements b \in \mathbf{B}(S), so that our polynomials = \mathbb{Z}-linear combinations of monomials are really \mathbb{Z}_2-linear combinations of Boolean monomials or supports. In other words, each element of \mathbf{B}(S) is uniquely a linear combination

\sum_{\sigma \in \mbox{supp}(S)} a_\sigma \sigma where a_\sigma \in \{0, 1\},

i.e., the set of supports \mbox{supp}(S) forms a basis of \mathbf{B}(S) as a \mathbb{Z}_2-vector space. Hence the cardinality of the free Boolean ring is 2^{|\mbox{supp}(S)|} = 2^{2^{|S|}}.

  • Remark: This gives an algorithm for checking logical equivalence of two Boolean algebra formulas: convert the formulas into Boolean ring expressions, and using distributivity, idempotence, etc., write out these expressions as Boolean polynomials = \mathbb{Z}_2-linear combinations of supports. The Boolean algebra formulas are equivalent if and only if the corresponding Boolean polynomials are equal.

But there is another way of understanding free Boolean algebras, via baby Stone duality. Namely, we have the power set representation

i: \mathbf{B}(S) \stackrel{\sim}{\to} \hom(\mbox{Bool}(\mathbf{B}(S), \mathbf{2}), \mathbf{2})

where \mbox{Bool}(\mathbf{B}(S), \mathbf{2}) is the set of Boolean algebra maps \mathbf{B}(S) \to \mathbf{2}. However, the freeness property says that these maps are in bijection with functions S \to \mathbf{2}. What are these functions? They are just truth-value assignments for the elements (atomic formulas, or variables) x, y, z, \ldots \in S; there are again 2^{|S|} many of these. This leads to the method of truth tables: each formula b \in \mathbf{B}(S) induces (in one-one fashion) a function

i(b): \mbox{Bool}(\mathbf{B}(S), \mathbf{2}) \to \mathbf{2}

which takes a Boolean algebra map \phi: \mathbf{B}(S) \to \mathbf{2}, aka a truth-value assignment for the variables x, y, z, \ldots, to the element of \{0, 1\} obtained by instantiating the assigned truth values 0, 1 for the variables and evaluating the resulting Boolean expression for b in \mathbf{2}. (In terms of power sets,

\mathbf{B}(S) \cong P(\mbox{Bool}(\mathbf{B}(S), \mathbf{2}))

identifies each equivalence class of formulas b \in \mathbf{B}(S) with the set of truth-value assignments of variables which render the formula b “true” in \{0, 1\}.) The fact that the representation b \mapsto i(b) is injective means precisely that if formulas b, c are inequivalent, then there is a truth-value assignment which renders one of them “true” and the other “false”, hence that they are distinguishable by truth tables.

  • Remark: This is an instance of what is known as a completeness theorem in logic. On the syntactic side, we have a notion of provability of formulas (that b is logically equivalent to \top, or b = \top in \mathbf{B}(S) if this is derivable from the Boolean algebra axioms). On the semantic side, each Boolean algebra homomorphism \phi: \mathbf{B}(S) \to \mathbf{2} can be regarded as a model of \mathbf{B}(S) in which each formula becomes true or false under \phi. The method of truth tables then says that there are enough models or truth-value assignments to detect provability of formulas, i.e., b is provable if it is true when interpreted in any model \phi. This is precisely what is meant by a completeness theorem.

There are still other ways of thinking about this. Let \phi: B \to \mathbf{2} be a Boolean algebra map, aka a model of B. This model is completely determined by

  • The maximal ideal \phi^{-1}(0) in the Boolean ring B, or
  • The maximal filter or ultrafilter \phi^{-1}(1) in B.

Now, as we saw last time, in the case of finite Boolean algebras, each (maximal) ideal is principal: is of the form \{x \in B: x \leq b\} for some b \in B. Dually, each (ultra)filter is principal: is of the form \{x \in B: c \leq x\} for some c = \neg b \in B. The maximality of the ultrafilter means that there is no nonzero element in B smaller than c; we say that c is an atom in B (NB: not to be confused with atomic formula!). So, we can also say

  • A model of a finite Boolean algebra B is specified by a unique atom of B.

Thus, baby Stone duality asserts a Boolean algebra isomorphism

i: B \to P(\mbox{Atoms}(B)).

Let’s give an example: consider the free Boolean algebra on three elements x, y, z. If you like, draw a Venn diagram generated by three planar regions labeled by x, y, z. The atoms or smallest nonzero elements of the free Boolean algebra are then represented by the 2^3 = 8 regions demarcated by the Venn diagram. That is, the disjoint regions are labeled by the eight atoms

x \wedge y \wedge z, x \wedge y \wedge \neg z, x \wedge \neg y \wedge z, x \wedge \neg y \wedge \neg z,

\neg x \wedge y \wedge z, \neg x \wedge y \wedge \neg z, \neg x \wedge \neg y \wedge z, \neg x \wedge \neg y \wedge \neg z.

According to baby Stone duality, any element in the free Boolean algebra (with 2^8 = 256 elements) is uniquely expressible as a disjoint union of these atoms. Another way of saying this is that the atoms form a basis (alternative to Boolean monomials) of the free Boolean algebra as \mathbb{Z}_2-vector space. For example, as an exercise one may calculate

(x \Rightarrow y) \wedge z = x \wedge y \wedge z + \neg x \wedge y \wedge z + \neg x \wedge \neg y \wedge z.

The unique expression of an element b \in \mathbf{B}(S) (where b is given by a Boolean formula) as a \mathbb{Z}_2-linear combination of atoms is called the disjunctive normal form of the formula. So yet another way of deciding when two Boolean formulas are logically equivalent is to put them both in disjunctive normal form and check whether the resulting expressions are the same. (It’s basically the same idea as checking equality of Boolean polynomials, except we are using a different vector space basis.)

All of the above applies not just to free (finite) Boolean algebras, but to general finite Boolean algebras. So, suppose you have a Boolean algebra B which is generated by finitely many elements x_1, x_2, \ldots, x_n \in B. Generated means that every element in B can be expressed as a Boolean combination of the generating elements. In other words, “generated” means that if we consider the inclusion function S = \{x_1, \ldots, x_n\} \hookrightarrow B, then the unique Boolean algebra map \phi: \mathbf{B}(S) \to B which extends the inclusion is a surjection. Thinking of \phi as a Boolean ring map, we have an ideal I = \phi^{-1}(0), and because \phi is a surjection, it induces a ring isomorphism

B \cong \mathbf{B}(S)/I.

The elements of I can be thought of as equivalence classes of formulas which become false in B under the interpretation \phi. Or, we could just as well (and it may be more natural to) consider instead the filter F = \phi^{-1}(1) of formulas in \mathbf{B}(S) which become true under the interpretation \phi. In any event, what we have is a propositional language \mathbf{B}(S) consisting of classes of formulas, and a filter F \subseteq \mathbf{B}(S) consisting of formulas, which can be thought of as theorems of B. Often one may find a filter F described as the smallest filter which contains certain chosen elements, which one could then call axioms of B.

In summary, any propositional theory (which by definition consists of a set S of propositional variables together with a filter F \subseteq \mathbf{B}(S) of the free Boolean algebra, whose elements are called theorems of the theory) yields a Boolean algebra B = \mathbf{B}(S)/F, where dividing out by F means we take equivalence classes of elements of \mathbf{B}(S) under the equivalence relation b \sim c defined by the condition “b \Leftrightarrow c belongs to F“. The partial order on equivalence classes [b] is defined by [b] \leq [c] iff b \Rightarrow c belongs to F. The Boolean algebra B defined in this way is called the Lindenbaum algebra of the propositional theory.

Conversely, any Boolean algebra B with a specified set of generators x_1, \ldots x_n can be thought of as the Lindenbaum algebra of the propositional theory obtained by taking the x_i as propositional variables, together with the filter \phi^{-1}(1) obtained from the induced Boolean algebra map \phi: \mathbf{B}(S) \to B. A model of the theory should be a Boolean algebra map \mathbf{B}(S) \to \mathbf{2} which interprets the formulas of \mathbf{B}(S) as true or false, but in such a way that the theorems of the theory (the elements of the filter) are all interpreted as “true”. In other words, a model is the same thing as a Boolean algebra map

B \cong \mathbf{B}(S)/F \to \mathbf{2}.

i.e., we may identify a model of a propositional theory with a Boolean algebra map f: B \to \mathbf{2} out of its Lindenbaum algebra.

So the set of models is the set \mbox{Bool}(B, \mathbf{2}), and now baby Stone duality, which gives a canonical isomorphism

i: B \cong \hom(\mbox{Bool}(B, \mathbf{2}), \mathbf{2}),

implies the following

Completeness theorem: If a formula of a finite propositional theory is “true” when interpreted under any model \phi of the theory, then the formula is provable (is a theorem of the theory).

Proof: Let B be the Lindenbaum algebra of the theory, and let b = [p] \in B be the class of formulas provably equivalent to a given formula p under the theory. The Boolean algebra isomorphism i takes an element b \in B to the map \phi \mapsto \phi(b). If \phi(b) = 1 for all models \phi, i.e., if i(b) = 1, then b = 1. But then [p] = 1, i.e., p \in F, the filter of provable formulas. \Box

In summary, we have developed a rich vocabulary in which Boolean algebras are essentially the same things as propositional theories, and where models are in natural bijection with maximal ideals in the Boolean ring, or ultrafilters in the Boolean algebra, or [in the finite case] atoms in the Boolean algebra. But as we will soon see, ultrafilters have a significance far beyond their application in the realm of Boolean algebras; in particular, they crop up in general studies of topology and convergence. This is in fact a vital clue; the key point is that the set of models or ultrafilters \mbox{Bool}(B, \mathbf{2}) carries a canonical topology, and the interaction between Boolean algebras and topological spaces is what Stone duality is all about.