Set theory seminar – Marion Scheepers: Coding strategies (IV)

October 12, 2010

For the third talk (and a link to the second one), see here. The fourth talk took place on October 12.

We want to show the following version of Theorem 2:

Theorem. Suppose \kappa is a singular strong limit cardinal of uncountable cofinality. Then the following are equivalent:

  1. For each ideal J on \kappa, player II has a winning coding strategy in RG(J).
  2. 2^\kappa<\kappa^{+\omega}.

Since 2^\kappa has uncountable cofinality, option 2 above is equivalent to saying that the instance of {\sf wSCH} corresponding to \kappa holds.

Before we begin the proof, we need to single out some elementary consequences in cardinal arithmetic of the assumptions on \kappa. First of all, since \kappa is singular strong limit, then for any cardinal \lambda<\kappa, we have that

\kappa^\lambda=\left\{\begin{array}{cl}\kappa&\mbox{\ if }\lambda<{\rm cf}(\kappa),\\ 2^\kappa&\mbox{\ otherwise.}\end{array}\right.

Also, since the cofinality of \kappa is uncountable, we have Hausdoff’s result that if n<\omega, then (\kappa^{+n})^{\aleph_0}=\kappa^{+n}. I have addressed both these computations in my lecture notes for Topics in Set Theory, see here and here.

We are ready to address the Theorem.

Proof. (2.\Rightarrow 1.) We use Theorem 1. If option 1. fails, then there is an ideal J on \kappa with {\rm cf}(\left< J\right>,{\subset})>|J|.

Note that {\rm cf}(\left< J\right>,{\subset})\le({\rm cf}(J,{\subset}))^{\aleph_0}, and \kappa\le|J|. Moreover, if \lambda<\kappa, then 2^\lambda<{\rm cf}(J,{\subset}) since, otherwise,

({\rm cf}(J,{\subset}))^{\aleph_0}\le 2^{\lambda\aleph_0}=2^\lambda<\kappa.

So {\rm cf}(J,{\subset})\ge\kappa and then, by Hausdorff, in fact {\rm cf}(J,{\subset})\ge \kappa^{+\omega}, and option 2. fails.

(1.\Rightarrow 2.) Suppose option 2. fails and let \lambda=\kappa^{+\omega}, so \kappa<\lambda<2^\kappa and {\rm cf}(\lambda)=\omega. We use \lambda to build an ideal J on \kappa with {\rm cf}(\left< J\right>,{\subset})>|J|.

For this, we use that there is a large almost disjoint family of functions from {\rm cf}(\kappa) into \kappa. Specifically:

Lemma. If \kappa is singular strong limit, there is a family {\mathcal F}\subseteq{}^{{\rm cf}(\kappa)}\kappa with {}|{\mathcal F}|=2^\kappa and such that for all distinct f,g\in{\mathcal F}, we have that {}|\{\alpha<{\rm cf}(\kappa)\mid f(\alpha)=g(\alpha)|<{\rm cf}(\kappa).

In my notes, I have a proof of a general version of this result, due to Galvin and Hajnal, see Lemma 12 here; essentially, we list all functions f:{\rm cf}(\kappa)\to\kappa, and then replace them with (appropriate codes for) the branches they determine through the tree \kappa^{{\rm cf}(\kappa)}. Distinct branches eventually diverge, and this translates into the corresponding functions being almost disjoint.

Pick a family {\mathcal F} as in the lemma, and let {\mathcal G} be a subfamily of size \lambda. Let S=\bigcup{\mathcal G}\subseteq{\rm cf}(\kappa)\times\kappa. We proceed to show that |S|=\kappa and use {\mathcal G} to define an ideal J on S as required.

First, obviously |S|\le\kappa. Since \kappa<\lambda=|{\mathcal G}| and {\mathcal G}\subseteq{\mathcal P}(S), it follows that {}|S|\ge\kappa, or else {}|{\mathcal P}(S)|<\kappa, since \kappa is strong limit.

Now define

J=\{X\subseteq S\mid\exists {\mathcal H}\subseteq{\mathcal G}\,(|{\mathcal H}|<\omega,\bigcup{\mathcal H}\supseteq X)\}.

Clearly, J is an ideal. We claim that |J|=\lambda. First, each singleton \{f\} with f\in{\mathcal G} is in J, so {}|J|\ge\lambda. Define \Phi:[{\mathcal G}]^{<\aleph_0}\to J by \Phi({\mathcal H})=\bigcup{\mathcal H}). Since the functions in {\mathcal G} are almost disjoint, it follows that \Phi is 1-1. Let G be the image of \Phi. By construction, G is cofinal in J. But then

{}|J|\le|{\mathcal G}|2^{{\rm cf}(\kappa)}=\lambda 2^{{\rm cf}(\kappa)}=\lambda,

where the first inequality follows from noticing that any X\in J has size at most {\rm cf}(\kappa). It follows that |J|=\lambda, as claimed.

Finally, we argue that {\rm cf}(\left< J\right>,{\subset})>\lambda, which completes the proof. For this, consider a cofinal {\mathcal A}\subseteq\left< J\right>, and a map f:{\mathcal A}\to[{\mathcal G}]^{\le\aleph_0} such that for all A\in{\mathcal A}, we have A\subseteq\bigcup f(A).

Since {\mathcal A} is cofinal in \left< J\right>, it follows that f[{\mathcal A}] is cofinal in {}[{\mathcal G}]^{\le\aleph_0}. But this gives the result, because

{}|{\mathcal A}|\ge{\rm cf}([{\mathcal G}]^{\le \aleph_0},{\subset})={\rm cf}([\lambda]^{\le \aleph_0},{\subset})>\lambda,

and we are done. \Box

Advertisement

1 Comment | Set theory seminar | Tagged: , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (7)

May 6, 2009

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.

Read the rest of this entry »

11 Comments | 580: Topics in set theory | Tagged: , , , , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (6)

April 24, 2009

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

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

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

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

for all {\mu<\kappa.}

 
Read the rest of this entry »

2 Comments | 580: Topics in set theory | Tagged: , , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (3)

April 6, 2009

1. Infinitary Jónsson algebras

Once again, assume choice throughout. Last lecture, we showed that {\kappa\not\rightarrow(\kappa)^{\aleph_0}} for any {\kappa.} The results below strengthen this fact in several ways.

Definition 1 Let {x} be a set. A function {f:[x]^{\aleph_0}\rightarrow x} is {\omega}-Jónsson for {x} iff for all {y\subseteq x,} if {|y|=|x|,} then {f''[y]^{\aleph_0}=x.}

 
Actually, for {x=\lambda} a cardinal, the examples to follow usually satisfy the stronger requirement that {f''[y]^\omega=\lambda.} In the notation from Definition 16 from last lecture, {\lambda\not\rightarrow[\lambda]^\omega_\lambda.}

The following result was originally proved in 1966 with a significantly more elaborate argument. The proof below, from 1976, is due to Galvin and Prikry.

Theorem 2 (Erdös-Hajnal) For any infinite {x,} there is an {\omega}-Jónsson function for {x.}

 
Read the rest of this entry »

6 Comments | 580: Topics in set theory | Tagged: , , , , , | Permalink
Posted by andrescaicedo