After this brief (?) categorical interlude, I’d like to pick up the main thread again, and take a closer look at the some of the ingredients of baby Stone duality in the context of categorical algebra, specifically through the lens of adjoint functors. By passing a topological light through this lens, we will produce the spectrum of a Boolean algebra: a key construction of full-fledged Stone duality!

Just before the interlude, we were discussing some consequences of baby Stone duality. Taking it from the top, we recalled that there are canonical maps

i_B: B \to \hom(\mbox{Bool}(B, \mathbf{2}), \mathbf{2}): b \mapsto (\phi \mapsto \phi(b))

j_X: X \to \mbox{Bool}(\hom(X, \mathbf{2}), \mathbf{2}): x \mapsto (\sigma \mapsto \sigma(x))

in the categories of Boolean algebras B and sets X. We said these are “natural” maps (even before the notion of naturality had been formally introduced), and recalled our earlier result that these are isomorphisms when B and X are finite (which is manifestly untrue in general; for instance, if B is a free Boolean algebra generated by a countable set, then for simple reasons of cardinality B cannot be a power set).

What we have here is an adjoint pair of functors between the categories Set and \mbox{Bool} of sets and Boolean algebras, each given by a hom-functor:

(P^{op} = \hom(-, \mathbf{2})^{op}: Set \to \mbox{Bool}^{op}) \dashv (Q = \mbox{Bool}(-, \mathbf{2}): \mbox{Bool}^{op} \to Set)

(P^{op} acts the same way on objects and morphisms as P: Set^{op} \to \mbox{Bool}, but is regarded as mapping between the opposite categories). This actually says something very simple: that there is a natural bijection between Boolean algebra maps and functions

\displaystyle \frac{\phi: B \to \hom(X, \mathbf{2})}{\hat{\phi}: X \to \mbox{Bool}(B, \mathbf{2})}

given by the formula \hat{\phi}(x)(b) = \phi(b)(x). [The very simple nature of this formula suggests that it’s nothing special to Boolean algebras — a similar adjunction could be defined for any algebraic theory defined by operations and (universally quantified) equations, replacing \mathbf{2} by any model of that theory.] The unit of the adjunction at X is the function j_X: X \to QP^{op}X, and the counit at B is the Boolean algebra map i_B (regarded as a morphism \varepsilon_B: P^{op}QB \to B mapping the other way in the opposite category \mbox{Bool}^{op}).

The functor QP^{op} is usually described in the language of ultrafilters, as I will now explain.

Earlier, we remarked that an ultrafilter in a Boolean algebra is a maximal filter, dual to a maximal ideal; let’s recall what that means. A maximal ideal I in a Boolean ring B is the kernel of a (unique) ring map

\phi: B \to \mathbf{2}

i.e., has the form I = \phi^{-1}(0) for some such map. Being an ideal, it is an additive subgroup I \subseteq B such that x \in B, y \in I implies x y = x \wedge y \in I. It follows that if x, y \in I, then x \vee y = x + y + xy \in I, so I is closed under finite joins (including the empty join 0 = \bot). Also, if x \leq y and y \in I, then x = x \wedge y = xy \in I, so that I is “downward-closed”.

Conversely, a downward-closed subset I \subseteq B which is closed under finite joins is an ideal in B (exercise!). Finally, if I is a maximal ideal, then under the quotient map

\phi: B \to B/I \cong \mathbf{2}

we have that for all b \in B, either \phi(b) = 0 or \phi(b) = 1, i.e., that either b \in I or \neg b = 1 - b \in I.

Thus we have redefined the notion of maximal ideal in a Boolean algebra in the first-order theory of posets: a downward-closed set I \subseteq B closed under finite joins, such that every element or its complement (but never both!) is contained in I. [If both x, \neg x \in I, then x \vee \neg x = 1 \in I, whence b \in I for all b \in B (since b \leq 1 and I is downward-closed). But then I isn’t a maximal (proper) ideal!]

The notion of ultrafilter is dual, so an ultrafilter in a Boolean algebra B is defined to be a subset F \subseteq B which

  • Is upward-closed: if x \in F and x \leq y, then y \in F;
  • Is closed under finite meets: if x, y \in F, then x \wedge y \in F;
  • Satisfies dichotomy: for every x \in B, exactly one of x, \neg x belongs to F.

If I is a maximal ideal, then \neg I = \{\neg x: x \in I\} is an ultrafilter, and we have natural bijections between the following concepts:

Boolean algebra maps B \to \mathbf{2} \leftrightarrow maximal ideals I \subseteq B \leftrightarrow ultrafilters F \subseteq B

so that QB = \mbox{Bool}(B, \mathbf{2}) is naturally identified with the set of ultrafilters in B.

If X is a set, then an ultrafilter on X is by definition an ultrafilter in the Boolean algebra P X. Hence QP^{op}X is identified with the set of ultrafilters on X, usually denoted \beta X. The unit map

j_X: X \to QP^{op}X \cong \beta X

maps x \in X to an ultrafilter denoted \mbox{prin}_X(x) \subseteq PX, consisting of all subsets S \subseteq X which contain x, and called the principal ultrafilter generated by x.

We saw that when X is finite, the function j_X (and therefore also \mbox{prin}_X) is a bijection: there every ultrafilter is principal, as part of baby Stone duality (see Proposition 4 here). Here is a slight generalization:

Proposition 1: If an ultrafilter F on X contains a finite set S \subseteq X, then F is principal.

Proof: It is enough to show F contains \{x\} for some x \in S. If not, then F contains the complement \neg\{x\} for every x \in S (by dichotomy), and therefore also the finite intersection

\bigcap_{x \in S} \neg\{x\} = \neg S,

which contradicts the fact that S \in F. \Box

It follows that nonprincipal ultrafilters can exist only on infinite sets X, and that every cofinite subset of X (complement of a finite set) belongs to such an ultrafilter (by dichotomy). The collection of cofinite sets forms a filter, and so the question of existence of nonprincipal ultrafilters is the question of whether the filter of cofinite sets can be extended to an ultrafilter. Under the axiom of choice, the answer is yes:

Proposition 2: Every (proper) filter in a Boolean algebra is contained in some ultrafilter.

Proof: This is dual to the statement that every proper ideal in a Boolean ring is contained in a maximal ideal. Either statement may be proved by appeal to Zorn’s lemma: the collection of filters which contain a given filter has the property that every linear chain of such filters has an upper bound (namely, the union of the chain), and so by Zorn there is a maximal such filter. \Box

As usual, Zorn’s lemma is a kind of black box: it guarantees existence without giving a clue to an explicit construction. In fact, nonprincipal ultrafilters on sets X, like well-orderings of the reals, are notoriously inexplicit: no one has ever seen one directly, and no one ever will.

That said, one can still develop some intuition for ultrafilters. I think of them as something like “fat nets”. Each ultrafilter F on a set X defines a poset (of subsets ordered by inclusion), but I find it more suggestive to consider instead the opposite F^{op}, where U \leq V in F^{op} means V \subseteq U — so that the further or deeper you go in F^{op}, the smaller or more concentrated the element. Since F is closed under finite intersections, F^{op} has finite joins, so that F^{op} is directed (any two elements have an upper bound), just like the elements of a net (or more pedantically, the domain of a net). I call an ultrafilter a “fat net” because its elements, being subsets of X, are “fatter” than mere points.

Intuitively speaking, ultrafilters as nets “move in a definite direction”, in the sense that given an element U \in F, however far in the net, and given a subset T \subseteq U, the ultrafilter-as-net sniffs out a direction in which to proceed, “tunneling” either into T if T \in F, or into its relative complement U \cap \neg T if this belongs to F. In the case of a principal ultrafilter, there is a final element x of the net; otherwise not (but we can think of a nonprincipal ultrafilter as ending at an “ideal point” of the set X if we want).

Since the intuitive imagery here is already vaguely topological, we may as well make the connection with topology more precise. So, suppose now that X comes equipped with a topology. We say that an ultrafilter F on X converges to a point x \in X if each open set U containing x (or each neighborhood of x) belongs to the ultrafilter. In other words, by going deep enough into the ultrafilter-as-net, you get within any chosen neighborhood of the point. We write F \to x to say that F converges to x.

General topology can be completely developed in terms of the notion of ultrafilter convergence, often very efficiently. For example, starting with any relation whatsoever between ultrafilters and points,

c \subseteq \beta(X) \times X,

we can naturally define a topology \mbox{top}(c) on X so that

F \to x with respect to \mbox{top}(c) whenever (F, x) \in c.

Let’s tackle that in stages: in order for the displayed condition to hold, a neighborhood of x must belong to every ultrafilter F for which (F, x) \in c. This suggests that we try defining the filter N_x of neighborhoods of x to be the intersection of ultrafilters

N_x = \bigcap_{F: (F, x) \in c} F.

Then define a subset U \subseteq X to be open if it is a neighborhood of all the points it contains. In other words, define U to be open if

\forall_{(F, x) \in c} x \in U \Rightarrow U \in F.

Proposition 3: This defines a topology, \mbox{top}(c).

Proof: Since X \in F for every ultrafilter F, it is clear that X is open; also, it is vacuously true that the empty set is open. If U, V are open, then for all (F, x) \in c, whenever x \in U \cap V, we have x \in U and x \in V, so that U \in F and V \in F by openness, whence U \cap V \in F since F is closed under intersections. So U \cap V is also open. Finally, suppose U_i is a collection of open sets. For all (F, x) \in c, if x \in \bigcup_i U_i, then x \in U_i for some i, so that U_i \in F by openness, whence \bigcup_i U_i \in F since ultrafilters are upward closed. So \bigcup_i U_i is also open. \Box.

Let’s recap: starting from a topology \tau on X, we’ve defined a convergence relation \mbox{conv}(\tau) \subseteq \beta(X) \times X (consisting of pairs (F, x) such that F \to x), and conversely, given any relation c \subseteq \beta(X) \times X, we’ve defined a topology \mbox{top}(c) on X. What we actually have here is a Galois connection where

c \subseteq \mbox{conv}(\tau) if and only if \tau \subseteq \mbox{top}(c)

Of course not every relation c \subseteq \beta(X) \times X is the convergence relation of a topology, so we don’t quite have a Galois correspondence (that is, \mbox{conv} and \mbox{top} are not quite inverse to one another). But, it is true that every topology \tau is the topology of its ultrafilter convergence relation, i.e., \tau = \mbox{top(conv}(\tau)). For this, it suffices to show that every neighborhood filter N_x is the intersection of the ultrafilters that contain it. But that is true of any filter:

Theorem 1: If N is a filter in PX and A \notin N, then there exists an ultrafilter F for which N \subseteq F and A \notin F.

Proof: First I claim \neg A \cap B \neq 0 for all B \in N; otherwise \neg A \cap B = 0 for some B \in N, whence B \subseteq \neg \neg A = A, so that A \in N since filters are upward closed, contradiction. It follows that N can be extended to the (proper) filter

\{C \in PX: \exists_{B \in N} \neg A \cap B \subseteq C\}

which in turn extends to some ultrafilter F, by proposition 2. Since \neg A \in F, we have A \notin F. \Box

Corollary 1: Every filter is the intersection of all the ultrafilters which contain it.

The ultrafilter convergence approach to topology is particularly convenient for studies of compactness:

Theorem 2: A space X is compact if and only if every ultrafilter F converges to at least one point. It is Hausdorff if and only if every ultrafilter converges to at most one point.

Proof: First suppose that X is compact, and (in view of a contradiction) that F converges to no point of X. This means that for every x \in X there is a neighborhood U_x which does not belong to F, or that \neg U_x \in F. Finitely many of these U_x cover X, by compactness. By De Morgan’s law, this means finitely many \neg U_x have empty intersection. But this would mean \emptyset \in F, since F is closed under finite intersections, contradiction.

In the reverse direction, suppose that every ultrafilter converges. We need to show that if C = \{U_i\}_{i \in I} is any collection of open subsets of X such that no finite subcollection covers X, then the union of the U_i cannot cover X. First, because no finite subcollection covers, we may construct a filter generated by the complements:

F = \{A \subseteq X: \bigcap_{j=1}^n \neg U_{i_j} \subseteq A \mbox{ for finitely many } U_{i_1}, \ldots, U_{i_n} \in C\}.

Extend this filter to an ultrafilter G; then by assumption \exists_{x \in X} G \to x. If some one of the U_i contained x, then U_i \in G by definition of convergence. But we also have \neg U_i \in F \subseteq G, and this is a contradiction. So, x lies outside the union of the U_i, as was to be shown.

Now let X be Hausdorff, and suppose that F \to x and F \to y. Let U_x, U_y be neighborhoods of x, y respectively with empty intersection. By definition of convergence, we have U_x, U_y \in F, whence \emptyset = U_x \cap U_y \in F, contradiction.

Conversely, suppose every ultrafilter converges to at most one point, and let x, y be two distinct points. Unless there are neighborhoods U_x, U_y of x, y respectively such that U_x \cap U_y = \emptyset (which is what we want), the smallest filter containing the two neighborhood filters N_x, N_y (that is to say, the join N_x \vee N_y in the poset of filters) is proper, and hence extends to an ultrafilter F. But then N_x \subseteq F and N_y \subseteq F, which is to say F \to x and F \to y, contradiction. \Box

Theorem 2 is very useful; among other things it paves the way for a clean and conceptual proof of Tychonoff’s theorem (that an arbitrary product of compact spaces is compact). For now we note that it says that a topology \tau is the topology of a compact Hausdorff space structure on X if and only if the convergence relation \mbox{conv}(\tau) \subseteq \beta(X) \times X is a function. And in practice, functions c: \beta(X) \to X which arise “naturally” tend to be such convergence relations, making X a compact Hausdorff space.

