Hilbert's Paradox of the Grand Hotel

Hilbert's Paradox of the Grand Hotel

A hotel with infinitely many rooms, all occupied, can still take in new guests, and even infinitely many of them. Hilbert's thought experiment shows how strange infinity really is.

A hotel is full. Every room is taken. A new guest walks in, and the manager cheerfully finds them a room without throwing anyone out. That's the puzzle at the heart of Hilbert's Paradox of the Grand Hotel, a thought experiment the mathematician David Hilbert used to show just how weird infinity is.

Start with an ordinary hotel. It has a fixed number of rooms, they're all occupied, a new guest arrives. Tough luck: no vacancies.

Now picture the Grand Hotel, which has infinitely many rooms, every one of them occupied. Surely it's full too?

Not quite. When a new guest arrives, the manager asks everyone to move up one room: the guest in room 1 goes to room 2, room 2 goes to room 3, and so on forever. Nobody is left without a room, and room 1 is suddenly free.

It gets stranger:

  1. An infinite number of new guests arriveThe manager asks each guest to move to the room with double their current number (1 goes to 2, 2 goes to 4, 3 goes to 6...). Every odd-numbered room is now empty, and there are infinitely many of those, enough for all the newcomers.

  2. A bus with a countably infinite number of passengers arrivesSame trick. Everyone doubles their room number, the odd rooms open up, and every passenger gets a bed.

However "full" the Grand Hotel is, it can always squeeze in more. That's not a booking error; it's how infinite sets behave. If that bends your brain, you're in good company: more than two thousand years earlier, Zeno's Dichotomy Paradox was already tying people in knots over infinity.

Hilbert's Paradox of the Grand Hotel, introduced by the German mathematician David Hilbert (Hilbert, 1924), is a thought experiment that makes the strange behaviour of infinite sets, particularly countable infinities, almost tangible. It throws the difference between countable and uncountable sets into relief and shows off the concept of cardinality in set theory (Cantor, 1895).

The setup: a hotel has a countably infinite number of rooms, and every one is occupied. Yet with a clever reassignment of rooms, the hotel can always take in more guests. The lesson is that the cardinality of a countably infinite set does not change when you add or remove elements (Halmos, 1974). "Full" simply doesn't mean what it means for a finite hotel.

The paradox opens onto several deeper ideas in mathematics and theoretical computer science:

  1. Set theory and cardinalityAll countably infinite sets have the same cardinality (size), written ℵ0 (aleph-null) (Cantor, 1895). Cardinality measures the "number of elements" in a set, and two sets have the same cardinality if there is a one-to-one correspondence (a bijection) between them (Cantor, 1895). Each room shuffle in the Grand Hotel is such a bijection, which is why the set of natural numbers keeps cardinality ℵ0 no matter how many guests check in or out (Halmos, 1974).

  2. Cantor's diagonal argumentGeorg Cantor (Cantor, 1891) showed that infinities come in different sizes. His diagonal argument proves that the set of real numbers is uncountable, with a strictly larger cardinality than the natural numbers (Cantor, 1891); that size is often written as ℵ1, an identification that strictly holds only if one assumes the continuum hypothesis. The Grand Hotel lives entirely in countable infinity, and Cantor's result is a reminder that there are infinities so much bigger that no room-numbering scheme could ever house them.

  3. Computability and the Halting problemThe paradox also has a cousin in theoretical computer science. The Halting problem asks for an algorithm that can decide whether any given program will eventually stop or run forever, and Turing proved no such algorithm can exist (Turing, 1936). Both the hotel and the Halting problem probe infinity and the limits of what can be computed.

Hilbert's hotel endures because it turns abstract set theory into a story you can picture, and in doing so it sharpens our intuitions about infinity, cardinality and the boundaries of computation, much as Zeno's Dichotomy Paradox did for infinite series two millennia earlier.

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

More Resources