Hilbert's paradox of the Grand Hotel

Hilbert's paradox of the Grand Hotel is a mathematical paradox named after the German mathematician David Hilbert. Hilbert used it as an example to show how infinity does not act in the same way as regular numbers do.

Normal hotels have a finite number of rooms. Once every room has been assigned to a guest, any new guest that wants a room can't get one. In other words, the hotel is fully booked.

The Grand Hotel is different, because it has infinite rooms. If all the rooms are filled, and a new guest wants a room, they can still get one. This might seem impossible, but there is a way.

Imagine moving the guest in room 1 to room 2, the guest in room 2 to room 3, the guest in room 3 to room 4, and so on. Every guest is moved to the room with one above their room number. It seems like the guest in the "last" room will end up without a room to stay in, but in the Grand Hotel, there is no last room. Every guest who already had a room still has a room.

Once this is done, room 1 will be vacant, so the new guest can go there. This shows how we can find a room for a new guest even if the Grand Hotel is completely full, something that could not happen in any hotel with a finite number of rooms.

Now imagine a massive bus arrives at the hotel, with infinite people inside of it. All of these infinite people want a room in the Grand Hotel. Again, this seems impossible, but there is a way.

Imagine telling the person in room 1 to move to room 2, the person in room 2 to move to room 4, the person in room 3 to move to room 6, and so on. Every guest is moved to the room with double their room number. When this is finished, all of the odd rooms will be vacant, and because there are infinite odd numbers, all of the new guests have a room to stay in.

Now imagine an infinite amount of busses, each containing infinite new guests, arrive at the hotel. Many different methods have been thought of to make this work.

Every whole number after 1 can be represented as a unique multiplication of prime numbers. This is called a prime factorization. For example, 10 is 2 * 5, 12 is 2 * 2 * 3, 14 is 2 * 7, etc. We can take advantage of this fact to give each infinite bus of infinite people a room.

First, we take out everybody currently in the hotel, and add them as another group in the infinite groups. They will be given new rooms later.

Next, we give each infinite group a prime number. The first group has the first prime number, the second group has the second prime number, and so on. We'll call this number ${\displaystyle P}$.

Then, inside each group, we give each infinite person a number, starting at 0. The first person in every group has 0, the second person in every group has 1, and so on. We'll call this number ${\displaystyle N}$.

Now, every person has two numbers to describe them. For example, the third person in the seventh group has (17, 2), the eightieth person in the fourth group has (7, 79), etc. These numbers are completely unique; each pair can only apply to one person. Therefore, we can use these pairs to give each person a room.

We'll do this by taking ${\displaystyle P}$, and multiplying it by itself ${\displaystyle N}$ times. In other words, we'll calculate ${\displaystyle P^{N}}$. The result of this calculation will be the room number for the passenger with any value of ${\displaystyle P}$ and ${\displaystyle N}$. For example, the passenger with (2, 5) will get room 16, the passenger with (7, 0) will get room 7, the passenger with (17, 1) will get room 289, etc.

This works for two reasons. First, each person's pair is unique to them, and is never repeated for any other person. Second, we use exponentiation, an anti-commutative math operation, to calculate the room numbers, which ensures that two reverse pairs—e.g. (7, 2) and (2, 7)—do not result in the same room number.

Imagine an infinite amount of airplanes, each containing an infinite amount of busses, each containing an infinite amount of people, arrive at the hotel. Again, there are many ways to make this work.

We can easily extend the prime powers method from before to make this work. We'll assign each airplane a prime number ${\displaystyle P_{1}}$, each bus a prime number ${\displaystyle P_{2}}$, and each person a natural number ${\displaystyle N}$. Then, every person will be given the room with the number ${\displaystyle P_{1}*(P_{2})^{N}}$. For example, the third person in the third bus in the third airplane will get room 125.

Address 4-7-7-4 goes to room 4774.

Address 0-1 (hotel dweller) stays because 1-0-0-0-1 moves to room 10,001.

and so on.

Each pod holds 10 people.

Each megapod holds 10 pods. (100 people)

Each supermegapod holds 10 megapods. (1,000 people)

Each superdupermegapod holds 10 supermegapods.

Each ultrasuperdupermegapod holds 10 superdupermegapod.

Each ultrasuperduperubermegapod holds 10 ultrasuperdupermegapods. (1,000,000 people)

And so on. This assumes that there is never an infinitieth layer. (The main ship)

Hilbert's paradox is a veridical paradox: it leads to a counter-intuitive result that is provably true. The statements "there is a guest to every room" and "no more guests can be accommodated" are not equivalent when there are infinitely many rooms. An analogous situation is presented in Cantor's diagonal proof.^[1]

At first, this state of affairs might seem to be counter-intuitive. The properties of "infinite collections of things" are quite different from those of "finite collections of things". The paradox of Hilbert's Grand Hotel can be understood by using Cantor's theory of transfinite numbers. In an ordinary (finite) hotel with more than one room, the number of odd-numbered rooms is obviously smaller than the total number of rooms. However, in Hilbert's aptly named Grand Hotel, the quantity of odd-numbered rooms is not smaller than the total "number" of rooms. In mathematical terms, the cardinality of the subset containing the odd-numbered rooms is the same as the cardinality of the set of all rooms. Indeed, infinite sets are characterized as sets that have proper subsets of the same cardinality. For countable sets (sets with the same cardinality as the natural numbers) this cardinality is ${\displaystyle \aleph _{0}}$.

Put differently, for any countably infinite set, there exists a bijective function which maps the countably infinite set to the set of natural numbers, even if the countably infinite set contains the natural numbers. For example, the set of rational numbers—those numbers which can be written as a quotient of integers—contains the natural numbers as a subset, but is no bigger than the set of natural numbers since the rationals are countable: there is a bijection from the naturals to the rationals.

• The Infinite Hotel Paradox - Jeff Dekofsky - TED-Ed Lessons