580 -II. Cardinal arithmetic

Homework problem 5. ({\sf ZF}). Show that if \omega\preceq{\mathcal P}(X) then in fact {\mathcal P}(\omega)\preceq{\mathcal P}(X).

Question. If X is Dedekind-finite but {\mathcal P}(X) is Dedekind-infinite, does it follow that there is an infinite Dedekind-finite set Y such that {\mathcal P}(Y)\preceq X?

From now on, until we cover determinacy, we assume the axiom of choice unless stated otherwise.

1. Preliminaries.

We use \kappa,\lambda,\dots to denote cardinals (initial ordinals), usually infinite. As usual, \kappa+\lambda is the cardinality of the disjoint union of two sets, one of size \kappa, and one of size \lambda, \kappa+\lambda=|\kappa\sqcup\lambda|. In fact, we can take \kappa+\lambda=|\kappa+\lambda|, where the latter + denotes ordinal addition.

The advantage of doing this is that we can generalize it to infinite sums.

Definition. Let \gamma be an ordinal and (\alpha_i:i<\gamma) a sequence of ordinals. Then \sum_{i<\gamma}\alpha_i is the ordinal resulting from concatenating the \alpha_i in the given order; formally, we consider the disjoint union \bigcup_{i\in\gamma}\alpha_i\times\{i\} and well-order it by setting (\beta,i)<(\delta,j) iff i<j or else i=j and \beta<\delta.

It is straightforward to check that this is indeed a well-ordering.

Definition. Let I be a set and let (\kappa_i:i\in I) be an I-indexed family of cardinals. Then \sum_{i\in I}\kappa_i=|\sum_{a<|I|}\kappa_{\pi(a)}| where \pi : |I|\to I is a bijection, and the later sum is the infinitary addition of ordinals defined above.

One easily checks that this is well-defined (i.e., the same number is obtained for all bijections \pi), and coincides with the cardinality of the disjoint union of the \kappa_i.

Remark. Without choice, there is no reasonable way of defining \sum_{i\in I}{\mathfrak m}_i, even if we make the sum dependent on the specific index set I. For example, it is consistent to have an uncountable set that is the countable union of sets of size two. The issue is that even if there are bijections between sets A_i and B_i for each i\in I, it is not necessarily the case that there is a function that to each i assigns some such bijection, and it is indeed possible that there is no bijection between the resulting sets \bigcup_{i\in I}A_i and \bigcup_{i\in I}B_i.

Homework problem 6. It is consistent with {\sf ZF} that {\mathbb R} is a countable union of countable sets. It is also consistent with {\sf ZF} that there are infinite Dedekind-finite subsets of {\mathbb R}. However, show that these two statements cannot hold simultaneously.

The first result shows that cardinal addition trivializes in the presence of choice.

Fact 1. Let I be a nonempty set. If the \kappa_i are nonzero, and either I or \sup_{i\in I}\kappa_i is infinite, then \sum_{i\in I}\kappa_i=\max\{|I|,\sup_{i\in I}\kappa_i\}. In particular, \kappa+\lambda=\max\{\kappa,\lambda\} if at least one of \kappa,\lambda is infinite.

Proof. First we argue the case for two cardinals: Let {\mathfrak m}=\max\{\kappa,\lambda\}. Then {\mathfrak m}\le\kappa+\lambda\le|\kappa\times\lambda|\le|{\mathfrak m}\times{\mathfrak m}|={\mathfrak m}, where we use the fact that there is an injection A\sqcup B\to A\times B whenever at least one of A,B is infinite, and the fact that \alpha and \alpha\times\alpha have the same size, for any infinite ordinal \alpha, as shown  on lecture 3, lemma in section 6. 

Remark. {\mathfrak m}+{\mathfrak n}\le{\mathfrak m}\times{\mathfrak n} holds in the absence of choice if both {\mathfrak m},{\mathfrak n} are at least two. It fails in the generality above, since if {\mathfrak m} is infinite and Dedekind-finite, {\mathfrak m}+1>{\mathfrak m}\times1.

The result is now easy: Clearly, \sum_{i\in I}\kappa_i\ge |I| and \sum_{i\in I}\kappa_i\ge\kappa_j for any j\in I. Also, if {\mathfrak m}=\sup_{i\in I}\kappa_i, then \sum_{i\in I}\kappa_i\le\sum_i{\mathfrak m}=|{\mathfrak m}\times I|. The result follows from the above and the Schröder-Bernstein theorem. {\sf QED}

Unlike addition, multiplication is significantly more difficult.

Definition. Let I be a set and let (\kappa_i:i\in I) be an I-indexed family of cardinals. Then \prod_{i\in I}\kappa_i=|\prod_{i\in I}\kappa_i| where the latter \prod denotes the product of the sets \kappa_i, the set of all (choice) functions f:I\to\bigcup_i\kappa_i such that for all i\in I, f(i)\in\kappa_i.

Clearly, a product is zero is one of its factors is zero, and a finite product has the size of the Cartesian product of the sets involved.

One easily checks that if A_i\sim B_i for all i\in I, then \prod_iA_i\sim\prod_iB_i.

