Set theory - Chapter 3: Cardinal Numbers
3.1
First, we notice that the ordering
is the same as for natural numbers. Let
be two natural numbers. We can suppose
. Then and the identity is 1-1 from
to , i.e. .
- Let be a finite set of cardinality
and 1-1 onto. Let . The identity of is 1-1 so we have . Let be the least natural number such that
. We shall show that
. If , then and we are done. Otherwise, we can write
and there exists a 1-1
from to that is not surjective. We can suppose
. Then is 1-1 and . A contradiction. Finally
is finite.
- Let and 1-1 (onto). Let where for each , is the least natural number such that
. Clearly, is well-defined and 1-1 so
. As in (i), we conclude that
is finite.
- Let be finite and 1-1 onto. Let . By unicity of the binary decomposition of a natural (easy to show
by induction) and because is one-to-one, see that
is also one-to-one. Hence
is finite.
- Let be finite and 1-1 onto and consider a mapping
. Then is 1-1 so is finite.
3.2
- Let be an enumeration of
(i.e. is 1-1 onto from to ) and . If is finite, then we are done. Define by induction for each
where is the least natural such that
and . Such an always exists for otherwise
would be finite by 3.1 (i). Then
is 1-1 from to and is 1-1 from to . By Cantor-Berstein,
is countable.
- Let with 1-1 onto. We suppose
for otherwise . Then is 1-1 from to . Define where is the least element such that
. By Cantor-Bernstein,
.
- Let 1-1 and . Define where is the least such that . Then is 1-1. By (i), is at most countable. So
too.
3.3
Let and p be the greatest natural such that
divides . Then is odd and can be written
for some natural . Thus is onto. If then . Hence since is odd. Then . Therefore is also onto. Finally is countable.
3.4
- Let where is the th prime number. Then
is 1-1 onto.
- Let a countable set. Let
where is the characteristic function of X. Then
is 1-1 onto.
3.5
For , . . Let such that .Then the order type of given by the canonical ordering is:
- First, the initial segment
given by
- The elements for
- The elements for
- and finally .
Consequently,
If is a limit ordinal such that
for all then since and are continuous then .
3.6
...
3.7
Let an onto mapping. Then is 1-1 and .
3.8
Let and . The onto mapping shows that is a projection of . But
Hence by 3.7, . Now is 1-1 so .
3.9
Let be a projection of and onto. Let . Suppose that then for all there is such that . Hence and . By symmetry, and so is 1-1. Thus .
3.10
Let such that for all , is the order-type of if this one is a well-ordering of
and any otherwise. In the former case,
for an ordinal such that . Hence and is well-defined.
Each is an ordinal and its well-ordering
satisfies . If and , then . Let be a one-to-one mapping from
onto and define the relation ≼ on
by iff . Then by construction we have
. Finally is onto.
Since we conclude that is a projection of .
3.11
By Cantor's theorem, . Using 3.10 and 3.9 we get
. Finally, .
3.12
Let an uncountable limit cardinal. Then
is limit. Let a cofinal sequence in . If , there is such that . Let such that . Then . So we have . By Lemma 3.7(ii) the sequence
shows that . Finally .
3.13
Suppose that with and let be the order-type of . We may assume that the sets
are disjoint. Then and . Define where is the th element of if and any element of otherwise. Then is onto and we can build a 1-1 map from
to (without AC since is well-ordered). Consequently
. A contradiction.
3.14
Let be D-infinite and a 1-1 onto map. Let and define for all . while for every . Hence is distinct of all . We show by induction on
that for all , . This is true for by the previous remark. Suppose it is true for some
. Then for all , or otherwise (since is 1-1) contradicts either the induction hypothese or the inital remark
on . Hence is 1-1 and contains the countable subset
.
Conversely, if is a countable subset of
. Then shows that S is D-infinite.
3.15
We use the equivalent definition of D-finiteness obtained in 3.14. For each
proof we suppose that final set is D-infinite and shows that one of the initial
set is not D-finite.
- Let a countable set. Then by 3.2 (ii),
and are at most countable. If one of them is finite, then so is
by 3.1 (i). Thus one of them is a countable subset of
or .
- Let a countable subset of
. Let and for where is the least index such that
(if such an index exists). The
sequence is defined similarly. At least one of these sequences is
completly defined, otherwise let
the least indices such that
and are not defined, then
is a subset of the finite set
. Suppose for instance that
is well defined, then it is a countable subset of
.
- Let a set and a countable set of 1-1 finite sequence of elements of
. Let and for all where is the least index such that
is not included in and the least index such that
. This sequence is well defined, otherwise if
is the least index such that
can not be defined, then
and is included in the finite set (by 3.4 i)
. Finally, is a countable subset of
.
- Let a dijoint family of D-finite sets and suppose that their union is
D-infinite. Let a countable subset of
. For each let the least natural such that
. Such an always exists for otherwise
while this union is D-finite by (i). Then, define
the unique index such that
. Finally, we get a countable set
.
3.16
Let an infinite set and for all
. Each is non-empty : is infinite so we can choose
elements of to build an element of . Moreover the are clearly pairwise distinct. Hence
is a countable subset of
. Finally, is D-infinite.