Tuesday, September 25, 2012

Where Do Ultrafilters Come From?

Where Do Ultrafilters Come From?:


MathML-enabled post (click for more details).

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.

MathML-enabled post (click for more details).

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 X be a set. An ultrafilter on X is
a set Ω of subsets such that whenever X 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 X be a set. An ultrafilter on X is
a set Ω of subsets such that whenever X 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 X and element x∈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 Ω on X. Let f be a
function from X to a finite set B. By the second definition above,
there is a unique b∈B whose fibre f −1(b) belongs to Ω. I
claim that b deserves to be called

∫ XfdΩ.

In other words, I claim that ∫ XfdΩ is the correct notation
for the unique element of B satisfying

f −1(∫ XfdΩ)∈Ω.

This integral notation imitates the standard notation from
measure theory. There, if μ is a measure on a space X and f is a
function on X, the integral of f against μ is written as ∫ Xfdμ.

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 Ω. Given a “nice”
function f on X, say f:X→B, the integral of f against
Ω 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 Ω 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 Ω), then their
    integrals should be equal.



And the fact is: the unique “integration” rule satisfying these two
conditions is ∫ X−dΩ, 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 ℝ 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 f:X→B, you can imagine each “voter” x∈X choosing a single element f(x) from the set B of all possible
“options”. Any ultrafilter Ω on X thinks that there’s one option
chosen by almost all of the voters, namely, ∫ XfdΩ.

Before the election, you could decide to use Ω as your
voting system, so that the final outcome of the election is ∫ XfdΩ∈B. This is
always unfair, but if Ω is the principal ultrafilter on some x∈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
Ω on X, we can integrate against Ω. The operation of
integration turns functions from X to a finite set B into elements of
B:

∫ X−dΩ:[X,B]→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 ∫ X−dΩ is an
element of the end

∫ B∈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
FinSet↪Set, evaluated at X. That is:
let G be the inclusion functor FinSet↪Set, and let T G be the codensity monad of G. Then (by
definition, if you like)

T G(X)=∫ B∈FinSet[[X,B],B].

So, given an ultrafilter Ω on a set X, you get an element ∫ X−dΩ 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:Set→Set. Since everything works
nicely, integrating against an
ultrafilter defines a natural transformation U→T G,

Ω↦∫ X−dΩ.

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→T G
respects the monad structures.

But best of all, this transformation U→T G is actually
an isomorphism:



Theorem  The codensity monad of the inclusion
FinSet↪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 B be a full subcategory of
FinSet containing at least one set with at least 3
elements. Then the codensity monad of the inclusion
B↪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
B is the whole of FinSet.

The other extreme case is
where B consists of a single finite set B with three or more
elements. In that case, the codensity monad T G of B↪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]→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]→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.


DIGITAL JUICE

No comments:

Post a Comment

Thank's!