Recall from PFDL I, I introduced distributive lattices and filters, and we proved the easy direction of a characterization of Boolean algebras. Today I’ll detail a proof of the tougher and far more obscure converse—it involves some sneaky technology from formal logic.
Theorem 1 states that, in a Boolean algebra, every (nonempty) prime filter is an ultrafilter. Its converse is as follows:
Theorem 2. Let be a (distributive, bounded) lattice. If every nonempty prime filter in is an ultrafilter, then is a Boolean algebra.
The goal of a proof of Theorem 2 is to find a complement to any given element. That is, for any , we want a such that and . There is no hope of doing this constructively, given our hypotheses, so we’ll instead try to show that if no element does both, there is a contradiction.
To show this, I’ll need to introduce some technology. A lot of the following is adapted from Chapter 5 of Introduction to Substructural Logic by Restall, but it has a somewhat different focus. I can’t in all honesty recommend the book, unless you have an intense interest in nonclassical logic.
A partial filter-ideal pair or PFI-pair is a pair of subsets of , such that there do not exist and satisfying . We will abbreviate this as for the collection of all finite meets in , and the finite joins in . It follows from the reflexivity of that and must be disjoint.
A PFI-pair is full if . The following should explain my nomenclature, though not the unfortunate redundancy in “full partial filter-ideal pair”.
Exercise. If is a full PFI-pair, then is a filter and is an ideal, that is, a filter in the dual . Furthermore, if is nonempty then is prime, and if is nonempty then is prime (as a filter in ).
Say that a pair of sets extends another pair if and . Clearly, if is a PFI-pair and extends , then is also a PFI-pair. We would like the ability to do the opposite: start with a PFI-pair and extend it to a larger one. Ideally a full pair, but let’s take it one step at a time.
Step Lemma. If is a PFI-pair and , then one of or is a PFI-pair.
Proof. Suppose that is a PFI-pair but neither extension is. Then there are and such that and . Then
contradicting the assumption that is a PFI-pair. ∎
Right on. Now we can just hit this sucker with Zorn’s Lemma.
Pair Extension Theorem. (Belnap, 1970s) Every PFI-pair is extended by some full PFI-pair.
Proof. Let be the poset of PFI-pairs extending , ordered by extension. If is a chain, then is an upper bound, because some any violation of the PFI-pair condition can also be found in some sufficiently large element of , contradicting its membership in . So by Zorn’s Lemma, has an maximal element . The PFI-pair must be full, for fear of contradicting the Step Lemma. ∎
For those of you who are afraid of very infinite sets: if is countable then we can get by by listing its elements and iterating the Step Lemma to infinity.
Now we have all the tools we need to prove Theorem 2. So let’s do that.
Let . The goal is to find a complement for , that is, letting
to show that is nonempty. These sets are rather mysterious, so we need to learn some more about them.
Exercise. is a nonempty filter and is a nonempty ideal (downward-closed and upward-directed).
That’s pretty good. But it gets better: if and , then
It easily follows that if and intersect, they do so in precisely one element, as we would expect. Suppose now for a contradiction that and are disjoint.
Claim. is a PFI-pair.
Proof. Otherwise, there exist and such that either or . The former is impossible, because , and the latter is too since it implies , i.e. . ∎
So by the Pair Extension Theorem, there exists a full pair extending . Then is a prime filter, and consequently an ultrafilter by hypothesis. But that means for some . Then , contradicting the fact that and are disjoint.
Thus, . is a complement for by definition. was arbitrary, so is a Boolean algebra. This concludes the proof of Theorem 2. ∎
I have tried my best to make that argument is as clear and intuitive as I could. Unfortunately, I don’t think there’s a way around the use of PFI-pairs. If you’ll permit me to try my hand at an intuitive explanation of these objects, please read on.
Just as in the construction of the integers from the naturals, or of the rationals from the integers, one often has to emulate some sort of oppositeness or negation by carrying around both the positive and negative parts, collected in an ordered pair. Here, the task in logic originally solved by PFI-pairs is to show there exist “prime theories”—basically prime filters, except living in the “quasilattice” of propositions in logics with conjunction and disjunction—possibly satisfying some mild desired conditions.
The use of prime theories, in turn, was to coherently select exactly one proposition from every pair of complements, even in logics without a negation. See, the theories of a logic are, in a sense, those collections of propositions that could coherently be considered true. Primality is then the assertion that this truth must be witnessed. For if then a prime theory must contain at least one of or , even if it cannot contain both without being trivial, due to e.g. .
Logician really love to require that disjunctions be witnessed, because that meshes with our intuitive understanding of the notion of alternatives. Even if it sometimes makes the math harder. I can probably come up with a lot of examples involving de Morgan’s law and/or frame semantics but I think I’ll stop before I drown the mathematics in my omphaloskepsis.