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
in the categories of Boolean algebras and sets . 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 and are finite (which is manifestly untrue in general; for instance, if is a free Boolean algebra generated by a countable set, then for simple reasons of cardinality cannot be a power set).
What we have here is an adjoint pair of functors between the categories and of sets and Boolean algebras, each given by a hom-functor:
( acts the same way on objects and morphisms as , 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
given by the formula . [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 by any model of that theory.] The unit of the adjunction at is the function , and the counit at is the Boolean algebra map (regarded as a morphism mapping the other way in the opposite category ).
The functor 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 in a Boolean ring is the kernel of a (unique) ring map
i.e., has the form for some such map. Being an ideal, it is an additive subgroup such that implies . It follows that if , then , so is closed under finite joins (including the empty join ). Also, if and , then , so that is “downward-closed”.
Conversely, a downward-closed subset which is closed under finite joins is an ideal in (exercise!). Finally, if is a maximal ideal, then under the quotient map
we have that for all , either or , i.e., that either or .
Thus we have redefined the notion of maximal ideal in a Boolean algebra in the first-order theory of posets: a downward-closed set closed under finite joins, such that every element or its complement (but never both!) is contained in . [If both , then , whence for all (since and is downward-closed). But then isn’t a maximal (proper) ideal!]
The notion of ultrafilter is dual, so an ultrafilter in a Boolean algebra is defined to be a subset which
- Is upward-closed: if and , then ;
- Is closed under finite meets: if , then ;
- Satisfies dichotomy: for every , exactly one of belongs to .
If is a maximal ideal, then is an ultrafilter, and we have natural bijections between the following concepts:
Boolean algebra maps maximal ideals ultrafilters
so that is naturally identified with the set of ultrafilters in .
If is a set, then an ultrafilter on is by definition an ultrafilter in the Boolean algebra . Hence is identified with the set of ultrafilters on , usually denoted . The unit map
maps to an ultrafilter denoted , consisting of all subsets which contain , and called the principal ultrafilter generated by .
We saw that when is finite, the function (and therefore also ) 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 on contains a finite set , then is principal.
Proof: It is enough to show contains for some . If not, then contains the complement for every (by dichotomy), and therefore also the finite intersection
which contradicts the fact that .
It follows that nonprincipal ultrafilters can exist only on infinite sets , and that every cofinite subset of (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.
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 , 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 on a set defines a poset (of subsets ordered by inclusion), but I find it more suggestive to consider instead the opposite , where in means — so that the further or deeper you go in , the smaller or more concentrated the element. Since is closed under finite intersections, has finite joins, so that 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 , are “fatter” than mere points.
Intuitively speaking, ultrafilters as nets “move in a definite direction”, in the sense that given an element , however far in the net, and given a subset , the ultrafilter-as-net sniffs out a direction in which to proceed, “tunneling” either into if , or into its relative complement if this belongs to . In the case of a principal ultrafilter, there is a final element of the net; otherwise not (but we can think of a nonprincipal ultrafilter as ending at an “ideal point” of the set 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 comes equipped with a topology. We say that an ultrafilter on converges to a point if each open set containing (or each neighborhood of ) 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 to say that converges to .
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,
we can naturally define a topology on so that
with respect to whenever .
Let’s tackle that in stages: in order for the displayed condition to hold, a neighborhood of must belong to every ultrafilter for which . This suggests that we try defining the filter of neighborhoods of to be the intersection of ultrafilters
Then define a subset to be open if it is a neighborhood of all the points it contains. In other words, define to be open if
Proposition 3: This defines a topology, .
Proof: Since for every ultrafilter , it is clear that is open; also, it is vacuously true that the empty set is open. If are open, then for all , whenever , we have and , so that and by openness, whence since is closed under intersections. So is also open. Finally, suppose is a collection of open sets. For all , if , then for some , so that by openness, whence since ultrafilters are upward closed. So is also open. .
Let’s recap: starting from a topology on , we’ve defined a convergence relation (consisting of pairs such that ), and conversely, given any relation , we’ve defined a topology on . What we actually have here is a Galois connection where
if and only if
Of course not every relation is the convergence relation of a topology, so we don’t quite have a Galois correspondence (that is, and are not quite inverse to one another). But, it is true that every topology is the topology of its ultrafilter convergence relation, i.e., . For this, it suffices to show that every neighborhood filter is the intersection of the ultrafilters that contain it. But that is true of any filter:
Theorem 1: If is a filter in and , then there exists an ultrafilter for which and .
Proof: First I claim for all ; otherwise for some , whence , so that since filters are upward closed, contradiction. It follows that can be extended to the (proper) filter
which in turn extends to some ultrafilter , by proposition 2. Since , we have .
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 is compact if and only if every ultrafilter 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 is compact, and (in view of a contradiction) that converges to no point of . This means that for every there is a neighborhood which does not belong to , or that . Finitely many of these cover , by compactness. By De Morgan’s law, this means finitely many have empty intersection. But this would mean , since is closed under finite intersections, contradiction.
In the reverse direction, suppose that every ultrafilter converges. We need to show that if is any collection of open subsets of such that no finite subcollection covers , then the union of the cannot cover . First, because no finite subcollection covers, we may construct a filter generated by the complements:
Extend this filter to an ultrafilter ; then by assumption . If some one of the contained , then by definition of convergence. But we also have , and this is a contradiction. So, lies outside the union of the , as was to be shown.
Now let be Hausdorff, and suppose that and . Let be neighborhoods of respectively with empty intersection. By definition of convergence, we have , whence , contradiction.
Conversely, suppose every ultrafilter converges to at most one point, and let be two distinct points. Unless there are neighborhoods of respectively such that (which is what we want), the smallest filter containing the two neighborhood filters (that is to say, the join in the poset of filters) is proper, and hence extends to an ultrafilter . But then and , which is to say and , contradiction.
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 is the topology of a compact Hausdorff space structure on if and only if the convergence relation is a function. And in practice, functions which arise “naturally” tend to be such convergence relations, making a compact Hausdorff space.
Here is our key example. Let be a Boolean algebra, and let , which we have identified with the set of ultrafilters in . Define a map by
where was the counit (evaluated at ) of the adjunction defined at the top of this post. Unpacking the definitions a bit, the map is the map , the result of applying the hom-functor to
Chasing this a little further, the map “pulls back” an ultrafilter to the ultrafilter , viewed as an element of . We then topologize by the topology .
This construction is about as “abstract nonsense” as it gets, but you have to admit that it’s pretty darned canonical! The topological space we get in this way is called the spectrum of the Boolean algebra . If you’ve seen a bit of algebraic geometry, then you probably know another, somewhat more elementary way of defining the spectrum (of 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 is compact, i.e., that every ultrafilter converges. Indeed, the relation is a function , and if you look at the condition for a set to be open w.r.t. ,
you see immediately that converges to .
To get Hausdorffness, take two distinct points (ultrafilters in ). Since these are distinct maximal filters, there exists such that belongs to but not to , and then belongs to but not to . Define
Proposition 4: is open in .
Proof: We must check that for all ultrafilters on , that
But . By definition of , we are thus reduced to checking that
or that . But (as a subset of ) is !
As a result, and are open sets containing the given points . They are disjoint since in fact (indeed, because preserves negation). This gives Hausdorffness, and also that the are clopen (closed and open).
We actually get a lot more:
Proposition 5: The collection is a basis for the topology on .
Proof: The sets form a basis for some topology , because (indeed, preserves meets). By the previous proposition, . So the identity on gives a continuous comparison map
between the two topologies. But a continuous bijection from a compact space to a Hausdorff space is necessarily a homeomorphism, so .
- Remark: In particular, the canonical topology on is compact Hausdorff; this space is called the Stone-Cech compactification of (the discrete space) . The methods exploited in this lecture can be used to show that in fact is the free compact Hausdorff space generated from the set , meaning that the functor is left adjoint to the underlying-set functor . 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 ): there is a equationally defined theory where the class of -ary operations (for each cardinal ) is coded by the set of ultrafilters , 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!
3 comments
Comments feed for this article
July 18, 2008 at 6:01 pm
Todd Trimble
I had meant (but then forgot) to refer to Terence Tao’s excellent exposition on ultrafilters here.
September 1, 2008 at 1:51 am
ZFC and ETCS: Elementary Theory of the Category of Sets « Todd and Vishal’s blog
[…] My original intent was to blog about that, as a kind of off-shoot of the general discussion of ultrafilters I started in connection with the series on Stone duality, and because it seems kind of cool. And I […]
December 23, 2008 at 6:49 am
Recent Links Tagged With "monads" - JabberTags
[…] on Wed 17-12-2008 functional programming and monads Saved by NoitacudE on Wed 17-12-2008 Ultrafilter convergence, compactness, and the spectrum of a … Saved by FrustratedSinger on Mon 08-12-2008 monad functions Saved by shougeki on Sun 07-12-2008 […]