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 .

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 = + 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.