502 – Ultraproducts of finite sets

I want to sketch here the proof that if {(M_n\mid n\in{\mathbb N})} is a sequence of finite nonempty sets, and {\lim_n |M_n|=\infty,} then {\prod_nM_n/{\mathcal U}} has size {|{\mathbb R}|} for any nonprincipal ultrafilter {{\mathcal U}} on {{\mathbb N}.}

The argument I present is due to Frayne, Morel, Scott, Reduced direct products, Fundamenta Mathematica, 51 (1962), 195–228.

The topic of the size of ultraproducts is very delicate and some open questions remain. For ultraproducts of finite structures, this is continued in Keisler, Ultraproducts of finite sets, The Journal of Symbolic Logic, 32 (1967), 47–57, and finally in Shelah, On the cardinality of ultraproduct of finite sets, The Journal of Symbolic Logic, 35 (1) (Mar., 1970), 83–84. Shelah shows that if an ultraproduct of finite sets is infinite, say of size {\kappa,} then {\kappa^{\aleph_0}=\kappa.} His argument is a very nice application of non-standard analysis. The case that interests us is easier.

Clearly,

\displaystyle |\prod_nM_n/{\mathcal U}|\le|\prod_n M_n|\le|{\mathbb N}^{\mathbb N}|=|{\mathbb R}|,

so it suffices to show that {|{\mathbb R}|\le|\prod_nM_n/{\mathcal U}|.}

We need the following combinatorial lemma:

Lemma 1 There is a family {{\mathcal F}} of functions {f:{\mathbb N}\rightarrow{\mathbb N}} such that: 

 

  1. {|{\mathcal F}|=|{\mathbb R}|,}
  2. For any {f\in{\mathcal F}} and any {n\in{\mathbb N},} {f(n)<2^n,} and
  3. If {f\ne g} are in {{\mathcal F},} then {\{n\mid f(n)=g(n)\}} is finite.

 

Proof: For each {A\subseteq{\mathbb N}} let {f_A:{\mathbb N}\rightarrow{\mathbb N}} be given by

\displaystyle  f_A(n)=\sum_{k<n}\chi_A(k)2^k,

where {\chi_A} is the characteristic function of {A,} i.e., {\chi_A(k)=1} if {k\in A} and else {\chi_A(k)=0.}

Then {{\mathcal F}=\{f_A\mid A\subseteq{\mathbb N}\}} is as needed. \Box

Let {A_n=\{k\in{\mathbb N}\mid 2^n\le |M_k|<2^{n+1}\},} so the sets {A_n} are all finite and partition {{\mathbb N}.} For each {k\in A_n} let {\{a_{k,j}\mid j<2^n\}} be a list of {2^n} distinct elements of {M_k.}

Let {{\mathcal F}} be as in the lemma. For {f\in{\mathcal F},} let {h_f:{\mathbb N}\rightarrow\bigcup_k M_k} be given by

\displaystyle  h_f(k)=a_{k,f(n)},

where {n} is such that {k\in A_n.}

Note that if {f\ne g} are in {{\mathcal F},} then

\displaystyle \{k\in{\mathbb N}\mid h_f(k)=h_g(k)\}=\bigcup\{ A_n\mid n\in{\mathbb N},f(n)=g(n)\}

is a finite union of finite sets and therefore finite. Hence, {[h_f]_{\mathcal U}\ne[h_g]_{\mathcal U},} and we are done.

Typeset using LaTeX2WP.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: