Where Do Ultrafilters Come From?
Posted by Tom Leinster
Here’s the central point of my new paper:
There is a standard piece of categorical machinery which, when fed the notion of finiteness of a set, produces as output the notion of ultrafilter.
More snappily:
Ultrafilters are inevitable.
The categorical machine I’m referring to is the one that makes codensity monads (which I explained last time). The result isn’t mine: it seems to have first appeared in a paper published the year I was born. But it deserves to be better known.
I’ll tell you roughly how the theorem works — and, perhaps more importantly, I’ll tell you what it means to integrate against an ultrafilter.
First a technological remark: usually I’d use a fancy-font capital letter U to denote an ultrafilter, something like $\mathcal{U}$. But I’m not sure how many people will be able to read that. (I know that until I installed some extra fonts, I wasn’t able to read all the symbols here.) So instead, I’ll use a capital omega: $\Omega$.
(Out of interest: how many readers can’t see the wedding-invitation U here: $\mathcal{U}$?)
What’s an ultrafilter?
Definition Let $X$ be a set. An ultrafilter on $X$ is a set $\Omega$ of subsets such that whenever $X$ is expressed as a disjoint union of three subsets, exactly one belongs to $\Omega$.
This isn’t the usual definition, but it’s equivalent (Proposition 1.5 of my paper). You can change “three” to any larger integer, but not to “two” — that gives a strictly weaker condition.
An equivalent definition is:
Definition Let $X$ be a set. An ultrafilter on $X$ is a set $\Omega$ of subsets such that whenever $X$ is expressed as a disjoint union of a finite number of subsets, exactly one belongs to $\Omega$.
The first thing anyone needs to know about ultrafilters is that there are some rather trivial examples. Given any set $X$ and element $x \in X$, the principal ultrafilter on $x$ is the set of all subsets containing $x$.
The second thing anyone needs to know is that there are other examples, but it’s impossible to describe them explicitly. If $X$ is finite then the principal ultrafilters are the only ultrafilters on $X$. If $X$ is infinite, however, there are nonprincipal ultrafilters on $X$ — but proving this makes essential use of the axiom of choice.
Suppose now that we have an ultrafilter $\Omega$ on $X$. Let $f$ be a function from $X$ to a finite set $B$. By the second definition above, there is a unique $b \in B$ whose fibre $f^{-1}(b)$ belongs to $\Omega$. I claim that $b$ deserves to be called
$\int_X f \, d\Omega.$
In other words, I claim that $\int_X f\, d\Omega$ is the correct notation for the unique element of $B$ satisfying
$f^{-1} \biggl( \int_X f\, d\Omega \biggr) \in \Omega.$
This integral notation imitates the standard notation from measure theory. There, if $\mu$ is a measure on a space $X$ and $f$ is a function on $X$, the integral of $f$ against $\mu$ is written as $\int_X f \, d\mu$.
So, we’re thinking of an ultrafilter on $X$ as something like a measure on $X$. If probability indicates your degree of belief, an ultrafilter is a probability measure for fundamentalists: everything has probability $0$ or $1$. The subsets of $X$ with measure $1$ are exactly the elements of the ultrafilter; every other subset has measure $0$. A more precise statement is that the ultrafilters on a set $X$ correspond one-to-one with the finitely additive probability measures on $X$, as noted in Lemma 3.1 of my paper (and many times before).
But what could it mean to integrate against an ultrafilter?
Take a set $X$ equipped with an ultrafilter $\Omega$. Given a “nice” function $f$ on $X$, say $f\colon X \to B$, the integral of $f$ against $\Omega$ should be an element of $B$. Here I’ll interpret “nice” as meaning simply that $B$ is finite. Whatever integration is, it should at the very least satisfy the following two conditions:
- Since $\Omega$ is a kind of probability measure (meaning that the measure of the whole of $X$ is $1$), the integral of a constant function should be that constant.
- If two functions $f$ and $g$ are equal almost everywhere (that is, the set of points of $X$ where they agree belongs to $\Omega$), then their integrals should be equal.
And the fact is: the unique “integration” rule satisfying these two conditions is $\int_X - \, d\Omega$, as defined above.
This tells us we’ve got the right definition of integration. Further confirmation comes from the fact that there’s a formula for integration under a change of variables, exactly analogous to the classical one. There are also nice things to say when the codomain $B$ carries some algebraic structure, which is what we’re used to — classically, integrands take values in $\mathbb{R}$ or $\mathbb{C}$. You can find all this in sections 3 and 4 of my paper.
Aside A function is like an election. When you have a function $f\colon X \to B$, you can imagine each “voter” $x \in X$ choosing a single element $f(x)$ from the set $B$ of all possible “options”. Any ultrafilter $\Omega$ on $X$ thinks that there’s one option chosen by almost all of the voters, namely, $\int_X f \, d\Omega$.
Before the election, you could decide to use $\Omega$ as your voting system, so that the final outcome of the election is $\int_X f \, d\Omega \in B$. This is always unfair, but if $\Omega$ is the principal ultrafilter on some $x \in X$, it’s spectacularly unfair: the outcome of the election is simply the option chosen by the privileged voter $x$.
There’s more on the voting/ultrafilter connection in a couple of blog posts: one of Terry Tao’s, and one of mine.
Let’s take stock. Let $X$ be any set. Whenever we have an ultrafilter $\Omega$ on $X$, we can integrate against $\Omega$. The operation of integration turns functions from $X$ to a finite set $B$ into elements of $B$:
$\int_X - \, d\Omega \colon [X, B] \to B.$
Here $[X, B]$ is the set of functions from $X$ to $B$.
Everything about integration against ultrafilters works nicely. In particular, integration against an ultrafilter is natural in the codomain $B$. Categorically, this says that $\int_X - \, d\Omega$ is an element of the end
$\int_{B \in \mathbf{FinSet}} [[X, B], B].$
It’s unfortunate that the integral sign is being used in two different ways here, but there we are: they’re both standard notation, and it shouldn’t cause confusion. Anyway, if you know about codensity monads — for instance, if you read my last post — that end formula should look familiar. It’s the codensity monad of the inclusion functor $\mathbf{FinSet} \hookrightarrow \mathbf{Set}$, evaluated at $X$. That is: let $G$ be the inclusion functor $\mathbf{FinSet} \hookrightarrow \mathbf{Set}$, and let $T^G$ be the codensity monad of $G$. Then (by definition, if you like)
$T^G(X) = \int_{B \in \mathbf{FinSet}} [[X, B], B].$
So, given an ultrafilter $\Omega$ on a set $X$, you get an element $\int_X - \, d\Omega$ of $T^G(X)$. You can think of $T^G(X)$ as the set of “integrals”, or integration operators, on $X$.
We can bundle this up into a neat categorical statement. The ultrafilters on a set $X$ form another set, $U(X)$, and this defines a functor $U \colon \mathbf{Set} \to \mathbf{Set}$. Since everything works nicely, integrating against an ultrafilter defines a natural transformation $U \to T^G$,
$\Omega \mapsto \int_X - \, d\Omega.$
In fact, $U$ is a monad in a unique way; I won’t say how, but you can read about it in my paper. It’s called the ultrafilter monad. As you might hope, our natural transformation $U \to T^G$ respects the monad structures.
But best of all, this transformation $U \to T^G$ is actually an isomorphism:
Theorem The codensity monad of the inclusion $\mathbf{FinSet} \hookrightarrow \mathbf{Set}$ is isomorphic to the ultrafilter monad.
So if ultrafilters are regarded as measures, this says that there’s a one-to-one correspondence between measures and integrals.
In my paper, I attribute this result to Ernie Manes, who included it as a guided exercise in his 1976 book Algebraic Theories. But in my last post, Tim Porter pointed out an earlier text in which the result appeared (thanks, Tim!):
- J. F. Kennison, Dion Gildenhuys, Equational completion, model induced triples and pro-objects, Journal of Pure and Applied Algebra 1 (1971), 317–346.
(Neither they nor Manes use the language of integration.)
The theorem justifies my claim at the beginning of this post: that if you take general categorical constructions for granted, the notion of ultrafilter is inherent in the notion of finitness of a set.
This isn’t the only way to conclude that “ultrafilters are inevitable”: for instance, you can view an ultrafilter on a set $X$ as a lattice homomorphism from the power set of $X$ to the two-element lattice. But perhaps the notion of lattice is slightly less primitive than the notion of finite set.
Actually, Kennison and Gildenhuys’s theorem can be strengthened. Theorem 3.5 of my paper states:
Theorem Let $\mathbf{B}$ be a full subcategory of $\mathbf{FinSet}$ containing at least one set with at least 3 elements. Then the codensity monad of the inclusion $\mathbf{B} \hookrightarrow \mathbf{Set}$ is isomorphic to the ultrafilter monad.
The isomorphism is, again, a version of the one-to-one correspondence between integrals and measures. The number 3 here is the same 3 as appears in the definition of ultrafilter given at the start. Again, it can’t be lowered to $2$.
One extreme case of this theorem is Kennison and Gildenhuys’s, where $\mathbf{B}$ is the whole of $\mathbf{FinSet}$.
The other extreme case is where $\mathbf{B}$ consists of a single finite set $B$ with three or more elements. In that case, the codensity monad $T^G$ of $\mathbf{B} \hookrightarrow \mathbf{Set}$ is particularly easy to describe. For any set $X$, the set $[X, B] = B^X$ has a natural action by the monoid $End(B)$ of endomorphisms of $B$. Of course, $B$ itself has a natural action by $End(B)$ too. Then $T^G(X)$ is simply the set of maps $[X, B] \to B$ preserving the $End(B)$-action. Hence:
Theorem Let $B$ be a finite set with at least three elements. Then for any set $X$, the set of $End(B)$-equivariant maps $[X, B] \to B$ is canonically isomorphic to the set of ultrafilters on $X$.
This result seems to be due to Lawvere, though he also seems not to have published it. Todd Trimble told me about it, and has written about it at the nLab.
Re: Where Do Ultrafilters Come From?
The fact that you need a form of the axiom of choice to produce nonprincipal ultrafilters means that in constructive mathematics, ultrafilters are not usually very useful. So I wonder, how constructive is Kennison and Gildenhuys’s theorem? On the one hand, if it is not constructive, then maybe elements of $T^G(X)$ could serve as a constructive substitute for ultrafilters in some contexts. But on the other hand, if it is constructive, then could there be models of set theory (with dramatic failures of AC) in which $FinSet$ is actually codense in $Set$? What do $T^G$-algebras look like constructively?