Ultrafilters I: The Stone–Čech Compactification

Today, we begin a new series on the marvels of ultrafilters. The journey will be wide-ranging and will bring us to great heights, but, as always, we start humbly, with definitions. As always, the reader is referred here for a reminder of basic set theoretic notation.

Meeting of the Bourbaki Group in Besse en Chandesse, Puy de Dome, July 1935 (b/w photo)
Nicolas Bourbaki

Before we learn about ultrafilters we must, naturally, learn about filters. Filters, introduced by Birkhoff and Cartan in the 1930s and popularized by the mighty Nicolas Bourbaki, can be thought of as a way of specifying which subsets of a given set should be considered to be “large.” More specifically, let X be a set. A filter on X is a collection \mathcal{F} of subsets of X (i.e.  \mathcal{F} \subseteq \mathcal{P}(X)) satisfying the following criteria:

  1. X \in \mathcal{F} and \emptyset \not\in \mathcal{F}.
  2. If Z \subseteq Y \subseteq X and Z \in \mathcal{F}, then Y \in \mathcal{F}.
  3. If Y,Z \in \mathcal{F}, then Y \cap Z \in \mathcal{F}.

These criteria should make sense in light of our informal definition of a filter as a collection of large subsets of a given set: the first asserts that the entire set is large and the empty set is not large, the second asserts that if a subset Z is large, then any subset that contains Z as a subset is also large, and the third asserts that if “most” elements are in a subset Y and “most” elements are also in a subset Z, then “most” elements are in both Y and Z. Note that, by applying the third criteria over and over again, one obtains that any finite intersection of elements of a filter is also in the filter, i.e. if n \in \mathbb{N} and Y_0, Y_1, \ldots, Y_n are in \mathcal{F}, then Y_0 \cap Y_1 \cap \ldots \cap Y_n is in \mathcal{F}.

An ultrafilter on X is a filter on X that contains as many sets as possible. What does this mean in practice? Notice that, if \mathcal{F} is a filter on X and Y \subseteq X, it cannot be the case that both Y and  X \setminus Y are in \mathcal{F}. This is because, if they were both in \mathcal{F}, then Y \cap (X \setminus Y) would also be in \mathcal{F}. But Y \cap (X \setminus Y) = \emptyset, and \emptyset \not\in \mathcal{F}. It turns out that this is the only real constraint, so a filter \mathcal{F} on X is an ultrafilter if, for every subset Y \subseteq X, either Y \in \mathcal{F} or (X \setminus Y) \in \mathcal{F}.

Let’s look at some examples of filters and ultrafilters. First, a rather trivial example. Suppose X is any non-empty set and x \in X. Let \mathcal{U} be the set of all subsets of X that contain x as an element. You can easily check that \mathcal{U} is an ultrafilter on X; in this case, \mathcal{U} is called the principal ultrafilter on X at x, and it is rather boring.

If X is a finite set, then it turns out that every ultrafilter on X is a principal ultrafilter. To see this, let n \in \mathbb{N}, let X be a set with n elements, e.g. X = \{0,1,2, \ldots, n-1\}, and let \mathcal{U} be an ultrafilter on X. If there is i < n such that \{i\} \in \mathcal{U}, then it follows that \mathcal{U} is the principal ultrafilter at i. Suppose this is not the case. Then, for all i < n, X \setminus \{i\} \in \mathcal{U}. Then X \setminus \{0\} \cap X \setminus \{1\} \cap \ldots \cap X \setminus \{n-1\} is a finite intersection of elements of \mathcal{U} and therefore is itself in \mathcal{U}. But this intersection is \emptyset, and \emptyset \not\in \mathcal{U}. Contradiction! Thus, there is i < n such that \{i\} \in \mathcal{U}.

Therefore, interesting ultrafilters only start showing up on infinite sets. But they show up immediately. Suppose X is an infinite set, and let \mathcal{F} be the set of all co-finite subsets of X, i.e. all sets Y \subseteq X such that X \setminus Y is finite. \mathcal{F} is easily seen to be a filter on X and is called the Fréchet filter. \mathcal{F} is certainly not an ultrafilter. If, for example, X = \mathbb{N}, then neither the set of even numbers nor the set of odd numbers is in \mathcal{F}. However, it is a consequence of Zorn’s Lemma, an equivalent form of the Axiom of Choice, that any filter can be extended to an ultrafilter. Therefore, we can find an ultrafilter \mathcal{U} on X such that \mathcal{F} \subseteq \mathcal{U}. For every x \in X, X \setminus \{x\} is clearly a cofinite subset of X and is hence in \mathcal{U}, so \mathcal{U} is not a principal ultrafilter (in fact, it is easily seen that, for an ultrafilter on X, extending the Fréchet filter and being non-principal are equivalent).

As we will see in coming posts, non-principal ultrafilters are wondrous creatures. We have time for one quick illustration today. Recall that, in a previous post, we introduced the notion of a topological space and a compactification thereof. We showed that, given any topological space (X, \tau), there is a smallest way to make X compact, and one can in fact achieve this by adding a single new point at infinity. There is also a largest (in a specific technical sense) compactification of (X, \tau). This is known as the Stone–Čech compactification.

In general, the Stone–Čech compactification of a space can be defined in terms of an abstract universality property. It can also be defined in a somewhat more complicated way in terms of continuous functions from the space to the closed unit interval. But, in the case in which (X, \tau) has the discrete topology, i.e. \tau = \mathcal{P}(X), then the Stone–Čech compactification has a very pleasing and initially surprising characterization: it is the space of all ultrafilters on X.

beta-x-extension1
A diagram illustrating the universality property characterizing the Stone-Čech compactification.

Let \beta X denote the set of all ultrafilters on X. What topology do we place on \beta X? If Y \subseteq X, then let O_Y be the set of \mathcal{U} \in \beta X such that Y \in \mathcal{U}. We can define a topology \tau' on \beta X by letting \tau' consist of all subsets of \beta X that can be expressed as arbitrary unions of sets in \{O_Y \mid Y \subseteq X\}. (\beta X, \tau') is then the Stone–Čech compactification of (X, \tau).

You might have a couple objections here. First, a compactification worthy of its name must be compact, and I have not shown that (\beta X, \tau') is compact. In fact, I will not do so here. It’s not particularly difficult, and I encourage interested readers to seek out its proof elsewhere, but neither is it trivial.

Second, a compactification of a space X should contain X as a subspace. But, here, X and \beta X consist of fundamentally different objects, and, formally, it is not the case that X \subseteq \beta X. This objection is easily and elegantly overcome, though, by saying that an element x \in X is identified with the element \mathcal{U}_x \in \beta X, where \mathcal{U}_x is the principal ultrafilter on X at x. Through this renaming, X is identified as a subspace of \beta X, and all is right in the world. In addition, this identification clarifies our picture of \beta X: the boring, principal ultrafilters in \beta X correspond to the points in our original space X, while the non-principal ultrafilters comprise a constellation of new points at infinity.

ultrafilter

Advertisements

3 thoughts on “Ultrafilters I: The Stone–Čech Compactification

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s