580 -Cardinal arithmetic (2)

At the end of last lecture, we showed Theorem 7, König’s lemma, stating that if \kappa_i<\lambda_i for all i\in I, then \sum_{i\in I}\kappa_i<\prod_i\lambda_i. We begin by looking at some  corollaries:

Corollary 8.

  1. If \beta is a limit ordinal and (\kappa_i:i<\beta) is a strictly increasing sequence of nonzero cardinals, then \sum_{\alpha<\beta}\kappa_\alpha<\prod_{\alpha<\beta}\kappa_\alpha.
  2. If (\kappa_i:i\in I) is an I-indexed sequence of nonzero cardinals and \kappa_i<\sum_{j\in I}\kappa_j for all i\in I, then \sum_i\kappa_i<\left(\sum_i\kappa_i\right)^{|I|}.
  3. (Cantor) \kappa<2^\kappa.
  4. For any infinite \kappa, one has \kappa<\kappa^{{\rm cf}(\kappa)}.
  5. {\rm cf}(2^\kappa)>\kappa.

Proof. 1. Notice that \kappa_i<\kappa_{i+1} for all i\in\beta, so \sum_i\kappa_i<\prod_i\kappa_{i+1} by König’s lemma. But, by an obvious injection, \prod_i\kappa_{i+1}\le\prod_i\kappa_i.

2. Let \lambda=\sum_{a\in I}\kappa_a. If \kappa_i<\lambda for all i\in I, then König’s lemma gives us that \sum_i\kappa_i<\prod_i\lambda=\lambda^{|I|}=\left(\sum_i\kappa_i\right)^{|I|}.

3. Use König’s lemma with I=\kappa, \kappa_\alpha=1 and \lambda_\alpha=2 for all \alpha<\kappa. Then \kappa=\sum_{\alpha\in\kappa}1<\prod_{\alpha\in\kappa}2=2^\kappa.

4. Let f:{\rm cf}(\kappa)\to\kappa be a cofinal function. Let \kappa_\alpha=1+|f(\alpha)| and \lambda_\alpha=\kappa for all \alpha<{\rm cf}(\kappa). Note that \kappa=\bigcup_\alpha f(\alpha)\le\sum_\alpha |f(\alpha)|\le\sum_\alpha\kappa_\alpha=\le\kappa\cdot{\rm cf}(\kappa)=\kappa and \prod_\alpha\lambda_\alpha=\kappa^{{\rm cf}(\kappa)}.

5. (2^\kappa)^{{\rm cf}(\kappa)}=2^{\kappa\cdot\kappa}=2^\kappa but, by 4., (2^\kappa)^{{\rm cf}(2^\kappa)}>2^\kappa. {\sf QED}

Note that once one decodes the argument, the proof of Cantor’s theorem above is exactly the same as the usual proof. On the other hand, Corollary 8.5 gives us more information and begins to show that the notion of cofinality is quite relevant in the study of cardinal arithmetic; much more dramatic illustrations of this claim are shown below. König’s lemma is the first genuinely new result in cardinal arithmetic (with choice) past Cantor’s theorem. For example, Specker’s result in Section I.5 and the Halbeisen-Shelah theorem in Section I.6 are both trivial once {\sf AC} is assumed. 

Some of the results that follow are available elsewhere in this blog, but I include them here to make these notes reasonably self-contained.

Definition. A cardinal \kappa is strong limit iff 2^\rho<\kappa for all cardinals \rho<\kappa.

Notice that the name is justified, since any strong limit is in particular (\aleph_0 or) a limit cardinal, i.e., an \aleph_\lambda with \lambda a limit ordinal.

Of course, \aleph_0 is a strong limit cardinal and, if {\sf GCH} holds below \aleph_\omega, then \aleph_\omega is also strong limit. Without this assumption, examples of strong limit cardinals can be found by iterating the power set operation. More precisely, define the sequence of beth cardinals by \beth_0=\omega, \beth_{\alpha+1}=2^{\beth_\alpha} and \beth_\lambda=\sup_{\alpha<\lambda}\beth_\alpha for \lambda a limit ordinal. Then the strong limit cardinals are precisely the \beth_\lambda with \lambda=0 or a limit ordinal.

