Boolean rings, ultrafilters, and Stone’s representation theorem

« A little more about zeta functions and statistical mechanics

Boolean rings, ultrafilters, and Stone’s representation theorem

November 22, 2010 by Qiaochu Yuan

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.

Idempotents

An idempotent of a ring $R$ is an element $r \in R$ such that $r^2 = r$ . Idempotents which are central (that is, which commute with all elements of $R$ ) occupy a special place in ring theory because of the following observation. If $M$ is a left $R$ -module, then every $m \in M$ can be uniquely written as $m = rm + (m - rm)$ where the first term satisfies $r(rm) = rm$ , hence is fixed by $r$ , and the second term satisfies $r(m - rm) = 0$ , hence is annihilated by $r$ . Moreover, since $r$ is central, the action of $R$ respects this decomposition. It follows that $M$ breaks up into a direct sum $M = M_1 \oplus M_0$ of $R$ -modules, and $r$ acts as projection onto the first summand. Since $r^2 = r \Leftrightarrow r(1 - r) = 0$ it follows that $1 - r$ is also idempotent and acts as projection onto the second summand.

Example. If $R = \mathbb{C}[G]$ where $G$ is a finite group, then $\displaystyle \frac{1}{|G|} \sum_{g \in G} g$ is a central idempotent. On any left $R$ -module (that is, representation of $G$ ), 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 $\chi$ is the character of some irreducible representation $V$ , then $\displaystyle \frac{1}{|G|} \sum_{g \in G} \overline{\chi(g)} g$ is a central idempotent and acts as projection onto the sum of the summands isomorphic to $V$ . (Exercise: classify the central idempotents of $\mathbb{C}[G]$ .)

Example. If $R$ is commutative and $r \in R$ is idempotent, then $R$ is a left $R$ -module, hence breaks into a direct sum $R_1 \oplus R_0$ where $r$ acts as projection onto the first factor and $1 - r$ acts as projection onto the second factor. As a direct sum of left $R$ -modules this is in fact a direct product of rings, so $R \simeq rR \times (1 - r) R$ . On the geometric side, this implies that $\text{Spec } R$ is a disjoint union of $\text{Spec } rR$ and $\text{Spec } (1-r)R$ , so idempotents disconnect the spectrum. One way to see this is that if $R \to R/P$ is a quotient of $R$ by a prime ideal, then the image of $r$ in $R/P$ is idempotent. But the only idempotents in an integral domain are $0$ and $1$ . Thus $r$ can be regarded as a function on $\text{Spec } R$ which takes the value $0$ on some points (those for which $r \equiv 0 \bmod P$ ) and the value $1$ on other points (those for which $r \equiv 1 \bmod P$ ). Since $r$ is continuous with respect to the Zariski topology, it follows that these two subspaces are disconnected from each other.

Boolean rings

With the second example above in mind, we make the following definition.

Definition: A Boolean ring $B$ is a ring satisfying $b^2 = b$ for all $b \in B$ .

In other words, every element of a Boolean ring is idempotent. This implies $(b + 1)^2 = b + 1 = b^2 + 2b + 1 = b + 1 + 2b$ , hence $2b = 0$ for all $b$ , so Boolean rings have characteristic $2$ . In turn this implies that $(a + b)^2 = a + b = a + b + ab + ba$ , hence $ab = ba$ , 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 $S$ , the space $\text{Hom}(S, \mathbb{F}_2)$ of functions from $S$ to $\mathbb{F}_2$ is a Boolean ring which can naturally be identified with the (indicator functions of) subsets of $S$ . 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 $\mathbb{F}_2$ as being “false” and “true” respectively, of addition as logical XOR, and of multiplication as logical AND.

Example. The forgetful functor $U : \text{BRing} \to \text{Set}$ sending a Boolean ring to its underlying set has a left adjoint $F : \text{Set} \to \text{BRing}$ sending a set $S$ to the free Boolean ring on $S$ . This is the commutative $\mathbb{F}_2$ -algebra freely generated by $s \in S$ subject to the relations $s^2 = s \forall s \in S$ , and is a commutative-algebraic setting for propositional logic where $S$ is the set of primitive propositions. As above, the sum of two propositions is their logical XOR and their product is logical AND.

