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.

This entry was posted on Monday, April 6th, 2009 at 12:19 am 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 (3)

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

April 9, 2009 at 4:52 pm

[…] I want to present some significant strengthenings of the results above. The results from last lecture exploit the fact that a great deal of coding can be carried out with infinitely many coordinates. […]

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

April 21, 2009 at 11:33 pm

[…] are no embeddings 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 assume there is an […]

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

May 7, 2009 at 6:58 am

[…] I also want to give an update on the topics discussed in lecture III.3. […]

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

August 31, 2012 at 12:25 pm

[…] I also want to give an update on the topics discussed in lecture III.3. […]

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

September 10, 2012 at 11:49 am

[…] are no embeddings 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 assume there is an […]

Reply
580 -Partition calculus (4) | A kind of library says:

September 25, 2017 at 7:07 am

[…] I want to present some significant strengthenings of the results above. The results from last lecture exploit the fact that a great deal of coding can be carried out with infinitely many coordinates. […]

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