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 . 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: .
(Out of interest: how many readers can’t see the wedding-invitation U here: ?)
What’s an ultrafilter?
Definition Let be a set. An ultrafilter on is a set of subsets such that whenever is expressed as a disjoint union of three subsets, exactly one belongs to .
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 be a set. An ultrafilter on is a set of subsets such that whenever is expressed as a disjoint union of a finite number of subsets, exactly one belongs to .
The first thing anyone needs to know about ultrafilters is that there are some rather trivial examples. Given any set and element , the principal ultrafilter on is the set of all subsets containing .
The second thing anyone needs to know is that there are other examples, but it’s impossible to describe them explicitly. If is finite then the principal ultrafilters are the only ultrafilters on . If is infinite, however, there are nonprincipal ultrafilters on — but proving this makes essential use of the axiom of choice.
Suppose now that we have an ultrafilter on . Let be a function from to a finite set . By the second definition above, there is a unique whose fibre belongs to . I claim that deserves to be called
In other words, I claim that is the correct notation for the unique element of satisfying
This integral notation imitates the standard notation from measure theory. There, if is a measure on a space and is a function on , the integral of against is written as .
So, we’re thinking of an ultrafilter on as something like a measure on . If probability indicates your degree of belief, an ultrafilter is a probability measure for fundamentalists: everything has probability or . The subsets of with measure are exactly the elements of the ultrafilter; every other subset has measure . A more precise statement is that the ultrafilters on a set correspond one-to-one with the finitely additive probability measures on , 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 equipped with an ultrafilter . Given a “nice” function on , say , the integral of against should be an element of . Here I’ll interpret “nice” as meaning simply that is finite. Whatever integration is, it should at the very least satisfy the following two conditions:
- Since is a kind of probability measure (meaning that the measure of the whole of is ), the integral of a constant function should be that constant.
- If two functions and are equal almost everywhere (that is, the set of points of where they agree belongs to ), then their integrals should be equal.
And the fact is: the unique “integration” rule satisfying these two conditions is , 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 carries some algebraic structure, which is what we’re used to — classically, integrands take values in or . 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 , you can imagine each “voter” choosing a single element from the set of all possible “options”. Any ultrafilter on thinks that there’s one option chosen by almost all of the voters, namely, .
Before the election, you could decide to use as your voting system, so that the final outcome of the election is . This is always unfair, but if is the principal ultrafilter on some , it’s spectacularly unfair: the outcome of the election is simply the option chosen by the privileged voter .
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 be any set. Whenever we have an ultrafilter on , we can integrate against . The operation of integration turns functions from to a finite set into elements of :
Here is the set of functions from to .
Everything about integration against ultrafilters works nicely. In particular, integration against an ultrafilter is natural in the codomain . Categorically, this says that is an element of the end
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 , evaluated at . That is: let be the inclusion functor , and let be the codensity monad of . Then (by definition, if you like)
So, given an ultrafilter on a set , you get an element of . You can think of as the set of “integrals”, or integration operators, on .
We can bundle this up into a neat categorical statement. The ultrafilters on a set form another set, , and this defines a functor . Since everything works nicely, integrating against an ultrafilter defines a natural transformation ,
In fact, 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 respects the monad structures.
But best of all, this transformation is actually an isomorphism:
Theorem The codensity monad of the inclusion 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 as a lattice homomorphism from the power set of 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 be a full subcategory of containing at least one set with at least 3 elements. Then the codensity monad of the inclusion 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 .
One extreme case of this theorem is Kennison and Gildenhuys’s, where is the whole of .
The other extreme case is where consists of a single finite set with three or more elements. In that case, the codensity monad of is particularly easy to describe. For any set , the set has a natural action by the monoid of endomorphisms of . Of course, itself has a natural action by too. Then is simply the set of maps preserving the -action. Hence:
Theorem Let be a finite set with at least three elements. Then for any set , the set of -equivariant maps is canonically isomorphic to the set of ultrafilters on .
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 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 is actually codense in ? What do -algebras look like constructively?