580 -Cardinal arithmetic (6)

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 be a sequence of cardinals such that $prod_{alpha for all $beta Then also $prod_{alpha

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 for all cardinals $sigma Then also $tau^kappa

Proof. Apply Theorem 1 with $kappa_alpha=tau$ for all $alpha ${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 for all cardinals $sigma Then also $2^tau

Proof. Let $(tau_alpha:alpha be a sequence of cardinals smaller than $tau$ such that $tau=sum_alphatau_alpha,$ and set $kappa_alpha=2^{tau_alpha}$ for all $alpha Then $prod_{alpha for all $beta by assumption. By Theorem 1, $prod_{alpha as well. ${sf QED}$

Corollary 4. Let $kappa,rho,tau$ be cardinals, with $rhoge2$ and $kappa$ regular and uncountable. Suppose that $tau^sigma for all cardinals $sigma Then also $tau^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 for all cardinals $sigma Then also $2^tau

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} for all $alpha Then also $2^{aleph_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 for all cardinals $sigma<{rm cf}(xi)$ and all $alpha Then also $aleph_xi^{{rm cf}(xi)}

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

Corollary 8. If $2^{aleph_alpha} for all $alpha then also  $2^{aleph_{omega_1}}

Proof. By Corollary 5. ${sf QED}$

Corollary 9.  If $aleph_alpha^{aleph_0} for all $alpha then also  $aleph_{omega_1}^{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.

Now I proceed to the proof of Theorem 1.

Definition 10. Let $kappa$ be a cardinal and let ${mathcal A}=(A_alpha:alpha be a sequence of nonempty sets. A set ${mathcal F}subseteqprod_alpha A_alpha$ is an almost disjoint transversal system (a.d.t.) for ${mathcal A}$ iff $|{alpha:f(alpha)=g(alpha)}| whenever $f,gin{mathcal F}.$

As in the proof of Silver’s theorem, Theorem 1 follows from an analysis of the possible sizes of a.d.t.s for a particular sequence ${mathcal A}.$

Theorem 11. Let $kappa,lambda$ be uncountable regular cardinals, and suppose that $lambda$ is $kappa$-inaccessible. Let ${mathcal A}=(A_alpha : alpha be a sequence of nonempty sets such that $|A_alpha| for all $alpha Let ${mathcal F}$ be an a.d.t. for ${mathcal A}.$ Then $|{mathcal F}|

Before proving Theorem 11, I show how it implies Theorem 1:

Lemma 12. Let $kappa$ be a cardinal and let $(kappa_alpha:alpha be a sequence of cardinals. For $alpha let $A_alpha$ be the set product $prod_{beta and set ${mathcal A}=(A_alpha:alpha Then there is an a.d.t. ${mathcal F}$ for ${mathcal A}$ with $|{mathcal F}|=prod_{alpha

Proof of Theorem 1. Let $kappa,$ $lambda,$ and $(kappa_alpha:alpha be as in the statement of Theorem 1. Let ${mathcal A}=(A_alpha : alpha where $A_alpha=prod_{beta for all $alpha By Lemma 12 there is an a.d.t. ${mathcal F}$ for ${mathcal A}$ of size $prod_{alpha By assumption, $|A_alpha| for all $alpha and it follows from Theorem 11 that $|{mathcal F}| as well. ${sf QED}$

Proof of Lemma 12. Let $tau$ be the cardinal $prod_{alpha Consider an injective enumeration $(g_eta:eta of the set product $prod_alphakappa_alpha.$ For $eta let $f_etainprod_{alpha be given by $f_eta(alpha)=g_etaupharpoonrightalpha$ for all $alpha Clearly, $eta implies that ${alpha:f_eta(alpha)=f_nu(alpha)}$ is an ordinal below $kappa,$ namely, the least $beta$ such that $g_eta(beta)ne g_nu(beta).$ It follows that ${mathcal F}={f_eta:eta is an a.d.t. for ${mathcal A}.$ ${sf QED}$

All that remains is to show Theorem 11.

Proof. The argument is organized as an induction. For this, we need a rank on which to induct.

Definition 13. Let $kappa$ be a cardinal. Let $<_{b,kappa}$ be the partial ordering on ${}^kappa{sf ORD}$ given by $f<_{b,kappa}g$ iff $|{alpha (The subindex $b$ stands for “bounded.”)

Lemma 14. If $kappa$ is a regular, uncountable cardinal, then $<_{b,kappa}$ is well-founded.

The result is fairly general. For example, instead of the ideal of bounded sets, we could have used the ideal of nonstationary sets in Definition 13 (i.e., requiring that $f(alpha) for club many values of $alpha$), and Lemma 14 would still hold; all we need is a $sigma$-complete ideal. Below I follow the usual convention that a $tau$-complete ideal means one closed under unions of any length less that $tau.$

Proof. Let ${mathcal C}$ be the filter of cobounded subsets of $kappa.$ Notice that ${mathcal C}$ is $kappa$-complete, by regularity of $kappa.$ In particular, $<_{b,kappa}$ is indeed a partial order: If $f<_{b,kappa}g$ and $g<_{b,kappa}h,$ then $f<_{b,kappa}h$ because ${alpha ${alpha : g(alpha)< h(alpha)}$ contains the intersection of two sets in ${mathcal C},$ so it is also in ${mathcal C}.$

To prove well-foundedness, consider a $<_{b,kappa}$-decreasing sequence $(f_n : n and let $A_n={alpha : f_{n+1}(alpha) so $A_nin{mathcal C}$ for all $n.$ But then $A=bigcap_n A_nin{mathcal C}.$ In particular, $Aneemptyset.$ If $alphainbigcap_nA_n,$ then $forall n,(f_{n+1}(alpha) and $(f_n(alpha) : n is a decreasing sequence of ordinals, contradiction. ${sf QED}$

Whenever we are given a well-founded partial order on a set $X,$ we can assign a rank (an ordinal) to the elements of $X,$ as follows:

Definition 15. Let $(X,<)$ be well-founded. The rank $|x|_<$ of a set $xin X$ is defined by transfinite recursion as $displaystyle |x|_<=sup{|y|_<+1 : y

It follows from standard arguments that, in the situation of Definition 15, $|cdot|_< : Xto{sf ORD}$ is well-defined. For example, considering some $x$ for which $|x|_<$ is not defined (or unbounded), it follows that for some $y either $|y|_<$ is not defined or it is also unbounded. This easily gives us a strictly $<$-decreasing sequence of members of $X,$ contradicting that $<$ is well-founded. It is immediate from the definition that if $y then $|y|_< < |x|_<.$

Definition 16. Given a cardinal $kappa$ and a sequence ${mathcal B}=(B_alpha:alpha of nonempty sets, let $displaystyle T({mathcal B})=sup{|{mathcal F}| : {mathcal F}mbox{ is an a.d.t. for }{mathcal B}}.$

Clearly,

• $T({mathcal B})=T({mathcal C})$ for ${mathcal C}=(|B_alpha|:alpha i.e., $T({mathcal B})$ only depends on the cardinalities of the terms of the sequence ${mathcal B}.$
• (Monotonicity). If ${mathcal B}=(B_alpha:alpha and ${mathcal C}=(C_alpha:alpha are sequences of nonempty sets with $|C_alpha|le|B_alpha|$ for all $alpha,$ then $T({mathcal C})le T({mathcal B}).$

For $fin{}^kappalambda$ let $T(aleph_f)$ be $T({mathcal B})$ where ${mathcal B}=aleph_f:=(aleph_{f(alpha)}:alpha By monotonicity, Theorem 11 will follow if I can show that $T(aleph_f) for all $f:kappatolambda,$ since if $A_alpha$ is finite for some $alpha,$ one can just replace it with $aleph_0.$ It is this reformulation that is proved by induction on the $<_{b,kappa}$-rank of $f.$

We argue by contradiction: Assume the claim above fails, and let $f$ be a counterexample of least $<_{b,kappa}$ rank. It is our goal to show that there must be another counterexample of strictly smaller rank. For this, consider the following set:

$displaystyle {mathcal I}={Xsubseteqkappa : exists gin{}^kappalambda,forall alphain X,(g(alpha) $displaystyle mbox{or }g(alpha)=0)mbox{ and }T(aleph_g)gealeph_lambda}.$

All we need from Lemma 17 below is that ${mathcal I}$ is a nontrivial proper ideal (i.e., it is closed under finite unions, does not contain $kappa,$ and contains the bounded sets), but proving $kappa$-completeness requires about the same amount of work.

Lemma 17. ${mathcal I}$ is a nontrivial $kappa$-complete proper ideal on $kappa.$

Proof. We prove this in four steps.

• Clearly, ${mathcal I}$ is $subseteq$-downward closed.
• $kappanotin{mathcal I}.$

Suppose $kappain{mathcal I},$ as witnessed by $g,$ so $T(aleph_g)gealeph_lambda$ and for all $alpha $g(alpha) or $g(alpha)=0.$

By $<_{b,kappa}$-minimality of $f,$ ${alpha ${alpha : f(alpha)=0}$ has size $kappa.$

If ${mathcal F}$ is an a.d.t. for $aleph_g,$ then for $hne jin{mathcal F},$ we have that ${alpha : h(alpha)=j(alpha)}$ is bounded, so for $kappa$ many values of $alpha,$ $h(alpha)ne j(alpha),$ and they are finite! Let $A$ be a subset of ${alpha of size $kappa.$ The number of functions from $A$ to $aleph_0$ is $|{}^Aomega|=aleph_0^kappa,$ and there are at most $|{mathcal P}(kappa)|=2^kappa$ many such sets $A,$ so the number of elements of ${mathcal F}$ is at most $2^kappacdotaleph_0^kappa=2^kappa,$ and $|T(aleph_g)|le2^kappa contradiction.

It follows that $kappanotin{mathcal I},$ i.e., ${mathcal I}$ is proper.

• If $Xsubseteqkappa$ is bounded, then $Xin{mathcal I}.$

For $Xsubsetkappa$ bounded, let $g_X:kappatolambda$ be given by $g_X(alpha)=f(alpha)$ if $alphanotin X,$ and $g_X(alpha)=0$ otherwise.

I claim that $g_X$ witnesses that $Xin{mathcal I}.$ Since $forallalphain X,(g(alpha)=0),$ it suffices to show that $T(aleph_{g_X})gealeph_lambda.$

Let ${mathcal F}$ be an a.d.t. for $aleph_f,$ and define $hat{mathcal F}$ as ${hat h : hin{mathcal F}}$ where $hat h(alpha)=left{begin{array}{cl}h(alpha)&mbox{if }alphanotin X,\ 0&mbox{otherwise,}end{array}right.$ so $hat hinprod_{alpha and $hmapstohat h$ is injective since $X$ is bounded and $h(alpha)ne g(alpha)$ for all but boundedly many values of $alpha.$ Thus, $hat{mathcal F}$ is an a.d.t. for $aleph_{g_X},$ and it follows that $T(aleph_{g_X})ge T(aleph_f)gelambda.$

• It remains to argue that ${mathcal I}$ is closed under unions of fewer than $kappa$ sets.

For this, let $X_beta$ be sets in ${mathcal I}$ for $beta where $gamma as witnessed by functions $f_beta,$ $beta Let $X=bigcup_{beta Let $g : kappatolambda$ be given by $g(alpha)=min_{beta for $alpha,kappa.$

Let $mu We argue that there is an a.d.t. ${mathcal F}_mu$ for $aleph_g$ of size at least $aleph_mu.$ Since this holds for all such $mu,$ it follows that $T(aleph_g)gealeph_lambda,$ and $g$ witnesses that $Xin{mathcal I}.$

To build ${mathcal F}_mu,$ fix an a.d.t. ${mathcal F}^beta$ for $aleph_{f_beta}$ of size $mu$ for each $beta and let $(f_{beta,delta} : delta be an injective enumeration of ${mathcal F}^beta.$

Partition $kappa$ into (possibly empty) sets $Y_beta,$ $beta such that $g(alpha)=f_beta(alpha)$ for all $alphain Y_beta.$ Set $g_delta=bigcup_{beta for $delta so if $alpha and $alphain Y_beta$ then $g_delta(alpha)=f_{beta,delta}(alpha) Let ${mathcal F}_mu={g_delta : delta

Notice that since each ${mathcal F}^beta$ is an a.d.t., if $delta_1nedelta_2 then $Z_beta={alphain Y_beta : f_{beta,delta_1}(alpha)=f_{beta,delta_2}(alpha)}$ is bounded in $kappa,$ so ${alpha: g_{delta_1}(alpha)=g_{delta_2}(alpha)}=bigcup_{beta is bounded in $kappa,$ by regularity of $kappa,$ so ${mathcal F}_mu$ is an a.d.t. for $aleph_g.$ ${sf QED}$

Split $kappa$ as $X_0cup X_1cup X_2$ where $X_0={alpha $X_1={alpha and $X_2={alpha As argued in the proof of Lemma 17, $|X_0| so the following holds:

Claim 18. $X_0in{mathcal I}.$ $Box$

Claim 19. $X_1in{mathcal I}.$

Proof. Since $lambda$ is regular and $kappa then $f : kappatolambda$ is bounded, and we can find $rho such that $f(alpha)lerho$ for all $alpha Let ${mathcal G}={gin{}^kappalambda : forallalphain X_1,(g(alpha) and $forall alphanotin X_1,(g(alpha)=f(alpha))}.$ Then $|{mathcal G}|le|rho|^kappa

For each $mu fix an a.d.t. ${mathcal F}_mu$ for $aleph_f$ with $|{mathcal F}_mu|>aleph_mu.$ For $mu and $gin{mathcal G},$ let ${mathcal F}_{mu,g}={mathcal F}_mucapprod_{alpha so ${mathcal F}_{mu,g}$ is an a.d.t. for $aleph_g.$ Moreover, since $f(alpha)$ is a limit ordinal for all $alphain X_1,$ we have that ${mathcal F}_mu=bigcup_{gin{mathcal G}}{mathcal F}_{mu,g}.$ For $mu sufficiently large so $|rho|^kappa we have that $|{mathcal G}| and therefore there must be some $g_muin{mathcal G}$ such that $|{mathcal F}_{mu,g_mu}|>aleph_mu.$

Since $lambda$ is regular, there must be some fixed $gin{mathcal G}$ such that $g=g_mu$ for $lambda$ many ordinals $mu>|rho|^kappa.$ But then $T(aleph_g)gealeph_lambda,$ and $g$ witnesses that $X_1in {mathcal I},$ as we wanted to show. ${sf QED}$

It follows that $X_2notin{mathcal I}.$

For $Xsubseteq X_2$ define $g_X:kappatolambda$ so $g_X(alpha)=f(alpha)$ if $alphanotin X,$ and $g_X(alpha)+1=f(alpha)$ otherwise. If $Xnotin {mathcal I},$ it follows that $T(aleph_{g_X})=aleph_{rho_X}$ for some $rho_X

Since $2^kappa there is some $rho such that $2^kappa and $rho_Xlerho$ for all $Xin{mathcal P}(X_2)setminus{mathcal I}.$ Let ${mathcal F}$ be an a.d.t. for $aleph_f$ of size strictly larger than $aleph_{rho+1}.$

Given $gin{mathcal F}$ and $Xin{mathcal P}(X_2)setminus{mathcal I},$ let $H_X(g)={hin{mathcal F} : forall alphain X,(h(alpha) It follows that $H_X(g)$ is an a.d.t. for $(B_alpha:alpha where $B_alpha=aleph_{f(alpha)}$ if $alphanotin X$ and $B_alpha=aleph_{g(alpha)}$ otherwise. By definition of $g_X,$ we have that $|B_alpha|lealeph_{g_X(alpha)}$ for all $alpha and it follows that there is an a.d.t. ${mathcal H}$ for $aleph_{g_X}$ of size $|H_X(g)|.$ But then $|H_X(g)|=|{mathcal H}|le T(aleph_{g_X})=aleph_{rho_X}lealeph_rho.$

Let $H(g)=bigcup_{Xin{mathcal P}(X_2)setminus{mathcal I}}H_X(g),$ so $|H(g)|le2^kappacdotaleph_rho=aleph_rho If ${mathcal E}subseteq{mathcal F}$ has size $aleph_{rho+1},$ there is then some $g_0in({mathcal F}setminus{mathcal E})setminusbigcup_{gin{mathcal E}}H(g)$ and some $g_1in{mathcal E}setminus H(g_0).$

We then have that $g_0,g_1in{mathcal F},$ $g_0ne g_1,$ $g_0notin H(g_1)$ and $g_1notin H(g_0).$ It follows that ${alpha in X_2 : g_0(alpha)=g_1(alpha)}in{mathcal I},$ since it is in fact a bounded subset of $kappa.$ Also, ${alphain X_2 : g_0(alpha) since otherwise it is a set $X$ such that $H_X(g_1)$ is defined and $g_0in H_X(g_1)subseteq H(g_1),$ contradiction. Similarly, ${alphain X_2 : g_1(alpha)

This is a contradiction, because then $X_2$ is the union of three sets in ${mathcal I}$ and is therefore also in ${mathcal I}.$ ${sf QED}$

12 Responses to 580 -Cardinal arithmetic (6)

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 and are uncountable regular cardinals, and is -inaccessible, then for any sequence of cardinals such that for all […]

2. […] Proof: Suppose first that is -complete. If there is a -decreasing sequence let Then for all and therefore (since it is in fact an element of ) If is in this intersection, then is an -decreasing sequence of sets, contradiction. (This is just the proof of Lemma 14 in lecture II.6.) […]

3. […] Zapletal has found a proof that uses a modicum of pcf theory, namely, Shelah’s result that any singular cardinal admits a scale, that is, there is an increasing sequence of regular cardinals cofinal in and a sequence of functions such that for all whenever then and whenever then for some Here, is the partial order induced by the ideal of bounded subsets of see Definition 13 in lecture II.6. […]

4. […] extend and improve the Galvin-Hajnal results on powers of singulars of uncountable cofinality (see lectures II.6 and II.7). His first success was an extension to cardinals of countable cofinality. For example: […]

5. hurburble says:

Hi,

In the proof of claim 19, in the line before the last one, should it be $T(aleph_g)gealeph_lambda$ instead of $T(aleph_g)gelambda$ or am I being silly?

Thanks.

6. Hi! There were a few other typos as well: In the proof of Lemma 17, “partition $X$” should have been “partition $kappa$”, and $f_{beta,delta}(alpha) should have been $f_{beta,delta}(alpha) In the paragraph above, $X_{f_beta}$ should have been $aleph_{f_beta}$. They are now fixed.

7. hurburble says:

Hi,

Ha yes, it is true, since the double indexed functions $f_{beta,delta}(alpha)$ go into $aleph_{f_beta(alpha)}$ because ${mathcal F}^beta$ is an a.d.t for $aleph_{f_beta}$ and that’s where the functions are by definition.

Right after the proof of claim 19, in the third paragraph of the proof of $X_2notin{mathcal I},$ do we need “and $B_alpha=aleph_{g(alpha)}$ otherwise” instead of “and $B_alpha=g(alpha)$ otherwise”?

R.A

8. […] 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 , and then replace them with (appropriate codes for) the […]

9. […] 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 , and then replace them with (appropriate codes for) the […]

10. […] Zapletal has found a proof that uses a modicum of pcf theory, namely, Shelah’s result that any singular cardinal admits a scale, that is, there is an increasing sequence of regular cardinals cofinal in and a sequence of functions such that for all whenever then and whenever then for some Here, is the partial order induced by the ideal of bounded subsets of see Definition 13 in lecture II.6. […]

11. […] extend and improve the Galvin-Hajnal results on powers of singulars of uncountable cofinality (see lectures II.6 and II.7). His first success was an extension to cardinals of countable cofinality. For […]