Hilbert's hotel: why can't I repeat it infinitely many times?

I was wondering about the following:

Suppose a new guest arrives and wishes to be accommodated in the hotel. We can (simultaneously) move the guest currently in room 1 to room 2, the guest currently in room 2 to room 3, and so on, moving every guest from his current room n to room n+1. After this, room 1 is empty and the new guest can be moved into that room. By repeating this procedure, it is possible to make room for any finite number of new guests.

However, if we have an infinite amount of guests, why can't we just say that each guest follows this procedure? Everyone would have to relocate infinitely many times, but what's the problem?

Solution 1:

Keep in mind that Hilbert's Hotel is really just an analogy for analyzing countable and uncountable sets, i.e., deciding whether we can construct a bijection from $\mathbb{N}$ to a given set.

If you insist on staying within the analogy, here's the issue with telling everyone to move "infinitely many times." As a hotelier, you need to have a list of who is each room. Similarly, each of your (very accomodating) guests, needs a specific room number to move to. If a guest is in room #1, telling them to move to room #2 (or room #37 or room #123094871230948172 or ...) is a well defined operation. While it may be a long walk, they can get to that room in finite time and know exactly where they are headed.

On the other hand, telling the guest in room #1 to keep walking down the hall until they seem a room that has a number larger than any natural number on the door is ill-defined. There is no way that they could possibly reach this room by walking down the hallway. In effect, you have told them "I don't actually have a room for you, but you are welcome to spend the rest of your life walking down the hallway trying to find one!" This sort of behavior by hotel management is generally frowned upon and leads to poor online reviews of the establishment.

Solution 2:

Hilbert's hotel (HH) is only a metaphor, and when pushed too far it can lead to confusions. I think this is one of those situations: the key point is "we can't obviously compose infinitely many functions," which is pretty clear, but it's obscured by the additional language.

The point of HH is to illustrate how an infinite set (the set of rooms) can have lots of maps from itself to itself ("person in room $n$ goes to room $f(n)$") which are injective ("no two different rooms send their occupants to the same room") but not surjective ("some rooms wind up empty"). Note that already we can see an added complexity in the metaphor: the statement

There is a set $X$ and a map $f:X\rightarrow X$ which is an injection but not a surjection

has only one type of "individual," namely the elements of $X$, but HH has two types of "individual," namely the rooms and the people.

Now let's look at the next level of HH: getting an injection which is far from a surjection. Throwing aside the metaphor at this point, all that's happening is composition. Suppose $f:X\rightarrow X$ is an injection but not a surjection. Pick $x\in X\setminus ran(f)$. Then it's a good exercise to check that $x\not\in ran(f\circ f)$, $f(x)\not\in ran(f\circ f)$, and $x\not=f(x)$.

What does this mean? Well, when we composed $f$ with itself we got a new "missed element," so that while $ran(f)$ need only miss one element of $X$ we know that $ran(f\circ f)$ is missing two elements of $X$. Similarly, by composing $n$ times we get a self-injection of $X$ whose range misses at least $n$ elements of $X$.

At this point it should be clear why we can't proceed this way to miss an infinite set: how do we define "infinite-fold" compositions? This is what the question "where should the guest in room $1$ go?" is ultimately getting at.

It's worth pointing out that there are situations where infinite composition makes sense. Certainly if $f:X\rightarrow X$ is such that for each $x\in X$ the sequence $$x,f(x),f(f(x)), f(f(f(x))),...$$ is eventually constant with eventual value $l_x$, then it makes some amount of sense to define the "infinite composition" as $$f^\infty:X\rightarrow X: x\mapsto l_x.$$ And if $X$ has some additional structure we might be able to be even more broad: for example, when $X=\mathbb{R}$ we can use the metric structure (really, the topology) and make sense of $f^\infty$ under the weaker assumption that the sequence $$x,f(x),f(f(x)), f(f(f(x))), ...$$ converges (in the usual calculus-y sense) for each $x\in \mathbb{R}$. For example, the function $f(x)={x\over 2}$ would yield $f^\infty(x)=0$ under this interpretation (even though only one of the "iterating $f$" sequences is eventually constant - namely, the $x=0$ one).

But this is not something we can do in all circumstances, and you should regard the idea of infinite composition with serious suspicion at best. (Although again, there are situations where it's a perfectly nice and useful idea!)

Solution 3:

You can do an infinite number of reshufflings provided that, after all of them, every guest has a room number.

Your proposal of shuffling every up one does not work for this, because if each step is to shuffle everybody up one than nobody ends up with a room number (everyboby moves up one an infinite number of times) and the hotel becomes empty.

So you need a slightly more subtle approach.

One might be on the $m$th arrival to take everybody in rooms of the form $2m+k$ (for non-negative integer $k$) and move them to room $2m+k+1$ putting the new arrival into the available room $2m$, leaving those in rooms $1$ through to $2m-1$ unmoved at this step. After an infinite number of steps, the room arrangement would be:

Room    Original position    
 1        Room 1
 2        1st arrival
 3        Room 2
 4        2nd arrival
 5        Room 3
 6        3rd arrival 
etc.      ...

and this works even for an infinite number of steps; everybody gets a room number. You might have saved time by moving the original occupants directly from room $n$ to room $2n-1$ and then filling the infinite number of empty rooms with the new arrivals.

With a more subtle approach you can even cope with a countably infinite number of coach arrivals where each coach has a countably infinite number of passengers.

Solution 4:

If you allow people to move infinitely many times, there is no need to have an infinite hotel in the first place. Say you have a two-room hotel which is full: person A is in room 1, and person B in room 2. Now C arrives. No problem! Put C in room 1 and tell A to move to room 2. Then when A gets to room 2, tell B to move to room 1. When B gets to room 1, tell C to move to room 2, and so on.

Of course, you haven't really accommodated three guests, because none of them ever stops moving and actually gets to stay in one of your rooms. The same applies to your infinite example.