May 30, 2009...3:43 pm

The Right Theorem

Jump to Comments

This post is about a simple and useful Fact:

The lattice of ideals of a Boolean algebra is a complete Heyting algebra.

The Fact is easily deduced from the Stone Representation Theorem. First, observe that the closed subsets of the Stone space \mathcal{S}(\mathbb{B}) of a Boolean algebra \mathbb{B} are in a one-to-one correspondence with the ideals of \mathbb{B} via the map that sends an ideal I to the set of all ultrafilters contained in the complement of I as subsets of \mathbb{B}.  This correspondence is order reversing, so we take complements to obtain an order preserving map from the ideals of \mathbb{B} onto the open subsets of \mathcal{S}(\mathbb{B}). The lattice of open sets of \mathcal{S}(\mathbb{B}) (or any topological space) is a complete Heyting algebra.

While simple enough, this proof is not elementary and it implicitly relies on the Boolean Prime Ideal Theorem. Moreover, establishing the Fact is a key step in the proof of the Stone Representation Theorem. Of course, the Fact itself cannot be found in Marshall Stone’s The Theory of Representation for Boolean Algebras [Trans. Amer. Math. Soc. 40 (1936), no. 1, 37–111] since complete Heyting algebras were essentially unknown at the time, but a proof can be gathered from the results in Chapter II. In fact, it is surprisingly difficult to find a standalone version of the Fact in the literature. (Theorem 46 and following remarks in Garrett Birkhoff’s Lattice-Ordered Groups [Ann. of Math. (2) 43 (1942). 298–331] is perhaps the earliest close call.)

The implicit use of the Boolean Prime Ideal Theorem in the proof of the Fact outlined above is only to show that the Stone space \mathcal{S}(\mathbb{B}) has points. In Pointless Topology, the Fact is indistinguishable from the Stone Representation Theorem. I did not try to find the earliest occurrence of the “Pointless Stone Representation Theorem” in the literature (which is with very likely in one of André Joyal’s unpublished notes), but it is discussed in Peter Johnstone’s essay The Point of Pointless Topology [Bull. Amer. Math. Soc. (N.S.) 8 (1983), no. 1, 41–53]. From the perspective of Pointless Topology, the Fact is just a statement of the Stone duality between the category of Stone spaces and the category of Boolean algebras. This is a very elegant perspective which fixes the reliance on the Boolean Prime Ideal Theorem, but it does not address the problem of elementarity.

The elementary proof sheds a completely different light on the Fact. In order to show that a complete lattice is a complete Heyting algebra, it is necessary and sufficient to show that it satisfies the infinite distributive law

x \wedge (\bigvee_{y \in A} y) = \bigvee_{y \in A} (x \wedge y),

where A is an arbitrary set of lattice elements. It is easy enough to show that the lattice of ideals of a Boolean algebra satisfies this. To carry out the proof, it is natural to first prove the finite distributive law

x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)

and then lift to the infinite case. This division is a manifestation of a general property of abstract algebras, which leads to a purely algebraic generalization of the Fact.

The ideals of a Boolean algebra are mildly disguised congruence relations on the Boolean algebra. The lattice of congruence relations of any algebra (hence, the lattice of ideals of a Boolean algebra) is always a complete algebraic lattice. Such a lattice is always meet-continuous, which means that

x \wedge (\bigvee_{y \in D} y) = \bigvee_{y \in D} (x \wedge y)

whenever D is a directed set of lattice elements. Therefore, the lattice of congruence relations of an algebra satisfies the infinite distributive law of the previous paragraph if and only if it satisfies the finite distributive law. To summarize, the Fact is equivalent to the elementary statement that the lattice of ideals (equivalently, the lattice of congruence relations) of a Boolean algebra is distributive.

The elementary proof reveals that the close connection between Boolean algebras and Heyting algebras has little or nothing to do with the Fact itself. Indeed, the lattice of congruence relations of any algebra is a complete Heyting algebra exactly when it is distributive. On the other hand, the elementary proof does not reveal any of the implicit topological structure. The two views of the Fact are at opposite ends of the spectrum. Are the two perspectives fundamentally different or is there a broader point of view that reconciles both?

Leave a Comment

Filed under Algebra, Logic, Orderings

Leave a Reply