Wednesday, April 22, 2009


Infinity plus one

John Tierney has included a series of amusing puzzles, recently, in his TierneyLab blog in the New York Times. This week’s has an aspect that I’d like to talk about a bit. Here’s a shortened version of the puzzle, removing the cutesy “Russell Crowe” stuff (go look at the original for the full version):

You arrive at a hotel with an infinite number of rooms, and no vacancy. Yes, despite the infinite number of rooms, they’re all full. Still, the desk clerk does some wangling, and finds a room for you, without throwing any existing guests out nor making then share rooms. How did he do it?

I like this one in part because it touches on the sort of stuff I talked about in October, when I covered countable and uncountable sets and the concepts of cardinality and infinity.

The answer that many readers got depends upon the axiom of choice and the assumption that the number of rooms is countably infinite, but that works for the puzzle — and one can make a more rigorous solution for a more general case. So, given those additional assumptions, here’s one way to free up a room:

  1. Because the rooms are countable and we have the axiom of choice, we can number the rooms with consecutive natural numbers starting at 1: 1, 2, 3, 4, ...
  2. Ask each guest to change rooms, moving to the room with the next higher number. The guest in room n will move to room n+1.
  3. Put the new guest in the now-available room 1.
It’s an amusing little demonstration of an aspect of infinite sets. It should be clear that we can repeat this a countably infinite number of times, thus fitting a countably infinite number of new guests into our already-full hotel.

Unfortunately, some people will understand it imperfectly and turn it into some attempt to do finite arithmetic on “infinity”, as commenter PolarBearNJ does (errors as in the original, but emphasis mine):

Well, this time I did some reading before answering...the puzzle is really a question of proving the following: n = n+1. Where N = infinity. How do we prove infinity plus one?

Some solutions suggest it means doubling up the guests temporarily, adding one guest to the first room, and the 2nd person leaves for the 2nd room, repeating this infinite room shifting...

Another solutions suggests it means moving the guest in the first room to the Hallway, and then moving into the 2nd room, forcing the 2nd guest into the Hallway, repeated to infinity...

Apparently, there is no answer that adequately proves n = n+1...but I would like to hear from the Math Wizards.

The problem with PolarBearNJ’s characterization is that “infinity”, as he’s thinking about it, is not a number; it’s a concept. It doesn’t make sense to talk about “infinity plus one” in the same way as “two plus three is five”. And not all “infinities” are the same, as we saw in my October series of posts.

But when we talk about cardinal numbers and the cardinality of sets, it becomes very clear, and it’s easy to see that the mapping f(n) := n + 1 defines a one-to-one correspondence between the set of natural numbers and the set of natural numbers except 1. Both sets have cardinality aleph-null.

And we can define “addition” on cardinal numbers:
Let a be the cardinality of set A, and b be the cardinality of set B. Define a + b to be the cardinality of the set A ∪ B.

So if N is the set of natural numbers and M is the set of natural numbers except 1, our mapping above (f(n) := n + 1) shows that |M| = |N|. But since N = M ∪ {1}, that means that |M| = |M| + |{1}|, or aleph-null = aleph-null + 1.

Which is sort of what PolarBearNJ was getting at, but not strictly the same thing. We should avoid talking about “infinity” as though it were a number.


Dr. Momentum said...

It bugs me that you might have to keep moving these poor hotel occupants every time a new guest arrives, so I just tell each occupant to double his room number and go to the corresponding even-numbered rooms. This leaves an infinite number of odd rooms that can accommodate any finite number of guests who subsequently arrive without moving people again!

Ruralmama said...

Just think of all the toilets!

? said...

The concept of infinity operates upon an all or nothing principle. In English, what you have done is simply added another room, however, and here is where the problem is; because infinity operates upon this all or nothing rule, that room that you added on was already included in the first place, making it occupied.
The fact that all of the rooms were filled, is actually not that surprising. All of the rooms must be filled or none of the can be filled. It would be impossible for only half of the infinite set of rooms to be filled, because there just is no such thing. Once again, infinity is NOT a number, it is simply a concept.
To restate, either all the rooms are filled or not, I'm sorry, you just can't have your cake and eat it as well. I'm sorry to the poor man who will have to do without a room, and I'm sorry, but this problem is wrong.

Barry Leiba said...

Yep, see: ? (who must have left the Mysterians at home) doesn't get the mathematics.

«It would be impossible for only half of the infinite set of rooms to be filled, because there just is no such thing.»

Oh, very-quite false. If you had a countably infinite number of rooms, numbered 1, 2, 3, 4, ..., and you only assigned a countably infinite number of people to even-numbered rooms, who is in room 1? 3?

But it's hard to grasp this. Read my other posts on it, and see if they help.

    Too many teardrops for one heart to be crying
    Too many teardrops for one heart to carry on
    Youre gonna cry 96 tears
    Youre gonna cry 96 tears