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<x_1<x_0,} 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.

Read the rest of this entry »

Advertisement

9 Comments | 580: Topics in set theory | Tagged: , , , , , , | Permalink
Posted by andrescaicedo