## 580 -Partition calculus (5)

1. Larger cardinalities

We have seen that ${\omega\rightarrow(\omega)^n_m}$ (Ramsey) and ${\omega\rightarrow[\omega]^n_\omega}$ (${\mbox{Erd\H os}}$-Rado) for any ${n,m<\omega.}$ On the other hand, we also have that ${2^\kappa\not\rightarrow(3)^2_\kappa}$ (${\mbox{Sierpi\'nski}}$) and ${2^\kappa\not\rightarrow(\kappa^+)^2}$ (${\mbox{Erd\H os}}$-Kakutani) for any infinite ${\kappa.}$

Positive results can be obtained for larger cardinals than ${\omega}$ if we relax the requirements in some of the colors. A different extension, the ${\mbox{Erd\H os}}$-Rado theorem, will be discussed later.

Theorem 1 (${\mbox{Erd\H os}}$-Dushnik-Miller) For all infinite cardinals ${\lambda,}$ ${\lambda\rightarrow(\lambda,\omega)^2.}$

This was originally shown by Dushnik and Miller in 1941 for ${\lambda}$ regular, with ${\mbox{Erd\H os}}$ providing the singular case. For ${\lambda}$ regular one can in fact show something stronger:

Theorem 2 (${\mbox{Erd\H os}}$-Rado) Suppose ${\kappa}$ is regular and uncountable. Then
$\displaystyle \kappa\rightarrow_{top}(\mbox{Stationary},\omega+1)^2,$ which means: If ${f:[\kappa]^2\rightarrow2}$ then either there is a stationary ${H\subseteq\kappa}$ that is ${0}$-homogeneous for ${f}$, or else there is a closed subset of ${\kappa}$ of order type ${\omega+1}$ that is ${1}$-homogeneous for ${f}$.

(Above, top stands for “topological.”)

Proof: Assume that for no set ${\vec\gamma=\{\gamma_n:n<\omega\}}$ with supremum ${\gamma<\kappa,}$ it is the case that ${\vec\gamma\cup\{\gamma\}}$ is ${1}$-homogeneous. For each ${\gamma\in S^\kappa_\omega}$ fix an increasing ${\omega}$-sequence ${(\delta^\gamma_n:n<\omega)}$ with limit ${\gamma,}$ and define ${n_\gamma<\omega}$ and a sequence ${(\epsilon^\gamma_m:m as follows:

• ${\gamma>\epsilon^\gamma_0\ge\delta^\gamma_0}$ and ${\{\epsilon^\gamma_0,\gamma\}}$ is 1-homogeneous.
• ${\gamma>\epsilon^\gamma_1>\epsilon^\gamma_0,}$ ${\epsilon^\gamma_1\ge\delta^\gamma_1,}$ and ${\{\epsilon^\gamma_0,\epsilon^\gamma_1,\gamma\} }$ is 1-homogeneous.
• In general, ${\gamma>\epsilon^\gamma_{k+1}>\epsilon^\gamma_k,}$ ${\epsilon^\gamma_{k+1}\ge\delta^\gamma_{k+1},}$ and$\displaystyle \{\epsilon^\gamma_0,\epsilon^\gamma_1,\dots,\epsilon^\gamma_{k+1},\gamma\}$
is 1-homogeneous.

• For each ${\gamma,}$ this is done for as long as we can. Notice that since ${\gamma>\epsilon^\gamma_k\ge\delta^\gamma_k,}$ if we can continue the construction for ${\omega}$ many steps, then we obtain a set ${\vec\gamma}$ of order type ${\omega,}$ with supremum ${\gamma,}$ such that ${\vec\gamma\cup\{\gamma\}}$ is 1-homogeneous, contradiction. It follows that the construction must stop at some finite stage. Let ${n_\gamma}$ be the length of the sequence of ${\epsilon^\gamma_m}$ so built, thus for any ${\epsilon\epsilon^\gamma_{n_\gamma-1},}$ ${\{\epsilon^\gamma_0,\dots, \epsilon^\gamma_{n_\gamma-1},\epsilon,\gamma\}}$ is not 1-homogeneous.

By repeated application of Fodor’s lemma, find ${S\subseteq S^\kappa_\omega}$ stationary, ${n<\omega}$ and ordinals ${\delta_0<\dots<\delta_n<\min(S)}$ and ${\epsilon_0<\dots<\epsilon_{n-1}}$ such that for all ${\gamma\in S,}$ ${\gamma}$ is limit, ${n_\gamma=n,}$ ${\delta^\gamma_m=\delta_m}$ for ${m\le n}$ and ${\epsilon^\gamma_m=\epsilon_m}$ for ${m

We claim that ${S}$ is 0-homogeneous: If ${\gamma_0<\gamma_1}$ are in ${S}$ then ${f''[\{\epsilon_i\colon i for ${j=0,1,}$ so if ${f(\gamma_0,\gamma_1)=1,}$ then ${\{\epsilon_i\colon i would be 1-homogeneous, and we could have defined ${\epsilon^{\gamma_1}_n}$ (for example, as ${\gamma_0}$), contradicting the definition of ${n_{\gamma_1}=n.}$ $\Box$

Since every stationary subset of ${\omega_1}$ contains closed subsets of order type ${\alpha+1}$ for all countable ordinals ${\alpha,}$ we immediately obtain:

Corollary 3 ${\omega_1\rightarrow_{top}(\alpha+1,\omega+1)^2}$ for any ${\alpha<\omega_1.}$ ${\Box}$

We will return to these matters later, when we discuss the Baumgartner-Hajnal theorem. Let us now present the proof of Theorem 1:

Proof: The argument in Theorem 2 gives a stronger result for ${\lambda}$ regular. Now assume that ${\lambda}$ is singular, let ${\kappa={\rm cf}(\lambda)}$ and let ${(\lambda_\xi\colon\xi<\kappa)}$ be an increasing sequence of regular cardinals cofinal in ${\lambda,}$ and such that ${\kappa<\lambda_0.}$ Fix a coloring ${f:[\kappa]^2\rightarrow2.}$

For ${\alpha\in\lambda}$ let
$\displaystyle B_\alpha=\{\beta\in\lambda\colon\alpha<\beta\mbox{ and }f(\alpha,\beta)=1\}.$

If for every ${X\in[\lambda]^\lambda}$ there is some ${\alpha\in X}$ such that ${|B_\alpha\cap X|=\lambda,}$ we can define a sequence ${(\alpha_n,X_n\colon n<\omega)}$ as follows: Let ${X_0=\lambda}$ and let ${\alpha_0\in X_0}$ be such that ${|B_{\alpha_0}\cap X_0|=\lambda.}$ Given ${\alpha_n}$ and ${X_n,}$ let ${X_{n+1}=B_{\alpha_n}\cap X_n}$ and let ${\alpha_{n+1}\in X_{n+1}}$ be such that ${|B_{\alpha_{n+1}}\cap X_{n+1}|=\lambda.}$ It follows that ${H=\{\alpha_n\colon n<\omega\}}$ is 1-homogeneous, and we are done.

We can then assume that there is some ${S\in[\lambda]^\lambda}$ such that for all ${\alpha\in S,}$ ${|B_\alpha\cap S|<\kappa.}$ Fix a partition ${(S_\xi\colon\xi<\kappa)}$ of ${S}$ into disjoint sets such that ${|S_\xi|=\lambda_\xi.}$ By regularity of ${\lambda_\xi,}$ either there is an infinite ${1}$-homogeneous subset of ${S_\xi}$ for some ${\xi<\kappa,}$ and again we are done, or else for each ${\xi<\kappa}$ we can find a 0-homogeneous set ${K_\xi\in[S_\xi]^{\lambda_\xi}.}$

Fix ${\xi<\kappa.}$ Since ${K_\xi\subset S,}$ for each ${\alpha\in K_\xi}$ there is some ${\beta<\kappa}$ such that ${|B_\alpha\cap S|\kappa,}$ it follows that there is some ${\gamma_\xi<\kappa}$ such that
$\displaystyle Z_\xi=\{\alpha\in K_\xi\colon |B_\alpha\cap S|<\lambda_{\gamma_\xi}\}$
has size ${\lambda_\xi.}$

We can now easily build an increasing sequence ${(\xi(\nu)\colon\nu<\kappa)}$ of ordinals below ${\kappa}$ such that ${\nu<\kappa}$ implies ${\sup_{\eta<\nu}\gamma_{\xi(\eta)}<\xi(\nu).}$ But then we can define
$\displaystyle H_\nu=Z_{\xi(\nu)}\setminus\bigcup\{B_\alpha\colon\alpha\in\bigcup_{\eta<\nu}Z_{\xi(\eta)}\},$
for each ${\nu<\kappa,}$ so ${|H_\nu|=\lambda_{\xi(\nu)}.}$ Note that ${H_\nu,}$ being a subset of ${K_{\xi(\nu)},}$ is 0-homogeneous. Finally, by definition of the ${H_\nu,}$
$\displaystyle H=\bigcup_\nu H_\nu$
has size ${\lambda}$ and is 0-homogeneous as well, completing the proof. $\Box$

Corollary 4 (${{\sf ZF}}$) Let ${X}$ be an infinite set and suppose that ${<_1}$ and ${<_2}$ are two well-orderings of ${X.}$ Then there is a ${Y\in[X]^{|X|}}$ such that ${<_1\upharpoonright Y^2=<_2\upharpoonright Y^2.}$

Proof: We may as well assume that ${X}$ is an initial ordinal ${\kappa.}$ Work in ${L[<_1,<_2].}$ This is a model of choice. By the ${\mbox{Erd\H os}}$-Dushnik-Miller theorem, either there is an infinite subset of ${\kappa}$ where ${<_1}$ and ${<_2}$ never coincide, or else there is a ${Y}$ as wanted. Since the first case is impossible because the ${<_i}$ are well-orderings, we are done. $\Box$

It is somewhat challenging to find a direct argument for the corollary that does not involve passing to a substructure where choice holds. Note that even for ${X=\omega_1}$ there is some work involved, since ${\omega_1}$ could have cofinality ${\omega,}$ so the straightforward inductive argument may fail.

I believe it is still open whether ${\kappa\rightarrow(\kappa,\omega+1)^2}$ holds whenever ${\kappa}$ is a cardinal of uncountable cofinality.

2. Jónsson cardinals

Recall from Definition 15 on lecture III.2 that a cardinal ${\kappa}$ is Jónsson iff every algebra on ${\kappa}$ admits a proper subalgebra of size ${\kappa.}$ Here, an algebra is a structure of the form ${(A,f_n)_{n<\omega}}$ where for each ${n}$ there is an ${m_n<\omega}$ such that ${f_n:[A]^{m_n}\rightarrow A.}$ An algebra without such proper substructures is called a Jónsson algebra.

The following is immediate:

Lemma 5 ${\omega}$ is not Jónsson.

Proof: Consider ${f_1(\{n\})=|n-1|.}$ $\Box$

From the Shelah-${\mbox{Todor\v cevi\'c}}$ results from last lecture, we have:

Theorem 6 (Shelah, ${\mbox{Todor\v cevi\'c}}$) If ${\kappa}$ is the successor of a regular cardinal (or simply if ${\omega<\kappa}$ is regular and admits a nonreflecting stationary subset), then ${\kappa}$ is not Jónsson, since in fact ${\kappa\not\rightarrow[\kappa]^2_{\kappa}.}$ ${\Box}$

Similarly:

Theorem 7 (${\mbox{Todor\v cevi\'c}}$) If all regular cardinals ${\kappa}$ below the singular cardinal ${\lambda}$ satisfy ${\kappa\not\rightarrow[\kappa]^2_\kappa,}$ then so does ${\lambda^+.}$ In particular, ${\lambda^+}$ is not Jónsson. It suffices that there is a scale for ${\lambda}$ supported by such cardinals ${\kappa.}$ ${\Box}$

A few additional cases are established by the following theorems. First, an obvious observation:

Lemma 8 For any infinite cardinal ${\kappa,}$ ${\kappa\not\rightarrow[\kappa]^{<\omega}_\omega.}$

Proof: Let ${f:[\kappa]^{<\omega}\rightarrow\omega}$ be given by ${f(x)=|x|.}$ $\Box$

We begin with several nice characterizations of Jónsson cardinals. Item 2 is due to ${\mbox{Erd\H os}}$-Hajnal, item 3 to Keisler-Rowbottom, items 4, 5 are due to Tryba, and item 6 is due to Kleinberg.

Theorem 9 The following are equivalent:

1. ${\kappa}$ is Jónsson.
2. ${\kappa\rightarrow[\kappa]^{<\omega}_\kappa.}$
3. Any structure for a countable first order language with domain of size ${\kappa}$ admits a proper elementary substructure with domain of size ${\kappa.}$
4. For every ${\gamma>\kappa}$ there exists an elementary embedding ${j : M\rightarrow V_\gamma}$ (for some transitive ${M}$) such that ${{\rm cp}(j)<\kappa}$ and ${j(\kappa)=\kappa.}$
5. For some ordinal ${\gamma\ge\kappa+2}$ there exists an elementary embedding ${j : M\rightarrow V_\gamma}$ such that ${{\rm cp}(j)<\kappa}$ and ${j(\kappa)=\kappa.}$
6. There is some cardinal ${\rho<\kappa}$ such that ${\kappa\rightarrow[\kappa]^{<\omega}_{\rho,<\rho}.}$
7. For every sufficiently large regular ${\theta>\kappa}$ and any ${t\in H_\theta,}$ there is an elementary substructure ${M}$ of ${(H_\theta,\in,<_\theta),}$ where ${<_\theta}$ is a well-ordering of ${H_\theta,}$ such that ${t,\kappa\in M,}$ ${|\kappa\cap M|=\kappa,}$ and yet ${\kappa\not\subseteq M.}$

Of course, items 5 and 6 can also be stated in terms of the ${H_\theta}$ structures, and item 7 also has a version in which we just require that some ${\theta}$ has the stated property.

Recall that ${H_\theta}$ is the collection of sets whose transitive closure has size strictly less than ${\theta.}$ This is a model of ${{\sf ZFC}-\mbox{Power set}.}$ The well-ordering ${<_\theta}$ is mostly for convenience, and provides us with definable Skolem functions.

Proof: 1 implies 2. Given ${f:[\kappa]^{<\omega}\rightarrow\kappa,}$ consider the algebra ${{\mathcal A}=(\kappa,f\upharpoonright [\kappa]^n)_{n<\omega}.}$ Since ${\kappa}$ is Jónsson, there is a proper subalgebra of ${{\mathcal A}}$ of size ${\kappa.}$ In particular, if ${A}$ is the universe of this subalgebra, ${f''[A]^{<\omega}\subseteq A\ne\kappa.}$

2 implies 3. By means of appropriate coding, one can represent any function ${f:\kappa^n\rightarrow\kappa}$ by finitely many functions ${f_i:[\kappa]^{m_i}\rightarrow\kappa.}$ For example, if ${f:\kappa^2\rightarrow\kappa,}$ we can set ${f_1(\alpha,\beta)=f(\alpha,\beta),}$ ${f_2(\alpha,\beta)=f(\beta,\alpha)}$ and ${f_3(\alpha)=f(\alpha,\alpha).}$ Note that here ${f_i(\vec \alpha)}$ means, according to our conventions, ${f_i(x)}$ where ${x=\{\vec\alpha\},}$ and ${\vec\alpha}$ lists the elements of ${x}$ in increasing order.

Given a structure ${{\mathcal A}}$ with universe ${\kappa}$ in a countable language, we can add Skolem functions to it, and still obtain a countable language. Apply the coding mentioned above, and let ${(h_i:i<\omega)}$ list all the resulting colorings in such a way that ${h_i}$ is ${n_i}$-ary for some ${n_i\le i.}$ (Add “dummy” functions if necessary to achieve this.)

Now define ${f:[\kappa]^{<\omega}\rightarrow\kappa}$ by ${f(x_0,\dots,x_{i-1})=h_i(x_0,\dots,x_{n_i-1}).}$ If ${A}$ is of size ${\kappa}$ and closed under ${f,}$ then ${A}$ is closed under the ${h_i}$ and therefore under the Skolem functions for the original structure. But then ${A}$ is the universe of a proper elementary substructure of ${{\mathcal A}.}$

3 implies 4. Let ${\gamma>\kappa.}$ By the Löwenheim-Skolem theorem there is an
$\displaystyle (A,\in)\preceq(V_\gamma,\in)$
with ${\kappa+1\subseteq A}$ and ${|A|=\kappa;}$ here, ${\preceq}$ denotes the elementary substructure relation.

Consider the structure ${{\mathcal A}=(A,\in,g,\kappa)}$ where ${\kappa}$ is treated as a constant and ${g:A\rightarrow\kappa}$ is a bijection. Since ${\kappa}$ is Jónsson, ${{\mathcal A}}$ admits a proper elementary substructure
$\displaystyle (B,\in,g\upharpoonright B,\kappa)$
of size ${\kappa.}$

Let ${\pi:B\rightarrow M}$ be the Mostowski collapsing map, which is defined since ${V_\gamma}$ is transitive. Since ${B\ne A,}$ we necessarily have ${\kappa\not\subseteq B.}$ Otherwise, since ${g}$ is a bijection, we could define ${g^{-1}}$ and it would follow that ${A\subseteq B.}$ Also, since ${|B|=\kappa,}$ we have that ${|B\cap\kappa|=\kappa}$ (again, because ${g}$ is a bijection), and therefore ${\pi(\kappa)=\pi''(\kappa\cap B)=\kappa,}$ but ${\pi\upharpoonright\kappa}$ is not the identity.

We now obtain the desired embedding by considering ${\pi^{-1}:M\rightarrow V_\gamma.}$

4 implies 5. This is obvious.

5 implies 6. Assume ${j:M\rightarrow V_\gamma}$ is elementary, where ${\gamma\ge\kappa+2,}$ ${j(\kappa)=\kappa}$ and ${{\rm cp}(j)<\kappa.}$ It is easy to check that ${\nu={\rm cp}(j)}$ is regular and uncountable in ${M.}$

We claim that ${\kappa\rightarrow[\kappa]^{<\omega}_{\nu,<\nu}}$ holds in ${M.}$ (It is in order to have the relevant functions around that we require that ${\gamma\ge\kappa+2.}$) Recall that ${\kappa\rightarrow[\kappa]^{<\omega}_{\nu,<\nu}}$ means that whenever ${f:[\kappa]^{<\omega}\rightarrow\nu,}$ there is some ${X\in[\kappa]^\kappa}$ such that ${|f''[X]^{<\omega}|<\nu.}$

Assume otherwise, and let ${f:[\kappa]^{<\omega}\rightarrow\nu}$ be a counterexample in ${M.}$ By elementarity, ${j(\nu)<\kappa}$ is an uncountable regular cardinal and ${j(f):[\kappa]^{<\omega}\rightarrow j(\nu)}$ witnesses ${\kappa\not\rightarrow[\kappa]^{<\omega}_{j(\nu), in ${V_\gamma}$ and therefore in ${V.}$ In particular, if ${X=j''\kappa,}$ then ${j(f)''[X]^{<\omega}}$ must have size ${j(\nu).}$ However, ${j(f)''[X]^{<\omega}=j''f''[\kappa]^{<\omega}\subseteq j''\nu}$ has size ${\nu contradiction.

By elementarity, it follows that ${\kappa\rightarrow[\kappa]^{<\omega}_{j(\nu), holds in ${V.}$

6 implies 1. This is clear.

7 implies 2. If ${\kappa}$ is not Jónsson and ${M}$ is as in 7 (for any ${t}$), there is in ${M}$ a witness ${f:[\kappa]^{<\omega}\rightarrow\kappa}$ to the failure of 2. But ${M\cap\kappa}$ is closed under ${f,}$ contradiction.

2 implies 7. Given ${t\in H_\theta,}$ let ${{\mathcal A}=(H_\theta,\in,<_\theta,\kappa,\{\kappa\},t),}$ where ${t}$ is treated as a constant, and ${\kappa}$ and ${\{\kappa\}}$ as relations, so any substructure of ${{\mathcal A}}$ contains ${t}$ and ${\kappa}$ as elements.

Let ${(h_n:n<\omega)}$ be a complete set of Skolem functions for ${{\mathcal A}}$ with ${h_n}$ of arity ${k_n\le n}$ for all ${n<\omega.}$ As in the proof that 2 implies 3, we may assume that ${{\rm dom}(h_n)=[H_\theta]^{k_n}}$ rather that ${H_\theta^{k_n}.}$

Set ${f:[\kappa]^{<\omega}\rightarrow\omega}$ by
$\displaystyle f(x)=\left\{\begin{array}{cl}h_n(x\upharpoonright k_n)&\mbox{ if }h_n(x\upharpoonright k_n)\in\kappa,\\ {0}&\mbox{ otherwise.}\end{array}\right.$

Here, ${n=|x|}$ for ${x\in[\kappa]^{<\omega}}$ and ${x\upharpoonright k_n}$ is the subset of ${x}$ consisting of its first ${k_n}$ many elements in increasing order.

By assumption, there is ${H\in[\kappa]^\kappa}$ such that ${f''[H]^{<\omega}\ne\kappa.}$ Let
$\displaystyle M=\bigcup_n h_n''[H]^{k_n},$
so ${|M|=\kappa}$ and ${M}$ is the universe of an elementary substructure of ${{\mathcal A}.}$ Note that ${M\cap \kappa=f''[H]^{<\omega},}$ so ${M\cap\kappa\ne\kappa.}$ It follows that ${M}$ is as required. $\Box$

By a standard Löwenheim-Skolem type of argument, we may also assume in 7 that ${s\subset M}$ for any ${s\in H_\theta}$ with ${|s|<\kappa.}$

Theorem 10 (${\mbox{Erd\H os}}$-Hajnal) If ${\kappa}$ is not Jónsson, neither is ${\kappa^+.}$

Proof: For each ${\alpha\in[\kappa,\kappa^+),}$ let ${f_\alpha:[\alpha]^{<\omega}\rightarrow\alpha}$ witness ${\alpha\not\rightarrow[\kappa]^{<\omega}_\alpha.}$ Since ${\kappa}$ is not Jónsson, these functions exist. Now set ${g:[\kappa^+]^{<\omega}\rightarrow\kappa^+}$ by
$\displaystyle g(s)=f_\alpha(s\setminus\{\alpha\})$
for ${\alpha=\max(s),}$ if this maximum is at least ${\kappa.}$ Set ${g(s)=0}$ otherwise.

It is straightforward to check that ${g}$ witnesses that ${\kappa^+}$ is not Jónsson. For suppose ${X\in[\kappa^+]^{\kappa^+}.}$ Let ${\alpha<\kappa^+}$ and let ${\beta\in X}$ be such that ${|X\cap\beta|=\kappa}$ and ${\alpha<\beta.}$ There is some ${s\in[X\cap\beta]^{<\omega}}$ such that ${f_\beta(s)=\alpha.}$ Then ${g(s\cup\{\beta\})=\alpha}$ and we are done. $\Box$

Lemma 11 (Kleinberg) If ${\kappa}$ is Jónsson, then the least cardinal ${\nu<\kappa}$ such that ${\kappa\rightarrow[\kappa]^{<\omega}_{\nu}}$ is regular and uncountable, and we actually have ${\kappa\rightarrow[\kappa]^{<\omega}_{\nu,<\nu}.}$

Proof: That there is some such ${\nu}$ follows from Theorem 9. Letting ${\nu}$ be least such that ${\kappa\rightarrow[\kappa]^{<\omega}_\nu,}$ Lemma 8 shows that ${\nu>\omega,}$ and it suffices to check that ${\kappa\rightarrow[\kappa]^{<\omega}_{{\rm cf}(\nu),<{\rm cf}(\nu)}.}$

For this, assume otherwise, and let ${g:[\kappa]^{<\omega}\rightarrow{\rm cf}(\nu)}$ be a counterexample. Let ${h:{\rm cf}(\nu)\rightarrow\nu}$ be increasing and cofinal. For each ${\beta<\nu,}$ let ${f_\beta:[\kappa]^{<\omega}\rightarrow\beta}$ witness ${\kappa\not\rightarrow[\kappa]^{<\omega}_\beta.}$

Now set ${f:[\kappa]^{<\omega}\rightarrow\nu}$ by
$\displaystyle f(\xi_1,\dots,\xi_n)=f_{h(g(\xi_1,\dots,\xi_{n_0}))}(\xi_{n_0+1},\dots,\xi_{n_0+n_1})$
whenever ${n=2^{n_0}3^{n_1},}$ for some ${n_0,n_1>0,}$ and ${f(x)=0}$ whenever ${|x|}$ is not of this form.

It is straightforward to check that ${f}$ witnesses ${\kappa\not\rightarrow[\kappa]^{<\omega}_\nu.}$ This is because if ${X\in[\kappa]^\kappa}$ then for each ${\gamma<\nu}$ we can find some ${\alpha<{\rm cf}(\nu)}$ such that ${\gamma There is some ${x\in[X]^{<\omega}}$ such that ${g(x)\ge\alpha.}$ Let ${\beta=h(g(x)),}$ and let ${Y=X\setminus(\max(x)+1).}$ Then ${|Y|=\kappa,}$ so there is some ${y\in[Y]^{<\omega}}$ such that ${f_\beta(y)=\gamma.}$ Now let ${s\in[X]^{<\omega}}$ have the form ${x\cup y\cup z}$ where ${z\in [X\setminus(\max(y)+1)]^{<\omega}}$ is chosen so that ${|s|=2^{|x|}3^{|y|}.}$ Then ${f(s)=\gamma.}$ Since ${\gamma<\nu}$ was arbitrary, this shows that ${f''[X]^{<\omega}=\nu,}$ contradiction. $\Box$

In light of characterization 6 in Theorem 9, it is natural to wonder whether one can have ${\kappa\rightarrow[\kappa]^{<\omega}_{\kappa,<\kappa}.}$ This is impossible for ${\kappa}$ regular:

Lemma 12 For all infinite cardinals ${\kappa,}$ ${\kappa\not\rightarrow[\kappa]^{1}_{{\rm cf}(\kappa),<{\rm cf}(\kappa)}.}$

Proof: Let ${g:{\rm cf}(\kappa)\rightarrow\kappa}$ be strictly increasing and cofinal with ${g(0)=0.}$ Define
$\displaystyle f:[\kappa]^{1}\rightarrow{\rm cf}(\kappa)$
by ${f(\gamma)=\alpha}$ iff ${\gamma\in[g(\alpha),g(\alpha+1)).}$

Assume that ${X\subseteq\kappa}$ and ${|f''[X]^{1}|<{\rm cf}(\kappa).}$ Then ${\beta=\sup (f''[X]^{1})<{\rm cf}(\kappa).}$ Thus ${X\subseteq g(\beta+1)}$ and ${|X|<\kappa.}$

This shows that ${f}$ witnesses ${\kappa\not\rightarrow[\kappa]^{1}_{{\rm cf}(\kappa),<{\rm cf}(\kappa)}.}$ $\Box$

Recall that if ${\kappa}$ is a cardinal, and ${\omega<\nu<\kappa,}$ then ${\kappa}$ is ${\nu}$-Rowbottom iff ${\kappa\rightarrow[\kappa]^{<\omega}_{\lambda,<\nu}}$ for any ${\lambda<\kappa,}$ and it is Rowbottom iff it is ${\omega_1}$-Rowbottom.

Obviously, if ${\kappa}$ is ${\nu}$-Rowbottom for some ${\nu,}$ then it is Jónsson. We want to show that, in fact, the least Jónsson cardinal must be ${\nu}$-Rowbottom for some ${\nu<\kappa.}$ First, an easy extension of the techniques showing Theorem 9 shows:

Lemma 13 (Rowbottom) Suppose that ${\kappa\ge\lambda}$ and ${\omega<\nu\le\mu\le \kappa.}$ Then the following are equivalent:

1. ${\kappa\rightarrow[\mu]^{<\omega}_{\lambda,<\nu}.}$
2. Every structure of size ${\kappa}$ in a countable language with a distinguished unary relation of size ${\lambda}$ admits an elementary substructure of size ${\mu}$ where the relation has size strictly smaller than ${\nu.}$

Proof: That 2 implies 1 is obvious: Given ${f:[\kappa]^{<\omega}\rightarrow\lambda}$ let
$\displaystyle {\mathcal A}=(\kappa,\lambda,\in,f\upharpoonright[\kappa]^n)_{n<\omega},$
where ${\lambda}$ is treated as a relation, and we are using that straightforward coding allows us to consider colorings (with domain ${[\kappa]^n}$ for some ${n}$) as elements of the language (rather than functions whose domain is ${\kappa^n}$ for some ${n}$).

There is an elementary substructure ${{\mathcal B}}$ of ${{\mathcal A}}$ of size ${\mu}$ such that ${|{\mathcal B}\cap\lambda|<\nu.}$ Since ${{\mathcal B}}$ is closed under ${f,}$ then ${{\mathcal B}}$ witnesses ${\kappa\rightarrow[\mu]^{<\omega}_{\lambda,<\nu}}$ for ${f.}$

That 1 implies 2 is essentially the proof that 2 implies 7 in Theorem 9: Given
$\displaystyle {\mathcal A}=(\kappa,\lambda,\dots)$
a structure in a countable language, where ${\lambda}$ is treated as a relation, let ${(h_n:n<\omega)}$ be a complete set of Skolem functions for ${{\mathcal A}}$ with ${h_n}$ of arity ${k_n\le n}$ for all ${n<\omega,}$ and define ${f:[\kappa]^{<\omega}\rightarrow\lambda}$ by setting
$\displaystyle f(x)=\left\{\begin{array}{cl}h_n(x\upharpoonright k_n)&\mbox{ if }h_n(x\upharpoonright k_n)<\lambda,\\ {0}&\mbox{ otherwise.}\end{array}\right.$

Here, ${n=|x|}$ for ${x\in[\kappa]^{<\omega}}$ and ${x\upharpoonright k_n}$ is the subset of ${x}$ consisting of its first ${k_n}$ many elements in increasing order.

By assumption, there is ${H\in[\kappa]^\mu}$ such that ${|f''[H]^{<\omega}|<\nu.}$ Let
$\displaystyle B=\bigcup_n h_n''[H]^{k_n},$
so ${|B|=\mu}$ and ${B}$ is the universe of an elementary substructure of ${{\mathcal A}.}$ Note that ${B\cap \lambda=f''[H]^{<\omega},}$ so ${|B\cap\lambda|<\nu.}$ It follows that ${B}$ is as required. $\Box$

Lemma 14 (Kleinberg) If ${\kappa\rightarrow[\kappa]^{<\omega}_\lambda}$ and ${\lambda}$ is not Jónsson, then ${\kappa\rightarrow[\kappa]^{<\omega}_{\lambda,<\lambda}.}$

Proof: Let ${g:[\kappa]^{<\omega}\rightarrow\kappa}$ be any function extending a witness to ${\lambda\not\rightarrow[\lambda]^{<\omega}_\lambda.}$ Given a structure
$\displaystyle {\mathcal A}=(\kappa,\lambda,\dots)$
in a countable language, extend ${{\mathcal A}}$ to
$\displaystyle \hat{\mathcal A}=(\kappa,\lambda,\dots,g\upharpoonright[\kappa]^n)_{n<\omega}.$
using Skolem functions for ${{\mathcal A},}$ define ${f:[\kappa]^{<\omega}\rightarrow\lambda}$ as before. Let ${B\in[\kappa]^\kappa}$ be such that ${f''[B]^{<\omega}\ne\lambda.}$ Let ${{\mathcal B}}$ be the elementary substructure of ${{\mathcal A}}$ generated by ${B,}$ so ${{\mathcal B}}$ is obtained by closing ${B}$ under the Skolem functions for ${{\mathcal A}.}$ As before, ${{\mathcal B}\cap\lambda=f''[B]^{<\omega}\ne\lambda.}$ This implies that, in fact, ${|{\mathcal B}\cap\lambda|<\lambda,}$ since ${{\mathcal B}}$ is closed under ${g.}$ The result now follows from Lemma 13. $\Box$

Corollary 15 (Kleinberg) Let ${\kappa}$ be the least Jónsson cardinal, and let ${\delta<\kappa}$ be least such that ${\kappa\rightarrow[\kappa]^{<\omega}_\delta.}$ Then ${\kappa}$ is ${\delta}$-Rowbottom.

Proof: We need to show that ${\kappa\rightarrow[\kappa]^{<\omega}_{\lambda,<\delta}}$ for all ${\lambda<\kappa.}$ Towards a contradiction, suppose ${\lambda}$ is least such that this fails, as witnessed by ${f:[\kappa]^{<\omega}\rightarrow\lambda.}$ Note that ${\kappa\rightarrow[\kappa]^{<\omega}_\lambda,}$ since ${\lambda\ge\delta}$ and ${\kappa\rightarrow[\kappa]^{<\omega}_\delta.}$ By Lemma 14, there is some ${\tau<\lambda}$ and an ${H\in[\kappa]^\kappa}$ such that ${|f''[H]^{<\omega}|=\tau.}$ Then, up to reindexing, ${f:[H]^{<\omega}\rightarrow\tau.}$ By minimality of ${\lambda,}$ there must be some ${I\in[H]^\kappa}$ such that ${|f''[I]^{<\omega}|<\delta.}$ This is a contradiction. $\Box$

Tryba has shown the following result, closely related to Corollary 15:

Theorem 16 (Tryba) Assume that ${\kappa}$ is Jónsson and strongly inaccessible. Then ${\kappa}$ is ${\delta}$-Rowbottom for some ${\delta<\kappa}$. ${\Box}$

Apparently it is still open whether every weakly inaccessible Jónsson cardinal satisfies the conclusion of Theorem 16.

From Lemmas 12 and 14, it follows that if ${\kappa\rightarrow[\kappa]^{<\omega}_{{\rm cf}(\kappa)},}$ then ${{\rm cf}(\kappa)}$ must be a Jónsson cardinal.

Theorem 17 (Prikry) Suppose that ${\kappa}$ is a singular limit of measurable cardinals. Then ${\kappa}$ is ${{\rm cf}(\kappa)^+}$-Rowbottom. ${\Box}$

As shown in Theorems 25 and 26 below, any measurable cardinal is Jónsson. It is then natural to ask whether ${\kappa\rightarrow[\kappa]^{<\omega}_{{\rm cf}(\kappa)}}$ can ever hold in the context of Theorem 17. This was recently shown by Woodin.

Theorem 18 (Woodin) If ${\kappa}$ is measurable, ${\lambda>\kappa}$ is a limit of measurable cardinals, and ${{\rm cf}(\lambda)=\kappa,}$ then ${\lambda\rightarrow[\lambda]^{<\omega}_\kappa.}$

We postpone the proof until next Section.

The following is a counterpart to ${\mbox{Todor\v cevi\'c}}$‘s Theorem 7. It illustrates a very useful pcf trick, the use of “characteristic functions.”

Theorem 19 (Shelah) Suppose that ${\lambda=\mu^+}$ where ${\mu}$ is a singular cardinal. Let ${(\vec\mu,\vec f)}$ be a scale for ${\mu}$ such that each ${\mu_i}$ is not Jónsson. Then neither is ${\lambda.}$

Proof: We use characterization 7 of Theorem 9.

Recall that if ${(\vec\mu,\vec f)}$ is a scale for ${\mu,}$ then ${\vec\mu=(\mu_i:i<{\rm cf}(\mu))}$ is a strictly increasing sequence of regular cardinals cofinal in ${\mu,}$ and ${\vec f=(f_\alpha:\alpha<\lambda)}$ where each ${f_\alpha\in\prod_i\mu_i,}$ the sequence is ${<_{b,{\rm cf}(\mu)}}$-increasing and cofinal, i.e., a witness to
$\displaystyle {\rm tcf}(\prod_i\mu_i,<_{b,{\rm cf}(\mu)})=\lambda.$

Let ${\theta}$ be a sufficiently large regular cardinal and let ${M\prec H_\theta}$ be such that ${\lambda,(\vec \mu,\vec f)\in M,}$ ${{\rm cf}(\mu)\subset M,}$ and ${|M\cap\lambda|=\lambda.}$ We need to show that ${\lambda\subseteq M.}$

Suppose first that for all large enough ${i<{\rm cf}(\mu)}$ we have that ${|M\cap\mu_i|<\mu_i.}$ Consider the characteristic function of ${M}$ on ${\vec\mu}$, defined by
$\displaystyle \chi_M^{\vec \mu}(i)=\left\{\begin{array}{cl}\sup(M\cap\mu_i)&\mbox{ if }\sup(M\cap\mu_i)<\mu_i,\\ {0}&\mbox{ otherwise.}\end{array}\right.$

By definition, ${\chi_M^{\vec\mu} \in\prod_i\mu_i.}$ Also, by our assumption, ${\chi_M^{\vec\mu}(i)=\sup(M\cap\mu_i)}$ for all ${i}$ large enough. Since ${\vec f}$ is ${<_{b,{\rm cf}(\mu)}}$-cofinal in ${\prod_i\mu_i}$ and ${|M\cap\lambda|=\lambda,}$ there must be some ${\alpha\in M\cap\lambda}$ such that
$\displaystyle \chi_M^{\vec \mu}(i)
for all large enough ${i.}$ Note that ${{\rm dom}(f_\alpha)\subseteq M}$ and ${f_\alpha\in M,}$ so ${f_\alpha(i)\in M}$ for all ${i.}$ This, of course, contradicts the displayed inequality.

It follows that ${|M\cap\mu_i|=\mu_i}$ for arbitrarily large values of ${i<{\rm cf}(\mu).}$ For any such ${i,}$ since ${\mu_i\in M}$ and ${\mu_i}$ is not Jónsson, then ${\mu_i\subseteq M.}$ This is because ${M}$ contains some witness ${g_i}$ to ${\mu_i\not\rightarrow[\mu_i]^{<\omega}_{\mu_i},}$ by elementarity, and so
$\displaystyle \mu_i=g_i''[M\cap\mu_i]^{<\omega}\subseteq M.$

It follows that ${\mu\subseteq M.}$ If ${\alpha<\lambda}$ and ${\alpha\in M,}$ then ${\alpha\subseteq M,}$ as ${M}$ must contain some surjection from ${\mu}$ onto ${\alpha,}$ and should therefore also contain its range. Since ${M\cap\lambda}$ is unbounded in ${\lambda,}$ we can now conclude that ${\lambda\subseteq M.}$ $\Box$

Theorem 20 (Rowbottom) The first Jónsson cardinal is either weakly inaccessible, or singular of cofinality ${\omega.}$

Proof: From the results above, the first Jónsson cardinal ${\kappa}$ is a limit. Suppose ${\omega<{\rm cf}(\kappa)=\lambda<\kappa.}$

Fix a club ${C=\{\mu_\alpha:\alpha<\lambda\}\subseteq\kappa}$ consisting of cardinals, with ${\lambda<\mu_0.}$ For each ${\alpha<\lambda,}$ fix also a witness ${f_\alpha}$ to ${\mu_\alpha\not\rightarrow[\mu_\alpha]^{<\omega}_{\mu_\alpha}.}$ Finally, let ${g:[\kappa]^{<\omega}\rightarrow\kappa}$ extend any witness to ${\lambda\not\rightarrow[\lambda]^{<\omega}_\lambda.}$ Let ${h:\kappa\rightarrow\lambda}$ be such that
$\displaystyle h(\xi)=\alpha\mbox{ iff }\xi\in[\mu_\alpha,\mu_{\alpha+1})$
for all ${\xi\ge\mu_0.}$

Now set ${f:[\kappa]^{<\omega}\rightarrow\kappa}$ by
$\displaystyle f(x)=\left\{\begin{array}{cl}f_\alpha(s\setminus\{\alpha\})&\mbox{ if }\alpha=\min(s)\mbox{ and }\max(s)<\mu_\alpha,\\ {0}&\mbox{ otherwise.}\end{array}\right.$

Let ${{\mathcal A}=(\kappa,f\upharpoonright[\kappa]^n,g\upharpoonright[\kappa]^n,h)_{n<\omega}.}$ It is enough to check that ${{\mathcal A}}$ is a Jónsson algebra.

Towards a contradiction, let ${X\in[\kappa]^\kappa}$ be the domain of a proper subalgebra of ${{\mathcal A}.}$ Since ${h}$ is in the language of ${{\mathcal A},}$ we have ${|X\cap\lambda|=\lambda.}$ By the presence of ${g,}$ it follows that ${\lambda\subset X.}$

Let ${\xi<\kappa.}$ Pick ${\alpha_0<\lambda}$ such that ${\xi<\mu_{\alpha_0}}$ and, recursively, choose ${\alpha_1,\alpha_2,\dots}$ so for each ${n<\omega,}$

• ${\alpha_n\le\alpha_{n+1}<\lambda,}$ and
• ${|X\cap\mu_{\alpha_{n+1}}|\ge\mu_{\alpha_n}.}$

Using that ${\lambda>\omega,}$ note that ${\beta=\sup_n\alpha_n<\lambda.}$ Since ${C}$ is club, ${\mu_\beta}$ is defined, and by choice of the ${\alpha_n,}$ we have that ${|X\cap\mu_\beta|=\mu_\beta.}$ Recall that ${\beta\in X,}$ because ${\beta\in\lambda\subset X.}$ It easily follows from the definition of ${f}$ and the choice of ${f_\beta}$ that ${\mu_\beta\subset X.}$ Since ${\xi\in\mu_\beta,}$ then ${\xi\in X.}$ Since ${\xi<\kappa}$ was arbitrary, ${\kappa=X.}$

This contradicts that ${\kappa}$ is Jónsson. $\Box$

Theorem 20 can be strengthened as follows:

Theorem 21 (Tryba) If ${\kappa}$ is a singular cardinal of uncountable cofinality, and ${\kappa}$ is Jónsson, then

$\displaystyle \{\lambda<\kappa:\lambda\mbox{ is J\'onsson}\}$
contains a club. ${\Box}$

There is a companion result to the theorem above for successors of singulars of uncountable cofinality:

Theorem 22 (Shelah) Suppose that ${\mu}$ is singular of uncountable cofinality, and that ${\mu^+}$ is Jónsson. Then

$\displaystyle \{\theta<\mu:\theta^+\mbox{ is J\'onsson}\}$
is club in ${\mu.}$ ${\Box}$

The following is the main open problem in this area:

Open question. Can ${\aleph_\omega}$ be Jónsson?

Kleinberg showed that the notion of Jónsson and Rowbottom are equiconsistent. Clearly, from characterization 6 in Theorem 9, say, if there is a Jónsson cardinal then ${0^\sharp}$ exists. Building on results of Donder and Koepke, Peter Koepke showed that if ${\aleph_\omega}$ is Jónsson, then for every ${\alpha}$ there is an inner model with ${\alpha}$ many measurable cardinals. I expect the assumption that ${\aleph_\omega}$ is Jónsson to carry a much higher consistency strength.

3. Large cardinals

Recall from Definition 13 in lecture III.2 that a cardinal ${\kappa}$ is Ramsey iff ${\kappa\rightarrow(\kappa)^{<\omega}.}$

Remember that this means that for any ${f:[\kappa]^{<\omega}\rightarrow 2}$ there is an ${H\in[\kappa]^\kappa}$ that is homogeneous for ${f\upharpoonright[\kappa]^n}$ for all ${n<\omega.}$ Obviously, Ramsey cardinals are Jónsson. They are large cardinals as well:

Definition 23 A weakly compact cardinal is a cardinal ${\kappa}$ such that ${\kappa\rightarrow(\kappa)^2.}$

Clearly, Ramsey cardinals are weakly compact.

Lemma 24 (${\mbox{Erd\H os}}$) If ${\kappa}$ is weakly compact, then it is strongly inaccessible.

Proof: It follows from Sierpi\’nski’s Theorem that ${\kappa}$ must be strong limit: Otherwise, let ${\lambda<\kappa}$ be such that ${2^\lambda\ge\kappa.}$ Then ${2^\lambda\not\rightarrow(\lambda^+)^2,}$ so ${\kappa\not\rightarrow(\kappa)^2.}$

We argue that ${\kappa}$ must also be regular: Otherwise, ${\kappa=\bigcup_{\xi<{\rm cf}(\kappa)}X_\xi}$ for some sets ${X_\xi}$ of size less than ${\kappa.}$ Let ${f:[\kappa]^2\rightarrow2}$ be given by ${f(\alpha,\beta)=0}$ iff ${ \alpha,\beta}$ are in the same ${X_\xi.}$ Then ${f}$ does not have a homogeneous set of size ${\kappa}$: It clearly does not admit a 0-homogeneous set, but if ${H\in[\kappa]^\kappa}$ then (since ${{\rm cf}(\kappa)<\kappa)}$ there must be two elements of ${H}$ in the same ${X_\xi,}$ so ${H}$ cannot be 1-homogeneous.

(For a different proof of regularity, see Lemma 7 in lecture III.2.) $\Box$

One can show that if ${\kappa}$ is weakly compact, then
$\displaystyle \{ \alpha<\kappa\colon \alpha\mbox{ is strongly inaccessible}\}$
is stationary in ${\kappa,}$ i.e., ${\kappa}$ is Mahlo.

By induction, say that ${\kappa}$ is 1-Mahlo iff it is Mahlo; say that it is ${( \alpha+1)}$-Mahlo iff it is strongly inaccessible and ${\{\rho<\kappa\colon\rho}$ is ${ \alpha}$-Mahlo${\}}$ is stationary in ${\kappa}$; and say that it is ${\lambda}$-Mahlo, for ${\lambda}$ limit, iff it is ${ \alpha}$-Mahlo for all ${ \alpha<\lambda.}$

Then one can in fact show that if ${\kappa}$ is weakly compact, it is ${\kappa}$-Mahlo and limit of cardinals ${\rho}$ that are ${\rho}$-Mahlo.

Many equivalent characterizations of weakly compact cardinals are known. For example, ${\kappa}$ is weakly compact iff it is inaccessible and has the tree property. This means that whenever ${T}$ is a tree of height ${\kappa}$ all of whose levels have size ${<\kappa,}$ then there is a cofinal branch through ${T,}$ i.e., the version of König’s lemma for ${\kappa}$ holds.

Keisler proved that ${\kappa}$ is weakly compact iff it has the extension property: for any ${R\subseteq V_\kappa,}$ there is a transitive ${X\ne V_\kappa}$ and an ${S\subseteq X}$ such that ${(V_\kappa,\in,R)\prec(X,\in,S).}$

Theorem 25 A Ramsey cardinal is Rowbottom. In fact, ${\kappa}$ is Ramsey iff for all ${\gamma<\kappa,}$ ${\kappa\rightarrow(\kappa)^{<\omega}_\gamma.}$

Proof: Let ${\kappa}$ be Ramsey and consider ${\gamma<\kappa}$ and a coloring ${f:[\kappa]^{<\omega}\rightarrow\gamma.}$ Define ${g:[\kappa]^{<\omega}\rightarrow2}$ by setting ${g(x)=1,}$ unless ${|x|=2n}$ for some ${n<\omega}$ and ${f(x\upharpoonright n)=f(x\upharpoonright(2n\setminus n)),}$ in which case ${g(x)=0.}$

If ${C\in[\kappa]^\kappa}$ is homogeneous for ${g,}$ then it must clearly be ${0}$-homogeneous, and therefore it is also homogeneous for ${f.}$ $\Box$

Theorem 26 (${\mbox{Erd\H os}}$-Rado) Measurable cardinals are Ramsey.

Proof: We present an argument due to Rowbottom. Let ${{\mathcal U}}$ be a normal ${\kappa}$-complete nonprincipal ultrafilter over ${\kappa.}$ Let ${\gamma<\kappa}$ and consider a coloring ${f:[\kappa]^{<\omega}\rightarrow\gamma.}$

By induction on ${n}$ we show that for any ${g:[\kappa]^n\rightarrow\gamma}$ there is an ${X\in{\mathcal U}}$ that is homogeneous for ${g.}$

For ${n=1}$ this is clear from the ${\kappa}$-completeness of ${{\mathcal U}.}$ Assume the result for ${n,}$ and consider a map ${g:[\kappa]^{n+1}\rightarrow\gamma.}$ For each ${s\in[\kappa]^n}$ let ${g_s:\kappa\rightarrow\gamma}$ be the map
$\displaystyle g_s(\alpha)=\left\{\begin{array}{cl}g(s\cup\{\alpha\})&\mbox{ if }\max(s)<\alpha,\\ {0}&\mbox{ otherwise.}\end{array}\right.$

By ${\kappa}$-completeness, for each ${s}$ there is a color ${\beta_s<\gamma}$ and a set ${X_s\in{\mathcal U}}$ such that ${g_s''X_s=\{\beta_s\}.}$ By induction, there is a color ${\beta}$ and a set ${X\in{\mathcal U}}$ such that ${\beta_s=\beta}$ for all ${s\in[X]^n.}$

For ${\alpha<\kappa}$ let ${Y_\alpha=\bigcap_{\max(s)\le\alpha}X_s,}$ so ${Y_\alpha\in{\mathcal U}}$ by ${\kappa}$-completeness. Let ${H=X\cap\bigtriangleup_{\alpha<\kappa}Y_\alpha,}$ so ${H\in{\mathcal U}.}$ It is enough to check that ${H}$ is ${\beta}$-homogeneous for ${g.}$

For this, let ${t\in[H]^{n+1}}$ and let ${\alpha=\max(t)}$ and ${s=t\setminus\{\alpha\},}$ so
$\displaystyle g(t)=g_s(\alpha)=\beta_s=\beta,$
since ${\alpha\in Y_{\max(s)}\subseteq X_s}$ and ${s\in[X]^n.}$

It follows that for all ${n}$ there is a set ${A_n\in{\mathcal U}}$ homogeneous for ${f\upharpoonright [\kappa]^n.}$ Let ${A=\bigcap_nA_n.}$ Then ${A\in{\mathcal U}}$ and ${A}$ is homogeneous for ${f.}$ $\Box$

Let me now sketch the proof of Woodin’s Theorem 18.

Proof: Recall that Theorem 18 states that ${\lambda\rightarrow[\lambda]^{<\omega}_{\kappa}}$ whenever ${\kappa={\rm cf}(\lambda)<\kappa,}$ ${\kappa}$ is measurable, and ${\lambda}$ is limit of measurable cardinals.

The argument requires some knowledge of directed systems. See, for example, the corresponding discussion in Chapter 0 of Kanamori’s book.

Let ${f:\kappa\rightarrow\lambda}$ be strictly increasing and cofinal with ${f(0)=\kappa}$ and ${f(\alpha)}$ measurable but not a limit of measurables, for all nonzero ${\alpha<\kappa.}$

Suppose that there is an elementary embedding ${\pi:M\rightarrow V_{\lambda+\omega}}$ with ${\pi(\kappa)=\kappa}$ and ${{\rm cp}(\pi)<\kappa}$ such that ${f\in{\rm ran}(\pi).}$ It follows that ${\pi(\lambda)=\lambda.}$ By the proof that 5 implies 6 in Theorem 9, it follows that ${\lambda\rightarrow[\lambda]^{<\omega}_\kappa.}$

It therefore suffices to build such an embedding ${\pi.}$ This is accomplished by building a directed system of embeddings
$\displaystyle (M_\alpha,j_{\alpha,\beta}:\alpha\le\beta<\kappa)$
together with embeddings
$\displaystyle \pi_\alpha:M_\alpha\rightarrow V_{\lambda+\omega}$
for all ${\alpha<\kappa,}$ such that the embeddings ${\pi_\alpha}$ commute with the embeddings ${j_{\alpha,\beta}}$ and, letting ${\pi:M\rightarrow V_{\lambda+\omega}}$ be the corresponding direct limit embedding, we have ${f\in{\rm ran}(\pi),}$ ${{\rm cp}(\pi)<\kappa,}$ and ${\pi(\kappa)=\kappa.}$

The construction is recursive. To begin with, arguing as in the proof that 3 implies 4 in Theorem 9, but using that measurable cardinals are Rowbottom, we may find
$\displaystyle \pi_0:M_0\rightarrow V_{\lambda+\omega}$
with ${f\in{\rm ran}(\pi_0)}$ such that ${\pi_0(\kappa)=\kappa}$ but ${{\rm cp}(\pi_0)<\omega_1.}$ Set ${j_{0,0}={\rm id}.}$

Let ${\bar f\in M_0}$ be the preimage of ${f.}$ Suppose that ${0<\gamma<\kappa}$ and
$\displaystyle (M_\alpha,j_{\alpha,\beta},\pi_\alpha:\alpha\le\beta<\gamma)$
has been defined.

• If ${\gamma}$ is limit, let ${\hat\pi_\gamma:N\rightarrow V_{\lambda+\gamma}}$ be the direct limit embedding.
• If ${\gamma=\beta+1,}$ let ${\hat\pi_\gamma=\pi_{\beta}}$ and ${N=M_\beta.}$

Let ${j:M_0\rightarrow N}$ be the natural embedding, and set ${\eta=j(\bar f)(\gamma)}$ and ${\nu=\hat\pi_\gamma(\eta),}$ so ${\nu}$ is a measurable cardinal. Let ${\mu}$ be a normal ${\nu}$-complete ultrafilter over ${\nu}$ with ${\hat\pi_\gamma(\bar\mu)=\mu}$ for some ${\bar\mu}$ that, from the point of view of ${N,}$ is a normal measure over ${\eta.}$

Let ${(A_\xi:\xi<\delta)}$ enumerate the members of ${\bar\mu,}$ so ${\delta<\nu}$ and
$\displaystyle \bigcap_\xi \hat\pi_\gamma(A_\xi)\ne\emptyset.$

Let ${\rho}$ be in this intersection. Using ${\rho,}$ one can define an embedding
$\displaystyle k_0: {\rm Ult}(N,\bar\mu)\rightarrow V_{\lambda+\omega}$
by setting ${k_0([g])=\hat\pi_\gamma(g)(\rho).}$ One easily checks that ${k_0}$ is indeed well-defined and elementary.

Let ${N_0=N,}$ ${N_1={\rm Ult}(N,\bar\mu),}$ and in general iterate the above construction to obtain a directed system
$\displaystyle (N_\alpha,i_{\alpha,\tau}:\alpha\le\tau
together with embeddings
$\displaystyle k_\alpha:N_\alpha\rightarrow V_{\lambda+\omega}$
that commute with the ${i_{\alpha,\tau}.}$

Let ${M_\gamma}$ be the direct limit of ${(N_\alpha,i_{\alpha,\tau}:\alpha\le\tau and define ${j_{\alpha,\gamma}}$ for ${\alpha\le\gamma,}$ and ${\pi_\gamma}$ in the natural way. One easily checks that ${\pi_\gamma(\nu)=\nu}$ and ${{\rm cp}(\pi_\gamma)<\kappa.}$

This completes the construction of the directed system. $\Box$

I close with a result about a strong version of Jónsson cardinals in the presence of a very strong axiom contradicting choice.

Recall that Kunen showed that there are no embeddings ${j:V\rightarrow V.}$ All the known proofs of this result (see for example lectures II.10, II.12, and III.3) use the axiom of choice in an essential way.

Theorem 27 (Sargsyan) In ${{\sf ZF},}$ assume there is an elementary embedding

$\displaystyle j:V\rightarrow V.$

Let ${\kappa_\omega}$ be the first fixed point of ${j}$ past its critical point. Then for all cardinals ${\lambda\ge\kappa_\omega}$ and all ${\delta<\kappa_\omega,}$ there is a cardinal ${\mu<\kappa_\omega}$ such that for every cardinal ${\theta\in[\mu,\kappa_\omega),}$ we have that

$\displaystyle \lambda\rightarrow[\lambda]^\delta_{\theta,<\theta}.$

In particular, all cardinals ${\lambda\ge\kappa_\omega}$ are Jónsson.

Proof: Let ${j:V\rightarrow V}$ be elementary, and set ${\kappa={\rm cp}(j).}$ Assume first that ${\delta<\kappa,}$ so ${j(\delta)=\delta.}$ Towards a contradiction, suppose that ${\lambda\ge\kappa_\omega}$ is the least cardinal such that ${\lambda\not\rightarrow[\lambda]^\delta_{\theta,<\theta}}$ for unboundedly many ${\theta<\kappa_\omega.}$ Since ${\kappa_\omega}$ is fixed by ${j}$ and ${\lambda}$ is definable from ${\kappa_\omega}$ and ${\delta,}$ then ${j(\lambda)=\lambda.}$

Let ${\theta\in[\kappa,\kappa_\omega)}$ and suppose that ${\lambda\not\rightarrow[\lambda]^\delta_{\theta,<\theta},}$ as witnessed by the function ${f.}$ Then
$\displaystyle j(f):[\lambda]^\delta\rightarrow j(\theta),$
and for all ${X\in[\lambda]^\lambda,}$ ${|j(f)''[X]^\delta|=j(\theta).}$

However, ${j''\lambda\in[\lambda]^\lambda}$ and ${j(f)''[j''\lambda]^\delta=j''f''[\lambda]^\delta\subseteq j''\theta}$ has size at most ${\theta This is a contradiction.

It follows that ${\lambda\rightarrow[\lambda]^\delta_{\theta,<\theta}}$ for all ${\theta\in[\kappa.\kappa_\omega).}$ This contradicts the definition of ${\lambda,}$ and we are done in the case that ${\delta<\kappa.}$

Consider now an arbitrary ${\delta<\kappa_\omega.}$ Again, suppose that ${\lambda\ge\kappa_\omega}$ and that ${\lambda\not\rightarrow[\lambda]^\delta_{\theta,<\theta}}$ for unboundedly many ${\theta<\kappa_\omega.}$

Recall that the critical sequence ${(\kappa_n:n<\omega)}$ is defined recursively by ${\kappa_0=\kappa}$ and ${\kappa_{n+1}=j(\kappa_n)}$ for all ${n<\omega,}$ so ${\kappa_\omega=\sup_n\kappa_n.}$

Let ${\alpha_0}$ be the least fixed point of ${j}$ past ${\lambda^{+\kappa},}$ and recursively define ${\alpha_{n+1}}$ as the least fixed point of ${j}$ past ${(\alpha_n)^{+\kappa}.}$ Define ${j_n=j\upharpoonright V_{\alpha_n}}$ and set
$\displaystyle i_n=j_n\circ j_{n-1}\circ\dots\circ j_0.$

One easily checks that ${i_n:V_{\alpha_0}\rightarrow V_{\alpha_0}}$ is elementary, ${{\rm cp}(i_n)=\kappa_n}$ and ${i_n(\kappa_m)=\kappa_{m+1}}$ whenever ${n\le m<\omega.}$

Notice that the contradiction for the case ${\delta<\kappa}$ works for our current ${\delta}$ inside ${V_{\alpha_0}}$ by considering ${i_{n+1}:V_{\alpha_0}\rightarrow V_{\alpha_0},}$ where ${n}$ is chosen so that ${\delta\in[\kappa_n,\kappa_{n+1}).}$ This completes the proof. $\Box$

Bibliography

Here are some references consulted while preparing this note:

• Arthur Apter, Grigor Sargsyan, Jónsson-like partition relations and ${j:V\rightarrow V}$, The Journal of Symbolic Logic, 69 (4) (Dec., 2004), 1267–1281.
• Todd Eisworth, Successors of singular cardinals, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., forthcoming.
• Paul ${\mbox{Erd\H os},}$ András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: partition relations for cardinals, North-Holland, (1984).
• Akihiro Kanamori, The higher infinite, Springer (1994).
• Peter Koepke, Some applications of short core models, Annals of Pure and Applied Logic, 37 (1988), 179–204.
• Grigor Sargsyan, unpublished notes.
• Jan Tryba, On Jónsson cardinals with uncountable cofinality, Israel Journal of Mathematics, 49 (4) (1984), 315–324.
• Jan Tryba, Rowbottom-type properties and a cardinal arithmetic, Proceedings of the American Mathematical Society, 96 (4) (Apr., 1986), 661–667.

Typeset using LaTeX2WP. Here is a printable version of this post.

### 6 Responses to 580 -Partition calculus (5)

1. […] also showed that cannot be replaced with in this result. And regarding Theorem 1 from last lecture, one can also prove a more general (non-topological) version: Theorem 4 (-Dushnik-Miller) Let be […]

2. […] a nice suggestion of Grigor Sargsyan, we use arguments as in Theorem 9 from lecture III.5 to show that this partition relation cannot […]

3. […] of a nice result on Reinhardt cardinals in . It complements Grigor Sargsyan’s result discussed here. Theorem (Asperó). Work in . Suppose is a nontrivial elementary embedding. Then there are a and […]

4. […] of a nice result on Reinhardt cardinals in . It complements Grigor Sargsyan’s result discussed here. Theorem (Asperó). Work in . Suppose is a nontrivial elementary embedding. Then there are a and […]

5. […] a nice suggestion of Grigor Sargsyan, we use arguments as in Theorem 9 from lecture III.5 to show that this partition relation cannot […]

6. […] also showed that cannot be replaced with in this result. And regarding Theorem 1 from last lecture, one can also prove a more general (non-topological) version: Theorem 4 (-Dushnik-Miller) Let be […]