Hilbert's Grand Hotel

File:Cobson.png

Hilbert's Grand Hotel is a famous analogy and paradox used to explain the notion of countability. One starts off by imagining a hotel, with an infinite amount of rooms, and each is occupied. One's intuition says that it's not possible to fit any more people - however, due to the often unintuitive ways infinite bijections work, it is actually possible to still fit many more people.

Firstly, if there is a single new guest who wants a room, it is possible to accommodate by simply telling everyone to move up one room - so the person checked in Room 0 moves to Room 1, the person checked in Room 1 moves to Room 2, and so on. Because every room has a room coming after it, everybody who was checked in still has a room. Yet Room 0 is now empty - the new guest can check in there. This is analogous to the proof that \(\omega\) and \(\omega+1\) are equinumerous (that is, they have the same cardinality). Similarly, if someone in room \(n\) checks out of the hotel, then everybody in room \(m\) for \(m > n\) can move one room to the left, and all the rooms will be filled again.

One can also accommodate countably infinitely many new guests, by requiring that every current guest in Room \(n\) goes to Room \(2n\) and that the \(n\)th new guest go to Room \(2n+1\). The first part frees up all the odd-numbered rooms, which the new guests can fill up. Therefore, \(\omega 2\) is equinumerous with \(\omega\).

In fact, it's even possible to accommodate a countably infinite collection of countably infinitely many sets of new guests! One can assign the current guest in room \(n\) to room \(2^n\), the \(n\)th guest in the first collection of new guests to room \(3^n\), the \(n\)th guest in the next collection of new guests to room \(5^n\), then \(7^n\), \(11^n\), and so on. Because there are infinitely many prime numbers, and powers of primes never overlap, everybody can be accommodated - even with many rooms now empty, such as room 6, which isn't a power of any prime number!

However, not every infinite batch of guests can fit in Hilbert's Grand Hotel. If a bus brings infinitely many guests whose names are all infinite strings made up of "a" and "b", and every string has a guest, not all of the guests can fit. In fact, it's possible to pair up each name to a real number, showing that there are more real numbers than natural numbers, even though there are infinitely many of both!