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.:

${\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.}$
${\emptyset\in I_\alpha}$ ; and ${A\subseteq B\in I_\alpha}$ implies ${A\in I_\alpha.}$
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.}$

Let

$\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 for an arbitrary set and ordinal 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:

${\alpha\ne\beta}$ implies ${f_\alpha\ne f_\beta.}$
${{\rm dom}(f_\alpha)}$ is an ordinal, ${{\rm dom}(f_\alpha)\le\alpha.}$
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).}$
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.

Bibliography

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.

This entry was posted on Friday, April 24th, 2009 at 12:13 pm 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.

2 Responses to 580 -Partition calculus (6)

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

May 7, 2009 at 6:58 am

[…] 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 […]

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

August 31, 2012 at 12:25 pm

[…] 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 […]

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 …

M	T	W	T	F	S	S
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

A kind of library