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.

Typeset using LaTeX2WP.

43.614000-116.202000

Advertisements

Like this:

LikeLoading...

Related

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.

(1) Patrick Dehornoy gave a nice talk at the Séminaire Bourbaki explaining Hugh Woodin's approach. It omits many technical details, so you may want to look at it before looking again at the Notices papers. I think looking at those slides and then at the Notices articles gives a reasonable picture of what the approach is and what kind of problems remain […]

The description below comes from József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (2009g:91038). Given a finite set $S$ of points in the plane $\mathbb R^2$, consider the following game between two players Maker and Breaker. The players alternat […]

Yes. This is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem, and some standard number theory. A number of papers have details of the $\Pi^0_1$ sentence. To begin with, take a look at the relevant paper in Mathematical developments arising from Hilbert's problems (Proc. Sympos. Pure Math., Northern Illinois Un […]

I am looking for references discussing two inequalities that come up in the study of the dynamics of Newton's method on real-valued polynomials (in one variable). The inequalities are fairly different, but it seems to make sense to ask about both of them in the same post. Most of the details below are fairly elementary, they are mostly included for comp […]

Let $C$ be the standard Cantor middle-third set. As a consequence of the Baire category theorem, there are numbers $r$ such that $C+r$ consists solely of irrational numbers, see here. What would be an explicit example of a number $r$ with this property? Short of an explicit example, are there any references addressing this question? A natural approach would […]

First of all, $f(z)+e^z\ne 0$ by the first inequality. It follows that $e^z/(f(z)+e^z)$ is entire, and bounded above. You should be able to conclude from that.

Yes. The standard way of defining these sequences goes by assigning in an explicit fashion to each limit ordinal $\alpha$, for as long as possible, an increasing sequence $\alpha_n$ that converges to $\alpha$. Once this is done, we can define $f_\alpha$ by diagonalizing, so $f_\alpha(n)=f_{\alpha_n}(n)$ for all $n$. Of course there are many possible choices […]

I disagree with the advice of sending a paper to a journal before searching the relevant literature. It is almost guaranteed that a paper on the fundamental theorem of algebra (a very classical and well-studied topic) will be rejected if you do not include mention on previous proofs, and comparisons, explaining how your proof differs from them, etc. It is no […]

No, the rank of a set $x$ is the least $\alpha$ such that $x\in V_{\alpha+1}$. Note that if $\alpha$ is limit, any $x\in V_\alpha$ belongs to some $V_\beta$ with $\beta