Theorem 9. (Bukovský-Hechler). 

  1. If \kappa is infinite then 2^\kappa=(\sup_{\rho<\kappa}2^{|\rho|})^{{\rm cf}(\kappa)}. 
  2. In particular, if \kappa is strong limit, then 2^\kappa=\kappa^{{\rm cf}(\kappa)}.
  3. Let \kappa be singular, and assume that the exponential \rho\mapsto 2^\rho is eventually constant below \kappa;  i.e., there is some \tau and some \rho<\kappa such that for all cardinals \lambda with \rho\le\lambda<\kappa, one has 2^\rho=2^\lambda=\tau. Then also 2^\kappa=\tau.

The theorem illustrates that the exponential map must satisfy certain restrictions, at least on its values on the singular cardinals. It is well known since the beginnings of forcing, from the work of Easton, that the exponential is `essentially’ arbitrary on the regular cardinals except that, of course, it is monotonic: If \lambda<\tau then 2^\lambda\le 2^\tau, and must obey König’s lemma, {\rm cf}(2^\kappa)>\kappa. However, once large cardinals are considered, these are not the only restrictions. We will show this in Section 4.

Proof. 1. Let \kappa be infinite and let \tau=\sup_{\rho<\kappa}2^{|\rho|}. Let f:{\rm cf}(\kappa)\to\kappa be strictly increasing, and let \kappa_\alpha=|f(\alpha)\setminus\bigcup_{\beta<\alpha}f(\beta)| for all \alpha<{\rm cf}(\kappa), so \kappa=\sum_\alpha\kappa_\alpha. Then 2^\kappa=2^{\sum_\alpha\kappa_\alpha}=\prod_\alpha 2^{\kappa_\alpha}, as the obvious bijection verifies. But \prod_\alpha 2^{\kappa_\alpha}\le\prod_\alpha \tau=\tau^{{\rm cf}(\kappa)}. On the other hand, clearly 2^{\kappa_\alpha}\le 2^\kappa for all \alpha<{\rm cf}(\kappa), so \tau\le 2^\kappa and therefore \tau^{{\rm cf}(\kappa)}\le (2^\kappa)^{{\rm cf}(\kappa)}=2^\kappa. The result follows from these two inequalities.

2. If \kappa is strong limit and \tau is as above, then \tau\le\kappa. On the other hand, for any \lambda<\kappa, \lambda<2^\lambda\le\tau, so \tau=\kappa, and 2. follows from 1. 

3. Assume \kappa is singular. With \tau as above, if \lambda<\kappa is sufficiently large, 2^\lambda=\tau. But then \tau^{{\rm cf}(\kappa)}=\tau, since we can take \lambda>{\rm cf}(\kappa). The result follows from 1. {\sf QED}

For example, if 2^{\aleph_0}=2^{\aleph_n}=\aleph_{\omega+1} for all n<\omega (this situation is easily achieved by forcing) then also 2^{\aleph_\omega}=\aleph_{\omega+1}.

The next result provides an easy `algorithm’ to compute any power, provided we know the values of the exponential function, the cofinality map, and the gimel function \gimel(\kappa)=\kappa^{{\rm cf}(\kappa)}. I’ll expand on this remark after the proof of the theorem. 

Theorem 10. Let \kappa and \lambda be infinite cardinals. Let \tau=\sup_{\rho<\kappa}|\rho|^\lambda. Then 

\displaystyle \kappa^\lambda=\left\{\begin{array}{cl} 2^\lambda & \mbox{if }\kappa\le 2^\lambda,\\ \kappa\cdot\tau & \mbox{if }\lambda<{\rm cf}(\kappa),\\ \tau & \begin{array}{l}\mbox{if }{\rm cf}(\kappa)\le\lambda,2^\lambda<\kappa,\mbox{ and }\\ \rho\mapsto|\rho|^\lambda\mbox{ is eventually constant below }\kappa,\end{array}\\ \kappa^{{\rm cf}(\kappa)} & \mbox{otherwise.}\end{array}\right.

Proof. 1. If \kappa\le 2^\lambda, then 2^\lambda\le\kappa^\lambda\le(2^\lambda)^\lambda=2^\lambda.

2. If \lambda<{\rm cf}(\kappa) then any function f:\lambda\to\kappa is bounded, so {}^\lambda\kappa=\bigcup_{\alpha<\kappa}{}^\lambda\alpha, and \kappa^\lambda\le\sum_\alpha|\alpha|^\lambda=\kappa\cdot\rho\le\kappa^\lambda.

3. Suppose that {\rm cf}(\kappa)\le\lambda, 2^\lambda<\kappa, and \rho\mapsto|\rho|^\lambda is eventually constant (and equal to \tau) as \rho approaches \kappa. 

Since \kappa>{\rm cf}(\kappa), \kappa is a singular cardinal and we can choose a strictly increasing sequence of cardinals (\kappa_\alpha:\alpha<{\rm cf}(\kappa)) cofinal in \kappa such that \kappa_\alpha^\lambda=\tau for all \alpha<{\rm cf}(\kappa). In particular, \tau^\lambda=\tau.

Note that for each \alpha<{\rm cf}(\kappa), \kappa_\alpha<\prod_{i\in{\rm cf}(\kappa)}\kappa_i, so also \kappa=\sup_\alpha\kappa_\alpha\le\prod_\alpha\kappa_\alpha. [Of course, it follows from König’s lemma that in fact we have a strict inequality, but we only need this weaker estimate.]

We now have \kappa^\lambda\le(\prod_\alpha\kappa_\alpha)^\lambda=\prod_\alpha\kappa_\alpha^\lambda=\prod_\alpha \tau =\tau^{{\rm cf}(\kappa)}=\tau. The other inequality is clear.

4. Finally, suppose that {\rm cf}(\kappa)\le\lambda, 2^\lambda<\kappa, and \rho\mapsto|\rho|^\lambda is not eventually constant as \rho approaches \kappa.

Notice that if \rho<\kappa then |\rho|^\lambda<\kappa. Otherwise, \mu^\lambda=(\mu^\lambda)^\lambda\ge\kappa^\lambda\ge\mu^\lambda for any \rho\le\mu<\kappa, and the map \rho\mapsto|\rho|^\lambda would be eventually constant below \kappa after all. Hence, \tau=\kappa.

Choose an increasing sequence of cardinals (\kappa_\alpha:\alpha<{\rm cf}(\kappa)) cofinal in \kappa. Then \kappa^\lambda\le(\prod_\alpha\kappa_\alpha)^\lambda=\prod_\alpha\kappa_\alpha^\lambda\le\prod_\alpha\kappa= \kappa^{{\rm cf}(\kappa)}. The other inequality is clear. {\sf QED}

Remark. By induction, it follows from Theorem 10 that the computation of the function (\kappa,\lambda)\mapsto\kappa^\lambda `reduces’ to computations of the functions \lambda\mapsto 2^\lambda and \lambda\mapsto\gimel(\lambda) for \lambda a cardinal, and the function \alpha\mapsto{\rm cf}(\alpha) for \alpha an ordinal. More precisely, if M and N are two models of set theory (with choice) with the same ordinals, and the values of any of these three functions are the same whether they are computed in M or in N, then also all the powers \kappa^\lambda are the same, whether they are computed in M or in N.

Forcing has shown that there is not much one can say about the exponential function \lambda\mapsto 2^\lambda when restricted to successor cardinals and small large cardinals. This indicates that to understand cardinal arithmetic, one’s efforts must concentrate on the exponential function on singular and large cardinals, and  on the gimel function.

In fact, the gimel function suffices to compute the exponential \lambda\mapsto2^\lambda, by Theorem 9: First, 2^\kappa=\kappa^\kappa=\gimel(\kappa) for \kappa regular. Assume now that \kappa is singular. Let \tau=\sup_{\rho<\kappa}2^{|\rho|}. If \rho\mapsto 2^{|\rho|} is not eventually constant below \kappa, then clearly {\rm cf}(\tau)={\rm cf}(\kappa), and 2^\kappa=\gimel(\tau), by Theorem 9.1, while if \rho\mapsto 2^{|\rho|} is eventually constant below \kappa, then 2^\kappa=\tau, by Theorem 9.3.

This observation explains why the bulk of research in cardinal arithmetic concentrates on understanding the gimel function. As we will see next time, this naturally leads to the study of certain infinite products. This latter study has proved quite fruitful. We will study two outcomes: Silver’s theorem, and one of the Galvin-Hajnal results. Then, we will briefly mention how Shelah has extended and generalized these theorems with his development of pcf theory.

This entry was posted on Saturday, February 7th, 2009 at 12:18 pm and is filed under 580: Topics in set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

18 Responses to 580 -Cardinal arithmetic (2)

  1. hurburble says:
    February 8, 2009 at 3:31 pm

    Thank you so much professor Caicedo for these online classes.
    In the paragraph right before the last one, I think you meant to write (if I am not mistaken) 2^\kappa=\kappa^{{\rm cf}(\kappa)}=\gimel(\kappa) (the formula right after “by theorem 9”).

    Reply
  2. andrescaicedo says:
    February 8, 2009 at 4:38 pm

    Hi,
    What I meant is: First, 2^\kappa=\kappa^\kappa, and second, \kappa={\rm cf}(\kappa) (trivially) if \kappa is regular, in which case it then just happens that \kappa^\kappa=\gimel(\kappa).
    There was a typo at the end of that paragraph, though; the second “is not eventually constant” should have been “is eventually constant.” It is now fixed.

    Reply
  3. hurburble says:
    February 8, 2009 at 6:06 pm

    Oh I see, indeed \kappa is a regular cardinal so we can write \kappa={\rm cf}(\kappa). Thank you professor Caicedo.

    I don’t want to take to much of your time but I would like to mention a theorem in Jech’s Set Theory whose demonstration seems quite hard to understand. It is Pospisil Theorem in page 75 which states that for every infinite cardinal \kappa, there exist 2^{2^\kappa} uniform ultrafilters on \kappa. First Jech proves a lemma stating that there exists an independent family of subsets of \kappa of cardinality 2^\kappa.
    He defines an independent family: a family A of subsets of \kappa is independent if for any distinct X_1,\dots, X_n, Y_1,\dots,Y_m \in A, the intersection
    X_1\cap \dots\cap X_n \cap (\kappa \setminus Y_1) \cap\dots\cap (\kappa \setminus Y_m) has cardinality \kappa.

    Now in the proof of Pospisil’s theorem, Jech states: Let A be an independent family of subsets of \kappa.
    For every function f: A \to \{0,1\}, consider this family of subsets of \kappa:
    G_f=\{X:|\kappa \setminus X|<\kappa\} \cup \{X: f(X)=1\} \cup \{\kappa \setminus X : f(X)=0\}. This family is independent and thus has the finite intersection property (he does this to prove that this family is included in an ultrafilter because thx to a previous lemma if a family has the finite intersection property then it is included in a filter, and then we extend it to an ultrafilter).
    The problem is that I can’t see why this family independent and has the finite intersection property.

    Any hint?
    Thank you.

    Reply
  4. 580 -Cardinal arithmetic (3) « Teaching page says:
    February 9, 2009 at 5:06 pm

    […] the end of last lecture we showed Theorem 10, a general result that allows us to compute products for infinite cardinals […]

    Reply
  5. andrescaicedo says:
    February 9, 2009 at 5:16 pm

    Hi hurburble,
    I don’t think you need (or want) to prove that G_f is independent. This is false, just look at sets in the first of the three members of the union that make up G_f. What you want is that
    1. G_f has the finite intersection property. This is easy since A is independent. I’ll let you think about it on your own.
    2. Any ultrafilter extending G_f is uniform. This is easy from the sets in the first of the three members of the union that make up G_f.
    3. If f\ne g then G_f\cup G_g does not have the finite intersection property. You want this to guarantee that any ultrafilter extending G_f is different from any ultrafilter extending G_g. This is easy from the fact that if f\ne g then for some X, f(X)=0 but g(X)=1.
    4. There are at least 2^{2^\kappa} many functions f, so there are at least that many collections G_f and therefore at least that many ultrafilters. This is easy from the size of A.

    Reply
  6. hurburble says:
    February 10, 2009 at 9:31 am

    Hi Mr Caicedo,

    Thank you so much for your explanation

    1) Indeed, you are right, G_f is not independent, it is A which is independent.
    I think I figured out why G_f has the finite intersection property.
    if A is independent then none of its elements can be the null set. If none of the elements of this family can be the null set then G_f has the finite intersection property because none of the elements of G_f can be the null set since G_f is constructed with the help of elements of A. In other words the elements of G_f are pairwise disjoint.

    2)Any ultrafilter extending G_f is uniform because for all X \in G_f the cardinality of X is \kappa.

    3) I now see why we don’t want G_f \cup G_g to have the finite intersection property. It is to guarantee that we have distinct ultrafilters in the end.

    4) Indeed, the cardinality of A is 2^{\kappa}.

    Again, thank you!

    Reply
  7. andrescaicedo says:
    February 10, 2009 at 11:39 am

    Hi again,

    One last pass at it:

    1) What you say is not enough to guarantee that G_f has the finite intersection property. I also assume at the end you meant “not pairwise disjoint,” but what you say does not imply this. You actually need to use the fact that A is independent, and the way that G_f is defined.

    2) What you say is not enough. You need to use the way that G_f is defined.

    3) and 4) are fine.

    Reply
  8. hurburble says:
    February 10, 2009 at 2:22 pm

    Hi again,

    1) Except for the fact that any finite subset of G_f has nonempty intersection because G_f is constructed with elements of A, I am not able to find another argument to make it accurate.

    2) It seems to me that the sets that make up G_f are large enough as to have an impact on the cardinality of the set resulting from taking them out of \kappa, which means that they have infinite cardinality cofinal in \kappa. Except from that argument, I can’t see the full justification.

    Reply
  9. hurburble says:
    February 10, 2009 at 2:38 pm

    I think the source of all my trouble comes from me being in difficulty understanding the way an independent family A is defined.

    It seems to me that in order for the condition to be fulfiled (i.e. for the intersection to have cardinality \kappa) we need to choose the sets X_1,...,X_n large enough, with a cardinality \kappa and the sets Y_1,...,Y_m small enough (with a cardinality that can’t be mapped cofinally in \kappa) so we can end up with an intersection of cardinality \kappa.

    Reply
  10. hurburble says:
    February 10, 2009 at 3:19 pm

    Does G_f has the finite intersection property because it is a filter (it looks like a principal filter because of the condition \kappa \backslash X) and it is filter because of A being independent?

    I am afraid that’s all I can make out of all of this.

    Reply
  11. 580 -Cardinal arithmetic (4) « Teaching page says:
    February 11, 2009 at 11:25 pm

    […] any power can be computed from the cofinality and gimel functions (see the Remark at the end of lecture II.2). What we can say about the numbers varies greatly depending on whether is regular or not. If is […]

    Reply
  12. 580 -Cardinal arithmetic (5) « Teaching page says:
    February 13, 2009 at 2:49 pm

    […] Before stating Silver’s result, we need one additional result. Recall that was introduced last lecture in Definition 4, it is the statement that for all infinite cardinals We break the result into two parts, Lemmas 17 and 18, corresponding respectively to Theorems II.1.9 (describing the behavior of the exponential ) and II.1.10 (describing the computation of powers ) from lecture II.2. […]

    Reply
  13. 580 -Cardinal arithmetic (6) « Teaching page says:
    February 17, 2009 at 2:58 pm

    […] This follows from Corollary 4: If , then by Theorem II.1.10 from lecture 2. But so both and are strictly smaller than […]

    Reply
  14. 580 -Cardinal arithmetic (7) « Teaching page says:
    March 4, 2009 at 12:21 am

    […] 2, recall from Corollary 8 in lecture II.2 […]

    Reply
  15. Set theory seminar – Marion Scheepers: Coding strategies (IV) « Teaching blog says:
    October 12, 2010 at 3:15 pm

    […] , then . I have addressed both these computations in my lecture notes for Topics in Set Theory, see here and […]

    Reply
  16. Set theory seminar – Marion Scheepers: Coding strategies (IV) « A kind of library says:
    August 26, 2012 at 2:50 pm

    […] , then . I have addressed both these computations in my lecture notes for Topics in Set Theory, see here and […]

    Reply
  17. 580 -Cardinal arithmetic (4) « A kind of library says:
    November 30, 2012 at 2:04 am

    […] any power can be computed from the cofinality and gimel functions (see the Remark at the end of lecture II.2). What we can say about the numbers varies greatly depending on whether is regular or not. If is […]

    Reply
  18. 580 -Cardinal arithmetic (7) | A kind of library says:
    June 2, 2018 at 5:43 pm

    […] 2, recall from Corollary 8 in lecture II.2 […]

    Reply

Leave a comment