Feeds:
Posts

## Ultrafilters in topology

Remark: To forestall empty set difficulties, whenever I talk about arbitrary sets in this post they will be non-empty.

We continue our exploration of ultrafilters from the previous post. Recall that a (proper) filter on a poset $P$ is a non-empty subset $F$ such that

1. For every $x, y \in F$, there is some $z \in F$ such that $z \le x, z \le y$.
2. For every $x \in F$, if $x \le y$ then $y \in F$.
3. $P$ is not the whole set $F$.

If $P$ has finite infima (meets), then the first condition, given the second, can be replaced with the condition that if $x, y \in F$ then $x \wedge y \in F$. (This holds in particular if $P$ is the poset structure on a Boolean ring, in which case $x \wedge y = xy$.) A filter is an ultrafilter if in addition it is maximal under inclusion among (proper) filters. For Boolean rings, an equivalent condition is that for every $x \in B$ either $x \in F$ or $1 - x \in F$, but not both. Recall that this condition tells us that ultrafilters are precisely complements of maximal ideals, and can be identified with morphisms in $\text{Hom}_{\text{BRing}}(B, \mathbb{F}_2)$. If $B = \text{Hom}(S, \mathbb{F}_2)$ for some set $S$, then we will sometimes call an ultrafilter on $B$ an ultrafilter on $S$ (for example, this is what people usually mean by “an ultrafilter on $\mathbb{N}$“).

Today we will meander towards an ultrafilter point of view on topology. This point of view provides, among other things, a short, elegant proof of Tychonoff’s theorem.

Some intuitions

There are several ways to get a more intuitive grasp on what it is, exactly, that ultrafilters are. We saw one of these intuitions already: an ultrafilter on $B$ is a maximal consistent deductively closed set of propositions in $B$. If $S$ is a set of propositions in $B$, then ultrafilters on $B$ containing $S$ can be identified with “models of $S$,” that is, ways to make the statements of $S$ all true. (We do not actually need to construct these models because the only thing we care about is which statements are true or false in a model, which is precisely what the ultrafilter tells us!) According to this intuition, the ultrafilter axioms are just familiar properties of propositional logic:

1. Conjunction: if $p$ and $q$, then $p \wedge q$ ($p$ and $q$).
2. Modus ponens: if $p$ and $p \rightarrow q$ (that is, $p \le q$, or $p$ implies $q$), then $q$.
3. Excluded middle: $p$ if and only if $\neg (\neg p)$ (not not $p$).

In his post on ultrafilters, Terence Tao also uses the closely related “voting” intuition. Here we only consider ultrafilters on sets. We think of the set $S$ as a collection of voters, and a collection of votes as a subset of $S$ (the subset of people who voted “yes” on something). An ultrafilter $F$ on $S$ is then a consistent way of deciding elections: given a collection of votes on some proposition, the outcome of the election is “yes” if the set of “yes” votes is in $F$ and “no” otherwise. According to this intuition, the ultrafilter axioms then say that this voting system does not produce voting paradoxes: the explanations are essentially the same as the ones above if one substitutes “$p$ is true” with “the electorate voted for $p$.”

Terence Tao also uses a third probabilistic, or measure-theoretic, intuition: an ultrafilter $F$ on $S$ can be thought of as defining a “measure” $\mu$ which assigns to each subset of $S$ measure $1$ if the subset is in $F$ (“almost surely true”) and $0$ otherwise (“almost surely false”). Informally, this is a kind of zero-one law. $\mu$ is precisely the morphism $\phi : \text{Hom}(S, \mathbb{F}_2) \to \mathbb{F}_2$ associated to the maximal ideal associated to $F$, but here we are thinking of its codomain in a somewhat different way. According to this intuition, the ultrafilter axioms set out several natural properties a “measure” like $\mu$ should have:

1. If $\mu(A) = 1$ and $\mu(B) = 1$, then $\mu(A \cap B) = 1$.
2. If $\mu(A) = 1$ and $A \subseteq B$, then $\mu(B) = 1$.
3. $\mu(A) = 1$ if and only if $\mu(A^c) = 0$.

