Page 194 - Discrete Mathematics and Its Applications

2.5 Cardinality of Sets 173

1 2 3 4 5 ...
1 1 1 1 1
Terms not circled
are not listed 1 2 3 4 5 ...
2 2 2 2 2
because they
repeat previously 1 2 3 4 5 ...
listed terms 3 3 3 3 3
1 2 3 4 5 ...
4 4 4 4 4
1 2 3 4 5 ...
5 ... 5 ... 5 ... 5 ... 5 ...

FIGURE 3 The Positive Rational Numbers Are Countable.

arrange the positive rational numbers by listing those with denominator q = 1 in the first row,
those with denominator q = 2 in the second row, and so on, as displayed in Figure 3.
The key to listing the rational numbers in a sequence is to first list the positive rational
numbers p/q with p + q = 2, followed by those with p + q = 3, followed by those with
p + q = 4, and so on, following the path shown in Figure 3. Whenever we encounter a number
p/q that is already listed, we do not list it again. For example, when we come to 2/2 = 1we
do not list it because we have already listed 1/1 = 1. The initial terms in the list of positive
rational numbers we have constructed are 1, 1/2, 2, 3, 1/3, 1/4, 2/3, 3/2, 4, 5, and so on. These
numbers are shown circled; the uncircled numbers in the list are those we leave out because
they are already listed. Because all positive rational numbers are listed once, as the reader can
verify, we have shown that the set of positive rational numbers is countable. ▲

An Uncountable Set

Not all infinite sets have
the same size! We have seen that the set of positive rational numbers is a countable set. Do we have a promising
candidate for an uncountable set? The first place we might look is the set of real numbers. In
Example 5 we use an important proof method, introduced in 1879 by Georg Cantor and known
as the Cantor diagonalization argument, to prove that the set of real numbers is not countable.
This proof method is used extensively in mathematical logic and in the theory of computation.

EXAMPLE 5 Show that the set of real numbers is an uncountable set.
Solution: To show that the set of real numbers is uncountable, we suppose that the set of real
numbers is countable and arrive at a contradiction. Then, the subset of all real numbers that
fall between 0 and 1 would also be countable (because any subset of a countable set is also
countable; see Exercise 16). Under this assumption, the real numbers between 0 and 1 can be
listed in some order, say, r 1 ,r 2 ,r 3 ,.... Let the decimal representation of these real numbers be

r 1 = 0.d 11 d 12 d 13 d 14 ...
r 2 = 0.d 21 d 22 d 23 d 24 ...
r 3 = 0.d 31 d 32 d 33 d 34 ...
r 4 = 0.d 41 d 42 d 43 d 44 ...
.
.
.
where d ij ∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. (For example, if r 1 = 0.23794102 ..., we have d 11 =
2, d 12 = 3, d 13 = 7, and so on.) Then, form a new real number with decimal expansion