Stone Spaces as Completions

Whenever I have a maths problem, I usually try to see what people more clever than me have to say about it so I can refer to their writings as a better introduction. Some time ago, I was dabbling in profinite topology, Stone duality, and its links to formal language theory and computational complexity. This is a relatively young research topic, so naturally there is only very little literature available . Luckily, a person that is very obviously more clever than me, Terry Tao, has taken the time to write about a very related subject: His blog post titled Nonstandard Analysis as a Completion of Standard Analysis has been around since 2010 and picks up quite a few of the ideas present in the field and connects very nicely to some thoughts I have been having. For this post, it is sufficient to read the introduction and the first section of that post stopping after Remark 1. I might return to the rest of the article some other day.

Stone Spaces

Remark 1 says that the predicates $P$ are generating a topology on the universe via $\lbrace x \in \mathfrak{U} \mid P(x) \rbrace$, which can then be completed. If the logic is sufficiently nice (i.e. it is closed under Boolean operations), this topology is exactly the one that you encounter when you construct the Stone dual space to the Boolean algebra generated by the logic. In the case considered in the blog post, there are only a countable number of predicates, and the topology is hence that generated (for example) by the following metric on the universe:

with the understanding that $[P_i(x) \leftrightarrow P_i(y)]$ is 1 if $P_i$ takes the same value for $x$ and $y$, 0 otherwise. This metric makes the universe a discrete space. You can now consider the completion w.r.t. that metric to get a nicer version of the original space.

Now, in the setting of formal language theory and computational complexity, you do not necessarily always start off with a logical language and a universe of models. Rather, you are interested in a specific class $\mathcal{C}$ of subsets (think: predicates) of $\Sigma^*$ (think: universe), the set of words over some finite alphabet $\Sigma$. In many cases $\mathcal{C}$ forms a field of sets, that is, a Boolean algebra with the usual operations of union, intersection, and complement: This is true of virtually all classes defined by deterministic machines or classical logics.

Instead of considering predicates on $\Sigma^*$ that give rise to the sets in $\mathcal{C}$ as their extension, we can take these sets themselves to generate a topology, define convergence, and construct the complection. The resulting space will generally be much bigger than $\Sigma^*$ and have the properties of what is known as a Stone space: It is zero-dimensional, compact, and Hausdorff. If you are not familiar with topology, forget about zero-dimensionality (you won’t need it) and Hausdorff (you probably have never encountered a space that is not Hausdorff), and replace compact with complete for a crude approximation.

The construction above is then merely a case of Stone duality, specifically the direction that takes you from a Boolean algebra to its corresponding dual space. These spaces are also known as profinite spaces, because you can also construct them by considering categorical limits of finite objects. This is a fun topic in and of itself; we will probably return to it some day.

Ultrafilters

As long as $\mathcal{C}$ is countable, the definition of the metric will still make sense. For uncountably infinite $\mathcal{C}$, this definition breaks down. Indeed, this is due to the fact that the dual space of $\mathcal{C}$ is simply too big; its properties cannot be described by sequences alone: You need ultrafilters for that. For our purposes, an ultrafilter of $\mathcal{C}$ is a collection $\mu \in 2^{\mathcal{C}}$ with the properties

1. $\emptyset \notin \mu$,
2. $\mu$ is closed under extensions: For $M, N \in \mathcal{C}$, if $M \subseteq N$ and $M \in \mu$, then $N \in \mu$,
3. $\mu$ is clsoed under intersection: For $M, N \in \mathcal{C}$, if $M, N \in \mu$ then $M \cap N \in \mu$,
4. for each set $M \in \mathcal{C}$, either $M \in \mu$ or $M^{c} \in \mu$.

Conceptually, an ultrafilter should be thought of as another description of a point in a space. The sets from $\mathcal{C}$ are regions of the space and if $M \in \mathcal{C}$ is in $\mu$, this is saying that the point described by $\mu$ is inside the region $M$. Under this interpretation, the first three properties ensure consistency of the specification and fourth its maximality.

For example, any $w \in \Sigma^*$ gives rise to a principal ultrafilter $\mu_w$ defined by

This ultrafilter describes the position of $w$ within $\Sigma^*$ relative to $\mathcal{C}$. Depending on the nature of $\mathcal{C}$, the map $w \mapsto \mu_w$ may or may not be injective: If $\mathcal{C}$ cannot separate two words $x, y$, in the sense that for all $M \in \mathcal{C}$ it is the case that $x \in M \leftrightarrow y \in M$, then $\mu_x = \mu_y$.

Likewise, this construction generally does not give rise to all ultrafilters of $\mathcal{C}$: Just like Cauchy-sequences do not need to converge to a point of the space, ultrafilters do not need to describe the position of an actual point of the space. They might just as well describe a position in space that really needs a point for the space to be beautiful. Ultrafilters with this property are called free or non-principal; if they correspond to an actual point, they are called principal or fixed.

Indeed, any Cauchy-sequence $\mathbf{a} = (a_{n})^\infty_{n=1}$ gives rise to an ultrafilter $\mu_{\mathbf{a}}$ by taking the family of all sets $M \in \mathcal{C}$ such that $\mathbf{a}$ is eventually in $M$. Formally,