Remark. Just as with addition, without choice there is no reasonable way of defining \prod_{i\in I}{\mathfrak m}_i, even if we make the product dependent on the specific index set I. For example, it is consistent to have a countable collection of sets of size two whose product is not in bijection with the product of countably many copies of \{0,1\}.

Definition. \kappa^\lambda=|{}^\lambda\kappa|, where {}^A B denotes the set of functions from A to B, so \prod_{i\in I}\kappa=\kappa^{|I|}. Also, \kappa\cdot\lambda=\kappa\times\lambda=\kappa\lambda denotes the product of \kappa and \lambda.

During the proof of Fact 1 we showed:

Fact 2. \kappa\lambda=\max\{\kappa,\lambda\} if at least one of \kappa,\lambda is infinite, and neither is zero. \Box

From choice it follows that a product of nonempty sets is nonempty. In fact, it tends to be a rather large object. Before we present quantitative evidence of this statement, one more definition is in order. This notion is central to set theoretic combinatorics.

Definition. If (X,<) is a linearly ordered set, a subset Y\subseteq X is cofinal in X iff \forall x\in X\,\exists y\in Y\,(x\le y).

Obviously, this notion coincides with the notion of an unbounded subset if X has no largest element. If X has a largest element, a subset of X is cofinal iff it contains this largest element.

Definition. A map into a linear order (X,<) is cofinal iff its range is cofinal. The cofinality {\rm cf}(X) of (X,<) is the smallest ordinal \beta such that there is a cofinal map f:\beta\to(X,<).

Lemma 3.

  1. {\rm cf}(0)=0, {\rm cf}(\alpha+1)=1, and {\rm cf}(\alpha) is an infinite cardinal for any limit ordinal \alpha.
  2. {\rm cf}({\rm cf}(\alpha))={\rm cf}(\alpha).
  3. Any cofinal subset of a linearly ordered set (X,<) contains a cofinal subset of size {\rm cf}(X).

Proof. In item 1, only that {\rm cf}(\alpha) is an infinite cardinal for \alpha limit needs to be argued. But if there is a cofinal map f:\beta\to\alpha and \beta\sim\gamma, then there is a cofinal map g:\gamma\to\alpha. It follows that {\rm cf}(\alpha) is a cardinal. It is obviously infinite, since \alpha is a limit ordinal and therefore no map from a finite set into \alpha will be cofinal. 

Item 2 is shown similarly: If \beta<{\rm cf}(\alpha) and there is a cofinal map f:\beta\to{\rm cf}(\alpha), then there is a cofinal map g:\beta\to\alpha, contradicting the definition of {\rm cf}(\alpha).

To prove item 3, let Y be a cofinal subset of the linearly ordered set X and let Z be a cofinal subset of Y of smallest cardinality. By transfinite recursion, define a strictly increasing sequence \vec a= (a_\alpha:\alpha<\theta) of elements of Z. The construction stops once the range of the sequence is cofinal in Z. Let \mu={\rm cf}(\theta), and select a cofinal subsequence of \vec a of length \mu. Then this sequence witnesses that {\rm cf}(X)\le\mu. By minimality of |Z| we must necessarily have |Z|=\mu.

Now we argue that {\rm cf}(X)=\mu. Letting Y' be the range of a cofinal map f:{\rm cf}(X)\to X, the argument above with Y' in place of Y shows that we can assume that f is is strictly increasing. The situation is now this: We have two maps g:\mu\to X and f:{\rm cf}(X)\to X, both strictly increasing and cofinal. Also, \mu={\rm cf}(\mu), from item 2. By transfinite induction define subsequences of f and g as follows:  Given (p_\alpha:\alpha<\beta), subsequence of f, and (q_\alpha:\alpha<\beta), subsequence of g, if neither is cofinal, define p_\beta to be the least element in the range of f that is an upper bound for all the p_\alpha and q_\alpha. Now define q_\beta as the least member of the range of g with q_\beta\ge p_\beta. The construction stops when the sequences so built are cofinal in X. 

If X has a largest element, then Z is a singleton, \mu=1, and also {\rm cf}(X)=1, so we may assume that this is not the case. It follows that the construction must stop at a limit ordinal \beta. But then (p_\alpha:\alpha<\beta) witnesses that \beta\ge{\rm cf}(X) (by definition of {\rm cf}(X)), so \beta={\rm cf}(X). Similarly, (q_\alpha:\alpha<\beta) is cofinal in Z and \beta\le\mu so \beta=\mu by definition of Z (or directly, from the sequence one easily sees that \beta\le{\rm cf}(\mu)=\mu and there is a cofinal map h:\beta\to\mu, so \beta=\mu).

We have shown that {\rm cf}(X)=\beta=\mu. This completes the proof. {\sf QED} 

Corollary 4. There is a strictly increasing cofinal map f:{\rm cf}(\alpha)\to\alpha. \Box

Definition. An infinite cardinal \kappa is regular iff {\rm cf}(\kappa)=\kappa. An infinite limit ordinal \alpha is singular iff {\rm cf}(\alpha)<\alpha.

The following is immediate from Fact 1:

