B Hilbert's Hotel: new Guest arrives (Infinite number of Guests)

[dakiprae]

TL;DR Summary

Hilberts Hotel, proof me that there is room 1 empty.

Hilberts Hotel has infinity numbers of rooms and in every room is exactly one guest.

On Wikipedia Hilberts Hotel gets described as well:
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.

My thoughts about this:

1) How can you proof, that you can move every guest from his current room to the next room (n+1).

2) Remeber the Text says: "After this, room 1 is empty". But then you have to proof first, that "before" really every guest moved into the next room.

My opinion: There is no proof that a single new guest can be moved in room 1. It can not be proofed, that every guest can move into the next room. As long you can't proof that ever guest moved from his current room to room n+1 you can not say room 1 is empty.

What do you think, do you think i am completely wrong?

 

[mfb]

1) How can you proof, that you can move every guest from his current room to the next room (n+1).

No room should be occupied by more than one guest, and every guest should have a room. This is satisfied for every room and guest. The question how to tell an infinite number of guests that they should change their room is not considered here.

2) Remeber the Text says: "After this, room 1 is empty". But then you have to proof first, that "before" really every guest moved into the next room.

Have to prove what?

 

[fresh_42]

Not completely, just a bit. You are right, it cannot be proven. It is an axiom (look up Peano). In this case the second: every natural number has a successor. This allows us to move the guests into the room labelled as successor.

 

[PeroK]

Summary:: Hilberts Hotel, proof me that there is room 1 empty.

Hilberts Hotel has infinity numbers of rooms and in every room is exactly one guest.

On Wikipedia Hilberts Hotel gets described as well:
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.

My thoughts about this:

1) How can you proof, that you can move every guest from his current room to the next room (n+1).

2) Remeber the Text says: "After this, room 1 is empty". But then you have to proof first, that "before" really every guest moved into the next room.

My opinion: There is no proof that a single new guest can be moved in room 1. It can not be proofed, that every guest can move into the next room. As long you can't proof that ever guest moved from his current room to room n+1 you can not say room 1 is empty.

What do you think, do you think i am completely wrong?

Hilbert's Hotel is not physically possible. But, it's mathematically possible.

 

[etotheipi]

Hilbert's Hotel is not physically possible. But, it's mathematically possible.

I mean how would they cater for the breakfast buffet? That's a lot of orange juice...

 

[Mark44]

@dakiprae, if you have trouble understanding how the hotel could accommodate a single new guest, you're really going to have trouble when that bus with an infinite number of passengers arrives.

In that case, any current guest in room N will be asked to move to room 2N, thereby freeing up all of the odd-numbered rooms.

1) How can you proof, that you can move every guest from his current room to the next room (n+1).

The guests are assumed to be very compliant. The guest in room 1 moved to room 2, the guest in room 2 moves to room 3, and so on, ad infinitum.

2) Remeber the Text says: "After this, room 1 is empty". But then you have to proof first, that "before" really every guest moved into the next room.

No, "before," the guests haven't moved yet. "After," the current guests are in a new room next to (higher room number than) their old room.

My opinion: There is no proof that a single new guest can be moved in room 1. It can not be proofed, that every guest can move into the next room. As long you can't proof that ever guest moved from his current room to room n+1 you can not say room 1 is empty.

What do you think, do you think i am completely wrong?

Yes.

 

[dakiprae]

Hilbert's Hotel is not physically possible. But, it's mathematically possible.

I can think about it, so it may be physically possible. Maybe there is a god who can create a universe with infinity space and this hotel. Or maybe there is a universe, which is already infinity years old and has infinity space and has this hotel.

 

[PeroK]

I can think about it, so it may be physically possible. Maybe there is a god who can create a universe with infinity space and this hotel. Or maybe there is a universe, which is already infinity years old and has infinity space and has this hotel.

I doubt that. As @etotheipi pointed out, there would be a problem with breakfast. Not to mention the infinite laundry bill.

 

[fresh_42]

I doubt that. As @etotheipi pointed out, there would be a problem with breakfast. Not to mention the infinite laundry bill.

Interesting physics question here: The communication of the order to move is of finite speed. Whereas this doesn't seem to be a problem for the first billion rooms, will it work out at infinity?

 

[PeroK]

Interesting physics question here: The communication of the order to move is of finite speed. Whereas this doesn't seem to be a problem for the first billion rooms, will it work out at infinity?

The other option is to have every room half the size of the previous one. That has its practical problem too!

 

[dakiprae]

@dakiprae, if you have trouble understanding how the hotel could accommodate a single new guest, you're really going to have trouble when that bus with an infinite number of passengers arrives.

In that case, any current guest in room N will be asked to move to room 2N, thereby freeing up all of the odd-numbered rooms.
The guests are assumed to be very compliant. The guest in room 1 moved to room 2, the guest in room 2 moves to room 3, and so on, ad infinitum.
No, "before," the guests haven't moved yet. "After," the current guests are in a new room next to (higher room number than) their old room.
Yes.

I have no trouble to think about an infinite number of buses, no problem. But my point is different, I asked for a proof, that every guest will find a room, when only 1 guest arrives.

1) Yes I can ad infinitum, but I did not see the proof, that all guest find a hotel room.

2) Same thing, how can you proof that every guest will find a room.

My point is, if there exists a hotel with infinite number of rooms and in every room is one guest, how can you proof that a new guest arriving will find a room in the hotel.

 

[PeroK]

I have no trouble to think about an infinite number of buses, no problem. But my point is different, I asked for a proof, that every guest will find a room, when only 1 guest arrives.

1) Yes I can ad infinitum, but I did not see the proof, that all guest find a hotel room.

2) Same thing, how can you proof that every guest will find a room.

My point is, if there exists a hotel with infinite number of rooms and in every room is one guest, how can you proof that a new guest arriving will find a room in the hotel.

Hilbert's hotel is about numbers; it has nothing to do with hotels, really.

You can think about an infinite number of buses, but you can't have them. Even the number of buses on Oxford Street is finite.

 

[dakiprae]

Hilbert's hotel is about numbers; it has nothing to do with hotels, really.

You can think about an infinite number of buses, but you can't have them. Even the number of buses on Oxford Street is finite.

Why I can not have an infinite number of buses? We do not know if we can have an infinite number of buses. Some people belief in an almighty god, where god can create an infinite number of buses. Also people not believe in god can think that an infinite number of buses could exists, but that's another topic.

 

[fresh_42]

Hilbert's hotel is about numbers; it has nothing to do with hotels, really.

You can think about an infinite number of buses, but you can't have them. Even the number of buses on Oxford Street is finite.

I answered this in post #3.

 

[dakiprae]

Not completely, just a bit. You are right, it cannot be proven. It is an axiom (look up Peano). In this case the second: every natural number has a successor. This allows us to move the guests into the room labelled as successor.

What is the successor for infinity?

 

[etotheipi]

What is the successor for infinity?

Infinity is not a number, it doesn't make sense to ask what its successor is. But for any natural number $n$ you can name, I can always do you one better with $n+1$.

 

[fresh_42]

What is the successor for infinity?

There is no infinity involved. Only a for all quantifier. Every single room is labelled with a natural (and finite) number. So every room has a successor.

 

[PeroK]

What is the successor for infinity?

That's God's room!

 

[dakiprae]

There is no infinity involved. Only a for all quantifier. Every single room is labelled with a natural (and finite) number. So every room has a successor.

So infinite numbers has an succesor, if every natural number has a succesor right? But we said in every succesor is already a guest. So there will be no free room and there is no proof that all guest will find a room, if one more guest arrives?

 

[fresh_42]

All rooms are occupied.
All guests step out at the same time.
All guests step in front of the next door.
All guest enter the new room.

Where do you see an infinite number?

You may equally require that only room number one is occupied and the arriving guests demands room number one. So the concierge uses the successor property to move the first guest in room number two. This is the same principle, just less funny.

 

[dakiprae]

All rooms are occupied.
All guests step out at the same time.
All guests step in front of the next door.
All guest enter the new room.

Where do you see an infinite number?

You may equally require that only room number one is occupied and the arriving guests demands room number one. So the concierge uses the successor property to move the first guest in room number two. This is the same principle, just less funny.

Thank you for your reply.

If there exists an infinite number of rooms, how can you proof that ever single guest can enter next door? If there is no last guest, how can we proof every guest entered the new room?

 

[fresh_42]

Every single guest has a finite room number. And the procedure only takes care about this room and the next one. Infinity is hidden in our predicate logic, which allows us to quantify "for all numbers". This way the logic applies to any finite number as long as we do not pose any restrictions on this number.

If you alter the logic, not the example, then we have another discussion. But in our common logical system we have an all quantifier and are allowed to handle all instances at once.

Edit: It is the same as if I claimed: every second number is divisible by two. This is true, although nobody ever divided all even numbers.

 

[Mark44]

So infinite numbers has an succesor, if every natural number has a succesor right?

No, not right. It makes no sense to say "infinite numbers has a successor." Every finite number N has a successor N + 1.

But we said in every succesor is already a guest. So there will be no free room and there is no proof that all guest will find a room, if one more guest arrives?

At the time all guests switch rooms, all of the current guests step outside and move to the next higher numbered room. The free room is room #1.

 

[dakiprae]

No, not right. It makes no sense to say "infinite numbers has a successor." Every finite number N has a successor N + 1.
At the time all guests switch rooms, all of the current guests step outside and move to the next higher numbered room. The free room is room #1.

I got you point, but for me, still there is no proof that all guest switch rooms. If there is no last guest, there is no proof that all guest moved.

 

[fresh_42]

I got you point, but for me, still there is no proof that all guest switch rooms. If there is no last guest, there is no proof that all guest moved.

You can't handle an infinite number of anything by imagination of a physical procedure. If we say "all guests move into the room on their right", then this happens at once and costs no time. It "happens" within the for-all-quantifier. Again, there is no way to prove that there are infinitely many even numbers by dividing all numbers and check.

 

[Mark44]

I got you point, but for me, still there is no proof that all guest switch rooms. If there is no last guest, there is no proof that all guest moved.

Obviously, since there are an infinite number of room and guests, there is no last room nor last guest. How about this -- you tell me a guest and his/her room number, and I'll tell you where that guest moves to.
Since you are insisting that some guest didn't move, tell me which guest do you believe doesn't move?

 

[QuantumQuest]

@dakiprae This is no kind of aggressive comment but I think that you keep on mixing the notion of infinity with the ordering in natural numbers and going from the first to the second in a somewhat alternate and arbitrary manner, during the same line of thought. As has already been pointed out, there is no next to infinity as there is also no previous to it; in other words you can't add or subtract or do any other math operations at infinity. So, either you accept Peano axioms as @fresh_42 pointed out or not. In the first case, you can see very well that for all ($\forall$) natural numbers there is the next one so the $n$-th guest (whichever countable $n$ is this) will go to $n + 1$ room, so room number $1$ will be left unoccupied to be given to the new guest or there's no point to deal with the problem at all because you put into doubt one of the cornerstone axioms.

But let me give my own answer - everything has already been said but I give it in my own words, to "where does the guest "at infinity" go?" Is there next to infinity? Well, he / she goes again to infinity. The next time which another guest comes, the last guest already being at infinity goes again to infinity and so on. Now, I ask, does this limit the number of guests which will occupy the room number $1$? Why should it do this? Is "infinity" a certain number? Obviously not. So, why should we not be certain that the last guest will go to the next room and the first room will be left unoccupied? Should we have a certain number for the room "at infinity" in order to be sure? If this were the case then what sort of "infinity" would this be? In other words the "infinity" is used in this problem in order to give some rather intuitive sense of magnitude or size and nothing more. The math for the occupation of rooms in each phase just follow the ordering of natural numbers. Nothing more - nothing less. Is there any reason for you to believe that something different happens according to math and what sort of proof do you need? (of course not in some sort of philosophical context).

 

[jbriggs444]

But let me give my own answer - everything has already been said but I give it in my own words, to "where does the guest "at infinity" go?" Is there next to infinity? Well, he / she goes again to infinity. The next time which another guest comes, the last guest already being at infinity goes again to infinity and so on.

The problem with the stance described above is in the word "the" in the first sentence. [highlighting mine].

The word "the" carries with it an assertion of existence and uniqueness. Before you are allowed to use it in mathematical discourse, you need to be prepared to justify both existence and uniqueness. I see no possibility for any such justifications.

There is no guest "at infinity" and no need for one.

 

[dakiprae]

Hey @QuantumQuest,

everything is fine, this is of course not a kind of aggressive comment. It is great to have a discussion here about this topic, I hope no one did felt offended by me neither.

First time I listened to Hilberts Hotel, I would argue with A.

A: Every guest is in exactly one room, there is no room left for a single new arriving guest.

After reading and watching YouTube Videos about Hilbert’s Hotel, I was not sure anymore (B).

B: We can move every guest from his current room n to room n+1. It is possible to make room for any finite number of new guests.

It seems like, everyone argues with A would be shown as wrong. It also seems like, people argue with B often think, only B can be right. This was the moment I was even more interested in the paradox.

But if you turned the tables and ask for the proof of B, it seems like there is no good logical or mathematical proof for B ether, to be shown as true (at least not for me). It feels like the mathematical or logical concepts do not fit for Hilberts Hotel anymore.

So for now I would go with C.

C: I have no idea what will happen to Hilberts Hotel.

But I would still stick to A more than to B. The reason why i stick more to A is the following: If I look at Hilberts Hotel, infinite rooms with one guest in each room just exist. In this existence, there is maybe no moving simultaneously n+1 possible, so it may never be done.

Also, your argument is very good and could be right. They come from infinity and go to infinity.

 

[jbriggs444]

It seems like, everyone argues with A would be shown as wrong. It also seems like, people argue with B often think, only B can be right.

The point is that both A and B are correct and that there is no paradox.

There are infinitely many rooms. All of them are occupied. That is proposition A. Proposition A is correct^*
Room can be made for one more guest without adding any rooms. That is proposition B. Proposition B is also correct^*

One definition for "infinite set" is based on this behavior.

(*) Provided that one is prepared to accept the Peano axioms or many of the various other foundational axiom suites which contemplate infinite sets.

 

[QuantumQuest]

The problem with the stance described above is in the word "the" in the first sentence. [highlighting mine].

The word "the" carries with it an assertion of existence and uniqueness. Before you are allowed to use it in mathematical discourse, you need to be prepared to justify both existence and uniqueness. I see no possibility for any such justifications.

There is no guest "at infinity" and no need for one.

Well, my main argument is in the first paragraph of post #27.

Now, in the second paragraph, I try to convey some ideas in an essentially informal manner. You are right that the word "the" you've highlighted carries an assertion of existence and uniqueness which, obviously enough, cannot be justified / proved. But, I have put the phrase "at infinity" in separate quotes because there is, exactly, no such mathematical thing as a specific person or a room at infinity. So, "at infinity" is used as a vehicle to serve the idea of each time occupying the next-to-last room and the first room be left unoccupied and nothing more. I have also put the rest of arguments about "infinity" in this same regard, in this paragraph. So, while I know of course the correctness of your argument, what I write is an attempt to convey some ideas in a manner of speaking. I'm really sorry if it was not written in a strict mathematical manner but I think that, reading the whole paragraph, my goal to convey the ideas I want becomes obvious.

 

[Mark44]

But if you turned the tables and ask for the proof of B, it seems like there is no good logical or mathematical proof for B ether, to be shown as true (at least not for me). It feels like the mathematical or logical concepts do not fit for Hilberts Hotel anymore.

You have been repeated shown a logical method for freeing up a single room, one that relies only on the mathematical concept that, for the integers, each integer has a successor -- an integer that is larger by one. Why do you believe that this does not constitute a proof? I think you might have a very narrow idea of what a mathematical proof must be.

So, "at infinity" is used as a vehicle to serve the idea of each time occupying the next-to-last room and the first room be left unoccupied and nothing more.

There is no next-to-last room, any more than there is a last room. "At infinity" doesn't apply here. In a similar vein, there is also no last '9' digit in the number 0.999...

 

[member 587159]

What is the successor for infinity?

Assuming you mean the ordinal $\omega$ as infinity,the successor is $\omega+1$.

 

[PeroK]

The point is that both A and B are correct and that there is no paradox.

There are infinitely many rooms. All of them are occupied. That is proposition A. Proposition A is correct^*
Room can be made for one more guest without adding any rooms. That is proposition B. Proposition B is also correct^*

One definition for "infinite set" is based on this behavior.

(*) Provided that one is prepared to accept the Peano axioms or many of the various other foundational axiom suites which contemplate infinite sets.

Or, even more succinctly. The function $f: \mathbb N \rightarrow \mathbb N$ such that $f(n) = n+1$ is well defined.

 

[pbuk]

I'm going to try a more direct approach to answering the OP - here is a series of statements which provide an informal proof for the 'always room for 1 more' solution.

1. Room $1$ exists (axiom)
2. If room $n$ exists then so does room $n + 1$ (axiom)
3. At the beginning of a transition all rooms are considered available (axiom)
4. At the end of a transition all rooms may be empty or be occupied by exactly 1 person i.e. full (axiom)
5. Immediately before transition $t_i$ all rooms are full (statement)
6. During transition $t_i$ each person $p_n$ in room $n$ moves to room $n+1$ (proof follows)
   1. Room $n+1$ exists (by 2)
   2. Room $n+1$ is available (by 3)
   3. No other person $p_m, m \ne n$ is moving to room $n+1$ so $p_n$ can move to room $n+1$ (by 4)
7. During transition $t_i$ the person in room 1 moves to room 2 (by 6)
8. After transition $t_i$ room 1 is empty (by 7) QED

 

[QuantumQuest]

There is no next-to-last room, any more than there is a last room. "At infinity" doesn't apply here. In a similar vein, there is also no last '9' digit in the number 0.999...

Fair enough. Although I just try to give an abstract idea - I have already mentioned in post #27

As has already been pointed out, there is no next to infinity as there is also no previous to it; in other words you can't add or subtract or do any other math operations at infinity.

I think that I did it in a rather violating way regarding math lingo (referring also to post #28 by @jbriggs444). So, I apologize for it. What I essentially mean is that our counting goes till very close to infinity (not "at infinity" as I said).Now, let me give it in a more formal manner as a continuation of the first paragraph of post #27.

We use the bijection $f(n) = n + 1$ in order to relocate all guests. This holds for the simple variation of one guest arrives each time. For the other variants of the problem we can also create an appropriate bijection. The whole idea is that we can put a set having infinitely many elements into one-to-one correspondence with (any) one of its proper subsets.

 

[jbriggs444]

very close to infinity

This is yet another undefined notion.

 

[Mark44]

We use the bijection $f(n) = n + 1$ in order to relocate all guests. This holds for the simple variation of one guest arrives each time. For the other variants of the problem we can also create an appropriate bijection. The whole idea is that we can put a set having infinitely many elements into one-to-one correspondence with (any) one of its proper subsets.

Yes. If we need to find space for 2 arriving guests, the bijection $f(n) = n + 2$ will do, and similar for any finite number N of new arrivals.
If we need to find space for a (countably) infinite number of new guests, here's a bijection that will work: $f(n) = 2n$. After the existing guests move, they will have moved to rooms with even numbers, freeing up all of the odd-numbered rooms.

 

[QuantumQuest]

This is yet another undefined notion.

What I mean is: up to the point where we have no means whatsoever to count further.

 

[PeroK]

Fair enough. Although I just try to give an abstract idea - I have already mentioned in post #27

How about this:

You are working reception at the Hilbert Hotel, which is full. A new guest arrives and you issue the order for every guest to move to the next room; leaving room 1 vacant for the new guest.

The phone rings because two people are now having to share. From which room is the phone call coming?

 

[gmax137]

I thought the point of the Hilbert Hotel was more about understanding the meaning of "infinity" than it is about hotels or rooms or proofs.

Say you see a billboard advertisement for a hotel, "We have an infinite number of rooms!" So you call and ask, "Is there always room for another guest?" If the clerk says "no, once every room is occupied we can take no more" then you know the billboard is just advertising hype.

 

[dakiprae]

I think there are good reasons out there for the n + 1 peano axioms. Still struggling, when its ends up in infinity. I am going to leave this topic for now. Thank you all for your input

 

[jbriggs444]

What I mean is: up to the point where we have no means whatsoever to count further.

That is yet another undefined notion. There is no such point in the natural numbers. By axiom, each one has a successor.

 

[Mark44]

Still struggling, when its ends up in infinity.

It doesn't end up. The number of rooms in this hypothetical hotel is unbounded.

 

[bahamagreen]

Let the room numbers and occupants be unique and paired natural numbers such that:
1 is in room 1, 2 is in room 2, 3 is in room 3...
Is there any question that the hotel now contains all of the natural numbers?
If posed a unique natural number not yet a guest shows up, what is this number?

 

[jbriggs444]

Let the room numbers and occupants be unique and paired natural numbers such that:
1 is in room 1, 2 is in room 2, 3 is in room 3...
Is there any question that the hotel now contains all of the natural numbers?
If posed a unique natural number not yet a guest shows up, what is this number?

Let the new guest be assigned a name instead: "new guest" such that "new guest" is not an element of $\mathbb{N}$

Is there a possible bijection between $\mathbb{N} \cup \{\text{new guest\}}$ and $\mathbb{N}$?

[I find it distasteful to dodge the problem by saying that no new guest shows up]

 

[bahamagreen]

Considering a kind of object, looks to me like "all" might be finite or infinite, and "infinite" might be some or all.

With natural numbers 1, 2, 3..., it looks to me like "all" does mean infinite and infinite does mean all. So no new guests in the form of a natural number.

I'm not seeing a bijection; {new guest} is not paired with a natural number. But I'm not seeing the motivation to propose a different kind of object as the new guest.

 

[jbriggs444]

Considering a kind of object, looks to me like "all" might be finite or infinite, and "infinite" might be some or all.

"All" is a quantifier. Not an object.

With natural numbers 1, 2, 3..., it looks to me like "all" does mean infinite and infinite does mean all.

That is not correct. There are many infinite subsets of the natural numbers. Uncountably many. Only one of those subsets consists of all of the natural numbers.

I'm not seeing a bijection; {new guest} is not paired with a natural number.

Yes. It is. The bijection that is proposed maps "new guest" to 1, 1 to 2, 2 to 3 and so on.

But I'm not seeing the motivation to propose a different kind of object as the new guest.

If you have no new guests to come to the hotel, the question of where to put a new guest does not arise. Insisting the new guest be a natural number would be dodging the scenario. It is not polite to pretend to have something relevant to contribute when one does not.

 

[Mark44]

If posed a unique natural number not yet a guest shows up, what is this number?

What does this even mean? It looks like something that Yoda might say, except that it's completely unintelligible.

It is not polite to pretend to have something relevant to contribute when one does not.

Amen...

 

[bahamagreen]

I'm thinking about it...