30
I - Sets and Functions
it from the axioms of set theory invented by the logicians nor, if one adopts
it, deduce a contradiction. You are very unlikely to need this very difficult
result; the overwhelming majority of mathematicians die before using it.
In proving these results by methods which, elementary as they are, were
totally unknown before him, Cantor showed that there are different sorts
of infinity, which twenty-five centuries of philosophers and theologians had
apparently never discovered. One can even always compare them. A famous
theorem (Schroder, 1896 and Bernstein, 1898 - it already appears in Cantor,
but his proof leaves much to be desired) says that if X and Yare two sets,
then there exists an injection of X into Y (Le. X is equipotent to a subset
of Y) or an injection of Y into X and that, if both these cases happen, then
X and Yare equipotent. A convenient way of expressing this result is to
attach to each set X a symbol Card(X), the cardinal of X, agreeing that the
relation Card(X) = Card(Y) means that X and Yare equipotent and that
the relation Card(X) < Card(Y) means that X is equipotent to a subset of
Y, but not to Y itself; the symbol Card(X) thus plays the role of the "number
of elements" of X. The theorem of Schroder-Bernstein can then be expressed
as saying that if28 Nl and N2 are two cardinals, then one and only one of the
three following cases occurs:
Nl < N2, Nl = N2, N2 < N1.
It is easy to construct infinite sets whose cardinals are increasingly large.
If X is a set, the subsets of X are, as we saw above, the elements of a new
set P(X). One can always construct an injection X - - t P(X), for example
x I---> {x}, but X and P(X) are never equipotent, an "obvious" result if X
is finite 29 . To see this, consider a map X - - t P(X); this associates to each
x E X a set M (x) eX. Let A c X be the set of x E X such that x ¢. M (x)
28 The use of Hebrew letters to baptise the cardinals goes back to Cantor and has
made many believe that he was a Jew; and with such a name ... His father,
a prosperous merchant and cosmopolitan, was protestant and his mother, nee
Marie B6hm, catholic and of a family of musicians. Their son was protestant,
but his family link to catholicism "may have made it easier for him to seek,
later on, support for his philosophical ideas among Catholic thinkers", his entry
in the DSB tells us. In fact, Cantor's father was indeed born to Jewish parents
but converted before the birth (in Saint Petersburg) of the mathematician. The
"Catholic thinkers" of the DSB were principally Jesuits, Fraenkel tells us in his
biography of Cantor. Their interest in his ideas was not the greatest service they
could render him ... The Dictionary of Scientific Biography (DSB), Princeton
UP, whose publication was directed by Charles Coulton Gillispie, an eminent
specialist in the history of science in France of the XVIIl th century and of the
Revolution, comprises about twenty large format volumes in which one can find
the essentials, even if the quality and the importance of articles, written by very
many authors, varies greatly.
29 If X has n elements, P(X) has 2n. A subset Y of X is essentially the same
as associating to each x E X the number 1 if x E Y, the number 0 if x f/; Y.
There are therefore as many subsets of X as ways of constructing a sequence of
I - Sets and Functions
it from the axioms of set theory invented by the logicians nor, if one adopts
it, deduce a contradiction. You are very unlikely to need this very difficult
result; the overwhelming majority of mathematicians die before using it.
In proving these results by methods which, elementary as they are, were
totally unknown before him, Cantor showed that there are different sorts
of infinity, which twenty-five centuries of philosophers and theologians had
apparently never discovered. One can even always compare them. A famous
theorem (Schroder, 1896 and Bernstein, 1898 - it already appears in Cantor,
but his proof leaves much to be desired) says that if X and Yare two sets,
then there exists an injection of X into Y (Le. X is equipotent to a subset
of Y) or an injection of Y into X and that, if both these cases happen, then
X and Yare equipotent. A convenient way of expressing this result is to
attach to each set X a symbol Card(X), the cardinal of X, agreeing that the
relation Card(X) = Card(Y) means that X and Yare equipotent and that
the relation Card(X) < Card(Y) means that X is equipotent to a subset of
Y, but not to Y itself; the symbol Card(X) thus plays the role of the "number
of elements" of X. The theorem of Schroder-Bernstein can then be expressed
as saying that if28 Nl and N2 are two cardinals, then one and only one of the
three following cases occurs:
Nl < N2, Nl = N2, N2 < N1.
It is easy to construct infinite sets whose cardinals are increasingly large.
If X is a set, the subsets of X are, as we saw above, the elements of a new
set P(X). One can always construct an injection X - - t P(X), for example
x I---> {x}, but X and P(X) are never equipotent, an "obvious" result if X
is finite 29 . To see this, consider a map X - - t P(X); this associates to each
x E X a set M (x) eX. Let A c X be the set of x E X such that x ¢. M (x)
28 The use of Hebrew letters to baptise the cardinals goes back to Cantor and has
made many believe that he was a Jew; and with such a name ... His father,
a prosperous merchant and cosmopolitan, was protestant and his mother, nee
Marie B6hm, catholic and of a family of musicians. Their son was protestant,
but his family link to catholicism "may have made it easier for him to seek,
later on, support for his philosophical ideas among Catholic thinkers", his entry
in the DSB tells us. In fact, Cantor's father was indeed born to Jewish parents
but converted before the birth (in Saint Petersburg) of the mathematician. The
"Catholic thinkers" of the DSB were principally Jesuits, Fraenkel tells us in his
biography of Cantor. Their interest in his ideas was not the greatest service they
could render him ... The Dictionary of Scientific Biography (DSB), Princeton
UP, whose publication was directed by Charles Coulton Gillispie, an eminent
specialist in the history of science in France of the XVIIl th century and of the
Revolution, comprises about twenty large format volumes in which one can find
the essentials, even if the quality and the importance of articles, written by very
many authors, varies greatly.
29 If X has n elements, P(X) has 2n. A subset Y of X is essentially the same
as associating to each x E X the number 1 if x E Y, the number 0 if x f/; Y.
There are therefore as many subsets of X as ways of constructing a sequence of