If $B$ is a Boolean ring, then either $B \simeq \mathbb{F}_2$ or there is some $b \in B$ which is not equal to $0$ or $1$ . Then $b$ is a central idempotent, hence $B$ is a direct product $B \simeq bB \times (1-b)B$ of two Boolean rings. In particular, if $B$ is finite, then by induction $B$ is the direct product of a finite number of copies $\mathbb{F}_2$ , hence is isomorphic to $\text{Hom}(S, \mathbb{F}_2)$ for some finite set $S$ . 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 $B$ is a Boolean ring and $P$ a prime ideal, then $B/P$ is a Boolean ring which is also an integral domain. But since $b^2 = b$ implies $b(1 - b) = 0$ , the only such Boolean ring is $\mathbb{F}_2$ , which is also a field. Hence every prime ideal in a Boolean ring is maximal. Thus a nonzero prime ideal of $B$ is the same thing as a maximal ideal, which is the same thing as the kernel of a morphism $B \to \mathbb{F}_2$ (which must be surjective since morphisms preserve units). If one interprets $B$ as a set of logical propositions, then a morphism $B \to \mathbb{F}_2$ is the same thing as a consistent assignment of truth values to elements of $B$ .

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 $\{ 0 \}$ . Since the nilradical is equal to the intersection of the prime ideals, we know that the intersection of the prime ideals is $\{ 0 \}$ , and since the nonzero prime ideals of a Boolean ring are all maximal, we know that the Jacobson radical of a Boolean ring is $\{ 0 \}$ . It follows that if $b \equiv 0 \bmod m$ for all maximal ideals $m$ , then $b = 0$ in $B$ , so an element of a Boolean ring is faithfully represented as a function $\text{Spec } B \to \mathbb{F}_2$ .

If $B$ is finite, then we know that $B$ is isomorphic to $\text{Hom}(S, \mathbb{F}_2)$ for some finite set $S$ . Let $1_s$ denote the function which is equal to $1$ on $s$ and $0$ elsewhere; these functions generate $B$ . Let $\phi : B \to \mathbb{F}_2$ be a surjective morphism. Then $\phi(1_s) = 1$ for some $s \in S$ (by surjectivity), and if $\phi(1_r) = 1$ for some other $r$ , then $\phi(1_s 1_r) = 1$ , which contradicts $1_s 1_r = 0$ . It follows that $\phi$ is the evaluation map at $s$ , hence $\text{Spec } B \simeq S$ and every function $\text{Spec } B \to \mathbb{F}_2$ defines an element of $B$ . It follows that the Zariski topology on $\text{Spec } B$ is discrete.

If $B$ is infinite, we should expect that $\text{Spec } B$ has nontrivial topology (given by the Zariski topology as usual), so elements of $B$ at best correspond to a subring of the continuous functions $\text{Spec } B \to \mathbb{F}_2$ . This suggests that it would be a good idea to study the Stone functor

$\displaystyle \text{Hom}_{\text{Top}}(-, \mathbb{F}_2) : \text{Top} \to \text{BRing}$

sending a topological space $T$ to the Boolean ring of continuous functions to $\mathbb{F}_2$ (given the discrete topology). Equivalently, $\text{Hom}_{\text{Top}}(T, \mathbb{F}_2)$ is isomorphic to the Boolean ring of (indicator functions of) clopen subsets of $T$ . If $T$ is locally connected, this ring is precisely the ring of functions constant on each connected component of $T$ , but this is false in general. Given that we already have a functor

$\text{Spec} = \text{Hom}_{\text{BRing}}(-, \mathbb{F}_2) : \text{BRing} \to \text{Top}$

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

$\displaystyle \text{Hom}_{\text{Top}}(T, \text{Hom}_{\text{BRing}}(B, \mathbb{F}_2)) \simeq \text{Hom}_{\text{BRing}}(B, \text{Hom}_{\text{Top}}(T, \mathbb{F}_2))$ .

Proof. It suffices to show that both sides can be identified with the set of functions $B \times T \to \mathbb{F}_2$ which are Boolean ring homomorphisms for fixed $t \in T$ and which are continuous for fixed $b \in B$ . These conditions are already enough to identify it with the RHS, so it remains to identify it with the LHS. Given a function $f : B \times T \to \mathbb{F}_2$ satisfying the above conditions we certainly get a set-theoretic map $T \to \text{Spec } B$ sending $t \in T$ to the kernel of the morphism $f_t : B \times \{ t \} \to \mathbb{F}_2$ , so it remains to show that this map is continuous. The basic closed sets in $\text{Spec } B$ are of the form

$\displaystyle C_b = \{ m : b \in m \}$

for $b \in B$ , so it suffices to show that the preimage of any such set is closed in $T$ . But the preimage of $C_b$ is precisely the set of all $t \in T$ such that the morphism $f_b : \{ b \} \times T \to \mathbb{F}_2$ evaluates to zero. Since $B$ is equipped with the discrete topology, any function $f : B \times T \to \mathbb{F}_2$ which is continuous for fixed $b$ is continuous in the product topology, so the set of $t \in T$ 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 $\text{Spec}$ sends colimits to limits. This is important for the following reason. Given $B$ , write down the diagram of finite subrings of $B$ , where there is a morphism $\phi_{i, j}$ from a subring $B_i$ to another subring $B_j$ if and only if $B_i \subset B_j$ . These morphisms satisfy the compatibility relation $\phi_{i, j} \circ \phi_{k, i} = \phi_{k, j}$ . In addition, the natural injections $\phi_i : B_i \to B$ are compatible with this diagram in the sense that $\phi_i \circ \phi_{j, i} = \phi_j$ .

It then follows that $B$ 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

$\displaystyle \text{Spec } B = \text{Spec colim } B_i = \lim \text{Spec } B_i$

where the RHS is the limit of the following diagram in $\text{Top}$ : the objects are the spectra of the finite subrings of $B$ , and there is a morphism $\text{Spec } B_j \to \text{Spec } B_i$ induced from each inclusion $B_i \subset B_j$ . 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 $\text{Top}$ 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 $S_i, i \in I$ be a collection of finite discrete spaces equipped with a compatible collection of morphisms $\phi_{i,j} : S_i \to S_j$ . Then the colimit $S$ of this diagram can be constructed as the subset of elements $\prod_i s_i$ the Cartesian product $\prod_i S_i$ satisfying $\phi_{i,j}(s_j) = s_i$ for all $i, j$ and equipped with the subspace topology from the product topology on $\prod_i S_i$ . Now, $S$ is definitely equipped with projection morphisms $\phi_i : S \to S_i$ which are continuous by the definition of the product topology and compatible with the morphisms $\phi_{i,j}$ by construction, so everything is as it should be.

$\prod S_i$ is a product of finite discrete spaces, which are compact, Hausdorff, and totally disconnected. It follows that $\prod S_i$ itself is compact, Hausdorff, and totally disconnected (we will get back to this use of Tychonoff’s theorem later). What does that say about $S$ ? Since the requirement that $\phi_{i,j}(s_j) = s_i$ is equivalent to the requirement that the continuous functions $\phi_{i,j} \circ \phi_j$ and $\phi_i$ agree, it follows that $S$ is a closed subset of $\prod S_i$ , and since it carries the subspace topology it follows that $S$ itself is compact, Hausdorff, and totally disconnected; that is, it is a Stone space.

In particular, it follows that $\text{Spec Hom}(S, \mathbb{F}_2)$ , for a discrete infinite set $S$ , cannot just be $S$ , since $S$ with the discrete topology is noncompact; it must be some compactification of $S$ . In fact, we will see later that it is the Stone-Čech compactification $\beta S$ of $S$ .

So, to summarize: we know that if $B$ is a Boolean ring, $\text{Spec } B$ is the limit of a diagram of finite sets in $\text{Top}$ , hence compact, Hausdorff, and totally disconnected. We also know that the map $B \mapsto \text{Hom}_{\text{Top}}(\text{Spec } B, \mathbb{F}_2)$ 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 $T$ is a Stone space. Then the map $T \mapsto \text{Spec Hom}_{\text{Top}}(T, \mathbb{F}_2)$ is a homeomorphism. (Hence every Stone space is a profinite set.)

