Recently, I have begun to appreciate the use of ultrafilters to clean up proofs in certain areas of mathematics. I’d like to talk a little about how this works, but first I’d like to give a hefty amount of motivation for the definition of an ultrafilter.
Terence Tao has already written a great introduction to ultrafilters with an eye towards nonstandard analysis. I’d like to introduce them from a different perspective. Some of the topics below are also covered in these posts by Todd Trimble.
An idempotent of a ring is an element such that . Idempotents which are central (that is, which commute with all elements of ) occupy a special place in ring theory because of the following observation. If is a left -module, then every can be uniquely written as where the first term satisfies , hence is fixed by , and the second term satisfies , hence is annihilated by . Moreover, since is central, the action of respects this decomposition. It follows that breaks up into a direct sum of -modules, and acts as projection onto the first summand. Since it follows that is also idempotent and acts as projection onto the second summand.
Example. If where is a finite group, then is a central idempotent. On any left -module (that is, representation of ), it acts as projection onto the invariant subspace, and this fact is fundamental to the basics of the representation theory of finite groups. More generally, if is the character of some irreducible representation , then is a central idempotent and acts as projection onto the sum of the summands isomorphic to . (Exercise: classify the central idempotents of .)
Example. If is commutative and is idempotent, then is a left -module, hence breaks into a direct sum where acts as projection onto the first factor and acts as projection onto the second factor. As a direct sum of left -modules this is in fact a direct product of rings, so . On the geometric side, this implies that is a disjoint union of and , so idempotents disconnect the spectrum. One way to see this is that if is a quotient of by a prime ideal, then the image of in is idempotent. But the only idempotents in an integral domain are and . Thus can be regarded as a function on which takes the value on some points (those for which ) and the value on other points (those for which ). Since is continuous with respect to the Zariski topology, it follows that these two subspaces are disconnected from each other.
With the second example above in mind, we make the following definition.
Definition: A Boolean ring is a ring satisfying for all .
In other words, every element of a Boolean ring is idempotent. This implies , hence for all , so Boolean rings have characteristic . In turn this implies that , hence , so Boolean rings are commutative. In fact, the category of Boolean rings is isomorphic (not just equivalent!) to the category of Boolean algebras, so are a disguised way to talk about basic logical operations.
Example. For any set , the space of functions from to is a Boolean ring which can naturally be identified with the (indicator functions of) subsets of . In terms of subsets, addition corresponds to symmetric difference and multiplication corresponds to intersection. From a logical perspective, one should think of the elements of as being “false” and “true” respectively, of addition as logical XOR, and of multiplication as logical AND.
Example. The forgetful functor sending a Boolean ring to its underlying set has a left adjoint sending a set to the free Boolean ring on . This is the commutative -algebra freely generated by subject to the relations , and is a commutative-algebraic setting for propositional logic where is the set of primitive propositions. As above, the sum of two propositions is their logical XOR and their product is logical AND.
If is a Boolean ring, then either or there is some which is not equal to or . Then is a central idempotent, hence is a direct product of two Boolean rings. In particular, if is finite, then by induction is the direct product of a finite number of copies , hence is isomorphic to for some finite set . So the only finite Boolean rings are the obvious ones.
Spectra of Boolean rings
Whenever we meet a commutative ring, we should ask what its spectrum is. If is a Boolean ring and a prime ideal, then is a Boolean ring which is also an integral domain. But since implies , the only such Boolean ring is , which is also a field. Hence every prime ideal in a Boolean ring is maximal. Thus a nonzero prime ideal of is the same thing as a maximal ideal, which is the same thing as the kernel of a morphism (which must be surjective since morphisms preserve units). If one interprets as a set of logical propositions, then a morphism is the same thing as a consistent assignment of truth values to elements of .
Note that since every element of a Boolean ring is idempotent, Boolean rings have no nontrivial nilpotents, so the nilradical of a Boolean ring is . Since the nilradical is equal to the intersection of the prime ideals, we know that the intersection of the prime ideals is , and since the nonzero prime ideals of a Boolean ring are all maximal, we know that the Jacobson radical of a Boolean ring is . It follows that if for all maximal ideals , then in , so an element of a Boolean ring is faithfully represented as a function .
If is finite, then we know that is isomorphic to for some finite set . Let denote the function which is equal to on and elsewhere; these functions generate . Let be a surjective morphism. Then for some (by surjectivity), and if for some other , then , which contradicts . It follows that is the evaluation map at , hence and every function defines an element of . It follows that the Zariski topology on is discrete.
If is infinite, we should expect that has nontrivial topology (given by the Zariski topology as usual), so elements of at best correspond to a subring of the continuous functions . This suggests that it would be a good idea to study the Stone functor
sending a topological space to the Boolean ring of continuous functions to (given the discrete topology). Equivalently, is isomorphic to the Boolean ring of (indicator functions of) clopen subsets of . If is locally connected, this ring is precisely the ring of functions constant on each connected component of , but this is false in general. Given that we already have a functor
sending a Boolean ring to its spectrum, we might expect that the two are (contravariantly) adjoint. And in fact they are!
Proposition: There is a natural isomorphism
Proof. It suffices to show that both sides can be identified with the set of functions which are Boolean ring homomorphisms for fixed and which are continuous for fixed . These conditions are already enough to identify it with the RHS, so it remains to identify it with the LHS. Given a function satisfying the above conditions we certainly get a set-theoretic map sending to the kernel of the morphism , so it remains to show that this map is continuous. The basic closed sets in are of the form
for , so it suffices to show that the preimage of any such set is closed in . But the preimage of is precisely the set of all such that the morphism evaluates to zero. Since is equipped with the discrete topology, any function which is continuous for fixed is continuous in the product topology, so the set of satisfying this condition is the preimage of a closed point under a continuous map, hence continuous. So the result follows.
What do we get out of this? As a contravariant adjoint, it now follows that sends colimits to limits. This is important for the following reason. Given , write down the diagram of finite subrings of , where there is a morphism from a subring to another subring if and only if . These morphisms satisfy the compatibility relation . In addition, the natural injections are compatible with this diagram in the sense that .
It then follows that is the colimit of the above diagram. In many algebraic categories, colimits of diagrams where all the objects embed into each other behave much like unions in the category of sets, so this isn’t too surprising. But this gives
where the RHS is the limit of the following diagram in : the objects are the spectra of the finite subrings of , and there is a morphism induced from each inclusion . Since the spectra of finite Boolean rings are finite discrete spaces, this is a limit of finite discrete spaces.
Definition: A limit of finite discrete spaces in is a profinite set.
This is a generalization of the definition of a profinite group, which is a limit of finite discrete groups. We now know that the spectrum of any Boolean algebra is a profinite set. Explicitly, let be a collection of finite discrete spaces equipped with a compatible collection of morphisms . Then the colimit of this diagram can be constructed as the subset of elements the Cartesian product satisfying for all and equipped with the subspace topology from the product topology on . Now, is definitely equipped with projection morphisms which are continuous by the definition of the product topology and compatible with the morphisms by construction, so everything is as it should be.
is a product of finite discrete spaces, which are compact, Hausdorff, and totally disconnected. It follows that itself is compact, Hausdorff, and totally disconnected (we will get back to this use of Tychonoff’s theorem later). What does that say about ? Since the requirement that is equivalent to the requirement that the continuous functions and agree, it follows that is a closed subset of , and since it carries the subspace topology it follows that itself is compact, Hausdorff, and totally disconnected; that is, it is a Stone space.
In particular, it follows that , for a discrete infinite set , cannot just be , since with the discrete topology is noncompact; it must be some compactification of . In fact, we will see later that it is the Stone-Čech compactification of .
So, to summarize: we know that if is a Boolean ring, is the limit of a diagram of finite sets in , hence compact, Hausdorff, and totally disconnected. We also know that the map is injective (and functorial). We might suspect that it is in fact an isomorphism. This is true, but we’ll wait until slightly later to prove it. For now, we can prove the corresponding result in the other direction.
Proposition: Suppose is a Stone space. Then the map is a homeomorphism. (Hence every Stone space is a profinite set.)
Proof. Let . Then clearly every element gives a morphism ; let be the corresponding maximal ideal. Suppose is a maximal ideal different from all of the ; then for each it contains an element not vanishing at . The sets on which each do not vanish form an open cover of which, by compactness, has a finite subcover corresponding to elements . By taking unions, it follows that generate the unit ideal; contradiction. Hence there exists no such maximal ideal.
It remains to check that the topologies match. First we need to show that the maximal ideals are all distinct. A standard lemma, which I just learned about on math.SE, asserts that the components and quasicomponents of a compact Hausdorff space coincide. Since is also totally disconnected, it follows that given we can find a partition into disjoint open sets with . It follows that there exists a continuous function such that , hence the ideals are in fact distinct.
Now, since the topology on is initial with respect to the morphisms given by elements of , it follows that the topology on is stronger than or the same as the topology on . But since they are both compact Hausdorff, by Lemma 1 in the link the topologies must agree.
(Compare with the argument from this previous blog post about recovering the topology of a compact Hausdorff space from the ring . Here total disconnectedness takes the place of Urysohn’s lemma.)
What do the maximal ideals of a Boolean ring actually look like? We know that is an ideal if and only if and . For Boolean rings, an equivalent set of conditions is more convenient. Define a partial order on as follows:
When , this is precisely the usual order on subsets of . In particular, note that is the intersection of the subsets corresponding to and , so , hence as expected. In fact, the intersection has a universal property: if then , hence , so . So the intersection is actually the infimum for any Boolean ring.
If one thinks of the elements of as logical propositions, then turns out to correspond to logical implication . Indeed, if is a consistent truth assignment, then , hence , so if then ; in other words, whenever is true, is also true.
In any case, it follows that if is an ideal, and with , then as well. So ideals are downward closed. In addition, if then . This is an element, which we might as well call the union of and , which satisfies and , hence . So ideals are directed. (When , then this is precisely the usual union operation on subsets of .) Like the intersection, the union has a universal property: it is the supremum of and .
We claim that these two conditions together already imply that is an ideal. Indeed, if and then , hence by downward closure . And if then by directedness there is some such that and by the universal property of union, . But then . (Note that the map is order-reversing on and, when , corresponds to complement of subsets.) This result motivates the general definition of an order ideal.
So we have a characterization of ideals. It remains to characterize maximal ideals among ideals.
Proposition: Let be a maximal ideal of . For any , either or , and not both.
Proof. Let be the corresponding quotient map. Then either or , and not both.
In fact, this condition characterizes maximal ideals among ideals, since if has this property, we cannot add to an element not already in it without forcing (since ). Note that in particular , so . So, to summarize, a maximal ideal is a subset of such that
- If , then there is some such that . (Equivalently, .)
- If with , then .
- For any , either or , but not both. (In particular, and .)
The last condition implies that the complement of a maximal ideal in is precisely the set . Running this condition through the other two conditions, and remembering that is order-reversing, we conclude that the following characterizes subsets which can be complements of maximal ideals:
- If , then there is some such that . (Equivalently, .)
- If with , then .
- For any , either or , but not both. (In particular, and .)
When is the ring of functions , this recovers precisely the usual definition of an ultrafilter on : a collection of subsets which is closed under intersection, upward closed, and maximal. (We will also refer to this as an ultrafilter on in an abuse of notation.)
Again, if one thinks of elements of as logical propositions, then an ultrafilter on is a set of logical propositions which is closed under AND and implication and which is consistent (does not imply ); in other words, it is a maximal consistent deductively closed set. So ultrafilters are very natural objects from the point of view of propositional logic (indeed the second axiom is just modus ponens).
We now know that can be identified with the set of ultrafilters on . Knowing this, we will freely switch between thinking of the elements of as maximal ideals, as ultrafilters, and as morphisms .
Let’s give a direct proof that is a Stone space using both the maximal ideal and ultrafilter language. Recall that the Zariski topology is given by the basic closed sets (which are also open) . Note that is the complement of . Note also that since by primality, the basic closed sets are already closed under finite union, so every closed set is an intersection of basic closed sets.
In terms of ultrafilters, the Zariski topology can equivalently be described by the basic open sets
where is an ultrafilter instead of a maximal ideal. (This is just the complement of .) Note that is the complement of . Note also that since , the basic open sets are already closed under finite intersection, so every open set is a union of basic open sets.
Proposition: is compact, Hausdorff, and totally disconnected.
Proof. Let be distinct maximal ideals. Then there is which is not in , hence while . Since these sets are disjoint and open, is Hausdorff. Since their union is the whole space, is totally disconnected. (Dually, let be distinct ultrafilters. Then there is which is not in , hence and . Since these sets are disjoint and open, is Hausdorff. Since their union is the whole space, is totally disconnected.)
To prove that is compact, it suffices to show that the finite intersection property holds for a collection of basic closed sets . Suppose any finite collection of these sets has a nontrivial intersection. Then there exists a maximal ideal containing any finite subset of the . It follows that the ideal generated by the is proper, since if and only if is generated by some finite subset of the (which contradicts the above). (Dually, there exists an ultrafilter avoiding any finite subset of the , hence containing any finite subset of the , so the filter generated by the is proper.)
By the Boolean prime ideal theorem, there exists a maximal ideal containing . But now and we are done. (Dually, by the ultrafilter lemma, there exists an ultrafilter containing . But now and we are done.)
Remark: The BPIT and the ultrafilter lemma are equivalent, as it is not hard to see. They can be proven from Zorn’s lemma but are strictly weaker than it, although they are independent of ZF.
Now we finally prove the following.
Theorem: Let be a Boolean ring. The injection is surjective.
Proof. Let be continuous. Then is open, hence is a union of basic open sets . Since is also closed, it is compact, so by compactness the open sets have a finite subcover . But it’s not hard to see that , so it follows that . The conclusion follows.
Together with our previous results and some fiddling with morphisms, it follows that in fact the category of Boolean rings is contravariantly equivalent to the category of Stone spaces.
Let be a set; recall that the free Boolean ring on is a setting for propositional logic where takes on the role of the set of primitive propositions. By freeness, where is the forgetful functor from Boolean rings to sets, so it follows that
so , and one readily verifies that the Zariski topology on is the product topology. In logical terms, a consistent assignment of truth values to propositions is determined by an arbitrary assignment of truth values to the primitive propositions.
The direct proof of compactness we gave above translates into a direct proof of the compactness theorem in propositional logic, as follows. We say that a subset has a model if there exists a morphism such that . When , this is equivalent to the statement that it is possible to assign truth values to the elements of so that all of the statements in are true. This condition is also equivalent to the condition that is contained in an ultrafilter. Then the compactness theorem states that if every finite subset of has a model, then has a model. But the set of ultrafilters containing some is closed in , so this immediately follows by the finite intersection property.
Remark: Since we gave a direct proof of the compactness of that does not use Tychonoff’s theorem, it follows that Tychonoff’s theorem for discrete spaces can be proven from the Boolean prime ideal theorem or, equivalently, the ultrafilter lemma. In fact, they are all equivalent, and also all equivalent to the compactness theorem!