580 -Partition calculus (2)

1. Infinite exponents

Last lecture we showed that {\omega\rightarrow(\omega)^m_n} for any {m,n<\omega.} Later, we will see that for any {\lambda,\rho} and any {m<\omega} there is {\kappa} such that {\kappa\rightarrow(\lambda)^m_\rho.} On the other hand (recall we are assuming choice), there are no nontrivial positive partition relations {\kappa\rightarrow(\lambda_i)^\tau_{i<\rho}} with {\tau} infinite.

(To avoid vacuously true statements, we are always assuming implicitly that {\kappa\rightarrow(\lambda_i)^\tau_{i<\rho}} requires {\kappa\ge\lambda_i\ge\tau} for at least one {i<\rho.})

Theorem 1 ({\mbox{Erd\H os}}-Rado) For all {\kappa} and all infinite {\tau,} {\kappa\not\rightarrow(\tau)^\tau.}

 
Proof: It is enough to show that {\kappa\not\rightarrow(\aleph_0)^{\aleph_0}.} In effect, if {\kappa\rightarrow(\tau)^\tau} holds and {\tau>\aleph_0,} we may assume that {\kappa>\tau} is regular, so any countable subset {X} of {\kappa} is bounded, and the ordinal {\sup(X)+\tau} is still strictly below {\kappa.}

For {x\in[\kappa]^\tau,} let {{}_\omega x} denote the subset of {x} consisting of its first {\omega} many members.

Now, given {f:[\kappa]^{\aleph_0}\rightarrow2,} let {g:[\kappa]^\tau\rightarrow2} be the function {g(x)=f({}_\omega x).} If {H} is homogeneous for {g} and of size {\tau,} then {{}_\omega H} is homogeneous for {f.} In effect, let {H'=H\setminus{}_\omega H,} so {|H'|=\tau.} If {x\in[{}_\omega H]^{\aleph_0},} then {f(x)=g(x\cup H')=g(H),} by homogeneity of {H.}

This shows that {\kappa\rightarrow(\tau)^\tau} for {\tau} infinite implies that there is some {\kappa'} such that {\kappa'\rightarrow(\aleph_0)^{\aleph_0},} so it is enough to show that the latter never holds. In fact, we cannot even have {\kappa\rightarrow(\omega)^\omega.} (Recall our convention that {\omega} denotes the order type and {\aleph_0} the size.)

For this, let {\kappa} be an arbitrary infinite cardinal, and let {<} be a well-ordering of {[\kappa]^\omega.} Define {f:[\kappa]^\omega\rightarrow 2} by {f(s)=0} iff {s} is the {<}-least member of {[s]^\omega,} and {f(s)=1} otherwise.

If {x\in[\kappa]^\omega} is homogeneous for {f} and {y} is the {<}-least member of {[x]^\omega,} then {f(y)=0,} so {x} is {0}-homogeneous. Now consider any infinite sequence {x_0\subsetneq x_1 \subsetneq\dots\subseteq x} of infinite subsets of {x.} Since {f(x_n)=0} for all {n,} we must have that {\dots<x_1<x_0,} contradicting that {<} is a well-order. \Box

In the presence of the axiom of choice, Theorem 1 completely settles the question of what infinite exponent partition relations hold. Without choice, the situation is different.

For example, Mathias showed that {\omega\rightarrow(\omega)^\omega} is consistent and, in fact, holds in Solovay’s model. It follows that in the presence of large cardinals, or under determinacy, {\omega\rightarrow(\omega)^\omega} holds in {L({\mathbb R}).} Amusingly, it is still open whether {{\sf AD}} suffices to obtain {\omega\rightarrow(\omega)^\omega} (not just in {L({\mathbb R}).}) This seems related to the question of whether {{\sf AD}} implies Woodin’s {{\sf AD}^+.}

Kleinberg and Seiferas studied the question of whether well-ordered choice suffices to prove Theorem 1. I believe the question is still open, but they showed that there is essentially only one instance that requires investigation, namely, whether Mathias’s partition relation {\omega\rightarrow(\omega)^\omega} is compatible with well-ordered choice. For the remainder of this lecture, we work without choice, and use the arrow notation in the sense of order types; unless otherwise stated, all variables denote ordinals. By a cardinal I mean an initial ordinal.

For {\alpha} an ordinal, let {\alpha_l} be the largest limit ordinal (or zero) not larger than {\alpha,} and let {\alpha_n} be the unique natural number such that

\displaystyle \alpha=\alpha_l+\alpha_n.

Definition 2 Let {\kappa} be an infinite cardinal. {{\sf AC}_\kappa,} {\kappa}-well-ordered choice, is the statement that every {\kappa}-sequence of nonempty sets admits a choice function.

{{\sf WOC},} well-ordered choice, is {\forall\kappa\,{\sf AC}_\kappa.}

For {R} a binary relation and {\lambda} an ordinal, an {R}-chain of length {\lambda} is a function {f} with domain {\lambda} such that {f(\alpha)R f(\beta)} whenever {\alpha<\beta<\lambda.} {{\sf DC}_\kappa,} {\kappa}-dependent choice, is the statement that for every binary relation {R,} if every {R}-chain of length less than {\kappa} can be extended to a longer {R}-chain, then there is an {R}-chain of length {\kappa.}

 

It is easy to see that, for any {\kappa,} {{\sf AC}} implies {{\sf DC}_\kappa,} which implies {{\sf AC}_\kappa.} However, {{\sf AC}_\kappa} does not imply {{\sf DC}_\kappa.} {{\sf WOC}} is strictly weaker than {{\sf AC}} but {\forall\kappa\,{\sf DC}_\kappa} implies {{\sf AC}.} Also, {{\sf WOC}} implies {{\sf DC}_\omega} but no {{\sf AC}_\kappa} suffices.

Homework 13 (Jensen) Show that {{\sf WOC}} implies {{\sf DC}_\omega.}

Recall the following monotonicity properties of the arrow notation; the only one that may need arguing is the last one, that can be proved as in the opening paragraphs of the proof of Theorem 1.

Lemma 3 Let {\kappa\ge\aleph_0} and {\gamma>1} be cardinals, and and let {\alpha} and {\beta} be ordinals such that {\alpha\le\beta\le\kappa.} Assume that {\kappa\rightarrow(\beta)^\alpha_\gamma.}

  1. If {\kappa'>\kappa,} then {\kappa'\rightarrow(\beta)^\alpha_\gamma.}
  2. If {\gamma'<\gamma,} then {\kappa\rightarrow(\beta)^\alpha_{\gamma'}.}
  3. If {\beta'<\beta,} then {\kappa\rightarrow(\beta')^\alpha_\gamma.}
  4. If {\alpha=\delta_1+\alpha'+\delta_2} and {\beta=\delta_1+\beta'+\delta_2,} then {\kappa\rightarrow(\beta')^{\alpha'}_\gamma.} {\Box}

 

Theorem 4 (Kleinberg-Seiferas) Assume {{\sf WOC}} and suppose that {\alpha\ge\omega.}

  1. If {\alpha\ge\omega+\omega} or {\beta\ge\alpha_l+\omega+\alpha_n} or {\gamma\ge\omega,} then for all {\kappa,} {\kappa\not\rightarrow(\beta)^\alpha_\gamma.}
  2. If {\alpha<\omega+\omega,} {\beta<\alpha_l+\omega+\alpha_n,} and {\gamma<\omega,} then {\omega\rightarrow(\omega)^\omega} iff there is some {\kappa} such that {\kappa\rightarrow(\beta)^\alpha_\gamma.}

 
By the proof of Theorem 1, it follows that {{\sf WOC}} plus the existence of a well-ordering of {[\omega]^\omega} implies that no infinite exponent partition relations hold.

The main use of {{\sf WOC}} in the proof below is as follows: Assuming {{\sf AC}_\kappa,} we can assign to each {\beta\in S^\kappa_\omega} a set {p_\beta\in[\kappa]^\omega} with {\sup(p_\beta)=\beta.} We also define {p_\kappa} this way if {{\rm cf}(\kappa)=\omega.} In what follows, we will always assume such an assignment has taken place.

Given any {p\in[\kappa]^\omega} and {n<\omega,} write {p(n)} for the {n}-th element of {p} in increasing order. Suppose {\sup(p)=\beta.} Define {n_p} as the least {n} such that {p_\beta(n)>p(0).} The following obvious remark will prove useful:

Lemma 5 Assume {{\sf AC}_\kappa.} Given any {p\in[\kappa]^\omega} and any {n<\omega} there is some {p'\in[p]^\omega} with {n_{p'}>n.} {\Box}

 
We need another preliminary result; its proof will be given in another lecture; the notation {\kappa\rightarrow(\alpha)^n_x} is defined in the obvious way for {x} an arbitrary set:

Theorem 6 ({\mbox{Erd\H os}}-Rado) For any set {x,} any ordinal {\delta,} and any nonzero {n<\omega} there is some {\kappa} such that {\kappa\rightarrow(\delta)^n_x.} {\Box}

 
The {\mbox{Erd\H os}}-Rado theorem was originally proved using choice. Proofs of the choiceless version above, that we need, have been rediscovered a few times. Apparently the first such proof is due to Keisler and Morley, from 1967. Kleinberg and Seiferas also provide a proof. Another proof (for {x} finite) is due to Thomas Forster, from 2007.

We are now ready to begin the proof of Theorem 4.

Proof: The proof divides naturally in several cases.

Suppose first that {\alpha\ge\omega+\omega.} By monotonicity, if {\kappa\rightarrow(\beta)^\alpha_\gamma,} then {\kappa\rightarrow(\beta)^\alpha,} which implies that {\kappa\rightarrow(\alpha)^\alpha,} and therefore {\kappa\rightarrow(\omega+\omega)^{\omega+\omega}.}

Given {p\in[\kappa]^{\omega+\omega},} denote by {p_1,p_2} the two sets of order type {\omega} with {\sup(p_1)\le\min(p_2)} such that {p=p_1\cup p_2.} Define {F:[\kappa]^{\omega+\omega}\rightarrow2} by {F(p)=1} iff {n_{p_1}\le n_{p_2}.}

It is enough to show that for any {p\in[\kappa]^{\omega+\omega}} there is some {p'\in[p]^{\omega+\omega}} such that {F(p)\ne F(p').} This shows that {F} does not admit homogeneous sets of order type {\omega+\omega,} and therefore {\kappa\not\rightarrow(\beta)^\alpha_\gamma} to begin with.

To see the claim, suppose {F(p)=1,} so {n_{p_1}\le n_{p_2}.} Let {\hat p\in[p_1]^\omega} be such that {n_{\hat p}>n_{p_2}} and take {p'=\hat p\cup p_2.} Then {F(p')=0.} The argument is similar if {F(p)=0.}

Suppose now that {\beta\ge\alpha_l+\omega+\alpha_n.} By the previous case, we may assume that {\alpha<\omega+\omega,} so {\alpha_l=\omega.} By monotonicity, if {\kappa\rightarrow(\beta)^\alpha_\gamma,} then {\kappa\rightarrow(\beta)^\alpha,} so {\kappa\rightarrow(\alpha_l+\omega+\alpha_n)^\alpha,} and therefore {\kappa\rightarrow(\omega+\omega)^\omega.}

Define {F:[\kappa]^\omega\rightarrow 2} by {F(p)=1} iff {p(n)>p_\rho(n)} for all {n,} where {\rho=\sup(p).} It is enough to show that {F} does not admit homogeneous sets of order type {\omega+\omega.} For this, it suffices to show that given any {C\in[\kappa]^{\omega+\omega},} there are {p,q\in[C]^\omega} with {F(p)\ne F(q).}

Let {\rho=\sup(C).} Define {p\in[C]^\omega} so that {p(n)} is the least member of {C} larger than {p(m)} for all {m<n} and also larger than {p_\rho(n).} By construction, {F(p)=1.} 

As before, let {C_1,C_2} be the subsets of {C} of order type {\omega} such that {\sup(C_1)\le\min(C_2)} and {C=C_1\cup C_2.} Let {n_0} be such that {p_\rho(n_0)\ge\sup(C_1),} and define {q\in[C]^\omega} by {q=\{C_1(0),\dots,C_1(n_0)\}\cup C_2.} Then {F(q)=0,} as witnessed by {n_0.}

Suppose that {\gamma\ge\omega.} As before, if {\kappa\rightarrow(\beta)^\alpha_\gamma,} then {\kappa\rightarrow(\beta)^\alpha_\omega,} so {\kappa\rightarrow(\alpha)^\alpha_\omega,} and therefore {\kappa\rightarrow(\omega)^\omega_\omega.}

Define {F:[\kappa]^\omega\rightarrow\omega} by {F(p)=n_p.} Since for any {p\in[\kappa]^\omega} there is some {p'\in[p]^\omega} with {n_{p'}>n_p,} it follows that {F} does not admit infinite homogeneous sets, and we are done.

Suppose that {\gamma<\omega} and {\beta<\omega+\omega.} Now we prove that {\kappa\rightarrow(\beta)^\alpha_\gamma} iff {\omega\rightarrow(\omega)^\omega.}

Suppose first that {\kappa\rightarrow(\beta)^\alpha_\gamma.} By monotonicity, {\kappa\rightarrow(\beta)^\alpha,} so {\kappa\rightarrow(\alpha)^\alpha} and therefore {\kappa\rightarrow(\omega)^\omega.}

Towards a contradiction, suppose that {\omega\not\rightarrow(\omega)^\omega,} and let {F:[\omega]^\omega\rightarrow2} be a witnessing coloring. Given {p\in[\kappa]^\omega} let {\rho=\sup(p)} and set

\displaystyle I_p=\{n<\omega: [p_\rho(n),p_\rho(n+1))\cap p\ne\emptyset\}.

Note that {I_p} is infinite, so {F(I_p)} is defined. Now define a coloring {G:[\kappa]^\omega\rightarrow2} by {G(p)=F(I_p).}

It is enough to check that {G} admits no infinite homogeneous sets. But this is clear, since given any {p\in[\kappa]^\omega,} any infinite subset {I} of {I_p} induces an infinite subset {q=q_I} of {p} with {I_q=I.} Since {F} admits no infinite homogeneous sets, there is {I\subset I_p} such that {G(q_I)\ne G(p).} But then {G} is not constant on {[p]^\omega.}

Conversely, suppose that {\omega\rightarrow(\omega)^\omega.} Let {i,j,k\in\omega} be such that {j\le i,} {1<k,} {\alpha=\omega+j,} {\beta=\omega+i,} and {\gamma=k.} We need to check that if {\kappa>\aleph_0,} then {\kappa\rightarrow(\omega+i)^{\omega+j}_k.}

First, notice that {\omega\rightarrow(\omega)^\omega_k,} by an obvious induction. Second, note that Ramsey’s theorem {\omega\rightarrow(\omega)^m_n} for any {m,n<\omega} holds; for example, the amount of choice used in the first proof given last lecture is {{\sf DC}_\omega,} which follows from {{\sf WOC}} by Homework 13.

We will show that {\omega+\omega\rightarrow(\omega+i)^{\omega+j}_k,} which clearly suffices. For this, consider a coloring {F:[\omega+\omega]^{\omega+j}\rightarrow k,} and let {p_0,p_1,\dots} enumerate {[\omega+\omega\setminus\omega]^j.} Use {{\sf DC}_\omega} to produce a sequence {(F_n,x_n:x<\omega)} where

  • {\omega=x_0\supseteq x_1\supseteq x_2\supseteq\dots} are infinite sets, and
  • {F_n:[x_n]^\omega\rightarrow k} for all {n.}

To do this, assume {x_n} is given, and set {F_n(p)=F(p\cup p_n)} for {p\in[x_n]^\omega.} Since {\omega\rightarrow(\omega)^\omega_k,} we can find an infinite {x_{n+1}\subseteq x_n} and an {l_n\in k} such that {x_{n+1}} is {l_n}-homogeneous for {F_n.}

Now define {G:[\omega+\omega\setminus\omega]^j\rightarrow k} by {G(p_n)=l_n.} By Ramsey’s theorem, there is an infinite set {y\subseteq\omega+\omega\setminus\omega} and an {l\in k} such that {y} is {l}-homogeneous for {G.} Let {z} consist of the first {i} elements of {y.}

Let {n} be largest such that {p_n\in[z]^j.} We claim that {x_{n+1}\cup z} is {F}-homogeneous. To see this, note that any {j}-sized subset of {z} is {p_m} for some {m\le n.} If {p\in[x_{n+1}]^\omega,} then {F(p\cup p_m)=F_m(p)=l_m,} because {p\in[x_{m+1}]^\omega} since the {x_s} are decreasing. But {l_m=G(p_m)=l,} since {p_m\in[z]^j.} This shows that {F} is constantly equal to {l} on {x_{n+1}\cup z.}

Finally, suppose that {\gamma<\omega,} {\alpha<\omega+\omega,} and {\omega+\omega\le\beta<\alpha_l+\omega+\alpha_n.} We need to show that {\omega\rightarrow(\omega)^\omega} iff there is some {\kappa} such that {\kappa\rightarrow(\beta)^\alpha_\gamma.}

First, suppose that {\kappa\rightarrow(\beta)^\alpha_\gamma.} By monotonicity, {\kappa\rightarrow(\beta)^\alpha,} so {\kappa\rightarrow(\alpha)^\alpha,} and therefore {\kappa\rightarrow(\omega)^\omega.} As shown above, this implies that {\omega\rightarrow(\omega)^\omega.}

Conversely, suppose that {\omega\rightarrow(\omega)^\omega.} Let {i<j<\omega} and {1<k<\omega.} We need to show that there is some {\kappa} such that {\kappa\rightarrow(\omega+\omega+i)^{\omega+j}_k.} For this, we use the choiceless {\mbox{Erd\H os}}-Rado Theorem 6.

We claim that we can take {\kappa} such that {\kappa\rightarrow(\omega+i)^j_{k\times 2^{\aleph_0}}.} To see this, consider a coloring {F:[\kappa]^{\omega+j}\rightarrow k.} For {p\in[\kappa\setminus\omega]^j} define {G_p:[\omega]^\omega\rightarrow k} by {G_p(x)=F(x\cup p).}

There is a canonical bijection between {[\kappa\setminus\omega]^j} and {\kappa.} By {{\sf AC}_\kappa,} it follows that we can associate to each {p\in[\kappa\setminus\omega]^j} a pair {(l_p,S_p)} such that {l_p\in k} and {S_p\in[\omega]^\omega} is {l_p}-homogeneous for {G_p.} By choice of {\kappa,} we can find {C\in[\kappa\setminus\omega]^{\omega+i},} an {l\in k,} and an {S\in[\omega]^\omega} such that {C} is {(l,S)}-homogeneous for the map {H(p)=(l_p,S_p).}

Let {H=S\cup C.} Then {H} is homogeneous for {F,} since any {y\in[H]^{\omega+j}} has the form {s\cup c} for some {s\in[S]^\omega} and {c\in[C]^j,} so {F(y)=G_c(s)=l.} \Box

2. Partition cardinals

By further restricting the amount of choice in the universe, it becomes possible that several of the infinite exponent relations shown inconsistent in the arguments above now hold. In fact, the study of infinite exponent relations under the axiom of determinacy has proved to be very fruitful, and a detailed theory has emerged. I illustrate this with a result of Kleinberg that shows that infinite exponents give rise to measurable cardinals. In what follows, whenever the elements of a linearly ordered set are displayed, as in {\{a_0,\dots,a_n\},} it is understood that {a_0<\dots<a_n.}

Lemma 7 Suppose that {\zeta\rightarrow(\zeta)^2.} Then {\zeta} is a regular cardinal.

 

Proof: It is easy to check that {\zeta} must be a limit ordinal. Let {\lambda\le\zeta} be such that there is some {p\in[\zeta]^\lambda} with {\sup(p)=\zeta.}

Define {F:[\zeta]^2\rightarrow 2} by {F(\{\alpha,\beta\})=0} iff {(\alpha,\beta)\cap p\ne\emptyset.} Let {C} be a homogeneous subset of {\zeta} of order type {\zeta.} Then {F''[C]^2=0,} since {C} is unbounded.

Now define {f:C\rightarrow\lambda} by {f(\alpha)=\min(p\setminus(\alpha+1)).} Then {f} is strictly increasing. Hence {\zeta={\rm ot}(C)\le\lambda.} \Box

Lemma 8 If {\kappa\rightarrow(\kappa)^{\beta+\beta}} and {\beta>1,} then {\kappa\rightarrow(\kappa)^\beta_\alpha} for all {\alpha<\kappa.}

 
Proof: It is easy to see that {\kappa\rightarrow(\kappa)^2,} so {\kappa} is regular.

Let {F:[\kappa]^\beta\rightarrow\alpha} be given. Given {p\in[\kappa]^{\beta+\beta},} let {p^1} and {p^2} denote the subsets of {p} consisting, respectively, of its first {\beta} elements and of its remaining {\beta.} Now define {G:[\kappa]^{\beta+\beta}\rightarrow 2} by {G(p)=0} iff {F(p^1)=F(p^2).}

Let {C} be homogeneous for {G} of type {\kappa.} Then in fact {C} is {0}-homogeneous. To see this, slice {C} off into successive sets {p_\gamma,} {\gamma<\kappa,} of order type {\beta.} Clearly, {F} cannot be injective on {\{p_\gamma:\gamma<\kappa\}\subset[C]^\beta,} since it only takes {|\alpha|<\kappa} many values.

It follows that {C} is also homogeneous for {F.} Because if {p,q\in[C]^\beta,} we can find {r\in[C]^\beta} with {\min(r)>\sup(p\cup q),} and since {G(p\cup r)=G(q\cup r),} we must have {F(p)=F(r)=F(q).} \Box

Lemma 9 If {\kappa\rightarrow(\kappa)^{\beta+\beta}} and {\beta>1,} then {\kappa\rightarrow(\kappa)^\beta_{2^{\alpha}}} for any {\alpha<\kappa.}

 

Proof: We argue as above: Let {F:[\kappa]^\beta\rightarrow2^\alpha} be given, where {2^\alpha} is the set of functions from {\alpha} into {2,} and define {G:[\kappa]^{\beta+\beta}\rightarrow2} by {G(p)=0} iff {F(p^1)=F(p^2),} where {p^1,p^2} are as before. Let {C} be homogeneous for {G} of order type {\kappa,} and define {(p_\gamma:\gamma<\kappa)} as before. If {C} is 0-homogeneous for {G,} then it is homogeneous for {F} as before, and we are done.

Suppose towards a contradiction that {C} is 1-homogeneous for {G,} so the map {g:\kappa\rightarrow2^\alpha} given by {g(\gamma)=F(p_\gamma)} is 1-1.

By lemma 8 and an easy argument, {\kappa\rightarrow(\kappa)^2_\alpha.} Let {H:[\kappa]^2\rightarrow\alpha} be given by {H(\{\gamma,\delta\})=}least {\xi<\alpha} such that {g(\gamma)(\xi)\ne g(\delta)(\xi).} Then we can find {\nu<\alpha} and {B\in[\kappa]^\kappa} that is {\nu}-homogeneous for {H.} Then {\{g(\gamma)(\nu):\gamma<\kappa\}} is a {\kappa}-sized subset of {2,} contradiction. \Box

Theorem 10 (Kleinberg) Suppose that {\kappa\rightarrow(\kappa)^{\lambda+\lambda}} for some limit ordinal {\lambda<\kappa.} Then {\kappa} is measurable, and there is a normal ultrafilter over {\kappa} concentrating on ordinals of the same cofinality as {\lambda.}

 

Proof: {\kappa} is measurable.

As before, {\kappa} is regular. First, we generalize the notion of {\omega}-club and identify the ultrafilter that witnesses the measurability of {\kappa.}

For {\lambda<\kappa} a limit ordinal and {A\subseteq\kappa,} let {(A)_\lambda} denote the set of all suprema of increasing {\lambda}-sequences of elements of {A.} Say that {A} is {\lambda}-closed iff {(A)_\lambda\subseteq A.} If {A} is {\lambda}-closed and unbounded in {\kappa,} say that {A} is a {\lambda}-club. Clearly, for any {B\in[\kappa]^\kappa,} the set {(B)_\lambda} is {\lambda}-club.

Let {{\mathcal F}_\lambda} denote the collection of subsets of {\kappa} that contain a {\lambda}-club. Clearly, {{\mathcal F}_\lambda} is nonempty, is closed under supersets, and does not contain the empty set.

We want to show that if {\kappa\rightarrow(\kappa)^{\lambda+\lambda},} then in fact {{\mathcal F}_\lambda} is a {\kappa}-complete filter over {\kappa.} To see this claim, suppose that {\gamma<\kappa} and that {(A_\alpha:\alpha<\gamma)} is a sequence of members of {{\mathcal F}_\lambda.} Since we are not assuming {{\sf AC}_{|\gamma|},} we cannot automatically pick {\lambda}-clubs {B_\alpha\subseteq A_\alpha} to conclude that {\bigcap_\alpha A_\alpha\supseteq \bigcap_\alpha B_\alpha,} which is again a {\lambda}-club. Instead, we use that {\kappa\rightarrow(\kappa)^\lambda_{2^{\gamma}}.}

For {p\in[\kappa]^\kappa} and {\rho\le\kappa} a limit ordinal, let {p\upharpoonright\rho} denote the initial segment of {p} of order type {\rho.} Let {A} and {B} be unbounded subsets of {\kappa.} By an obvious back-and-forth construction, we can find {p_A} and {p_B} unbounded subsets of {A} and {B,} respectively, such that for all limit ordinals {\rho\le\kappa,} {\sup (p_A\upharpoonright \rho)=\sup(p_B\upharpoonright \rho).}

Define {F:[\kappa]^\lambda\rightarrow2^\gamma} as follows: Given {p\in[\kappa]^\lambda} and {\alpha<\gamma,} let {F(p)(\alpha)=0} iff {\sup(p)\in A_\alpha.} Let {C} be homogeneous for {F} of size {\kappa.} Then in fact {F(p)(\alpha)=0} for all {p\in[C]^\lambda} and {\alpha<\gamma.}

To see this, suppose that {\alpha<\gamma} is such that {F(p)(\alpha)=1} for all {p\in[C]^\lambda.} Let {B\subseteq A_\alpha} be {\lambda}-club, and consider {p_C} and {p_B} as above. Then {F(p_C\upharpoonright\lambda)(\alpha)=1,} so {\sup(p_B\upharpoonright \lambda)=\sup(p_C\upharpoonright\lambda)\notin A_\alpha,} contradicting that {(B)_\lambda\subseteq B\subseteq A_\alpha.}

Now let {A=(C)_\lambda,} so {A} is {\lambda}-club. It is enough to show that {A\subseteq\bigcap_\alpha A_\alpha.} To see this, let {\eta\in A,} so there is {p\in[C]^\lambda} with {\sup(p)=\eta.} Then {F(p)(\alpha)=0} for all {\alpha,} so {\eta\in A_\alpha} for all {\alpha,} and the claim follows.

A similar argument shows that {{\mathcal F}_\lambda} is in fact an ultrafilter. To see this, let {A\subseteq\kappa} be given. We use that {\kappa\rightarrow(\kappa)^\lambda,} and consider the partition {F:[\kappa]^\lambda\rightarrow2} given by {F(p)=0} iff {\sup(p)\in A.} If {C} is homogeneous for {F} of size {\kappa,} then {(C)_\lambda} is {\lambda}-club, and either {(C)_\lambda\subseteq A} or {(C)_\lambda\cap A=\emptyset} depending on whether {C} is {0}-homogeneous or {1}-homogeneous.

{{\mathcal F}_\lambda} is normal.

First we show that {{\mathcal F}_\lambda={\mathcal F}_{{\rm cf}(\lambda)}.} Clearly, {{\mathcal F}_{{\rm cf}(\lambda)}\subseteq{\mathcal F}_\lambda.} To see the other containment, it is enough to see that if {B} is {\lambda}-club, then {(B)_\lambda} is {{\rm cf}(\lambda)}-closed. Let {p\in[(B)_\lambda]^{{\rm cf}(\lambda)},} and let {(p_\alpha:\alpha<{\rm cf}(\lambda))} be its increasing enumeration.

Let {\xi=\min\{{\rm ot}(\lambda\setminus\beta):\beta<\lambda\},} so {{\rm cf}(\xi)={\rm cf}(\lambda).} Fix {f:{\rm cf}(\lambda)\rightarrow\xi} strictly increasing, continuous, and cofinal, and let {\beta<\lambda} such that {{\rm ot}(\lambda\setminus\beta)=\xi.}

For {\alpha<{\rm cf}(\lambda),} let {P_\alpha} be the initial segment of {B\setminus p_\alpha} such that {{\rm ot}(P_\alpha)={\rm ot}[f(\alpha),f(\alpha+1)).} Also, let {P^0\subset(B\cap p_0)} have order type {\beta.} Then {P\cup\bigcup_{\alpha<{\rm cf}(\lambda)}P_\alpha} has order type {\beta+\xi=\lambda,} and the same supremum as {p.} Thus, {\sup(p)\in(B)_\lambda.}

Note that {\kappa\rightarrow(\kappa)^{\lambda+\lambda}} implies {\kappa\rightarrow(\kappa)^{{\rm cf}(\lambda)}.} This is all we require below, so it follows that we may assume that {\lambda} is a regular cardinal.

To show that {{\mathcal F}_\lambda} is normal, consider a function {g:\kappa\rightarrow\kappa} regressive on a {{\mathcal F}_\lambda}-measure 1 set, and we need to argue that {g} is constant on a {{\mathcal F}_\lambda}-measure 1 set.

For this, fix a {\lambda}-club {A} where {g} is regressive, and let {F:[A]^\lambda\rightarrow2} be given by {F(p)=0} iff {g(\sup(p))\le\min(p).} Let {C} be homogeneous for {F} of size {\kappa.} Given {p\in[A]^\lambda,} let {q=p\setminus g(\sup(p)).} Then {q\in[A]^\lambda} and {\sup(q)=\sup(p),} so {F(q)=0.} Hence {C} is {0}-homogeneous.

