126 Chapter 2 • Sequences
in 1-1 correspondence with N , and is uncountable otherwise. To make these
ideas clear we must begin with precise definitions.
Definition 2.8.1 (Equivalent Sets) We say that two sets, A and B , are
equivalent (in symbols, AS:! B) if there is a 1-1 correspondence f: A --t B. If
AS:! B, we say that A and B have the same number of elements.
Definition 2.8.2 (a) A set S is finite if 3 n EN 3 SS:! {1, 2,-· · , n };
(b) A set Sis denumerable if SS:! N;
(b) A set is countable if it is finite or denumerable;
( c) A set is uncountable if it is not countable.
Example 2.8.3 The even numbers form a denumerable set; so do the odd
numbers and sets like {1, 4, 9, 16, 25 ,... } = {n^2 : n EN}.
Theorem 2.8.4 Every infinite set has a denumerable subset.
Proof. Let S be an infinite set. Let x 1 E S. Then^17 S - {xi} is still
infinite. Choose any X2 E S - {xi}. Then x2 -=/=-x1 and S - { x1, x2} is still
infinite. We proceed by mathematical induction. Assume x 1 , x2, · · · , Xn (all
different) have been chosen in S; then S - { x 1 , x 2 ,. · · , Xn} is still infinite.
Choose Xn+i E S - { x 1 , x2, .. · , Xn}. By mathematical induction, we get a
denumerable subset { x 1 , x2, · · · , Xn, · · · } of S. •
Thus, denumerable sets are the smallest infinite sets, while uncountable
sets are a larger order of infinity in size. This topic fits nicely into this chapter,
since denumerable sets are those sets whose elements can be arranged
in a sequence. An uncountable set has so many elements that they cannot
be arranged in a sequence; there are more elements in the set than there are
natural numbers for use as subscripts in naming the elements of the set.
Cantor went on to classify many known infinite sets according to whether
they were countable or uncountable. He made some surprising discoveries.
THE RATIONAL NUMBERSOne might guess that the rational numbers form an uncountable set, since
they seem to be much more numerous than the natural numbers. After all, the
natural numbers are discretely located at one-unit intervals along the number
line, whereas the rational numbers are densely scattered everywhere along the
line. In every interval of the number line, no matter how small, there are in-
finitely many rational numbers. Imagine the astonishment of the mathematical
world when Cantor successfully proved that the rational numbers are count-
able. They are not more numerous than the natural numbers. Theorem 2.8.5
and its corollary are essentially his proof of this remarkable fact.
- In Appendix B.l, we define S -{xi} to be {x ES: xi= xi}.