Josh's blog

Ultrafilters and ultralimits

These are some notes on ultrafilters and ultralimits that are currently in the draft introduction of my thesis. Feel free to follow along.

Even in seemingly benign situations, ordinary sequential limits can fail to exist. One solution is the ultralimit. To define ultralimits, one needs ultrafilters, and hence filters.

Definition 1 A filter \(F\) on a set \(X\) is a collection of subsets of \(X\) satisfying the following properties:

(F1) \(\emptyset \notin F\) (this mostly serves to exclude the “improper” filter \(\mathcal{P}(X)\));

(F2) If \(A\in F\) then every superset \(B\) is also in \(F\) (it is upwards-closed);

(F3) If \(A\) and \(B\) are in \(F\), then \(A\cap B\in F\).

Note that a filter \(F\) cannot contain any pair of disjoint sets; by (F3) their intersection would be in \(F\), but by (F1), this is a contradiction.

If a set \(A\notin F\) then every subset is also not in \(F\). To see this, suppose some subset \(B\subseteq A\) is in \(F\): by (F2), this implies that \(A\in F\), contradicting \(A\notin F\).

Definition 2 An ultrafilter \(U\) on \(X\) satisfies the further property that for any \(A\subseteq X\), either \(A\) or \(X\backslash A\) is in \(U\).

Since \(A\) and \(X\backslash A\) are disjoint, by the above, for any ultrafilter \(U\) on \(X\), precisely one of them is in \(U\). It is not possible to include more sets in an ultrafilter without it failing to be a filter, so there is no filter finer than an ultrafilter.

Lemma 1 There are two disjoint kinds of ultrafilters on a set \(X\): the principal ultrafilters, containing some singleton set \(\{x\}\) where \(x\in X\), and the non-principal or free ultrafilters, which contain no finite sets at all.

Proof If an ultrafilter \(U\) on \(X\) contains any finite set \(F\), we may see that it necessarily contains a singleton set, and is therfore principal, as follows. Assume that \(\{x\}\notin U\) for all \(x\in X\). In particular \(\{f\}\notin U\) for each \(f\in F\). Thus \(X\backslash\{f\}\in U\) for all \(f\in F\), and by property (F3) we thus have \(F\cap (X\backslash\{f\}) = F\backslash\{f\} \in U\) for all \(f\in F\). Inductively each element of \(F\) can be removed, one at a time, until none remain, at which point it contradicts (F1). \(\square\)

While it is easy to exhibit a principal ultrafilter on many infinite sets, one must rely on some additional axiom to provide the existence of free ultrafilters. The Ultrafilter Lemma (UL) does this nearly directly: UL asserts that every filter is contained within an ultrafilter, and some filters (such as the Fréchet filter described below) can only be contained within a free ultrafilter. The Ultrafilter Lemma is also a consequence of the Axiom of Choice. However, the Axiom of Choice does not follow from the Ultrafilter Lemma, so UL is a weakening of AC. One useful consequence of the Ultrafilter Lemma is the Hahn-Banach theorem.

Since free ultrafilters do not contain any finite sets, by definition they must contain all cofinite sets. The filter consisting of cofinite sets (this is the Fréchet filter) is therefore contained in any free ultrafilter; conversely, any ultrafilter containing the Fréchet filter is a free ultrafilter. The Fréchet filter itself is not usually an ultrafilter: consider two infinite sets which are complements of each other, and so neither is cofinite.

Definition 3 Given any sequence of real or complex numbers \(\{x_n\}_{n=0}^\infty\) and a free ultrafilter \(U\) over \(\mathbb{N}\), if for some value \(x\) and each \(\epsilon>0\), we have

$$\{n: |x_n - x| \le\epsilon\}\in U,$$

then \(x\) is the (unique) ultralimit of the sequence with respect to \(U\), written

$$x = \lim_U x_n \quad\text{or}\quad x = U\text{-}\lim x_n. $$

This generalises to sequences in any metric space \((X,d)\) by

$$x = \lim_U x_n \quad\iff\quad \{n: d(x_n, x) \le\epsilon\}\in U.$$

Note that if we try to do the same thing with a principal ultrafilter, then we allow the ultralimit to take the value of the sequence at a single point. For the ultralimit and ordinary limits to coincide, one must require a free ultrafilter.

Some authors sometimes require, for ultralimits, that the ultrafilter \(U\) over \(\mathbb{N}\) used, instead of explicitly being required to be “free”, is required to contain every interval \([n,\infty)\) for each \(n\in\mathbb{N}\).

Lemma 2 An ultrafilter \(U\) on \(\mathbb{N}\) is free if, and only if, it contains every interval of the form \([n,\infty)\) for each\(n\in\mathbb{N}\).

Proof A free ultrafilter contains all cofinite sets, including as examples the intervals of the form \([n,\infty)\).

To show the converse, suppose a ultrafilter \(U\) contains every interval \([n,\infty)\) for \(n\in\mathbb{N}\), and assume that \(U\) is not free (i.e. principal). \(U\), being principal, contains a singleton set, \(\{k\}\) say, and therefore does not contain \(\mathbb{N}\backslash\{k\} = [1,k) \cup [k+1, \infty)\). Since subsets of sets not in a filter are also not in the filter, this implies \([k+1,\infty)\) is not in \(U\). This contradicts the requirement that every \([n,\infty) \in U\). \(\square\)

Ultralimits provide a resolution to the problem of defining a unique limit for a sequence that fails to converge due to having multiple limit points, effectively by choosing one of the limit points. Intuitively, a free ultrafilter will contain a set of indexes corresponding to one of the convergent subsequences, but none of the others, as they will necessarily be indexed by sets in the complement of the index set of the chosen subsequence. If a sequence is bounded, then by the Bolzano-Weierstrass theorem there is at least one convergent subsequence, so an ultralimit is always defined on bounded sequences.

Sources: mostly Wikipedia.