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.

Advertisement

This entry was posted on Friday, October 2nd, 2009 at 1:37 pm and is filed under 502: Logic and set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

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

Gravatar
WordPress.com Logo

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

Facebook photo

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

Cancel

Connecting to %s

%d bloggers like this: