§l. Set Theory
31
and suppose that there exists an a E X such that A = M(a) [as would be the
case if the map x f-----+ M(x) of X into P(X) were surjective]. If a E A, one has
a ¢. M (a) = A by the definition of A, absurd; if a ¢. A, the relation a ¢. M (a)
is false by the definition of A, whence a E M(a) = A, a new contradiction.
Thus there cannot be a map of X into P(X) which is surjective, even less
bijective, qed. This proof is due to Cantor, even as formulated here.
The simplest illustration of the preceding result, though not very useful
to us, is when X = N: the set P(N) is equipotent to lR or, what comes to the
same 30 , to the interval X : 0 ~ x ~ 1 in lR. One proves this by associating to
each subset A of N the number x E X whose nth binary digit is equal to 1
if n E A and to 0 if not; one has to take note of the existence of numbers x
which have two different binary expansions (0.1000 ... = 0.0111 ... ), but they
form a countable set since they are of the form p/2 n with p and n integers.
The reader may provide the details as an exercise.
However it may be,
etc., are sets whose "powers" become larger and larger, even though negligible
in comparison with the analogous sets constructed starting from lR. It is not
advisable to plunge into contemplation of these vertiginous elaborations. One
may also absolve oneself from reading the following nO which, for us, is only
a gymnastic exercise in manipulating the symbols E and c; but if you read
and understand all the proofs, you will be liberated for the rest of your days
from any inferiority complex as regards the mysteries of the "transfinite" ...
However one should not believe that these weird creatures have no practical use in mathematics; on the contrary, they are used to prove indispensable
theorems in functional analysis (the Hahn-Banach Theorem to mention only
one), in general topology (every cartesian product of compact spaces is compact), in algebra (existence of bases in any vector space), etc.
9 - Ordinals and cardinals
The von Neumann sets used above in defining the whole numbers have very
curious properties. For a start, if X is such a set, then every element of X
is also a subset of X; for example, the element {0, {0}, {0, {0}}} of the set 4
has as its elements 0, {0} and {0, {0}}, which themselves belong to 4. One
notes also that if a and b are two elements of X, then either a E b, or a = b,
n numbers equal to 0 or 1, and since there are two possible choices for each of n
terms of such a sequence, one obtains 2 x 2 x ... x 2 possibilities (application:
coin tossing). More generally, if X has n elements and if Y has p, then the set
of maps from X into Y has n P elements (same argument).
30 Every school-Ieaver can tell you that x 1----+ x/(1 + Ixi) is a bijection of JR onto
the interval I : -1 < x < 1. Since the interval J : -1 ~ x ~ 1 differs from I by
only a countable (even finite) set, it is equipotent to I, thus to JR. It remains to
find a bijection of J onto the interval 0 ~ x ~ 1.
31
and suppose that there exists an a E X such that A = M(a) [as would be the
case if the map x f-----+ M(x) of X into P(X) were surjective]. If a E A, one has
a ¢. M (a) = A by the definition of A, absurd; if a ¢. A, the relation a ¢. M (a)
is false by the definition of A, whence a E M(a) = A, a new contradiction.
Thus there cannot be a map of X into P(X) which is surjective, even less
bijective, qed. This proof is due to Cantor, even as formulated here.
The simplest illustration of the preceding result, though not very useful
to us, is when X = N: the set P(N) is equipotent to lR or, what comes to the
same 30 , to the interval X : 0 ~ x ~ 1 in lR. One proves this by associating to
each subset A of N the number x E X whose nth binary digit is equal to 1
if n E A and to 0 if not; one has to take note of the existence of numbers x
which have two different binary expansions (0.1000 ... = 0.0111 ... ), but they
form a countable set since they are of the form p/2 n with p and n integers.
The reader may provide the details as an exercise.
However it may be,
etc., are sets whose "powers" become larger and larger, even though negligible
in comparison with the analogous sets constructed starting from lR. It is not
advisable to plunge into contemplation of these vertiginous elaborations. One
may also absolve oneself from reading the following nO which, for us, is only
a gymnastic exercise in manipulating the symbols E and c; but if you read
and understand all the proofs, you will be liberated for the rest of your days
from any inferiority complex as regards the mysteries of the "transfinite" ...
However one should not believe that these weird creatures have no practical use in mathematics; on the contrary, they are used to prove indispensable
theorems in functional analysis (the Hahn-Banach Theorem to mention only
one), in general topology (every cartesian product of compact spaces is compact), in algebra (existence of bases in any vector space), etc.
9 - Ordinals and cardinals
The von Neumann sets used above in defining the whole numbers have very
curious properties. For a start, if X is such a set, then every element of X
is also a subset of X; for example, the element {0, {0}, {0, {0}}} of the set 4
has as its elements 0, {0} and {0, {0}}, which themselves belong to 4. One
notes also that if a and b are two elements of X, then either a E b, or a = b,
n numbers equal to 0 or 1, and since there are two possible choices for each of n
terms of such a sequence, one obtains 2 x 2 x ... x 2 possibilities (application:
coin tossing). More generally, if X has n elements and if Y has p, then the set
of maps from X into Y has n P elements (same argument).
30 Every school-Ieaver can tell you that x 1----+ x/(1 + Ixi) is a bijection of JR onto
the interval I : -1 < x < 1. Since the interval J : -1 ~ x ~ 1 differs from I by
only a countable (even finite) set, it is equipotent to I, thus to JR. It remains to
find a bijection of J onto the interval 0 ~ x ~ 1.