28
I - Sets and Functions
8 - The different types of infinity
Since there are "no more" rational numbers than whole numbers one can go
further and ask whether there are not also "as many" whole numbers as real
numbers (rational or irrational), which would allow one to "enumerate" all
the points of a line. The answer is negative (Cantor, 1874).
Let us confine ourselves to considering the set X = [0, 1 J of numbers
x such that 0 ~ x ~ 1. As we shall see in Chap. II, such a number can
be written in decimal notation in the form x = 0.XIX2X3 ••. with "digits"
Xl, X2, ... between 0 and 9; this expansion is unique if, for all n, one insists
that the number O.XI ... Xn be strictly less than x, so that, for example, 1/4
is written as 0.2499999 ... and not 0.2500000 .... That said, consider a map
f of N into X; for all n E N, denote by an the nth digit of f(n) and, for all n,
let us choose a bn -=I an between 1 and 9. Consider the number b = 0.bl b2 •••
whose nth digit is bn for every n. It belongs to X but not, as we shall see, to
the image f(N) of N of f, whence the result: a map f of N into X is never
surjective, let alone bijective.
Indeed, suppose that b = f(n) for an n E N. Since the digits of b are all
-=I 0, the decimal expansion b = 0.bl b2 ... cannot terminate in an unending
sequence of zeros; thus O.bl ... bp < b for all p, strict inequality, from which
we see that this decimal expansion definitely satisfies the condition imposed
above. If one had b = f(n) for a particular n, the nth digit bn of b would
be, from the construction of b, different from the nth digit of f(n), Le. of bn ;
which is absurd 24 .
Since the set Q of rational numbers is countable, one sees that JR - Q, the
set of irrational numbers, is equipotent to JR (nO 7, point 6).
When there exists a bijection of JR, the set of real numbers (geometrically:
the set of points of aline), onto a set X, one says that X has the power of the
continuum. One of the most paradoxical of Cantor's results is that JR x JR has
the power of the continuum; in other words, there exist bijective maps of the
set of points of a line onto the set of points of a plane: there are "no more"
points in a plane than on a line. Here again there is a very simple proof2 5 ,
for f'xflmple by using the binary counting of the computer scientists; others
would say "of Leibniz", but he had invented a calculating machine and also
24 Cantor's method for for showing that IR is not equipotent to N is very different but
presupposes some knowledge. Suppose that we could write all the real numbers
between 0 and 1 as a sequence U 1 , U2, ••• , and let us construct a sequence of
compact intervals II J 12 J h J ... of lengths> 0 in [0,1] and such that
Un rt In for all n (if Un rt In-I, choose In = In-I; if Un E In-I, choose for In
an interval contained in In-l and not containing Un: this is possible since In-l
does not reduce to a single point). The results of Chap. III, nO 9 show that the
In have a point x in common; if one had x = Un for some n, then one would
have x rt In, which is absurd.
25 That of Cantor, much more scholarly, exploits the classical theory of continued
fractions.
I - Sets and Functions
8 - The different types of infinity
Since there are "no more" rational numbers than whole numbers one can go
further and ask whether there are not also "as many" whole numbers as real
numbers (rational or irrational), which would allow one to "enumerate" all
the points of a line. The answer is negative (Cantor, 1874).
Let us confine ourselves to considering the set X = [0, 1 J of numbers
x such that 0 ~ x ~ 1. As we shall see in Chap. II, such a number can
be written in decimal notation in the form x = 0.XIX2X3 ••. with "digits"
Xl, X2, ... between 0 and 9; this expansion is unique if, for all n, one insists
that the number O.XI ... Xn be strictly less than x, so that, for example, 1/4
is written as 0.2499999 ... and not 0.2500000 .... That said, consider a map
f of N into X; for all n E N, denote by an the nth digit of f(n) and, for all n,
let us choose a bn -=I an between 1 and 9. Consider the number b = 0.bl b2 •••
whose nth digit is bn for every n. It belongs to X but not, as we shall see, to
the image f(N) of N of f, whence the result: a map f of N into X is never
surjective, let alone bijective.
Indeed, suppose that b = f(n) for an n E N. Since the digits of b are all
-=I 0, the decimal expansion b = 0.bl b2 ... cannot terminate in an unending
sequence of zeros; thus O.bl ... bp < b for all p, strict inequality, from which
we see that this decimal expansion definitely satisfies the condition imposed
above. If one had b = f(n) for a particular n, the nth digit bn of b would
be, from the construction of b, different from the nth digit of f(n), Le. of bn ;
which is absurd 24 .
Since the set Q of rational numbers is countable, one sees that JR - Q, the
set of irrational numbers, is equipotent to JR (nO 7, point 6).
When there exists a bijection of JR, the set of real numbers (geometrically:
the set of points of aline), onto a set X, one says that X has the power of the
continuum. One of the most paradoxical of Cantor's results is that JR x JR has
the power of the continuum; in other words, there exist bijective maps of the
set of points of a line onto the set of points of a plane: there are "no more"
points in a plane than on a line. Here again there is a very simple proof2 5 ,
for f'xflmple by using the binary counting of the computer scientists; others
would say "of Leibniz", but he had invented a calculating machine and also
24 Cantor's method for for showing that IR is not equipotent to N is very different but
presupposes some knowledge. Suppose that we could write all the real numbers
between 0 and 1 as a sequence U 1 , U2, ••• , and let us construct a sequence of
compact intervals II J 12 J h J ... of lengths> 0 in [0,1] and such that
Un rt In for all n (if Un rt In-I, choose In = In-I; if Un E In-I, choose for In
an interval contained in In-l and not containing Un: this is possible since In-l
does not reduce to a single point). The results of Chap. III, nO 9 show that the
In have a point x in common; if one had x = Un for some n, then one would
have x rt In, which is absurd.
25 That of Cantor, much more scholarly, exploits the classical theory of continued
fractions.