7.17 Theorem. the Countable Union of Countable Sets Is Countable
CHAPTER 6
The Cardinals
Project # 32.
Using ZFC prove:
7.17 Theorem. The countable union of countable sets is countable.
Proof: If we can list the elements of the set, that is equivalent to the set being
countable.
Suppose that we had Xi countable sets, and X = , i N (since we have a countable union).
X0 X1 X2 …
------
a0,0 a1,0 a2,0 …
a0,1 a1,1 a2,1 …
a0,2 a1,2 a2,2 …
a0,3 a1,3 a2,3 …
: : :
: : :
ai,j is the jth element in the ith countable set Xi.
Let 0 map to a0,0,
1 map to a0,1
2 map to a1,0
3 map to a0,2
4 map to a1,1
:
:
(Dovetailing) We can use the same function Simon defined for theorem 7.3.
**Where is the axiom of choice used in this proof?
For each set Xi, we must ‘choose’ a representative from the collection of orderings of the elements. This requires the notion of a ‘choice’ function for each Xi.
Theorem 7.18. If A is countable, then A x A is countable.
Proof: Let a A, {a} is a set by Theorem 1.3. {a}x A is a set by Theorem 1.8.
||{a}x A|| = ||A|| ||||
So {a}x A is countable. A x A = is a countable union of countable sets, so by Theorem 7.17, A x A is countable.
QED.
7.19. Theorem. There is no largest cardinal number.
Proof: Suppose otherwise, that we have some largest cardinal .
Zermelo’s Well-Ordering Theorem tells us that every set has a well-ordering. Thus P() has a well-ordering. Next by theorem 6.13, every well-ordered set has a unique order-type (ie. it has the same order type as some ordinal ). Thus:
||P()|| = || || (**)
Choose the smallest ordinal satisfying (**). We claim two things: first that is a cardinal, and second that |||| < || || (ie. is a bigger cardinal than ).
To show is indeed a cardinal, consider any 0 (ie. . Then either || 0 || or || 0 ||. If || 0 ||, then we have that
||P()|| = || || = || . But we chose to be the least cardinal such that (**) holds, so this cannot happen. Thus we must have that
|| 0 || = ||P()||. So is an cardinal.
To prove the second claim, we merely note that by theorem 7.6, we know that:
|||| < ||P()|| = || ||
Thus, there is no largest cardinal.
QED.
Project #33. Using only ZF prove:
Theorem 7.20. If a function which maps a set X one-to-one onto an ordinal , then there is a well-ordering of X of order-type .
Proof: Let the ordering on X be: for any a, b X, a <x b iff f(a) f(b), for f(a),
f(b) .
Since is an ordinal, there is a well ordering on , ie. is a linear ordering and every subset of has a least element. Let A X, A . f(A) , and since is an ordinal, f(A) has a least element. Suppose the least element of f(A) is b0. f -1(b0) = x0 is the least element of A X.
Irreflexivity, transitivity, and trichotomy are satisfied for <x since they are satisfied for . So X has a well ordering.
It is of order type , since f is one-to-one, f -1 is a set, it is also one-to-one and if , f -1() < f -1() by definition of f.
QED.
7.21. Theorem. There is no largest cardinal number (Using only ZF Axioms)
Note: We presume that the purpose of this exercise is not to appreciate the tediousness of a world without the Axiom of Choice, and is instead to demonstrate that this conclusion can be reached regardless of whether or not one invokes the Axiom. It is certainly easier to use Choice (ie. Zermelo’s Theorem), but it is important to show this property of the cardinal numbers independently.
Idea: ------) ======… )
| ------A------| <-- The set of all ordinals with the same cardinality as
Take the Least Upper Bound of A (ie. A, see theorem 6.8), and this is a new cardinal, which is greater than (in fact, it is the next smallest).
Proof: Suppose otherwise, that we have some largest cardinal . Let A be the set
of all ordinals , such that || || = |||| (ie. has the same order type as each ). We can say this is a set because of the replacement axiom. We write down a function from , a set, to A: Since A is a set of well orderings of , we can define a subset of P(x), such that this function maps each well-ordering of to its order type. Thus the range, A, must be a set by the Replacement Axiom.
Let = A. We know is an ordinal by theorem 6.8. We claim that is a cardinal, and that |||| < || ||.
**To show is a cardinal, we suppose it wasn’t. Then there is some with || || = || ||.
-By definition of , we know that for some (ie. we took the union of A)
- || || = || || < || || < || ||. Thus || || = || || by the Schroeder-Bernstein theorem.
-But since || || = || || there is a one-to-one function from onto We also know || || = |||| so there is a one-to-one function from onto (Theorem 7.20, and choice of Thus there is a one-to-one function from onto
-By theorem 7.20, we know that is an order type of a well ordering of . So we must have that A.
-Since there is a well ordering of with order type , there must be one with order type +o 1. We simply define a well ordering on as follows:
< <=> = 0, or ^ =/= 0
(idea: Put 0 at the ‘top’ of your cardinal).
-This is a well ordering of of order type +o 1, and so
A =
Thus there could be no such andis a cardinal.
**The fact that |||| < || || comes from the fact that there is a well ordering of of order type +o 1. As before, we define a well ordering on as follows:
< <=> = 0, or ^ =/= 0
This is a well ordering of of order type +o 1, and thus
A = |||| < || ||.
Thus, we have shown that there is no greatest cardinal, independent of the axiom of choice.
QED.