Given any {\alpha\in(C)_\lambda} and any {p\in[C]^\lambda} with {\sup(p)=\alpha,} let {p'=\{\min(C)\}\cup p.} It follows that {g(\alpha)\le\min(C).} By {\kappa}-additivity of {{\mathcal F}_\lambda,} it follows that there is some {\beta\le \min(C)} such that {g^{-1}(\{\beta\})\in{\mathcal F}_\lambda.} \Box

Definition 11 A strong partition cardinal is a cardinal {\kappa} such that {\kappa\rightarrow(\kappa)^\kappa.}

A weak partition cardinal is a cardinal {\kappa} such that {\kappa\rightarrow(\kappa)^{\lambda}} for all {\lambda<\kappa.}

 
In the presence of {{\sf DC},} the existence of uncountable strong partition cardinals {\kappa} implies the existence of large cardinals {\lambda>\kappa.} Also, uncountable strong partition cardinals satisfy stronger partition relations than the one required by the definition. For example, one has:

Definition 12 {\kappa\rightarrow(\kappa)^{<\gamma}_\delta} means that for any partition {f : [\kappa]^{<\gamma}\rightarrow\delta} there is a set {X\in[\kappa]^\kappa} such that {f} is constant on {[X]^\beta} for all {\beta<\gamma.}

 
Note that {\omega\rightarrow(\omega)^\omega_\omega} fails; for example, consider {F:[\omega]^\omega\rightarrow\omega} given by {F(p)=\min(p).} Also, as noted by {\mbox{Erd\H os}} and Rado, {\omega\rightarrow(\omega)^{<\omega}} fails; for example, consider {F:[\omega]^{<\omega}\rightarrow2} given by {F(x)=0} iff {\min(x)\le|x|.}

Definition 13 A Ramsey cardinal is a cardinal {\kappa} such that {\kappa\rightarrow(\kappa)^{<\omega}.}

 

Theorem 14 (Henle)

  1. If {\kappa} is an uncountable cardinal, {\gamma} is a cardinal, and {\kappa\rightarrow(\kappa)^\gamma,} then {\kappa\rightarrow(\kappa)^{<\gamma}.} In particular, an uncountable strong partition cardinal is both Ramsey and a weak partition cardinal.
  2. If {\kappa\rightarrow(\kappa)^{<\gamma},} then {\kappa\rightarrow(\kappa)^{<\gamma}_{2^\delta}} for all {\delta<\kappa.}
  3. If {\omega\cdot \gamma=\gamma} then {\kappa\rightarrow(\kappa)^\gamma} implies that the least {\delta} such that {\kappa\not\rightarrow(\kappa)^\gamma_\delta} admits a {\delta}-complete nonprincipal ultrafilter. If {{\sf AC}_\omega} holds, then {\delta>\omega} (and therefore {\delta} is measurable.) If {{\sf DC}} holds, then the ultrafilter can be taken to be normal.
  4. If {\kappa} is uncountable and {\kappa\rightarrow(\kappa)^\kappa_\delta,} then {\kappa\rightarrow(\kappa)^\kappa_{2^\delta}.} {\Box}

 

On the other hand, it is not the case that if {\kappa\rightarrow(\kappa)^\beta_x} then {\kappa\rightarrow(\kappa)^\beta_{2^x}} for arbitrary sets {x.} For example, {\omega_1\rightarrow(\omega_1)^{\omega_1}} holds under {{\sf AD}} and therefore also {\omega_1\rightarrow(\omega_1)^{2}_{2^\omega}.} However, {\omega_1\preceq {\mathcal P}^2(\omega),} and it follows that {\omega_1\not\rightarrow(\omega_1)^2_{2^{2^\omega}}.}

To state the main result about partition cardinals, we need two additional large cardinal notions:

Definition 15 An algebra on {A} is a structure of the form {(A,f_n)_{n<\omega}} where for each {n} there is an {m_n<\omega} such that {f_n:[A]^{m_n}\rightarrow A.}

A cardinal {\kappa} is Jónsson iff every algebra on {\kappa} admits a proper subalgebra of size {\kappa.}

 

For example, that {\omega} is not Jónsson can be witnessed by letting {f(n)=n-1} if {n\ge1,} {f(0)=0,} and setting {f_1(\{n\})=f(n),} and {f_k} arbitrary for {k\ne1.} We will return to Jónsson cardinals next lecture.

We also need the notion of Rowbottom cardinal, that requires a significant weakening of the ordinary partition relation for ordinals. We briefly encountered this weakening when discussing Chang’s conjecture in lecture II.7.

Definition 16 Given ordinals {\alpha,\beta,\gamma,\delta,} say that {\beta\rightarrow[\alpha]^\gamma_\delta} iff for any {f:[\beta]^\gamma\rightarrow\delta} there is an {H\in[\beta]^\alpha} such that {f''[H]^\gamma\ne\delta.} Similarly, by replacing {\gamma} with {<\gamma.}

Say that {\beta\rightarrow[\alpha]^\gamma_{\delta,<\eta}} iff for any {f:[\beta]^\gamma\rightarrow\delta} there is an {H\in[\beta]^\alpha} such that {|f''[H]^\gamma|<\eta.} Similarly by replacing {\gamma} with {<\gamma.}

If {\omega<\nu<\kappa,} say that {\kappa} is {\nu}-Rowbottom iff {\kappa\rightarrow[\kappa]^{<\omega}_{\lambda,<\nu}} for any {\lambda<\kappa,} and say that {\kappa} is Rowbottom iff it is {\omega_1}-Rowbottom.

 

Theorem 17 (Kleinberg) Assume {{\sf DC}.} Let {\kappa} be an uncountable strong partition cardinal. Then there are cardinals {\kappa=\kappa_1<\kappa_2<\dots} such that:

  1. {\kappa_2\rightarrow(\kappa_2)^\alpha} for all {\alpha<\omega_1.} In particular, {\kappa_1} and {\kappa_2} are measurable.
  2. All the {\kappa_n,} {n\ge 3,} are singular Jónsson cardinals of cofinality {\kappa_2,} and {\sup_n\kappa_n} is a Rowbottom cardinal. {\Box}

 

Theorem 18 (Kleinberg) In the situation of Theorem 17, assume moreover that there is a normal ultrafilter {{\mathcal U}} over {\kappa} such that {{}^\kappa\kappa/{\mathcal U}} has order type {\kappa^+.} Then:

  1. {\kappa_{n+1}=\kappa_n^+} for {n\ge1.}
  2. {\kappa_2} is a weak partition cardinal.
  3. Every normal ultrafilter over {\kappa_1} or {\kappa_2} is an {{\mathcal F}_\lambda,} as defined in the proof of Theorem 10. {\Box}

 
It is in the context of {{\sf AD}} that Kleinberg results have proved useful. In part, this may be accidental, in that we do not know any ways of obtaining partition cardinals other than via determinacy. On the other hand, Kechris and Woodin have shown that, in {L({\mathbb R}),} determinacy is equivalent to the existence of unboundedly many strong partition cardinals below {\Theta,} so determinacy seems to be the natural setting for studying these cardinals.

As mentioned above,

\displaystyle \omega_1\rightarrow(\omega_1)^{\omega_1}

holds under {{\sf AD}.} This is a theorem of Martin.

In {{\sf ZF}} one can make sense of ultrapowers of ordinals by {\sigma}-complete ultrafilters; this is not necessarily the case in general without any amount of choice, since one cannot prove {\mbox{\L o\'s}}‘s theorem for the full ultrapower of {V,} so some care is required.

Theorem 19 (Martin) Assume {{\sf ZF}+{\sf DC}.} If {\kappa\rightarrow(\kappa)^\kappa} and {\kappa} is uncountable, then for any {\sigma}-complete ultrafilter {{\mathcal U}} over {\kappa,} the image {j_{\mathcal U}(\kappa)} of {\kappa} under the induced ultrapower map, is a cardinal. {\Box}

 

From Martin’s theorem 19 it follows that {j_{{\mathcal F}_\omega}(\omega_1)=\omega_2} where {{\mathcal F}_\omega} is the {\omega}-club ultrafilter over {\omega_1.} Hence from Theorems 17 and 18 it follows that

\displaystyle \omega_2\rightarrow(\omega_2)^{<\omega_2},

and that each {\omega_n,} {n\ge3,} is a Jónsson cardinal of cofinality {\omega_2,} and {\omega_\omega} is Rowbottom.

Under {{\sf AD}+{\sf DC},} a very detailed analysis of measures has been carried out by Steve Jackson and others, and so many cardinals with strong partition properties have been identified. Steel proved, for example, that in {L({\mathbb R}),} under {{\sf AD},} every regular cardinal below {\Theta=\aleph_*({\mathbb R})} is in fact measurable. Also, it follows from Jackson’s analysis that

\displaystyle \aleph_{\omega+1}, \aleph_{\omega^{\omega^\omega}+1}, \aleph_{\omega^{\omega^{\omega^{\omega^\omega}}}+1}, \dots

are all strong partition cardinals and their successors are weak partition cardinals; here, exponentiation is ordinal exponentiation.

The precise result shown by Kleinberg is that if {\kappa_1} is a strong partition cardinal and {{\mathcal U}} is a normal ultrafilter over {\kappa_1,} then we can define {\kappa_{n+1},} {1\le n<\omega,} as in Theorem 17 by setting {\kappa_{n+1}=j_{\mathcal U}(\kappa_n).} A careful analysis of measures under {{\sf AD}} then allows us to study many cardinals above a given {\kappa_1.} For example, the only regular cardinals under {{\sf AD}} between {\aleph_{\omega+1}} and {\aleph_{\omega^{\omega^\omega}+1}} are {j_{{\mathcal F}_\lambda}(\aleph_{\omega+1})} for {\lambda=\omega,\omega_1,\omega_2} and {{\mathcal F}_\lambda} the {\lambda}-club ultrafilter over {\aleph_{\omega+1}.} These cardinals are precisely {\aleph_{\omega+2},} {\aleph_{\omega+\omega+1},} and {\aleph_{\omega^\omega+1}.}

Theorem 20 (Jackson-Khafizov) Assume {{\sf AD}.} Suppose that

\displaystyle \aleph_{\omega+1}<\aleph_{\alpha+1}<\aleph_{\omega^{\omega^\omega}+1}.

Let

\displaystyle \alpha =\omega^{\beta_1}+\dots+\omega^{\beta_n},

where {\beta_1\ge\dots\ge\beta_n,} be the Cantor normal form of {\alpha.} Then the following hold:

  1. If {\beta_n=0,} then {{\rm cf}(\aleph_{\alpha+1})=\aleph_{\omega+2}.}
  2. If {\beta_n} is a successor ordinal, then {{\rm cf}(\aleph_{\alpha+1})=\aleph_{\omega\cdot2+1}.}
  3. If {\beta_n} is a limit ordinal, then {{\rm cf}(\aleph_{\alpha+1})=\aleph_{\omega^\omega+1}.} {\Box}

 

Löwe exploited Kleinberg’s result and the Jackson-Khafizov analysis thanks to the following “shifting lemma:”

Theorem 21 (Löwe) Assume {{\sf ZF}+{\sf DC}.} Let {\kappa=\aleph_\alpha<\lambda=\aleph_{\alpha+\beta},} and let {{\mathcal U}} be a {\kappa}-complete ultrafilter over {\kappa.} Let {j_{\mathcal U}(\kappa)=\aleph_\gamma.} Suppose that for all cardinals {\nu\in(\kappa,\lambda],} either {\nu} is a successor of cofinality strictly larger than {\kappa,} or else {\nu} is a limit of cofinality strictly smaller than {\kappa.} Then {j_{\mathcal U}(\lambda)\le\aleph_{\gamma+\beta}.} {\Box}

 

For example, under {{\sf AD},} if {\kappa_1=\aleph_{\omega+1},} then there are only three normal ultrafilters over {\kappa_1,} namely {{\mathcal F}_\lambda} for {\lambda=\omega,\omega_1, \omega_2.} It follows that the Kleinberg sequence associated to {{\mathcal F}_\lambda} is:

  • If {\lambda=\omega,} then {\kappa_n=\aleph_{\omega+n}} for {2 \le n.}
  • If {\lambda=\omega_1,} then {\kappa_n=\aleph_{\omega\cdot n+1}} for {2 \le n.}
  • If {\lambda=\omega_2,} then {\kappa_n=\aleph_{\omega^\omega\cdot(n-1)+1}} for {2 \le n.}

 
Bibliography

Here are some references consulted while preparing this note:

 

  • James Henle, Some consequences of an infinite-exponent partition relation, The Journal of Symbolic Logic, 42 (4), (Dec., 1977), 523–526.
  • Steve Jackson, Structural consequences of {{\sf AD}}, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., to appear.
  • Akihiro Kanamori, The higher infinite, Springer (1994).
  • Eugene Kleinberg, Strong partition properties for infinite cardinals, The Journal of Symbolic Logic, 35 (3), (Sep., 1970), 410–428.
  • Eugene Kleinberg, Infinitary combinatorics and the axiom of determinateness, Springer (1977).
  • Eugene Kleinberg and J. Seiferas, Infinite exponent partition relations and well-ordered choice, The Journal of Symbolic Logic, 38 (2), (Jun., 1973), 299–308.
  • Benedikt Löwe, Kleinberg sequences and partition cardinals below {\delta^1_5}, Fundamenta Mathematicae, 171 (1), (2002), 69–76.

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

Advertisement

This entry was posted on Wednesday, April 1st, 2009 at 10:56 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.

9 Responses to 580 -Partition calculus (2)

  1. 580 -Partition calculus (3) « Teaching page says:
    April 6, 2009 at 12:21 am

    […] again, assume choice throughout. Last lecture, we showed that for any The results below strengthen this fact in several ways. Definition 1 […]

    Reply
  2. 580 -Partition calculus (6) « Teaching page says:
    April 24, 2009 at 12:13 pm

    […] proof of Theorems 1 and 3 above require the axiom of choice. However, the proof of Theorem 4 in lecture III.2 requires a choiceless version. I now proceed to establish this version. Theorem 5 () For any set […]

    Reply
  3. andrescaicedo says:
    May 12, 2009 at 10:28 pm

    Woodin has extended significantly the results about Jónsson cardinals mentioned in the context of {\sf AD}; namely, he has shown using the directed systems analysis of {\sf HOD} that (assuming determinacy) in L({\mathbb R}), every uncountable cardinal below \Theta is Jónsson. It is not clear whether the argument can be extended to strengthen the conclusion to say that every such cardinal is Rowbottom.

    Steve Jackson has shown (from determinacy) that this is the case for all uncountable cardinals below \aleph_{\omega_1}.

    Reply
  4. 580 -Partition calculus (5) « Teaching blog says:
    October 27, 2010 at 4:54 pm

    […] from Definition 15 on lecture III.2 that a cardinal is Jónsson iff every algebra on admits a proper subalgebra of size Here, an […]

    Reply
  5. Determinacy and Jónsson cardinals « A kind of library says:
    April 9, 2012 at 7:53 pm

    […] of partition properties and the computation of ultrapowers of associated measures. See also here for extensions of this result, references, and some additional […]

    Reply
  6. 580 -Partition calculus (6) « A kind of library says:
    September 7, 2012 at 12:28 pm

    […] proofs of Theorems 1 and 3 above require the axiom of choice. However, the proof of Theorem 4 in lecture III.2 requires a choiceless version. I now proceed to establish this version. Theorem 5 () For any set […]

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

    […] from Definition 15 on lecture III.2 that a cardinal is Jónsson iff every algebra on admits a proper subalgebra of size Here, an […]

    Reply
  8. 580 -Partition calculus (3) « A kind of library says:
    January 20, 2013 at 9:30 am

    […] again, assume choice throughout. Last lecture, we showed that for any The results below strengthen this fact in several […]

    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: