26
I - Sets and Functions
the difficult concept of the "power" of a set, which generalises that of "number
of elements"; see nO 9); since the composition of two bijections is a bijection
it is clear that if X is equipotent to Y and Y is equipotent to Z then X is
equipotent to Z.
The concept of equipotence is familiar as applied to finite sets: it is the
foundation of the naive definition of the whole numbers. Its extension to
infinite sets was Cantor's first great idea. Seen from 1997 it does not have
a very revolutionary air, but when Cantor proved that the set N of whole
numbers is equipotent to the set Q of rational numbers he created a sensation:
there were no more rational numbers p/q than integers, and yet there is an
infinity of rationals between 0 and 1, then between 1 and 2, etc.?
Further, Cantor's proof was accessible to anybody. Every rational number
can be written in a unique way in the form p/q with p and q having no
common divisor (Le. are relatively prime) and q > O. One can then group the
rational numbers according to the value of Ipl + q; since q is positive there are
only finitely many numbers for which Ipi + q has a given value s. You write
on a line of infinite length the numbers for which s = 0 (there are none), then
those for which s = 1, etc.; you obtain
0/1, 1/1, -1/1, 1/2, -1/2, 2/1, - 2/1, 1/3, -1/3, 3/1, - 3/1,
4/1, - 4/1, 3/2, - 3/2, 2/3, - 2/3, 1/4, - 1/4, 5/1, etc.
In this way one can assign to every irreducible fraction x = p/q an integer
n = f(x), its rank in the above order; hence we have a bijection from Q onto
N after agreeing to assign rank zero to 0/1 = 0, qed.
A similar argument will show the existence of bijections of N onto N x N,
onto N x N x N [group the elements (p, q, r) of N x N x N according to the
value of p + q + rJ, etc., or onto Q x Q, Q x Q x Q, etc.
If there is a bijection of N onto a set X one says that X is countable. Our
convention, in contrast to that of some other authors, is that finite sets are
not reckoned as countable, but in fact we shall often say "countable" when
actually meaning "finite or countable" .
There are several useful theorems on countable sets; we shall confine ourselves to giving semi-naive proofs of them.
(1) Every subset Y of a countable set X is finite or countable. To see this
naively one writes the elements of X as a sequence Xl,X2,"" suppresses
those x rf- Y, and reenumerates the remaining elements, i.e. those of Y.
(2) The image Y = f(X) of a countable set X under a map f is finite
or countable. We enumerate the elements of X as we have just done and put
Y~ = f(x n ); one thus obtains all the elements of Y, in general several or even
infinitely many times. To write the elements of Yonce and once only one
proceeds as follows: put Yl = Y~, then let Y2 be the first term of the sequence
of Y~ which is -=J Yl, then Y3 the first term of the sequence Y~ different from
Yl and Y2, and so on indefinitely.
I - Sets and Functions
the difficult concept of the "power" of a set, which generalises that of "number
of elements"; see nO 9); since the composition of two bijections is a bijection
it is clear that if X is equipotent to Y and Y is equipotent to Z then X is
equipotent to Z.
The concept of equipotence is familiar as applied to finite sets: it is the
foundation of the naive definition of the whole numbers. Its extension to
infinite sets was Cantor's first great idea. Seen from 1997 it does not have
a very revolutionary air, but when Cantor proved that the set N of whole
numbers is equipotent to the set Q of rational numbers he created a sensation:
there were no more rational numbers p/q than integers, and yet there is an
infinity of rationals between 0 and 1, then between 1 and 2, etc.?
Further, Cantor's proof was accessible to anybody. Every rational number
can be written in a unique way in the form p/q with p and q having no
common divisor (Le. are relatively prime) and q > O. One can then group the
rational numbers according to the value of Ipl + q; since q is positive there are
only finitely many numbers for which Ipi + q has a given value s. You write
on a line of infinite length the numbers for which s = 0 (there are none), then
those for which s = 1, etc.; you obtain
0/1, 1/1, -1/1, 1/2, -1/2, 2/1, - 2/1, 1/3, -1/3, 3/1, - 3/1,
4/1, - 4/1, 3/2, - 3/2, 2/3, - 2/3, 1/4, - 1/4, 5/1, etc.
In this way one can assign to every irreducible fraction x = p/q an integer
n = f(x), its rank in the above order; hence we have a bijection from Q onto
N after agreeing to assign rank zero to 0/1 = 0, qed.
A similar argument will show the existence of bijections of N onto N x N,
onto N x N x N [group the elements (p, q, r) of N x N x N according to the
value of p + q + rJ, etc., or onto Q x Q, Q x Q x Q, etc.
If there is a bijection of N onto a set X one says that X is countable. Our
convention, in contrast to that of some other authors, is that finite sets are
not reckoned as countable, but in fact we shall often say "countable" when
actually meaning "finite or countable" .
There are several useful theorems on countable sets; we shall confine ourselves to giving semi-naive proofs of them.
(1) Every subset Y of a countable set X is finite or countable. To see this
naively one writes the elements of X as a sequence Xl,X2,"" suppresses
those x rf- Y, and reenumerates the remaining elements, i.e. those of Y.
(2) The image Y = f(X) of a countable set X under a map f is finite
or countable. We enumerate the elements of X as we have just done and put
Y~ = f(x n ); one thus obtains all the elements of Y, in general several or even
infinitely many times. To write the elements of Yonce and once only one
proceeds as follows: put Yl = Y~, then let Y2 be the first term of the sequence
of Y~ which is -=J Yl, then Y3 the first term of the sequence Y~ different from
Yl and Y2, and so on indefinitely.