## 580 -Partition calculus (3)

1. Infinitary Jónsson algebras

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

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

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

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

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

Proof: It is enough to show that ${\lambda\not\rightarrow[\lambda]^\omega_\lambda}$ for all infinite cardinals ${\lambda.}$

Define a version of the equivalence relation ${E_0}$ on ${[\lambda]^\omega}$ by setting ${x\sim y}$ iff there is some ${\alpha<\sup x}$ such that ${x\setminus\alpha=y\setminus\alpha.}$ Choose a representative ${\pi_\tau}$ from each ${\sim}$-equivalence class ${\tau.}$ For ${x\in[\lambda]^\omega}$ let ${\tau=[x]_\sim}$ and let ${\alpha_x\in \pi_\tau}$ be least such that ${\pi_\tau\setminus(\alpha_x+1)=x\setminus(\alpha_x+1).}$

(Note that ${\alpha_x}$ needs not be in ${x,}$ and that it needs not be the least ${\alpha}$ such that ${\pi_\tau\setminus(\alpha+1)=x\setminus(\alpha+1).}$)

Consider the function ${f(x)=\alpha_x.}$ Although ${f}$ may fail to be ${\omega}$-Jónsson, we claim that it has the following property: There is an ${A\in[\lambda]^\lambda}$ such that for any ${B\in[A]^\lambda,}$ ${f''[B]^\omega\supseteq A.}$ It is obvious one can now use ${f}$ and a bijection between ${A}$ and ${\lambda}$ to define an ${\omega}$-Jónsson function for ${\lambda.}$

To see the claim, assume otherwise and use this to define recursively a sequence ${(A_n,\alpha_n:n<\omega)}$ as follows:

• ${A_0=\lambda.}$ Pick ${A_1\in[\lambda]^\lambda}$ such that there is some ${\alpha_0\in \lambda\setminus f''[A_1]^\omega.}$
• Given ${A_{n+1}}$ (of size ${\lambda}$) and ${\alpha_n,}$ let ${A_{n+2}\in[A_{n+1}\setminus(\alpha_n+1)]^\lambda}$ be such that there is some ${\alpha_{n+1}\in (A_{n+1}\setminus(\alpha_n+1))\setminus f''[A_{n+2}]^\omega.}$

It follows that ${(\alpha_n:n<\omega)}$ is strictly increasing, ${(A_n:n<\omega)}$ is strictly decreasing, and for all ${k<\omega,}$ ${\{\alpha_n:n\ge k\}\in[A_k]^\omega.}$

Now let ${y=\{\alpha_n\colon n\in\omega\}}$ and ${\tau=[y]_\sim.}$ Let ${\alpha\in\lambda}$ be least such that

$\displaystyle \pi_\tau\setminus\alpha=y\setminus\alpha=\{\alpha_n\colon n\ge m\}$

for some ${m\in\omega,}$ and fix such ${m.}$ Note that ${\{\alpha_n\colon n>m\}\sim \pi_\tau}$ and ${\alpha_m\in \pi_\tau,}$ so ${f(\{\alpha_n:n>m\})=\alpha_m.}$ It follows that ${\alpha_m\in f''[A_{m+1}]^\omega,}$ contradiction. $\Box$

In a few particular cases, direct proofs are also possible, and I discuss a few below, before exploring generalizations.

I begin with a result of Solovay. We need a preliminary lemma, generalizing Ulam’s Theorem 13 from lecture II.5 that stationary subsets of ${\kappa^+}$ can be split into ${\kappa^+}$ many stationary subsets:

Theorem 3 (Solovay) Any stationary subset of a regular cardinal ${\kappa}$ can be split into ${\kappa}$ many disjoint stationary sets.

Proof: Let ${ \kappa}$ be regular and ${ S\subseteq\kappa}$ be stationary, and set

$\displaystyle T=\{\alpha\in S:{\rm cf}(\alpha)=\omega$ or $\displaystyle ({\rm cf}(\alpha)>\omega\mbox{ and }S\cap\alpha \mbox{ is not stationary in }\alpha)\}.$

We claim that ${ T}$ is stationary. To see this, let ${ C}$ be an arbitrary club subset of ${ \kappa.}$ Then the set ${ C'}$ of limit points of ${ C}$ is also club (and a subset of ${ C}$), so it meets ${ S,}$ since ${ S}$ is stationary. Let ${ \alpha=\min(C'\cap S).}$ Then either ${ \alpha}$ has cofinality ${ \omega,}$ so it is in ${ T,}$ or else it has uncountable cofinality. In that case, notice that since ${ \alpha\in C',}$ it is a limit of points in ${ C,}$ so ${ C\cap\alpha}$ is club in ${ \alpha,}$ and therefore ${ (C\cap\alpha)'=C'\cap\alpha}$ is also club in ${ \alpha.}$ Were ${ S\cap\alpha}$ stationary in ${ \alpha,}$ it would meet ${ C'\cap\alpha,}$ and this would contradict the minimality of ${ \alpha.}$ It follows that ${ \alpha\in T\cap C,}$ and therefore ${ T}$ is stationary, as wanted.

Let now ${ \alpha}$ be an arbitrary point of ${ T.}$ If ${ \alpha}$ has cofinality ${ \omega,}$ it is the limit of an ${ \omega}$-sequence of successor ordinals. Let ${ f_\alpha}$ be the increasing enumeration of this sequence, and notice that ${ {\rm ran}(f_\alpha)\cap T=\emptyset,}$ since all ordinals in ${ T}$ are limit ordinals. Suppose now that ${ \alpha}$ has uncountable cofinality, so ${ S\cap\alpha}$ is not stationary in ${ \alpha.}$ Since ${ T\subseteq S,}$ it follows that ${ T\cap\alpha}$ is not stationary either, so there is a club subset of ${ \alpha}$ disjoint from ${ T,}$ and let ${ f_{\alpha}}$ be the increasing enumeration of this club set so, again, ${{\rm ran}(f_\alpha)\cap T=\emptyset.}$

With the sequences ${ f_\alpha}$ defined as above for all ${ \alpha\in T,}$ we now claim that there is some ${ \xi<\kappa}$ such that for all ${ \eta<\kappa,}$ the set

$\displaystyle T^\xi_\eta=\{\alpha\in T:\xi\in{\rm dom}(f_\alpha)\mbox{ and } f_\alpha(\xi)\ge\eta\}$

is stationary. The proof is by contradiction, assuming that no ${ \xi<\kappa}$ is as wanted.

It follows then that for all ${ \xi<\kappa}$ there is some ${\eta(\xi)<\kappa}$ such that the set ${T_{\eta(\xi)}^\xi}$ as above is non-stationary. Fix a club ${ C_\xi}$ disjoint from it, and let ${ C}$ be the club ${ C=\bigtriangleup_\xi C_\xi.}$ Let ${ D=C\cap E,}$ where ${ E=\{\alpha<\kappa:\eta''\alpha\subseteq\alpha\}.}$ Notice that ${ E}$ is club, and so is ${ D.}$ We claim that ${ |D\cap T|\le 1.}$ This contradicts that ${ T}$ is stationary, and therefore there must be a ${ \xi<\kappa}$ as claimed.

Suppose then that ${ \gamma<\alpha}$ are points in ${ D\cap T.}$ Since ${ \alpha\in D,}$ then ${ \alpha\in C,}$ so ${ \alpha\in C_\xi}$ (hence, ${ \alpha\notin T^\xi_{\eta(\xi)}}$) for all ${ \xi<\alpha.}$ We claim that ${ \gamma\in{\rm dom}(f_\alpha).}$ To see this, let ${ \xi\in\gamma\cap{\rm dom}(f_\alpha).}$ Then (by definition of ${ T^\xi_{\eta(\xi)}}$), ${ f_\alpha(\xi)<\eta(\xi).}$ Since ${ \gamma\in D,}$ then ${ \gamma\in E}$ and, since ${ \xi<\gamma,}$ then ${ \eta(\xi)<\gamma.}$ It follows that ${ \sup{\rm ran}(f_\alpha\upharpoonright\gamma)\le\gamma<\alpha.}$ Since ${ f_\alpha}$ is cofinal in ${ \alpha,}$ we must necessarily have ${ \gamma\in{\rm dom}(f_\alpha).}$

Since ${ f_\alpha}$ is continuous and ${ \gamma}$ is a limit ordinal (since it is in ${T}$), it follows that ${ f_\alpha(\gamma)=\sup_{\xi<\gamma}f_\alpha(\xi)\le\gamma.}$ But, since ${ f_\alpha}$ is increasing, then also ${ f_\alpha(\gamma)\ge\gamma.}$ Hence, ${ f_\alpha(\gamma)=\gamma.}$ We have finally reached a contradiction, because ${ \gamma\in T,}$ but the sequence ${ f_\alpha}$ was chosen so its range is disjoint from ${ T.}$ This proves that ${ |D\cap T|\le 1,}$ which of course is a contradiction since ${ T}$ is stationary. It follows that indeed there is some ${ \xi<\kappa}$ such that all the sets ${ T_\eta=T_\eta^\xi}$ are stationary for all ${\eta<\kappa.}$

Now let ${ f:T\rightarrow\kappa}$ be the map

