Discrete Mathematics for Computer Science

266 CHAPTER 4 Functions

Theorem 1. (Properties of Cardinalities) Let X, Y, and Z be sets.

(a) IXI < IXI.

(b) If IXlI<lIY Iand IYl <IZ1, then IX < _ IZ 1.

(c) IX =IXI.

(d) If I X I = l Yl, then lYI = IXi.

(e) IflXI = IYI andIYI-=I ZI,thenlXI---Z1.

Proof This proof is left as an exercise for the reader.^0

One is tempted to restate parts (c) through (e) of Theorem 1 by stating that the relation

has the same cardinality as is an equivalence relation. This is not done, however, because

if it is an equivalence relation, then it is an equivalence relation on the set of all sets-but

the set of all sets does not exist! Even so, it is correct to say that has the same cardinality

as is an equivalence relation on any set of sets.

A fundamental result regarding cardinality uses the work of Georg Cantor, Friedrich

Schrider (1841-1902, b. Germany), and Sergi Bernstein (1880-1968, b. Ukraine).

Theorem 2. (Cantor-Schroder-Bernstein) Let X and Y be sets, and let I X I <I Y I

and I Y I _ I X 1. Then, I XI = I Y 1.

The proof of the Cantor-Schroder-Bemstein Theorem is fairly complicated, and we re-

fer the reader to a text about set theory. A related question is whether there exist two sets X

and Y where I X I • I Y I and I Y I ;ý I X I. This question turns out to be related to whether

one accepts a famous and, sometimes, controversial axiom called the Axiom of Choice.

The reader is also referred to books on set theory and the foundations of mathematics for

discussion of this issue.

4.8.1 Countably Infinite Sets

Cantor's definition allows a more careful development of the study of finite sets, but the

study of infinite sets under Cantor's definition is sometimes surprising. The simplest infi-

nite sets are N and those other sets with the same cardinality as N.

Definition 3. Let X be a set. X is countably infinite if I X I = I N I. If X is countably

infinite, the cardinality of X is No (pronounced aleph nought), written I X I = Ko. X is

countable if it is either finite or countably infinite. If a set is not countable, then it is

uncountable.

In Definition 3 the object No was left undefined. For set theorists, No is another name

for N, but the symbol tRo is used almost exclusively to denote the cardinality of N.

Theorem 3. Any countably infinite set is infinite.

Proof. As noted earlier, N is infinite. Now, suppose a set X is both countably infinite and

finite. Then, there are 1-1 correspondences F : X -+ N and G : X -+ {0, 1, 2,..., n} for

some natural number n. However, then F-1 o G : N -* {0, 1, 2 ... , n} is 1-1 and onto by

Theorem 3(c) in Section 4.3.2, contradicting the result, noted above, that N is infinite. U

Theorem 5 in Section 4.6.2 says that for finite X and F : X -> X, F is 1-1 if and only

if F is onto. This result fails for infinite X. Earlier (see Section 4.1.8), a 1-1 function from