The "Paradox" of Hilbert's Hotel

Question

I'm not a mathematician at all. From this I read a sentence like this :

A. Imagine a Grand Hotel with a (countably) infinite number of floors and rooms. On this particular night, the hotel is completely full.

The thing that I don't understand is : Why the illustration say "the hotel is completely full" ?

When we hear "the hotel is completely full" doesn't that mean this hotel has a finite number of rooms ?

The article continue :

B. Late in the evening, you arrive at the hotel and inquire about a room. Although there is no vacancy the hotel manager tells you that since this is an infinite hotel she can easily make room for you!

To me, it seems the illustration want to show that the hotel will make one room each time there is a guest to check in. So, if at 3 pm there are 10 guests want to check in, then the hotel make 10 rooms. By 4 pm, there are another guest want to check in, then the hotel make one more room. Please correct me if I'm wrong.

BUT, the article continues :

C. You’re delighted, but confused. If the infinite hotel is completely filled with an infinite number of guests, how does the manager go about securing a room for you?

I don't understand, why the illustration say that I'm confused ? If I know that the hotel can always receive a guest just before I check in then why do I confuse ?

The thing that I confuse is if the manager tell me "our hotel is completely full" at the time I want to check in. So, it's not the "how does the manager go about securing a room for me" which made me confuse, but why the hotel's manager told me "our hotel is completely full" which made me confuse.

The article continue :

D. Now this is perplexing. At first you may think, “Well since it’s infinite can’t we just put the new guest in the last room?”

To me, the thing that "at first I may think" is :
How come it is said "the hotel is completely full" ? And of course, since it's infinite - there will never be "a last room". To me, the hotel will never say "we are completely full" since it has an infinite number of rooms.

Except, "the hotel is completely full" means at the time I want to check in. But then there is no problem since the hotel can always make another new room for each of their future guests as seen in point B. So, "the last room" means the newly build one - not the existing one. The hotel's manager doesn't have to move each existed guest to the next room in order to put me in room #1, but just put me to the newly build one, "the last room".

What did I do wrong in understanding this Hilbert's hotel illustration ?

---

I'm sorry as my question above is not fit to be asked. Now I understand that it seems the answer to my last question : "What did I do wrong in understanding this Hilbert's hotel illustration ?" is simple ---> "I put the illustration as if in a real event/condition" which actually I should try to put it in a mathematical condition.

I'm sorry once again for my mistake :).

Thank you for all the answers and the comments. I give up.

Answer 1

A. We label the hotel rooms in $\mathbb{N}$, that is in terms of $1, 2, 3, \ldots$ and the hotel is full in the sense that whenever you give me a positive room number, I can go check that room and there will be a customer there. Hence, there is no empty room.

B. Now, you just arrive at the hotel and you want to check in. hmmm... each room is occupied, but you will be accomodated by making the customer in room $i$ to room $i+1$ and the first room is assigned to you. Hence a room is given to you (i.e. a room is made in this sense). It doesn't mean we build a new room but we just shift the customers.

C. The description that you are confused perhaps treat the new customer as someone who is new to the idea of countably infinite.

D. I believe part $A$ has answered your question that the hotel can be full. And yes, there is no such thing as the last room in this context just like there is no such thing as the biggest positive integer. Also, the writing treat it as someone is not familiar with countably infinite.

Answer 2

I don't know the best way of addressing all of your questions except point by point, so bear with me.

A) There are an infinite number of rooms. At no point should you assume that anything that is said implies there are only finitely many rooms, since that is in contradiction with very first line. When we say that the hotel is completely full, what we mean is that there is currently a person in every room; room 1 has person 1 in it, and room 2 and person 2 in it, and room 3 has person 3, and so on.

To say that the hotel is completely full, in the parlance of mathematics, is to say that there is a one-to-one and onto function from the list of people (1,2,3,...) to the list of rooms(1,2,3,...). This function did not have to send person $n$ to room $n$, but we can start with that function to help us understand the setup of the hotel.

B) The phrase "to make room" is a colloquialism for providing an accommodation to someone, typically based on space. So in this case, when the receptionist says "we can make room for you" they are NOT creating a new room, but rather saying that is is possible to find a room for you to stay in. This is not a mathematical statement, it is just narrative wrapping for the problem at hand.

C) Your confusion is supposed to be as follows: On the one hand, you know that the hotel is completely full, since every room has a person already in it. On the other hand, the receptionist has just promised you that by the end of the night, you will have a room to yourself. These two statements are seemingly contradictory, which is why you might find yourself confused.

D) What the punchline of the rhetorical question is supposed to be is that there is no such thing as a last room in this hotel. To see this, try and name the room number of this hypothetical last room; is it room $17$? Room $128$? Room $10^{10^{10^{10^{10}}}}$? Of course not, because those are all finite numbers, and hence there is always a room after them in sequence.

Now, since there is no last room, and every room is currently occupied, and since we cannot make rooms on the spot, it would appear that you will not get a room. However, as the rest of the example will hopefully show you, there is a way to reorganize the guests so that you can get a bed by the end of the night.

Answer 3

I believe this is more of an issue of the particular language used here, and not so much of the math. With that idea in mind, I will try to walk you over this as carefully as I can. Without any loss of the mathematical understanding.

Imagine a Grand Hotel with a (countably) infinite number of floors and rooms.

Here, countably refers to a particular kind of infinity.

However, the term "countable" can be confusing misinterpreted if you are not familiar with the term. As, you see... "countable" does not mean that you can count the rooms as a real thing that can happen in the real world (that would be a supertask).

Instead it means that it is the kind of infinity that corresponds to the amount of natural numbers. How many natural numbers are there? Infinite. Or, more precisely, the kind of infinity that corresponds to the cardinality of the set of numbers that follow Peano arithmetic.

This implies that we can give a number to each room. It is implied that we do that. Thus, for every natural number there is a room, and every room has a natural number.

A set of elements that is this particular kind of infinite has the property that there is always a next element. And thus, there is NO last element. This follows from the definition of the successor function that is used in peano axioms.

This fact that there is NO last element (no last room in the hotel) is why they cannot put you in the last room.

On this particular night, the hotel is completely full.

The way to make sense of this phrase in the context of Hilbert's Hotel is as following: Each and every room in the hotel is currently occupied (there is no room that is not occupied). That is, all rooms are occupied. We can say that the hotel is fully occupied, or that it is full.

Perhaps that can be strange when talking about something that is infinite. In particular given that you can always put more stuff in something infinite... which is kind of the point of Hilbert's Hotel, but I digress.

To make it easier to understand, let us think of a Bus. A finite Bus, mind you. But one of which we do not know how many seats it has. Why we do not know? Because we haven't counted. Let us pretend we do not know how to count...

However, in this particular moment we notice that none of the seats are empty. They all have people sitting there. Furthermore, in the bus there is nobody standing (or laying down or whatever, there nobody without a seat). What can we say about the number of people in the bus?

Well, we can say that in the bus are as many people as seats. That is, that the amount of people is the same as the amount of seats, in the bus. And we can say that without knowledge of the number of seats in the bus.

We do the same thing for the Hotel. On this particular night, there are no rooms that are empty, and there is no people waiting for a room. Thus, the number of people in Hilbert's Hotel is the same as the number of room. Which, is infinite, by definition.

Again, all rooms are taken, the Hotel is full.

Late in the evening, you arrive at the hotel and inquire about a room.

We are going to see what happens when somebody comes to the hotel... They are making you into a character in the history to make it more relatable.

Although there is no vacancy the hotel (...)

Meaning that no room is empty.

(...) manager tells you that since this is an infinite hotel she can easily make room for you!

Here, make room does not mean to contruct a new room. Instead room means space. The phrace "make room for you" means to move things around in a way that they open space that allows you to enter.

The following is from the oxford dictionary:

room

NOUN

1. Space that can be occupied or where something can be done, especially viewed in terms of whether there is enough.

(...)

make room

Move aside or move something aside to allow someone to enter or pass or to clear space for something.

‘the secretary entered with the coffee tray and made room for it on the desk’

Source: room at oxforddictionaries.com

You’re delighted, but confused.

Forget it says you. It is this character that is delighted, but confused. Forget about him.

If the infinite hotel is completely filled with an infinite number of guests, how does the manager go about securing a room for you?

---

So, if we look at the function f(n) = n + 1, and we say that the input (domain) is all natural numbers. We would observe that the output (range) are all natural numbers except 0 (that is, the set of all positive integers). Because there is no natural number for which n + 1 = 0. We would have to introduce negative numbers for that... but we are working on the natrual numbers.

Thus, if we tell every guest of the hotel to move from their current room (n) to the next room (n), we are certain that the first room will be empty. And the number of guests in the hotel did not change.

Given that now we have the first room empty, we can give it to the new guest. Effectively adding 1 to the number of guests. And the result? How many guests are there now? The same amount: infinite.

Note: Of course the example of Hilbert's hotel uses positive integers instead of the natural numbers. However, exactly by the argument above, there are as many positive integers as there are natural numbers: (countably) infinte.

---

Now this is perplexing. At first you may think, “Well since it’s infinite can’t we just put the new guest in the last room?”

As explained above, there is no last room. By the way, do not let them tell you what do you think. Who thinks that, is the character in the history.

Answer 4

I think your basic problem here is that you are misunderstanding the term "infinite". Saying that there is an infinite number of rooms doesn't mean that you can never reach the end of the rooms since more can always be added. It means there actually are infinitely many rooms that exist in a single instant. In other words, "infinite" isn't describing some process that can be carried out forever; it's describing the actual state of the hotel all at once. Explicitly, for every positive integer $1,2,3,4,5,\dots$, there is a room in this hotel. You want to go visit room $576$? There's a room with that number. What about room $3263646475454575$? Yep, that room exists too. These aren't new rooms that are being added on as new people arrive; all of them are already there.

And, since all of these rooms already exist, they can all be occupied! Every single one of the hotel's numbered rooms has a person staying in it already. So in that sense, the hotel is "full". There is no reason an infinite hotel can't be "full" in this sense, if you can also have an infinite number of people!

The surprising thing is then that even when the hotel is full (every room is occupied), it is possible to accommodate a new guest without adding any new rooms to the hotel.

Answer 5

The number of rooms in Hilberts hotel is a countable infinity and is completely filled with an infinite number of guests . Just think of it as there being a $1$ to $1$ correspondence with the natural numbers {$\,1,2,3,4,5,....$}and think of the guests being numbers, So the hotel is always completely full since each number staying there is always matched one to one to a room.

The reason you cant put a new guest at the last room is because there is no last room, there is always an room after the so called "last room" . But you can make space for a new guest if you move each guest to the next room ie $1 \rightarrow 2,2\rightarrow3,3\rightarrow,......$ie $n\rightarrow n+1$.

I'll leave a link to a nice video that shows this very nicely and is more understandable. But, just one thing ,if you're thinking about a thought experiment its better to look at it from multiple perspectives essentially because thought experiments cant be done in real life and many do not obey with our real life understandings so its hard to think of it as happening in real life. So an out of the box thinking is always helpful.

The Infinite Hotel Paradox - Jeff Dekofsky

Answer 6

Perhaps a little parable may help.

Let's imagine ourselves standing next to the manager outside of Room 1. The next room down the hall is Room 2. Next to that is Room 3. Looking further down the hall, one can see Rooms 4, 5, 6, 7, and so on. With our limited way of seeing, the rooms appear to shrink off into the distance. But the manager, of course, can see all of the infinitely many rooms simultaneously, that's his job.

The manager also knows, as part of his job, which customers are in which room, and he knows that there is a customer in every room: Customer 1 is in Room 1, Customer 2 is in Room 2, Customer 3 is in Room 3, and so on.

Now Customer A arrives, comes up to the manager, and asks for a room.