The converse is generally not true, since very large spaces (that is, without a countable base) cannot be sufficiently described by sequences anymore.

Another way to look at an ultrafilter is to interpret it as a maximally consistent specification of an object: It is the collection of properties that we would like it to have. The sets of $\mathcal{C}$ are then seen as the extension of predicates again. Completing the space then acts as wish-fulfillment: We get to add points with properties that would not have been possible in the original universe.

As an example for this point of view: From the definition of an ultrafilter $\mu$, it is immediately clear that $\Sigma^* \in \mu$ (combine properties 1 and 4). Under the interpretation of a specification, this is merely saying that $\mu$ describes a word. Now we can add in the set of all even length words $(\Sigma^{2})^*$ to specify that we also want that word to be of even length.

Anyway - just like you can complete a metric space by considering equivalence classes of Cauchy-sequences, you can from a completion of $\Sigma^*$ relative to $\mathcal{C}$ by considering all its ultrafilters. This new space will contain a copy of $\Sigma^*$ if the map $w \mapsto \mu_w$ is injective, otherwise it will only contain a quotient of $\Sigma^*$. To no-one’s surprise, this space is a Stone space. I will sometimes use $\mathcal{S}(\mathcal{C})$ to denote this completion and/or call it a dual space.

Examples

Finally, let us consider a few examples. The examples will not be limited to words, because there is little reason to not use another arbitrary set and a field of its subsets.

1. For any finite set $F$, consider the field of sets $\mathcal{C} = 2^F$. The completion $\mathcal{S}(\mathcal{C})$ of $F$ w.r.t. $\mathcal{C}$ is again $F$. In general, for $\mathcal{C} \subseteq 2^F$ with $F$ finite, the corresponding dual space is a quotient of $F$ and hence finite and discrete. Two elements are identified if $\mathcal{C}$ cannot separate them.

2. Consider $\mathbb{N}$ and let $\mathcal{C}$ be the family of all finite and cofinite subsets of $\mathbb{N}$. The corresponding completion is $\mathbb{N}^\infty = \mathbb{N} \cup \lbrace \infty \rbrace$. Each natural $n$ gives rise to a principal ultrafilter, so $n \mapsto \mu_n$ embeds $\mathbb{N}$ in $\mathcal{S}(\mathcal{C})$. Then there is another free ultrafilter which does not contain any finite set, hence describes a point that is not finite. This is easier to grasp with a reformulation: $\mathcal{C}$ is also the field of sets generated by the sets $n_< = \lbrace m \in \mathbb{N} \mid m < n \rbrace$ and $n_> = \lbrace m \in \mathbb{N} \mid m > n \rbrace$. Thus, an ultrafilter must answer for each $n \in \mathbb{N}$ whether it is smaller than $n$ – and it is perfectly consistent to just always deny that. The topology here is also as you’d expect: A sequence converges to $\infty$ if and only if it eventually leaves any finite subset of $\mathbb{N}$ behind. As a bonus to whet your appetite, there even is a principled way to derive the addition operation (let me state the obvious: $\mathbb{N}$ is a monoid with zero) on this space by considering the profinite limit for this case; we will get to that some other day.

3. As a slightly more involved example, first consider $\mathbb{Z}$ with $\mathcal{C}$ generated by all finite sets. This yields the dual space $\mathbb{Z} \cup {\infty}$, where $\infty$ is neither negative or positive. Now take $\mathcal{C}_1 = <\mathcal{C}, \lbrace \mathbb{N} \rbrace >$, that is, $\mathcal{C}_1$ is generated by all finite sets and $\mathbb{N}$. Then $\mathcal{S}(\mathcal{C}’) = \mathbb{Z} \cup \lbrace -\infty, +\infty \rbrace$. In essence, for $\mathcal{C}_1$ we enhanced the underlying language with a predicate to check whether a number is less than zero and hence split the free ultrafilter into two: One where it chose to negative and one where it chose to be positive. We could just as well have chosen the set $n_>$ for any $n\in\mathbb{N}$ instead of $\mathbb{N}$ to get the same result. To drive the point home, replace $\mathbb{N}$ with the set of all even numbers $2\mathbb{Z}$. This would create a different compactification of $\mathbb{Z}$ where there is an even and an odd version of infinity (and a sequence converges to them if it is eventually even or odd, respectively). Add in both $2\mathbb{Z}$ and $\mathbb{N}$ to get 4 versions of infinity - negative even, negative odd, positive even, positive odd. Contrast this with the various compactifications of $\mathbb{R}$ that you may have come across with: You can add in a single point at infinity to get nice a circle or two to get the unit interval if you also care about the sign of infinity.

