Prime Filters in Distributive Lattices II

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 $L$ be a (distributive, bounded) lattice. If every nonempty prime filter in $L$ is an ultrafilter, then $L$ 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 $a \in L$, we want a $b \in L$ such that $a \wedge b = \bot$ and $a \vee b = \top$. 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 $(F,I)$ of subsets of $L$, such that there do not exist $f_1, ..., f_m \in F$ and $i_1, ..., i_n \in I$ satisfying $f_1 \wedge \cdots \wedge f_m \le i_1 \vee \cdots \vee i_m$. We will abbreviate this as $m \nleq j$ for $\def\finwedge{\bigwedge^{\text{fin}}}m \in \finwedge F$ the collection of all finite meets in $F$, and $\def\finvee{\bigvee^{\text{fin}}}j \in \finvee I$ the finite joins in $I$. It follows from the reflexivity of $\le$ that $F$ and $I$ must be disjoint.

A PFI-pair $(F,I)$ is full if $F \cup I = L$. The following should explain my nomenclature, though not the unfortunate redundancy in “full partial filter-ideal pair”.

Exercise. If $(F,I)$ is a full PFI-pair, then $F$ is a filter and $I$ is an ideal, that is, a filter in the dual $L^*$. Furthermore, if $I$ is nonempty then $F$ is prime, and if $F$ is nonempty then $I$ is prime (as a filter in $L^*$).

Say that a pair of sets $(S,T)$ extends another pair $(s,t)$ if $S \supseteq s$ and $T \supseteq t$. Clearly, if $(F',I')$ is a PFI-pair and extends $(F,I)$, then $(F,I)$ 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 $(F,I)$ is a PFI-pair and $x \notin F \cup I$, then one of $(F \cup \{x\},I)$ or $(F,I \cup \{x\})$ is a PFI-pair.

Proof. Suppose that $(F,I)$ is a PFI-pair but neither extension is. Then there are $m,m' \in \finwedge F$ and $j,j' \in \finvee I$ such that $m \wedge x \le j$ and $m' \le x \vee j'$. Then

$$m \wedge m' \le m \wedge (x \vee j') = (m \wedge x) \vee (m \wedge j') \le j \vee j',$$

contradicting the assumption that $(F,I)$ 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 $P$ be the poset of PFI-pairs extending $(F_0,I_0)$, ordered by extension. If $C \subseteq P$ is a chain, then $\bigl( \bigcup\{ F : (F,I) \in C \}, \bigcup\{ I : (F,I) \in C \} \bigr)$ is an upper bound, because some any violation $f \le i$ of the PFI-pair condition can also be found in some sufficiently large element of $C$, contradicting its membership in $P$. So by Zorn’s Lemma, $P$ has an maximal element $(F, I)$. The PFI-pair $(F, I)$ must be full, for fear of contradicting the Step Lemma. ∎

For those of you who are afraid of very infinite sets: if $L$ 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 $x \in L$. The goal is to find a complement for $x$, that is, letting

$$A = \{ a \in L : x \vee a = \top \} \quad \text{and} \quad B = \{ b \in L : x \wedge b = \bot \},$$

to show that $A \cap B$ is nonempty. These sets are rather mysterious, so we need to learn some more about them.

Exercise. $A$ is a nonempty filter and $B$ is a nonempty ideal (downward-closed and upward-directed).

That’s pretty good. But it gets better: if $a \in A$ and $b \in B$, then

$$b = \top \wedge b = (a \vee x) \wedge b = (a \wedge b) \vee (x \wedge b) = (a \wedge b) \vee \bot = a \wedge b \le a.$$

It easily follows that if $A$ and $B$ intersect, they do so in precisely one element, as we would expect. Suppose now for a contradiction that $A$ and $B$ are disjoint.

Claim. $(A, B \cup \{x\})$ is a PFI-pair.

Proof. Otherwise, there exist $a \in A$ and $b \in B$ such that either $a \le b$ or $a \le b \vee x$. The former is impossible, because $a \ge b$, and the latter is too since it implies $b \vee x \ge a \vee x = \top$, i.e. $b \in A$. ∎

So by the Pair Extension Theorem, there exists a full pair $(F, I)$ extending $(A, B \cup \{x\})$. Then $F$ is a prime filter, and consequently an ultrafilter by hypothesis. But that means $f \wedge x = \bot$ for some $f \in F$. Then $f \in B \subseteq I$, contradicting the fact that $F$ and $I$ are disjoint.

Thus, $A \cap B = \{y\}$. $y$ is a complement for $x$ by definition. $x \in L$ was arbitrary, so $L$ 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 $\top \vdash A \vee B$ then a prime theory must contain at least one of $A$ or $B$, even if it cannot contain both without being trivial, due to e.g. $A \wedge B \vdash \bot$.

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.

This is the second post in a series. Here is the next.