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.

18 Responses to 580 -Cardinal arithmetic (2)

1. hurburble says:

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”).

2. 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.

3. hurburble says:

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 thanks 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 hints?
Thank you.

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

5. 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,$ we have $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.$

6. hurburble says:

Hi Professor 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!

7. 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.

8. hurburble says:

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.

9. hurburble says:

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,\dots,X_n$ large enough, with a cardinality $\kappa$ and the sets $Y_1,\dots,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.$

10. hurburble says:

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

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

11. […] 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 […]

12. […] 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. […]

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

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

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

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

17. […] 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. […]

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