I'm gunna have to be one of those people that says "really? O_o" when presumably everyone else clearly grasps the concept.

I get that if you had an infinite number of rooms, and an infinite number of guests staying, you still have room for an infinite number more guests.

But in your example, surely "occupied" is, more than just an indicator of another guest, a state of the room. You have an infinite number of occupied rooms, but zero unoccupied rooms, so no space for more guests.

You need to go and read up on the transfinite numbers. Swizec is talking about what happens when you deal with a certain sort of infinity (a countable infinity) where there's a one-to-one mapping between the hotel rooms and the numbers.

In the transfinite numbers things that at first seem unintuitive happen, e.g.:

1. There are the same number of integers as there are even numbers. And there are the same number of integers as there are odd numbers.

2. There are the same number of rational numbers (fractions) as there are integers.

3. There are more real numbers than integers.

Here are some interesting questions on the Hilbert hotel which boggles my mind. Shortly, If you can keep as many rooms as you wish unoccupied, can you still claim your hotel is full?

(1) Example, if you can move everyone from N to N+1 or (N+5); and get an unoccupied room for new reservations, can you still claim anyone that your hotel with infinite rooms is fully occupied?

(2) Or is a fully occupied infinite-roomed hotel an oxymoron, or a self-contradictory dasein; which can not exist upfront?

(3) Or is it better to call an infinite-roomed hotel both fully occupied and fully available, a superposition of both predicates, or un-predicatable?

I think the mathematical definition of 'the hotel is full' would be 'there is a one-to-one correspondence, also called an isomorphism, between the hotel rooms and occupants'.

So, if the hotel has empty rooms, even if there are an infinite number of occupied rooms it is not 'full'.

On a side note: no matter how many occupants there are in the hotel one might argue that it was also 'empty' given that it can always accommodate a countably infinite number of new arrivals.

Honest question here; is the phrase "same number of X and Y" equivalent mathematically to "the cardinality of X and the cardinality of Y are the same"? I was taught "no", since "number of" doesn't apply to any of the infinities.

But perhaps I was taught incorrectly, or I have misremembered.

Well, Cantor's big thing was partly that he extended cardinality to infinite sets (http://en.wikipedia.org/wiki/Cardinal_number). The first infinite cardinal \aleph_0 is the cardinality of the natural numbers.

There are many very entertaining discussions of "Hilbert's Hotel" online. I look them up once or twice a year for teaching my math classes. To answer your very pertinent question, I suggest looking at

http://opinionator.blogs.nytimes.com/2010/05/09/the-hilbert-...

for an illustrated, and I think illuminating, discussion of what to do if countably infinite buses, each with countably infinite passengers, drive up to Hilbert's Hotel with infinite rooms, each of which is already full.

The classic approach is to move all the existing guests from room n to n+1 and put the new party in room 1.

I can see how that works if you have an infinite number of rooms and an infinite number of guests, because you still have an unoccupied room to move them up into. But how does that work when you've stated that all rooms are occupied?

I'm really struggling to square up my understanding of how the former problem works with my intuition that if every room is in an occupied state, you can't magic up some in an unoccupied state.

> I'm really struggling to square up my understanding of how the former problem works with my intuition that if every room is in an occupied state, you can't magic up some in an unoccupied state.

That's the problem with infinites. Consider the number of all positive integers. Let's call it a1.

Now consider the number of all even positive integers. Let's call it a2.

Each even integer can be directly mapped to an integer and the other way around by multiplying or dividing by 2, right? All integers can be multiplied by 2, and all even integers can be divided by 2.

So a1 = a2, the number of integers is the same as the number of even integers, even though you'd intuit the number of integers to be twice the number of even integers.

Just as it does when reaching the infinitely small (0.999… is precisely equal to 1), intuition breaks down when reaching into the infinitely big.

Your intuition is correct. The hotel paradox is a trick of symbolic manipulation, and the analogy to a real hotel is an amusing deceptive misdirection.

  > Your intuition is correct. 

No, the intuition is not correct.

  > The hotel paradox is a trick of symbolic manipulation,
  > and the analogy to a real hotel is an amusing deceptive
  > misdirection.

No, it's a visualization to help people understand about matchings between infinite sets. It's an accurate analogy.

Aren't there already guests in room n+1?

Right, so the occupants of n+1 would have to move to n+2, the occupants of n+2 would have to move to n+3, and so on. Somewhere, the occupants of n+infinity-1 and n+infinity would have to share a room, but I guess everyone accepts this issue because you'd never actually reach rooms n+infinity-1 and n+infinity by counting/visiting.

I'm no mathematician, but this seems to be an edge phenomenon that everyone is willing to ignore. I suppose you could just as easily tell the new guests to run down the hallway until they find an empty room at the end; out of sight, out of mind...

Infinity is not a number.

There is no room 'n+infinity'. There's just not such a room, anywhere, even in principle. Each guest n can move to room n+1 because the guest there is moving to n+2. This works. That's the point.

And you couldn't, in fact, tell the guests to run down the hallway to find an empty room: There is no empty room until you move everyone.

Infinity is counterintuitive, you say? Well, yes, that's the point of this illustration.

"Infinity" may not be a number, but omega is a number, and it is transfinite. Omega is the first transfinite ordinal.

You are certainly correct, however, that Cantor's hotel does not need to have any rooms with transfinite room numbers.

Not just counterintuitive, but counterfactual and counterphysical. You can't "do it", you can only "model it in the realm of formal mathematics", which by the way proves that this model is not a model of reality, and infinite hotels cannot exist in physics. If you push the physical analysis further, you can get into the speed of light and bosons.

You certainly can't have infinite hotels in physics, but it would be incorrect to assert that we have any good reason to believe that infinite quantities can't exist in nature. For instance, the model of the universe most widely accepted by cosmologists today implies an infinite universe, assuming that our measurements of the curvature of space are correct. And these cosmologists don't believe that these infinities are just a mathematical artifact. Rather, they believe that the universe is likely to be infinitely large, in actuality.

Yes. The statement as given doesn't work out. If you say "an infinite number of guests and an infinite number of rooms" it works. But when every room is endowed with the property of being occupied there is no room for more guests.

No, the problem was phrased correctly. What we are saying is that for each natural number n, room n is occupied by a guest. This is the mathematical idea embodied by "an infinite number of occupied rooms". If you say "an infinite number of guests and an infinite number of rooms", then the question becomes obvious and trivial.

What makes it interesting is that we really do mean that every room is occupied to begin with. The surprising result is that we can in fact add another guest by having everyone move over one room, even though we started out with every room occupied. And in fact, we can add infinitely many new guests by telling everyone to move to their room number \* 2.

It brings up an interesting point, though. If I have an infinite number of rooms and an infinite number of guests, then one might intuit that every room is occupied.

There is a mapping of every guest to a room: guest n is in room n. Yet somehow there exists a room that has no guest, despite being able to model both rooms and guests with the same infinite set.

There is no empty room initially. However, by having all guests move simultaneously, you can make one room free without having any guest leave the hotel.

Incidentally, this is one way to define infinite sets. A set is infinite if and only if there exists a proper subset that has the same size (cardinality).

That's the sort of thing that happens when semantics meets mathematics; Swizec screwed up his statement of the problem. Swizec and the people agreeing that the answer is yes are confusing the problem's literal statement with the common statement of similar problems.

I am thoroughly confused as to what your point is. What is the problem with Swizec's wording in your view? Should s/he have written "Can you make room for more guests?". I agree that you could argue that right now there is no room free, and that the answer should be No because of that. However, given that you can easily make one room free by having every guest go to the next room, that just seems overly nit-picky to me, and like you are intentionally trying to miss the point.

The difference is an infinite number of rooms can accommodate an infinite number of guests and still have room for one more. An infinite number of full rooms can accomodate no more guests. They're all full by definition.

That is, unless I am also thoroughly confused.

>That is, unless I am also thoroughly confused.

You are, but that's OK; they call it a "veridical paradox" for a reason.

The part that makes the assertion false is "...all of which are currently occupied." Moving n to n+1 only works when that restriction is lifted.

No, because the people in n+1 simultaneously move to n+2. (and so on)

No, those guests now stay in room n+2.

I don't get it. Can't I just as easily say that n+2 is also occupied? After all, they're all occupied by definition, aren't they?

For example. All blocks are either red or blue. You have an infinite number of blocks that are all red. Do you have any blue blocks? No. Where is the mistake in my logic?

>Can't I just as easily say that n+2 is also occupied?

No, because the former occupants of n+2 are now in n+3.

You do it for all natural numbers n=1, 2, 3 , ... (those are countably infinately many numbers).

Because every natural number n has a successor n+1, you can do it for all of them.

Each n except 1 has a predecessor n-1 from which guests where moved to n. Nobody moved into 1, therefore you can put the new arrivals there.

After that, there are still (countably) infinite many guests. They are just matched up differently with the rooms/numbers.

Because you have infinitely many rooms, you were able to accomodate one more by matching them up differently. That's sort of the point :-)

You cannot move someone to a full room. All of the rooms are full. Explain that part.

I think nhaehnle explained it very nicely.

n+2 was occupied, but it's not anymore because you moved them to n+3.

no, n+3 is also full. See? Why do you get to win that back-and-forth and not me? After all, the problem stated that all rooms are full, even N+3, 4, 5, etc. Why do you get to construct a new room without also constructing a new pre-existing occupant?

You don't have to do that. Just use following simple steps (assuming that the hotel rooms are all along one infinitely long corridor):

1. Have all guests of the hotel simultaneously pack their things and move out of their room onto the hallway.

2. Have all guests simultaneously move along the hallway to be standing in front of the room next door (in the same direction, obviously).

3. Have all guests simultaneously move into the room they are now standing in front of.

