270 CHAPTER 4 Functions
Set G(n) to be the nth rational number on the list above. Then, by the discussion
above, G : N --* Q is 1-1 and onto. 0
The proof of Theorem 7 is especially important. This method of proof is called Can-
tor's first diagonal argument. Another view of how the positive elements of Q are arranged
and counted shows why this is called a diagonal argument (see Figure 4.27). Only elements
of Q with no common factors in the numerator and the denominator are shown so that no
element is counted more than once.
1/1 --* 1/2 1/3 - 1/4 1/5 1/6 1/7 - 1/8 ...2/1 2/3 2/5 2/7 ...
177I.. 7 7J 7" 7" -
3/1 3/2 3/4 3/5 3/7 3/8 ...
7- , 7 77 7/ 7 7
4/1 4/3 4/5 4/75/1 5/2 5/3 5/4 5/6 5/7 5/8 ...Figure 4.27 Counting positive rational numbers.4.8.3 Uncountable Sets and Cantor's Second Diagonal Argument
After one sees Cantor's proof that Q is countably infinite, it is natural to conjecture that
all infinite sets are countably infinite. Hence, it may be a bit surprising that sets that are
not countable (or uncountable) exist. Cantor proved that IR is not countable. That proof
involves using the decimal expansions of real numbers.
Several familiar facts about the decimal expansion of rational numbers were presented
in Section 4.6.3. The fundamental idea needed here is that for any real number, there is a
decimal expansion of the formC CO.C1 C2C3 ... Ci ...
where co is in Z and ci e 10, 1 ... , 91 where i c N - {O}. A thorough study of decimal
expansions requires careful development of the real numbers and will not be discussed in
this book. One property of some real numbers is that they have two decimal expansions-
for example,
117
0.233999 .... 0.2340000 ....
500
Important properties of the decimal representations of real numbers needed here are listed
in Theorem 8.Theorem 8.
(a) Every real number has at least one decimal expansion, and no real number has more
than two decimal expansions.
(b) Every decimal expansion is the decimal expansion of some real number.