8.3 CARDINAL NUMBER OF A SET 287Proof Since (0, 1) z R, by Exercise 1, we may just as well prove that (0, 1)
9(N). We will show that (0,l) 5 9(N) and P(N) 11 (0,l) and appeal to
Schroeder-Bemstein. To define a one-to-one mapping f of (0, 1) into
P(N), let .b, b2b3... be the binary expansion of a given x E (0, I), so that
each bi is either 0 or 1. As before; that is, in the proof of Theorem 3,
we outlaw the use of an infinite string of 1's in a binary representation,
in order to guarantee uniqueness. Now define f by the rule f(x) =
(n E N 1 b, = 1). By the uniqueness of binary representation, we conclude
that f is a one-to-one mapping of (0,l) into 9(N). To prove 90 I<_ (0, I),
let A G N. We must associate with A in a one-to-one fashion an element
of (0, 1). Using standard decimal representation of numbers in (0, I),
with the (by now familiar) eschewing of infinite strings of nines, we decree
that g(A) = .xlx2x3... , where xi = 4 if i E A and xi = 7 if i 4 A. Clearly
g maps 9(N) into (0, 1). Furthermore, by uniqueness of decimal repre-
sentation, if g(A) = g(B), where g(B) = .y,y2y,... , then xi = yi = either
4 or 7 for all i E N, so that i E A if and only if i E B; that is, A = B.
Hence g is one to one and the proof is complete. 0
Before concluding our coverage of cardinality of sets, we allude briefly
to one of the most famous (and, until recently, unsolved) problems in mod-
em mathematics. In the continuum hypothesis Cantor conjectured that there
is no infinite cardinal number properly between KO and c; that is, no set
X exists such that N < X < P(N). Only in 1963 was it proved by the
logician Paul Cohen that this proposition is undecidable on the basis of
the usual axioms of formal set theory; that is, the proposition can neither
be proved nor disproved in that context. This may give you some idea of
the kinds of research problems Cantor's theory has led to in modern times,
as well as indicating the level of difficulty involved in dealing with those
problems. Actually, there are many other, relatively elementary, questions
on cardinality of sets whose answers are known, but whose solutions (i.e.,
proofs) we choose not to deal with in this text. We conclude this article,
presenting, without proof and with only brief commentary, a list of addi-
tional theorems about cardinality.
- Results about finite and infinite sets (several of these may be proved
by mathematical induction):
(a) A set X is finite if and only if X z F, for some n E N.
(b) F, r F, if and only if m = n, for any m, n E N.
(c) F, I F, if and only if m I n, for any m, n E N.
(d) Every subset of a finite set is finite.
(e) If A and B are finite sets, then A u B is finite.
(f) If A,, A,,... , A, are finite sets, then U;=, A, is finite.
(g) If A is infinite and B is finite, then A - B is infinite.