In this installment, I will introduce the concept of Boolean algebra, one of the main stars of this series, and relate it to concepts introduced in previous lectures (distributive lattice, Heyting algebra, and so on). Boolean algebra is the algebra of classical propositional calculus, and so has an abstract logical provenance; but one of our eventual goals is to show how any Boolean algebra can also be represented in concrete set-theoretic (or topological) terms, as part of a powerful categorical duality due to Stone.
There are lots of ways to define Boolean algebras. Some definitions were for a long time difficult conjectures (like the Robbins conjecture, established only in the last ten years or so with the help of computers) — testament to the richness of the concept. Here we’ll discuss just a few definitions. The first is a traditional one, and one which is pretty snappy:
A Boolean algebra is a distributive lattice in which every element has a complement.
(If is a lattice and , a complement of is an element such that and . A lattice is said to be complemented if every element has a complement. Observe that the notions of complement and complemented lattice are manifestly self-dual. Since the notion of distributive lattice is self-dual, so therefore is the notion of Boolean algebra.)
- Example: Probably almost everyone reading this knows the archetypal example of a Boolean algebra: a power set , ordered by subset inclusion. As we know, this is a distributive lattice, and the complement of a subset satisfies and .
- Example: Also well known is that the Boolean algebra axioms mirror the usual interactions between conjunction , disjunction , and negation in ordinary classical logic. In particular, given a theory , there is a preorder whose elements are sentences (closed formulas) of , ordered by if the entailment is provable in using classical logic. By passing to logical equivalence classes ( iff in ), we get a poset with meets, joins, and complements satisfying the Boolean algebra axioms. This is called the Lindenbaum algebra of the theory .
Exercise: Give an example of a complemented lattice which is not distributive.
As a possible leading hint for the previous exercise, here is a first order of business:
Proposition: In a distributive lattice, complements of elements are unique when they exist.
Proof: If both and are complementary to , then . Since , we have . Similarly , so
The definition of Boolean algebra we have just given underscores its self-dual nature, but we gain more insight by packaging it in a way which stresses adjoint relationships — Boolean algebras are the same things as special types of Heyting algebras (recall that a Heyting algebra is a lattice which admits an implication operator satisfying an adjoint relationship with the meet operator).
Theorem: A lattice is a Boolean algebra if and only if it is a Heyting algebra in which either of the following properties holds:
- if and only if
- for all elements
Proof: First let be a Boolean algebra, and let denote the complement of an element . Then I claim that if and only if , proving that admits an implication . Then, taking , it follows that , whence 1. follows. Also, since (by definition of complement) is the complement of if and only if is the complement of , we have , whence 2. follows.
[Proof of claim: if , then . On the other hand, if , then . This completes the proof of the claim and of the forward implication.]
In the other direction, given a lattice which satisfies 1., it is automatically a Heyting algebra (with implication ). In particular, it is distributive. From , we have (from 1.) ; since is automatic by definition of , we get . From , we have also (from 1.) that ; since is automatic by definition of , we have . Thus under 1., every element has a complement .
On the other hand, suppose is a Heyting algebra satisfying 2.: . As above, we know . By the corollary below, we also know the function takes 0 to 1 and joins to meets (De Morgan law); since condition 2. is that is its own inverse, it follows that also takes meets to joins. Hence . Thus for a Heyting algebra which satisfies 2., every element has a complement . This completes the proof.
- Exercise: Show that Boolean algebras can also be characterized as meet-semilattices equipped with an operation for which if and only if .
The proof above invoked the De Morgan law . The claim is that this De Morgan law (not the other !) holds in a general Heyting algebra — the relevant result was actually posed as an exercise from the previous lecture:
Lemma: For any element of a Heyting algebra , the function is an order-reversing map (equivalently, an order-preserving map , or an order-preserving map ). It is adjoint to itself, in the sense that is right adjoint to .
Proof: First, we show that in (equivalently, in ) implies . But this conclusion holds iff , which is clear from . Second, the adjunction holds because
in if and only if
in if and only if
in if and only if
in if and only if
Corollary: takes any inf which exists in to the corresponding inf in . Equivalently, it takes any sup in to the corresponding inf in , i.e., . (In particular, this applies to finite joins in , and in particular, it applies to the case , where we conclude, e.g., the De Morgan law .)
- Remark: If we think of sups as sums and infs as products, then we can think of implications as behaving like exponentials . Indeed, our earlier result that preserves infs can then be recast in exponential notation as saying , and our present corollary that takes sups to infs can then be recast as saying . Later we will state another exponential law for implication. It is correct to assume that this is no notational accident!
Let me reprise part of the lemma (in the case ), because it illustrates a situation which comes up over and over again in mathematics. In part it asserts that is order-reversing, and that there is a three-way equivalence:
if and only if if and only if .
This situation is an instance of what is called a “Galois connection” in mathematics. If and are posets (or even preorders), a Galois connection between them consists of two order-reversing functions , such that for all , we have if and only if . (It’s actually an instance of an adjoint pair: if we consider as an order-preserving map and an order-preserving map , then in if and only if in .)
Here are some examples:
- The original example arises of course in Galois theory. If is a field and is a finite Galois extension with Galois group (of field automorphisms which fix the elements belonging to ), then there is a Galois connection consisting of maps and . This works as follows: to each subset , define to be . In the other direction, to each subset , define to be . Both and are order-reversing (for example, the larger the subset , the more stringent the conditions for an element to belong to ). Moreover, we have
iff ( for all ) iff
so we do get a Galois connection. It is moreover clear that for any , is an intermediate subfield between and , and for any , is a subgroup of . A principal result of Galois theory is that and are inverse to one another when restricted to the lattice of subgroups of and the lattice of fields intermediate between and . Such a bijective correspondence induced by a Galois connection is called a Galois correspondence.
- Another basic Galois connection arises in algebraic geometry, between subsets (of a polynomial algebra over a field ) and subsets . Given , define (the zero locus of ) to be . On the other hand, define (the ideal of ) to be . As in the case of Galois theory above, we clearly have a three-way equivalence
iff ( for all ) iff
so that , define a Galois connection between power sets (of the -variable polynomial algebra and of -dimensional affine space ). One defines an (affine algebraic) variety to be a zero locus of some set. Then, on very general grounds (see below), any variety is the zero locus of its ideal. On the other hand, notice that is an ideal of the polynomial algebra. Not every ideal of the polynomial algebra is the ideal of its zero locus, but according to the famous Hilbert Nullstellensatz, those ideals equal to their radical are. Thus, and become inverse to one another when restricted to the lattice of varieties and the lattice of radical ideals, by the Nullstellensatz: there is a Galois correspondence between these objects.
- Both of the examples above are particular cases of a very general construction. Let be sets and let be any relation between them. Then set up a Galois connection which in one direction takes a subset to , and in the other takes to . Once again we have a three-way equivalence
iff iff .
There are tons of examples of this flavor.
As indicated above, a Galois connection between posets is essentially the same thing as an adjoint pair between the posets (or between if you prefer; Galois connections are after all symmetric in ). I would like to record a few basic results about Galois connections/adjoint pairs.
- Given order-reversing maps , which form a Galois connection, we have for all and for all . (Given poset maps which form an adjoint pair , we have for all and for all .)
- Given a Galois connection as above, for all and for all . (Given an adjoint pair as above, the same equations hold.) Therefore a Galois connection induces a Galois correspondence between the elements of the form and the elements of the form .
Proof: (1.) It suffices to prove the statements for adjoint pairs. But under the assumption , if and only if , which is certainly true. The other statement is dual.
(2.) Again it suffices to prove the equations for the adjoint pair. Applying the order-preserving map
to from 1. gives . Applying from 1. to gives . Hence . The other equation is dual.
Incidentally, the equations of 2. show why an algebraic variety is the zero locus of its ideal (see example 2. above): if for some set of polynomials , then . They also show that for any element in a Heyting algebra, we have , even though is in general false.
Let be a Galois connection (or an adjoint pair). By the proposition, is an order-preserving map with the following properties:
for all .
Poset maps with these properties are called closure operators. We have earlier discussed examples of closure operators: if for instance is a group, then the operator which takes a subset to the subgroup generated by is a closure operator. Or, if is a topological space, then the operator which takes a subset to its topological closure is a closure operator. Or, if is a poset, then the operator which takes to is a closure operator. Examples like these can be multiplied at will.
One virtue of closure operators is that they give a useful means of constructing new posets from old. Specifically, if is a closure operator, then a fixed point of (or a -closed element of ) is an element such that . The collection of fixed points is partially ordered by the order in . For example, the lattice of fixed points of the operator above is the lattice of subgroups of . For any closure operator , notice that is the same as the image of .
One particular use is that the fixed points of the double negation closure on a Heyting algebra form a Boolean algebra , and the map is a Heyting algebra map. This is not trivial! And it gives a means of constructing some rather exotic Boolean algebras (“atomless Boolean algebras”) which may not be so familiar to many readers.
The following exercises are in view of proving these results. If no one else does, I will probably give solutions next time or sometime soon.
Exercise: If is a Heyting algebra and , prove the “exponential law” . Conclude that .
Exercise: We have seen that in a Heyting algebra. Use this to prove .
Exercise: Show that double negation on a Heyting algebra preserves finite meets. (The inequality is easy. The reverse inequality takes more work; try using the previous two exercises.)
Exercise: If is a closure operator, show that the inclusion map is right adjoint to the projection to the image of . Conclude that meets of elements in are calculated as they would be as elements in , and also that preserves joins.
Exercise: Show that the fixed points of the double negation operator on a topology (as Heyting algebra) are the regular open sets, i.e., those open sets equal to the interior of their closure. Give some examples of non-regular open sets. Incidentally, is the lattice you get by taking the opposite of a topology also a Heyting algebra?