Cardinality of ultraproducts (an update)

I thought a little more about the proof that an ultraproduct of finite sets is either finite (if the family of cardinals is bounded with respect to the chosen ultrafilter) or has the power of the continuum. I believe that I can now state things in a neater, albeit longer, way.

Let me recall the notation:  $(A_x)$ be a family of sets indexed by a set $X$, $A=\prod A_x$ is the product of the sets $A_x$, $\cal U$ be a nonprincipal ultrafilter on a set $X$, and $A^*$ is the ultraproduct of the $A_x$ with respect to $\cal U$.

I then recall the notion of convergence with respect to the ultrafilter $\cal U$. Let $V$ be a topological space and let  $(v_x)$ be a family of points of $V$.

1. Say $(v_x)$ $\cal U$-converges to $v$ if for any neighborhood $W$ of $v$, the set of $x\in X$ such that $v_x\in W$ belongs to $\cal U$. 
2. If $V$ is Hausdorff, then $(v_x)$ has at most one limit. In particular, if $(w_x)$ is another family of points of $V$ indexed by $X$ which converges to a point $w\neq v$, the set of $x\in X$ such that $v_x\neq w_x$ belongs to $\cal U$.
3. Moreover, if $V$ is compact, then any family $(v_x)$ has a $\cal U$-limit in $V$. This is essentially the definition of compactness in terms of ultrafilters, but it does no harm recalling the proof. If, by contradiction, $(v_x)$ has no $\cal U$-limit, any point $v\in V$ has a neighborhood $W_v$ such that the set $X_v$ $x\in X$ with $x\not\in W_v$ belongs to $\cal U$. Since $V$ is compact, there exists a finite set $T$ in $V$ such that the $W_v$, for $v\in T$, cover $V$. This implies that the intersection of the $X_v$, for $v\in T$, is empty. However, this is a finite intersection of elements of $\cal U$, hence belongs to $\cal U$, hence is non-empty.

Last reminding. The set of nonnegative integers $\mathbf N$ is dense in the Hausdorff and compact set $\mathbf Z_2$ of $2$-adic integers endowed with the $2$-adic distance.

For every $x\in X$, choose a surjection $f_x$ from $A_x$ to the interval of integers $[0,\mathrm{Card}(A_x))$, viewed as a subset of $\mathbf Z_2$. For any family $a=(a_x)$ where $a_x\in A_x$ for every $x\in X$, the family $(f_x(a_x))$ has a unique $\cal U$-limit in $\mathbf Z_2$, denoted $f(a)$. This defines a map $f\colon A\to \mathbf Z_2$.

Let $a=(a_x)$ and $b=(b_x)$ be two such families and assume that $f(a)\neq f(b)$. It follows from the fact that $\mathbf Z_2$ is Hausdorff that the set of $x\in X$ such that $a_x\neq b_x$ belongs to $\cal U$. Said the other way round, if $a$ and $b$ are $\cal U$-equivalent, then $f(a)=f(b)$, so that $f$ defines a map $f^*\colon A^*\to\mathbf Z_2$.

We now show that if the cardinalities $\mathrm{Card}(A_x)$ are not bounded (with respect to $\cal U$), this map $f^*$ is surjective. Let $v\in\mathbf Z_2$; for any $x\in X$, let $v_x$ be the integer in $[0,\mathrm{Card}(A_x))$ which is the closest to $v$ with respect to the $2$-adic distance and let $a_x\in A_x$ be such that $f_x(a_x)=v_x$. I claim that $d(v,v_x)$ $\cal U$-converges to $0$; indeed, for any $k$, the set $X_k$  of $x\in X$ such that $\mathrm{Card}(A_x)\geq 2^k$ belongs to $\cal U$ (this is what it means to be unbounded with respect to $\cal U$) and for  $x\in X_k$, $d(v,v_x)\leq 2^{-k}$.  By construction, $(f_x(a_x))=(v_x)$, hence $f((a_x))=v$; if $a^*$ is the class in $A^*$ of the family $(a_x)$, we thus have $f^*(a^*)=v$.

Finally, $\mathrm{Card}(A^*) \geq \mathrm{Card}(\mathbf Z_2)=2^{\mathbf N}$, as was to be shown.

(This proof is longer, but only because I needed to recall—I mean, to recall to myself—the topological apparatus of convergence for ultrafilters.)

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.

Birth of a new blog

It may have been like when you take care of a friend's pet for a week-end: you get used to it and eventually want to have your own. I had run a familial blog for one year, when we all left Rennes to Princeton, but we went back home, and left Rennes again to Paris. So this old blog I cherish couldn't really host the sequel of our adventures. I am not sure I am willing to discuss that kind of adventures publicly neither. It's okay to chat about your life when your 6000km away, but it's slightly more problematic when you live next to the one you would chat about.

So I needed fresh ideas, for a fresh blog, and today, here it is !

So what will this blog be about ?

Sorry for some of you, primarily math.

But I will probably use it to store some computer tricks (the kind of recipes you don't want
to forget but have no convenient place to keep in).

And I'll certainly talk about music too. In fact, finding a title for this blog has been a sad experience.
The first three names I tried were already used, namely Garden of Eden, Lost in a Dream and Mumbo Jumbo. These are three beautiful songs of the revered drummer Paul Motian — a musical poet among all. The New York Times said of him he was a “composer of grace and abstraction”. The fourth try has been taken from a Eddie Harris song I know from a duet by Motian and Enrico Pieranunzi, Freedom Jazz Dance; it lead to the actual title of this new blog.

I hope this title convey the kind of things I want to discuss here, the way I expect to discuss it: freely, as a math dance.

In fact, and this was not intended, this title reminds me of the envoi of a beautiful collective small book on transcendental number theory : et que commence la transe en danse !