## 580 -Partition calculus (2)

April 1, 2009

1. Infinite exponents

Last lecture we showed that ${\omega\rightarrow(\omega)^m_n}$ for any ${m,n<\omega.}$ Later, we will see that for any ${\lambda,\rho}$ and any ${m<\omega}$ there is ${\kappa}$ such that ${\kappa\rightarrow(\lambda)^m_\rho.}$ On the other hand (recall we are assuming choice), there are no nontrivial positive partition relations ${\kappa\rightarrow(\lambda_i)^\tau_{i<\rho}}$ with ${\tau}$ infinite.

(To avoid vacuously true statements, we are always assuming implicitly that ${\kappa\rightarrow(\lambda_i)^\tau_{i<\rho}}$ requires ${\kappa\ge\lambda_i\ge\tau}$ for at least one ${i<\rho.}$)

Theorem 1 (${\mbox{Erd\H os}}$-Rado) For all ${\kappa}$ and all infinite ${\tau,}$ ${\kappa\not\rightarrow(\tau)^\tau.}$

Proof: It is enough to show that ${\kappa\not\rightarrow(\aleph_0)^{\aleph_0}.}$ In effect, if ${\kappa\rightarrow(\tau)^\tau}$ holds and ${\tau>\aleph_0,}$ we may assume that ${\kappa>\tau}$ is regular, so any countable subset ${X}$ of ${\kappa}$ is bounded, and the ordinal ${\sup(X)+\tau}$ is still strictly below ${\kappa.}$

For ${x\in[\kappa]^\tau,}$ let ${{}_\omega x}$ denote the subset of ${x}$ consisting of its first ${\omega}$ many members.

Now, given ${f:[\kappa]^{\aleph_0}\rightarrow2,}$ let ${g:[\kappa]^\tau\rightarrow2}$ be the function ${g(x)=f({}_\omega x).}$ If ${H}$ is homogeneous for ${g}$ and of size ${\tau,}$ then ${{}_\omega H}$ is homogeneous for ${f.}$ In effect, let ${H'=H\setminus{}_\omega H,}$ so ${|H'|=\tau.}$ If ${x\in[{}_\omega H]^{\aleph_0},}$ then ${f(x)=g(x\cup H')=g(H),}$ by homogeneity of ${H.}$

This shows that ${\kappa\rightarrow(\tau)^\tau}$ for ${\tau}$ infinite implies that there is some ${\kappa'}$ such that ${\kappa'\rightarrow(\aleph_0)^{\aleph_0},}$ so it is enough to show that the latter never holds. In fact, we cannot even have ${\kappa\rightarrow(\omega)^\omega.}$ (Recall our convention that ${\omega}$ denotes the order type and ${\aleph_0}$ the size.)

For this, let ${\kappa}$ be an arbitrary infinite cardinal, and let ${<}$ be a well-ordering of ${[\kappa]^\omega.}$ Define ${f:[\kappa]^\omega\rightarrow 2}$ by ${f(s)=0}$ iff ${s}$ is the ${<}$-least member of ${[s]^\omega,}$ and ${f(s)=1}$ otherwise.

If ${x\in[\kappa]^\omega}$ is homogeneous for ${f}$ and ${y}$ is the ${<}$-least member of ${[x]^\omega,}$ then ${f(y)=0,}$ so ${x}$ is ${0}$-homogeneous. Now consider any infinite sequence ${x_0\subsetneq x_1 \subsetneq\dots\subseteq x}$ of infinite subsets of ${x.}$ Since ${f(x_n)=0}$ for all ${n,}$ we must have that ${\dots contradicting that ${<}$ is a well-order. $\Box$

In the presence of the axiom of choice, Theorem 1 completely settles the question of what infinite exponent partition relations hold. Without choice, the situation is different.