# Transgressing the limits

Today, the 14th of January 2014, we had a special session of our Theory Lunch. I spoke about ultrafilters and how they allow to generalize the notion of limit.

Consider the space $\ell^\infty$ of bounded sequences of real numbers, together with the supremum norm. We would like to define a notion of limit which holds for every $\{x_n\}_{n \geq 0} \in \ell^\infty$ and satisfies the well known properties of standard limit:

1. Linearity: $\lim_{n \to \infty} (\lambda x_n + \mu y_n) = \lambda \lim_{n \to \infty} x_n + \mu \lim_{n \to \infty} y_n$.
2. Homogeneity: $\lim_{n \to \infty} (x_n \cdot y_n) = (\lim_{n \to \infty} x_n) \cdot (\lim_{n \to \infty} y_n)$.
3. Monotonicity: if $x_n \leq y_n$ for every $n \geq 0$ then $\lim_{n \to \infty} x_n \leq \lim_{n \to \infty} y_n$.
4. Nontriviality: if $x_n = 1$ for every $n \geq 0$ then $\lim_{n \to \infty} x_n = 1$.
5. Consistency: if the limit exists in the classical sense, then the two notions coincide.

The consistency condition is reasonable also because it avoids trivial cases: if we fix $n_0 \in \mathbb{N}$ and we define the limit of the sequence $x_n$ as the value $x_{n_0}$, then the first four properties are satisfied.

Let us recall the classical definition of limit: we say that $x_n$ converges to $x$ if and only if, for every $\varepsilon > 0$, the set of values $n \in \mathbb{N}$ such that $|x_n - x| < \varepsilon$ is cofinite, i.e., has a finite complement: the inequality $|x_n - x| \geq \varepsilon$ can be satisfied at most for finitely many values of $n$. The family $\mathcal{F}$ of cofinite subsets of $\mathbb{N}$ (in fact, of any set $X$) has the following properties:

1. Upper closure: if $A \in \mathcal{F}$ and $B \supseteq A$ then $B \in \mathcal{F}$.
2. Meet stability: if $A,B \in \mathcal{F}$ then $A \cap B \in \mathcal{F}$.

A family $\mathcal{F}$ of subsets of $X$ with the two properties above is called a filter on $X$. An immediate example is the trivial filter $\mathcal{F} = \{X\}$; another example is the improper filter $\mathcal{F} = \mathcal{P}(X)$. The family $\mathcal{F}(X)$ of cofinite subset of $X$ is called the Fréchet filter on $X$. The Fréchet filter is not the improper one if and only if $X$ is infinite.

An ultrafilter on $X$ is a filter $\mathcal{U}$ on $X$ satisfying the following additional conditions:

1. Properness: $\emptyset \not \in \mathcal{U}$.
2. Maximality: for every $A \subseteq X$, either $A \in \mathcal{U}$ or  $X \setminus A \in \mathcal{U}$.

For example, if $x \in X$, then $(x) = \{ A \subseteq X \mid x \in A \}$ is an ultrafilter on $X$, called the principal ultrafilter generated by $x$. Observe that $\bigcap_{A \in (x)} A = \{x\}$: if $\bigcap_{A \in \mathcal{U}} A = \emptyset$ we say that $\mathcal{U}$ is free. These are, in fact, the only two options.

Lemma 1. For a proper filter $\mathcal{F}$ to be an ultrafilter, it is necessary and sufficient that it satisfies the following condition: for every $n \geq 2$ and nonempty $A_1, \ldots, A_n \subseteq X$, if $\bigcup_{i=1}^n A_i \in \mathcal{F}$ then $A_i \in \mathcal{F}$ for at least one $i \in \{1, \ldots, n\}$.

Proof: It is sufficient to prove the thesis with $n=2$. If $A \cup B \in \mathcal{F}$ with $A,B \not \in \mathcal{F}$, then $\mathcal{F}' = \{ B' \subseteq X \mid B' \neq \emptyset, A \cup B' \in \mathcal{F} \}$ is a proper filter that properly contains $\mathcal{F}$. If the condition is satisfied, for every $A \subseteq X$ which is neither $\emptyset$ nor $X$ we have $A \cup (X \setminus A) = X \in \mathcal{F}$, thus either $A \in \mathcal{F}$ or $X \setminus A \in \mathcal{F}$. $\Box$

Theorem 1. Every nonprincipal ultrafilter is free. In addition, an ultrafilter is free if and only if it extends the Fréchet filter. In particular, every ultrafilter over a finite set is principal.

Proof: Let $\mathcal{U}$ be a nonprincipal ultrafilter. Let $x \in X$: then $\mathcal{U} \neq (x)$, so either there exists $B \subseteq X$ such that $x \not \in B$ and $B \in \mathcal{U}$, or there exists $B' \subseteq X$ such that $x \in B'$ and $B' \not \in \mathcal{U}$. In the first case, $x \not \in \bigcap_{A \in \mathcal{U}} A$; in the second case, we consider $B = X \setminus B'$ and reduce to the first case. As $x$ is arbitrary, $\mathcal{U}$ is free.

Now, for every $x \in X$ the set $X \setminus \{x\}$ belongs to $\mathcal{F}(X)$ but not to $(x)$: therefore, no principal ultrafilter extends the Fréchet filter. On the other hand, if $\mathcal{U}$ is an ultrafilter, $A \subseteq X$ is finite, and $X \setminus A \not \in \mathcal{U}$, then $A \in \mathcal{U}$ by maximality, hence $\{x\} \in \mathcal{U}$ for some $x \in A$ because of Lemma 1, thus $\mathcal{U} = (x)$ cannot be a free ultrafilter. $\Box$

So it seems that free ultrafilters are the right thing to consider when trying to expand the concept of limit. There is an issue, though: we have not seen any single example of a free ultrafilter; in fact, we do not even (yet) know whether free ultrafilters do exist! The answer to this problem comes, in a shamelessly nonconstructive way, from the following

Ultrafilter lemma. Every proper filter can be extended to an ultrafilter.

The ultrafilter lemma, together with Theorem 1, implies the existence of free ultrafilters on every infinite set, and in particular on $\mathbb{N}$. On the other hand, to prove the ultrafilter lemma the Axiom of Choice is required, in the form of Zorn’s lemma. Before giving such proof, we recall that a family of sets has the finite intersection property if every finite subfamily has a nonempty intersection: every proper filter has the finite intersection property.

Proof of the ultrafilter lemma. Let $\mathcal{F}$ be a proper filter on $X$ and let $\mathcal{M}$ be the family of the collections of subsets of $X$ that extend $\mathcal{F}$ and have the finite intersection property, ordered by inclusion. Let $\{U_i\}_{i \in I}$ be a totally ordered subfamily of $\mathcal{M}$: then $U = \bigcup_{i \in I} U_i$ extends $\mathcal{F}$ and has the finite intersection property, because for every finitely many $A_1, \ldots, A_n \in U$ there exists by construction $i \in I$ such that $A_1, \ldots, A_n \in U_i$.

By Zorn’s lemma, $\mathcal{M}$ has a maximal element $\mathcal{U}$, which surely satisfies $\emptyset \not \in \mathcal{U}$ and $\mathcal{F} \subseteq \mathcal{U}$. If $A \in \mathcal{U}$ and $B \supseteq A$, then $\mathcal{U} \cup \{B\}$ still has the finite intersection property, therefore $B \in \mathcal{U}$ by maximality. If $A,B \in \mathcal{U}$ then $\mathcal{U} \cup \{A \cap B\}$ still has the finite intersection property, therefore again $A \cap B \in \mathcal{U}$ by maximality.

Suppose, for the sake of contradiction, that there exists $A \subseteq X$ such that $A \not \in \mathcal{U}$ and $X \setminus A \not \in \mathcal{U}$: then neither $\mathcal{U} \cup \{A\}$ nor $\mathcal{U} \cup \{X \setminus A\}$ have the finite intersection property, hence there exist $A_1, \ldots, A_m, B_1, \ldots, B_n \in \mathcal{U}$ such that $A_1 \cap \ldots \cap A_m \cap A = B_1 \cap \ldots \cap B_n \cap (X \setminus A) = \emptyset$. But $A_1 \cap \ldots \cap A_m \cap A = \emptyset$ means $A_1 \cap \ldots \cap A_m \subseteq X \setminus A$, and $B_1 \cap \ldots \cap B_n \cap (X \setminus A) = \emptyset$ means $B_1 \cap \ldots \cap B_n \subseteq A$: therefore,

$A_1 \cap \ldots \cap A_m \cap B_1 \cap \ldots \cap B_n \subseteq (X \setminus A) \cap A = \emptyset,$

against $\mathcal{U}$ having the finite intersection property. $\Box$

We are now ready to expand the idea of limit. Let $(X,d)$ be a metric space and let $\mathcal{U}$ be an ultrafilter on $X$: we say that $x \in X$ is the ultralimit of the sequence $\{x_n\}_{n \geq 0} \subseteq X$ along $\mathcal{U}$ if for every $\varepsilon > 0$ the set

$\{ n \geq 0 \mid d(x_n, x) < \varepsilon \}$

belongs to $\mathcal{U}$. (Observe how, in the standard definition of limit, the above set is required to belong to the Fréchet filter.) If this is the case, we write

