Recall from PFDL II, I gave an interesting characterization of Boolean algebras among distributive lattices, using a technique from formal logic. Today I’d like to share some final musings on the topic, specifically in the form of a counterexample to a weakening of the hypotheses.
To remind ourselves of the work done so far in the series:
Theorem 1. Let be a Boolean algebra. Then every nonempty prime filter in is an ultrafilter.
Theorem 2. Let be a distributive bounded lattice. If every nonempty prime filter in is an ultrafilter, then is a Boolean algebra.
I’ve stated before that this proof was a homework problem in a logic course I took. But actually, that’s only half-right: as homework, we were assigned a weaker version of Theorem 2 in which the assumption of boundedness is omitted. And the interesting thing about that weaker version is it has no proof, because it’s false! I didn’t know at the time, but I couldn’t find a proof without assuming boundedness, so I told the professor as much and he accepted that submission.
To be clear, in the presence of Theorems 1 and 2, this weakening amounts to saying if every prime filter in a distributive lattice is an ultrafilter, then the lattice is bounded. And for the longest time I couldn’t figure out how to show this, because it doesn’t seem like it has any reason to follow. Well, in 2019, the problem floated back into my head and I was irritated enough that I wrote out some counterexamples, explaining very neatly why boundedness is necessary and killing this problem for good.
Let’s recall the terminology so you don’t have to click back to the previous installments. For a distributive lattice and a subset , we consider five properties:
- if and then ,
- if then ,
- if then or ,
- for all there exists so that ,
- there exists such that for all , .
If satisfies properties 1 and 2, it is a filter, and if it also satisfies property 3 then it is nontrivial. We will almost exclusively be considering nontrivial filters. If a nontrivial filter satisfies property 4, it is a prime filter, while if it satisfies property 5 it is an ultrafilter. Property 5 easily implies property 4 in distributive lattices, and there is a short proof of this in PFDL I. Finally, if a filter satisfies property 6, then it is a principal filter, and the least element is its generator—this has a complicated relationship with properties 4 and 5, but the terminology will be handy.
To show that boundedness in both directions is necessary in theorem 2, I need to produce a counterexample with no top, and another counterexample with no bottom.
First, unbounded above. Let be the lattice of finite subsets of . Obviously, this lattice is distributive, and is bounded below but not above.
Proposition 1. Every nonempty filter in is principal.
Proof. Let be a nonempty filter of , and let be the intersection of all the sets in . By property 1, it suffices to show that . Consider . We have , and for each , there exists such that . Then
is finite, so by property 2, . ∎
With this characterization, analysing the prime filters and ultrafilters becomes a lot easier to manage.
Proposition 2. A filter in is prime iff its generator is a singleton.
Proof. First, note that if , then is a trivial filter, so it cannot be prime.
Else, suppose . Then for any two finite sets , if , then . Obviously, either or , so at least one of or belongs to . Therefore, is prime.
Finally, suppose is the union of two nonempty proper subsets. Both are strict subsets of , so neither belong to , but their union is . Thus, is not prime.
These cases are jointly exhaustive. ∎
And now we swing it home.
Claim. Every prime filter in is an ultrafilter.
Proof. Let be a prime filter. By the previous proposition, . Let , that is, and . Define , so that , and observe that
Thus, is an ultrafilter. ∎
Therefore, boundedness above is required.
Now, we will show another example for bounded below. Let be the dual lattice of , which we will identify as the cofinite subsets of , that is, the sets whose complement is finite. This case is essentially the same as the previous, but a little dirtier to prove. For starters, we can no longer get away with the adjective ‘principal’, though we can still state something very similar.
Proposition 3. Every nonempty filter in is of the form for some subset .
Proof. Let be a filter and . Suppose be a cofinite set and . It suffices to show that . Consider its complement, , which is finite and disjoint from . Thus, for each , there exists with .
Let be their intersection. by property 2, and , so by property 1. ∎
This is essentially the same as being principal, but you can’t literally call it that because your generator does not belong to the lattice. As a result, the analogue of Proposition 2 goes through with little trouble.
Proposition 4. A filter in is prime iff its generator is a singleton.
Proof. If is empty, or is empty or a singleton, then is easily trivial and prime respectively. If contains two distinct elements , then clearly neither nor belongs to but
so is not prime. These cases are jointly exhaustive. ∎
Because the characterization of the prime filters are exactly the same ones as in , the proof that prime filters are ultrafilters goes through without any modification. I’m not even going to copypaste it. So, boundedness below is also required.
Now, of the people I imagine to have read this far, there are two kinds. The first kind would say, hey, this is boring, who even cares, why are you still beating this dead-ass horse. To them, I say, first of all, the way this was presented to me was very different then the way it was presented to you. You got three cute little blog posts all wrapped up in a bow, while I got Assignment 3 Question 1(c). It burrowed its way into my brain and I am proud for having excised it and achieved the happy ending.
And second of all, I would continue, lattices are a dying art. All the papers were written like a hundred years ago and the textbooks shortly afterwards. You don’t see them until they get quickly glossed over when you need to learn about like Stone-Čech compactification or something real quick while you’re in the middle of some godforsaken functional analysis class. Hell, half the uses of the word lattice nowadays are referring to discrete subgroups of , instead of special posets. Nobody stans lattices.
The second kind of person that I imagine still reads my undying screeds would say to me, hold on a second there, you haven’t given a counterexample that is unbounded in both directions. And to you, I say, truly you are my people. And unto you I bestow the most sacred of gifts, that I have reserved for you and you alone:
Exercise. Show that every prime filter in the product lattice is an ultrafilter.
Hint. There are two ways of doing this: following the blueprint laid out in this ‘blog post, or developing a little general theory of filters and product lattices.