"You own a hotel with an infinite number of rooms, all of which are currently occupied. A group of four guests comes and wants to rent a room. Do you have a room for them?"
The answer is that yes, you do in fact have room for infinitely more guests.
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.
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?
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.
No, because the former occupants of n+2 are now in n+3.
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 :-)
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.
That is, unless I am also thoroughly confused.
You are, but that's OK; they call it a "veridical paradox" for a reason.
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.
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).
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.
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...
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.
You are certainly correct, however, that Cantor's hotel does not need to have any rooms with transfinite room numbers.
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.
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.
(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?
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.
But perhaps I was taught incorrectly, or I have misremembered.
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.
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...)
a hotel with an infinite number of rooms, all of which are currently occupied
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.
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!
I believe David Hilbert was the first to describe this paradox. Source: http://en.m.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Gr...