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

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

580 -Cardinal arithmetic (7)

March 4, 2009

[This document was typeset using Luca Trevisan‘s LaTeX2WP. I will refer to result n (or definition n) from last lecture as 3.n.]

A. The Galvin-Hajnal rank and an improvement of Theorem 3.1

Last lecture, I covered the first theorem of the Galvin-Hajnal paper and several corollaries. Recall that the result, Theorem 3.1, states that if {\kappa} and {\lambda} are uncountable regular cardinals, and {\lambda} is {\kappa}-inaccessible, then {\prod_{\alpha<\kappa}\kappa_\alpha<\aleph_\lambda} for any sequence {(\kappa_\alpha:\alpha<\lambda)} of cardinals such that {\prod_{\alpha<\beta}\kappa_\alpha<\aleph_\lambda} for all {\beta<\kappa.}

In particular (see, for example, Corollary 3.7), if {{\rm cf}(\xi)>\omega} and {\aleph_\xi} is strong limit, then {2^{\aleph_\xi}<\aleph_{(|\xi|^{{\rm cf}(\xi)})^+}.}

The argument relied in the notion of an almost disjoint transversal. Assume that {\kappa} is regular and uncountable, and recall that if {{\mathcal A}=(A_\alpha:\alpha<\kappa)} is a sequence of sets, then {T({\mathcal A})=\sup\{|{\mathcal F}|:{\mathcal F}} is an a.d.t. for {{\mathcal A}\}.} Here, {{\mathcal F}} is an a.d.t. for {{\mathcal A}} iff {{\mathcal F}\subseteq\prod{\mathcal A}:=\prod_{\alpha<\kappa}A_\alpha} and whenever {f\ne g\in{\mathcal F},} then {\{\alpha<\kappa:f(\alpha)=g(\alpha)\}} is bounded.

With {\kappa,\lambda} as above, Theorem 3.1 was proved by showing that there is an a.d.t. for {(\prod_{\beta<\alpha}\kappa_\beta:\alpha<\kappa)} of size {\prod_{\alpha<\kappa}\kappa_\alpha,} and then proving that, provided that {|A_\alpha|<\aleph_\lambda} for all {\alpha<\kappa,} then {T({\mathcal A})<\aleph_\lambda.}

In fact, the argument showed a bit more. Recall that if {f:\kappa\rightarrow{\sf ORD},} then {\aleph_f=(\aleph_{f(\alpha)}:\alpha<\kappa).} Then, for any {f:\kappa\rightarrow\lambda}, {T(\aleph_f)<\aleph_\lambda.}

The proof of this result was inductive, taking advantage of the well-foundedness of the partial order {<_{b,\kappa}} defined on {{}^\kappa{\sf ORD}} by {f<_{b,\kappa}g} iff {\{\alpha:f(\alpha)\ge g(\alpha)\}} is bounded in {\kappa.} That {<_{b,\kappa}} is well-founded allows us to define a rank {\|f\|_b} for each {f:\kappa\rightarrow{\sf ORD},} and we can argue by considering a counterexample of least possible rank to the statement from the previous paragraph.

In fact, more precise results are possible. Galvin and Hajnal observed that replacing the ideal of bounded sets with the nonstationary ideal (or, really, any normal ideal), results in a quantitative improvement of Theorem 3.1. Read the rest of this entry »

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

580 -Cardinal arithmetic (6)

February 17, 2009

3. The Galvin-Hajnal theorems.

In this section I want to present two theorems of Galvin and Hajnal that greatly generalize Silver’s theorem. I focus on a “pointwise” (or everywhere) result, that gives us information beyond the pointwise theorems from last lecture, like Corollary 23. Then I state a result where the hypotheses, as in Silver’s theorem, are required to hold stationarily rather than everywhere. From this result, the full version of Silver’s result can be recovered.

Both results appear in the paper Fred Galvin, András Hajnal, Inequalities for Cardinal Powers, The Annals of Mathematics, Second Series, 101 (3), (May, 1975), 491–498, available from JSTOR, that I will follow closely. For the notion of \kappa-inaccessibility, see Definition II.2.20 from last lecture.  

Theorem 1. Let \kappa,\lambda be uncountable regular cardinals, and suppose that \lambda is \kappa-inaccessible. Let (\kappa_\alpha:\alpha<\kappa) be a sequence of cardinals such that \prod_{\alpha<\beta}\kappa_\alpha<\aleph_\lambda for all \beta<\kappa. Then also \prod_{\alpha<\kappa}\kappa_\alpha<\aleph_\lambda.

The second theorem will be stated next lecture. Theorem 1 is a rather general result; here are some corollaries that illustrate its reach:  

Corollary 2. Suppose that \kappa,\lambda are uncountable regular cardinals, and that \lambda is \kappa-inaccessible. Let \tau be a cardinal, and suppose that \tau^\sigma<\aleph_\lambda for all cardinals \sigma<\kappa. Then also \tau^\kappa<\aleph_\lambda.

Proof. Apply Theorem 1 with \kappa_\alpha=\tau for all \alpha<\kappa. {\sf QED}

Corollary 3. Suppose that \kappa,\lambda are uncountable regular cardinals, and that \lambda is \kappa-inaccessible. Let \tau be a cardinal of cofinality \kappa, and suppose that 2^\sigma<\aleph_\lambda for all cardinals \sigma<\tau. Then also 2^\tau<\aleph_\lambda.

Proof. Let (\tau_\alpha:\alpha<\kappa) be a sequence of cardinals smaller than \tau such that \tau=\sum_\alpha\tau_\alpha, and set \kappa_\alpha=2^{\tau_\alpha} for all \alpha<\kappa. Then \prod_{\alpha<\beta}\kappa_\alpha=2^{\sum_{\alpha<\beta}\tau_\alpha}<\aleph_\lambda for all \beta<\kappa, by assumption. By Theorem 1, \prod_{\alpha<\kappa}\kappa_\alpha=2^{\sum_\alpha\tau_\alpha}=2^\tau<\aleph_\lambda as well. {\sf QED}    

Corollary 4. Let \kappa,\rho,\tau be cardinals, with \rho\ge2 and \kappa regular and uncountable. Suppose that \tau^\sigma<\aleph_{(\rho^\kappa)^+} for all cardinals \sigma<\kappa. Then also \tau^\kappa<\aleph_{(\rho^\kappa)^+}.

Proof. This follows directly from Corollary 2, since \lambda=(\rho^\kappa)^+ is regular and \kappa-inaccessible. {\sf QED}

Corollary 5. Let \rho,\tau be cardinals, with \rho\ge2 and \tau of uncountable cofinality \kappa. Suppose that 2^\sigma<\aleph_{(\rho^\kappa)^+} for all cardinals \sigma<\tau. Then also 2^\tau<\aleph_{(\rho^\kappa)^+}.

Proof. This follows directly from Corollary 3 with \lambda=(\rho^\kappa)^+. {\sf QED}

Corollary 6. Let \xi be an ordinal of uncountable cofinality, and suppose that 2^{\aleph_\alpha}<\aleph_{(|\xi|^{{\rm cf}(\xi)})^+} for all \alpha<\xi. Then also 2^{\aleph_\xi}<\aleph_{(|\xi|^{{\rm cf}(\xi)})^+}.

Proof. This follows from Corollary 5 with \rho=|\xi|, \tau=\aleph_\xi, and \kappa={\rm cf}(\xi). {\sf QED}

Corollary 7. Let \xi be an ordinal of uncountable cofinality, and suppose that \aleph_\alpha^\sigma<\aleph_{(|\xi|^{{\rm cf}(\xi)})^+} for all cardinals \sigma<{\rm cf}(\xi) and all \alpha<\xi. Then also \aleph_\xi^{{\rm cf}(\xi)}<\aleph_{(|\xi|^{{\rm cf}(\xi)})^+}.

Proof. This follows from Corollary 4: If \sigma<{\rm cf}(\xi), then \aleph_\xi^\sigma=\aleph_\xi\sup_{\alpha<\xi}\aleph_\alpha^\sigma, by Theorem II.1.10 from lecture II.2. But \xi<(|\xi|^{{\rm cf}(\xi)})^+, so both \aleph_\xi and \sup_{\alpha<\xi}\aleph_\alpha^\sigma are strictly smaller than \aleph_{(|\xi|^{{\rm cf}(\xi)})^+}. {\sf QED} 

Corollary 8. If 2^{\aleph_\alpha}<\aleph_{(2^{\aleph_1})^+} for all \alpha<\omega_1, then also  2^{\aleph_{\omega_1}}<\aleph_{(2^{\aleph_1})^+}.

Proof. By Corollary 5. {\sf QED}

Corollary 9.  If \aleph_\alpha^{\aleph_0}<\aleph_{(2^{\aleph_1})^+} for all \alpha<\omega_1, then also  \aleph_{\omega_1}^{\aleph_1}<\aleph_{(2^{\aleph_1})^+}.

Proof. By Corollary 7. {\sf QED}

Notice that, as general as these results are, they do not provide us with a bound for the size of 2^\tau for \tau the first cardinal of uncountable cofinality that is a fixed point of the aleph sequence, \tau=\aleph_\tau, not even under the assumption that \tau is a strong limit cardinal. 

Read the rest of this entry »

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