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<n_\gamma)}$ 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<n.}$

We claim that ${S}$ is 0-homogeneous: If ${\gamma_0<\gamma_1}$ are in ${S}$ then ${f''[\{\epsilon_i\colon i<n\}\cup\{\gamma_j\}]^2=1}$ for ${j=0,1,}$ so if ${f(\gamma_0,\gamma_1)=1,}$ then ${\{\epsilon_i\colon i<n\}\cup \{\gamma_0,\gamma_1\}}$ 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:

${\kappa}$ is Jónsson.

${\kappa\rightarrow[\kappa]^{<\omega}_\kappa.}$

Any structure for a countable first order language with domain of size ${\kappa}$ admits a proper elementary substructure with domain of size ${\kappa.}$

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

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

There is some cardinal ${\rho<\kappa}$ such that ${\kappa\rightarrow[\kappa]^{<\omega}_{\rho,<\rho}.}$

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),<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<j(\nu),}$ contradiction.

By elementarity, it follows that ${\kappa\rightarrow[\kappa]^{<\omega}_{j(\nu),<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<h(\alpha).}$ 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:

${\kappa\rightarrow[\mu]^{<\omega}_{\lambda,<\nu}.}$

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)<f_\alpha(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<f(\gamma))$
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<f(\gamma))}$ 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<j(\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.

This entry was posted on Tuesday, April 21st, 2009 at 11:32 pm and is filed under 580: Topics in 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.

6 Responses to 580 -Partition calculus (5)

580 -Partition calculus (6) « Teaching page says:

April 24, 2009 at 12:13 pm

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

Reply
580 -Partition calculus (7) « Teaching page says:

May 7, 2009 at 6:58 am

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

Reply
Luminy – Coda « Teaching blog says:

October 27, 2010 at 5:12 pm

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

Reply
Luminy – Coda « A kind of library says:

August 27, 2012 at 1:49 pm

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

Reply
580 -Partition calculus (7) « A kind of library says:

August 31, 2012 at 12:25 pm

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

Reply
580 -Partition calculus (6) « A kind of library says:

September 7, 2012 at 12:28 pm

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

Reply

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library