38
$\begingroup$

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?

$\endgroup$
  • 7
    $\begingroup$ I'm not sure that taking this metaphor too literally makes much sense. But if one could perform this manoeuvre "infinitely many times" where would the guest in room 1 end up? $\endgroup$ – Lord Shark the Unknown Sep 18 at 17:41
  • 26
    $\begingroup$ Under your thinking, the person who was in room $1$ ends up in what room? $\endgroup$ – Thomas Andrews Sep 18 at 17:43
  • 29
    $\begingroup$ Of course you can easily make room for an infinite number of guests relocating all the existing guests just once each. Move room 1 to room 2, 2 to 4, 3 to 6, … $n$ to $2n$, … and all the (infinite number of) odd-numbered rooms are empty. $\endgroup$ – alephzero Sep 19 at 9:32
  • 6
    $\begingroup$ @alphazero That assumes a countable infinity of incoming guests. If, say, the real numbers dropped by, you wouldn't be able to accommodate them even if the hotel were empty. $\endgroup$ – Lee Daniel Crocker Sep 19 at 23:37
  • 2
    $\begingroup$ @LeeDanielCrocker Have you ever seen $\mathfrak{c}$ many people checking in in the same hotel? $\endgroup$ – Bubaya Sep 20 at 10:10
62
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is $ran(f) $? $\endgroup$ – T.D. Sep 25 at 17:02
  • $\begingroup$ @T.D. The range (also called the image) of $f$ - not to be confused with the codomain (which, annoyingly, is sometimes called "range" in older texts). $\endgroup$ – Noah Schweber Sep 25 at 17:19
75
$\begingroup$

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.

$\endgroup$
  • 31
    $\begingroup$ +1 for "This sort of behavior by hotel management is generally frowned upon and leads to poor online reviews of the establishment." Attempts to show that uncountable sets are actually countable often reduce to this (and end with the elements of said sets leaving to an $\mathbb{R}$bnb). $\endgroup$ – Noah Schweber Sep 19 at 15:27
  • 9
    $\begingroup$ Except what the OP proposes does not tell any customer to move to a room beyond all natural numbers. Each customer is told to move to the very next room every time. It is just that they are told to do this an infinite number of times. And it is not necessary that it take an infinite amount of time to accomplish. The extraordinary customers may become so proficient at room swapping that they can accomplish each swap twice as fast as the previous swap. Unfortunately, once finished, management will no longer be able to tell where any guest is, nor who is in any room. That too is frowned upon. $\endgroup$ – Paul Sinclair Sep 19 at 17:00
12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Small quibble: the hotel does not become empty under the OP's approach. It's occupancy becomes undefined. At no time is any room left without being re-filled, but there is no definitive answer as to who is in any room. $\endgroup$ – Paul Sinclair Sep 19 at 16:51
  • 2
    $\begingroup$ @PaulSinclair nobody who was in an original room remains in a room (or at least one which is finitely numbered) and similarly nobody who arrived, so you can certainly say that none of the rooms has any of these people. $\endgroup$ – Henry Sep 19 at 18:36
  • 1
    $\begingroup$ But you can also certainly say that no room is ever left vacant, and therefore every room should be filled. And you can also certainly say that at no time did anyone leave the hotel, so all the guests are still there, in rooms. This is why the final result of the supertask is undefined. $\endgroup$ – Paul Sinclair Sep 19 at 23:09
  • 1
    $\begingroup$ @PaulSinclair Wow, are you sure this isn't Schrodinger's Hotel? $\endgroup$ – Michael Sep 20 at 16:26
  • 1
    $\begingroup$ @Michael - Supertasks are ill-defined by their nature. So it is not surprising that if you make assumptions about how they work, you may get contradictory results from different assumptions. Unlike quantum mechanics, you can't do experiments to figure out what "true" behavior is. $\endgroup$ – Paul Sinclair Sep 20 at 20:19
9
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

You can accomodate a countably infinite number of new guests in Hilbert's Hotel. Just have each current guest, who is in room number i, move to room 2i. Then all the odd numbered rooms are open and the new guests can move in, and everybody only has to move once.

$\endgroup$
  • 3
    $\begingroup$ This doesn't answer the question. The OP has stated they already know that approach. The question asked is why moving the guests infinitely many times is not another solution. $\endgroup$ – Paul Sinclair Sep 20 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.