4. $\Sigma^*$ with $\mathcal{C}$ generated by $w_< = \lbrace v \in \Sigma^* \mid \exists u \in \Sigma^* : v = wu \rbrace$ for all $w \in \Sigma^*$, that is, the class of languages definable by only asking whether a specific word is a prefix of another. Note that $\mathcal{C}$ contains all finite sets. This is slightly different from the last example, because this is not a total order anymore. Hence, there are significantly more than just a single free ultrafilter. In fact, $\mathcal{S}(\mathcal{C}) = \Sigma^\infty = \Sigma^* \cup \Sigma^\omega$, where $\Sigma^\omega$ are literally infinite words that just continue on and on and on. Convergence in this space works as you would expect it to: A sequence converges to some infinite word $x$ if for each prefix of $x$, the sequence eventually only contains words with that prefix. These infinite words are quite well studied and behave in a very natural way: Because $\mathcal{C}$ is sufficiently powerful to define sets such as all words that have an ‘a’ in their 17th position, these questions can also be asked for these infinite words. Unsurprisingly, $\mathcal{S}(\mathcal{C})$ forms a profinite monoid with the property that for $v$ infinite and $w$ arbitrary, $v \cdot w = v$.

5. $\Sigma^*$ with $\mathcal{C}$ generated by $w_> = \lbrace v \in \Sigma^* \mid \exists u \in \Sigma^* : v = uw \rbrace$. This is equivalent to a quantifier-free logic where you can only check for suffixes. This is distinct from the previous example and leads to a completely dual result: $\mathcal{S}(\mathcal{C}) = \Sigma^{-\infty} = \Sigma^* \cup \Sigma^{-\omega}$, where $\Sigma^{-\omega}$ is the set of all left-infinite words.

6. $\Sigma^*$ with $\mathcal{C}$ generated by $w_<$ and $w_>$. Then the dual is $\Sigma^* \cup \Sigma^{<\infty>}$ where $\Sigma^{<\infty>}$ is the set of infinite words with an infinite start and an infinite end: It’s what you get when you glue together two total orders on their infinite ends - they never meet, but have well-defined beginnings and ends. Convergence in the space is eventual stabilization of prefixes and suffixes in the sequence.

7. ${a}^*$ with $\mathcal{C}$ all regular languages on this unary alphabet. By interpreting ${a}^*$ as $\mathbb{N}$, these can be conveniently described as the semilinear-sets, generated by the sets $c + p\mathbb{N}$ for $c, p \in \mathbb{N}$. Note that I assume $0 \in \mathbb{N}$, so this includes the finite sets of the form $c + 0\mathbb{N}$. This is more accessible when expressed as the field of sets generated by all finite sets and sets of the form $\lbrace x \in \mathbb{N} \mid x \equiv c \mod p \rbrace$. It is sufficient to consider these sets for $p$ prime. Hence the dual space has the form $\mathbb{N} \cup X$ where the elements of $X$ can be seen as large numbers that have decided (in a consistent manner) for each prime $p$ what their remainder modulo that prime is. For example, the sequence $(n!)_{n=1}^\infty$ converges to an infinite number that is evenly divisible by any non-zero natural. This space again has a very natural monoid structure.

8. Instead of considering $\mathbb{N}$ with its recognizable subsets (this was the previous example), we can also consider $\mathbb{Z}$ (as a monoid) and its recognizable subsets. Recall that a subset $U$ of $\mathbb{Z}$ is recognizable if there is a finite quotient monoid $M$ with quotient map $\varphi : \mathbb{Z} \to M$ and $F \subseteq M$ such that $U = \varphi^{-1}(F)$. Since the quotients of $\mathbb{Z}$ are all of the form $\mathbb{Z}/p$, the recognizable subsets are generated by the sets $c + p\mathbb{Z}$ for $p > 0$. In other words, the dual space (for the first time in the examples) does not include a copy of $\mathbb{Z}$ via their principal ultrafilters, because the recognizable subsets do not include the finite sets. Instead, you just get the $X$-part from the previous example: Infinite numbers that have consistently chosen their remainders for all primes. These are also known as the profinite integers and can of course be interpreted as containing a copy of $\mathbb{Z}$ - but with a different topology, so it is not a compactification of $\mathbb{Z}$ in our sense. By restricting the quotients of $\mathbb{Z}$ that you consider to $Z/p, Z/p^2, Z/p^3, \ldots$, you get exactly the $p$-adic integers.

9. Continuing from example 3: What happens when you keep enlarging $\mathcal{C}$ by adding in single sets (and generating the field from that)? Well, at some point no two sequences converge to the same point. In fact, there will be so many directions to converge in that there are not enough sequences to go in all of them! As soon as $\mathcal{C}$ becomes uncountable (ok, this technically will never happen if you just keep adding single sets) it will become increasingly hard to give nice interpretations for the new points you added. The point is that by specifying $\mathcal{C}$ you declare what differences in how a sequence (or rather, net) escapes the space you care about. Finally, when $\mathcal{C}$ is the powerset of your universe $X$, the resulting dual space is $\beta X$ - the Stone-Čech compactification of $X$. Essentially, this just gives up on interpretation completely and just adds an ultrafilter in any direction that you could want to escape the space.

There are plenty of other examples and I still have some more thoughts on this topic, but this blog post has to end somewhere – and the Stone-Čech compactifications feels like a good point to stop :)