Together with the other axioms, the third axiom is actually equivalent to $\mu$ being finitely additive (and equal to $1$ on the entire set): if $A_1, ... A_n$ are disjoint subsets, then either they all have measure $0$ (hence so does their union) or some $A_i$ has measure $1$, hence its complement (hence all of the other subsets) has measure $0$. This is not as strong as countable additivity, so $\mu$ does not actually form a measure.

Nevertheless, finite additivity is a convenient way to think about how ultrafilters work: if $X : S \to \mathbb{R}$ is a “random variable” which takes on finitely many values, it breaks $S$ up into a disjoint union of finitely many sets, exactly one of which can have measure $1$, hence $X$ takes that value “almost surely” (so that value is its “expected value”). In voter-theoretic terms, the electorate can hold elections with any finite number of options, rather than just two.

Non-principal ultrafilters

Given a set $S$, there are some obvious ultrafilters we can write down on $S$. These are the ultrafilters consisting of the set of all subsets containing some $s \in S$, or the principal ultrafilters. It’s not hard to see that this condition is equivalent to the condition that the ultrafilter has a least element (the intersection of all of its elements), since this least element must be a singleton. Algebraically, principal ultrafilters correspond to principal ideals generated by elements of $B = \text{Hom}(S, \mathbb{F}_2)$ vanishing at one point $i$ and not vanishing anywhere else, and the corresponding morphism $B \to \mathbb{F}_2$ is the obvious projection to the $i^{th}$ coordinate. In voting terms these are “dictatorial” voting systems, in measure-theoretic terms these are Dirac measures supported on points, and in probabilistic terms these are deterministic random variables taking a single value.

When $S$ is finite, all ultrafilters are principal. However, when $S$ is infinite, we know that $\text{Spec } B$ is compact, Hausdorff, and totally disconnected. But it’s not hard to see that $S \subset \text{Spec } B$ has the discrete topology, so there must be more points than the elements of $S$; in other words, there must be non-principal ultrafilters (hence morphisms $B \to \mathbb{F}_2$ other than the obvious ones) which, as points in the spectrum, give a compactification of the discrete space $I$.

Proposition: An ultrafilter on an infinite set $S$ is non-principal if and only if it contains the Fréchet filter of cofinite subsets of $S$.

Proof. An ultrafilter contains the Fréchet filter if and only if its complement contains all finite subsets of $S$. Since principal ultrafilters contain singletons, no principal ultrafilter can contain the Fréchet filter, and conversely if a principal ultrafilter contains the Fréchet filter it cannot contain any singletons.

At this point, the statements I’ve been making about compactification are probably worth justifying. Recall that given a space $T$, a space $C$ equipped with a continuous injection $T \to C$ is said to be a compactification of $T$ if $C$ is compact Hausdorff and the image of $T$ is dense. In this case, $C = \text{Spec } B$ has the property that its topology is determined by the continuous functions $C \to \mathbb{F}_2$, so to show that $T = S$ is dense it suffices to show that a function is determined by its values on $S$. But this is true by definition. So the space of ultrafilters on $S$ is in fact a compactification of the discrete space $S$, which sits inside it as the subspace of principal ultrafilters.

In voting terms, if a principal ultrafilter is like having a dictator, a non-principal ultrafilter is like having a “virtual” or “ideal” dictator. This perspective was explained to me, in different words, by Todd Trimble in the comments to the previous post. Given an ultrafilter $F$, imagine playing the following game (which we might call “Find the Dictator”): repeatedly ask yes or no questions of the electorate. Then you know that the set of voters who voted against the outcome of any particular election have no say in any of them; in probabilistic terms, they have measure $0$. So the next question you ask, you only look at the set of voters who do have some say (measure $1$), and ask them some question. Continuing in this way you end up looking at a smaller and smaller set of voters who have some say in the elections. (In topological terms, these smaller and smaller sets of voters are precisely intersections of neighborhoods of the ultrafilter $F$ with the discrete subspace of principal ultrafilters; by density, this essentially determines the neighborhoods.) If $F$ is principal, then if you get lucky with the questions you’ll eventually find the dictator. But if $F$ is non-principal, there isn’t one! So your chain of questions is attempting to converge to a dictator which isn’t actually there, but which is mysteriously somehow still influencing the election.