Here is our key example. Let B be a Boolean algebra, and let X = QB = \mbox{Bool}(B, \mathbf{2}), which we have identified with the set of ultrafilters in B. Define a map c: \beta(X) \to X by

\displaystyle \beta (QB) \cong QP^{op}QB \stackrel{Q\varepsilon_B}{\to} QB

where \varepsilon_B: P^{op}QB \to B was the counit (evaluated at B) of the adjunction P^{op} \dashv Q defined at the top of this post. Unpacking the definitions a bit, the map Q \varepsilon_B is the map \mbox{Bool}(i_B, \mathbf{2}), the result of applying the hom-functor \mbox{Bool}(-, \mathbf{2}) to

i_B: B \to P^{op}QB = \hom(\mbox{Bool}(B, \mathbf{2}), \mathbf{2}): b \mapsto (\phi \mapsto \phi(b))

Chasing this a little further, the map c “pulls back” an ultrafilter F \subseteq P^{op}QB to the ultrafilter i_B^{-1}(F) \subseteq B, viewed as an element of QB. We then topologize QB by the topology \mbox{top}(c).

This construction is about as “abstract nonsense” as it gets, but you have to admit that it’s pretty darned canonical! The topological space QB we get in this way is called the spectrum of the Boolean algebra B. If you’ve seen a bit of algebraic geometry, then you probably know another, somewhat more elementary way of defining the spectrum (of B as commutative ring), so we may as well make the connection explicit. However you define it, the result is a compact Hausdorff space structure with some other properties which make it very reminiscent of Cantor space.

It is first of all easy to see that X = QB is compact, i.e., that every ultrafilter F converges. Indeed, the relation c is a function \beta (QB) \to QB, and if you look at the condition for a set U to be open w.r.t. \mbox{top}(c),

\forall_{(F, x = c(F))} x \in U \Rightarrow U \in F,

you see immediately that F converges to x = c(F).

To get Hausdorffness, take two distinct points u, v \in QB (ultrafilters in B). Since these are distinct maximal filters, there exists b \in B such that b belongs to u but not to v, and then \neg b belongs to v but not to u. Define

U(b) := \{w \in QB: b \in w\}.

Proposition 4: U(b) is open in \mbox{top}(c).

Proof: We must check that for all ultrafilters F on QB, that

c(F) \in U(b) \Rightarrow U(b) \in F.

But c(F) = i_B^{-1}(F). By definition of U(b), we are thus reduced to checking that

b \in i_B^{-1}(F) \Rightarrow U(b) \in F

or that i_B(b) \in F \Rightarrow U(b) \in F. But i_B(b) \in P^{op}QB (as a subset of QB) is U(b)! \Box

As a result, U(b) and U(\neg b) are open sets containing the given points u, v. They are disjoint since in fact U(\neg b) = \neg U(b) (indeed, because i_B preserves negation). This gives Hausdorffness, and also that the U(b) are clopen (closed and open).

We actually get a lot more:

Proposition 5: The collection \{U(b): b \in B\} is a basis for the topology \mbox{top}(c) on QB.

Proof: The sets U(b) form a basis for some topology \tau, because U(b) \wedge U(c) = U(b \wedge c) (indeed, i_B preserves meets). By the previous proposition, \tau \subseteq \mbox{top}(c). So the identity on QB gives a continuous comparison map

QB_{\mbox{top}(c)} \to QB_{\tau}

between the two topologies. But a continuous bijection from a compact space to a Hausdorff space is necessarily a homeomorphism, so \tau = \mbox{top}(c). \Box

  • Remark: In particular, the canonical topology on \beta X = QP^{op}X is compact Hausdorff; this space is called the Stone-Cech compactification of (the discrete space) X. The methods exploited in this lecture can be used to show that in fact \beta X is the free compact Hausdorff space generated from the set X, meaning that the functor \beta is left adjoint to the underlying-set functor U: \mbox{CompHaus} \to Set. In fact, one can go rather further in this vein: a fascinating result (first proved by Eduardo Manes in his PhD thesis) is that the concept of compact Hausdorff space is algebraic (is monadic with respect to the monad \beta): there is a equationally defined theory where the class of J-ary operations (for each cardinal J) is coded by the set of ultrafilters \beta J, and whose models are precisely compact Hausdorff spaces. This goes beyond the scope of these lectures, but for the theory of monads, see the entertaining YouTube lectures by the Catsters!