580 -Partition calculus (4)

1. Colorings of pairs. I

There are several possible ways in which one can try to generalize Ramsey’s theorem to larger cardinalities. We will discuss some of these generalizations in upcoming lectures. For now, let’s highlight some obstacles.

Theorem 1 ({\mbox{\bf Erd\H os}}-Kakutani) {\omega_1\not\rightarrow(3)^2_\omega.} In fact, {2^\kappa\not\rightarrow(3)^2_\kappa.}

Proof: Let {S={}^\kappa\{0,1\}.} Let {F:[S]^2\rightarrow\kappa} be given by

\displaystyle F(\{f,g\})=\mbox{least }\alpha<\kappa\mbox{ such that }f(\alpha)\ne g(\alpha).

Then, if {f,g,h} are distinct, it is impossible that {F(\{f,g\})=F(\{f,h\})=F(\{g,h\}).} \Box

Theorem 2 (Sierpiński) {\omega_1\not\rightarrow(\omega_1)^2.} In fact, {2^\kappa\not\rightarrow(\kappa^+)^2.}

Proof: With {S} as above, let {F:[S]^2\rightarrow2} be given as follows: Let {<} be a well-ordering of {S} in order type {2^\kappa.} Let {<_{lex}} be the lexicographic ordering on {S.} Set

\displaystyle F(\{f,g\})=1\mbox{ iff }<_{lex}\mbox{ and }<\mbox{ coincide on }\{f,g\}.

Lemma 3 There is no {<_{lex}}-increasing or decreasing {\kappa^+}-sequence of elements of {S.}

Proof: Let {W=\{f_\alpha\colon\alpha<\kappa^+\}} be a counterexample. Let {\gamma\le\kappa} be least such that {\{f_\alpha\upharpoonright\gamma\colon\alpha<\kappa^+\}} has size {\kappa^+,} and let {Z\in[W]^{\kappa^+}} be such that if {f,g\in Z} then {f\upharpoonright\gamma\ne g\upharpoonright\gamma.} To simplify notation, we will identify {Z} and {W.} For {\alpha<\kappa^+} let {\xi_\alpha<\gamma} be such that {f_\alpha\upharpoonright\xi_\alpha=f_{\alpha+1} \upharpoonright\xi_\alpha} but {f_\alpha(\xi_\alpha)=1-f_{\alpha+1}(\xi_\alpha).} By regularity of {\kappa^+,} there is {\xi<\gamma} such that {\xi=\xi_\alpha} for {\kappa^+} many {\alpha.}

But if {\xi=\xi_\alpha=\xi_\beta} and {f_\alpha\upharpoonright\xi=f_\beta\upharpoonright\xi,} then {f_\beta<_{lex} f_{\alpha+1}} iff {f_\alpha<_{lex} f_{\beta+1},} so {f_\alpha=f_\beta.} It follows that {\{f_\alpha\upharpoonright\xi\colon\alpha<\kappa^+\}} has size {\kappa^+,} contradicting the minimality of {\gamma.} \Box

The lemma implies the result: If {H\subseteq S} has size {\kappa^+} and is {F}-homogeneous, then {H} contradicts Lemma 3. \Box

Now I want to present some significant strengthenings of the results above. The results from last lecture exploit the fact that a great deal of coding can be carried out with infinitely many coordinates. Perhaps surprisingly, strong anti-Ramsey results are possible, even if we restrict ourselves to colorings of pairs.

Recall our convention that if {a=\{a_\alpha:\alpha<\tau\}} for some subset {a} of a linearly ordered set, then {a_0<a_1<\dots.}

{\mbox{Todor\v cevi\'c}} proved the following theorem in 1987. This is one of the gems of modern combinatorial set theory. Previous versions of this result were known to {\mbox{Erd\H os},} Hajnal and Rado in the presence of {{\sf CH}.} The argument below is due to Velleman, from 1990; thanks to Assaf Rinot for pointing me to this argument.

Theorem 4 ({\mbox{\bf Todor\v cevi\'c}}) {\omega_1\not\rightarrow[\omega_1]^2_{\omega_1},} i.e., there is a function {f:[\omega_1]^2\rightarrow2} such that whenever {X\in[\omega_1]^{\omega_1},} then {f''[X]^2=\omega_1.}

Proof: As in the proof of Theorem 4 from last lecture, it is enough to find a function {f:[\omega_1]^2\rightarrow\omega_1} such that whenever {X\in[\omega_1]^{\omega_1},} then {f''[X]^2} contains a club. In effect, let {\psi:\omega_1\rightarrow\omega_1} be such that {\psi^{-1}(\{\alpha\})} is stationary for all {\alpha<\omega_1,} and consider {\psi\circ f.} If {X\in[\omega_1]^{\omega_1},} then {(f''[X]^2)\cap \psi^{-1}(\{\alpha\})\ne\emptyset} for all {\alpha<\omega_1,} so {(\psi\circ f)''[X]^2=\omega_1.}

To define {f,} begin with an injective sequence {(r_\alpha:\alpha<\omega_1)} of functions {r_\alpha:\omega\rightarrow2.} Also, for each {\alpha<\omega_1,} fix an injection {e_\alpha:\alpha\rightarrow\omega.}

For countable ordinals {\alpha\ne\beta,} let

\displaystyle \Delta(\alpha,\beta)=\min\{n:r_\alpha(n)\ne r_\beta(n)\}.

For {\alpha<\beta<\omega_1,} let

\displaystyle \Gamma(\alpha,\beta)=\{\delta\in[\alpha,\beta): e_\beta(\delta)\le\Delta(\alpha,\beta)\},

and set

\displaystyle f(\alpha,\beta)=\left\{\begin{array}{cl}\min(\Gamma(\alpha,\beta))&\mbox{if }\Gamma(\alpha,\beta)\ne\emptyset,\\ 0&\mbox{otherwise.}\end{array}\right.

To see that {f} is as wanted, fix an uncountable {A\subseteq\omega_1.} For {g\in{}^{<\omega}2} let

\displaystyle B_g=\{\alpha\in A: g\subseteq r_\alpha\}.

If {B_g} is countable, let

\displaystyle C^g=\{\delta<\omega_1: B_g\subseteq \delta\}.

Otherwise, let

\displaystyle C^g=\{\delta<\omega_1:0<\delta=\sup(B_g\cap\delta)\}.

Finally, set

\displaystyle C=\bigcap\{C^g:g\in{}^{<\omega}2\},

so {C} is club. Now we show that {C\subseteq f''[A]^2.}

To see this, pick {\delta\in C} and {\beta\in A} with {\delta<\beta.} We will find an {\alpha\le\delta} such that {\alpha\in A} and {f(\alpha,\beta)=\delta.}

Let

\displaystyle n=e_\beta(\delta)

and {g=r_\beta\upharpoonright n,} so {g\subseteq r_\beta} or {\beta\in B_g.} Since {\delta\in C} and {\delta<\beta\in B_g,} we have that {B_g\not\subseteq\delta,} so {B_g} is uncountable, and {0<\delta=\sup(B_g\cap\delta).}

For {\gamma\ne\beta} in {B_g,} let {m_\gamma=\Delta(\beta,\gamma)} and {h_\gamma=r_\gamma\upharpoonright(m_\gamma+1).}

Since {\gamma\in B_g,} {g=r_\beta\upharpoonright n\subseteq r_\gamma} and, by the definition of {m_\gamma,} {r_\beta\upharpoonright m_\gamma=r_\gamma\upharpoonright m_\gamma,} but {r_\beta(m_\gamma)\ne r_\gamma(m_\gamma),} so {n\le m_\gamma.}

Since {B_g} is uncountable, there is an uncountable {B\subseteq B_g,} an {m<\omega} and an {h\in{}^{<\omega}2} such that for all {\gamma\in B,} {\gamma\ne\beta,} ({g\subseteq r_\gamma,}) {m=\Delta(\beta,\gamma),} and {h=r_\gamma\upharpoonright(m+1),} so {h\subseteq r_\gamma,} and it follows that {B\subseteq B_h.} Then {B_h} is uncountable and, since {\delta\in C,} {\delta=\sup(B_h\cap\delta).} Note that {n\le m.}

Let

\displaystyle F=\{\gamma<\delta: e_\beta(\gamma)\le m\}.

Note that {F} is finite, since {e_\beta} is injective. We can then find an {\alpha\in B_h\cap\delta} with {F\subseteq\alpha.} Note that {\alpha\in A.}

Since {\alpha\in B_h,} then {h\subseteq r_\alpha.} Since {h\upharpoonright m=r_\beta\upharpoonright m} and {h(m)\ne r_\beta(m),} then {\Delta(\alpha,\beta)=m.} Since {e_\beta(\delta)=n} and {n\le m,} then {\Gamma(\alpha,\beta)\ne\emptyset.}

Finally, if {\gamma\in[\alpha,\delta)} then, since {F\subseteq\alpha,} we must have {e_\beta(\gamma)>m.} It follows that {\delta=\min(\Gamma(\alpha,\beta)),} so {f(\alpha,\beta)=\delta.} This shows that {\delta\in f''[A]^2.} Since {\delta\in C} was arbitrary, it follows that {C\subseteq f''[A]^2,} and we are done. \Box

The result also holds for many larger cardinals. For example, we have the following generalization obtained independently by Shelah and {\mbox{Todor\v cevi\'c}.} The proof below is Shelah’s.

Theorem 5 (Shelah, {\mbox{\bf Todor\v cevi\'c}}) Suppose {\lambda} is an uncountable regular cardinal and there is some nonreflecting stationary subset of {\lambda.} Then {\lambda\not\rightarrow[\lambda]^2_\lambda.}

Proof: We use the method of walks.

Fix {S\subseteq\lambda} stationary and nonreflecting; we may assume that all the ordinals in {S} are limit ordinals. For each nonzero {i<\lambda} choose {C_i\subseteq i} so that:

  1. {C_{i+1}=\{0,i\}.}
  2. If {i} is limit, {C_i\subseteq i} is club in {i} and disjoint from {S,} {0\in C_i,} and any point of {C\setminus C'} is a successor ordinal.

Fix a partition {S=\bigcup_{\xi<\lambda}S_\xi} of {S} into stationary sets.

Given {\alpha<\beta} in {\lambda} define {\gamma_l^+(\alpha,\beta),} {\gamma_l^-(\alpha,\beta)} by induction on {l<\omega:}

  1. {\gamma^+_0(\beta,\alpha)=\beta,} {\gamma^-_0(\beta,\alpha)=0.}
  2. If {\gamma^+_l(\beta,\alpha)} is defined and strictly larger than {\alpha,} let

    \displaystyle \gamma^+_{l+1}(\alpha,\beta)=\min(C_{\gamma^+_l(\alpha,\beta)}\setminus\alpha),

    and

    \displaystyle \gamma^-_{l+1}(\alpha,\beta)=\sup(C_{\gamma^+_l(\alpha,\beta)}\cap\alpha).

  3. Let {k=k(\alpha,\beta)} be the least {k} such that {\gamma^+_k(\alpha,\beta)=\alpha.} At this point, the construction stops.

We can think of the sequence of {\gamma^+_l(\alpha,\beta)} as describing a walk from {\beta} down to {\alpha} through the ladders {C_i.} Note that {k} is well-defined, since the {\gamma^+_l(\alpha,\beta)} form a decreasing sequence of ordinals.

Note that if {0<\alpha<\beta} are in {\lambda} and {l<k(\alpha,\beta),} then {\gamma^-_l(\alpha,\beta)<\alpha<\gamma^+_l(\alpha,\beta).} For {k=k(\alpha,\beta),} we have {\gamma^-_k(\alpha,\beta)\le\alpha=\gamma^+_k(\alpha,\beta),} and equality occurs only if {\alpha\in C'_{\gamma^+_{k-1}(\alpha,\beta)}.}

Suppose {0<\alpha<\beta} are in {\lambda.} Let {m\le k(\alpha,\beta).} Set

\displaystyle \epsilon=\epsilon_m(\alpha,\beta)=\max\{\gamma^-_l(\alpha,\beta)+1:l\le m\}.

Then {\epsilon\le\alpha+1} and, if {\epsilon\le\alpha,} then

  • {\gamma^+_l(\alpha,\beta)=\gamma^+_l(\xi,\beta)} and {\gamma^-_l(\alpha,\beta)=\gamma^-_l(\xi,\beta)} for all {\xi\in[\epsilon,\alpha]} and {l\le m.}

Now define {d:[\lambda]^2\rightarrow\lambda} as follows: Given {0<\alpha<\beta} in {\lambda,} let {m\le k(\alpha,\beta)} be largest such that, letting {\epsilon_l=\epsilon_l(\alpha,\beta)} for all {l\le m,}

  1. {\epsilon_m<\alpha,}
  2. {\gamma_l^-(\epsilon_j,\alpha)=\gamma_l^-(\epsilon_j,\beta)} for all {l\le j\le m,} and
  3. {\gamma^+_m(\alpha,\beta)\in S,}

if such an {m} exists, and in that case let {d(\alpha,\beta)} be the unique {\xi} such that {\gamma^+_m(\alpha,\beta)in S_\xi.} Otherwise let {d(\alpha,\beta)=0.}

(The strange looking condition 2 will be used at the end of the argument. For now, notice that if {m} does not satisfy conditions 1 and 2, then no larger {m'} can satisfy them either.)

Let now {Y\in[\lambda]^\lambda} and {\xi<\lambda} be given. We need {\alpha<\beta} in {Y} with {d(\alpha,\beta)=\xi.}

Consider the model {M=(\lambda,<,Y,R),} where {R(i,j)} holds iff {i\in C_j.} Let {(N_i:i<\lambda)} be a continuous increasing sequence of elementary substructures of {M} with {|N_i|<\lambda} and {i \in N_{i+1}} for all {i<\lambda.}

Note that there is a club of ordinals {\delta} such that {N_\delta=\delta.} This is because both {(N_i:i<\lambda)} and {(i:i<\lambda)} are filtrations of {\lambda.}

Definition 6 A filtration of {\lambda} is a strictly increasing continuous sequence {(t_i:i<\lambda)} with union {\lambda} such that {|t_i|<\lambda} for all {i.}

(The above definition is somewhat more restrictive than the general notion of filtration one finds in algebra.) Suppose {(t_i:i<\lambda)} and {(s_i:i<\lambda)} are filtrations of {\lambda.} By regularity of {\lambda,} given any {i} we can find {j} such that {t_i\subseteq s_j,} and similarly there is some {k} such that {s_i\subseteq t_k.} By an obvious back-and-forth argument we can find a club of ordinals {i<\lambda} such that {s_i=t_i.}

In particular, {N_\delta=\delta} for club many {\delta<\lambda.} We can then find a limit ordinal {\delta\in S_\xi} such that {N_\delta=\delta.}

Choose {\beta\in Y,} {\beta>\sup(N_{\delta+1}),} so {\beta>\delta} and {k(\delta,\beta)} is defined and larger than {0.}

Let {\epsilon=\epsilon_{k(\delta,\beta)}(\delta,\beta).} We claim that {\epsilon<\delta.}

Note that if {l<k(\delta,\beta),} then {\gamma^-_l(\delta,\beta)<\delta} and therefore {\gamma^-_l(\delta,\beta)+1<\delta,} since {\delta} is limit.

If {\gamma^-_{k(\delta,\beta)}(\delta,\beta)=\delta,} then {\delta\in C_{\gamma^+_{k(\delta,\beta)-1}(\delta,\beta)}.} Since {\delta\in S,} then {\gamma^+_{k(\delta,\beta)-1}(\delta,\beta)} is a successor ordinal, and must therefore be {\delta+1.} Hence {\gamma^-_{k(\delta,\beta)}(\delta,\beta)=0\ne\delta.} This is the only place in the argument where we use the assumption that {S} is nonreflecting.

Thus for all {l\le k(\delta,\beta),} {\gamma^-_l(\delta,\beta)+1<\delta.} Therefore {\epsilon<\delta,} as claimed.

Let {\varphi (x, y)} be the first-order formula in the language of {M} with parameters {\gamma_l^-(\delta,\beta)} for all {l\le k(\delta,\beta),} asserting that, letting {k=k(\delta,\beta)} and {\epsilon_l=\epsilon_l(\delta,\beta)} for all {l\le k,} we have that:

  • {y} is limit,
  • {x\in Y,}
  • {\epsilon_k<y<x,}
  • {\gamma^-_l(y,x)=\gamma_l^-(\epsilon_j,x)=\gamma^-_l(\delta,\beta)} for all {l\le j\le k(\delta,\beta),} and
  • {\gamma^+_k(y,x)=y.}

(That there is such a formula takes but a moment’s thought and is best argued by induction on {l .} The strange looking condition 4 is the counterpart of condition 2 in the definition of {d,} and will be used towards the end of the argument.)

Note all the parameters in {\varphi} belong to {N_\delta,} and {M\models \varphi(\beta,\delta),} since {\epsilon<\delta.}

Recall that {\delta\in N_{\delta+1}\setminus N_\delta} and {\beta>\sup(N_{\delta+1}).} Let {\rho\in N_{\delta+1}.} Then

\displaystyle M\models\exists x'>\rho\,\varphi(x',\delta)

so, by elementarity, the same holds in {N_{\delta+1}.} Since {\rho} was arbitrary,

\displaystyle N_{\delta+1}\models\forall x\,\exists x'>x\,\varphi(x',\delta).

Now let {\eta\in N_\delta.} Then

\displaystyle N_{\delta+1}\models\exists y'>\eta\,\forall x\,\exists x'>x\,\varphi(x',y').

By elementarity, the same holds in {N_\delta} and, since {\eta} was arbitrary, then

\displaystyle N_\delta\models\forall y\,\exists y'>y\,\forall x\,\exists x'>x\,\varphi(x',y').

Therefore there are {\delta'<\beta'} in {N_\delta} such that {M\models\varphi(\beta',\delta'),} and {(\delta',\beta')\cap C_\delta\ne\emptyset.}

For all {l\le k(\delta,\beta),} since {\epsilon<\delta'<\beta'<\delta,} we have that {\gamma^-_l(\beta',\beta)=\gamma^-_l(\delta,\beta)=\gamma^-_l(\epsilon,\beta),} and {\gamma^+_l(\beta',\beta)=\gamma^+_l(\delta,\beta)=\gamma^+_l(\epsilon,\beta).}

In particular, {\epsilon_l(\beta',\beta)=\epsilon_l(\delta,\beta)\le\epsilon} for all {l\le k(\delta,\beta),} and {\gamma^+_{k(\delta,\beta)}(\beta',\beta)=\delta,} and therefore {k(\delta,\beta)<k(\beta',\beta).}

We claim that {d(\beta',\beta)=\xi.}

To see this, notice that if {k=k(\delta,\beta),} then:

  • {k<k(\beta',\beta).}
  • {\epsilon_k(\beta',\beta)=\epsilon<\beta'.}
  • {\gamma_l^-(\epsilon_j,\beta')=\gamma_l^-(\delta,\beta)=\gamma_l^-(\epsilon_j,\beta)} for all {l\le j\le k,} since {M\models\varphi(\beta',\delta'),} and {\epsilon=\epsilon_k(\delta,\beta)<\delta.} Here, {\epsilon_j} denotes {\epsilon_j(\delta,\beta)=\epsilon_j(\beta',\beta)} for all {j\le k.}
  • {\gamma^+_k(\beta',\beta)=\delta\in S.}

This means that {k} satisfies the requirements of {m} in the definition of {d(\beta',\beta).}

On the other hand, {\gamma^-_{k+1}(\beta',\beta)=\sup(C_\delta\cap\beta')} and, since {(\delta',\beta')\cap C_\delta\ne\emptyset,} it is larger than {\delta'.}

But then no {m'\in[k+1,k(\beta',\beta)]} satisfies the requirements of {m} in the definition of {d(\beta',\beta).} To see this, note that

\displaystyle \epsilon_{k+1}(\beta',\beta)>\gamma^-_{k+1}(\beta',\beta)>\delta'.

If {\epsilon_{m'}(\beta',\beta)<\beta',} then

\displaystyle \gamma_l^- (\beta', \beta)= \gamma_l^- (\epsilon_{j} (\beta', \beta), \beta)

for all {l\le j\le m',} in particular for {l=j=k+1.}

However, we must also have {\gamma^+_k(\epsilon_{k+1}(\beta',\beta),\beta')=\gamma^+_k(\epsilon_k(\beta',\beta),\beta')=\gamma^+_k(\delta',\beta')=\delta',} so

\displaystyle \gamma^-_{k+1}(\epsilon_{k+1}(\beta',\beta),\beta')\le \delta'.

This means that in the definition of {d(\beta',\beta),} {m=k(\delta,\beta),} and {\gamma^+_m(\beta',\beta)=\delta.} Since {\delta\in S_\xi,} we are done. \Box

Corollary 7 If {\lambda} is regular, {\lambda^+\not\rightarrow[\lambda^+]^2_{\lambda^+}.}

Proof: The set {S^{\lambda^+}_\lambda} is stationary and nonreflecting. This is because {\alpha\cap S^{\lambda^+}_\lambda} consists of ordinals of cofinality {\lambda} for any {\alpha<\lambda^+.} If {C\subseteq\alpha} is a club set of minimal order type, such that every ordinal in {C\setminus C'} is a successor, then no ordinal in {C} has cofinality {\lambda} and therefore {C} avoids {\alpha\cap S^{\lambda^+}_\lambda.} \Box

This implies that {\aleph_n\not\rightarrow[\aleph_n]^2_{\aleph_n}} for all nonzero {n\in\omega.}

The situation for {\omega} is different, and we turn to it before moving to larger cardinals.

The argument of Theorem 5 makes use of (basic) ideas from mathematical logic. This is a very useful tool in combinatorial set theory, and more substantial applications will be encountered in future lectures.

2. Canonical partitions

Definition 8 Let {0<r\in\omega,} let {F} be a set, and let {L\subset r.} A function {f: [\omega]^r \rightarrow F} is {L}-canonical on {B\subseteq\omega} iff whenever {x=\{x_0,\dots,x_{r-1}\}} and {y=\{y_0,\dots,y_{r-1}\}} are subsets of {B,} then {f(x)=f(y)} iff {x_i=y_i} for all {i\in L.}

(Compare with the discussion of canonical relations in {\S2.2} of lecture III.1.)

Here are some examples; suppose that {f: [\omega]^r \rightarrow F} and that {f} is {L}-canonical on {B .} Then:

  1. {L=\emptyset} iff {f} is constant on {B .}
  2. {L=r} iff {f} is injective on {B .}
  3. {L=\{0\}} iff {B} is (strictly) min-homogeneous, i.e., whenever {x,y\in[B]^r,} then {f(x)=f(y)} iff {\min(x)=\min(y).}
  4. {L=r-1=r\setminus\{r-1\}} iff {B} is (strictly) end-homogeneous, i.e., {f(x)=f(y)} iff {x\setminus\max(x)=y\setminus\max(y).}
  5. {L=\{r-1\}} iff {B} is (strictly) max-homogeneous, i.e., {f(x)=f(y)} iff {\max(x)=\max(y).}

(The nonstrict versions are obtained by replacing equivalence with implication: {B} is min-homogeneous iff {f(x)=f(y)} whenever {\min(x)=\min(y),} etc.)

Theorem 9 ({\mbox{\bf Erd\H os}}-Rado) If {f: [\omega]^r \rightarrow F} then there is some {B\in[\omega]^\omega} and an {L\subseteq r} such that {f} is {L}-canonical on {B .}

Note that if {F} is finite, then necessarily {L=\emptyset,} so this generalizes Ramsey’s theorem.

Theorem 10 For all {0<r\in\omega} and all {L\subseteq r} there is an {L}-canonical partition of {[\omega]^r.}

Proof: The obvious attempt is to define {f_L:[\omega]^r\rightarrow V} by

\displaystyle f_L(p)=\{q\in[\omega]^r:q\upharpoonright L=p\upharpoonright L\},

where if {p=\{p_0,\dots,p_{r-1}\}} and {q=\{q_0,\dots,q_{r-1}\},} then {q\upharpoonright L=p\upharpoonright L} means that {\forall i\in L\,(q_i=p_i).}

Clearly, if {f_L(p)=f_L(r)} then {p\upharpoonright L=r\upharpoonright L.}

Conversely, suppose {p\upharpoonright L=r\upharpoonright L.} Let {q\in f_L(p).} Then {q\upharpoonright L=p\upharpoonright L=r\upharpoonright L,} so {q\in f_L(r).} Hence, {f_L (p) \subseteq f_L (r).} Conversely, {f_L (r) \subseteq f_L (p) .} \Box

Recall now the ultrafilter proof of Ramsey’s theorem from {\S2.5} of lecture III.1. We showed there that if {{\mathcal U}} is a nonprincipal ultrafilter over {\omega} and {f: [\omega]^r \rightarrow F} for some finite {F,} then there is some infinite set {M\subseteq\omega} and a color {i\in F} such that {f^{-1} (\{i\}) \in {\mathcal U}^k} and {[M]^k\subseteq f^{-1}(\{i\}).} Here,

\displaystyle {\mathcal U}^k=\{X\in[\omega]^k:{\mathcal U}n_0\dots{\mathcal U}n_{k-1}\,(\{n_0,\dots,n_{k-1}\}\in X)\}.

Definition 11 An ultrafilter {{\mathcal U}} over {\omega} is Ramsey iff it is nonprincipal and for all {k>0,} {{\mathcal U}^k} is generated by the sets {[M]^k} for {M\in{\mathcal U}.}

Whether there are Ramsey ultrafilters is independent of {{\sf ZFC},} and follows from {{\sf CH}.}

It follows from the definition and the argument in {\S2.5} of lecture III.1 that a nonprincipal ultrafilter {{\mathcal U}} over {\omega} is Ramsey iff for any {k>0} and any finite coloring of {[\omega]^k,} there is some {M\in{\mathcal U}} such that {[M]^k} is monochromatic.

For {r=1} we have a “Ramsey-ultrafilter” version of Theorem 9:

Homework problem 14. Let {{\mathcal U}} be a nonprincipal ultrafilter over {\omega.} Show that {{\mathcal U}} is Ramsey iff for any {f:\omega\rightarrow\omega} there is some {M\in{\mathcal U}} such that {f\upharpoonright M} is 1-1 or constant.

Now we proceed to the proof of the canonization Theorem 9:

Proof: Let {f: [\omega]^r \rightarrow F} be given. For {x=\{x_0,\dots,x_{2r-1}\}} let {g(x)} be the set of all tuples {(y_0,\dots,y_{2r-1})} where {y_0<\dots<y_{r-1}<2r,} {y_r<\dots<y_{2r-1}<2r,} and {f(x_0,\dots,x_{r-1})=f(x_r,\dots,x_{2r-1}).}

(Note that, against convention, we are not requiring that {y_{r-1}<y_r.})

Then {g} defines a coloring of {[\omega ]^{2 r}} with finitely many colors, and Ramsey’s theorem guarantees that there is some {B'\in[\omega]^\omega} such that {g\upharpoonright[B']^{2r}} is constant. Let {b_0<b_1<\dots} be the enumeration of {B'.}

Let {B=\{b_0,b_2,b_4,\dots\},} and let {L=\{n<r:\forall y,y'\in[B']^r,(} if {y\upharpoonright r\setminus\{n\}=y'\upharpoonright r\setminus\{n\}} and {y_n\ne y'_n,} then {f(y)\ne f(y'))}.}

We claim that {f} is {L}-canonical on {B .}

Step 1: Suppose {y,y'\in[B]^r} and {y\upharpoonright L=y'\upharpoonright L.} We need to prove that {f(y)=f(y').}

For this, we define a transformation {T: ([B ]^r )^2 \rightarrow ([B ]^r )^2} as follows:

  • If {y=y'} then {T(y,y')=(y,y').}
  • Otherwise, let {n} be least such that {y_n\ne y'_n} (so {n\notin L}.) Let {z,z'\in[B]^r} be such that {z\upharpoonright r\setminus\{n\}=y\upharpoonright\setminus\{n\},} {z'\upharpoonright r\setminus\{n\}=y'\upharpoonright\setminus\{n\},} and {z_n = z'_n = \min \{ y_n, y'_n \}.} Then, by definition of {L,} {f(z)=f(y)} and {f(z')=f(y').} We then set {T(y,y')=(z,z').}

Iterating {T} we see that {T^r(y,y')=(w,w)} for some {w\in[B]^r} such that {f(y)=f(w)=f(y'),} and we are done.

Step 2: Conversely, suppose that {x,x'\in[B]^r,} that {n\in L,} and that {x_n<x_n'.} We need to prove that {f(x)\ne f(x').}

Assume otherwise. Define an equivalence relation on pairs of elements of {[B']^r} by setting {(p,p')\equiv(q,q')} for {p,p',q,q'\in[B']^r,} iff there is an order isomorphism {phi:p\cup p'\rightarrow q\cup q'} such that {\phi''p=q} and {\phi''p'=q'.}

The following is immediate from the fact that {B'} is homogeneous for {g :}

Lemma 12 Suppose that {p,p',q,q'in[B']^r,} that {f(p)=f(p'),} and that {(p,p')\equiv(q,q').} Then {f(q)=f(q').} {\Box }

For {t\ge1} let {B_t=\{b_0,b_t,b_{2t},\dots\}.} For {s>r} let {x_0,x_1\in[B_{r^s}]^r} be such that {(x_0,x_1)\equiv(x,x').}

Then there is:

  • An {x_2\in [B_{r^{s-1}}]^r} such that {(x_0,x_1)\equiv(x_1,x_2).}
  • An {x_3\in[B_{r^{s-2}}]^r} such that {(x_1,x_2)\equiv(x_2,x_3).}
  • {\vdots}
  • An {x_s\in[B_r]^r} such that {(x_{s-2},x_{s-1})\equiv(x_{s-1},x_s).}

Say that {x_i^0<\dots<x_i^{r-1}} enumerates {x_i.} Then, by definition of {\equiv,} and recalling that {x_n<x_n',} we have that {x_0^n<\dots<x_s^n.}

Since {s>r,} we can then find {i_0} with {1\le i_0\le s} such that {x_{i_0}^n\ne x_0^m} for {m<r.} Let {j} be such that {x^n_{i_0}=b_{2j}.}

Define {z_{i_0}\in[B]^r} by setting {z_{i_0}\upharpoonright r\setminus\{n\}=x_{i_0}\upharpoonright r\setminus\{n\},} and {z_{i_0}^n=b_{2j+1}.}

Note that since {n\in L,} then {f(x_{i_0})\ne f(z_{i_0}).}

However, by choice of {i_0} and the definition of {z_{i_0},} we have that {(x_0,x_1)\equiv(x_{i_0-1},x_{i_0})} and {(x_0,x_{i_0})\equiv(x_0,z_{i_0}),} and therefore (since {B'} is homogeneous for {g}) {f(x_0)=f(x_1)=\dots=f(x_{i_0})} and (by Lemma 12) {f(x_{i_0})=f(x_0)=f(z_{i_0}),} contradiction. \Box

It follows immediately that {\omega\rightarrow[\omega]^2_\omega:} Let {f:[\omega]^2\rightarrow\omega.} We can then find {B\in[\omega]^\omega} and {L\subseteq 2} such that {f} is {L}-canonical on {B .} If {L=\emptyset,} then {f\upharpoonright[B]^2} is constant. For {L\ne\emptyset,} by passing to an appropriate proper subset of {B} we necessarily make the range of {f} smaller. In either case, we find an infinite subset {H} of {\omega} such that {f'' [H ]^2 \ne \omega.}

We can extract a bit of additional information from the proof of Theorem 9 without too much effort. I state the result without proof.

Definition 13 Let {A,Bin[omega]^omega} and consider a coloring {f: [Acup B ]^r rightarrow F.}

Say that {(f,A)} is invariant iff whenever {p,q,p',q'in[A]^r} and {(p,q)equiv(p',q')} with {equiv} as in the proof of Theorem 9 above, then {f(p)=f(q)} iff {f(p') = f(q').}

Say that {(f,A)} is isomorphic to {(f,B),} {(f,A)cong(f,B),} iff whenever {p,qin[A]^r} and {phi:Arightarrow B} is the unique order isomorphism, then {f(p)=f(q)} iff {f(phi''p)=f(phi''q).}

Say that {(f,A)} is stationary iff {(f,A)cong(f,B)} for all {Bin[A]^omega.}

Then we have:

Theorem 14 (Rado) The following are equivalent for {Ain[omega]^omega} and {f:[A]^rrightarrowomega:}  

 

 

  1. {(f,A)} is invariant.
  2. {(f,A)} is stationary.
  3. {f} is {L}-canonical on {A} for some {Lsubseteq r.} {Box }

 

3. Colorings of pairs. II

Magidor has shown that, consistently, every stationary subset of {aleph_{omega+1}} may reflect. Therefore we cannot apply Theorem 5 to conclude that {aleph_{omega+1}notrightarrow[aleph_{omega+1}]^2_{aleph_{omega+1}}.} Fortunately, this case is covered by another result of {mbox{Todorv cevi'c}.}

Recall from Theorem 20 in lecture II.12 that for every singular cardinal {lambda} there is an increasing sequence {(lambda_i:i<{rm cf}(lambda))} of regular cardinals cofinal in {lambda} such that

displaystyle {rm tcf}(prod_ilambda_i,<_{b,{rm cf}(lambda)})=lambda^+,

i.e., there is a sequence {(f_alpha:alpha<lambda^+)} where each {f_alphainprod_ilambda_i,} and we have that {f_alpha<_{b,{rm cf}(lambda)}f_beta} whenever {alpha<beta<lambda^+,} and that for any {finprod_ilambda_i} there is some {alpha} such that {f<_{b,{rm cf}(lambda)}f_alpha,} where {g<_{b,{rm cf}(lambda)}h} iff for all but boundedly many {i<{rm cf}(lambda),} we have that {g(i)<h(i).}

We call such a tuple {(veclambda_i,vec f_alpha)} a scale for {lambda.}

Theorem 15 ({mbox{Todorv cevi'c}}) Suppose that {lambda} is a singular cardinal and that {(veclambda_i,vec f_alpha)} is a scale for {lambda} such that {lambda_inotrightarrow[lambda_i]^2_{lambda_i}} for all {i<{rm cf}(lambda).} Then also {lambda^+notrightarrow[lambda^+]^2_{lambda^+}.} {Box }

I omit the proof of Theorem 15 (which also uses an elementary substructures argument); see for example the paper by Burke and Magidor cited at the end. Instead, I briefly describe the witnessing coloring:

For each {i<{rm cf}(lambda),} let {c_i:[lambda_i]^2rightarrowlambda_i} witness {lambda_inotrightarrow[lambda_i]^2_{lambda_i}.} Consider the map {d:[lambda^+]^2rightarrow{rm cf}(lambda)} where {d(alpha,beta)} is the largest {i<{rm cf}(lambda)} such that {f_beta(i)<f_alpha(i)} if such {i} exists, and {d (alpha, beta)= 0} otherwise.

Now let {c:[lambda^+]^2rightarrowlambda} be the coloring given by {c(alpha,beta)=c_i(f_beta(i),f_alpha(i)),} where {i=d(alpha,beta),} if {i>0,} and {c(alpha,beta)=0} otherwise.

One then proceeds to show that {c} witnesses {lambda^+notrightarrow[lambda^+]^2_lambda.} To conclude, the following “stepping up” argument can now be invoked:

Lemma 16 Suppose that {lambda} is an infinite cardinal and that {lambda^+notrightarrow[lambda^+]^2_lambda.} Then also {lambda^+notrightarrow[lambda^+]^2_{lambda^+}.}

Proof: Given {c} witnessing {lambda^+notrightarrow[lambda^+]^2_lambda,} let {i_beta:betarightarrowlambda} be an injection for all {beta<lambda^+,} and set {c^*:[lambda^+]^2rightarrowlambda^+} by {c^*(alpha,beta)=i_beta^{-1}(c(alpha,beta)),} if {c(alpha,beta)in{rm ran}(i_beta),} and {c^*(alpha,beta)=0} otherwise.

To see that {c^*} works, let {Xin[lambda^+]^{lambda^+},} and fix {deltainlambda^+.} Let {Y=Xcap(delta,lambda^+),} so {|Y|=lambda^+} but {{i_beta(delta):betain Y}subseteqlambda.} It follows that there is some {eta<lambda} such that

displaystyle |{betain Y:i_beta(delta)=eta}|=lambda^+.

But now we can conclude that there are {alpha<beta} in {Y} such that {i_beta(delta)=eta} and {c(alpha,beta)=eta.} Thus {c^*(alpha,beta)=delta,} and we are done. Box

Notice that the result applies to all singular cardinals {lambda} in a large initial segment of the sequence of cardinals, for example, it applies to all {lambda} below the first weakly inaccessible cardinal.

An analysis of the argument showing that {c} indeed works led Shelah to isolate a family of combinatorial principles from which the following result follows:

Theorem 17 (Shelah) If {lambda} is singular, then {lambda^+notrightarrow[lambda^+]^2_{{rm cf}(lambda)}.} {Box }

Shelah has also shown that {lambdanotrightarrow[lambda]^2_omega} for many inaccessible cardinals (for example, for any cardinal that is inaccessible but not Mahlo.) Further results have been obtained by Eisworth and Shelah.

It is still open whether there can be a successor cardinal {lambda^+} (necessarily, the successor of a singular) such that {lambda^+rightarrow[lambda^+]^2_{lambda^+}.}

Before {mbox{Todorv cevi'c}} transformed the area with his results, some particular cases were known. The following is from 1965:

Theorem 18 ({mbox{ErdH os}}-Hajnal-Rado) If {2^kappa=kappa^+,} then {kappa^+notrightarrow[kappa^+]^2_{kappa^+}.}

Proof: Using that {2^kappa=kappa^+,} let {(X_alpha:alpha<kappa^+)} enumerate the bounded subsets of {kappa^+} in such a manner that {X_alphasubseteqalpha.}

We claim that there is a function {f:[kappa^+]^2rightarrowkappa^+} such that for all {alpha<beta} in {kappa^+} with {kappalealpha,} and all {gamma<beta} there is {xiin X_alpha} such that {f(xi,beta)=gamma.}

Assume that {f} is such a function, let {Ain[kappa^+]^{kappa^+}} and let {gamma<kappa^+.} Find some {alpha ge kappa} such that {X_alphasubseteq A,} and let {betain A} be larger than {gamma} and than {alpha.} Then for some {xiin A} we have {f(xi,beta)=gamma,} and we are done.

To prove the claim, for each {beta>kappa} let {S_beta=[kappa,beta)timesbeta,} and list {S_beta} as {{(alpha_i,eta_i):i<kappa}.} Now define {(xi_i:i<kappa)} recursively so that {xi_iin X_{alpha_i}setminus{xi_j:j<i}} for all {i<kappa.} Now set {f(xi_i,beta)=eta_i} for all {i<kappa.} Box

The following extension of Theorem 18 shows that one can require a stronger property of the witnessing function {f:}

Theorem 19 ({mbox{ErdH os}}-Hajnal-Milner) Assume that {2^kappa=kappa^+.} Then there is {f:[kappa^+]^2rightarrowkappa^+} such that whenever {X,Y} are subsets of {kappa^+} with {|X|=kappa} and {|Y|=kappa^+,} there is {xiin X} such that {{ f ( xi, alpha) : xi< alpha in Y }= kappa^+ .}

Proof: Let {(h_alpha : alpha< kappa^+ )} enumerate all partial functions {h} with {{rm dom}(h),{rm ran}(h)subseteq kappa^+} and {|h|lekappa.}

Given {alpha<kappa^+,} let {A_alpha={beta<alpha:{rm dom}(h_beta)subseteqalpha},} and fix a bijection {g_alpha : rho_alpha rightarrow A_alpha} where {rho_alpha=|A_alpha|lekappa.}

Now, by transfinite recursion, define {(xi^alpha_nu:nu<rho_alpha)} so that

displaystyle xi^alpha_nu in {rm dom} (h_{g_alpha (nu)}) setminus {xi^alpha_mu : mu< nu}

for all {nu<rho_alpha.} Notice that this is possible, since {rho_alphalekappa=|{rm dom}(h_beta)|} for all {betain A_alpha.}

To define {f:[kappa^+]^2rightarrowkappa^+,} we set {f(xi^alpha_nu,alpha)=h_{g_alpha(nu)}(xi^alpha_nu)} for all {alpha<kappa^+} and all {nu<rho_alpha,} and let {f(beta,alpha)=0} for all {beta<alpha} not specified by this rule.

We claim that {f} is as wanted. Suppose otherwise, and pick counterexamples {X,Ysubseteqkappa^+} with {|X|=kappa} and {|Y|=kappa^+.} Define {h:Xrightarrowkappa^+} by picking

displaystyle h(xi)notin{f(xi,alpha):xi<alphain Y}

for all {xiin X.}

Let {beta<kappa^+} be such that {h=h_beta} and pick {alphain Y} such that {beta<alpha} and {Xsubseteqalpha.} Let {xi=xi^alpha_nu} for the unique ordinal {nu<rho_alpha} such that {g_alpha(nu)=beta.} Then, by construction, {f(xi,alpha)=h_beta(xi)=h(xi).} But this contradicts the definition of {h,} and we are done. Box

One sometimes writes {[ X, Y]} for {{{x,y}:xne y} and {xin X} and {yin Y}} and {Xotimes Y} for { { { x , y } : x < y} and {xin X} and {yin Y}.} The conclusion of the theorem above can then be stated as saying that {f''[X,Y]=kappa^+} or even that {f''(Xotimes Y)=kappa^+} for all suitable {X,Y.}

Corollary 20 Assume {{sf CH}} and let {W} be an outer model with the same reals. Then there is in {V} a sequence {(S_alpha:alpha<omega_1)} of pairwise disjoint stationary subsets of {omega_1} all of which remain stationary in {W.}

Notice that this is obvious if we just require that there is some pairwise disjoint collection in {W} of size {omega_1} consisting of stationary subsets of {omega_1,} all of which belong to {V.} This weaker version is an obvious consequence of the existence of {omegatimesomega_1} Ulam matrices in {V,} does not require {{sf CH}} to hold in {V,} and only needs that {omega_1^W=omega_1.}

Proof: With {f} defined in {V} as in Theorem 19 for {kappa^+=omega_1,} note that {f} also satisfies the conclusion of Theorem 19 in {W,} since any countable partial function from {omega_1} to itself in {W} belongs to {V.}

Now define {S^i_alpha={beta>alpha:f(alpha,beta)=i}} for all {i,alphainomega_1.} We claim that for some {alpha} all the sets {S^i_alpha,} {i<omega_1,} are stationary. Clearly, they are disjoint, and the result follows.

To see the claim, assume otherwise. Then for each {alpha} we can find {i_alpha<omega_1} and a club {C_alphasubseteqomega_1} disjoint from {S^{i_alpha}_alpha.} Now set {C=bigtriangleup_alpha C_alpha.} This is an uncountable (in fact, a club) set, so there is some {alpha} such that

displaystyle {f(alpha,beta):beta>alphambox{ and }betain C}=omega_1.

In particular, there is some {beta_alphain C} such that {f(alpha,beta_alpha)=i_alpha.} But {beta_alphain C} and {alpha<beta_alpha,} so {beta_alphain C_alpha} and we are forced to conclude that {f(alpha,beta_alpha)ne i_alpha,} contradiction. Box

It is worth pointing out that {mbox{Todorv cevi'c}'s} original proof of Theorem 4 implies, by a similar argument, the following version of Corollary 20 that does not depend on {{sf CH} :}

Theorem 21 Assume that {W} is an outer model and that {omega_1^W=omega_1.} Then there is in {V} a sequence {(S_n:n<omega)} of pairwise disjoint subsets of {omega_1,} all of which are stationary in {W.} {Box }

On the other hand, Paul Larson has shown that the conclusion of Corollary 20 (that there is such a sequence of length {omega_1}) fails in this generality. Larson’s argument builds a forcing extension of {V} in which reals are added and {{mathcal P}(omega_1)} is collapsed. It is open whether Corollary 20 holds without the assumption of {{sf CH}} but assuming that no reals are added and no cardinals are collapsed.

Note also that the proofs given above of Theorems 4 and 5 do not allow us to conclude Theorem 21, since both constructions depend on a partition into disjoint stationary sets.

In this regard, I should mention here the following recent result of Justin Moore. Moore’s construction allowed him to solve the {L}-space problem and settle several famous problems in set theory and set theoretic topology. Moreover, just as {mbox{Todorv cevi'c}}‘s original proof, Moore’s argument is sufficiently absolute that the function he builds satisfies the conclusion of Theorem 22 in any outer model with the same {omega_1.}

Theorem 22 (Moore) There is a function {f:[omega_1]^2rightarrowomega_1} such that whenever {A , B in [ omega_1 ]^{omega_1} ,} we have that {f''(Aotimes B)=omega_1.} {Box }

I find it impossible to resist mentioning that Magidor has reproved Corollary 20 with a remarkably short argument. I proceed to include it below; once again, thanks to Assaf Rinot for showing me this result.

Theorem 23 (Magidor) Let {lambda} be a cardinal, assume that {2^lambda=lambda^+,} and let {W} be an outer model such that {{mathcal P}^W(lambda)={mathcal P}(lambda).} Then for every stationary {Ssubseteqlambda^+} in {V} that remains stationary in {W,} there exists in {V} a silly diamond sequence for {S} over {W,} that is, a sequence {(A_delta:deltain S)in V} such that, in {W,} {{deltain S:A_delta=X}} is stationary for all {Xsubseteqlambda.}

Proof: Working in {V,} let {(Y_alpha:alpha<lambda^+)} enumerate {{mathcal P}(lambdatimeslambda).} Given {delta<lambda^+,} let {(Y^i_delta:i<lambda)} enumerate {{Y_alpha:alpha<delta).}

For {deltain S,} set

displaystyle A^i_delta={alpha<lambda:(i,alpha)in Y^i_delta}

for all {i<lambda.} It is enough to check that for some {i<lambda,} {(A^i_delta:deltain S)} is as wanted.

To see this, assume otherwise. Working in {W,} pick {X^isubseteqlambda} and {C^isubseteqlambda^+} for all {i<lambda,} so that {A^i_deltane X^i} for all {deltain Scap C^i.} Now set {Y=bigcup_i{i}times X^i.} Since {Yin V,} there is some {alpha<lambda^+} such that {Y=Y_alpha.} Let {deltain Scapbigcap_i C^i} be larger than {alpha,} and let {j<lambda} be such that {Y=Y^j_delta.} Then {A^j_delta={alpha<lambda:(j,alpha)in Y}=X^j.} However, {deltain Scap C^j,} contradiction. Box

Corollary 24 Assume {2^lambda=lambda^+} and let {W} be an outer model with {{mathcal P}^W(lambda)={mathcal P}(lambda).} Then there is in {V} a partition of {S^{lambda^+}_{{rm cf}(lambda)}} into {lambda^+} stationary sets, all of which remain stationary in {W.}

Proof: Note that the assumption guarantees that {(S^{lambda^+}_{{rm cf}(lambda)})^W=S^{lambda^+}_{{rm cf}(lambda)}.}

Let {(A_delta:deltain S^{lambda^+}_{{rm cf}(lambda)})} be a silly diamond sequence for {S^{lambda^+}_{{rm cf}(lambda)}} over {W.} For {Xsubseteqlambda} let

displaystyle S_X={deltain S^{lambda^+}_{{rm cf}(lambda)}:A_delta=X}.

Then {S_X} is stationary in {W.} Since {(S_X:Xsubseteqlambda)} lies in {V,} we are done. Box

To conclude, I want to mention briefly what the situation is at singular cardinals.

Theorem 25 Let {kappa} be a singular cardinal and let {r>1} be an integer. Then {kappanotrightarrow[kappa]^r_{2^{r-1}}.}

Proof: Let {kappa=bigsqcup_{xi<{rm cf}(kappa)}X_xi} be a partition of {kappa} into {{rm cf}(kappa)} many sets of size smaller than {kappa.} Given {xin[kappa]^r,} let {xi_0(x)<dots<xi_{k(x)}(x)} be the ordinals {xi} such that {x cap X_xi ne emptyset ,} and set

displaystyle {rm typ}(x)=(|xcap X_{xi_i(x)}|:ile k(x)).

Note that the numbers in the sequence {{rm typ}(x)} are nonzero and add up to {r.}

Lemma 26 For any integer {rge1,} let {A(r)} be the set of all sequences {(m_0,dots,m_k)} where {k0} is an integer, and {sum_i m_i=r,} and let {N_r = |A (r)| .} Then {N_r=2^{r-1}.}

Proof: We may as well define {N_0,} noting that {N_0=|{emptyset}|=1.} Note also that {N_1=1.} For {r>1} and {0<ile r,} let {A_i} be the set of all sequences in {A(r)} with {m_0=i.} Then {|A_i| = N_{r- i}} and

displaystyle N_r=|A(r)|=|bigsqcup_{1le ile r}A_i|=sum_{i=1}^r N_i.

The result follows now by an obvious induction. Box

It follows that there are {N_r=2^{r-1}} possible values for {{rm typ}(x),} and we can then define {f:[kappa]^rrightarrow A(r)} by {f (x) = {rm typ} (x) .}

If {Xin[kappa]^kappa,} there are at least {r} different ordinals {xi<{rm cf}(kappa)} such that {|Xcap B_xi|ge r,} and it follows that {A(r)=f''[X]^r.} Box

On the other hand, a version of the Canonization theorem for singular cardinals allows one to show the following:

Theorem 27 Let {kappa} be an infinite cardinal such that {kapparightarrow(kappa)^2.} Let {lambda} be singular strong limit of cofinality {kappa.} For any integer {r>1} and any {tauin(2^{r-1},lambda),} we have 

 

 

displaystyle lambdarightarrow[lambda]^r_{tau,2^{r-1}},

i.e., for any coloring {f:[lambda]^rrightarrowtau} there is an {Xin[lambda]^lambda} such that {|f''[X]^r|le2^{r-1}.} {Box }

As we will see in future lectures, other than {omega,} the cardinals {kappa} such that {kapparightarrow(kappa)^2} (the weakly compact cardinals) are strongly inaccessible. I suspect that stronger versions of Theorem 27 should be known (with weaker large cardinal restrictions on {kappa} or without the strong limit assumption on {lambda}), and would be glad to hear of any references.

Bibliography

Here are some references consulted while preparing this note:

  • Maxim Burke, Menachem Magidor, Shelah’s pcf theory and its applications, Annals of Pure and Applied Logic, 50 (1990), 207–254.
  • Todd Eisworth, Successors of singular cardinals, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., forthcoming.
  • Paul {mbox{ErdH os},} András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: partition relations for cardinals, North-Holland (1984).
  • Akihiro Kanamori, The higher infinite, Springer (1994).
  • Richard Rado, Note on canonical partitions, Bulletin of the London Mathematical Society, 18 (1986), 123-126.
  • Assaf Rinot. Surprisingly short, unpublished note; version of April 3, 2009. Available (as of this writing) at his webpage.
  • Saharon Shelah, Was Sierpinski right? I, Israel J. Math, 62 (3) (1988), 355–380.
  • Stevo {mbox{Todorv cevi'c}}, Walks on ordinals and their characteristics, Birkhäuser (2007).
  • Dan Velleman, Partitioning pairs of countable sets of ordinals, The Journal of Symbolic Logic, 55 (3) (Sep., 1990), 1019–1021.

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

This entry was posted on Thursday, April 9th, 2009 at 4:47 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.

4 Responses to 580 -Partition calculus (4)

  1. andrescaicedo says:
    April 10, 2009 at 1:33 pm

    Silly fix in the proof of Theorem 18: Rather, let (X_alpha:alpha<kappa^+) enumerate the subsets of kappa^+ of size kappa, and require that X_alphasubseteqalpha for alphagekappa.

    Reply
  2. andrescaicedo says:
    April 13, 2009 at 3:55 pm

    Ok, I see what the typo is in the proof of Theorem 9 (sorry about the confusion):

    In the first paragraph, given x of size 2r, g(x) should be the set of all (y_0,y_1,dots,y_{2r-1}) such that:
    * {y_0,dots,y_{r-1}} and {y_r,dots,y_{2r-1}} are in [2r]^r, and
    * f(x_{y_0},dots,x_{y_{r-1}})=f(x_{y_r},dots,x_{y_{2r-1}}).

    Reply
  3. 580 -Partition calculus (5) « Teaching page says:
    April 21, 2009 at 11:32 pm

    […] the Shelah- results from last lecture, we have: Theorem 6 (Shelah, ) If is the successor of a regular cardinal (or simply if is […]

    Reply
  4. 580 -Partition calculus (5) « A kind of library says:
    September 10, 2012 at 11:49 am

    […] the Shelah- results from last lecture, we have: Theorem 6 (Shelah, ) If is the successor of a regular cardinal (or simply if is […]

    Reply

Leave a comment