Comprehending ultrafilters

This is the first of a projected two-part series of articles about ultrafilters. The former introduces ultrafilters and establishes various properties about them, so that the latter article can concentrate entirely on applications of ultrafilters.

Much of this material is from Professor Imre Leader’s lecture course on Ramsey theory, notes of which can be obtained from Paul Russell’s website.

I’ve been intending to write about ultrafilters for some time, but, whilst simple to define and manipulate, they are rather abstract objects. I suppose I’ll first give a formal definition, and then attempt to provide a more intuitive interpretation of what an ultrafilter is.

So, an ultrafilter U on a set S is a collection of subsets of S with the following properties:

  • If A is in U, then every superset of A is also in U (U is an upset);
  • If A and B are in U, then the intersection A ∩ B is also in U;
  • Precisely one of A and S\A belongs to U.

The correct way to view ultrafilters is a way to assign a finitely-additive measure to S, where every set has either measure 0 (almost nothing) or measure 1 (almost everything). Then, U is the collection of big (measure-1) subsets of S. The axioms then have entirely intuitive interpretations:

  • If A is a big set (has measure 1), then so is every superset of A;
  • The union of two measure-0 sets also has measure 0;
  • If A has measure 1, its complement has measure 0, and vice-versa.

Very often, we take S to be the set of positive integers, \mathbb{N}. From the ultrafilter axioms, we can deduce the following:

  • If we partition a measure-1 set into finitely many sets, then precisely one of those has measure 1.

There is a notion of a stronger version of an ultrafilter (on necessarily uncountable sets) where ‘finitely’ is replaced with ‘countably’ (thus is a genuine measure in the usual sense), but their existence is equivalent to that of a certain large cardinal called a measurable cardinal for obvious reasons. Anyway, in the remainder of the article we will only consider ultrafilters on the set N of positive integers.

Examples of ultrafilters

When trying to explain ultrafilters, I am compelled to provide a few examples. The easiest examples to provide are the principal (boring) ultrafilters, such as the following:

A set has measure 1 if and only if it contains the number 7.

There is a principal ultrafilter for each natural number n, by replacing 7 with n. Principal ultrafilters are somewhat silly, since they only care about a single element of S. Note that if a finite set has measure 1 with respect to some ultrafilter, then one of its elements must have measure 1 and the ultrafilter must be principal. So, in a non-principal ultrafilter, all measure-1 sets are infinite (as they should be).

Anyway, what’s an example of a non-principal ultrafilter?

It transpires that non-principal (or free) ultrafilters cannot be explicitly constructed, relying heavily on the axiom of choice. We create an ultrafilter U by extending a filter F, which is a strictly weaker notion than that of an ultrafilter. A filter F need only satisfy the following properties:

  • The empty set does not belong to F;
  • The entire set S does belong to F;
  • If A and B belong to F, then so does the intersection;
  • If A belongs to F, then so does every superset of A.

Unlike ultrafilters, there are lots of interesting examples of filters. For instance, we can take the filter of cofinite sets, where a set belongs to F if and only if its complement is finite.

There is an obvious partial order on the set of filters, namely inclusion. If a filter is not an ultrafilter, then we can extend it by throwing in another set. If we have a chain (totally-ordered set of filters), then the union is a filter which is an upper bound. Hence, by Zorn’s lemma, we can extend any filter to a maximal filter (an ultrafilter).

Ultrafilters as quantifiers

You are probably aware of the universal quantifier ∀ and the existential quantifier ∃. Given your favourite ultrafilter U, we can define the quantifier ∀U (pronounced ‘for U-most’) as follows:

  • ‘∀U x : P(x)’ means ‘P(x) is satisfied by a measure-1 set of x in S’

It has the beautiful property that it distributes over all Boolean operators:

  • ∀U x : (P(x) or Q(x)) ⇔ (∀U x : P(x)) or (∀U x : Q(x))
  • ∀U x : (P(x) and Q(x)) ⇔ (∀U x : P(x)) and (∀U x : Q(x))
  • ∀U x : (not P(x)) ⇔ not (∀U x : P(x))

The first two of these also apply to ∃ and ∀, respectively, but the third applies to neither (∀ and ∃ are interchanged, rather than preserved, when conjugated by logical negation).

Warning: it does not commute with itself (∀U x ∀U y is not the same as ∀U y ∀U x). This again contrasts with the more familiar logical quantifiers.

The Stone-Cech compactification of N

The space of ultrafilters on the positive integers is denoted βN and admits a natural topology. Specifically, we define a base of open sets:

  • For every set A of positive integers, let C(A) = {U in βN | A in U} be an open set.

C(N) and C(Ø) are βN and Ø, respectively. The intersection of two base sets, C(A) and C(B), is easily verified to be C(A ∩ B), so this is indeed a base of open sets. A set is open if and only if it is some arbitrary union of base sets. Note that again we have C distributing over everything:

  • C(A ∩ B) = C(A) ∩ C(B)
  • C(A ∪ B) = C(A) ∪ C(B)
  • C(N \ A) = C(N) \ C(A) = βN \ C(A)

In particular, the base sets C(A) are both open and closed.

So, why are we interested in the topology on βN? It transpires that it has several very nice properties:

  • Hausdorffness: For two distinct ultrafilters, U and V, we can find a set A such that A belongs to U but not to V. Then, C(A) contains U and C(N\A) contains V. Since C(A) and C(N\A) are disjoint open sets, this means that βN is a Hausdorff space.
  • Compactness: Suppose we have a collection P of closed sets, such that the intersection of any finite subset of P is non-empty. It suffices to consider the case where the elements of P are all base sets. Indeed, let P = {C(A) : A in Q}, where Q is a collection of subsets of N, such that any intersection of finitely many elements of Q is non-empty. Let F be the filter of all supersets of elements of Q, and extend it to an ultrafilter U. U must necessarily belong to all elements of P, and therefore their intersection. This establishes the finite intersection property, which is trivially equivalent to topological compactness.
  • N is dense in βN: We can embed N in βN by associating the number n with the principal ultrafilter {A in N : n in A}. Then N is a dense subset of βN, since for every non-empty C(A) in the base of open sets, we can choose an arbitrary a in A and observe that the principal ultrafilter on a belongs to C(A). βN is actually the largest compact Hausdorff space in which N is dense, and is called the Stone-Cech compactification of N. It is a surprising fact — which is not too difficult but still non-trivial to prove – that after removing N from βN, we are left with an inseparable space (one with no countable dense subset).

Even though it is very nice from a topological point of view, little is known about βN. Assuming the continuum hypothesis, Parovicenko proved that several topological assumptions are sufficient to characterise βN; conversely, in the absence of the continuum hypothesis, there exist non-homeomorphic spaces satisfying the same properties. Also, if we assume certain large cardinal axioms, then βN has completely different properties than under the (incompatible) assumption of the continuum hypothesis.

Ultrafilter addition and idempotent ultrafilters

Recall that N admits a commutative addition operation. This can be extended to a non-commutative addition on βN, where we define the sum of two ultrafilters as follows:

  • U + V = {A ⊆ N | ∀U x ∀V y : x + y in A}

Note that this can easily be verified to satisfy the defining properties of an ultrafilter. This is associative, since (U + V) + W = U + (V + W) = {A ⊆ N | ∀U x ∀V y ∀W z : x + y + z in A}. We can also prove that it is left-continuous, that is to say that U + V is a continuous function of U. Of course, working in a general topological space, there is only one definition of continuity that we’re allowed to use: the pre-image of an open set is open.

It suffices to prove that, for an arbitrary fixed ultrafilter V, the pre-image of C(A) is always open, for every A ⊆ N. So, let’s unpack the definitions:

Note that U + V = {A ⊆ N | ∀U x : (∀V y : x + y in A)}, so the pre-image of C(B) is the set:

  • {U in βN | {A ⊆ N | ∀U x : (∀V y : x + y in A)} in C(B)}
  • = {U in βN | B in {A ⊆ N | ∀U x : (∀V y : x + y in A)}}
  • = {U in βN | ∀U x : (∀V y : x + y in B)}
  • = {U in βN | {x in N | (∀V y : x + y in B)} in U}
  • = C({x in N | (∀V y : x + y in B)})

which is open, by definition. To summarise, the operation + is associative and left-continuous, and βN is a compact Hausdorff space. We’re now going to forget absolutely everything else about ultrafilters, and prove the following lemma:

The idempotent lemma: If X is a non-empty compact Hausdorff space and + is a left-continuous associative operation, then there exists x in X such that x + x = x.

The proof requires extensive use of Zorn’s lemma.

We firstly consider the collection S of non-empty closed sets Y with the property that Y + Y is a subset of Y. The entire space X is trivially one such example, so our collection S is non-empty. Endow S with the partial order of inclusion.

If we have a chain of such sets, then the intersection is non-empty (since all finite intersections are non-empty, and we are working in a compact Hausdorff space where compact sets are closed and vice-versa) and closed (by virtue of being an intersection of closed sets). So, every chain has a ‘lower bound’ in S and thus we can find a minimal Y by Zorn’s lemma.

Choose an arbitrary x in Y, which we can do by the fact that Y is non-empty. Y + x is the continuous image of a non-empty compact set, thus non-empty and compact. Also, (Y + x) + (Y + x) = Y + Y + x + x, by associativity, which is clearly a subset of Y + x. Hence, Y + x is also in S and is a subset of Y, so Y + x = Y (as otherwise Y + x would be more minimal than Y).

Now define Z = {y in Y | y + x = x}, which is non-empty since Y + x = Y, and Y contains x. It is the pre-image of a singleton set (which must be compact and thus closed) under a continuous function, so is itself closed. If y and y‘ both belong to Z, then (y + y‘) + x = y + (y‘ + x) = y + x = x, so Z + Z is a subset of Z and therefore belongs to S. So Z = Y by minimality of Y.

Hence, since x is in Y, x is in Z and therefore x + x = x, concluding our claim.

Consequently, there must exist an ultrafilter U with U + U = U. It is clear that such an ultrafilter must necessarily be non-principal. U is known as an idempotent ultrafilter. Non-principal ultrafilters themselves already have many applications (as we shall see in the follow-up post), but idempotent ultrafilters are even more useful, powerful and generally awesome. I can imagine that you’re all bursting with excitement in anticipation of the follow-up article, so I shall endeavour to write it as soon as feasibly possible.

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to Comprehending ultrafilters

  1. wojowu says:

    Thank you for this article. I haven’t asked for it, but it seems to clarify everything about ultrafilters I wished to know :) I also ask for few things about article:
    You mentioned that “There is a principal ultrafilter for each natural number n”, but you seem to forgot to mention these are all, i.e. principal ultrafilters are exactly these defined by single element.
    When mentioning measurable cardinals, you said they have to be countably additive. On Wikipedia, it’s said that it must be κ-additive. Does former imply latter?
    Other than that, I wish you Merry Christmas! (P.S. I love the new logo ^^)

    • apgoucher says:

      Thank you, and Merry Christmas!

      Yes, I promised that I would have a Christmas-themed banner over the festive period (and I’m going to re-use last winter’s New Year banner).

      Stanislaw Ulam (who deserves to be better known than he currently is) showed that if κ is the minimal cardinal admitting a countably-additive measure, then κ must also admit a κ-additive measure. Hence, the existence of a countably-additive ultrafilter is indeed equivalent to the axiom that a measurable cardinal exists.

  2. Pingback: Applications of ultrafilters | Complex Projective 4-Space

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s