Thursday, October 18, 2012

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.)

No comments :

Post a Comment