8.3 CARDINAL NUMBER OF A SET 281N, they have just as many elements as N! In fact, it can be proved that N
is numerically equivalent to any infinite subset of itself. More surprises
are in store in the following theorems. When Cantor established the car-
dinality relationships between N and Q (the same cardinal number) and
between N and R (different cardinal numbers), so unexpected were these
types of conclusions and so innovative was his approach that his results
did not immediately win wide acceptance among mathematicians. Yet his
extraordinarily clever arguments are not really that difficult to follow. In
addition, the arguments in Theorems 3 and 4 illustrate the possibilities
for both aesthetic appeal and monumental power that are inherent in the
method of proof by contradiction.
THEOREM 2
N is numerically equivalent to Q, in symbols N z 0.
Proof We wish to define a one-to-one mapping of N onto Q. To define
a bijection between N and any set X, it is sufficient to create a scheme
in which we "line up" the elements of X in such a manner that every
element of X is accounted for. We then associate with each element of
X the positive integer corresponding to its place on the list, noting that
the place of any given element of X can be determined (if in no simpler
way) by "counting" through the list until we arrive at that element (thus
our use of the term countably injnite, see Definition 3).
The problem then for a given set X we believe to be equivalent to N
is to find such a scheme. In the case X = Q an ingenious scheme was
developed by Cantor. We first show that N is equivalent to Q+, the
positive rationals, by lining up the positive rationals according to the
sum of their numerator and denominator. One picture (or actually two)
is worth a thousand words at this stage. Note that repeats clearly occur
in the array in Figure 8.6a. In counting through the array of positiveFigure 8.6 The idea behind the proof that Q
is countable is a systematic "lining up" of the
positive rationals, as pictured.
11 11 L...
12345
11 12345 2 22 ...
2 12345 2.3 2 2...
...
...
...
(a)