Homework problem 5. (). Show that if then in fact .
Question. If is Dedekind-finite but is Dedekind-infinite, does it follow that there is an infinite Dedekind-finite set such that ?
From now on, until we cover determinacy, we assume the axiom of choice unless stated otherwise.
We use to denote cardinals (initial ordinals), usually infinite. As usual, is the cardinality of the disjoint union of two sets, one of size , and one of size , In fact, we can take where the latter denotes ordinal addition.
The advantage of doing this is that we can generalize it to infinite sums.
Definition. Let be an ordinal and a sequence of ordinals. Then is the ordinal resulting from concatenating the in the given order; formally, we consider the disjoint union and well-order it by setting iff or else and
It is straightforward to check that this is indeed a well-ordering.
Definition. Let be a set and let be an -indexed family of cardinals. Then where 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 ), and coincides with the cardinality of the disjoint union of the .
Remark. Without choice, there is no reasonable way of defining , even if we make the sum dependent on the specific index set . 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 and for each it is not necessarily the case that there is a function that to each assigns some such bijection, and it is indeed possible that there is no bijection between the resulting sets and
Homework problem 6. It is consistent with that is a countable union of countable sets. It is also consistent with that there are infinite Dedekind-finite subsets of . 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 be a nonempty set. If the are nonzero, and either or is infinite, then In particular, if at least one of is infinite.
Proof. First we argue the case for two cardinals: Let Then where we use the fact that there is an injection whenever at least one of is infinite, and the fact that and have the same size, for any infinite ordinal , as shown on lecture 3, lemma in section 6.
Remark. holds in the absence of choice if both are at least two. It fails in the generality above, since if is infinite and Dedekind-finite,
The result is now easy: Clearly, and for any . Also, if then . The result follows from the above and the Schröder-Bernstein theorem.
Unlike addition, multiplication is significantly more difficult.
Definition. Let be a set and let be an -indexed family of cardinals. Then where the latter denotes the product of the sets , the set of all (choice) functions such that for all ,
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 for all , then
Remark. Just as with addition, without choice there is no reasonable way of defining , even if we make the product dependent on the specific index set . 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
Definition. , where denotes the set of functions from to , so Also, denotes the product of and
During the proof of Fact 1 we showed:
Fact 2. if at least one of is infinite, and neither is zero.
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 is a linearly ordered set, a subset is cofinal in iff
Obviously, this notion coincides with the notion of an unbounded subset if has no largest element. If has a largest element, a subset of is cofinal iff it contains this largest element.
Definition. A map into a linear order is cofinal iff its range is cofinal. The cofinality of is the smallest ordinal such that there is a cofinal map .
- , , and is an infinite cardinal for any limit ordinal
- Any cofinal subset of a linearly ordered set contains a cofinal subset of size .
Proof. In item 1, only that is an infinite cardinal for limit needs to be argued. But if there is a cofinal map and then there is a cofinal map It follows that is a cardinal. It is obviously infinite, since is a limit ordinal and therefore no map from a finite set into will be cofinal.
Item 2 is shown similarly: If and there is a cofinal map , then there is a cofinal map contradicting the definition of .
To prove item 3, let be a cofinal subset of the linearly ordered set and let be a cofinal subset of of smallest cardinality. By transfinite recursion, define a strictly increasing sequence of elements of The construction stops once the range of the sequence is cofinal in Let , and select a cofinal subsequence of of length . Then this sequence witnesses that By minimality of we must necessarily have
Now we argue that Letting be the range of a cofinal map , the argument above with in place of shows that we can assume that is is strictly increasing. The situation is now this: We have two maps and both strictly increasing and cofinal. Also, from item 2. By transfinite induction define subsequences of and as follows: Given subsequence of and subsequence of if neither is cofinal, define to be the least element in the range of that is an upper bound for all the and . Now define as the least member of the range of with The construction stops when the sequences so built are cofinal in
If has a largest element, then is a singleton, , and also , so we may assume that this is not the case. It follows that the construction must stop at a limit ordinal . But then witnesses that (by definition of ), so Similarly, is cofinal in and so by definition of (or directly, from the sequence one easily sees that and there is a cofinal map so ).
We have shown that This completes the proof.
Corollary 4. There is a strictly increasing cofinal map
Definition. An infinite cardinal is regular iff . An infinite limit ordinal is singular iff
The following is immediate from Fact 1:
Corollary 5. for all
Proof. If and then and all the for have size at most But then and , by Fact 1. It follows that is bounded in
Remark. That is regular does not require choice. Similarly, has cofinality and choice is not needed to establish this. On the other hand, Gitik showed that it is consistent with that every uncountable initial ordinal has cofinality
If , then is the countable union of countable sets, since if is cofinal, then and each is a countable ordinal. On the other hand, if 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 This is a curious situation, in that it is consistent that , and therefore there are countable unions of countable unions of countable sets that are not countable unions of countable sets, etc.
Homework problem 7. ().
- Assume that is the countable union of countable sets. Show that .
- Assume that every countable union of countable sets is also a countable union of finite sets. Show that is regular.
Question. In , 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 is regular if and only if it cannot be written as a union of fewer than many sets, each of size less than .
Proof. If the right hand side holds, no map with can be cofinal, so is regular. Assume now that where and for each Without loss, is an infinite cardinal, and it is least for which such a decomposition of is possible. Let and define a function by where sums denote ordinal addition. That the range of is indeed in follows from our assumption on the minimality of Notice that the ordinal has size , as the decomposition provides us with a straightforward bijection between and It follows that in fact i.e., is cofinal and therefore is singular.
We are ready to prove the first significant result.
Theorem 7. (König). Assume that for all . Then
Notice that is possible. For example, let and let each be 1 and each be 2. Then both sums equal
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 into the collection of functions Simply assign to each the function that is zero in each coordinate except the -th one, where it takes the value Note that since , then indeed and the function is well defined. Clearly, from the function we can recover so the assignment is injective.
Now consider an arbitrary map and we need to exhibit a function not in its range. For this, notice that the assignment maps into and therefore there is some ordinal not in its range. The function so defined is not in the range of since for any and any
Note that at the heart of the proof just given there is again a diagonal argument.