580 -Partition calculus (7)

Updates

Let me begin with a couple of updates.

In the last Corollary of the Appendix to lecture I.5, I indicate that in {{\sf ZF},} we have that

\displaystyle \aleph(X)<\aleph({\mathcal P}^2(X))

whenever {\aleph(X)} is not {\aleph_\alpha} for some infinite limit ordinal {\alpha<\aleph_\alpha.} In fact,

\displaystyle {\mathcal P}(\aleph(X))\preceq{\mathcal P}^2(X)

holds.

This result is best possible in terms of positive results. In Theorem 11 of the paper by John Hickman listed at the end, it is shown that for any such {\alpha} it is consistent with {{\sf ZF}} that there is an {X} with {\aleph(X)=\aleph_\alpha} for which {\aleph(X)=\aleph({\mathcal P}^2(X)).}

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

{\mbox{Erd\H os}} and Hajnal asked whether it is possible to have infinite cardinals {\tau,\lambda,\kappa} such that

\displaystyle \tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa}.

Galvin and Prikry showed (see Corollaries 16 and 18 of lecture III.3) that any such {\tau} must be larger than {\lambda^\kappa} and that {\kappa<\lambda.}

Following a nice suggestion of Grigor Sargsyan, we use arguments as in Theorem 9 from lecture III.5 to show that this partition relation cannot hold.

The key is the following:

Lemma 1 If there are infinite cardinals {\tau,\lambda,\kappa} such that {\tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa},} then for every sufficiently large {\gamma} there is an elementary embedding {j:M\rightarrow V_\gamma} such that {|M|=\lambda^\kappa,} {{\rm cp}(j)<\lambda,} {j(\lambda)=\lambda,} and {{}^\kappa M\subseteq M.}

 
Here is a brief sketch:

Proof: By Corollary 20 from lecture III.3, the given relation is equivalent to {\tau\rightarrow[\lambda]^\kappa_\lambda.} Consider a {\kappa}-Skolem function {F:[V_\gamma]^\kappa\rightarrow V_\gamma} so that any {Y\subset V_\gamma} closed under {F} is both closed under {\kappa}-sequences and an elementary substructure of {V_\gamma.}

Use {F} to define a coloring {G:[\tau]^\kappa\rightarrow\lambda} by setting {G(x)=F(x)} whenever {F(x)\in\lambda,} and {G(x)=0} otherwise. By assumption, there is {H\in[\tau]^\lambda} with {G''[H]^\kappa\ne\lambda.} Note that if {Y} is the closure of {H} under {F,} then {Y\cap\lambda=G''[H]^\kappa\cap\lambda\ne\lambda.} But we can assure that {|H\cap\lambda|=\lambda,} and the result follows by taking as {M} the transitive collapse of {H.} \Box

One concludes the proof by noting that it is impossible to have such embeddings. For this, it suffices that {{}^\omega M\subseteq M} and that {M} admits a fixed point past its critical point. One then obtains a contradiction just as in Kunen’s proof that there are no embeddings {j:V\rightarrow V,} see Corollary 9 in lecture III.3.

Similarly, Matthew Foreman has shown that there are no embeddings {j:M\rightarrow V} with {M} closed under {\omega}-sequences. The reason is that any such embedding must admit a fixed point past its critical point, as can be argued from the existence of scales. See the paper by Vickers and Welch listed at the end for a proof of this result.

On the other hand, it is still open whether one can have embeddings {j:M\rightarrow V} such that {M} computes cofinality {\omega} correctly.

1. The Baumgartner-Hajnal theorem

In Theorem 2 of lecture III.5 we showed the {\mbox{Erd\H os}}-Rado result that

\displaystyle \kappa\rightarrow_{top}(Stationary,\omega+1)^2

whenever {\kappa} is regular. It is natural to wonder whether stronger results are possible. We restrict ourselves here to the case {\kappa=\omega_1.} Due to time constraints, we state quite a few results without proof.

1.1. Hajnal’s counterexample

In general, we cannot even have

\displaystyle \omega_1\rightarrow(\omega_1,\omega+2)^2.

For example, Hajnal showed that this fails under {{\sf CH},} and {\mbox{Todor\v cevi\'c}} showed that it fails in well-known forcing extensions (e.g., after adding one Cohen real). I present here Hajnal’s argument:

Theorem 2 (Hajnal) Let {\lambda} be regular and assume that {2^\lambda=\lambda^+=\kappa.} Then

\displaystyle \kappa\not\rightarrow((\kappa:\kappa),(\lambda:2)_<)^2.

This means that there is a coloring {f:[\kappa]^2\rightarrow2} that neither admits a {0}-homogeneous bipartite graph with {\kappa} plus {\kappa} vertices, nor a {1}-homogeneous bipartite graph with {\lambda} vertices below and {2} vertices above.

 
From this, one immediately concludes:

Corollary 3 If {\lambda} is regular and {2^\lambda=\lambda^+,} then {\lambda^+\not\rightarrow(\lambda^+,\lambda+2)^2.} {\Box}

Proof: Let {(A_\alpha:\alpha<\kappa)} enumerate {[\kappa]^\lambda.} By transfinite recursion we will define a sequence

\displaystyle (F_\xi:\xi<\kappa)

of subsets of {\kappa} in terms of which we will then define the coloring {f:[\kappa]^2\rightarrow2:} We require that {F_\xi\subseteq\xi,} and define {f} so that

\displaystyle F_\xi=\{\eta<\xi:f(\eta,\xi)=1\}

for all {\xi<\kappa.}

We start by setting {F_\xi=\emptyset} for all {\xi<\lambda.} Suppose now that {\xi\in[\lambda,\kappa)} and {F_\eta} has been defined for all {\eta<\xi.} To define {F_\xi,} we use transfinite recursion to define a sequence

\displaystyle (\delta_{\eta,\xi}:\eta<\lambda)

of ordinals below {\xi,} and then set {F_\xi=\{\delta_{\eta,\xi}:\eta<\lambda\}.}

Fix a bijection {g_\xi:\lambda\rightarrow\xi,} let {\eta<\lambda,} and suppose that {(\delta_{\zeta,\xi}:\zeta<\eta)} has been defined. Let

\displaystyle D_{\eta,\xi}=((A_{g_\xi(\eta)}\cap\xi)\setminus\{\delta_{\zeta,\xi}:\zeta<\eta\})\setminus\bigcup_{\zeta<\eta} F_{g_\xi(\zeta)}.

If this set is nonempty, let {\delta_{\eta,\xi}=\min(D_{\eta,\xi}).} Otherwise, let {\delta_{\eta,\xi}=0.} This completes the construction of the sequence {(\delta_{\eta,\xi}:\eta<\lambda),} hence that of the sequence {(F_\xi:\xi<\kappa),} and of the coloring {f.}

It remains to show that {f} has the stated property. First, we observe the following almost-disjoint property of the sets {F_\xi:}

Lemma 4 If {\alpha<\xi<\kappa,} then {|F_\alpha\cap F_\xi|<\lambda.}

 
Proof: We may assume that {\xi\ge\lambda.} Let {\eta<\lambda} be such that {\alpha=g_\xi(\eta).} We then have that

\displaystyle F_\alpha\cap F_\xi\subseteq\{0\}\cup\{\delta_{\zeta,\xi}:\zeta<\eta\},

since any nonzero {\delta_{\zeta,\xi}} with {\zeta\ge\eta} is not in {F_\alpha,} by definition of {D_{\zeta,\xi}.} \Box

Next we check that there is no {1}-homogeneous graph of type {(\lambda:2)_<.} In effect, fix {X\in[\kappa]^\lambda} and two ordinals {\alpha<\xi<\kappa} such that {\sup(X)\le\alpha.} If

\displaystyle f''(X\otimes\{\alpha\})=f''(X\otimes\{\xi\})=\{1\},

then {X\subseteq F_\alpha\cap F_\xi,} contradicting Lemma 4.

Now we check that there is no {0}-homogeneous graph of type {(\kappa:\kappa).} Towards a contradiction, suppose that {X,Y\in[\kappa]^\kappa,} that {X\cap Y=\emptyset,} and that

\displaystyle f''[X,Y]=\{0\}.

Let {Z=\{\gamma<\kappa:|F_\gamma\cap X|=\lambda\}.}

Lemma 5 {|Z|\ge\lambda.}

 
Proof: Suppose otherwise. Pick

\displaystyle A\in [X\setminus(\sup(Z)+1)]^\lambda,

and let {\alpha<\kappa} be such that {A=A_\alpha.} Pick {\xi\in Y\setminus(\sup(A)+\alpha+1)} and let {\eta<\lambda} be such that {g_\xi(\eta)=\alpha.}

We claim that {D_{\eta,\xi}\ne\emptyset.} Hence

\displaystyle \delta_{\eta,\xi}\in D_{\eta,\xi}\subseteq A_\alpha\subset X,

and since {f(\delta_{\eta,\xi},\xi)=1,} we obtain a contradiction.

To see that {D_{\eta,\xi}\ne\emptyset,} note that:

  • {|\{\delta_{\zeta,\xi}:\zeta<\eta\}|\le|\eta|<\lambda.}
  • For any {\gamma,} if {\gamma\in Z} then

    \displaystyle F_\gamma\cap A_\alpha\subseteq \gamma\cap A=\emptyset

    and, if {\gamma\notin Z,} then

    \displaystyle |F_\gamma\cap A_\alpha|\le|F_\gamma\cap X|<\lambda.

  • Therefore {\bigcup_{\zeta<\eta}F_{g_\xi(\zeta)}\cap A} has size strictly less than {\lambda,} by regularity of {\lambda.}

It follows that {|D_{\eta,\xi}|=\lambda.} \Box

Let {\{\gamma_\nu:\nu<\lambda\}} enumerate the first {\lambda} elements of {Z.} Now set

\displaystyle A=\bigcup_{\nu<\lambda}(X\cap F_{\gamma_\nu}),

so {A} has size {\lambda} and there is some {\alpha<\kappa} such that {A=A_\alpha.}

Pick {\xi\in Y\setminus(\sup(A)+\alpha+1)} and let {\eta<\lambda} be such that {g_\xi(\eta)=\alpha.} Just as above, we reach a contradiction once we show that {D_{\eta,\xi}\ne\emptyset.}

To prove that this is the case, let {\nu<\lambda} be such that {\gamma_\nu\notin\{g_\xi(\zeta):\zeta<\eta\}.} Since {\lambda} is regular, it follows from Lemma 4 that

\displaystyle (X\cap F_{\gamma_\nu})\setminus\bigcup_{\zeta<\eta}F_{g_\xi(\zeta)}

has size {\lambda,} and therefore so does {D_{\xi,\eta}.} \Box

1.2. Countable ordinals

Hajnal’s result rules out a natural extension of the relation

\displaystyle \omega_1\rightarrow_{top}(Stationary,\omega+1)^2,

so we need to look a bit harder for possible extensions. Note that the relation implies immediately that

\displaystyle \omega_1\rightarrow_{top}(\alpha+1,\omega+1)^2

for any {\alpha<\omega_1.} This is because of the following result:

Lemma 6 Any stationary subset of {\omega_1} contains closed subsets of order type {\alpha+1} for any countable {\alpha.}

 
(Of course, we cannot replace {\alpha+1} with {\omega_1,} since there are disjoint stationary sets.)

Proof: Let { S\subseteq\omega_1} be a given stationary set, and argue by induction on { \alpha<\omega_1} that { S} contains closed copies { t} of { \alpha+1} with { \min(t)} arbitrarily large. (Of course, if the result holds, this must be the case: Given any { \gamma<\omega+1}, notice that { S\setminus(\gamma+1)} is stationary, so it must contain a closed copy { t} of { \alpha+1}, and { \min(t)<\gamma}.)

This strengthened version holds trivially for { \alpha} finite or successor, by induction. So it suffices to show it for { \alpha} limit, assuming it holds for all smaller ordinals. Define a club { C\subseteq\omega_1} with increasing enumeration { \{\gamma_\beta:\beta<\omega_1\}} as follows:

Let { (\alpha_n:<\omega)} be strictly increasing and cofinal in { \alpha}. Since { S} contains closed copies { A_n} of { \alpha_n+1} for all { n}, with their minima arbitrarily large, by choosing such copies { A_n} with { \min(A_{n+1})>\max(A_n)} and taking their union, we see that { S} must contain copies of { \alpha}, closed in their supremum, with arbitrarily large minimum element. (I am not claiming that { A=\bigcup_n A_n} built this way has order type { \alpha}. For example, if { \alpha=\omega+\omega} and { \alpha_n=\omega+n}, then { A} would have order type { \omega^2}; but for sure { A\subset S} is closed in its supremum and has order type at least { \alpha}. So a suitable initial segment of { A} is as wanted.)

Let { \gamma_0} be the supremum of such a copy of { \alpha}. At limit ordinals { \beta}, let { \gamma_\beta=\sup_{\delta<\beta}\gamma_\delta}. Once { \gamma_\beta} is defined, find such a copy of { \alpha} inside { S} with minimum larger than { \gamma_\beta}, and let { \gamma_{\beta+1}} be its supremum.

The set { C} so constructed is club, so it meets { S}. If they meet in { \gamma_0} or in a { \gamma_{\beta+1}}, this immediately gives us a closed copy of { \alpha+1} inside { S}. If they meet in a { \gamma_\beta} with { \beta} limit, let { (\beta_n:n<\omega)} be strictly increasing and cofinal in { \beta}, and consider an appropriate initial segment of { A=(\bigcup_n A_n)\cup\{\gamma_\beta\}}, where { A_n} is a closed copy of { \alpha_n+1} in { S\cap[\gamma_{\beta_n},\gamma_{\beta_{n+1}})}. \Box

A direct extension of the relation {\omega_1\rightarrow_{top}(\alpha+1,\omega+1)^2} is briefly discussed in Subsection 1.6. This relation certainly implies {\omega_1\rightarrow(\alpha+1,\omega+1)^2,} so one natural attempt at extending this result is seeing whether for a fixed {\alpha<\omega_1} there is a {\beta<\omega_1} such that {\beta\rightarrow(\alpha,\omega+1)^2.} This is not the case: From Ramsey’s theorem, we know that {\omega\rightarrow(\omega)^2;} however, no countable {\alpha} satisfies {\alpha\rightarrow(\omega,\omega+1)^2.} In fact, more is true:

Lemma 7 If {(X,<)} is a linearly ordered set, then {X\not\rightarrow(\omega,|X|+1)^2.}

 
Proof: Let {\prec} be an ordering of {X} in order type {|X|,} and let {f:[X]^2\rightarrow2} be the corresponding “{\mbox{Sierpi\'nski}}” coloring:

\displaystyle f(x,y)=1\mbox{ iff }(x<_Xy\Leftrightarrow x\prec y).

Then clearly there can be no {1}-homogeneous set of order type {|X|+1}, while a {0}-homogeneous set of order type {\omega} would give us an infinite {\prec}-descending sequence. \Box

Since {\alpha\not\rightarrow(\beta,\omega)^2} for all {\alpha<\omega_1} and all {\beta\in[\omega+1,\omega_1),} the best we could hope for is that for any {\beta<\omega_1} and any finite {n} there is an {\alpha<\omega_1} such that {\alpha\rightarrow(\beta,n)^2.} Note that, trivially, {\alpha\rightarrow(\alpha,2)^2.} However, relations of the form {\alpha\rightarrow(\beta,3)^2} are already significantly harder to achieve. The key to positive results of this kind is to study indecomposable ordinals, those of the form {\omega^\gamma.}

Theorem 8 Let {\alpha,\beta} be countable, and let {k} be finite. Suppose that

\displaystyle \omega^\alpha\rightarrow(\omega^{1+\beta},k)^2.

Then {\omega^{\alpha+\beta}\rightarrow(\omega^{1+\beta},2k)^2.} {\Box}

 

Corollary 9 ({\mbox{Erd\H os}}-Milner) If {m<\omega} and {\mu<\omega_1,} then {\omega^{1+\mu m}\rightarrow(\omega^{1+\mu},2^m)^2.} Thus

\displaystyle \omega^{1+\mu\omega}\rightarrow(\omega^{1+\mu},<\omega)^2

for all {\mu<\omega_1.} {\Box}

 

For certain ordinals, something stronger is true; for example, Specker showed that

\displaystyle \omega^2\rightarrow(\omega^2,m)^2

for all finite {m,} but the same statement fails if we replace {\omega^2} with {\omega^3;} on the other hand, Chang showed that

\displaystyle \omega^\omega\rightarrow(\omega^\omega,m)^2

for all finite {m.} The precise characterization of those countable ordinals {\alpha} such that

\displaystyle \alpha\rightarrow(\alpha,m)^2

for all finite {m} stills seems to be open. Special attention has been given to partition ordinals, these are countable ordinals {\alpha} such that

\displaystyle \alpha\rightarrow(\alpha,3)^2.

Theorem 10 (Galvin-Larson) Any partition ordinal other than {\omega^2} has the form {\omega^{\omega^\beta}} for some countable {\beta.} {\Box}

 
The Galvin-Larson result uses the notion of pinning, introduced by Specker:

Definition 11 (Specker) An ordinal {\alpha} pins an ordinal {\beta,} in symbols

\displaystyle \alpha\rightarrow\beta,

iff there is a pinning map {\pi:\alpha\rightarrow\beta,} that is, a map such that for any {A\in[\alpha]^\alpha} we have that {\pi''A\in[\beta]^\beta.}

 
The connection of this notion with the partition calculus comes from Specker’s observation that if {\alpha\rightarrow(\alpha,\kappa)^2} for {\alpha>1} an ordinal and {\kappa\ge3} a cardinal, and if {\alpha\rightarrow\beta,} then {\beta\rightarrow(\beta,\kappa)^2.} For example, Specker showed that {\omega^m\rightarrow\omega^3} for {3\le m<\omega,} and that {\omega^3\not\rightarrow(\omega^3,3)^2,} from which it follows that {\omega^m\not\rightarrow(\omega^m,3)^2} for {3\le m<\omega.}

Theorem 12 (Schipperus) If {\beta<\omega_1} is indecomposable or the sum of two indecomposable ordinals, then

\displaystyle \omega^{\omega^\beta}\rightarrow(\omega^{\omega^\beta},3)^2

holds. {\Box}

 

On the other hand, one has:

Theorem 13

  1. If {\beta} is the sum of at least four indecomposable ordinals, then

    \displaystyle \omega^{\omega^\beta}\not\rightarrow(\omega^{\omega^\beta},3)^2.

  2. If {\beta} is the sum of at least three indecomposable ordinals, then

    \displaystyle \omega^{\omega^\beta}\not\rightarrow(\omega^{\omega^\beta},4)^2.

  3. If {\beta} is the sum of two indecomposable ordinals, then

    \displaystyle \omega^{\omega^\beta}\not\rightarrow(\omega^{\omega^\beta},5)^2.

  4. If {\beta=\omega^{\alpha+1}} and {m\rightarrow(4)^3_{2^{32}},} then

    \displaystyle \omega^{\omega^\beta}\not\rightarrow(\omega^{\omega^\beta},m)^2

    holds. {\Box}

 
Items 1–3 of Theorem 13 are due to Schipperus, with 6 instead of 5 in item 3; the stated version of item 3 is due to Larson, and item 4 is due to Darby.

1.3. Non-special linear orders

Another possible extension of the relation {\omega_1\rightarrow(\alpha,\omega+1)^2} for all {\alpha<\omega_1} comes from replacing {\omega_1} with some other (necessarily uncountable) linear order. A first result of this kind was obtained by {\mbox{Erd\H os}} and Rado. Recall that {\lambda_0} is the order type of {{\mathbb R}.}

Theorem 14 ({\mbox{Erd\H os}}-Rado) {\lambda_0\rightarrow(\alpha,\omega+1)^2} for all {\alpha<\omega_1;} in fact, whenever {X\subseteq{\mathbb R}} is uncountable, {X\rightarrow(\alpha,\omega+1)^2.}

 
Proof: Let {X\subseteq{\mathbb R}} be uncountable. Without loss, assume that {X} is of size {\omega_1,} and let {\{x_\alpha:\alpha<\omega_1\}} enumerate it. Let {f:[X]^2\rightarrow2} be a given coloring.

Mimicking the proof that {\omega_1\rightarrow_{top}(Stationary,\omega+1),} for each limit {\alpha} let’s build a strictly increasing sequence {(\alpha_n:n<m_\alpha)} such that:

  1. {\alpha_n<\alpha} for all {n<m_\alpha.}
  2. {x_{\alpha_n}<x_\alpha} for all {n<m_\alpha.}
  3. {\{x_{\alpha_n}:n<m_\alpha\}\cup\{x_\alpha\}} is 1-homogeneous for {f.}
  4. Either {m_\alpha=\omega,} or else {m_\alpha=k} for some {k<\omega,} and there is no {\alpha_k} such that items 1–3 hold with {m_\alpha+1} in place of {m_\alpha.}

If for some limit {\alpha} we have {m_\alpha=\omega} we are done, as we have found a subset of {X} of order type {\omega+1} that is {1}-homogeneous for {f.} We can then assume that {m_\alpha<\omega} for all limit ordinals {\alpha.} By repeated application of Fodor’s lemma we can then find an uncountable (in fact, stationary) subset {S} of {\omega_1} consisting of limit ordinals, and such that there is an {m<\omega} with {m_\alpha=m} for all {\alpha\in S,} and there are ordinals {\beta^0,\dots,\beta^{m-1}} such that {\alpha_n=\beta^n} for all {\alpha\in S} and all {n<m.}

It then follows that whenever {S'\subseteq S} and {\alpha<\beta} in {S'} implies {x_\alpha<x_\beta,} then {\{x_\alpha:\alpha\in S'\}} is {0}-homogeneous. Otherwise, if {\alpha^0<\alpha^1} are in {S'} and {f(x_{\alpha^0},x_{\alpha^1})=1,} we could take {(\alpha^1)_m=\alpha^0,} contradiction.

We have essentially reduced the partition problem to a problem which is solely about ordered sets: It now suffices to show that whenever {Y} is an uncountable subset of {{\mathbb R},} then {\alpha\le Y} for all {\alpha<\omega_1.} We prove something stronger; recall that {\eta=\eta_0} is the order type of {{\mathbb Q}.} (Actually, we need something a bit stronger, namely, that there is a subset of Y of type {\alpha} whose indices are also ordered that way. This follows easily by induction from the argument below. We will prove a more general result later, so I will leave this last step as an exercise.)

Lemma 15 Let {Y} be an uncountable subset of {{\mathbb R}.} Then {\eta_0\le Y.}

 
Proof: Let

\displaystyle A=\{x\in Y:(x,\infty)\cap Y\mbox{ is countable}\},

and

\displaystyle B=\{y\in Y:(-\infty,y)\cap Y\mbox{ is countable}\}.

The coinitiality of {A} and the cofinality of {B} are both countable, since {\omega_1\not\le\lambda_0} and {\omega_1^*\not\le\lambda_0.} It follows that {A} and {B} are in fact countable. Also, {A} is a final segment of {Y} and {B} is an initial segment. Let {Y'=Y\setminus(A\cup B),} so {Y} is uncountable and for any {z\in Y',} both {(-\infty,z)\cap Y'} and {(z,\infty)\cap Y'} are uncountable.

A straightforward recursive construction using the above observation easily gives us that {\eta_0\le Y'.} \Box

Applying Lemma 15 to the set {Y=\{x_\alpha:\alpha\in S\},} we are done. \Box

A careful study of the above argument seems to indicate that the notion below is the key to the “right” generalization of {\omega_1\rightarrow(\alpha,\omega+1)^2} for {\alpha<\omega_1.} The concept was introduced by Galvin, although the name is probably due to {\mbox{Todor\v cevi\'c}.}

Definition 16 A linear order {X} is non-special if it is not the union of countably many reverse well-orders, i.e.,

\displaystyle X\rightarrow(\omega)^1_\omega.

Clearly, any non-special order is uncountable.

Here are some examples of non-special orders:

  • {\omega_1.}
  • Suppose that {X} is an uncountable linear order and that {\omega_1^*\not\le X.} Then {\omega\le X.} It follows that {X} is non-special, since if {X} is partitioned into countably many pieces, one of them must be uncountable (and does not embed {\omega_1^*}). In particular, the set of reals or, more generally, any uncountable subset of {{\mathbb R},} is non-special. Because of this example, uncountable linearly ordered sets that embed neither {\omega_1} nor {\omega_1^*} are called of real type. It easily follows from the argument above that for any such {X} we have {X\rightarrow(\alpha,\omega+1)^2} for all {\alpha<\omega_1.}
  • Baumgartner has shown that there are non-special orders such that {\omega_1^*} embeds into any uncountable subset. For example, for each limit {\alpha<\omega_1} let {C_\alpha} be cofinal in {\alpha} of order type {\omega.} Denote by {C_\alpha(n)} the {n}-th member in the increasing enumeration of {C_\alpha,} and set

    \displaystyle \alpha\prec\beta

    for {\alpha\ne\beta} countable limit ordinals iff, letting {n} be least such that {C_\alpha(n)\ne C_\beta(n),} then

    \displaystyle C_\beta(n)<C_\alpha(n).

Galvin noted that Lemma 7 could be improved as follows:

Lemma 17 If {X\rightarrow(\omega+1,\omega)^2,} then {X\rightarrow(\omega)^1_\omega.}

 
Proof: Consider an arbitrary partition of {X} into {\omega} many pieces {X_i}; we must show that at least one of them admits a subset of order type {\omega}. Define {f:[X]^2\rightarrow2} by setting, for {x<y}, {f(x,y)=0} iff there are {i<j} such that {x\in X_i} and {y\in X_j}. Clearly {f} does not admit a 0-homogeneous set of order type {\omega+1}. By assumption, it must therefore admit a {1}-homogeneous set of order type {\omega}. All but finitely many of its members must then belong to the same {X_i}, and thus {X_i} contains a subset of order type {\omega}, as wanted. \Box

The Baumgartner-Hajnal theorem is the statement that a strong converse to Lemma 17 holds.

Theorem 18 (Baumgartner-Hajnal) If {X} is non-special, then {X\rightarrow(\alpha)^2_n} for all {n<\omega} and {\alpha<\omega_1.} {\Box}

 
In Subsection 1.5, I present a proof of Theorem 18 in the particular case that {\omega_1\not\le X.} The argument I will show is very recent and due to Clinton Conley. It also provides us with additional information about colorings of {{\mathbb Q},} and I address this as well.

1.4. Partial orders

The original proof of the Baumgartner-Hajnal theorem used forcing. More precisely, the result was shown under the additional assumption of {{\sf MA},} and then an absoluteness result is invoked to guarantee that it follows without this axiom. This involves two steps: Assume {X\rightarrow(\omega)^1_\omega,} and let {f:[X]^2\rightarrow n} be a finite coloring of {X.} Force {{\sf MA}} (plus {\lnot{\sf CH}}) the usual way, so the forcing notion involved is ccc, and {\omega_1} is preserved. In the extension, {X\rightarrow(\omega)^1_\omega} still holds, and therefore {X\rightarrow(\alpha)^2_n.}

  • We may assume that {\alpha} is infinite. Let {\pi:\omega\rightarrow\alpha} be a bijection. Use {\pi} and {f} to define a tree of height {\omega,} any (infinite) branch through which gives a homogeneous subset of {X} for {f} of order type {\alpha.} The tree is defined in the ground model, but it is ill-founded in the forcing extension. Well-foundedness is absolute (being equivalent to the existence of a ranking function) and therefore the tree must also be ill-founded in the ground model. It follows that there is, in {V,} a homogeneous subset of {X} for {f} of type {\alpha.} This is true for all {\alpha<\omega_1} and all colorings {f,} and therefore {X\rightarrow(\alpha)^2_n.}
  • More delicately, one needs to verify that, indeed, {X\rightarrow(X)^1_\omega} still holds in the forcing extension. This uses that the forcing involved is ccc.

It is natural to wonder whether Theorem 18 admits a forcing-free proof. Galvin found such an argument, and noticed that in a natural way one is led to consider not just linear orders but partial orders. Somewhat later, {\mbox{Todor\v cevi\'c}} extended the result to this setting:

Theorem 19 ({\mbox{Todor\v cevi\'c}}) Assume that {X} is a non-special partial order. Then

\displaystyle X\rightarrow(\alpha)^2_n

for all {n<\omega} and all {\alpha<\omega_1.} {\Box}

 
As with the original argument of Baumgartner and Hajnal, {\mbox{Todor\v cevi\'c}}‘s proof uses forcing, and I do not know of a way of removing this need. For the case {\omega_1\le X,} a new (forcing-free) proof has been recently found by Foreman and Hajnal; it is a significant generalization of the elementary substructures argument used to prove the {\mbox{Erd\H os}}-Rado Theorem 1 from last lecture. Together with the argument below, this provides us with a nice, relatively short, purely combinatorial proof of the Baumgartner-Hajnal theorem for linear orders. The Foreman-Hajnal result can be found in the survey by Hajnal and Larson listed in the references at the end.

This is not yet the end of the story. {\mbox{Todor\v cevi\'c}} has shown that {{\sf PFA}} implies {\omega_1\rightarrow(\omega_1,\alpha)^2} for all {\alpha<\omega_1.} It is not known yet whether the same follows from {{\sf MA}.} I believe the best known result in this direction is due to Hirschorn, who showed that under {{\sf MA},} one has

\displaystyle \omega_1 \rightarrow (\omega_1, \omega^2+1)^2.

1.5. The Baumgartner-Hajnal theorem

I follow closely the note by Conley listed in the references at the end. Our goal is to show that if {X} is a non-special linear order such that {\omega_1\not\le X,} then {X\rightarrow(\alpha)^2_n} for all {n<\omega} and all {\alpha<\omega_1.}

Fix a linearly ordered set {(X, <).} For sets {A, B\subseteq X,} say that

\displaystyle A \mbox{ \bf is below } B

iff {a < b} for all {a\in A} and {b\in B.} (The notation {A<B} is commonly used, but we already use {A<B} to indicate that {A} embeds into {B.})

Fix a proper ideal {{\mathcal I}} of subsets of {X ,} and use terms like small, positive, and large, in the usual way: A small set is a member of {{\mathcal I}.} A positive set is one not in {{\mathcal I}.} A large set is one whose complement is in {{\mathcal I}.} A set {A} is large in {B} iff {B\setminus A\in{\mathcal I}.} The quantifier {\forall^+A} means “for all positive {A.}” Similarly, {\exists^+A} means “there exists a positive {A.}”

Say that positive sets split iff any positive set {A\subseteq X} contains positive sets {A_0} and {A_1,} with {A_0} below {A_1.}

Definition 20 For {c : [X ]^2\rightarrow 2} a coloring and {i \in2,} say that {(A, B)} is an {i}-compatible pair iff {A} and {B} are both positive subsets of {X ,} and for all positive {B'\subseteq B,} the set

\displaystyle \{a \in A : \{b \in B' : c(\{a, b\}) = i\}\mbox{ is positive}\}

is large in {A.}

 
Note that if {B} is positive and {c:[X]^2\rightarrow2} is a coloring, then for any {a,} one of

\displaystyle \{b\in B:c(\{a,b\})=0\}

and

\displaystyle \{b\in B:c(\{a,b\})=1\}

must be positive. Definition 20 asserts that there is a “coherent” way of (almost) always picking the same color that gives us a positive set. One can strengthen this notion as follows:

Definition 21 For {c : [X ]^2\rightarrow 2} a coloring and {i\in2,} say that {(A, B)} is an {i}-focused pair iff {A} and {B} are positive subsets of {X,} and for all {a\in A,} the set

\displaystyle \{b \in B : c(\{a, b\}) = i\}

is large in {B.}

Note that an {i}-focused pair is {i}-compatible, and that the notions are hereditary, in the sense that if {(A, B)} is {i}-compatible, and {A'\subseteq A} and {B'\subseteq B} are both positive, then {(A' , B' )} is also {i}-compatible. Similarly with {i}-focused instead of {i}-compatible.

Lemma 22 Suppose that {c : [X ]^2\rightarrow 2} is a coloring, and that {A, B\subseteq X} are positive. Then there are positive sets {A^*\subseteq A} and {B^*\subseteq B} such that either

  1. {(A^*,B^*)} is {i}-focused for some {i\in2,} or
  2. {(A^*,B^*)} is {i}-compatible for both {i=0} and {i=1.}

Proof: Consider the statement

\displaystyle \exists i\in 2\,\exists^+ B'\subseteq B\,\exists^+ A'\subseteq A\, (\{a\in A': \{b\in B' : c(\{a, b\}) = i\} \displaystyle \mbox{ is positive}\}\mbox{ is small}).

Case 1: It is true, as witnessed by {i,} {A' ,} and {B'.} Let

\displaystyle A^*=A'\setminus\{a\in A': \{b\in B' : c(\{a, b\}) = i\}\mbox{ is positive}\},

and notice that {(A^*,B')} is {(1-i)}-focused.

Case 2: It is false. We then have

\displaystyle \forall i\in2\,\forall^+ B'\subseteq B\,\forall^+ A'\subseteq A\, (\{a\in A' : \{b\in B' : c(\{a, b\}) = i\} \displaystyle\mbox{ is positive}\}\mbox{ is positive}).

But this is equivalent to

\displaystyle \forall i \in 2\,\forall^+ B'\subseteq B\, (\{a\in A : \{b\in B' : c(\{a, b\}) = i\}\mbox{ is positive}\} \displaystyle\mbox{ is large in }B).

(Otherwise, fixing counterexamples {i} and {B',} the complement {A'} of the displayed set would contradict the displayed statement immediately preceding it.) Consequently, {(A, B)} is {i}-compatible for both {i=0} and {i=1.} \Box

Note that the notion of an {i}-compatible pair depends on the order in which we list the sets {A} and {B.}

Definition 23 For {c : [X ]^2\rightarrow 2} a coloring and {i, j \in 2,} say that {(A, B)} is an {(i, j )}-compatible pair iff {(A, B)} is {i}-compatible, and {(B, A)} is {j}-compatible.

 
The following three consequences of Lemma 22 are straightforward; for Lemma 26, use Corollary 25 and a density argument.

Corollary 24 Let {c : [X ]^2\rightarrow2} be a coloring, and suppose that {A, B\subseteq X} are positive. Then there exist positive sets {A^*\subseteq A} and {B^*\subseteq B} such that either

  1. {(A^*,B^*)} is {i}-focused for some {i\in2,} or
  2. {(A^*,B^*)} is {(i, i)}-compatible for some {i\in2.} {\Box}

 

Corollary 25 Let {c : [X ]^2\rightarrow2} be a coloring, and suppose that {A, B\subseteq X} are positive. Then there exist positive sets {A^*\subseteq A} and {B^*\subseteq B} such that {(A^*,B^*)} is {(i,j)}-compatible for some {i,j\in2.} {\Box}

 

Lemma 26 Suppose that positive sets split, and let {c : [X ]^2\rightarrow2} be a coloring. Then there is a positive {A\subseteq X} and {i,j\in2} such that whenever {A'\subseteq A} is positive, then we may find positive subsets {A'_0} and {A'_1} of {A,} with {A'_0} below {A'_1,} such that that the pair {(A'_0,A'_1)} is {(i,j)}-compatible. {\Box}

 
In the setting of Lemma 26, it follows that, by passing to a positive subset of {X,} we may assume that the coloring {c} is {(i,j)}-splitting, in the following sense:

Definition 27 Assume that positive sets split, and let {c:[X]^2\rightarrow2} be a coloring. For {i,j\in2,} say that {c} is {(i,j)}-splitting iff for any positive {A} there are positive subsets {B} and {C} with {B} below {C,} such that {(B,C)} is {(i,j)}-compatible.

 

Lemma 28 Let {c : [X ]^2\rightarrow2} be an {(i,j)}-splitting coloring. Then there are positive sets {X_0} and {X_1,} and an element {x\in X,} such that:

  1. {X_0} is below {\{x\}} and {\{x\}} is below {X_1,}
  2. {(X_0,X_1)} is {(i, j )}-compatible,
  3. {c''(X_0\otimes\{x\})=\{j\}} and {c''(\{x\}\otimes X_1)=\{i\}.}

 
Proof: Use twice that {c} is {(i, j)}-splitting, and find positive sets {A,B,C} with {A} below {B} and {B} below {C,} such that {(A, B),} {(A, C),} and {(B, C)} are all {(i, j)}-compatible.

Since {(B, A)} is {j}-compatible, then the set

\displaystyle B_A= \{b \in B : \{a \in A : c(a, b) = j \}\mbox{ is positive}\}

is large in {B.} Similarly,

\displaystyle B_C=\{b \in B : \{d\in C : c(b, d) = i\}\mbox{ is positive}\}

is large in {B.}

It follows that {B_A\cap B_C\ne\emptyset.} Let {x} be in this intersection. Now set

\displaystyle X_0=\{a \in A : c(a, x) = j\}

and

\displaystyle X_1=\{d \in C : c(x, d) = i\}.

Then {X_0,x,X_1} is as wanted. \Box

It will be important in what follows to study colorings of {{\mathbb Q}.} It turns out to be convenient to have a representation of {{\mathbb Q}} different from the standard one. For this, simply recall that any countable linear order dense in itself and without end points is isomorphic to {{\mathbb Q}.}

Extend the lexicographic order on each {{}^n2=2^n} to a linear order on {2^{<\omega}} by setting {s < t} for {s\ne t} iff {s(n) < t(n),} where {n} is the first coordinate on which they differ, adopting the convention that {0 <} undefined {< 1.} The following is obvious from the characterization of {{\mathbb Q}} just mentioned:

Lemma 29 {{\rm ot}(2^{<\omega},<)=\eta.} {\Box}

 
For {s\in2^{<\omega}} let {|s|} denote its length. We now define four colorings of {{\mathbb Q}.}

Definition 30 For {i,j\in2,} let {c_{ij} : [2^{<\omega} ]^2\rightarrow 2} be the map given by

\displaystyle c_{ij}(s,t)=\left\{\begin{array}{cl}i&\mbox{ if }s<t\mbox{ and }|s|\le|t|,\\ j&\mbox{ if }s<t\mbox{ and }|s|>|t|.\end{array}\right.

 
These colorings are rather special. {c_{00}} and {c_{11}} are constant. {c_{01}} and {c_{10}} do not admit homogeneous sets of type {\eta.} {c_{01}} admits a 1-homogeneous set of type {\omega^*} and {c_{10}} admits a 1-homogeneous set of type {\omega.} These two colorings are standard counterexamples to a version of Ramsey’s theorem on {[{\mathbb Q}]^2} in which the homogeneous set has order type {\eta.} Before hand, we knew that such counterexamples were to be expected, since {\eta\not\rightarrow(\omega+1,\omega),} by Lemma 7.

Theorem 31 (Conley) Suppose that positive sets split, and let {c:[X]^2\rightarrow2} be a coloring. Then there are {i,j\in2} and an order-preserving injection {\phi: 2^{<\omega}\rightarrow X} such that

\displaystyle \forall s, t \in 2^{<\omega}\,(c(\{\phi(s), \phi(t)\}) = c_{ij} (\{s,t\})).

Proof: As explained after Lemma 26, we may assume that {c : [X ]^2\rightarrow 2} is {(i, j)}-splitting for some {i,j\in2.} We now proceed to embed {c_{ij}} into {c.} For this, we recursively construct for each {n\in\omega} a function {\phi_n:{}^n2\rightarrow X} so that the functions {\phi_n} are compatible as {n} varies and, letting {\phi=\bigcup_n\phi_n,} then {\phi} is as wanted. To guarantee this, we construct in addition for each {s\in{}^{n+1}2} a positive set {A_s\subseteq X} so that

  • {(A_s , A_t )} is {(i, j )}-compatible whenever {s<t} are in {{}^{n+1}2,}

and

  • For all {a\in A_t,} {c(\{\phi_{|s|}(s), a\}) = c_{ij} (\{s, t\})} whenever {s,t\in2^{<n+1}.}

At stage {n = 0,} use the splitting assumption and Lemma 28 to find {x\in X} and positive sets {A_0} and {A_1} such that

  • {A_0} is below {\{x\},} {\{x\}} is below {A_1,}
  • {c''(A_0\otimes\{x\})=\{j\}} and {c''(\{x\}\otimes A_1)=\{i\},} and
  • {(A_0 , A_1 )} is {(i, j )}-compatible,

and set {\phi(\emptyset)=x.}

Suppose that the construction has been carried out through stage {n-1.} Stage {n} is completed by going from left to right in {(2^n,<_{lex}).} To begin with, by the assumption of compatibility, we may assume that there is a set {A'_{0^n}} large in {A_{0^n}} such that for all {x\in A'_{0^n}} and all {t\in{}^n2} with {0^n<t,} the set

\displaystyle \{a \in A_t : c(\{a, x\}) = c_{ij} (\{0^n, t\}) = i\}

is positive. Apply Lemma 28 to {A'_{0^n}} as in stage {0} to obtain {\phi_n(0^n)\in A'_{0^n}} and an {(i, j )}-compatible pair {(A_{0^n{}^\frown0} , A_{0^n{}^\frown 1} ).} Then, replace each {A_t} with the positive set

\displaystyle \{a \in A_t : c(\{\phi_n(0^n), a\}) = c_{ij} (\{0^n, t\})\}.

Suppose now that we have defined {\phi_n(t),} {A_{t{}^\frown 0},} and {A_{t{}^\frown1},} for all {t\in{}^n2} smaller than {s\in{}^n2.} By the assumption of compatibility, we may assume that for all {x\in A_s} and all {t\in {}^n2} with {s<t,} the set

\displaystyle \{a \in A_t : c(\{x, a\}) = c_{ij} (\{s, t\}) = i\}

is positive, and that for all {x\in A_s} and all {t \in {}^{n+1}2} with {t < s,} the set

\displaystyle \{a \in A_t : c(\{a, x\}) = c_{ij} (\{s, t\}) = j \}

is positive.

Apply Lemma 28 to {A_s} as before, and obtain {\phi_n(s)\in A_s,} and an {(i, j )}-compatible pair {(A_{s{}^\frown0} , A_{s{}^\frown1} ).} Now, for each {t\in{}^n2} with {s < t,} replace {A_t} with

\displaystyle \{a \in A_t : c(\{\phi_n (s), a\}) = c_{ij} (\{s, t\})\}

and, for each {t\in {}^{n+1}2} with {t < s,} replace {A_t} with

\displaystyle \{a \in A_t : c(\{a, \phi_n (s)\}) = c_{ij} (\{t, s\})\}.

At the end of the construction, we obtain an order-preserving injection {\phi:2^{<\omega}\rightarrow X,} and now we proceed to verify that it is as desired. Fix {s\ne t\in2^{<\omega}.} If the construction defined {\phi(s)} before {\phi(t),} then {\phi(t)} belongs to the refined version of {A_t} constructed right after {\phi(s)} was defined. But then

\displaystyle c(\{\phi(s), \phi(t)\}) = c_{ij} (\{s, t\}),

and we are done. \Box

The following canonization result is immediate:

Corollary 32 Suppose that {c : [{\mathbb Q}]^2\rightarrow 2} is an arbitrary coloring. Then there are {i, j\in 2} and {A\in[{\mathbb Q}]^\eta} such that {c\upharpoonright[A]^2 = c_{ij} \upharpoonright [A]^2.}

 
Proof: Apply Theorem 31 to {{\mathbb Q}} and the ideal {{\mathcal I}=\{A\subseteq{\mathbb Q}:\eta\not\le A\}.} \Box

The above results (as well as the results in the remainder of this subsection) hold for any finite number of colors. In this setting, the only change we obtain is that the basis of colorings in the canonization result has size larger than four, but they are all either constant functions or of the form {c_{ij}} for {i\ne j.}

Corollary 33 ({\mbox{Erd\H os}}-Rado) The partition relation {\eta\rightarrow(\eta,\aleph_0)^2} holds, i.e., any coloring of {[{\mathbb Q}]^2} with two colors black and red either admits a black-homogeneous copy of {{\mathbb Q},} or else it admits an infinite red-homogeneous set. {\Box}

 
Note also that {\aleph_0} cannot be improved to either {\omega} or {\omega^*.}

Corollary 34 (Galvin) For any {n<\omega,} we have {\eta\rightarrow[\eta]^2_{n,2},} i.e., for any coloring of {[{\mathbb Q}]^2} with finitely many colors, there is a copy of {{\mathbb Q}} that uses at most two colors. {\Box}

This is an example of a so-called “rainbow” Ramsey theorem. The ultimate result in this direction is due to D. Devlin:

Definition 35 Let

\displaystyle \tan(z)=\sum_{n=0}^\infty\frac{T_n}{n!}z^n

be the Taylor series expansion of {\tan(z)} about {z=0.} Define the sequence {(t_n:1\le n<\omega)} of odd tangent numbers by {t_k=T_{2k-1},} so

\displaystyle t_1=1,t_2=2,t_3=16,\dots

 

Theorem 36 (Devlin)

  1. For every positive integer {k} we have {\eta\not\rightarrow[\eta]^k_{t_k}.}
  2. However, for any {n<\omega,} we have {\eta\rightarrow[\eta]^k_{n,t_k}.} {\Box}

 
We can now deduce the promised version of the Baumgartner-Hajnal theorem from Theorem 31.

Corollary 37 Suppose that {{\mathcal I}} is {\sigma}-additive and that positive sets split. Let {c : [X ]^2\rightarrow2} be a coloring. Then, for all {\alpha<\omega_1,} there exists a homogeneous set for {c} of order type {\alpha.}

 
Proof: By Theorem 31, if we can find an {(i, i)}-splitting, positive set {X'\subseteq X,} then in fact {X} admits a homogeneous set for {c} of order type {\eta.}

By Corollary 24 and a density argument, we may then assume that there is an {i\in2} such that every positive set {X'\subseteq X} can split into positive sets {X_0} and {X_1,} with {X_0} below {X_1,} and {(X_0 , X_1 )} an {i}-focused pair.

We now proceed by induction on {\alpha<\omega_1} to show that {X} admits an {i}-homogeneous subset of type {\alpha.}

Assume the result for all {\beta<\alpha.} Suppose first that {\alpha=\beta+1.} Split {X} into sets {X_0} below {X_1} where {(X_0 , X_1 )} is {i}-focused. Let {A_\beta\in[X_0]^\beta} be {i}-homogeneous. For each {x_0\in A_\beta,} the set

\displaystyle \{x_1 \in X_1 : c(x_0 , x_1) = i\}

is large in {X_1.} Since {{\mathcal I}} is {\sigma}-additive, we may find an {x_\beta} in the intersection of all these sets and, clearly, {A_\beta\cup\{x_\beta\}} is {i}-homogeneous and of type {\alpha.}

Suppose now that {\alpha} is a limit ordinal, and let {(\beta_n:n<\omega)} be increasing and cofinal in {\alpha.} Split {X} several times to find

\displaystyle X_0\mbox{ below }X_1\mbox{ below }\dots

such that each pair {(X_{n_0} , X_{n_1} )} with {n_0<n_1} is {i}-focused. By the inductive hypothesis, find an {i}-homogeneous set {A_{\beta_0}\in[X_0]^{\beta_0}.} As in the previous case, refine each {X_n} with {n>0} in such a way that

\displaystyle c''(A_{\beta_0}\otimes X_n)=\{i\}.

Now continue inductively, finding an {i}-homogeneous set {A_{\beta_n}\in[X_n]^{\beta_n},} and refining all {X_m} with {m>n.}

Finally, let {A=\bigcup_n A_{\beta_n}.} Then {A} is {i}-homogeneous and of type {\sum_n\beta_n\ge\alpha.} \Box

Again, Corollary 37 holds for colorings into any finite number of colors.

Corollary 38 (Baumgartner-Hajnal) Suppose that {X} is a non-special linearly ordered set and that {\omega_1\not\le X.} Then {X\rightarrow(\alpha)^2_n} for all {n<\omega} and {\alpha<\omega_1.}

 
Proof: Let {{\mathcal I}=\{A\subseteq X:A\not\rightarrow(\omega)^1_\omega\}.} By Corollary 37, it suffices to show that positive sets split.

Bearing in mind the proof of Theorem 14, consider a positive {A\subseteq X,} and let

\displaystyle B=\{x\in A:(-\infty,x)\cap A\in{\mathcal I}\}

and

\displaystyle C=\{x\in A:(x,\infty)\cap A\in{\mathcal I}\}.

Since {\omega_1\not\le A,} then {B} has cofinality {\omega,} and it follows that {B\in{\mathcal I}.} We are done once we show that {C\in{\mathcal I},} because then we can replace {A} with {A'=A\setminus(B\cup C),} and note that for all {x\in A',} both {(-\infty,x)\cap A'} and {(x,\infty)\cap A'} are positive.

We are not assuming that {\omega_1^*\not\le X,} so the argument is slightly more delicate than in Theorem 14. Let {(x_\beta:\beta<\kappa)} be a strictly decreasing, coinitial sequence in {C.} For each {\beta<\kappa} let {c_\beta:[x_\beta,\infty)\cap A\rightarrow\omega} be a partition without homogeneous sets of type {\omega.} For {x\in C,} let {\pi(x)\in\kappa} be the least ordinal {\beta} such that {x\in[x_\beta,\infty).} Now define

\displaystyle c: C\rightarrow\omega

by {c(x)=c_{\pi(x)}(x),} and note that {c} witnesses {C\not\rightarrow(\omega)^1_\omega.} \Box

It would be interesting to find a unified proof of the full Baumgartner-Hajnal theorem following the methods of this subsection, and to see whether these methods can be extended to provide a combinatorial proof of {\mbox{Todor\v cevi\'c}}‘s Theorem 19.

  1.6. The topological Baumgartner-Hajnal theorem

An easy variation of the argument used to show Theorem 14 gives us that

\displaystyle X\rightarrow_{top}(\omega,\omega+1)^2

whenever {X} is an uncountable subset of {{\mathbb R},} meaning that any coloring {f:[X]^2\rightarrow2} either admits an infinite increasing {0}-homogeneous set, or else it admits a closed subset of order type {\omega+1} that is {1}-homogeneous. The following extension was recently obtained by Schipperus; it solves questions of Laver and Weiss:

Theorem 39 (Schipperus) {\omega_1\rightarrow_{top}(\alpha+1)^2_k} and {X\rightarrow_{top}(\alpha+1)^2_k} for any uncountable {X\le\lambda_0,} any {k<\omega,} and any {\alpha<\omega_1.} {\Box}

 
Once again, Schipperus’s argument uses forcing and absoluteness. It is easy to see that being non-special is not enough to imply the result, and I do not know of a more general setting for which Schipperus’s theorem holds; see his paper (listed below) for details.

I do not know whether under {{\sf MA}} or {{\sf PFA}} one can prove that {\omega_1\rightarrow_{top}(Stationary,(\alpha+1)_n)^2} for all {n<\omega} and {\alpha<\omega_1.}

1.7. Partitions of triples

 Finally, I would like to close with a couple of words on an extension of a different kind, namely, what occurs when we color triples rather than pairs.

Theorem 40 (Jones) Let {X} be a non-special partial order. Then

  1. {X\rightarrow (\omega+\omega+ 1, 4)^3,} and
  2. {X\rightarrow(\omega+m, n)^3} for each {m, n < \omega.}
  3. For {X=\omega_1,} item 1 can be improved to {\omega_1\rightarrow(\omega+\omega+1,n)^3} for all {n<\omega.} {\Box}

 
It has been conjectured by Jones and others that if {X} is a non-special partial order, then {X\rightarrow(\alpha,n)^3} for all {\alpha<\omega_1} and {n<\omega.} The assumption on {X} cannot be weakened, in light of the following result; a similar obstacle holds for partial orders:

Theorem 41 If {X} is a linear order, {\kappa} is an infinite cardinal, and {X\not\rightarrow({\rm cf}(\kappa))^1_\kappa,} then {X\not\rightarrow(\kappa+1,4)^3.} {\Box}

 
Bibliography
 

  • James Baumgartner, A new class of order types, Annals of Mathematical Logic, 9 (1976), 187–222.
  • James Baumgartner, András Hajnal, A proof (involving Martin’s axiom) of a partition relation, Fund. Math., 78 (3) (1973), 193–203.
  • Clinton Conley, Colors and ideals: An artistic extravaganza, preprint.
  • Paul {\mbox{Erd\H os},} András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: Partition relations for cardinals, North-Holland, (1984).
  • András Hajnal, Jean Larson, Partition relations, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., to appear.
  • John L. Hickman, {\Lambda}-minimal lattices, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 26 (2) (1980), 181–191.
  • Albin Jones, Partitioning triples and partially ordered sets, Proceedings of the American Mathematical Society, 136 (5) (May 2008), 1823–1830.
  • Rene Schipperus, Countable partition ordinals, PhD thesis, University of Colorado, Boulder; Richard Laver, advisor, (1999).
  • Rene Schipperus, The topological Baumgartner-Hajnal theorem, Transactions of the American Mathematical Society, DOI: http://dx.doi.org/10.1090/S0002-9947-2012-04990-7
  • John Vickers, Philip Welch, On Elementary Embeddings of an Inner Model to the Universe, The Journal for Symbolic Logic, 66 (3) (2001), 1090–1116.
  • Neil Williams, Combinatorial set theory, North-Holland (1977).

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

Advertisement

This entry was posted on Wednesday, May 6th, 2009 at 12:59 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.

11 Responses to 580 -Partition calculus (7)

  1. andrescaicedo says:
    May 12, 2009 at 9:34 am

    Silly typo: In Corollary 9, the last \omega should be <\omega.

    In the proof of Theorem 31, in two instances I write c_{ij}({x,a}) or c_{ij}({a,x}). It should be c_{ij}({s,t}) in both cases.

    Reply
  2. andrescaicedo says:
    May 26, 2009 at 7:46 pm

    A nice remark of Galvin shows that Baumgartner-Hajnal for \omega_1 follows from Clinton’s result in 1.5, so we now have a very nice, easy to remember, short, and purely combinatorial proof of the full Baumgartner-Hajnal theorem for linear orders.

    It is remark 1 (pg 714) in F. Galvin “On a partition theorem of Baumgartner and Hajnal,” Colloquia Mathematica Societatis Janos Bolyai, vol 10. Infinite and Finite Sets, Keszthely (Hungary), 1973, 711-729.

    Let P be any non-special linear order of size \omega_1 that does not embed \omega_1, so from Clinton’s result, Baumgartner-Hajnal holds for P. Let f:P \to \omega_1 be an injection.

    Given a finite k, a coloring c:[\omega_1]^2\to k and an infinite countable ordinal \alpha, let d:[P]^2 \to k+1 be given by:
    1. d(x,y)=k iff f(x)>f(y),
    2. d(x,y)=c(f(x),f(y)) iff f(x)<f(y).

    There is then some A subset of P of type \alpha, i-homogeneous for d for some i\in k+1.

    Notice i cannot be k, since \alpha\ge \omega.

    Then f''A is a subset of \omega_1 of type \alpha and is i-homogeneous for c for some i\in k.

    [This also shows that one cannot improve Clinton's result to show that if P is non-special and does not embed \omega_1, and c:[P]^2\to 2, then P admits a homogeneous set of type \eta.]

    Reply
  3. andrescaicedo says:
    June 9, 2009 at 2:39 pm

    WordPress has added a few changes to the way LaTeX is compiled in their posts, and this has introduced hundreds of error messages through dozens of previous entries. It will take me a while to fix them.

    This has happened before, which is making me reconsider whether to keep the formatting I’ve been using. Any suggestions? I may even simply post pdf files if an entry has too much LaTeX into it to avoid having to revise the code every few months.

    [Update: The issue seems to have been resolved.]

    Reply
  4. Peter Komjath says:
    September 26, 2009 at 8:33 am

    Corollary 33 is in fact due to Erdos and Rado.
    “A partition calculus in set theory”, Bull AMS, 62(1956), 427-489.

    Click to access 1956-02.pdf

    Reply
    • andrescaicedo says:
      September 26, 2009 at 11:57 am

      Hi Peter,

      Thanks! I am slowly editing these notes, and in my current TeX file I had the right reference, but (even though I mentioned it to Conley) somehow missed mentioning it here.

      Reply
  5. Albin Jones says:
    March 21, 2010 at 7:05 pm

    Incidentally, there is a proof of Theorem 19 that doesn’t involve any forcing. Essentially, one can generalize the Foreman-Hajnal method for \omega_1 to arbitrary non-special trees. This is sufficient by a result of \mbox{Todor\v cevi\'c.}

    Reply
    • andrescaicedo says:
      March 21, 2010 at 7:51 pm

      Hi Albin,

      This sounds very nice! I would be grateful if you have a write-up (even if not entirely polished) that you can send me, or a reference. (Last I visited your page, what I think would be the relevant paper was listed as ‘in progress’.)

      I like very much your work on colorings of triples, by the way.

      Reply
      • Albin Jones says:
        June 2, 2011 at 10:10 pm

        Oddly enough, I guess, I only ever tried for the result on non-special trees, thinking that Galvin had already produced a forcing-free proof for linear orders and figuring that a proof for non-special trees would cover all bases in one go.

        I discovered my argument independently of Foreman and Hajnal’s results (and nearly simultaneously). I presented it in a seminar just over ten years ago now. I *might* be able to dig up my notes, but probably not.

        I did start writing up the result, but stopped midway through because I thought that the Foreman and Hajnal proof was less messy, better for generalization, and would still generalize from \omega_1 to non-special-trees directly.

        I still have the unfinished write-up. It *might* be readable as is, but if you’re really interested in the proof, I’d like to try to finish writing it up right. (I say “try” only because I’m a slow writer.)

        I’m glad you like the results on triples. Thank you. I’m very happy to have made even a little progress on those problems.

      • andrescaicedo says:
        June 4, 2011 at 1:55 pm

        Albin: Many thanks for the comment. I’m definitely interested in the result. Would you email me the current version? Of course, if you rather I wait for a final version, that is fine as well.

  6. saf says:
    March 21, 2012 at 7:30 pm

    Theorem 39 is now available online.
    DOI: 10.1090/S0002-9947-2012-04990-7.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
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 )

Cancel

Connecting to %s

%d bloggers like this: