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.

${\rm cf}(0)=0$ , ${\rm cf}(\alpha+1)=1$ , and ${\rm cf}(\alpha)$ is an infinite cardinal for any limit ordinal $\alpha.$
${\rm cf}({\rm cf}(\alpha))={\rm cf}(\alpha)$ .
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}$ ).

Assume that ${\mathbb R}$ is the countable union of countable sets. Show that ${\rm cf}(\omega_1)=\omega$ .
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.

This entry was posted on Thursday, February 5th, 2009 at 11:51 am 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.

6 Responses to 580 -II. Cardinal arithmetic

580 -Cardinal arithmetic (2) « Teaching page says:

February 7, 2009 at 12:20 pm

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

Reply
580 -Cardinal arithmetic (3) « Teaching page says:

February 9, 2009 at 5:03 pm

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

Reply
580 -Partition calculus (6) « Teaching page says:

April 24, 2009 at 12:13 pm

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

Reply
580 -Partition calculus (6) « A kind of library says:

September 7, 2012 at 12:28 pm

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

Reply
580 -Cardinal arithmetic (2) « A kind of library says:

January 1, 2013 at 2:50 pm

[…] the end of last lecture, we showed Theorem 7, König’s lemma, stating that if for all then We begin by looking at […]

Reply
580 -Cardinal arithmetic (3) « A kind of library says:

January 1, 2013 at 3:04 pm

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

Reply

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

A kind of library