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.

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}\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 »

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.