Wednesday, July 13, 2011

The Uncountable Hotel

This story is a follow-up to The Infinite Hotel.

David Hilbert had been getting quite some attention with his Infinite Hotel. Georg Cantor, a fellow mathematician who was always in for an impossible challenge, wondered if he could design an even bigger hotel. So that when it was completely full, there would be no way all those guests could ever fit in Hilbert's hotel. No matter what clever trick Hilbert would come up with (and as we know, he had quite a few of those).

So Cantor started to think. Hilbert's hotel had an infinite amount of rooms, each denoted by its own room number. The first was number 1, the next number 2, and so on — all the way to infinity. Basically, there was a room for every possible positive (whole) number. How could he design more rooms than that? Hmmm... what if, maybe, his hotel was to include rooms for all negative numbers as well? A list of all rooms would then go on indefinitely in both the positive and the negative direction! Surely he would then have twice as many rooms as Hilbert did.

Cantor soon realized it was not going to be that easy. Infinity times two? That's still infinity. Just arrange the rooms so that you can match them, and you'll see:

Cantor's Room Number 1-1 2-2 3-3 4-4...
Hilbert's Room Number12345678...

The idea sounded good at first, but the above shows that Hilbert's hotel would still be able to house every potential guest in Cantor's hotel. It doesn't matter if you change the labels on the doors; the number of rooms is still infinite.