Corollary 5. {\rm cf}(\kappa^+)=\kappa^+ for all \kappa. 

Proof. If f:\alpha\to\kappa^+ and \alpha<\kappa^+, then \alpha and all the f(\beta) for \beta\in\alpha have size at most \kappa. But then \sup({\rm ran}(f))=\bigcup_\beta f(\beta)\le\sum_\beta f(\beta), and |\sum_\beta f(\beta)|\le\kappa, by Fact 1. It follows that f is bounded in \kappa^+. {\sf QED}  

Remark. That \omega is regular does not require choice. Similarly, \aleph_\omega has cofinality \omega, and choice is not needed to establish this. On the other hand, Gitik showed that it is consistent with {\sf ZF} that every uncountable initial ordinal has cofinality \omega.

If {\rm cf}(\omega_1)=\omega, then \omega_1 is the countable union of countable sets, since if f:\omega\to\omega_1 is cofinal, then \omega_1=\bigcup_n f(n) and each f(n) is a countable ordinal. On the other hand, if X is a countable set of ordinals, then its order type is a countable ordinal, and it follows that any countable union of countable sets of ordinals has size at most \omega_1. This is a curious situation, in that it is consistent that {\rm cf}(\omega_1)={\rm cf}(\omega_2)=\dots=\omega, and therefore there are countable unions of countable unions of countable sets that are not countable unions of countable sets, etc.

Homework problem 7. ({\sf ZF}).

  1. Assume that {\mathbb R} is the countable union of countable sets. Show that {\rm cf}(\omega_1)=\omega
  2. Assume that every countable union of countable sets is also a countable union of finite sets. Show that \omega_1 is regular.

Question. In {\sf ZF}, if every countable union of countable sets is also a countable union of finite sets, does it follow that every countable union of countable sets is countable?

Lemma 6. A cardinal \kappa is regular if and only if it cannot be written as a union of fewer than \kappa many sets, each of size less than \kappa.

Proof. If the right hand side holds, no map f:\beta\to\kappa with \beta<\kappa can be cofinal, so \kappa is regular. Assume now that \kappa=\bigcup_{i\in I}X_i where |I|<\kappa and |X_i|<\kappa for each i\in I. Without loss, I=|I| is an infinite cardinal, and it is least for which such a decomposition of X is possible. Let \kappa_i=|X_i|, and define a function f: |I| \to \kappa by f(\alpha)=\sum_{\beta<\alpha}\kappa_\beta, where sums denote ordinal addition. That the range of f is indeed in \kappa follows from our assumption on the minimality of |I|. Notice that the ordinal \sup({\rm ran}(f))=\sum_{\alpha<|I|}\kappa_\alpha has size \kappa, as the decomposition X=\bigcup_{\alpha\in|I|}X_\alpha provides us with a straightforward bijection between \kappa and \sup({\rm ran}(f)). It follows that in fact \sup({\rm ran})(f)=\kappa, i.e., f is cofinal and therefore \kappa is singular. {\sf QED} 

We are ready to prove the first significant result.

Theorem 7. (König). Assume that \kappa_i<\lambda_i for all i\in I. Then \sum_i\kappa_i<\prod_i\lambda_i.

Notice that \sum_i\kappa_i=\sum_i\lambda_i is possible. For example, let I=\omega and let each \kappa_i be 1 and each \lambda_i be 2. Then both sums equal \omega.

Proof. First we show that the inequality holds, and then we argue that it is strict. For the first part, we simply need to exhibit an injection from \sqcup_{i\in I}\kappa_i=\bigcup_{i\in I}\kappa_i\times\{i\} into the collection of functions \prod_{i\in I}\lambda_i. Simply assign to each (\alpha,i) the function that is zero in each coordinate except the i-th one, where it takes the value \alpha+1. Note that since \alpha<\kappa_i<\lambda_i, then indeed \alpha+1<\lambda_i, and the function is well defined. Clearly, from the function we can recover (\alpha,i), so the assignment is injective.

Now consider an arbitrary map \varphi:\bigcup_i\kappa_i\times\{i\}\to\prod_i\lambda_i, and we need to exhibit a function not in its range. For this, notice that the assignment \alpha\mapsto\varphi(\alpha,i)(i) maps \kappa_i into \lambda_i, and therefore there is some ordinal g(i)\in\lambda_i not in its range. The function g so defined is not in the range of \varphi, since g(i)\neq \varphi(\alpha,i)(i) for any i\in I and any \alpha\in\kappa_i. {\sf QED}

Note that at the heart of the proof just given there is again a diagonal argument.


3 Responses to 580 -II. Cardinal arithmetic

  1. […] -Cardinal arithmetic (2) At the end of last lecture, we showed Theorem 7, König’s lemma, stating that if for all then We begin by looking at […]

  2. […] It is easy to solve negatively the question immediately following Homework problem 5 on lecture II.1. I asked whether if  is Dedekind-finite but  is Dedekind-infinite, then it followed that there is […]

  3. […] Given an infinite cardinal let be the largest cardinal that can be represented as a union of many sets of size Hence, is either or and under choice it coincides with (The case was briefly discussed before Homework problem 7 in lecture II.1.) […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: