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}


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),<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:

  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)<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


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.


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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: