Page 29 - Advanced Linear Algebra

Preliminaries 13

not finite is infinite . The cardinal number or cardinality) of a finite set is
(
just the number of elements in the set.
2 The cardinal number of the set of natural numbers is L read “aleph
)
(
o
)
nought” , where is the first letter of the Hebrew alphabet. Hence,
L
(( ~ o ( ( ~ { ( ( ~ r L
) is called a countably infinite set and any finite
3 Any set with cardinality L
or countably infinite set is called a countable set. An infinite set that is not
countable is said to be uncountable .
Since it can be shown that (( € (( , the real numbers are uncountable.
o
s
If and are finite sets, then it is well known that
:
;
((
((
( (
;
((  ( ( and ( ( : ¬: ~;
:
;
The first part of the next theorem tells us that this is also true for infinite sets.
The reader will no doubt recall that the power set F²:³ of a set is the set of
:
all subsets of . For finite sets, the power set of is always bigger than the set
:
:
itself. In fact,
(
F
((:~ ¬ ( ²:³ ~
The second part of the next theorem says that the power set of any set is
:
)
(
bigger has larger cardinality than itself. On the other hand, the third part of
:
this theorem says that, for infinite sets , the set of all finite subsets of is the
:
:
same size as .
:
Theorem 0.12
¨
1 )(Schroder –Bernstein theorem ) For any sets and ,
:
;
:
;
((: ( ( and ( (  (( ¬ ((:~ ( (
;
;
2 )(Cantor's theorem ) If F²:³ denotes the power set of , then
:
F
((: ( ²:³ (
)
:
3 If F ²:³ denotes the set of all finite subsets of and if is an infinite set,
:
then
((:~ (F ²:³ (
)
)
Proof. We prove only parts 1 and 2 . Let ¢ : ¦ ; be an injective function
;
:
:
;
from into and let ¢ ; ¦ : be an injective function from into . We
want to use these functions to create a bijective function from to . For this
;
:
purpose, we make the following definitions. The descendants of an element
: are the elements obtained by repeated alternate applications of the
functions and , namely