The first room is now empty, with nobody having had to leave the hotel, and every guest still has his/her own room.

Thanks. I can understand that.

You don't need a hallway as a holding area. Everyone in the hotel simultaneously moves one room up. Talking about it sequentially as "1 moves to 2 and 2 moves to 3 etc." is convenient for describing it, but the process does not actually happen sequentially; otherwise it would take an infinite amount of time. But since each person is capable of moving at the same time, and since their movements need not interfere with each other, the whole process can happen instantly.

If you are visualizing a traditional hotel, then this means that everyone walks out of their room into the hallway and then moves one door down. But the hallway is irrelevant. The rooms could instead be directly connected by doors, and everyone would still just simultaneously move to the next room. No holding area needed.

One more question. What if the rooms are not in an infinitely long hallway (with or without interconnecting doors), but a ring of infinite circumference? Or is there such a thing?

It depends on what you mean by "ring of infinite circumference", because you're going to have to discard some conventional ideas associated with a "ring" in order to make the definition work. If you just mean "the rooms extend infinitely in both directions", then yes, the same reasoning applies; we'll just have an arbitrary "room 0", and then "room -1" on one side and "room 1" on the other. Then you tell everyone in a negative room to move to room n-1 and everyone in a positive room to move to room n+1.

However, this definition does away with the idea of a ring meeting itself on the other side. We cannot say that "room -∞" is the same as "room ∞" for example, because there neither of those rooms actually exist.

When dealing with infinities you need to be really precise, and very careful. When you ask about "a ring of infinite circumference" I have to ask - what do you mean by that? The only thing I can think of that's related is a "circle if infinite radius", but the usual interpretation of that is a straight line. Then we're back to an infinitely long hallway.

So - what do you mean?

That's kind of my question. Is there a logically consistent concept of an infinite ring where the "first" room is moved into by the "last" occupant, therefore making the problem dependent on the configuration of the rooms? Or is such a thing inherently finite?

It's very much a case of "it depends".

Firstly, the whole point of the hotel story is to talk about addition of cardinals. You are moving off topic and to some extent "bike-shedding" - discussing something other than the real point.

In particular, if there are infinitely many rooms then you must be able to create an embedding of the counting numbers into it. Regardless of whether or not that accounts for all the rooms, you then have an infinite chain, one without a concept of a "last room".

It is possible to have infinitely many cycles, and in those cycles the "last room" is followed by the first room, but there are infinitely many of these cycles, so we can order them in a different way, and we get back again the infinite chain with no "last room".

And this matters. We say that two sets are the same size if we can create a matching between them, and we say they are of different sizes of there is no matching. Be careful. Just because your first attempt at a matching doesn't work, that doesn't mean there isn't one. So in this case of the infinite number of rooms, just because one arrangement seems not to work, that doesn't mean that no arrangement will work.

And indeed, the very definition of the number of rooms being infinite means there is a way to arrange the movements of the existing guests to ensure that there are no "last room" problems.

Thanks. Great explanation.

Yes. They must move to room n+2.

But how do you get a situation where there is one more room than occupants, if both are infinite and matched up?

You rematch. Mathematically, not physically! There isn't' "one more", all finite differences between infinite sets are equivalent to each other, including zero.

Ponder this if you will: how did the hotel get full in the first place? if you assume that is possible, then you can reverse the original room assignments, and reassign rooms.

The source of your confusion is that you trusted the problem is even possible to set up, without availing yourself of the power that the setup implies.

The mixing of the possible with the impossible is certainly jarring.

Infinity is one of those things that makes little sense to people who are not mathematicians.

Cantor's diagonal argument is something else that I get caught up on.

(http://en.wikipedia.org/wiki/Cantors_diagonal_argument)

An explanation of why it's hard:

(http://rjlipton.wordpress.com/2010/01/20/are-the-reals-reall...)

I'm assuming that you have a hotel with a countably infinite number of rooms all of which are occupied. In that case you have room to accommodate a finite or countably infinite number of new arrivals.

    a hotel with an infinite number of rooms, all of which are currently occupied

So you have an infinite number of occupied rooms. That is, you have a one-to-one mapping between rooms and parties.

Do you have room for more guests? I don't think so, because none of the rooms are unoccupied. You could try to free up some space by consolidating parties, though.

You don't have to consolidate, just move people: move the occupants of room n to room 2n and now you have infinitely many empty rooms (all the odd-numbered ones).

... which would consolidate the occupants of rooms n and 2n (and there are people in room 2n to begin with, if all of the rooms are indeed currently occupied).

edit: I see that the folks in 2n would now be in 4n, and so on down the chain. You'd always have some guests that are in the process of being evicted (i.e. between rooms); then again, that's negligible because we're not talking about real life (™). Clever!

If you move every guest from n to 2n, all of the odd rooms will open up, and you have room for a countably infinite number of new guests.

I believe David Hilbert was the first to describe this paradox. Source: http://en.m.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Gr...