580 -Partition calculus (3)

April 6, 2009

 

1. Infinitary Jónsson algebras

 

Once again, assume choice throughout. Last lecture, we showed that {\kappa\not\rightarrow(\kappa)^{\aleph_0}} for any {\kappa.} The results below strengthen this fact in several ways.

Definition 1 Let {x} be a set. A function {f:[x]^{\aleph_0}\rightarrow x} is {\omega}-Jónsson for {x} iff for all {y\subseteq x,} if {|y|=|x|,} then {f''[y]^{\aleph_0}=x.}

 

Actually, for {x=\lambda} a cardinal, the examples to follow usually satisfy the stronger requirement that {f''[y]^\omega=\lambda.} In the notation from Definition 16 from last lecture, {\lambda\not\rightarrow[\lambda]^\omega_\lambda.}

The following result was originally proved in 1966 with a significantly more elaborate argument. The proof below, from 1976, is due to Galvin and Prikry.

Theorem 2 (Erdös-Hajnal) For any infinite {x,} there is an {\omega}-Jónsson function for {x.}

 

Read the rest of this entry »

Advertisements

580 -Cardinal arithmetic (10)

March 9, 2009

Let me begin with a couple of comments that may help clarify some of the results from last lecture.

First, I want to show a different proof of Lemma 21.2, that I think is cleaner than the argument I gave before. (The argument from last lecture, however, will be useful below, in the proof of Kunen’s theorem.)

Lemma 1 If {\kappa} is measurable, {{\mathcal U}} is a {\kappa}-complete nonprincipal ultrafilter over {\kappa,} and {j_{\mathcal U}:V\rightarrow M} is the corresponding ultrapower embedding, then {{}^\kappa M\subset M.}

 

Proof: Recall that if {\pi} is Mostowski’s collapsing function and {[\cdot]} denotes classes in {V^\kappa/{\mathcal U},} then {M=\{\pi([f]):f\in{}^\kappa V\}.} To ease notation, write {\langle f\rangle} for {\pi([f]).}

Let {h:\kappa\rightarrow M.} Pick {f:\kappa\rightarrow V} such that for all {\alpha<\kappa,} {h(\alpha)=\langle f(\alpha)\rangle.}

Lemma 2 With notation as above, {\langle f\rangle=j_{\mathcal U}(f)(\langle{\rm id}\rangle)} for any {f:\kappa\rightarrow V.}

 