Proof. Let $B = \text{Hom}_{\text{Top}}(T, \mathbb{F}_2)$ . Then clearly every element $t \in T$ gives a morphism $B \to \mathbb{F}_2$ ; let $m_t$ be the corresponding maximal ideal. Suppose $m$ is a maximal ideal different from all of the $m_t$ ; then for each $t \in T$ it contains an element $b_t \in B$ not vanishing at $t$ . The sets $U_{b_t}$ on which each $b_t$ do not vanish form an open cover of $T$ which, by compactness, has a finite subcover corresponding to elements $b_{t_1}, ... b_{t_n}$ . By taking unions, it follows that $b_{t_1}, ... b_{t_n}$ 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 $m_t$ 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 $T$ is also totally disconnected, it follows that given $s, t \in T$ we can find a partition $T = U \cup V$ into disjoint open sets with $s \in U, t \in V$ . It follows that there exists a continuous function $f : T \to \mathbb{F}_2$ such that $f(s) = 0, f(t) = 1$ , hence the ideals $m_t, m_s$ are in fact distinct.

Now, since the topology on $\text{Spec } B$ is initial with respect to the morphisms given by elements of $B$ , it follows that the topology on $T$ is stronger than or the same as the topology on $\text{Spec } B$ . 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 $X$ from the ring $\text{Hom}_{\text{Top}}(X, \mathbb{R})$ . Here total disconnectedness takes the place of Urysohn’s lemma.)

Ultrafilters

What do the maximal ideals of a Boolean ring $B$ actually look like? We know that $I$ is an ideal if and only if $a \in I, b \in I \Rightarrow a + b \in I$ and $a \in I, r \in B \Rightarrow ar \in I$ . For Boolean rings, an equivalent set of conditions is more convenient. Define a partial order on $B$ as follows:

$\displaystyle a \le b \Leftrightarrow ab = a$ .

When $B = \text{Hom}(S, \mathbb{F}_2)$ , this is precisely the usual order on subsets of $S$ . In particular, note that $ab$ is the intersection of the subsets corresponding to $a$ and $b$ , so $(ab)a = ab, (ab)b = ab$ , hence $ab \le a, ab \le b$ as expected. In fact, the intersection has a universal property: if $i \le a, i \le b$ then $ai = i, bi = i$ , hence $abi = i$ , so $i \le ab$ . So the intersection is actually the infimum for any Boolean ring.

If one thinks of the elements of $B$ as logical propositions, then $a \le b$ turns out to correspond to logical implication $a \Rightarrow b$ . Indeed, if $\phi : B \to \mathbb{F}_2$ is a consistent truth assignment, then $a \le b \Leftrightarrow ab = a$ , hence $\phi(a) \phi(b) = \phi(a)$ , so if $\phi(a) = 1$ then $\phi(b) = 1$ ; in other words, whenever $a$ is true, $b$ is also true.

In any case, it follows that if $I$ is an ideal, $b \in I$ and $a \in B$ with $a \le b$ , then $a \in I$ as well. So ideals are downward closed. In addition, if $a \in I, b \in I$ then $a + b + ab \in I$ . This is an element, which we might as well call the union $a \cup b$ of $a$ and $b$ , which satisfies $(a + b + ab)a = a$ and $(a + b + ab)b = b$ , hence $a + b + ab \ge a, b$ . So ideals are directed. (When $B = \text{Hom}(S, \mathbb{F}_2)$ , then this is precisely the usual union operation on subsets of $S$ .) Like the intersection, the union has a universal property: it is the supremum of $a$ and $b$ .

We claim that these two conditions together already imply that $I$ is an ideal. Indeed, if $a \in I$ and $r \in B$ then $ar \le a$ , hence by downward closure $ar \in I$ . And if $a, b \in I$ then by directedness there is some $u \in I$ such that $a \le u, b \le u$ and by the universal property of union, $a + b + ab \in I$ . But then $(a + b + ab)(1 - ab) = a + b \in I$ . (Note that the map $a \mapsto 1 - a$ is order-reversing on $B$ and, when $B = \text{Hom}(S, \mathbb{F}_2)$ , 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 $M$ be a maximal ideal of $B$ . For any $b \in B$ , either $b \in M$ or $1 - b \in M$ , and not both.

Proof. Let $\phi : B \to B/M \simeq \mathbb{F}_2$ be the corresponding quotient map. Then either $\phi(b) = 0$ or $\phi(1 - b) = 0$ , and not both.

In fact, this condition characterizes maximal ideals among ideals, since if $M$ has this property, we cannot add to $M$ an element $b$ not already in it without forcing $1 \in M$ (since $1 - b \in M$ ). Note that in particular $0 \in M$ , so $1 \not \in M$ . So, to summarize, a maximal ideal is a subset $M$ of $B$ such that

If $a \in M, b \in M$ , then there is some $s \in M$ such that $a \le s, b \le s$ . (Equivalently, $a \cup b \in M$ .)
If $b \in M, a \in B$ with $a \le b$ , then $a \in M$ .
For any $b \in B$ , either $b \in M$ or $1 - b \in M$ , but not both. (In particular, $0 \in M$ and $1 \not \in M$ .)

The last condition implies that the complement of a maximal ideal $M$ in $B$ is precisely the set $\{ 1 - m : m \in M \}$ . Running this condition through the other two conditions, and remembering that $b \mapsto 1 - b$ is order-reversing, we conclude that the following characterizes subsets $S$ which can be complements of maximal ideals:

If $a \in S, b \in S$ , then there is some $i \in S$ such that $i \le a, i \le b$ . (Equivalently, $ab \in S$ .)
If $b \in S, a \in B$ with $a \ge b$ , then $a \in S$ .
For any $b \in B$ , either $b \in S$ or $1 - b \in S$ , but not both. (In particular, $1 \in S$ and $0 \not \in S$ .)

When $B$ is the ring of functions $S \to \mathbb{F}_2$ , this recovers precisely the usual definition of an ultrafilter on $S$ : a collection of subsets which is closed under intersection, upward closed, and maximal. (We will also refer to this as an ultrafilter on $B$ in an abuse of notation.)

Again, if one thinks of elements of $B$ as logical propositions, then an ultrafilter on $B$ is a set of logical propositions which is closed under AND and implication and which is consistent (does not imply $0$ ); 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 $\text{Spec } B$ can be identified with the set of ultrafilters on $B$ . Knowing this, we will freely switch between thinking of the elements of $\text{Spec } B$ as maximal ideals, as ultrafilters, and as morphisms $B \to \mathbb{F}_2$ .

Let’s give a direct proof that $\text{Spec } B$ 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) $C_b = \{ m : b \in m \}$ . Note that $C_{1-b}$ is the complement of $C_b$ . Note also that since $C_a \cup C_b = C_{ab}$ 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

$\displaystyle U_b = \{ u : b \in u \}$

where $u$ is an ultrafilter instead of a maximal ideal. (This is just the complement of $C_b$ .) Note that $U_{1-b}$ is the complement of $U_b$ . Note also that since $U_a \cap U_b = U_{ab}$ , the basic open sets are already closed under finite intersection, so every open set is a union of basic open sets.

Proposition: $\text{Spec } B$ is compact, Hausdorff, and totally disconnected.

Proof. Let $m, n$ be distinct maximal ideals. Then there is $a \in m$ which is not in $n$ , hence $m \in C_a$ while $n \in C_{1-a}$ . Since these sets are disjoint and open, $\text{Spec } B$ is Hausdorff. Since their union is the whole space, $\text{Spec } B$ is totally disconnected. (Dually, let $u, v$ be distinct ultrafilters. Then there is $b \in u$ which is not in $v$ , hence $u \in U_b$ and $v \in U_{1-b}$ . Since these sets are disjoint and open, $\text{Spec } B$ is Hausdorff. Since their union is the whole space, $\text{Spec } B$ is totally disconnected.)

To prove that $\text{Spec } B$ is compact, it suffices to show that the finite intersection property holds for a collection of basic closed sets $C_{b_i}$ . Suppose any finite collection of these sets has a nontrivial intersection. Then there exists a maximal ideal containing any finite subset of the $b_i$ . It follows that the ideal $I$ generated by the $b_i$ is proper, since $1 \in I$ if and only if $1$ is generated by some finite subset of the $b_i$ (which contradicts the above). (Dually, there exists an ultrafilter avoiding any finite subset of the $b_i$ , hence containing any finite subset of the $1 - b_i$ , so the filter $F$ generated by the $1 - b_i$ is proper.)

By the Boolean prime ideal theorem, there exists a maximal ideal $m$ containing $I$ . But now $m \in \bigcap C_{b_i}$ and we are done. (Dually, by the ultrafilter lemma, there exists an ultrafilter $u$ containing $F$ . But now $u \in \bigcap C_{b_i}$ 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 $B$ be a Boolean ring. The injection $B \mapsto \text{Hom}_{\text{Top}}(\text{Spec } B, \mathbb{F}_2)$ is surjective.

Proof. Let $f : \text{Spec } B \to \mathbb{F}_2$ be continuous. Then $f^{-1}(0)$ is open, hence is a union of basic open sets $U_{b_i}$ . Since $f^{-1}(0)$ is also closed, it is compact, so by compactness the open sets $U_{b_i}$ have a finite subcover $U_{b_1}, ... U_{b_n}$ . But it’s not hard to see that $U_{b_1} \cup ... \cup U_{b_n} = U_{b_1 \cup ... \cup b_n}$ , so it follows that $f = b_1 \cup ... \cup b_n$ . 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.

Propositional logic

Let $S$ be a set; recall that the free Boolean ring $F(S)$ on $S$ is a setting for propositional logic where $S$ takes on the role of the set of primitive propositions. By freeness, $\text{Hom}_{\text{BRing}}(F(S), B) \simeq \text{Hom}_{\text{Set}}(S, U(B))$ where $U$ is the forgetful functor from Boolean rings to sets, so it follows that

$\text{Hom}_{\text{BRing}}(F(S), \mathbb{F}_2) \simeq \text{Hom}_{\text{Set}}(S, \mathbb{F}_2)$

so $\text{Spec } F(S) \simeq \{ 0, 1 \}^S$ , and one readily verifies that the Zariski topology on $\text{Spec } F(S)$ is the product topology. In logical terms, a consistent assignment $\phi : F(S) \to \mathbb{F}_2$ 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 $A \subset B$ has a model if there exists a morphism $\phi : B \to \mathbb{F}_2$ such that $\phi(a) = 1 \forall a \in A$ . When $B = F(S)$ , this is equivalent to the statement that it is possible to assign truth values to the elements of $S$ so that all of the statements in $A$ are true. This condition is also equivalent to the condition that $A$ is contained in an ultrafilter. Then the compactness theorem states that if every finite subset of $A$ has a model, then $A$ has a model. But the set of ultrafilters containing some $a \in A$ is closed in $\text{Spec } B$ , so this immediately follows by the finite intersection property.

Remark: Since we gave a direct proof of the compactness of $\text{Spec } B$ 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!

Posted in math.AC, math.CT, math.GN, math.LO | Tagged adjoint functors, ultrafilters, universal properties | 12 Comments

12 Responses

on July 15, 2016 at 12:46 am | Reply Mahmoud Abdelrazek

Nice … But wasn’t it enough showing equivalence of $\textbf{BRing}$ and $\textbf{StonTop}$ , and as you showed the functors involved in such equivalence are $\text{Spec}$ and $\text{Hom}( _ , \{0,1\})$ , they are automatically (contravariantly) adjoint, so you needn’t show this independently … I think I am messing something
on November 26, 2015 at 9:14 pm | Reply The Lawvere theory of Boolean functions | Annoying Precision

[…] answer is that they are Boolean algebras, and also that they are Boolean rings. Equivalently, the standard axiomatizations of Boolean algebras resp. Boolean rings describe two […]
on June 23, 2013 at 12:40 pm | Reply Operations, pro-objects, and Grothendieck’s Galois theory | Annoying Precision

[…] of finite sets, which is one way to define the category of profinite sets. This is essentially Stone duality, except that we have not mentioned topological spaces at […]
on April 1, 2013 at 4:03 pm | Reply Connected objects and a reconstruction theorem | Annoying Precision

[…] in the categorical sense – is false. For example, let be a homomorphism induced by a non-principal ultrafilter on an infinite set . Then the corresponding morphism does not factor through any of the […]
on December 9, 2010 at 7:57 pm | Reply Ultrafilters in topology « Annoying Precision

[…] Boolean rings, ultrafilters, and Stone’s representation theorem […]
on November 23, 2010 at 10:00 am | Reply Todd Trimble

Argh, wish I could edit. If A’ is the complement of A, I should have written “switch to A’ – B and pick a subset of that”. I hope my meaning was clear.
on November 23, 2010 at 9:57 am | Reply Todd Trimble

Can I just say one more thing about ultrafilters? I think there is a psychological tendency to think of ultrafilters as somehow “big”: a really big collection of subsets hard to comprehend (at least in the case of a non-principal ultrafilter). And it’s not that that’s wrong exactly. But considered topologically, one can consider an ultrafilter as a process of zeroing in on an ideal point, hence something that gets smaller and smaller (or more and more precise).

I can best explain it by the game you see on The Price Is Right, where the contestant has to zero in on the price of some item by iterating guesses in response to the emcee saying “higher” or “lower”. Imagine playing the game with an ultrafilter U. The contestant asks: is subset A in U? and Bob Barker says “yes” or “no”. If he says no, player switches to the complement of A, and then picks a subset B of that and asks if it’s in U? If so, pick a subset C of B; if not, then switch to A – B and pick a subset of that. And so on. So as you get deeper in the game you work with smaller and smaller (but never empty) subsets, which tunnel in a certain direction, according to the ultrafilter, toward an “ideal point”. What makes the ultrafilter “big” is the upward closure condition, but somehow you don’t care about all that surrounding fluff, you just care about how the smaller and smaller subsets you can identify as being within U.
- on November 23, 2010 at 11:06 am | Reply Qiaochu Yuan
  
  This is a nice intuition. I think Terence Tao says something similar in his post about how ultrafilters can be thought of as voting algorithms. Hopefully I can work some of this in to the next post (which will have to wait for awhile as I have some actual work to do). Also, thanks for the reference to Johnstone’s book! It’s quite interesting.
on November 23, 2010 at 4:56 am | Reply Todd Trimble

Ernest Manes has an old book out, Algebraic Theories, which I believe explains this in detail (the theorem that compact Hausdorff spaces are algebraic/monadic over sets is one of the main results of his thesis). There’s a good chance it’s in Stone Spaces as well.

It’s easy enough to explain in outline. The ultrafilter monad $\beta: Set \to Set$ takes a set $X$ to the set of ultrafilters on $X$ . The unit of the monad is the principal filter function. If $X$ is provided with a compact Hausdorff topology, then there is a map $\beta X \to X$ which sends an ultrafilter to the unique point it converges to (compactness is equivalent to having every ultrafilter converge to some point, and Hausdorffness is equivalent to having that point be unique). The multiplication of the monad can be extracted from the compact Hausdorff structure which obtains on the space of ultrafilters with the Zariski topology that you wrote about (and can even be given more “conceptually”, but I won’t go into that). It all fits together so that the convergence map $\beta X \to X$ is precisely an algebra for this monad, and given an algebra structure, a compact Hausdorff topology can be extracted from that structure by thinking of it as a convergence relation.

I do believe this can be worked out as an extended exercise for anyone who has carefully gone through your post. One pleasant corollary is the Tychonoff theorem for compact Hausdorff spaces, which becomes clear since monadic functors preserve and reflect limits and in particular products.
on November 22, 2010 at 9:11 pm | Reply Todd Trimble

Oh, I forgot about latexing in wordpress; sorry.
on November 22, 2010 at 9:10 pm | Reply Todd Trimble

Nice post, Qiaochu. Do you have by any chance the book Stone Spaces by Johnstone? I reckon you’d enjoy it.

A passing comment on Stone duality. The two-element set carries a structure of Boolean algebra object in the category of compact Hausdorff spaces. So we have two algebraic structures on $\mathbb{F}_2$ whose operations commute with one another (here a compact Hausdorff space is an algebra for the ultrafilter monad, hence ‘algebraic’). This means two things: (1), that the hom-functor $CH(-, \mathbb{F}_2): CH^{op} \to Set$ is a Boolean algebra object, hence canonically lifts to a functor $CH^{op} \to Bool$. That’s one half of Stone duality. But equally well, $\mathbb{F}_2$ is a compact Hausdorff space object in the category of Boolean algebras. So (2), the hom-functor $Bool(-, \mathbb{F}_2): Bool^{op} \to Set$ is a compact Hausdorff space object, hence canonically lifts to a functor $Bool^{op} \to CH$. This is the other half of Stone duality. (All of this can be made set-theoretically rigorous.)

In the nLab, we have taken to calling objects with two structures that commute with each other “ambimorphic objects”. (An older name is “schizophrenic object”, but some of us dislike that term.)
- on November 23, 2010 at 3:31 am | Reply Qiaochu Yuan
  
  Thanks, Todd. Is there a place where this ultrafilter monad stuff is written up? I heard someone mention it on MO and it seems very interesting.

Comments RSS

	ZW on The double commutant theo…
	auto on More about the Schrödinger equ…
	Jaromir Kuben on Meditation on the Sylow theore…
	Qiaochu Yuan on Meditation on the Sylow theore…
	Qiaochu Yuan on Some remarks on the infinitude…

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos