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


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}subseteqprod{mathcal A}:=prod_{alpha<kappa}A_alpha} and whenever {fne gin{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:kapparightarrow{sf ORD},} then {aleph_f=(aleph_{f(alpha)}:alpha<kappa).} Then, for any {f:kapparightarrowlambda}, {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:kapparightarrow{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 »


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_alphatau_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_alphatau_alpha}=2^tau<aleph_lambda as well. {sf QED}    

Corollary 4. Let kappa,rho,tau be cardinals, with rhoge2 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 rhoge2 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_xisup_{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 »