Proof: For a set {X} let {c_X:\kappa\rightarrow V} denote the function constantly equal to {X.} Since {\pi} is an isomorphism, {\mbox{\L o\'s}}‘s lemma gives us that the required equality holds iff

\displaystyle \{\alpha<\kappa : f(\alpha)=((c_f)(\alpha))({\rm id}(\alpha))\}\in{\mathcal U},

but this last set is just {\{\alpha<\kappa:f(\alpha)=f(\alpha)\}=\kappa.} \Box

From the nice representation just showed, we conclude that {\langle f(\alpha)\rangle=j_{\mathcal U}(f(\alpha))(\langle{\rm id}\rangle)} for all {\alpha<\kappa.} But for any such {\alpha,} {j_{\mathcal U}(f(\alpha))=j_{\mathcal U}(f)(\alpha)} because {{\rm cp}(j_{\mathcal U})=\kappa} by Lemma 21 from last lecture. Hence, {h=(j_{\mathcal U}(f)(\alpha)(\langle{\rm id}\rangle):\alpha<\kappa),} which is obviously in {M,} being definable from {j_{\mathcal U}(f),} {\langle{\rm id}\rangle,} and {\kappa.} \Box

The following was shown in the proof of Lemma 20, but it deserves to be isolated.

Lemma 3 If {{\mathcal U}} is a normal nonprincipal {\kappa}-complete ultrafilter over the measurable cardinal {\kappa,} then {{\mathcal U}=\{X\subseteq\kappa:\kappa\in i_{\mathcal U}(X)\},} i.e., we get back {{\mathcal U}} when we compute the normal measure derived from the embedding induced by {{\mathcal U}.} {\Box}

 

Finally, the construction in Lemma 10 and preceeding remarks is a particular case of a much more general result.

Definition 4 Given {f:I\rightarrow J} and an ultrafilter {{\mathcal D}} over {I,} the projection {f_*({\mathcal D})} of {{\mathcal D}} over {J} is the set of {X\subseteq J} such that {f^{-1}(X)\in{\mathcal D}.}

 

Clearly, {f_*({\mathcal D})} is an ultrafilter over {J.}

Notice that if {\kappa={\rm add}({\mathcal D}),} {(X_\alpha:\alpha<\kappa)} is a partition of {I} into sets not in {{\mathcal D},} and {f:I\rightarrow\kappa} is given by {f(x)=} the unique {\alpha} such that {x\in X_\alpha,} then {f_*({\mathcal D})} is a {\kappa}-complete nonprincipal ultrafilter over {\kappa.} (Of course, {\kappa=\omega} is possible.)

For a different example, let {{\mathcal U}} be a {\kappa}-complete nonprincipal ultrafilter over the measurable cardinal {\kappa,} and let {f:\kappa\rightarrow\kappa} represent the identity in the ultrapower by {{\mathcal U},} {\langle f\rangle=\kappa.} Then {f_*({\mathcal U})} is the normal ultrafilter over {\kappa} derived from the embedding induced by {{\mathcal U}.}

Definition 5 Given ultrafilters {{\mathcal U}} and {{\mathcal V}} (not necessarily over the same set), say that {{\mathcal U}} is Rudin-Keisler below {{\mathcal V},} in symbols, {{\mathcal U}\le_{RK}{\mathcal V},} iff there are sets {S\in{\mathcal U},} {T\in{\mathcal V},} and a function {f:T\rightarrow S} such that {{\mathcal U}\upharpoonright S=f_*({\mathcal V}\upharpoonright T).}

 

Theorem 6 Let {{\mathcal U}} be an ultrafilter over a set {X} and {{\mathcal V}} an ultrafilter over a set {Y.} Suppose that {{\mathcal U}\le_{RK}{\mathcal V}.} Then there is an elementary embedding {j:V^X/{\mathcal U}\rightarrow V^Y/{\mathcal V}} such that {j\circ i_{\mathcal U}=i_{\mathcal V}.}

 

Proof: Fix {T\in{\mathcal U}} and {S\in{\mathcal V}} for which there is a map {f:S\rightarrow T} such that {{\mathcal U}\upharpoonright T=f_*({\mathcal V}\upharpoonright S).} Clearly, {V^X/{\mathcal U}\cong V^T/({\mathcal U}\upharpoonright T)} as witnessed by the map {[f]_{\mathcal U}\mapsto[f\upharpoonright T]_{{\mathcal U}\upharpoonright T},} and similarly {V^Y/{\mathcal V}\cong V^S/({\mathcal V}\upharpoonright S),} so it suffices to assume that {S=Y} and {T=X.}

Given {h:X\rightarrow V,} let {h_*:Y\rightarrow V} be given by {h_*=h\circ f.} Then {j([h]_{\mathcal U})=[h_*]_{\mathcal V}} is well-defined, elementary, and {j\circ i_{\mathcal U}=i_{\mathcal V}.}

In effect, {h=_{\mathcal U}h'} iff {\{x\in X:h(x)=h'(x)\}\in{\mathcal U}} iff {\{y\in Y:h\circ f(y)=h'\circ f(y)\}\in{\mathcal V}} iff {h_*=_{\mathcal V}h'_*,} where the second equivalence holds by assumption, and it follows that {j} is well-defined.

If {c_B^A} denotes the function with domain {A} and constantly equal to {B,} then for any {x,} {j\circ i_{\mathcal U}(x)=j([c^X_x]_{\mathcal U})=[(c^X_x)_*]_{\mathcal V}=[c^Y_x]_{\mathcal V}=i_{\mathcal V}(x)} since {(c^X_x)_*=c^Y_x} by definition of the map {h\mapsto h_*.} This shows that {j\circ i_{\mathcal U}=i_{\mathcal V}.}

Elementarity is a straightforward modification of the proof of Lemma 10 from last lecture. \Box

One can show that Theorem 6 “very nearly” characterizes the Rudin-Keisler ordering, see for example Proposition 0.3.2 in Jussi Ketonen, Strong compactness and other cardinal sins, Annals of Mathematical Logic 5 (1972), 47–76.

Read the rest of this entry »