Relevant definitions:
“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 called uncountable. 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.”
“The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. We also say that such a function is bijective.”
HILBERT’S GRAND HOTEL “We now describe a paradox that shows that something impossible 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.”
The definitions above are from the textbook Discrete Mathematics and its Applications by Rosen.
Answer:
We have a countably infinite set of guests as the Grand Hotel is fully occupied.
To spread the guests to fill every room in the two buildings we can do the following:
- Every guest in room n, where n is an even number, goes to room n/2 in the first building. As n=1,2,3,…, the guest in room 2, goes to room 1 in the first building; the guest in room 4, goes to room 2 in the first building; the guest in room 6, goes to room 3 in the first building, and so on. As you can see, there are no rooms left empty in the first building.
- Every guest in room n, where n is an odd number, goes to room (n+1)/2 in the second building. As n=1,2,3,…, the guest in room 1, goes to room (1+1)/2=1 in the second building; the guest in room 3, goes to room (3+1)/2=2 in the second building; the guest in room 5, goes to room (5+1)/2=3 in the second building, and so on. As you can see, there are no rooms left empty in the first building.
Related exercises:
- 3. Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set
- 4. Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.
- 6. Suppose that Hilbert’s Grand Hotel is fully occupied, but the hotel closes all the even numbered rooms for maintenance. Show that all guests can remain in the hotel
- 8. Show that a countably infinite number of guests arriving at Hilbert’s fully occupied Grand Hotel can be given rooms without evicting any current guest
- ∗9. Suppose that a countably infinite number of buses, each containing a countably infinite number of guests, arrive at Hilbert’s fully occupied Grand Hotel. Show that all the arriving guests can be accommodated without evicting any current guest