The manager telephones every room simultaneously (it sounds impossible, I know, but that's his job and he does his job well). He telephones Customer 1 and says "Please move to Room 2"; he telephones Customer 2 and says "Please move to Room 3"; he telephones Customer 3 and says "Please move to Room 4"; and so on.

Standing next to the manager, we see the door of every room open simultanously. We see a customer come out of every door, walk further down the hall to the next door, go into that room, and finally we see every door close simultaneously except the door to Room 1. The manager turns to Customer A and gesturing towards Room 1 says "Your room is ready".

At that moment, all of the doors to Rooms 2, 3, 4, ... re-open simultaneously, and all of the customers come out of their rooms simultaneously: Customer 1 comes out of Room 2; Customer 2 comes out of Room 3; Customer 3 comes out of Room 4; and so on.

Then, all of Customers A,1,2,3,4,.... say, in an infinite, simultaneous chorus of complaining voices, "Aren't you going to change the sheets?"

Answer 7

The existing answers are correct, but it seems you are still confused. Let me try a different way of phrasing what's going on here.

First, re: your comments about what the manager knows: the manager knows, at any given time, how many rooms there are in the hotel (it's always $\aleph_0$) and which of them have people in them (this set changes over time as people move from room to room). There's no ambiguity here. You're conflating two senses of "completely full" - "every room has a person in it" (correct) and "there is no way we can accommodate another guest" (incorrect) - and I think this is leading to some confusion.

Second, it may be helpful to cast the problem in terms of sets and functions, since this gets rid of some extraneous details which may be more confusing than helpful in this case (namely, the whole "story," complete with manager, knowledge, etc.). Before diving into the precise mathematical content of the story, let me state the key underlying principle:

Sometimes there can be a bijection between a set and one of its proper subsets.

That is, "bigger" doesn't always mean what we think it means! For example, the even integers form a proper subset of the integers, but the map $x\mapsto 2x$ is a bijection from the integers to the even integers. The story concerns a slightly more complicated, but ultimately equivalent, situation (for simplicity let's just think about the original, one-new-guest version):

• We have the set $A$ of original guests and the set $B$ of original guests plus the new guest.

• Clearly $A\subsetneq B$.

• We also have a set $H$ of hotel rooms, and a function $f: A\rightarrow H$ which is surjective (= the map sending each original guest to the room they have at the beginning of the story; the point is that surjectivity means that every room has a guest, and it is in this sense that "every room is full" (at this point it might be helpful to look back at the second paragraph of this answer re: the two senses of "full")).

• We then construct an injection $g:B\rightarrow H$, despite the existence of a surjection (namely, $f$) from a proper subset of $B$ to $H$.

• Note that this can't happen with finite sets: if $X, Y$ are finite sets with $X\subsetneq Y$, and $Z$ is a set with a surjection from $X$ to $Z$, then there can be no injection from $Y$ to $Z$. This is a good exercise.

The whole "the manager knows" bit is incidental: it's just a device used to frame the situation in hopefully more intuitive language. Pruning away the flowery language, the mathematical content of the story is:

In general, even if $A\subsetneq B$ and there is a surjection from $A$ to $C$, there may still be an injection from $B$ to $C$.

Answer 8

The notion of the "Hilbert Hotel" seems to have developed from a lecture David Hilbert gave in 1924 entitled $About$ $the$ $Infinite$.

Hilbert was very keen on the set theory that had recently been developed by Georg Cantor (which was not initially well received) and wanted to convey some of the astonishing (i.e., contrary to intuition) results that transpire when considering sets with an infinite number of elements.

So, he postulated a hotel with a countably infinite number of rooms and where all of those rooms are occupied. (If you have trouble visualizing this, consider a countably infinite number of rooms that are numbered in increasing order beginning with the number $1$). Another person (or number, say $0$) enters the hotel and requests a room where currently there is no vacant room (or, in the case of $0$, no unnumbered room as all of the rooms are currently numbered $1, 2, 3, \ldots $).

Though the hotel manager asserts this, the person (or, number $0$) suggests to move each guest (number on the door) one room over (or, do this adding $1$ the each newly moved number). Such will result in a vacant (unnumbered) room to which the new guest (new number, now called $1$) can be accommodated.

Conclusion: the set $\{1, 2, \ldots \}$ contains exactly the same number of elements as the set $\{0, 1, 2, \ldots \}$.

This idea is furthermore extendable to any countable number of new guests (numbers), which thus yields the counter-intuitive conclusion that sets such as $\{-100, -99, \ldots, 0, 1, 2, \ldots \}$ contain exactly the same number of elements as the set of counting numbers $\{1, 2, 3, \ldots \}$!

These results can be more rigorously substantiated using Cantor's notion of a 1-1 correspondence, which, we can also make use of to show even more shocking results such as the cardinality of the set of rational numbers (i.e., the set of all real numbers that are equivalent to fractions) is exactly the same as that of the counting numbers.