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 Color1 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
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 perhaps, at last, defined) a term we have used throughout this book, some of our earlier 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 mathematics, 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 critically 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 proving 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.
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 Color1 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
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 perhaps, at last, defined) a term we have used throughout this book, some of our earlier 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 mathematics, 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 critically 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 proving 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.