$\displaystyle f(\alpha)=\left\{\begin{array}{cl}f_\alpha(\xi)&\mbox{ if }\xi\in{\rm dom}(f_\alpha),\\ 0&\mbox{ otherwise.}\end{array}\right.$

Clearly, ${ f}$ is regressive. Also, from the definition of ${ f,}$ it follows that

$\displaystyle \{\alpha\in T:f(\alpha)\ge\eta\}=T_\eta$

for all ${ \eta<\kappa,}$ so ${ f}$ is unbounded in ${ \kappa,}$ since each ${ T_\eta}$ is in fact stationary, as we showed above. Given any ${ \eta<\kappa,}$ since ${ f\upharpoonright T_\eta}$ is regressive, there is some ${ \gamma}$ (necessarily, ${ \gamma\ge\eta}$) such that ${ \{\alpha\in T_\eta:f(\alpha)=\gamma\}}$ is stationary, by Fodor’s lemma. A simple induction allows us to define a strictly increasing sequence ${ (\gamma_\eta:\eta<\kappa)}$ such that ${ \{\alpha\in T_{\gamma_\eta+1}:f(\alpha)=\gamma_{\eta+1}\}}$ is stationary for all ${ \eta.}$ Notice that these ${ \kappa}$ many subsets of ${ T}$ (hence, of ${ S}$) so defined are all disjoint. By adding to one of them whatever (if anything) remains of ${ S}$ after removing all these sets, we obtain a partition of ${ S}$ into ${ \kappa}$ many disjoint stationary subsets, as wanted. $\Box$

Theorem 4 (Solovay) Let ${\mu}$ be a regular uncountable cardinal. Then ${\mu\not\rightarrow[\mu]^\omega_\mu.}$ In fact, for any infinite regular ${\kappa<\mu,}$ ${\mu\not\rightarrow[\mu]^\kappa_\mu,}$ even if we consider ${\kappa}$ as an order type.

Proof: Let ${(S_\alpha\colon\alpha<\mu)}$ be a partition of ${S^\mu_\kappa}$ into stationary sets, and let ${f:[\mu]^\kappa\rightarrow\mu}$ be given by ${f(s)=}$ the unique ${\alpha}$ such that ${\sup(s)\in S_\alpha.}$ Then ${f}$ is as required, i.e., ${f''[Y]^\kappa=\mu}$ for any ${Y\in[\mu]^\mu.}$

To see this, let ${Y\in[\mu]^\mu}$ and set ${Y^*=\{\sup(s)\colon s\in[Y]^\kappa\}.}$ Then ${Y^*}$ is a ${\kappa}$-club subset of ${\mu}$ so, for all ${\alpha<\mu,}$ ${Y^*\cap S_\alpha\ne0.}$ Hence ${f''[Y]^\kappa=\mu.}$ $\Box$

For ${\mu=\omega}$ we can in fact show something stronger:

Theorem 5 (${\mbox{Erd\H os}}$-Hajnal) For any infinite cardinal ${\kappa,}$ ${\kappa\not\rightarrow[\kappa]^\kappa_{2^\kappa},}$ i.e., there is a map ${f:[\kappa]^\kappa\rightarrow2^\kappa}$ such that for any ${Y\in[\kappa]^\kappa,}$ ${f''[Y]^\kappa=2^\kappa.}$

Proof: Let ${\vec X=(X_\xi\colon\xi<2^\kappa)}$ enumerate ${[\kappa]^\kappa}$ in such a way that each set is listed ${2^\kappa}$ many times. Inductively define ${(Y_\xi\colon\xi<2^\kappa)}$ so that ${Y_\xi\in[X_\xi]^\kappa}$ and ${Y_\xi\ne Y_\eta}$ for all ${\eta<\xi<2^\kappa.}$

Let ${f(Y_\xi)={\rm ot}(\{\alpha<\xi\colon X_\alpha=X_\xi\}),}$ and set ${f(Y)=0}$ if ${Y\ne Y_\xi}$ for all ${\xi.}$

We claim that ${f}$ is as wanted. Because given any ${Y\in[\kappa]^\kappa}$ and ${\eta<2^\kappa,}$ if we let ${X_\gamma}$ be the ${(\eta+1)}$-st occurrence of ${Y}$ in the sequence ${\vec X,}$ then ${f(Y_\gamma)=\eta}$ and ${Y_\gamma\in[Y]^\kappa.}$ $\Box$

This can be generalized thanks to the following strengthening of its core idea.

Lemma 6 (Galvin-Prikry) For every infinite cardinal ${\kappa}$ and every ${S,}$ there is an injective function ${\varphi:[S]^\kappa\times 2^\kappa\rightarrow[S]^\kappa}$ such that ${\varphi(X,\xi)\subseteq X}$ for all ${X\in[S]^\kappa}$ and ${\xi\in2^\kappa.}$ (Here, ${\kappa}$ is treated as a cardinal rather than an order type.)

Proof: If ${|S|\le2^\kappa,}$ as in Theorem 5, a straightforward transfinite induction suffices to find ${\varphi.}$

For general ${S,}$ let ${(S_\alpha:\alpha<\gamma)}$ enumerate ${[S]^\kappa.}$ For ${\alpha<\gamma}$ let ${\varphi_\alpha:[S_\alpha]^\kappa\times2^\kappa\rightarrow[S_\alpha]^\kappa}$ be injective and such that ${\varphi_\alpha(X,\xi)\subseteq X}$ for all ${X\in[S_\alpha]^\kappa}$ and ${\xi\in2^\kappa.}$

Now, given ${\xi\in2^\kappa}$ and ${X\in[S]^\kappa,}$ let ${\alpha(X)}$ be the least ${\alpha}$ such that ${|X\cap S_\alpha|=\kappa,}$ and define

$\displaystyle \varphi(X,\xi)=(X\setminus S_{\alpha(X)})\cup\varphi_{\alpha(X)}(X\cap S_{\alpha(X)},\xi).$

Then ${\varphi(X,\xi)\in[X]^\kappa}$ and ${\alpha(\varphi(X,\xi))=\alpha(X).}$ It follows that if ${\varphi(X,\xi)=\varphi(Y,\eta)=Z,}$ say, then there is an ordinal ${\alpha}$ such that ${\alpha=\alpha(Z)=\alpha(X)=\alpha(Y).}$ Therefore ${Z\setminus S_\alpha=X\setminus S_\alpha=Y\setminus S_\alpha}$ and ${Z\cap S_\alpha=\varphi_\alpha(X\cap S_\alpha,\xi)=\varphi_\alpha(Y\cap S_\alpha,\eta).}$ Since ${\varphi_\alpha}$ is 1-1, we conclude that ${X\cap S_\alpha=Y\cap S_\alpha}$ and ${\xi=\eta.}$ But then ${X=Y}$ as well, and ${\varphi}$ is 1-1. $\Box$

Corollary 7 (Galvin-Prikry) If ${\tau}$ and ${\kappa}$ are cardinals and ${\kappa}$ is infinite, then ${\tau\not\rightarrow[\kappa]^\kappa_{2^\kappa}.}$

Proof: Let ${\varphi:[\tau]^\kappa\times 2^\kappa\rightarrow[\tau]^\kappa}$ be as in Lemma 6 with ${S=\tau.}$ Since ${\varphi}$ is 1-1, we can define ${f:[\tau]^\kappa\rightarrow2^\kappa}$ so that ${f(\varphi(X,\xi))=\xi}$ for all ${X\in[\tau]^\kappa}$ and ${\xi\in2^\kappa.}$ But then ${f''[X]^\kappa=2^\kappa.}$ $\Box$

The same idea gives us ${\omega}$-Jónsson functions for some singular cardinals, as shown by Kunen in this argument from 1971.

Theorem 8 Let ${{\rm cf}(\lambda)=\omega}$ for ${\lambda}$ singular strong limit. Then ${\lambda\not\rightarrow[\lambda]^\omega_\lambda.}$

Proof: Let ${\{(X_\alpha,\gamma_\alpha)\colon\alpha<2^\lambda\}}$ enumerate ${[\lambda]^\lambda\times\lambda.}$ By transfinite recursion define ${(s_\alpha\colon\alpha<2^\lambda)}$ such that ${s_\alpha\in[X_\alpha]^\omega\setminus\{s_\beta\colon\beta<\alpha\}}$ for all ${\alpha.}$ This is possible, because there are ${\lambda^{\aleph_0}}$ elements of ${[X_\alpha]^\omega}$ and ${\alpha<2^\lambda=\lambda^{\aleph_0}.}$ Now let ${f:[\lambda]^\omega\rightarrow\lambda}$ be such that ${f(s_\alpha)=\gamma_\alpha}$ for ${\alpha<2^\lambda}$ and ${f(s)=0}$ if ${s}$ is not an ${s_\alpha.}$

To see that ${f}$ is ${\omega}$-Jónsson, let ${X\in[\lambda]^\lambda.}$ Let ${I=\{\alpha<2^\lambda:X_\alpha=X\},}$ so

$\displaystyle \lambda=\{\gamma_\alpha: \alpha\in I\}=\{f(s_\alpha):\alpha\in I\}\subseteq f''[X]^\omega.$

The result follows. $\Box$

This gives us another proof of Kunen’s inconsistency Theorem 13 from lectures II.10 and II.12.

Corollary 9 (Kunen) If ${j:V\rightarrow M}$ is elementary, then ${V\ne M.}$

Proof: Argue by contradiction. As usual, let ${\lambda}$ be the first fixed point of ${j}$ past its critical point ${\kappa.}$ If ${V=M,}$ then elementarity implies that ${j^n(\kappa)}$ is a strong limit cardinal for all ${n<\omega,}$ so ${\lambda}$ is a singular strong limit cardinal of cofinality ${\omega}$ and, by Theorem 8, there is an ${\omega}$-Jónsson function ${f:[\lambda]^\omega\rightarrow\lambda.}$ If ${A=j''\lambda\in M,}$ then by elementarity there is some ${s\in[A]^\omega\cap M}$ such that ${j(f)(s)=\kappa.}$ But then ${s=j''t=j(t)}$ for some ${t\in[\lambda]^\omega,}$ and ${\kappa=j(f(t))}$ is in the range of ${j.}$ Of course, ${\kappa}$ cannot then be the critical point of ${j,}$ and we are done. $\Box$

For ${\kappa=\aleph_0,}$ one can further strengthen Corollary 7 as follows.

Theorem 10 (Galvin-Prikry) For any set ${A}$ there is a function ${f:[A]^{\aleph_0}\rightarrow2^\omega}$ such that whenever ${X,Y\in[A]^{\aleph_0}}$ and ${|X\bigtriangleup Y|<\aleph_0,}$ then ${f(X)=f(Y);}$ and for any ${\omega}$-sequence ${(P_0,P_1,\dots)}$ of pairwise disjoint sets in ${[A]^2,}$ and any ${t\in 2^\omega,}$ there is a sequence ${(x_0,x_1,\dots)}$ with ${x_n\in P_n}$ for all ${n,}$ and ${f(\{x_n:n\in\omega\})=t.}$

Proof: In fact, we build ${f:[A]^{\aleph_0}\rightarrow2^\omega}$ so that

• ${f(X)}$ only depends on ${X/{\mathcal P}_\omega(A)}$ for any ${X\in[A]^{\aleph_0},}$ and
• Whenever ${(P_0,Q_0,P_1,Q_1,\dots)}$ is a sequence of pairwise disjoint finite subsets of ${A}$ such that ${\bigcup_n(P_n\cup Q_n)}$ is infinite, and ${t\in2^\omega,}$ then there is a sequence ${(R_0,R_1,\dots)}$ with ${R_n\in\{P_n,Q_n\}}$ for all ${n,}$ ${\bigcup_n R_n}$ is infinite, and ${f(\bigcup_n R_n)=t.}$

To do this, use Zorn’s lemma to find a maximal sequence ${(A_\beta:\beta<\alpha)}$ of pairwise almost disjoint elements of ${[A]^{\aleph_0}.}$ For each ${A_\beta,}$ being countable, it is easy to find a function ${f_\beta:[A_\beta]^{\aleph_0}\rightarrow2^\omega}$ satisfying the two conditions above with ${A_\beta}$ in place of ${A.}$

Now, given ${X\in[A]^{\aleph_0},}$ set ${f(X)=f_\beta(X\cap A_\beta),}$ where ${\beta}$ is least such that ${X\cap A_\beta}$ is infinite. It is now easy to check that ${f}$ is as wanted. $\Box$

A variant of Lemma 6 gives us the following:

Lemma 11 (Galvin-Prikry) Given an infinite cardinal ${\kappa}$ and a set ${S,}$ there is an injective function ${\varphi:[S]^\kappa\times\kappa\rightarrow[S]^\kappa}$ such that ${\varphi(X,\xi)\subseteq X}$ and ${X\setminus\varphi(X,\xi)}$ is a singleton for all ${X\in[S]^\kappa}$ and ${\xi\in\kappa.}$

Proof: It suffices to argue when ${|S|=\kappa,}$ and the general case is then handled as in the proof of Lemma 6.

Let ${(C_i:i<\tau)}$ be an injective enumeration of ${[S]^\kappa/{\mathcal P}_\omega(S).}$ Note that ${|C_i|=\kappa}$ for all ${i<\tau.}$ One can easily find ${\varphi_i:C_i\times\kappa\rightarrow C_i}$ such that ${\varphi_i}$ is injective, ${\varphi_i(X,\xi)\subseteq X,}$ and ${X\setminus\varphi_i(X,\xi)}$ is a singleton for all ${X\in C_i.}$

We can then take ${\varphi=\bigcup_i\varphi_i.}$ $\Box$

Corollary 12 For all infinite cardinals ${\kappa}$ and all sets ${S,}$ there is a function ${f:[S]^\kappa\rightarrow\kappa}$ such that ${\{f(X\setminus\{x\}):x\in X\}=\kappa}$ for al ${X\in[S]^\kappa.}$

Proof: With ${\varphi}$ as above, let ${f:[S]^\kappa\rightarrow\kappa}$ satisfy ${f(\varphi(X,\xi))=\xi}$ for all ${X\in[S]^\kappa}$ and ${\xi\in\kappa.}$ $\Box$

We now proceed to show that one can `lift’ exponents and relax the requirements a bit, while still obtaining infinitary Jónsson algebras. We will repeatedly use the following lemma.

Lemma 13 Let ${\kappa}$ be an infinite cardinal and let ${S}$ and ${W}$ be sets, with ${W\ne\emptyset.}$ Given ${F:[S]^\kappa\rightarrow[W]^{\le2^\kappa},}$ there is a function ${f:[S]^\kappa\rightarrow W}$ such that ${F(X)\subseteq f''[X]^\kappa}$ for all ${X\in[S]^\kappa.}$

Proof: Use Lemma 6 to find an injective ${\varphi:[S]^\kappa\times 2^\kappa\rightarrow[S]^\kappa}$ such that ${\varphi(X,\xi)\subseteq X}$ for all ${X\in[S]^\kappa}$ and ${\xi\in 2^\kappa.}$

Choose injections ${h_X:F(X)\rightarrow2^\kappa}$ for all ${X\in[S]^\kappa.}$

Now define ${f:[S]^\kappa\rightarrow W}$ so that ${f(\varphi(X,h_X(w)))=w}$ for all ${X\in[S]^\kappa}$ and ${w\in F(X).}$ $\Box$

Corollary 14 (Hajnal) If ${\kappa_0\le\kappa\le\lambda}$ and ${\kappa}$ is infinite, then ${\tau\not\rightarrow[\lambda]^{\kappa_0}_\delta}$ implies ${\tau\not\rightarrow[\lambda]^\kappa_\delta.}$

Proof: Let ${g:[\tau]^{\kappa_0}\rightarrow\delta}$ witness ${\tau\not\rightarrow[\lambda]^{\kappa_0}_\delta.}$

Define ${F:[\tau]^\kappa\rightarrow[\delta]^{\le2^\kappa}}$ as follows: Given ${X\in[\tau]^\kappa,}$ let ${F(X)=g''[X]^{\kappa_0}.}$ By Lemma 13, we can then find ${f:[\tau]^\kappa\rightarrow\delta}$ such that ${g''[X]^{\kappa_0}\subseteq f''[X]^\kappa}$ for all ${X\in[\tau]^\kappa.}$ But ${\kappa\ge\kappa_0,}$ so in fact ${g''[A]^{\kappa_0}\subseteq f''[A]^\kappa}$ for all ${A\subseteq\tau}$ with ${|A|\ge\kappa.}$

Now consider ${A\in[\tau]^\lambda.}$ It follows that ${\delta=f''[A]^\kappa,}$ so ${f}$ witnesses ${\tau\not\rightarrow[\lambda]^\kappa_\delta.}$ $\Box$

Recall that ${\tau\rightarrow[\lambda]^\kappa_{\delta,<\rho}}$ means that whenever ${f:[\tau]^\kappa\rightarrow\delta,}$ there is some ${A\in[\tau]^\lambda}$ and ${|f''[A]^\kappa|<\rho.}$

Theorem 15 (Galvin-Prikry) If ${\kappa}$ is infinite, then ${\tau\rightarrow[\lambda]^\kappa_\delta}$ iff ${\tau\rightarrow[\lambda]^\kappa_{\delta,<\delta}.}$

Proof: Clearly, ${\tau\rightarrow[\lambda]^\kappa_{\delta,<\delta}}$ implies ${\tau\rightarrow[\lambda]^\kappa_{\delta}.}$

Suppose now that ${\tau\not\rightarrow[\lambda]^\kappa_{\delta,<\delta},}$ and let ${g:[\tau]^\kappa\rightarrow\delta}$ be a witness. We need to show that ${\tau\not\rightarrow[\lambda]^\kappa_{\delta}.}$ We may assume that ${\lambda\ge\kappa}$ and that ${\delta>2^\kappa,}$ by Corollary 7.

By Theorem 2 and Corollary 14, ${\delta\not\rightarrow[\delta]^\kappa_\delta.}$ Let ${h:[\delta]^\kappa\rightarrow\delta}$ be a witness, and define ${F:[\tau]^\kappa\rightarrow[\delta]^{\le2^\kappa}}$ by ${F(X)=h''[g''[X]^\kappa]^\kappa}$ for all ${X\in[\tau]^\kappa.}$

Use Lemma 13 to find a function ${f:[\tau]^\kappa\rightarrow\delta}$ such that ${h''[g''[X]^\kappa]^\kappa\subseteq f''[X]^\kappa}$ for all ${X\in[\tau]^\kappa.}$ Hence the same holds for all ${X\in[\tau]^\lambda,}$ and since ${|g''[X]^\kappa|=\delta}$ for all such ${X,}$ then ${h''[g''[X]^\kappa]^\kappa=\delta.}$ It follows that ${f}$ witnesses ${\tau\not\rightarrow[\lambda]^\kappa_\delta.}$ $\Box$

Corollary 16 If ${\lambda\ge\kappa\ge\aleph_0,}$ then ${\lambda^\kappa\not\rightarrow[\lambda]^\kappa_{\lambda^\kappa}.}$

Proof: For any ${\tau,}$ any injective ${f:[\tau]^\kappa\rightarrow\tau^\kappa}$ witnesses ${\tau\not\rightarrow[\lambda]^\kappa_{\tau^\kappa,<\lambda^\kappa} .}$ Take ${\tau=\lambda^\kappa,}$ and apply Theorem 15. $\Box$

Theorem 17 (Galvin-Prikry) If ${\kappa}$ is infinite, ${\tau\not\rightarrow[\lambda]^\kappa_{\delta,<\epsilon},}$ and ${\delta\not\rightarrow[\epsilon]^\kappa_{\pi,<\sigma},}$ then also ${\tau\not\rightarrow[\lambda]^\kappa_{\pi,<\sigma}.}$

Proof: Let ${g:[\tau]^\kappa\rightarrow\delta}$ witness ${\tau\not\rightarrow[\lambda]^\kappa_{\delta,<\epsilon},}$ and ${h:[\delta]^\kappa\rightarrow\pi}$ witness ${\delta\not\rightarrow[\epsilon]^\kappa_{\pi,<\sigma}.}$

Let ${F:[\tau]^\kappa\rightarrow[\pi]^{\le2^\kappa}}$ be given by ${F(X)=h''[g''[X]^\kappa]^\kappa}$ for all ${X\in[\tau]^\kappa,}$ and find ${f:[\tau]^\kappa\rightarrow\pi}$ with ${F(X)\subseteq f''[X]^\kappa}$ for all such ${X.}$ As before, we also have ${h''[g''[X]^\kappa]^\kappa\subseteq f''[X]^\kappa}$ for all ${X\in[\tau]^\lambda.}$

But, for any such ${X,}$ ${|g''[X]^\kappa|\ge\epsilon}$ and therefore ${|h''[g''[X]^\kappa]^\kappa|\ge\sigma,}$ and it follows that ${f}$ witnesses ${\tau\not\rightarrow[\lambda]^\kappa_{\pi,<\sigma}.}$ $\Box$

Galvin and Prikry point out that one could define a relation ${\ge_\kappa}$ by ${(\tau,\lambda)\ge_\kappa(\delta,\epsilon)}$ iff ${\tau\not\rightarrow[\lambda]^\kappa_{\delta,<\epsilon},}$ and then Theorem 17 could be read as saying that ${\ge_\kappa}$ is transitive.

Corollary 18 If ${\lambda\ge\kappa\ge\aleph_0}$ and ${\tau^\kappa\not\rightarrow[\lambda^\kappa]^\kappa_{\delta,<\epsilon}}$ then, in fact, ${\tau^\kappa\not\rightarrow[\lambda]^\kappa_{\delta,<\epsilon}.}$

Proof: As mentioned in the proof of Corollary 14, one always has ${\rho\not\rightarrow[\lambda]^\kappa_{\rho^\kappa,<\lambda^\kappa} .}$ In particular, ${\tau^\kappa\not\rightarrow[\lambda]^\kappa_{\tau^\kappa,<\lambda^\kappa}.}$ By transitivity, ${\tau^\kappa\not\rightarrow[\lambda]^\kappa_{\delta,<\epsilon}.}$ $\Box$

Corollary 19 If ${\kappa\ge\aleph_0}$ and ${\tau\not\rightarrow[\lambda]^\kappa_{\delta,<\epsilon},}$ then ${\tau\not\rightarrow[\lambda]^\kappa_{\delta^\kappa,<\epsilon^\kappa}.}$

Proof: We may of course assume ${\lambda\ge\kappa}$ and ${\delta>1.}$ By Corollary 7, we may also assume that ${\epsilon>2^\kappa.}$ Clearly, ${\delta\not\rightarrow[\epsilon]^\kappa_{\delta^\kappa,<\epsilon^\kappa}.}$ By transitivity, ${\tau\not\rightarrow[\lambda]^\kappa_{\delta^\kappa,<\epsilon^\kappa}.}$ $\Box$

Corollary 20 For any infinite cardinal ${\kappa,}$ ${\tau\rightarrow[\lambda]^\kappa_\delta}$ iff ${\tau\rightarrow[\lambda]^\kappa_{\delta^\kappa}.}$

Proof: By Theorem 15 and Corollary 19, ${\tau\not\rightarrow[\lambda]^\kappa_\delta}$ iff ${\tau\not\rightarrow[\lambda]^\kappa_{\delta,<\delta},}$ which implies ${\tau\not\rightarrow[\lambda]^\kappa_{\delta^\kappa,<\delta^\kappa}}$ or, equivalently, ${\tau\not\rightarrow[\lambda]^\kappa_{\delta^\kappa}.}$

The reverse implication is clear. $\Box$

Definition 21 (Kunen) For ${\lambda}$ an infinite cardinal, let ${P(\lambda)}$ be the statement that for all functions ${f:[\lambda]^{\aleph_0}\rightarrow\lambda}$ there is an infinite set ${A\subseteq\lambda}$ such that ${|A|\not\subseteq f''[A]^{\aleph_0}.}$

Kunen showed that ${P(\lambda)}$ implies that ${\lambda\ge{\mathfrak c}^{++}}$ and that the assertion that ${P(\lambda)}$ holds for some ${\lambda}$ is of large cardinal character, in the sense that it implies that for all ${\alpha<\omega_1}$ there is an inner model with at least (order type) ${\alpha}$ many measurable cardinals.

Corollary 22 If ${\lambda\ge\kappa\ge\aleph_0}$ and ${\tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa},}$ then ${P(\tau)}$ holds.

Proof: By Corollaries 14 and 20, ${\tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa}}$ is equivalent to ${\tau\rightarrow[\lambda]^\kappa_\lambda,}$ which implies ${\tau\rightarrow[\lambda]^{\aleph_0}_\lambda,}$ which implies ${P(\tau)}$. $\Box$

It is a question of ${\mbox{Erd\H os}}$ and Hajnal whether ${\tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa}}$ can ever hold. As far as I know, this is still open (I would be glad to hear of any updates). On the other hand, the existence of some ${\lambda}$ such that ${P(\lambda)}$ is consistent.

Theorem 23 (Kunen) If ${\kappa}$ is a ${\kappa^+}$-supercompact cardinal, then ${P(\kappa^+).}$

Proof: Fix an elementary ${j:V\rightarrow M}$ with critical point ${\kappa}$ such that ${{}^{\kappa^+}M\subseteq M,}$ and let ${A=j''\kappa^+.}$

Let ${F:[\kappa^+]^{\aleph_0}\rightarrow\kappa^+.}$ As in the proof of Corollary 9, ${\kappa\notin (j(F))''[A]^{\aleph_0}.}$ Also, ${A\subset j(\kappa^+).}$ By elementarity, there is some ${X\subset \kappa^+}$ such that ${|X|\not\subseteq F''[X]^{\aleph_0}.}$ $\Box$

Theorem 24 (Galvin-Prikry) Let ${\kappa}$ and ${\rho}$ be infinite cardinals, with ${\rho}$ singular. Suppose that ${\tau\not\rightarrow[\lambda]^\kappa_\delta}$ for all ${\delta<\rho.}$ Then also ${\tau\not\rightarrow[\lambda]^\kappa_\rho.}$

Proof: Let ${\sigma={\rm cf}(\rho),}$ and fix a strictly increasing sequence ${(\delta_i:i<\sigma)}$ of cardinals cofinal in ${\rho.}$ Let ${g:[\tau]^\kappa\rightarrow\sigma}$ witness ${\tau\not\rightarrow[\lambda]^\kappa_\sigma}$ and for all ${i<\sigma}$ let ${h_i:[\tau]^\kappa\rightarrow\delta_i}$ witness ${\tau\not\rightarrow[\lambda]^\kappa_{\delta_i}.}$

Let ${F:[\tau]^\kappa\rightarrow[\rho]^{\le2^\kappa}}$ be given by

$\displaystyle F(X)=\{h_{g(Y)}(Z):Y,Z\in[X]^\kappa\}$

for all ${X\in[\tau]^\kappa.}$ Let ${f:[\tau]^\kappa\rightarrow\rho}$ be such that ${F(X)\subseteq f''[X]^\kappa}$ for all such ${X.}$ We claim that ${f}$ witnesses ${\tau\not\rightarrow[\lambda]^\kappa_\rho.}$

Let ${A\in[\tau]^\lambda}$ and ${\xi\in\rho.}$ Then there is some ${i\in\sigma}$ with ${\xi\in \delta_i.}$ There must then be some ${Y\in[A]^\kappa}$ such that ${g(Y)=i,}$ and some ${Z\in[A]^\kappa}$ such that ${h_i(X)=\xi,}$ and it follows that ${\xi=h_{g(Y)}(Z)\in F(X)\subseteq f''[X]^\kappa\subseteq f''[A]^\kappa.}$ This shows that ${f''[A]^\kappa=\rho,}$ and we are done. $\Box$

Bibliography

Here are some references consulted while preparing this note:

• Fred Galvin, Karel Prikry, Borel sets and Ramsey’s theorem, The Journal of Symbolic Logic, 38 (2) (Jun., 1973), 193–198.
• Fred Galvin, Karel Prikry, Infinitary Jonsson algebras and partition relations, Algebra Universalis, 6 (1976), 367–376.
• Akihiro Kanamori, The higher infinite, Springer (1994).
• Kenneth Kunen, Elementary embeddings and infinitary combinatorics, The Journal of Symbolic Logic, 36 (3), (Sep., 1971), 407–413.

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