# The “Paradox” of Hilbert's Hotel

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.

• If you have no problem with a thought experiment of infinite hotel rooms, then you shouldn't have a problem with infinite blue hotel rooms, or infinite hotel rooms all with a lamp, or infinite hotel rooms all with a human being inside. – Jonathan Hebert Mar 25 '18 at 7:44
• (a) Full does not mean finite number of rooms. Full means every room has an occupant. (b) The hotel does not build new rooms. (c) Going into the hotel, you didn't know the hotel can always receive a guest. You are confused because you don't know how they can secure a room if they have no rooms available. (d) I don't understand what your question is in this part. – anon Mar 25 '18 at 7:47
• One of your confusions is rather about the word make which in this contexts means 'free up a room', and not 'building a new one'. – Berci Mar 25 '18 at 8:02
• Full does not mean the hotel cannot accommodate another person. Full means every room has an occupant. The hotel is full in this story. The manager is being completely truthful in saying the hotel is full. – anon Mar 25 '18 at 8:06
• Yes. The manager knows the hotel has (countably) infinitely many rooms, and knows every one of them is occupied. The manager is the manager, after all. – anon Mar 25 '18 at 8:11

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.

• Siong, you wrote "I can go check that room and there will be a customer there. Hence, there is no empty room". This the thing which made me confuse, from the bold sentence and based on the Hilbert's hotel illustration, I don't understand why it is said "there is no empty room" while the hotel's manager can move each existing guest to the increment N+1 room ? Doesn't that mean there is an empty room available so that's why the hotel's manager can move each of the existing guests to the next room ? – karma Mar 25 '18 at 8:38
• @karma : no, it doesn't mean there was an empty room. Actually every occupant is move to a room that was already occupied (from n to n+1). It is only after that clever manoeuvre that an empty room is created (room 1). – Evargalo Mar 25 '18 at 8:50
• This doesn’t sound like a hotel I’d like to stay in. All that moving around to different rooms all the time. I’m trying to have my bath here! – Janus Bahs Jacquet Mar 25 '18 at 9:01
• @karma: "Completely full" means that all the space within is filled. Even in real life that does not mean the same thing as "you can't add more"; e.g. you can always add more material to something by compressing what's already present to take up less volume. – user14972 Mar 25 '18 at 10:07
• @karma It's true that you can never make an infinite hotel full by adding any finite number of guests. But the point of the story is that the hotel already has an infinite number of guests, such that all the infinitely many rooms are filled, and thus it is full. The point of the story is to show how countable infinity can be counterintuitive and somewhat confusing, precisely because any assumption and intuition you may have about finite numbers, and what "full" means, simply doesn't work. – Ove Mar 25 '18 at 15:10

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.

• Valborg, you are right on point-C. That's the thing that made me confuse. Because as long as I know, in reality when somebody say "X is completely full", then this person know that something can not be added into X anymore. – karma Mar 25 '18 at 8:36
• @karma The issue you seem to be having is translating back and forth between the mathematical statements and the English colloquialisms. In reality, when someone says "X is completely full" we know that nothing can be added, but there are no infinite objects in reality. In mathematics, when someone says "X is completely full", it turns out that we cannot know for sure that nothing can be added, because there might be an infinity involved somewhere. – Valborg Mar 25 '18 at 8:40
• @karma It might be helpful for you to try and approach this as a mathematical problem, rather than simply trying to understand the problem through this "pop-math" explanation. Convince yourself of the following facts: There is a one-to-one and onto function from $\{0\}\cup\mathbb{N}$ to $\mathbb{N}$, there is a one-to-one and onto function from $\mathbb{Z}$ to $\mathbb{N}$, and there is a one-to-one and onto function from $\mathbb{Q}$ to $\mathbb{N}$. These are the three mathematical facts that this example is supposed to ultimately demonstrate. – Valborg Mar 25 '18 at 8:47
• Valborg, thank you for your explanation. And I must admit that I give up. I will add a few sentence in my question to tell my reader that I give up because I can not put "the situation" as in mathematical condition. As it seen in my question, "the situation" I put is more in a reality event. I'm very sorry for my mistake. – karma Mar 25 '18 at 8:51
• @karma No need to apologize, you did not make a mistake. Dealing with infinity is hard, even for mathematicians. We try to come up with these kinds of cute explanations with infinite hotels to try and bridge the gap and get people interested in math, but just like pop-science there is something lost in translation. I would encourage you to not give up though, and keep trying to wrap your head around it. Maybe not today, maybe not tomorrow, but eventually it will make sense, though I do suspect that you would benefit from learning the actual math behind this hotel problem. – Valborg Mar 25 '18 at 8:58

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 ammount 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’

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.

