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 accommodate 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 accommodate 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 accommodate 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 accommodate all of them.

Actually that’s not always true. I’m being lazy and using words poorly. The infinite hotel can only accommodate 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 accommodate 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 PS, 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 accommodated 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.

§

Fifty two comments here (latest comments)

  1. Thanks!

    If I understand, this says that integers (1,2,…) are infinite in one way because they can keep on going.

    And reals (1.35345346, 1.45645, etc) are infinite in this way, but also infinite in *another* way because they can keep on dividing.

    (integers aren’t infinite in the dividing way, because there’s a limit to the ways you can divide integers and still get integers).

    And the names of the ways are countable (ℵ0) and uncountable (ℵ1).

    Is there an ℵ2?

    — Lloyd Dalton #

  2. Do each of these infinite hotel rooms have a mini-bar? Assuming they do- this being the Infinite Hotel, there’s probably an infinite number of miniture bottles of whiskey in each minibar. If I get a mathematician drunk in order to hear the gory details, and in the process burn through a dozen or so miniature bottles, how will the hotel be able to charge me for them? If they count them, they’ll still find an infinite number. They also can’t check for empty shelf space… I’ll be sure to move the bottle in slot 13 to slot 1, the bottle in slot 14 to slot 2….

    My head hurts and I haven’t had a drop to drink.

    — Jason Clark #

  3. There is an ℵ2, and an ℵ3 (though I don’t think ℵ3 is useful for counting much, so ℵ4 and so forth don’t get talked about much). IIRC,ℵn is the set of all possible subsets of a set in ℵn-1, so ℵn is defined nicely for any integer.

    I believe ℵ2 contains the set of all possible curves, and its cousin the set of all possible reasonably normal functions. I can’t recall any proof of that though, so I could be remembering things completely wrong.

    — jacob #

  4. Dichotomy's Purgatory (trackback)

  5. Lloyd is correct, Jacob is correct, and I suppose Jason is also correct, although the process of hiding the evidence in his infinite mini-bar is called a supertask, since it requires an infinite number of steps in a finite time. (Moving the hotel guests around to accomodate newcomers is also a supertask, unless you want the newcomers waiting around forever.)

    We’re off to a roaring start.

    — Mark #

  6. Have you read Rudy Rucker’s _White Light_, in which the narrator’s soul, on a journey to the place where zero and infinity meet, takes a stop at the Hilbert Hotel and has coffee with Georg Cantor in the lobby?

    It’s a wonderful fictional treatment of the wonderland beyond alef-null.

    — Lisa Williams #

  7. So x1 = 2^x0 is god? More! More!

    — Huck #

  8. I’ve always liked this discussion. Hilbert’s Hotel is one of those “no-one believes it at first” sorts of topics, I think.
    Minor correction, although I might be wrong, and if I am you can mock me mercilessly: the continuum hypothesis states that there is no set with a cardinality between ℵ0 and ℵ1, rather than that ℵ1 = 2^ℵ0, i.e., there’s not a “number” in between the two alephs. Of course, if we run off into Gödel in the next post I’m gonna stop understanding it, but hey.

    — sil #

  9. Re: “And the names of the ways are countable (ℵ0) and uncountable (ℵ1).”

    “How do I love thee, let me count the ways…oh, I can’t, because they are uncountably infinite.” Heh. A Valentine’s Day message for those of you with mathematically-aware partners, perhaps. :)

    — sil #

  10. Jacob,

    Aleph-n is *not* necessarily the set of all possible subsets in aleph-(n-1). This is the “generalised continuum hypothesis” and, like the basic continuum hypothesis (aleph-1 = set of all subsets of aleph-0 (or equivalently, the set of reals)), GCH is neither provable nor disprovable within standard set theory. You can come up with different “models” that satisfy all the axioms of set theory, and in some of them CH/GCH will be true and in others CH/GCH will be false.

    Sil,

    Aleph-1 is defined as the first cardinal after aleph-0, so by definition there is no cardinality between aleph-1 and aleph-0. The continuum hypothesis is that there is no cardinality between the set of integers and the set of reals i.e. 2 ^ aleph-0 is the first cardinal after aleph-0 i.e. 2 ^ aleph-0 = aleph-1.

    Next stop, the large cardinals, the ones that can’t even be proven to exist: inaccessible cardinals, the subtle cardinals, the ineffable cardinals and the magnificently named “totally indescribable cardinals”… I love infinities…

    — Ivan Towlson #

  11. Sil, I think the two statements of the continuum hypothesis are equivalent. (No promises though.)

    — Matthew #

  12. “I?ve always liked this discussion. Hilbert?s Hotel is one of those “no-one believes it at first” sorts of topics, I think.”

    I strongly disagree
    No-one understands it at first. Or second. Or third. Possibly some Nth time later they understand it. Then comes the disbelief.

    — Sparticus #

  13. Flatlander (trackback)

  14. I really enjoyed reading that. Thanks, Mark!

    — Anonymous #

  15. So, since you brought Gödel up, I’m going to tell one of my favourite Gödel related anecdotes so that one of the people who actually knows what they are talking about can tell me I’m wrong. Apparentley, Gödel was both very logically inclined, as you might expect given his line of work, and also very antisocial. In fact, he supposedly hated meeting people and would go to extreme lengths to avoid seeing people he did not wish to. Applying logic to the problem, he realised that the only way to ensure that he did not see someone who wanted to meet him was to make a definite arrangement of a time and place to meet, and then studiously avoid being anywhere near the specified place at that time by, for example, staying in his office instead.

    — jgraham #

  16. Anybody who enjoys reading stuff like what Marks been presenting us, should consider getting one of Smullyan’s Books. He has a couple of them where he talks about Logic, Infinity etc. in short stories and lots of riddles to choose, of course you can look up the solutions at the end of the book, but who is going to do that, since it takes out all the fun… *G*

    Here’s a link to one of them:

    http://www.amazon.com/exec/obidos/tg/detail/-/0679406883/

    (Don’t know if Mark has an amazon-id to use? Feel free to adjust if you do.)

    — Sencer #

  17. i am sparticus v11. Sheep Everywhere (trackback)
  18. Lost Boy (trackback)
  19. Cranky Dan (trackback)

  20. This story come from this book:

    http://www.amazon.com/exec/obidos/asin/0393003388

    Which I would highly recommend

    — Anonymous #

  21. This argument is only possible if you have an infinite number of desk managers with an infinite amount of patience!

    Do you realize how long it would take the average hotel employees to swap all those rooms! And the fuss the visitors would put up! I’m sorry, there is just no way this could happen. Israel and the Palestians will make up and kiss long before all those rooms are swapped.

    — Jeff #

  22. Douwe Osinga's Blog (trackback)

  23. “Infinity +1″ is a meaningless term and cannot be used to prove the point. “Infinity + 1″ is more akin to “refridgerator + 1″ than “5 + 1.”

    Yet somehow when me and my two friends got our money back for the 3 cameras we bought, the delivery boy made a $5 gain out of thin air. Maybe we shouldn’t have stayed at that hotel.

    — SteveD #

  24. A Father and his two girls (trackback)
  25. Elwing's weblog (trackback)

  26. there was a charming little educational tv programme late one night on the BBC (part of the Open University programmes) about the Hotel Infinity.
    I think part of its script was based on this http://www.c3.lanl.gov/mega-math/workbk/infinity/inhotel.html

    — Patrick H. Lauke #

  27. Infinitely interesting.

    — Jesper #

  28. “Galileo, after pissing off the church…”

    For some reason, this put some weird imagery into my head–that is, Galileo standing atop a church building and, well, pissing. (Which, I suppose, would be pissing off the church in more than one way.)

    — Greg H. #

  29. Here’s a question about supertasks: what if you have an infinite amount of time? Is it still called a “supertask”, or does it get a new name?

    I’m serious, and here’s why: as a Buddhist, I believe in beginningless time, and that each of us has had “countless” (infinite? countably infinite or ℵ1? that’s a bit over my head …) previous lives. I had this argument with a Christian in an airport who said that because infinity of any kind is uncountable, beginningless time is impossible. My counter-argument is that infinity is only uncountable in finite time, but given infinite time you could count, say, all the whole numbers. Similarly, given infinite time you could live every moment of infinite lives.

    I didn’t convince him and he didn’t convince me.

    Anyone care to comment?

    Thanks in advance …

    — Anonymous #

  30. “Galileo, after pissing off the church and being sent into exile for being inappropriately right,”

    Perhaps a bit of an oversimplification. Galileo wanted to push a scientific debate at the time (which the Church had no problem with) into the theological realm and was rather antgaonistic about it. More details at http://catholic.com/library/galileo_controversy.asp

    — Scott B. #

  31. Couple of BBC radio programmes well worth listening to:
    http://www.bbc.co.uk/radio4/science/5numbers.shtml
    http://www.bbc.co.uk/radio4/science/another5.shtml

    very interesting, including one on infinity that fits nicely in with your post here.

    — David House #

  32. #29: even if you had an infinite amount of time, you would never ‘reach’ infinity. You could spend all your time from here to ℵ-null counting higher and higher, but would still be in the realm of finite, because you’d never *get* to ℵ-null.

    Speaking of “really frickin’ huge, yet finite:”

    http://www-users.cs.york.ac.uk/~susan/cyc/g/graham.htm

    To quote Yudkowsky, (who’s referenced on that page,) “This number is far larger than most people’s conception of *infinity*. I know that it was larger than mine.”

    — kami #

  33. brethorsting (trackback)

  34. Re the first problem (adding 1 guest to an infinite hotel), couldn’t you just add the new guest to room N0 + 1 (copy/pasting Aleph-null doesn’t work, doesn’t display properly when previewed, btw)?

    Or is this not commutative with having the guest in room 1 move to room 2, and domino-ing the rest upward, to move the new guest to room 1?

    I suppose N0 is not really a room number?

    — Mark Szpakowski #

  35. Amateurs, the lot of you. Just sign up for a sophomore-level mathematical structures class and you’ll cover all this in a week or two. Infinity is not nearly as exciting as non-mathematicians seem to think it is.

    — Anonymous #

  36. Quarter Life Crisis (trackback)

  37. re: “Just sign up for a sophomore-level mathematical structures class…”

    Beware the word “just”.

    — Mark #

  38. Quarter Life Crisis (trackback)

  39. #34: to write ℵ0 in your comments, use this fragment of HTML:

    &#8501;<sub>0</sub>

    but for some reason Mark’s comments system strips out the <sub> and </sub>, so you’ll have to settle for the non-subscripted version as in the first line of this comment.

    — Anonymous #

  40. There is an infinite number of comments. One more person posts. Server explodes.

    — hao2lian #

  41. #40: or not, 1+infinity = infinity ;)

    — David House #

  42. Any chance this hotel is owned by an airline? I’ve been on many a flight where the seats have been reserved based on these exact calculations.

    — B. Johannessen #

  43. Infinity is a concept, not a number. So “infinity + 1″ is about as logical as saying “barbecue + 1″.

    — Anonymous #

  44. Re: #43. It’s a colloquial way of saying “for 2 sets A and B, if |A| = ℵ0 and |B| = 1, then |A ∪ B| = ℵ0.”

    — Mark #

  45. “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.”

    Moral: if you are discrete, you will get a room.

    — Moss Collum #

  46. I’ve always had a big problem with the Hilbert Hotel scenario. It makes an invalid assumption, that the exchange of rooms are instant. This isn’t a problem when you just have one new guest, but it becomes a problem with the infinite number of new guests. I don’t consider the problem solved until EVERY guest gets a new room, and it would take an infinite amount of time to relocate an infinite number of guests, they can never be relocated fully within any finite time. That’s the whole reason for Cantor’s convoluted relocations, you can’t just tell the one new guest to check into Room Aleph+1, it would take him an infinite amount of time to get there. But you can tell the guy in room Aleph to go to Room Aleph+1, it takes him the same amount of time as it takes to move between Rm 1 and Rm 2. But I’m probably wrong on all this because cardinal infinites is not my specialty.

    Anyway, as Lisa (and I) have previously mentioned, you gotta read Rudy Rucker’s “White Light,” which partly takes place in Hilbert’s Hotel. He has an interesting solution to my objection, but I still don’t buy it.

    And now I’m going to make Lisa jealous, by telling her I own one of the infamous 100 preprint copies of White Light, it includes a cover letter by Bruce Sterling telling everyone to read this crazy new author.

    — Charles #

  47. I remember telling my (now spouse but then) boyfriend about a cartoon with two cats in an alley and the caption “if I had two dead rats I’d give you one…” He immediately replied “if I had an infinite number of dead rats, I’d give you an infinite number of dead rats … and I’d still have an infinite number of dead rats.”

    His explanation: “label the rats 1, 2, 3, 4… you take the odds, I’ll take the evens.”

    Ah, geeks in love.

    — Ann Maria Bell #

  48. Tin Ear | Blog (trackback)
  49. Tin Ear | Blog (trackback)

  50. accommodate

    — xiffix #

  51. Yes indeed.

    — Mark #

  52. A shame Douglas Adams never crafted a hotel like this to accompany Milliways.

    — Nick Douglas #

Respond privately

I am no longer accepting public comments on this post, but you can use this form to contact me privately. (Your message will not be published.)



§

firehose ‧ code ‧ music ‧ planet

© 2001-8 Mark Pilgrim