Mfcttrf

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 rellocate infinitely many times, but what's the problem?

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:Xrightarrow 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:Xrightarrow X$ is an injection but not a surjection. Pick $xin Xsetminus ran(f)$. Then it's a good exercise to check that $xnotin ran(fcirc f)$, $f(x)notin ran(fcirc f)$, and $xnot=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(fcirc 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:Xrightarrow X$ is such that for each $xin 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:Xrightarrow X: xmapsto l_x.$$ And if $X$ has some additional structure we might be able to be even more broad: for example, when $X=mathbbR$ 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 $xin mathbbR$. For example, the function $f(x)=xover 2$ would yield $f^infty(x)=0$ under this interpretation (even though it isn't eventually constant).

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!)

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 $mathbbN$ 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.

As described, each person would move infinitely many times too. There's a popular alternative where the person in room $nge1$ moves to room $2n$.