Bridge to Abstract Mathematics: Mathematical Proof and Structures

8.3 CARDINAL NUMBER OF A SET 285

either x E f(x) or x 4 f(x) for each x E S. Consider the set N =

(x E S 1 x 4 f (x)}. Clearly N E S so N E 9(S). Since f is assumed to be

onto, there exists x, E S such that f (x,) = N. Now either x, E N or

x, & N. If x, E N, then x, & f(x,) = N, so x,^4 N, a contradiction. If

x, # N, then x, E f(x0) = N, again a contradiction. Our assumption of

the existence of a one-to-one mapping of S onto 9(S) leads to a contra-

diction, so that no such mapping exists, and our desired conclusion

S < 9(S) is established. 0

Note that N < 9(N) < 9(P(N)) <.. and so forth. The same can be
said of R, 9(R), 9(9(R)), and so on. The existence of infinitely many dis-
tinct infinite cardinal numbers is established.
We now wish to get at the relationship between KO and c. Our first
result (Theorem 5) will probably come as no surprise to you; first, we prove
a more general fact, from which our theorem follows immediately.

LEMMA

If A and B are sets with A E B, then A <_ 6.

Proof Clearly the inclusion mapping i,: A + B is a one-to-one mapping
of A into B.

THEOREM 5

N 5 R.

Since R z (0, I), we may conclude from Theorem 5 [by way of Exer-
cise 6(c)] that N 5 (0, 1) also. Viewing the relation 5 between sets as a
relation between the cardinal numbers of those sets, we may rephrase Theo-
rem 5 as KO < c [again, see Exercise 6(c)].
Actually, there is much more we can say about the relationship between
KO and c. First, as a result of Theorems 3 and 5, we may conclude KO < c.
Second, and quite remarkably, we can prove that P(N) s R, a result often
expressed in terms of cardinal numbers by the equation 2'0 = c. (Note: If
A and B are sets with cardinal numbers a and B, we denote by aS the car-
dinal number of the set of all mappings from B into A. Hence 2'0 is the
cardinal number of the set of all mappings of N into (0, I}, clearly numeri-
cally equivalent to the collection of all subsets of N.) An important tool
in the derivation of this result is a theorem that is both very famous and
highly important in its own right. The Schroeder-Bernstein theorem states
essentially that .< is an antisymmetric relation between cardinal numbers.

T H E 0 R E M 6 (Schroeder-Bernstein)

Given sets A and 8, if A I B and B 5 A, then A r B.

Proof Our hypotheses yield the existence of injections f: A -, B and

g: B -* A. We must use these mappings somehow to produce a bijection

h: A -, B. The technique is more complicated than you might suspect