## Thursday, December 4, 2003

### The infinite hotel »

Imagine a hotel with an infinite number of rooms, numbered 1, 2, 3, and so on forever. All the rooms are full. A man comes in and asks the desk manager whether any rooms are available, and the desk manager replies, "All our rooms are full, but I’d be happy to accomodate you." How does he do it?

The answer: take the guest currently in room 1 and move him to room 2. Take the guest currently in room 2 and move him to room 3. And so forth. Put the new guy in room 1.

Infinity + 1 is still infinity. There are just as many integers from 1 to infinity as there are from 2 to infinity. If any finite number of new guests show up at the hotel, you can accomodate all of them.

Now imagine the same hotel, same situation, all rooms are full, and an infinite number of people all show up at the same time and ask for their own rooms. Once again, the desk manager replies, "All our rooms are full, but I’d be happy to accomodate all of you." How does he do it?

Answer: take the guest currently in room 1 and move him to room 2. Take the guest currently in room 2 and move him to room 4. The guest in room 3 gets bumped to room 6, and so forth. The guest in room N gets bumped to room 2 × N. Now take all the new guests and put them in the odd-numbered rooms that have just opened up.

Infinity × 2 is still infinity. There are just as many even numbers as there are natural numbers, and there are just as many odd numbers as there are natural numbers. If you combine the set of the evens with the set of the odds, you get a set that’s no larger than either of the sets you started with. If an infinite number of new guests show up at the hotel, you can accomodate all of them.

Actually that’s not always true. I’m being lazy and using words poorly. The infinite hotel can only accomodate a *countably* infinite number of guests, now or in the future. If an uncountably infinite number of guests show up, you’re screwed and most of them are going to end up sleeping on the street. But never mind that for a moment.

If this surprises or disturbs you, you’re in good company. Galileo, after pissing off the church and being sent into exile for being inappropriately right, accidentally discovered one day that there are as many perfect squares as there are integers. This surprised and disturbed him very much, and he quietly and probably wisely decided not to make a big deal of it.

Now imagine the same hotel, same situation, all rooms are full, and an infinite number of Infinity Tour Buses all show up at the same time. The tour buses are numbered 1, 2, 3 and so on forever, and each of the buses has an infinite number of passengers sitting in seats 1, 2, 3 and so forth.

The desk manager can still accomodate all of them by taking all the guests in room N and moving them to room 2 × N, then putting each of the new guests in room P^{S}, where P is the (B+1)-th prime number, B is the bus number, and S is the seat number. Work it out on paper if you have to, but you’ll see that all the passengers will be accomodated and none of them will end up sharing a room with any of the old guests or any of the other passengers on any of the other buses.

Infinity squared is still infinity. Each passenger can be thought of as a rational number, with the bus number in the numerator and the seat number in the denominator, and there are as many rational numbers as there are natural numbers. There are also as many prime numbers as there are natural numbers. So this is really the same problem as the previous one, where an infinite number of people showed up on foot, but with slightly trickier math for the desk manager. Poor guy.

But not all infinities are the same.

There are, for example, more real numbers between 0 and 1 then there are natural numbers from 1 to infinity. There are more real numbers between 0 and 1 than there are even numbers, odd numbers, rational numbers, prime numbers, perfect squares, or all of these put together.

I’d lay out the proof here, but there’s a wonderful proof on the Wikipedia. It’s called the diagonal argument, and it was invented by Georg Cantor, who also invented many of the other concepts we now use to talk about infinity and infinite sets. The gist of it is this: two infinite sets are considered the same size (technically the same “cardinality”) if you can map each element of one set to an element of the other set with none left over on either side (technically called a “bijection”). That’s why there as many even numbers as there are natural numbers: you can map one to the other with the function F(N) = 2 × N, and you’ll hit all of them eventually. Mapping the rationals to the natural numbers is a little trickier, and mapping the primes is even trickier, but both are doable.

But mapping the real numbers to the natural numbers is not doable, because no matter how hard you try, there will always be reals left over. That’s what Cantor’s diagonal argument proves. Mathematicians express this by saying that the natural numbers are countable, but the reals are uncountable. They have a name for the size of the set of natural numbers: “aleph-null”, written as ℵ_{0}. There are ℵ_{0} natural numbers, ℵ_{0} even numbers, ℵ_{0} odd numbers, ℵ_{0} prime numbers, ℵ_{0} rational numbers, and ℵ_{0} perfect squares.

But there are ℵ_{1} real numbers. ℵ_{1} is, pardon the pun, infinitely larger than ℵ_{0}. Asking exactly how much larger is a good way to get mathematicians to swear at each other, and combined with a few rounds at the bar, can lead to predictably disastrous results. There is something called the continuum hypothesis that states that ℵ_{1} = 2^{ℵ0}. Cantor tried in vain to prove this, but never succeeded. In 1940, several decades after Cantor’s death, Kurt Gödel proved that the continuum hypothesis could not be disproven. In 1963, Paul Cohen proved that it could not be proven either.

As you might expect, there’s more to it than that, but you’ll have to get a real mathematician drunk to hear the gory details. I’m all tapped out.

## Older posts

[12/03/2003] Cantor sets » There are an infinite number of points in the Cantor set. There are also an infinite number of points within the original line segment which are not in the Cantor set. Both of these numbers are equally large, and both are as large as the number of points in the original line segment. (442 words, 39 comments)

[12/01/2003] Aggregator usage is a power law too » Look ma, a power law. Let’s do that thing again, the one where we all bicker in predictable ways. (246 words, 45 comments)

[11/29/2003] Thanksgiving 2003 » They brought babies. (4 words, 4 comments)

[11/28/2003] No use » "He’s of no use anymore," the son thought to himself. (213 words)

[11/27/2003] The way out » This guy’s walking down a street, when he falls in a hole. (144 words)