I want to sketch here the proof that if is a sequence of finite nonempty sets, and then has size for any nonprincipal ultrafilter on

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 then His argument is a very nice application of non-standard analysis. The case that interests us is easier.

Clearly,

so it suffices to show that

We need the following combinatorial lemma:

Lemma 1There is a family of functions such that:

For any and any and

If are in then is finite.

Proof: For each let be given by

where is the characteristic function of i.e., if and else

Then is as needed.

Let so the sets are all finite and partition For each let be a list of distinct elements of

Let be as in the lemma. For let be given by

where is such that

Note that if are in then

is a finite union of finite sets and therefore finite. Hence, and we are done.

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.