Ultrafilters

Ultrafilters won't make american coffee better, but they have nice applications in mathematics. In fact, the last three (working) days, I happened to hear about them with three different colleagues, in three different directions.

Let me recall that an ultrafilter $\cal U$ on a set $X$ is a subset of $\mathfrak P(X)$ satisfying the following axioms:

1. The empty set does not belong to $\cal U$;
2. If $A\in\cal U$ and $B\supset A$, then $B\in\cal U$;
3. If $A,B\in \cal U$, then $A\cap B\in\cal U$;
4. For any subset $A\subset X$, either $A$ or $\complement A$ belongs to $\cal U$ (but not both).

In informal terms, an element of $\cal U$ may be thought of as a “large” subset of $X$; the axioms say 1. that the empty set is not large, 2. that a superset of a large set is again large, 3. that large sets are large enough so that intersections of two large sets is large, and finally, 4. that if a set is not large, then its complement is large. In fact, this last axiom is the one which makes a filter “ultra”.

Here is an example of an ultrafilter. Fix a point $x\in X$ and decree that a set $A\subset X$ is large iff it contains $x$. Such ultrafilters are called principal and they do not quite respect the intuition of elements of an ultrafilter being a large set. Unfortunately, there is no explicit construction of an ultrafilter which is not principal. Fortunately, choice-like axioms imply the existence of non principal ultrafilters.

Ultrafilters are used to construct ultraproducts. 

Take a family $(A_x)$ of  non-empty sets indexed by the set $X$ and fix a nonprincipal ultrafilter on $X$. (The definition below is not the correct one when some sets $A_x$ may be empty; the correct one is slightly more elaborate. I learnt it from Laurent Moret-Bailly, see Section 2 of his beautiful paper An extension of Greenberg's theorem to general valuation rings, arXiv:1106.0984v3.) Define an equivalence relation on the product set $A=\prod A_x$ by saying that two families $(a_x)$ and $(b_x)$ are equivalent iff the set of $x$ such that $a_x=b_x$ is large. Let $A^*$ be the quotient of $A$ by this equivalence relation; it is called the ultraproduct of the $A_x$. When the $A_x$ have some extra-structure (relations, operations, etc.) on can transport them to the ultraproduct $A^*$. For example, if, for each $x$, $R_x$ is a binary relation on $A_x$, $a,b\in A^*$ are classes of $(a_x)$ and $(b_x)$, say that $R(a,b)$ iff the set of $x$ such that $R_x(a_x,b_x)$ is large. We shall see some specific examples below.

There are many nice bits of mathematics where ultrafilters are involved. Here are three of them which I would like not to forget.

1) Cardinality of ultraproducts of countable sets.

If there is a large subset of $X$ on which $\mathrm{Card}(A_x)$ is bounded, then $A^*$ is finite. Otherwise, $A^*$ is infinite, and has in fact at least the power of the continuum.

Here is a classical proof in the case $X=\mathbf N$, with some twists that helped me understand it.

We want to construct a map from $2^{\mathbf N}$ to $A^*$. Here, $2^{\mathbf N}$ is the set of subsets of $\mathbf N$,  but can be almost viewed as the set of $2$-adic integers, a subset of $\mathbf N$ corresponding to a $2$-adic integer whose nonzero digits are exactly those belonging to the given subset. In formula, $S\subset\mathbf N$ corresponds to the $2$-adic integer $f(S)=\sum_{n=0}^\infty \chi_S(n) 2^n$. If we sum only $n$ terms, we get an approximation $f_n(S)$ modulo $(2^n)$ which is an element of $\{0,\dots,2^n-1\}$. In particular, $f_n(S)\rightarrow f(S)$. This shows that if $S\neq T$ are two distincts subsets of $B$, then $f_n(S)\neq f_n(T)$ for all but finitely many integers~$n$.

Enumerate a large subset $X_1=\{x_0,\dots\} $ of $X$ such that $A_{x_n}$ has at least $2^n$ elements and enumerate those elements. For any $S\in 2^{\mathbf N}$, consider the family $a(S)=(a_x)$ of $\prod A_x$ such that for every $n$, $a_{x_n}$ is the $f_n(S)$th element of $A_{x_n}$, and $a_x$ is any fixed element of $A_x$ otherwise. Let $a^*(S)$ be the class of this family in $A^*$. If $S\neq T$, then $f_S(n)\neq f_T(n)$ for all but finitely many $n$, so that $a(S)$ and $a(T)$ differ in a large set (the complement to a finite set in a large set), hence $a^*(S)\neq a^*(T)$. We have thus constructed an injective map from $2^{\mathbf N}$ to $A^*$, hence $\mathrm{Card}(A^*)\geq 2^{\mathbf N}$.

2) An “ultrafilter proof” of the infinite Ramsey theorem

Any infinite graph contains an infinite subset which is either a complete subgraph (any two vertices are linked by an edge) or a discrete subgraph (no two vertices are linked by an edge). In this statement, a graph is assumed to have no loop.

Let $V$ be the set of vertices of your graph $G$. Choose a non principal ultrafilter on $V$. Say a vertex $v\in V$ is social if the set of its neighbors (those linked to $v$ by an edge of $G$) is large; otherwise, say it is lonely. Now, assuming that the set of social vertices is large, we will construct an infinite complete subgraph of $G$. Otherwise, the set of lonely vertices is large and the same construction (or the consideration of the opposite graph) gives an infinite discrete subgraph.

Fix a social vertex $v_0$. The set of social neighbors of $v_0$ is large, because it is the intersection of the large set of social vertices with the large set of neighbors of $v_0$; so $v_0$ has a social neighbor $v_1$. Assume we have constructed social vertices $v_0,\dots,v_{n-1}$ which are pairwise linked by an edge, the set of social vertices of $V$ which are linked to all of the $v_i$ is large, again because it is the intersection of the large set of social vertices with finitely many large sets of neighbors of each $v_i$. So there is a social vertex $v_n$ which is a neighbor of $v_0,\dots,v_{n-1}$. Go on.

This infinite Ramsey theorem implies the finite one: For any integer $n$, there is an integer $r(n)$ such that  each graph with at least $r(n)$ vertices possesses a subgraph of cardinality $n$ which is either complete or discrete. The proof uses ultrafilters again, but in a different way. Assume by contradiction that the finite Ramsey theorem is false. So there is an integer $n$ and a family $(G_i)$ of finite graphs with an increasing number of vertices, none of which contains a complete or discrete subgraph with $n$ vertices. Take the ultraproduct $G$ of the graphs $G_i$, namely the product graph $\prod G_i$ modulo the equivalence relation $(g_i)\sim (g'_i)$ iff the set of $i$ such that $g_i=g'_i$
is large, for some given non principal ultraproduct on the set $I$ of indices. Write $[g_i]$ for the class of a family $(g_i)$; say that $[g_i]$ is linked to $[g'_i]$ if the set of indices $i$ for which $g_i$ is linked to $g'_i$ in $G_i$ is large. Then $G$ is a graph, an infinite graph (by the result on cardinalities of ultraproducts).

While I write this proof, I realize that this proof prompts naturally the question of the Ramsey theorem for cardinals: Assuming $V$ has some (infinite) cardinality, what is the smallest cardinality for which
there may not exist an either complete or discret subgraph of that cardinality? For the previous proof to work, one needs transfinite induction, so one needs the ultrafilter to be stable by possibly infinite intersections.

3) Ax's proof of Hilbert's Nullstellensatz

Let $k$ be an algebraically closed field, let $f_1,\dots,f_m$ be polynomials in $d$ variables with coefficients in $k$. Assume that the system of polynomial equations
\[ f_1(x_1,\dots,x_d)=\dots=f_m(x_1,\dots,x_d)=0 \]
has a solution in some extension $K$ of $k$. Then, it already has a solution in $k$.

The following proof is given by Ax in the surprising paper A Metamathematical Approach to some Problems in Number Theory, published in the proceedings of a conference  (Proc. Symp. Pure Math., 20, Amer. Math. Soc). I say surprising, because the main part of this 30-pages paper is about 6 pages, the rest is an appendix providing a beautiful introduction the theory of valuations!

I basically copy Ax. One may assume that both fields $k$ and $K$ are countable and algebraically closed (first replace $k$ by the algebraic closure of the subfield generated by the coefficients

of the polynomials $f_1,\dots,f_m$; then replace $K$ by the algebraic closure of the subfield generated over $k$ by the coordinates $(x_1,\dots,x_d)$ of some solution). 

Consider a nonprincipal ultrafilter on the set $\mathbf N$ of integers and look at the ultraproducts $k^*$ and $K^*$ of the families $(k_n)$ and $(K_n)$, where $k_n=k$ and $K_n=K$ for each $K$. These are algebraically closed fields; moreover,  $k^*$ contains $k$ (the set of classes of all families $(a_n)$ where $a_n\equiv a$ for  some $a\in k$). From a solution $(x_1,\dots,x_d)$ in $K$ and considering the class of the constant family, one gets a solution $(x^*_1,\dots,x^*_d)$ in $(K^*)^d$ of the system of equations $f_1(x^*)=\dots=f_m(x^*)=0$.

By set theory, $\mathrm{Card}(k^*)\leq {\mathbf N}^{\mathbf N}=2^{\mathbf N}$, while we have shown that $\mathrm{Card}(k^*)\geq 2^{\mathbf N}$, so that $k^*$ has the cardinality of the continuum. Likewise, $K^*$ has the cardinality of the continuum. Consequently (by set theory again),  $k^*$ and $K^*$ both have a transcendence basis over $k$ of cardinality the continuum; since they are algebraically closed, they are isomorphic as extensions of $k$. The image of the solution $x^*$ by a $k$-isomorphism from $K^*$ to $k^*$ is a solution $y^*$ of our system in $k^*$. By definition, $y^*=(y^*_1,\dots,y^*_d)$ where for each $i$, $y^*_i$ is the class of a sequence $(y_{i,n})$ of elements of $k$. Since $f_j(y^*)=0$, the set of integers $n$ such that $f_j(y_{1,n},\dots,y_{d,n})=0$ is large. Consequently, there is a large set of integers $n$ such that $(y_{1,n},\dots,y_{d,n})$ is a solution of our system. Any such integer $n$ is a proof that this system already has a solution in $k$. Q.E.D.

I do no know whether this proof is really easier than the ones usually given in an algebra course, for all the set theory involved is rather delicate, but I found it rather appealing.