Hilbert's Hotel

As it says on the margins, I'm a physics student.  But I have a small confession to make: I'm taking all math classes this quarter.  I have been thinking about writing a series of posts explaining infinite sets at a popular level, one I will likely never finish.

The problem with infinite sets is that they're counter-intuitive. This isn't a problem with the math, but a problem with our intuition.  If you find these things strange, you just have to get used to it.

Let's start with Hilbert's Hotel, the hotel with an infinite number of rooms.  More specifically, there is exactly one room for each positive integer (1, 2, 3, 4, ...).  Hilbert's Hotel has the interesting property that you can always make room for more guests, even if all the rooms are filled.

You simply tell each guest to move to the next room over.  The person in room 1 moves to room 2, and the person in room moves to room 3.  The person in room 10¹⁰⁰ moves to the room 10¹⁰⁰ + 1.  Every single guest has somewhere to go, because for every positive integer you can add 1 and get another positive integer.  At the end of this shuffle, room 1 is empty.  Now Hilbert can accommodate one new guest.

Some people might see this as an illustration of the statement, "Infinity plus one equals infinity."  But that is an inaccurate way of describing it.  Infinity is not the same kind of number that we usually work with.  We're used to working with "real" numbers, which can be approximated with decimal expansions.  For instance, we can approximate π within 1/100th by 3.14.  You cannot approximate infinity within 1/100th, because every decimal number will still be infinitely far away.  Since infinity isn't a real number, you can't add it to real numbers and get a sensible answer.

But there are other number systems besides the real numbers.  With Hilbert's Hotel, we're working with cardinal numbers, which are a way of characterizing the size of a set.  For example, we could take the set of all rooms in Hilbert's Hotel and give it a cardinal number.  Similarly, we can take the set of all guests in the hotel and give them another cardinal number.

If the guests exactly fill the rooms, then we say that the two cardinal numbers are equal.  For example, if there are three guests and three rooms, then the guests can exactly fill the rooms, and the two sets have the same cardinal number.  This is true, even if the guests decide to all occupy the same room, leaving the other two empty.  The point is that the guests could exactly occupy the rooms if they were shuffled around the right way.

With this in mind, let's return to the original example, where there are an infinite number of rooms exactly filled.  Because they're exactly filled, we can say that the set of rooms and set of guests are of equal size.  If one more guest needs a room, then we can shuffle around the guests to exactly fill the rooms again.  Therefore, the set of guests remains the same size before and after we add a new guest to the guest list.

Suppose that Hilbert has not one but two hotels, all exactly filled up.  But he needs to close down the second hotel and kick out all the guests.  Luckily, the set of guests and set of rooms is still equal. If we shuffle around the guests we can still make room for all of them.  Just tell all the guests in the first hotel to take their room number and double it.  All the odd-numbered rooms are now empty, and Hilbert can accommodate the rest of his guests.

Hey, remember back when Chuck Norris jokes were cool?  One of the jokes was, "Chuck Norris counted to infinity... twice!"  When you understand why two infinite hotels are just as good as one, then you will understand why counting to infinity twice is no harder than counting to infinity once.  I was far more impressed the time Chuck Norris counted the real numbers.

The series on infinite sets:
Hilbert's Hotel
Doubling the Sphere
Larger infinities and the Diagonal Proof 
Power sets and the Chef Paradox 
The unmeasurable set