Convergence and Tychonoff’s theorem

The remarks about convergence above suggest the following definition.

Definition: Let $X$ be a topological space and let $F$ be a filter on $X$. We say that $F$ converges to $x \in X$ (written $F \to x$) if for every open set $U$ containing $x$, there exists $f \in F$ such that $f \subseteq U$.

Filter convergence is a generalization of convergence of sequences which is better adapted to spaces which are far from being metric spaces (for example, spaces which aren’t first-countable). For a thorough explanation of the issues here, I recommend Pete Clark’s notes on convergence.

It is useful to extend the definition of filter convergence and clustering to filter bases, or prefilters, which are nonempty collections of nonempty sets closed under finite intersection. The collection of all supersets of the elements of a prefilter forms a filter, the filter generated by the prefilter, and a prefilter converges to a point $x$ if and only if the filter it generates converges to $x$.

We can recover convergence of sequences as follows. If $a : X \to Y$ is a continuous function and $F$ a prefilter on $X$, then $a(F) = \{ a(f) : f \in F \}$ is a prefilter on $Y$ (the image or pushforward prefilter). If $X = \mathbb{N}$ and $F$ is the Fréchet filter, then $a(F)$ converges to $x$ precisely when the sequence defined by $a$ converges to $x$ in the usual sense. If we want to stick to filters, we can instead take the filter generated by $a(F)$.

In a metric space, the closure of a subset is precisely the set of limits of sequences of elements in the subset. This fails for more general topological spaces, but the corresponding statement is true for filters.

Proposition: Let $X$ be a topological space, $S \subset X$, and $x \in X$. Then the following are equivalent:

1. $x \in \bar{S}$.
2. There exists a prefilter on $S$ which converges to $x$.
3. There exists a filter containing $S$ which converges to $x$.
4. There exists an ultrafilter containing $S$ which converges to $x$.

Proof. Let $N_x$ denote the collection of all neighborhoods of $x$. This is the neighborhood filter at $x$, and by definition, $x \in \bar{S}$ if and only if $N_x \cap S$ converges to $x$. This gives $1 \Rightarrow 2$. That $2 \Rightarrow 3$ follows by taking the filter generated by the prefilter in question, and that $3 \Rightarrow 4$ follows by taking any ultrafilter containing the filter in question, so it remains to prove that $4 \Rightarrow 1$.

Let $F$ be an ultrafilter containing $S$ and converging to $x$, hence for every open set $U$ containing $x$ there exists $f \in F$ such that $f \subset U$. Then $F$ does not contain any subset of the complement of $S$, so for any $f \in F$ the intersection $S \cap f \in F$ is nonempty. Moreover, $f \subset U$ implies that $S \cap f \subset U$. It follows that every open set $U$ containing $x$ contains elements of $S$, so $x \in \bar{S}$ as desired.

In voting terms, an ultrafilter containing $S$ is an electorate where the voters in $S$ are the ones which have power, and it converges to $x$ if and only if any neighborhood of $x$ contains voters in power. In probabilistic terms, an ultrafilter containing $S$ is a “random variable” which is in $S$ almost surely, and it converges to $x$ if and only if it is in any neighborhood of $x$ almost surely.

Recall that the topology of a space is determined by the closure operator $S \mapsto \bar{S}$, and that conversely any such operator satisfying the Kuratowski closure axioms defines a topology. It follows that the topology of a space is determined by (pre/ultra)filter convergence. In particular, a function $f : X \to Y$ is continuous if and only if it preserves convergence of (pre/ultra)filters. As the following proposition shows, this is a convenient way to rephrase certain topological properties.

Proposition: Let $X$ be a topological space.

1. $X$ is Hausdorff if and only if every ultrafilter on $X$ converges to at most one point.
2. $X$ is compact if and only if every ultrafilter on $X$ converges to at least one point.