• Very good, but would be better if you addressed the English language confusion: make room does not mean make a room — no new construction will happen. It's not "a part of the inside of a building that is separated from other parts by walls, floor, and ceiling", but "the amount of space that someone or something needs". dictionary.cambridge.org/dictionary/english/room?a=british. "Make room for" means "find space for". – TRiG Mar 25 '18 at 19:51
• @TRiG addressed – Theraot Mar 26 '18 at 6:27
• Theraot, I get your bus illustration. But to be honest, once it's about the infinite - the one that I can think of is "it's as far as I can see" in a real world. The seats (with people) in the bus are finite, it's not "as far as I can see" because in deed I see all the seats in the bus are all occupied by the passengers without having to know how many people/seats are there in the bus. About the last room, I understand that there will never be a last room... that's why my mind keep on asking "how come it's said it's full ?" :). – karma Mar 27 '18 at 16:18
• @karma did I say "as far as I can see"? I do not find that on my answer. Anyway, for an infinite bus, checking if there is somebody in every seat is an infinite task. Yo are not arguing how it is full, but how to know it is full. For Hilbert's Hotel, that is part of the given. If we are to question the given, then we also need to question how do we know it is infinite, how can there be something infinite, and what are the implications of an infinite object in the real world (can the material of the hotel hold infintie wheight? etc.). Ask Worldbuilding. For math, do not question the given. – Theraot Mar 27 '18 at 16:44
• @karma perhaps that sounds a bit too rude. I am not saying that it is incorrect or not worth to question the given of the scenario, just that it is not math. Mathematics, the way I like to see them, is about inventing some rules and seeing what happens. We invent the rules and we discover the consequences. Some rules we invent lead to paradoxes, others don't. Some rules match what we see in the real world, others don't. Sometimes the rules are useful, sometimes they aren't... or perhaps we do not know yet what they are useful for. – Theraot Mar 27 '18 at 17:01

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.

• A perhaps more fundamental problem is misunderstanding the meaning of the English phrase make room for. – TRiG Mar 25 '18 at 19:52
• Eric, I understand that the problem is me because I can't escape thinking in chronological order. It seems to me the illustration already starts in the middle (infinite rooms available already occupied by infinite guests) ---> and my mind think "how is the process until it reach full from the beginning ? which is when the first guest check in ?" This leads me to think that even there is an infinite guest who will go check-in, the are always available room for them. continue – karma Mar 27 '18 at 15:32
• So, starts from the beginning, there is one guest check in, put in room#1. Next there is a second guest check in, tell the first guest to move to the room next to his room.... and so on. Say... the next day, the 100th guest come to the hotel and check in, do the same thing like before which is move each existing guest to the next room of their room. How do I reach "ah... finally all the rooms available are occupied" ? – karma Mar 27 '18 at 15:37

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

• pranavB23, you wrote "But you can make space for a new guest if you move each guest to the next room ie 1→2,2→3,3→,......ie n→n+1. " I think I now understand what is my mistake. From your sentence above, I think it is in a reality event... which make me think : I need to know the last number (N) in order to move it to an incremental N+1. But in mathematical, it seems I don't need to know what is the last number (as there is no last number) ---> just asume it that N is the infinite number (which always can be added to whatever number). Please correct me if I'm wrong. – karma Mar 25 '18 at 9:01
• pranaveB23, Thanks for the link, I'm going there now. – karma Mar 25 '18 at 9:07

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?"

• Lee, you wrote : 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" ---> to be honest my mind keep on coming back in thinking like this : then the manager know that there is an empty room available. :). – karma Mar 27 '18 at 15:16
• No, the manager is not using any such knowledge. He's using the knowledge that if all of those customers vacate their rooms simultaneously, and if they all walk one door down the hall simultaneously, then they will each simultaneously find an empty room at the next door. – Lee Mosher Mar 27 '18 at 19:24

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

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.