580 -Partition calculus (6)

1. The {\mbox{Erd\H os}}-Rado theorem

Large homogeneous sets (of size {\omega_1} or larger) can be ensured, at the cost of starting with a larger domain. The following famous result was originally shown by {\mbox{Erd\H os}} and Rado using tree arguments (with {\kappa+1} lowered to {\kappa} in the conclusion). We give instead an elementary substructures argument due to Baumgartner, Hajnal and {\mbox{Todor\v cevi\'c},} which proves the stronger version. For {\kappa} a cardinal let {2^{<\kappa}=\sup_{\lambda<\kappa}2^\lambda.}

Theorem 1 ({\mbox{Erd\H os}}-Rado) Let {\kappa} be a regular cardinal and let {\lambda=(2^{<\kappa})^+.} Then

\displaystyle  \lambda\rightarrow(\kappa+1)^2_\mu

for all {\mu<\kappa.}


Proof: Let {\mu<\kappa} and let {f:[\lambda]^2\rightarrow\mu.}

Lemma 2 There is {N\prec H_{\lambda^+}} such that {f\in N,} {|N|=2^{<\kappa},} {[N]^{<\kappa}\subseteq N} and {N\cap\lambda=\alpha<\lambda.}

Proof: Start with any {N_0\prec H_{\lambda^+}} with {f\in N} and {|N|=2^{<\kappa}} and inductively build a continuous chain

\displaystyle  N_0\prec N_1\prec\dots\prec N_\alpha\prec\dots

for {\alpha<\kappa} so that if {|N_\alpha|=2^{<\kappa},} then {\bigcup(N_\alpha\cap\lambda)\subset N_{\alpha+1},} {[N_\alpha]^{<\kappa}\subset N_{\alpha+1}} and {|N_{\alpha+1}|=2^{<\kappa}.} This is possible since {N_\alpha\cap\lambda} is bounded in {\lambda} by regularity of {\lambda} and

\displaystyle  |[N_\alpha]^{<\kappa}|=(2^{<\kappa})^{<\kappa}=2^{<\kappa}.

Let {N=\bigcup_{\alpha<\kappa}N_\alpha.} Then {N} is as required, by regularity of {\kappa.} \Box

Fix {N,\alpha} as in the lemma. Let

\displaystyle  I_\alpha = \{X \subseteq\alpha\colon \exists A\in N\,(\alpha\notin A\mbox{ and }X \subseteq A)\}.

Then {I_\alpha} is a {\kappa}-complete ideal over {\alpha,} i.e.:

  1. {\alpha\notin I_\alpha}: Notice that {\lambda\in N,} since {\lambda} is definable in {H_{\lambda^+}} as the largest cardinal. If {\alpha\subseteq A\in N,} then {\alpha\subseteq\bigcup(A\cap\lambda)\subseteq\bigcup(N\cap\lambda)=\alpha,} so {\alpha\in N} since {\bigcup(A\cap\lambda)\in N.} 
  2. {\emptyset\in I_\alpha}; and {A\subseteq B\in I_\alpha} implies {A\in I_\alpha.} 
  3. If {\{A_\alpha\colon\alpha<\gamma\}\in I_\alpha} and {\gamma<\kappa,} then {\bigcup_ \alpha A_ \alpha\in I_ \alpha}: Let {X_ \alpha\in N} witness that {A_ \alpha\in I_ \alpha.} Then {\{X_ \alpha\colon \alpha<\gamma\}\in N,} since {[N]^{<\kappa}\subseteq N.} Thus, {\bigcup_ \alpha X_ \alpha \in N,} and it witnesses that {\bigcup_ \alpha A_ \alpha\in I_ \alpha.} In particular, {[ \alpha]^{<\kappa}\subseteq I_ \alpha,} since clearly {\{\beta\}\in I_ \alpha} for all {\beta< \alpha.}

For {i<\mu} let

\displaystyle  H_i=\{\beta< \alpha\colon f(\beta, \alpha)=i\}.

Then {\bigcup\{H_i\colon i<\mu\}= \alpha} so, for some {i,} {H_i\notin I_ \alpha} (since {I_ \alpha} is {\kappa}-closed). Fix such {i}. We claim that for any {X\subseteq H_i} such that {X\notin I_ \alpha} there is {Y\subseteq X} such that {{\rm ot}(Y)=\kappa} and {Y} is {i}-homogeneous. This will suffice, because {Y\cup\{ \alpha\}} is also {i}-homogeneous (by definition of {H_i}) and has order type {\kappa+1.}

To see the claim, it suffices to show, by regularity of {\kappa,} that if {x\in[X]^{<\kappa}} is {i}-homogeneous, then there is {\beta\in X,} {\beta>\sup(x),} such that {x\cup\{\beta\}} is also {i}-homogeneous. Fix such {x,} and notice that {x\in N.} Let

\displaystyle  Z=\{\gamma<\lambda:\gamma>\sup(x)\mbox{ and }\forall\delta\in x\,(f(\delta,\gamma)=i)\}.

Then {Z\in N.} Since {x\subset H_i,} { \alpha\in Z.} But then { \alpha\setminus Z\in I_ \alpha,} as witnessed by {\lambda\setminus Z.} Since {X\notin I_ \alpha,} we must have that {X\cap Z\notin I_ \alpha} and in particular there is some {\beta\in X\cap Z.} \Box

The full version of the {\mbox{Erd\H os}}-Rado theorem (for partitions of {n}-sets with {n>2}) can be obtained by combining this method with the end-homogeneous sets approach, as in the proof of Ramsey’s theorem in Subsection 2.3 of lecture III.1. One can thus show the following:

Theorem 3 ({\mbox{Erd\H os}}-Rado) Let {\beth_1(<\kappa)=2^{<\kappa}} and {\beth_{m+1}(<\kappa)=2^{\beth_m(<\kappa)}} for {m>1.} Let {n<\omega} and let {\kappa} be an infinite regular cardinal. Then 

\displaystyle \beth_n(<\kappa)^+\rightarrow(\kappa)^{n+1}_\mu\mbox{ for any }\mu<\kappa.\ \Box

{\mbox{Erd\H os}}-Rado also showed that {\beth_n(<\kappa)^+} cannot be replaced with {\beth_n(<\kappa)} in this result. And regarding Theorem 1 from last lecture, one can also prove a more general (non-topological) version:

Theorem 4 ({\mbox{Erd\H os}}-Dushnik-Miller) Let {\kappa} be regular and let {\lambda=(2^{<\kappa})^+} and {\mu<\kappa.} Then {\lambda\rightarrow(\lambda,(\kappa+1)_{\mu-1})^2.}

Proof: Argue as before, and use the same notation. Now {f:[\lambda]^2\rightarrow\mu} and we need either a {0}-homogeneous set of size {\lambda,} or an {i}-homogeneous set of order type {\kappa+1} for some {i\ne0.} If {H_i\notin I_ \alpha} for some {i>0,} the proof above works, so we can assume that {H_i\in I_ \alpha} for all {i>0.} Since {I_ \alpha} is {\kappa}-complete, we then have

\displaystyle  \alpha\setminus H_0=\bigcup_{i>0}H_i\in I_ \alpha.

Let {X\in N} be a witness so { \alpha\notin X} and { \alpha\setminus H_0\subseteq X.} Let {Y=\lambda\setminus X,} so {Y\in N,} { \alpha\in Y} and {Y\subseteq\lambda\setminus( \alpha\setminus H_0)=H_0\cup(\lambda\setminus \alpha).} Then {Y\cap \alpha\subseteq \alpha\setminus H_0.}


\displaystyle  Z=\{\beta\in Y\colon\forall\gamma\in Y\cap\beta\,(f(\gamma,\beta)=0)\},

so { \alpha\in Z} and {Z\in N.} It follows from elementarity (see below) that {Z} is unbounded in {\lambda.} Since {\lambda} is regular, this means that {|Z|=\lambda} and, by construction, it is 0-homogeneous and we are done.

To prove that {Z} is unbounded, notice that if {\beta< \alpha} then

\displaystyle  H_{\lambda^+}\models\exists \gamma\in Z\,(\beta<\gamma)

as witnessed, for example, by {\gamma= \alpha.} By elementarity,

\displaystyle  N\models\exists\gamma\in Z\,(\beta<\gamma)

so, since {\beta\in\lambda\cap N= \alpha} was arbitrary,

\displaystyle  N\models\forall\beta<\lambda\,\exists\gamma>\beta\,(\gamma\in Z).

By elementarity, the same holds in {H_{\lambda^+},} so {Z} is unbounded in {\lambda.} \Box

The proofs of Theorems 1 and 3 above require the axiom of choice. However, the proof of Theorem 4 in lecture III.2 requires a choiceless version. I now proceed to establish this version.

Theorem 5 ({{\sf ZF}}) For any set {x,} any ordinal {\delta,} and any nonzero {n<\omega,} there is some initial ordinal {\kappa} such that

\displaystyle  \kappa\rightarrow(\delta)^n_x.

As mentioned in lecture III.2, this version of the {\mbox{Erd\H os}}-Rado theorem seems to have been rediscovered a few times, by Keisler and Morley in 1967, by Kleinberg and Seiferas in 1973, and by Forster (for {x} finite) in 2007. I follow the elegant presentation from Keisler-Morley, which also seems to give the optimal bounds. The three arguments are rather similar, using the technique of end-homogeneous sets; the lack of choice actually does not affect very much the argument below:

Proof: Let’s begin with some notation.

  • A cardinal will mean here an initial ordinal.
  • Given a set {x,} write {|x|} for the sup of the cardinals that inject into {x.} Note that we only look at cardinals rather than ordinals, so {|x|} does not necessarily coincide with {\aleph(x).} If {x} is well-orderable, then the notation coincides with the standard usage: {|x|} is the unique cardinal bijectable with {x}.
  • Write {|x|^+} for the first cardinal larger than {|x|,} even if this is a finite number.
  • Given an infinite cardinal {\kappa,} let {\kappa^0} be the largest cardinal that can be represented as a union of {\kappa} many sets of size {\kappa.} Hence, {\kappa^0} is either {\kappa} or {\kappa^+,} and under choice it coincides with {\kappa.} (The case {\kappa=\omega_1} was briefly discussed before Homework problem 7 in lecture II.1.)
  • By transfinite recursion, define the numbers {\beth(x,\alpha)} for an arbitrary set {x} and ordinal {\alpha,} as follows: 
    • {\beth(x,0)=|x|.}
    • {\beth(x,\alpha+1)} is the least cardinal strictly larger than {\beth(x,\alpha)^0,} and at least as large as {|{\mathcal P}(\beth(x,\alpha)^0)|.}
    • For {\delta} limit, {\beth(x,\delta)=\sup_{\alpha<\delta}\beth(x,\alpha).}

    Under choice, {\beth(x,\alpha)=\beth_\alpha(|x|)} is the cardinality of the result of iterating {\alpha} many times the power set operation on {|x|,} i.e., {\beth_{\alpha+1}(x)=2^{\beth_\alpha(x)}.}

Let {I} be a set. We will show by induction on {n\in\omega} that if {\kappa>\beth(I,n)^0} is an infinite cardinal, then {\kappa\rightarrow(|I|^+)^{n+1}_I.} This obviously gives the result.

Note that {[\kappa]^{n+1}} is well-orderable, as it can be identified in a natural way with a subset of {\kappa^{n+1}\sim\kappa.} Letting {F:[\kappa]^{n+1}\rightarrow I} be a coloring, it follows that we may as well assume that {I=|I|.} The case {n=0} is now immediate.

Assume {n>0} and that the result is valid for {n-1.} We now describe a tree construction that gives rise to a large end-homogeneous set. We define for each {\alpha<\kappa} a function {f_\alpha} according to the following requirements:

  1. {\alpha\ne\beta} implies {f_\alpha\ne f_\beta.}
  2. {{\rm dom}(f_\alpha)} is an ordinal, {{\rm dom}(f_\alpha)\le\alpha.}
  3. Whenever {\beta\in{\rm dom}(f_\alpha),} there is a {\gamma<\alpha} such that {f_\alpha\upharpoonright\beta=f_\gamma.} Note that by 1 this {\gamma} is unique. Denote it by {g(\beta,\alpha).}
  4. If {\beta\in{\rm dom}(f_\alpha),} then {f_\alpha(\beta)} is the function {t:[\beta+1]^n\rightarrow I} defined by

    \displaystyle  t(\delta_0,\dots,\delta_{n-1})=F(g(\delta_0,\alpha),\dots,g(\delta_{n-1},\alpha),\alpha).

Note that conditions 1–4 uniquely specify {\{f_\alpha:\alpha<\kappa\},} by a straightforward inductive argument. This is because, by 3, {\beta\le\alpha} is the domain of {f_\alpha} iff {f_\alpha\upharpoonright\beta} is defined but does not coincide with any {f_\gamma} for {\gamma<\alpha.}

Lemma 6 Suppose {\beta} is an ordinal and {|\beta|\le\beth(I,n-1)^0.} Then

\displaystyle  |\{\alpha\in\kappa:{\rm dom}(f_\alpha)=\beta\}|\le\beth(I,n).

Proof: If {\gamma<\beta} there is an obvious injection from {[\gamma+1]^n} into the ordinal {\beta^n,} so we can identify any function {f_\alpha} with domain {\beta} with a {\beta}-sequence of sequences of elements of {I,} each of these sequences of length at most {\beta^n.} Hence, we can identify {f_\alpha} with a sequence of length at most {\beta^{n+1}} of elements of {I.}

Since {\beth(I,n-1)^0\ge|I|,} there are at most {\beth(I,n)} many such sequences. \Box

Since {\kappa>\beth(I,n)^0,} it follows from the lemma that there is some {\alpha<\kappa} such that {|{\rm dom}(f_\alpha)|>\beth(I,n-1)^0.} Fix such {\alpha.}

Let {X=\{g(\beta,\alpha):\beta\in{\rm dom}(f_\alpha)\},} note that {|X|=|{\rm dom}(f_\alpha)|,} and consider the coloring {H:[X]^n\rightarrow I} given by

\displaystyle  H(a)=F(a\cup\{\alpha\}).

By the induction hypothesis there is a {Y\subseteq X} with {|Y|>|I|,} and an {i\in I} such that {Y} is {i}-homogeneous for {H.}

It is enough to check that {Y} is also {i}-homogeneous for {F.} For this, let {b\in[Y]^{n+1},} and let {\gamma=\max(b)} and {a=b\setminus\{\gamma\}.} Then {F(a\cup\{\alpha\})=i} and, from conditions 3 and 4 above, it follows that {F(b)=i} as well. \Box

Note that this argument also proves Theorem 3 above.


  • James Baumgartner, András Hajnal, Stevo {\mbox{Todor\v cevi\'c}}, Extensions of the {\mbox{Erd\H os}}-Rado theorem, in Finite and infinite combinatorics in sets and logic, NATO (1991), 1–18.
  • Jerome Keisler, Michael Morley, Elementary extensions of models of set theory, Israel J. Math., 6 (1968) 49–65.

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


2 Responses to 580 -Partition calculus (6)

  1. […] generalization of the elementary substructures argument used to prove the -Rado Theorem 1 from last lecture. Together with the argument below, this provides us with a nice, relatively short, purely […]

  2. […] generalization of the elementary substructures argument used to prove the -Rado Theorem 1 from last lecture. Together with the argument below, this provides us with a nice, relatively short, purely […]

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 )

Facebook photo

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

Connecting to %s

%d bloggers like this: