284 RELATIONS: FUNCTIONS AND MAPPINGS Chapter 8
interval on the real line (see Exercise 1) are uncountable, and in fact have
the cardinal number c.
There are two remaining questions about cardinality that we wish'to
address in some detail. First, is there any relationship of order between
the two infinite cardinal numbers KO and c, similar to the relation < existing
between any two finite cardinal numbers? We have seen that N and (0, 1)
have different cardinal numbers, KO and c, respectively. Is one of these sets
of a "higher" or "larger" level of infinity than the other? The answer is not
totally clear if we rely solely on our intuition. N seems larger in the sense
that it is unbounded, whereas (0,l) is bounded. On the other hand, between
any two elements of (0, 1) lies another element of (0, I), a statement not
true for N. In this sense (0, 1) seems larger. To "muddy the waters" fur-
ther, keep in mind that Q r N and Q (0, l), even though Q differs from
N and resembles (0, 1) in containing, between any two of its members, an-
other of its members. Clearly this problem calls for some clear and rigor-
ous thinking.
Second, we wish to ask whether there are other infinite cardinal numbers
besides KO and c. Our starting point in dealing with both these problems
is the following definition.
DEFINITION 4(a) Let A and B be sets. We write A^5 B and say the cardinal number of A
is less than or equal to the cardinal number of 6, if and only if there
exists a one-to-one mapping f: A + B.
(6) We write A < B if and only if A 5 B, but A $ B. In this case we say that
the cardinal number of A is (strictly) less than the cardinal number of 6.Note that A 5 B if and only if A is numerically equivalent to a subset
of B (namely, im f), including possibly B itself. Stated differently, the rela-
tionship A 5 B between two sets leaves open the possibility that A r B,
analogous to the connection between the relations I and = on the real
numbers. On the other hand, A < B means that there exists a one-to-one
mapping of A into B, but no such mapping of A onto B.
Only (b) of Definition 4 is needed to settle the question whether KO and
c are the only infinite cardinal numbers. An immediate consequence of the
following result is that there are infinitely many infinite cardinal numbers.
T H E 0 R E M 4 (Cantor's theorem)
Let S be any set. Then S < B(S).
Proof First, the mapping x -, {x) is clearly a one-to-one mapping of S
into 9(S), so that S 5 9(S). We must still show that there is no one-
to-one mapping of S onto 9(9. For suppose f: S -+ 9(S) were such a
mapping. Now, for each x E S, f(x) E 9(S), so that f(x) E S. Thus for
each x E S, we may consider whether x E f (x). Surely we may say that