Discrete Mathematics for Computer Science

Countable and Uncountable Sets 265

cardinality of finite sets more precisely. In Section 1.5.1, we gave a provisional definition

for counting the number of elements in a set that can now be made more precise.

Consider checking to see whether the sets {red, blue, green) and {Jean, Michele, Paul)

have the same number of elements. Of course, each set has three elements, and one merely

counts the elements:

{(0, red), (1, blue), (2, green))

and

{(0, Jean), (1, Michele), (2, Paul)}

Each of the two sets of ordered pairs are 1-1 functions, the first from {0, 1, 21 onto {red,

blue, green--call it Color-and the second from {0, 1, 2} onto {Jean, Michele, Paul)-

call it Person. Consider the set {0, 1, 2} only as an intermediary. The function Color-^1 o

Person is a 1-1 function (Theorem 3(c) in Section 4.3.2 and Theorem 2(a) in Section

4.3.1) (from {red, blue, green) onto {Jean, Michele, Paul). This function shows, without

explicitly counting, that the two sets have the same number of elements in the sense that

we now make more precise.

Definition 1. (Cantor) Let X and Y be sets. Then, the cardinality of X is less than or

equal to the cardinality of Y, written I X I < I Y 1, if there is a 1-1 function F : X --* Y.

The cardinality of X is equal to the cardinality of Y, written I X I = I Y I, if there is a 1-1

correspondence F : X --> Y. The cardinality of X is less than the cardinality of Y, written

X I<IY 1, if IX l_<IYland IY I IX 1.

The definition of I X = I Y I generalizes Theorem 5 in Section 4.6. Notice that we

have not defined the term cardinality of X here, only some relationship between X and Y.

Using these notions, one can define the usual notion of cardinality for a finite set.

Definition 2. Let X be a set and n e N. If X has the same cardinality as the set
{0, 1,2 ... , n - 1}, then the cardinality of X is n. We say X is finite if X has cardinality
equal to some natural number. We say X is infinite if X is not finite.
At this point, the careful reader should note that, since we have redefined (or per-
haps, at last, defined) a term we have used throughout this book, some of our ear-
lier proofs may have been false, relying on unprovable intuitions. In fact, as the reader
surely suspects, the earlier results are not false by this definition; however, the proofs
may have important parts missing. This is not a book about the foundations of math-
ematics, so we shall not go back to recheck any proofs. We shall make one further
remark, however: The entire discussion of the Pigeon-Hole Principle depended crit-
ically on the result that if m and n are natural numbers and m > n, then the sets
{0, 1, 2 ... , m - 11 and {0, 1, 2, ...., n - 1) do not have the same cardinality. After the
previous discussion, the student likely has no idea what one is allowed to use in prov-
ing such a result. In the development of the foundations of mathematics, this theorem
can be proved by induction on m. The interested reader is invited to look for a simple
proof.
The following properties of cardinalities are easy to prove. They are also suggested by
the notations for equal (=) and less than or equal (<), but it is, of course, very dangerous
to assume such results by analogy based on notation.