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.

I am not sure which statement you heard as the "Ultimate $L$ axiom," but I will assume it is the following version: There is a proper class of Woodin cardinals, and for all sentences $\varphi$ that hold in $V$, there is a universally Baire set $A\subseteq{\mathbb R}$ such that, letting $\theta=\Theta^{L(A,{\mathbb R})}$, we have that $HOD^{L(A,{\ma […]

A Wadge initial segment (of $\mathcal P(\mathbb R)$) is a subset $\Gamma$ of $\mathcal P(\mathbb R)$ such that whenever $A\in\Gamma$ and $B\le_W A$, where $\le_W$ denotes Wadge reducibility, then $B\in\Gamma$. Note that if $\Gamma\subseteq\mathcal P(\mathbb R)$ and $L(\Gamma,\mathbb R)\models \Gamma=\mathcal P(\mathbb R)$, then $\Gamma$ is a Wadge initial se […]

Craig: For a while, there was some research on improving bounds on the number of variables or degree of unsolvable Diophantine equations. Unfortunately, I never got around to cataloging the known results in any systematic way, so all I can offer is some pointers to relevant references, but I am not sure of what the current records are. Perhaps the first pape […]

Yes. Consider, for instance, Conway's base 13 function $c$, or any function that is everywhere discontinuous and has range $\mathbb R$ in every interval. Pick continuous bijections $f_n:\mathbb R\to(-1/n,1/n)$ for $n\in\mathbb N^+$. Pick a strictly decreasing sequence $(x_n)_{n\ge1}$ converging to $0$. Define $f$ by setting $f(x)=0$ if $x=0$ or $\pm x_n […]

(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 […]

I feel this question may be a duplicate, because I am pretty certain I first saw the paper I mention below in an answer here. You may be interested in reading the following: MR2141502 (2006c:68092) Reviewed. Calude, Cristian S.(NZ-AUCK-C); Jürgensen, Helmut(3-WON-C). Is complexity a source of incompleteness? (English summary), Adv. in Appl. Math. 35 (2005), […]

The smallest such ordinal is $0$ because you defined your rank (height) inappropriately (only successor ordinals are possible). You want to define the rank of a node without successors as $0$, and of a node $a$ with successors as the supremum of the set $\{\alpha+1\mid\alpha$ is the rank of an immediate successor of $a\}$. With this modification, the smalles […]

The perfect reference for this is MR2562557 (2010j:03061) Reviewed. Steel, J. R.(1-CA). The derived model theorem. In Logic Colloquium 2006. Proceedings of Annual European Conference on Logic of the Association for Symbolic Logic held at the Radboud University, Nijmegen, July 27–August 2, 2006, S. B. Cooper, H. Geuvers, A. Pillay and J. Väänänen, eds., Lectu […]

Consider $A=\{(x,y)\in\mathbb R^2\mid x\notin L[y]\}$. Check that this set is $\Pi^1_2$ (this is similar to the proof that there is a $\Delta^1_2$ well-ordering in $L$). The point is that $A$ does not admit a projective uniformization. It does not really matter that the number of Cohen reals you added is $\aleph_2$; any uncountable number would work. The rea […]