§l. Set Theory
29
was one of the precursors of formal logic, which, among other titles, makes
bim an honorary computer scientist.
In binary counting, every real number between 0 and 1 can be written
with the aid of a sequence of digits 0 and 1, and in a unique way, if one insists
that the sequence does not consist only of 0 from a certain point on. If one
considers only those digits equal to 1, this amounts to writing x in the form
_ (1) PI
( 1 ) PI +P2
( 1 ) PI +P2 +P3
x- -
+ -
+ -
+ ...
2 2 2
with well-determined integers PI, P2, P3, ... > 0: the digits 1 in the "default"
binary description of x are those of rank PI, PI + P2, etc., the others being zeros; if for example one writes 1/2 in the form 0.01111 ... (and not
0.1000 ... ), one has PI = 2, Pn = 1 for all n > 1. Conversely, such a sequence of integers defines a number between 0 and 1. In other words, there
exists a bijection between the interval I = [0, 1 J and the set S of sequences 26
(PbP2,"') of integers> O. That said, let (x, y) be a pair of elements of I and
let (PI, P2, ... ), (ql, q2, ... ) be the elements of S corresponding to x and y;
we associate with the pair (x, y) the number z E I that corresponds to the
sequence (PI, qb P2, q2, ... ) obtained by interlacing the sequences corresponding to x and y; thus one constructs, as one sees immediately, a bijective map
of I x I into I (or, from the other point of view, of S x S into S), whence
Cantor's result.
One would be wrong to believe that he sawall this immediately; to start
with, it took him years to surmount the psychological obstacle which the
implausibility of the results 27 and the predictable reactions of the majority
of his contemporaries presented. The very simple proofs we have presented
came later.
Cantor, and others after him, believed for a long time that every infinite
subset of R falls into one of the three categories which we have just defined,
the finite, the countable and the power of the continuum; we know now that
this "continuum hypothesis" is neither true nor false: one can neither deduce
26 If one denotes the set of integers > 0 by X then S is precisely the set of maps
from X into Y = N - {o}. A map of X into Y is a subset of X x Y, i.e. an
element of P(X x Y); the set S of these maps thus satisfies
S C P(P(X x Y)) C P(P(P(P(X u Y)))).
27 Peano did much better than Cantor a little later: if one represents I as an interval
of a line and I x I as a square in the plane, Peano constructed a map of I into
I x I which is surjective and continuous. This amounts to the fact that a point
moving in the plane in a continuous manner can, in a finite time, pass through
ALL the points of a square. The Dutchman J. L. E. Brouwer later completed
the statement: a map f of I into I x I can be continuous and surjective, but
not continuous and bijective; the point has to pass through all the points of the
square an infinite number of times.
29
was one of the precursors of formal logic, which, among other titles, makes
bim an honorary computer scientist.
In binary counting, every real number between 0 and 1 can be written
with the aid of a sequence of digits 0 and 1, and in a unique way, if one insists
that the sequence does not consist only of 0 from a certain point on. If one
considers only those digits equal to 1, this amounts to writing x in the form
_ (1) PI
( 1 ) PI +P2
( 1 ) PI +P2 +P3
x- -
+ -
+ -
+ ...
2 2 2
with well-determined integers PI, P2, P3, ... > 0: the digits 1 in the "default"
binary description of x are those of rank PI, PI + P2, etc., the others being zeros; if for example one writes 1/2 in the form 0.01111 ... (and not
0.1000 ... ), one has PI = 2, Pn = 1 for all n > 1. Conversely, such a sequence of integers defines a number between 0 and 1. In other words, there
exists a bijection between the interval I = [0, 1 J and the set S of sequences 26
(PbP2,"') of integers> O. That said, let (x, y) be a pair of elements of I and
let (PI, P2, ... ), (ql, q2, ... ) be the elements of S corresponding to x and y;
we associate with the pair (x, y) the number z E I that corresponds to the
sequence (PI, qb P2, q2, ... ) obtained by interlacing the sequences corresponding to x and y; thus one constructs, as one sees immediately, a bijective map
of I x I into I (or, from the other point of view, of S x S into S), whence
Cantor's result.
One would be wrong to believe that he sawall this immediately; to start
with, it took him years to surmount the psychological obstacle which the
implausibility of the results 27 and the predictable reactions of the majority
of his contemporaries presented. The very simple proofs we have presented
came later.
Cantor, and others after him, believed for a long time that every infinite
subset of R falls into one of the three categories which we have just defined,
the finite, the countable and the power of the continuum; we know now that
this "continuum hypothesis" is neither true nor false: one can neither deduce
26 If one denotes the set of integers > 0 by X then S is precisely the set of maps
from X into Y = N - {o}. A map of X into Y is a subset of X x Y, i.e. an
element of P(X x Y); the set S of these maps thus satisfies
S C P(P(X x Y)) C P(P(P(P(X u Y)))).
27 Peano did much better than Cantor a little later: if one represents I as an interval
of a line and I x I as a square in the plane, Peano constructed a map of I into
I x I which is surjective and continuous. This amounts to the fact that a point
moving in the plane in a continuous manner can, in a finite time, pass through
ALL the points of a square. The Dutchman J. L. E. Brouwer later completed
the statement: a map f of I into I x I can be continuous and surjective, but
not continuous and bijective; the point has to pass through all the points of the
square an infinite number of times.