Page 193 - Discrete Mathematics and Its Applications

172 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

. . .
. . .

8
7 . . .
6
5
4
3
Hilbert’s
2
1
Grand
Hotel
Take room 1,
everyone else
move down one room
Manager New guest

FIGURE 2 A New Guest Arrives at Hilbert’s Grand Hotel.

EXAMPLE 2 How can we accommodate a new guest arriving at the fully occupied Grand Hotel without
removing any of the current guests?

Solution: Because the rooms of the Grand Hotel are countable, we can list them as Room 1,
Room 2, Room 3, and so on. When a new guest arrives, we move the guest in Room 1 to Room
2, the guest in Room 2 to Room 3, and in general, the guest in Room n to Room n + 1, for all
positive integers n. This frees up Room 1, which we assign to the new guest, and all the current
guests still have rooms. We illustrate this situation in Figure 2. ▲

When there are finitely many room in a hotel, the notion that all rooms are occupied is
equivalent to the notion that no new guests can be accommodated. However, Hilbert’s paradox
of the Grand Hotel can be explained by noting that this equivalence no longer holds when there
are infinitely many room.

EXAMPLES OF COUNTABLE AND UNCOUNTABLE SETS We will now show that cer-
tain sets of numbers are countable. We begin with the set of all integers. Note that we can show
that the set of all integers is countable by listing its members.

EXAMPLE 3 Show that the set of all integers is countable.

Solution: We can list all integers in a sequence by starting with 0 and alternating between
positive and negative integers: 0, 1, −1, 2, −2,... . Alternatively, we could find a one-to-one
correspondence between the set of positive integers and the set of all integers. We leave it to the
reader to show that the function f (n) = n/2 when n is even and f (n) =−(n − 1)/2 when n
is odd is such a function. Consequently, the set of all integers is countable. ▲

It is not surprising that the set of odd integers and the set of all integers are both countable
sets (as shown in Examples 1 and 3). Many people are amazed to learn that the set of rational
numbers is countable, as Example 4 demonstrates.

EXAMPLE 4 Show that the set of positive rational numbers is countable.

Solution: It may seem surprising that the set of positive rational numbers is countable, but we
will show how we can list the positive rational numbers as a sequence r 1 ,r 2 ,...,r n ,.... First,
note that every positive rational number is the quotient p/q of two positive integers. We can