Proof.

1. $\Rightarrow$: Let $F$ be an ultrafilter converging to $x$, and let $y \neq x$. By assumption, there exist disjoint open sets $U, V$ with $x \in U, y \in V$. Since $F \to x$, there is $f \in F$ such that $f \subset U$. It follows that $V \not \in F$, so $f$ cannot converge to $y$. $\Leftarrow$: By assumption, there exist $x \neq y$ such that every neighborhood of one intersects a neighborhood of another. It follows that any ultrafilter containing the filter $N_x \cap N_y$ (the collection of intersections of neighborhoods of $x$ and neighborhoods of $y$) converges to both $x$ and $y$.
2. $\Rightarrow$: Given an ultrafilter $F$, the collection of closures of elements of $F$ satisfies the finite intersection property, so by assumption there exists $x$ which is in the closure of every element of $F$. For any open set $U$ containing $x$, the closure of $U^c$ does not contain $x$, hence $F$ cannot contain $U^c$ and must contain $U$. It follows that $F \to x$. $\Leftarrow$: Any collection of closed sets $C_i$ with the finite intersection property is contained in an ultrafilter $F$. (In order for a collection of sets to be contained in an ultrafilter it is necessary and sufficient that it have the finite intersection property.) By assumption this ultrafilter converges to some point $x$. Since $F$ contains each $C_i$, it cannot contain their complements $C_i^c$ (or any subset thereof), so $F$ cannot converge to any element of $\bigcup C_i^c$. It follows that $x \in \bigcap C_i$.

Note that unlike the case of sequential compactness of metric spaces, we don’t have to pass to a subsequence to find a limit; in some sense the ultrafilter has already done the passing to a subsequence for us. This is one reason why ultrafilters are so convenient in analysis.

In voting terms, an ultrafilter $F$ converging to a set $S$ of points is a voting system where the elements of $S$ are “approximate dictators.” A Hausdorff space of voters is then one for which at most one approximate dictator can occupy the throne, and a compact space of voters is one for which at least one approximate dictator must occupy the throne. In probabilistic terms, an ultrafilter $F$ converging to a set $S$ of points is a “random variable” which is in a neighborhood of any $s \in S$ almost surely. A Hausdorff space is then one for which such a random variable can be at most one such collection of neighborhoods almost surely, and a compact space is one for which such a random variable must be in at least one such collection of neighborhoods almost surely.

Since every ultrafilter on a finite set is principal, I think the above proposition is a elegant way to justify the intuition that compact spaces “behave like” finite discrete spaces. It also manifests a certain duality between the properties of being compact and being Hausdorff. Finally, it helps explains why compact Hausdorff spaces are so special: these are the ones for which every ultrafilter converges to exactly one point.
Thus giving the structure of a compact Hausdorff space on a set $X$ is equivalent to giving a function $\beta X \to X$ describing which ultrafilters converge to which points in a consistent manner. One can think of this as a kind of algebraic structure on $X$ whose $J$-ary operations can be identified with ultrafilters on $J$; we’ll come back to this in a later post.

We will now give the ultrafilter proof of Tychonoff’s theorem. First recall that if $X_i, i \in I$ are a collection of topological spaces, then the product topology on $X = \prod X_i$ is the initial topology with respect to the projections $\pi_i : X \to X_i$. In ultrafilter terms, this means that an ultrafilter $F$ on $X$ converges to $x \in X$ if and only if $\pi_i(F) \to \pi_i(x)$ for all $i$.

Theorem (Tychonoff): A product of compact spaces is compact.

Proof. Let $F$ be an ultrafilter on $X = \prod X_i$. Since each space $X_i$ is compact, $\pi_i(F)$ converges to some non-empty set of points $S_i \subset X_i$ for each $i$. Then $F$ converges to precisely the points in $\prod S_i$, and by the axiom of choice (!) this set is non-empty.

I find this proof much more elegant and easier to follow than the typical proof, which is some combination of the Alexander subbase theorem and messing around with a basis for the product topology. Munkres gave an alternate proof when I took his class, but I don’t remember any of the details. This proof, on the other hand, is perhaps maximally easy to reconstruct.

Note that if we assume in addition that each $X_i$ is Hausdorff, each $S_i$ is a singleton, so we do not need to use the axiom of choice to prove that $\prod S_i$ is non-empty. We only need the ultrafilter lemma (to prove all of the equivalences above), so it follows that Tychonoff’s theorem for compact Hausdorff spaces follows from (hence is equivalent to) the ultrafilter lemma.

Topology and logic

Since ultrafilters are, at their heart, logical constructions, what we have described above is a tantalizing connection between topology and logic. There appear to be several such connections. There is, for example, this answer and this answer to Minhyong Kim’s MO question about open sets, which identifies topology with an idealization of measurement and with an idealization of computation, respectively, both of which appear to be related to what I’ve said above. There is also an interpretation of the open sets of a topological space as a Heyting algebra, which is related to intuitionistic logic. Perhaps this all fits into a cohesive picture which I’ll understand one day.

### 12 Responses

1. […] can say more: given any nonprincipal ultrafilter $mathcal{F}$, it of course converges to a single point $xin X$, by compact Hausdorffness. Hence its image under any continuous $f:Xto Y$ into a compact […]

2. […] Notice that the fact that this is a compact Hausdorff space follows immediately from equivalence with the product formulation. But just for fun, we briefly see that the Hausdorff compactness of in this construction is also a consequence of the use of ultrafilters themselves to define topological properties. […]

3. […] is just the functor which associates to a set the set of ultrafilters on it (see, for example, this previous post). It follows that the ultrafilters on a set give us the -ary operations on compact Hausdorff […]

4. Thanks for taking the time to reply to my question!

5. Hi,
I know this post is a bit old but I am curious to know how ultrafilters are useful. In particular, did you learn ultrafilters while learning point-set topology for the first time ? I haven’t studied topology in detail yet except for that used in real analysis and I am trying to select a textbook- there are so many texts out there !
Thanks!

• No, I didn’t learn ultrafilters while learning point-set topology for the first time. The first time it’s probably unnecessary to learn about ultrafilters. They’re useful elsewhere, though (e.g. in model theory).

• I think Anonymous meant:
– Did you lear about ultrafilters for the first time in a topological context?
🙂

6. I think I once looked up that the earliest introduction of ultrafilters is found in topology (I think Cartan in the 30s?) to get convergence defined properly. So even though you could consider them creatures of logic, their origin is more topological.

• Dear Peter,

Yes, you are remembering correctly. Bibliographic data for Cartan’s paper (Comptes Rendus, 1937) on filters is given in my notes on convergence that Qiaochu links to above:

http://math.uga.edu/~pete/convergence.pdf

Of course in many ways (and probably in others yet to be discovered) topology, algebra and logic are three sides of the same coi….er, everyday object with at least three sides. Moreover, once you learn about ultrafilters, you start seeing traces of them everywhere: when combined with the fact that probably the majority of research mathematicians live in blissful ignorance of their existence, it’s a pretty strange situation.

• Pete, thank you for the link. I agree that mathematicians are too unaware of their (terrible) beauty (non-measurable sets anyone?). From my point of view I would add that even those aware are not aware how different ultrafilters can be.

Take for example non-standard arguments using ultrapowers. Outside of logic and set theory it seems to be enough to consider an ultrapower by any odd free ultrafilter. At most, I have seen a selective or a p-point being used (which reminds me of another proof of Ramsey’s Theorem via forcing).

Do you know of any example where specific properties of an ultrafilter are used? I can only think of minimal idempotent ultrafilters in ergodic theory.

• on August 30, 2014 at 4:55 am | Reply Mozibur Ullah

There are actually three sides to a *real* coin – top, bottom & the circular rim;of course with the idealised coins that mathematicians like to play with there are only two!

7. […] Comments Ultrafilters in topo… on Boolean rings, ultrafilters, a…Peter Cameron on Empty setsTodd Trimble on […]