Page 192 - Discrete Mathematics and Its Applications

2.5 Cardinality of Sets 171

1 2 3 4 5 6 7 8 9 10 11 12 ...

1 3 5 7 9 11 13 15 17 19 21 23 ...

FIGURE 1 A One-to-One Correspondence Between Z and the Set of Odd Positive
+
Integers.

DEFINITION 3 A set that is either finite or has the same cardinality as the set of positive integers is called
countable.A set that is not countable is calleduncountable.When an infinite set S is countable,
we denote the cardinality of S by ℵ 0 (where ℵ is aleph, the first letter of the Hebrew alphabet).
We write |S|=ℵ 0 and say that S has cardinality “aleph null.”

We illustrate how to show a set is countable in the next example.
EXAMPLE 1 Show that the set of odd positive integers is a countable set.

Solution: To show that the set of odd positive integers is countable, we will exhibit a one-to-one
correspondence between this set and the set of positive integers. Consider the function

f (n) = 2n − 1

+
from Z to the set of odd positive integers. We show that f is a one-to-one correspondence by
showing that it is both one-to-one and onto. To see that it is one-to-one, suppose that f (n) =
f (m). Then 2n − 1 = 2m − 1, so n = m. To see that it is onto, suppose that t is an odd positive
integer. Then t is 1 less than an even integer 2k, where k is a natural number. Hence t = 2k − 1 =
f(k). We display this one-to-one correspondence in Figure 1. ▲

An infinite set is countable if and only if it is possible to list the elements of the set in a
sequence (indexed by the positive integers). The reason for this is that a one-to-one correspon-
dence f from the set of positive integers to a set S can be expressed in terms of a sequence
a 1 ,a 2 ,...,a n ,..., where a 1 = f(1), a 2 = f(2),...,a n = f(n),....
You can always get a room
at Hilbert’s Grand Hotel!
HILBERT’S GRAND HOTEL We now describe a paradox that shows that something impos-
sible with finite sets may be possible with infinite sets. The famous mathematician David Hilbert
invented the notion of the Grand Hotel, which has a countably infinite number of rooms, each
occupied by a guest. When a new guest arrives at a hotel with a finite number of rooms, and
all rooms are occupied, this guest cannot be accommodated without evicting a current guest.
However, we can always accommodate a new guest at the Grand Hotel, even when all rooms
are already occupied, as we show in Example 2. Exercises 5 and 8 ask you to show that we can
accommodate a finite number of new guests and a countable number of new guests, respectively,
at the fully occupied Grand Hotel.

DAVID HILBERT (1862–1943) Hilbert, born in Königsberg, the city famous in mathematics for its seven
bridges, was the son of a judge. During his tenure at Göttingen University, from 1892 to 1930, he made many
fundamental contributions to a wide range of mathematical subjects. He almost always worked on one area of
mathematics at a time, making important contributions, then moving to a new mathematical subject. Some areas
inwhichHilbertworkedarethecalculusofvariations,geometry,algebra,numbertheory,logic,andmathematical
physics. Besides his many outstanding original contributions, Hilbert is remembered for his famous list of 23
difficult problems. He described these problems at the 1900 International Congress of Mathematicians, as a
challenge to mathematicians at the birth of the twentieth century. Since that time, they have spurred a tremendous
amount and variety of research. Although many of these problems have now been solved, several remain open,
including the Riemann hypothesis, which is part of Problem 8 on Hilbert’s list. Hilbert was also the author of several important
textbooks in number theory and geometry.