## 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.}$

## 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.