$\lim_{n \to \mathcal{U}} x_n = x$

Ultralimits, if they exist, are unique and satisfy our first four conditions. Moreover, the choice of a principal ultrafilter $\mathcal{U} = (n_0)$ corresponds to the trivial definition $\lim_{n \to \mathcal{U}} x_n = x_{n_0}$. So, what about free ultrafilters?

Theorem 2. Every bounded sequence of real numbers has an ultralimit along every free ultrafilter on $\mathbb{N}$.

Proof: It is not restrictive to suppose $x_n \in [0,1]$ for every $n \geq 0$. Let $\mathcal{U}$ be an arbitrary, but fixed, free ultrafilter on $\mathbb{N}$. We will construct a sequence of closed intervals $A_k$, $k \geq 0$, such that $A_{k+1} \subseteq A_k$ and $\mathrm{diam} \, A_k = 2^{-k}$ for every $k \geq 0$. By the Cantor intersection theorem it will be $\bigcap_{k \geq 0} A_k = \{x\}$: we will then show that $\lim_{n \to \mathcal{U}} x_n = x$.

Let $A_0 = [0,1]$. Let $A_1$ be either $[0,1/2]$ or $[1/2,1]$, chosen according to the following criterion: $\{n \geq 0 \mid x_n \in A_1\} \in \mathcal{U}$. If both halves satisfy the criterion, then we just choose one once and for all. We iterate the procedure by always choosing $A_{k+1}$ as one of the two halves of $A_k$ such that $\{n \geq 0 \mid x_n \in A_{k+1}\} \in \mathcal{U}$.

Let $\bigcap_{k \geq 0} A_k = \{x\}$. Let $\varepsilon > 0$, and let $k$ be so large that $2^{-k} < \varepsilon$: then $A_k \subseteq (x-\varepsilon, x+\varepsilon)$, thus $\{n \geq 0 \mid x_n \in A_k\} \subseteq \{n \geq 0 \mid |x_n-x| < \varepsilon\}$. As the smaller set belongs to $\mathcal{U}$, so does the larger one. $\Box$

We have thus almost achieved our original target: a notion of limit which applies to every bounded sequence of real numbers. Such notion will depend on the specific free ultrafilter we choose: but it is already very reassuring that such a notion exists at all! To complete our job we need one more check: we have to be sure that the definition is consistent with the classical one. And this is indeed what happens!

Theorem 3. Let $\{x_n\}_{n \geq 0}$ be a sequence of real numbers and let $x \in \mathbb{R}$. Then $\lim_{n \to \infty} x_n = x$ in the classical sense if and only if $\lim_{n \to \mathcal{U}} x_n = x$ for every free ultrafilter $\mathcal{U}$ on $\mathbb{N}$.

To prove Theorem 3 we make use of an auxiliary result, which is of interest by itself.

Lemma 2. Let $\mathcal{M}(X)$ be the family of collections of subsets of $X$ that have the finite intersection property. The maximal elements of $\mathcal{M}$ are precisely the ultrafilters.

Proof: Every ultrafilter is clearly maximal in $\mathcal{M}$. If $\mathcal{U}$ is maximal in $\mathcal{M}$, then it is clearly proper and upper closed, and we can reason as in the proof of the ultrafilter lemma to show that it is actually an ultrafilter. $\Box$

Proof of Theorem 3: Suppose $x_n$ does not converge to $x$ in the classical sense. Fix $\varepsilon_0 > 0$ such that the set $S = \{n \geq 0 \mid |x_n-x| \geq \varepsilon_0\}$ is infinite. Then the family $\mathcal{V} = \{S \setminus \{n\} \mid n \geq 0\}$ has the finite intersection property: an ultrafilter $\mathcal{U}$ that extends $\mathcal{V}$ must be free. Then $S \in \mathcal{U}$, and $x_n$ does not have an ultralimit along $\mathcal{U}$.

The converse implication follows from the classical definition of limit, together with the very notion of free ultrafilter. $\Box$

Theorem 3 does hold for sequences of real numbers, but does not extend to arbitrary metric spaces. In fact, the following holds, which we state without proving.

Theorem 4. Let $X$ be a metric space. The following are equivalent.

1. For some free ultrafilter $\mathcal{U}$ on $\mathbb{N}$, every sequence in $X$ has an ultralimit along $\mathcal{U}$.
2. For every free ultrafilter $\mathcal{U}$ on $\mathbb{N}$, every sequence in $X$ has an ultralimit along $\mathcal{U}$.
3. $X$ is compact.

Ultrafilters are useful in many other contexts. For instance, they are used to construct hyperreal numbers, which in turn allow a rigorous definition of infinitesimals and the foundation of calculus over those. But this might be the topic for another Theory Lunch talk.