An ultrafilter on a set is a collection of subsets of with the following properties: (i) and ; (ii) is closed under finite intersections; (iii) if and then ; (iv) for every , either or . A trivial example of an ultrafilter is the collection of all sets containing some fixed element of Such ultrafilters are called principal. It is not trivial that there are any non-principal ultrafilters, but this can be proved using Zorn's lemma. Here we explain various ways of using non-principal ultrafilters in analysis and infinitary combinatorics.
Some familiarity with basic Ramsey theory; knowledge of the results from a first analysis course.
A filter on a set is a collection of sets with the following three properties: (i) and ; (ii) is closed under finite intersections; (iii) if and then . For example, if then the collection of all sets such that is finite forms a filter (known as the cofinite filter). A filter is called an ultrafilter if in addition it has the property (iv) that for any partition of into two sets and , either belongs to or belongs to .
Notice that an ultrafilter is a maximal filter, since properties (i) and (ii) imply that and cannot both belong to if they form a partition of . The converse is true as well: every maximal filter is an ultrafilter. To see this, suppose that is a maximal filter, that and partition into two sets, and that neither nor belongs to . We shall obtain a contradiction by showing that is not maximal.
Let us attempt to add to . If we do so, then we must also add for every set , and we must add all supersets of these sets. If all the sets are non-empty, then the result will be a filter, since if and , then . From this we see that we can extend unless there is some set with . Similarly, we can extend unless there is some set with . But then, since and are a partition of , , which is a contradiction.
A standard application of Zorn's lemma proves that every filter is contained in a maximal filter. Since no extension of the cofinite filter can contain any finite sets, it follows that non-principal ultrafilters exist.
The following facts about ultrafilters, which follow easily from the basic definition, will be used in this article. Let be an ultrafilter on a set . If is partitioned into finitely many sets , then precisely one belongs to . If and do not belong to then neither does . If any finite set belongs to then is a principal ultrafilter.
Example 1: generalized limits
We can think of the process of taking limits of sequences as a linear functional defined on the convergent sequences. That is, given a convergent sequence we define to be its limit, and we have the two properties and for any two convergent sequences and and any scalar .
Can we generalize by finding a linear functional that is defined on all bounded sequences and not just all convergent ones? In order for it to count as a generalization, we would like to be linear, and we would like to equal whenever is a convergent sequence.
If is a non-principal ultrafilter, and is a sequence that takes values in , then we can define a limit along as follows. Let be the collection of all subintervals of such that belongs to . Then the ultrafilter properties of imply that has all the ultrafilter properties but restricted to intervals. That is, does not contain the empty set, is closed under finite intersections, has the property that if and is an interval that contains then , and if is partitioned into finitely many intervals then at least one of these intervals belongs to .
From this it follows that is something like a "principal interval-ultrafilter". More precisely, it contains all open intervals that contain some particular point . To see this, for each partition into finitely many subintervals of length at most . Then one of these subintervals belongs to . So for every we have an interval of length at most that belongs to . Now let . Since is closed under intersection, belongs to . Let be the intersection of the closures of the (which are non-empty and nested). If is any open interval containing , then contains some , so belongs to .
Thus, we have found a number with the following property: for every , the set belongs to . Moreover, it is easy to see that this is unique. We write it as . It is easy to check that is linear. For example, if and , then and both belong to , and from this and the intersection property of it follows that belongs to . Since this is true for every , . A similar but easier argument deals with scalar multiplication.
To see even more clearly how this ties in with the usual notion of a limit, note that converges to if and only if for every the set belongs to the cofinite filter.
One can rewrite sentences involving " " or " " in terms of set systems. Let be a set and let be the set system consisting of just the set . That is, . Let be the set system consisting of all non-empty subsets of . Then the statement can be rewritten and the statement can be rewritten .
This is of course a silly thing to do, but that is precisely the point I want to make here: it is often better to think of a set system as a quantifier. In particular, if is an ultrafilter then one often finds oneself writing sentences of the form , as we have already seen. But it can be much easier to deal with these sentences if one instead writes . One can read this as "For -almost every , ." As we shall see, this simple notational change can make some statements much easier to understand.
Before we continue, let us translate the ultrafilter axioms into quantifier language.
If then .
If and then .
If then implies .
If then either or .
Actually, the fourth property is not quite a direct translation of the axiom we gave, but of the equivalent property that if belongs to then either belongs to or belongs to . The equivalence is an easy exercise.
To the above properties we can add the following consequences, valid for any property .
If then .
Exactly one of and is true.
Example 2: the infinite Ramsey theorem
The infinite Ramsey theorem that we shall prove here is the statement that if all pairs of natural numbers are coloured either red or blue, then there is an infinite set such that all pairs of elements of have the same colour.
The usual proof goes like this. Build a sequence of integers and at the same time a sequence of infinite sets with the following property: for every , every pair such that has the same colour. To see that this is possible, suppose we have constructed the sequences up to . Let be the smallest element of (which we have defined in such a way that every element of is bigger than ). Then either there are infinitely many elements of such that is red or there are infinitely many elements of such that is blue. Therefore, we can find an infinite subset of such that for every in the pair has the same colour. Let us call red if all the pairs with are red, and blue if they are all blue. Then we can find infinitely many all of the same colour. Since for every , it follows that all pairs have the same colour. The theorem is proved.
Note that in the above proof we often used sentences of the form "for infinitely many , ". The negation of such a statement is "for finitely many , ", which is equivalent to "the set of such that belongs to the cofinite filter". We shall now discuss a proof where the cofinite filter is replaced by an ultrafilter. In the above proof, we regarded a set as large if it was infinite. Now we shall regard a set as large if it belongs to some given non-principal ultrafilter . This turns out to make the proof neater, because now it is not possible for a set and its complement both to be large. Here are the details. We shall make constant use of the quantifier properties just listed.
Let us write for the statement that the pair is red, and for the statement that the pair is blue. Then , which implies that , which implies that , which implies that either or . Without loss of generality it is the first that holds.
Now we construct a sequence inductively, ensuring at each stage that for every and that . If we have got as far as the th stage, then we know that (i) ; (ii) . Therefore we know that for -almost every we have both that for every and that . From this it follows that there exists such that for every and that . Let . Since we also know that , we find that , and the induction continues. The resulting sequence satisfies for every .
The main difference between the proof using ultrafilters and the normal proof is that the proof using ultrafilters decides in advance which colour to go for, and thereby avoids the final use of the pigeonhole principle. This on its own would not be enough of a motivation for coming to grips with ultrafilters, but as we shall see there are other results that have beautifully simple proofs that use ultrafilters.
Central to many of these applications is a notion of ultrafilter addition. If and are ultrafilters defined on , then we define to be . Do you find that hard to take in? If so, then you will appreciate the value of the quantifier notation: a set belongs to if and only if .
A basic fact about ultrafilter addition is that it is associative. The proof without quantifiers is horrendous to look at, but basically trivial. The quantifier notation makes the triviality clear: a set belongs to if and only if , which is true if and only if , which is true if and only if , which is true if and only if .
And now, a non-trivial but very useful fact is that there exist non-principal idempotent ultrafilters: that is, ultrafilters such that . (There is a natural topology on the space of all ultrafilters on , which makes that space compact. It can be shown that every compact semigroup such that addition is left-continuous contains an idempotent. The proof is a beautiful application of Zorn's lemma: one can prove that a minimal closed non-empty subsemigroup must consist of a single element, which is an idempotent ultrafilter.)
Note that the property of being idempotent has the following quantifier reformulation.
if and only if .
Indeed, note also that the definition of ultrafilter addition can be reformulated as follows.
means that .
Example 3: Hindman's theorem
Hindman's theorem is a celebrated result in Ramsey theory, which asserts the following. Suppose that is coloured with finitely many colours. Then it is possible to find such that all numbers of the form , where is a non-empty finite set, have the same colour.
To prove this using an idempotent ultrafilter , we proceed in a fairly similar way to the way we proved Ramsey's theorem. In particular, we once again decide in advance what colour to go for. Since every integer has one of a finite collection of colours, there must be some colour such that -almost every has colour . Let us write for the statement that has colour . So we know that . Now we shall try to build a sequence inductively in such a way that all finite sums have the colour .
What should we hope for at stage ? By then we will have chosen . Clearly we will want to have colour for every . But we need more than this, because we want to have a chance of continuing the induction. For that we want there to be plenty of such that has colour for every . But what does "plenty of " mean? In an ultrafilter proof it can mean only one thing: plenty of have property means that .
Without any real thought we have arrived at the correct inductive hypothesis: that has colour for every , and that for -almost every , has colour for every . Let us introduce a condensed notation for this: we shall write for the set of all sums with Then our inductive hypothesis is .
If this is the case, then , and of course it is also the case that . But then it follows from the intersection property that . But this union is equal to , so we have shown that . From this it follows that there exists such that . This has got us to the next stage of the induction, so the proof is finished.
Example 4: polynomial recurrence of rotations
Here is a cute application of the existence of idempotent ultrafilters due to Vitaly Bergelson. Let be a real number. Our aim is to prove that for every there exists a positive integer such that is within of an integer. To do that, let us first solve an easier problem. We take the compact set and map to it by sending to , which for convenience we shall denote by . Then we calculate . Since is idempotent, this is equal to , which can easily be checked to be the same as . So , from which it follows that .
Now let and let . Since is idempotent, this is equal to , which equals , where the first limit is as varies and the second is as varies. Taking the inner limit first (as we must), and using the previous result with , we find that this equals , which in turn equals . So and therefore .
As one might expect, this proof can be generalized. Indeed, it can be used to prove the same result for , where is any polynomial that vanishes at .
Clearly the definition of ultrafilter addition works for any with a binary operation, and it will be associative if the binary operation on is associative. Let and be idempotent ultrafilters with respect to some associative binary operation on a set . We say that if . It is easy to check that this is a partial order, and it can be shown that for every idempotent there is a minimal idempotent such that . Minimal idempotents turn out to be useful for proving more complicated results with a similar flavour to Hindman's theorem.