Page 30 - Advanced Linear Algebra
P. 30
14 Advanced Linear Algebra
² ³Á ² ² ³³Á ² ² ² ³³³Á Ã
If is a descendant of , then is an ancestor of . Descendants and ancestors
!
!
of elements of are defined similarly.
;
Now, by tracing an element's ancestry to its beginning, we find that there are
three possibilities: the element may originate in , or in , or it may have no
;
:
point of origin. Accordingly, we can write as the union of three disjoint sets
:
I : ~¸ : originates in :¹
I ; ~¸ : originates in ;¹
I B ~¸ : has no originator ¹
; J J J .
Similarly, is the disjoint union of : , ; and B
Now, the restriction
O ¢ I I : ¦ J : :
, then originated in and
:
!
is a bijection. To see this, note that if ! J :
!
therefore must have the form ² ³ for some : . But and its ancestor have
the same point of origin and so ! J implies I : : . Thus, O I : is surjective
and hence bijective. We leave it to the reader to show that the functions
² O ³ ¢ I c ; ¦ J ; and O I B ¢ I B ¦ J B
J ;
are also bijections. Putting these three bijections together gives a bijection
between and . Hence, : ~ (( ( ( , as desired.
:
;
;
We now prove Cantor's theorem. The map F¢: ¦ ²:³ defined by ² ³ ~ ¸ ¹
is an injection from to ² : ³ F and so : (( ² : ( ³ F ( . To complete the proof we
:
must show that no injective map ¢ : ¦ F ²:³ can be surjective. To this end, let
? ~ ¸ : ¤ ² ³¹ F ²:³
We claim that is not in im ² ³ . For suppose that ? ~ ²%³ for some % : .
?
?
Then if %? , we have by the definition of that %¤? . On the other hand, if
%¤?, we have again by the definition of ? that %?. This contradiction
implies that ?¤ im ² ³ and so is not surjective.
Cardinal Arithmetic
Now let us define addition, multiplication and exponentiation of cardinal
numbers. If and are sets, the cartesian product : d ; is the set of all
;
:
ordered pairs
: d ; ~ ¸² Á !³ :Á ! ;¹
The set of all functions from to is denoted by : ; .
;
:
