Hilbert's Paradox of the Grand Hotel
What is it?
Hilbert's Paradox of the Grand Hotel is a mathematical thought experiment that shows how an infinite hotel with an infinite number of rooms can still accommodate additional guests, even if the hotel is already fully occupied.
Hilbert's Paradox of the Grand Hotel is a thought experiment created by the mathematician David Hilbert. It is meant to illustrate some of the counterintuitive properties of infinite sets. Let's break it down using a simple example.
Imagine a hotel with a finite number of rooms. Suppose all the rooms are occupied, and a new guest arrives. Since there are no vacancies, the new guest cannot be accommodated, and the hotel is considered full.
Now, imagine a hotel with an infinite number of rooms, called the Grand Hotel. Every room is occupied by a guest. At first glance, you might think that the Grand Hotel is also full, and that no more guests can be accommodated. However, this is where the paradox comes into play.
If a new guest arrives at the Grand Hotel, the manager can simply ask every current guest to move to the room with the room number one higher than their current room number (i.e., the guest in room 1 moves to room 2, the guest in room 2 moves to room 3, and so on). By doing this, the first room becomes vacant, and the new guest can be accommodated.
The paradox becomes even more counterintuitive when you consider different scenarios:
An infinite number of new guests arrive: The manager can ask each current guest to move to the room with twice their current room number (i.e., the guest in room 1 moves to room 2, the guest in room 2 moves to room 4, and so on). This way, all odd-numbered rooms become vacant, and the infinite number of new guests can be accommodated.
A bus with a countably infinite number of passengers arrives: Similar to the first scenario, the manager can ask each current guest to move to the room with twice their current room number, freeing up all odd-numbered rooms for the new guests.
In all these cases, despite the Grand Hotel being "full," it can still accommodate more guests, which is a paradoxical result that highlights the peculiar nature of infinite sets.
Hilbert's Paradox of the Grand Hotel, introduced by the German mathematician David Hilbert (Hilbert, 1924), is a thought experiment that serves as an illustration of the counterintuitive properties of infinite sets, particularly countable infinities. It highlights the distinction between countable and uncountable infinite sets and showcases the concept of cardinality in set theory (Cantor, 1895).
In the paradox, there exists a hypothetical hotel with a countably infinite number of rooms, each occupied by a guest. Despite being fully occupied, the hotel can still accommodate additional guests by employing a suitable room reassignment strategy. This paradox exposes the unique properties of countable infinity and demonstrates that the cardinality of a countably infinite set remains unchanged even after adding or removing elements (Halmos, 1974).
The Grand Hotel paradox can be connected to several principles and concepts in mathematics and theoretical computer science:
Set theory and cardinality: The paradox demonstrates that countably infinite sets have the same cardinality (size), denoted as âľ0 (aleph-null) (Cantor, 1895). The cardinality of a set is a measure of the "number of elements" in the set, and two sets have the same cardinality if there exists a one-to-one correspondence (a bijection) between them (Cantor, 1895). In the case of the Grand Hotel, the bijections formed by reassigning rooms show that the cardinality of the set of natural numbers (âľ0) remains the same even after adding or removing elements (Halmos, 1974).
Cantor's diagonal argument: This thought experiment, introduced by Georg Cantor (Cantor, 1891), demonstrates that there are different "sizes" of infinity. Cantor's diagonal argument proves that the set of real numbers is uncountable and has a larger cardinality (denoted as âľ1) than the set of natural numbers (Cantor, 1891). While the Grand Hotel paradox deals with countable infinity, Cantor's diagonal argument highlights the existence of uncountable infinities that are fundamentally larger.
Computability and the Halting problem: The Grand Hotel paradox is related to the concept of computability and the Halting problem in theoretical computer science. The Halting problem, which is undecidable, refers to the impossibility of creating an algorithm that can determine whether an arbitrary computer program will halt or run forever (Turing, 1936). Both the paradox and the Halting problem involve concepts of infinity and the limits of computation.
In summary, Hilbert's Paradox of the Grand Hotel is an important thought experiment that highlights the unique properties of countably infinite sets and their implications in mathematics and theoretical computer science. By understanding the paradox, we gain valuable insights into the nature of infinity, cardinality, and the limitations of computation.
References
- Cantor, G. (1891). Ăber eine elementare Frage der Mannigfaltigkeitslehre. Jahresbericht der Deutschen Mathematiker-Vereinigung, 1, 75-78.
- Cantor, G. (1895). Beiträge zur Begrßndung der transfiniten Mengenlehre. Mathematische Annalen, 46, 481-512.
- Halmos, P. R. (1974). Naive set theory. Springer.
- Hilbert, D. (1924). Grundlagen der Mathematik. Springer.
- Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42
