Hilbert's grand hotel as infinite number of pairs

1. Jan 20, 2014

Sissoev

Can we think of Hilbert's Grand Hotel problem as of infinite number of pairs; room/guest pairs?

If we pair infinite number of left shoes with infinite number of right shoes, we will have infinite number of shoe pairs.
In such pairing there will not be left any unpaired shoes, because that would brake the infinity in both the sets.
That would mean that there is no way to add one left shoe and get new pair of shoes in the shoe pair infinity.
Same way, it would not be possible to add even one only guest in Hilbert's Grand Hotel.

Should we not treat Hilbert's hotel as two paired infinite sets, where adding to one of the pair sides will brake the infinity in both sides?

2. Jan 20, 2014

pwsnafu

No, if I take away a left shoe from you, you still have an infinite number of left shoes and an infinite number of right shoes left over. Just one of which is unpaired. And then, if you want, you can pair them up again if you want.
If you have an infinite number of something and take away a finite number, you still have an infinite number left over.
Similarly, if you have an infinite number of something and add a finite number, you still have an infinite number.

I also have no idea what you mean by the words "break infinity".

Sure if that's your model. The Hotel is now a subset of $\mathbb{N} \times \mathbb{Z}$.
The first coordinate is room number, second coordinate guest number. I chose the integers here because I want "old guests" as positives and "newly arrived guests" as negatives.

The Hotel starts with $\{(1,1), (2,2), (3,3), \ldots\}$.

A new guest arrives, whose name is "-1". The clerk sends the guest in room 1 to room 2 etc. Guest "-1" goes to Room 1. We now have a Hotel that looks like $\{(1,-1), (2,1), (3,2), \ldots\}$.

Last edited: Jan 20, 2014
3. Jan 20, 2014

Sissoev

To break infinity... :shy:
Well, not exactly to break it, but in a meaning that it wasn't infinity in a first place.

We know that infinity+1=infinity, but that's not the case with pairs, I think.
Why?
In the OP I said:
In other words; if we pair two infinite sets, and we are left with one unpaired object, that would tell us that we weren't dealing with infinite sets.
I think that we have to keep that in mind when we work with paired sets.
Right and left shoes are in pairs, which brings equation in the two paired infinite sets.
If you take one out from one of the sets, the equation breaks, from which the infinity "breaks".
(One of the sets becomes with 1 greater than the other set, which results in one object not having its pair. And that is clearly not infinity.)

Following the above we can create a rule: two infinite sets can be paired only once.
Breaking that rule would create paradoxes.

Last edited: Jan 20, 2014
4. Jan 20, 2014

pwsnafu

This does not follow. You cannot pair the natural numbers with the reals because the latter is uncountable. Doesn't change the fact that the naturals and reals are infinite to begin with.

No it does not. All it does is a relabel.

"One of the sets becomes with 1 greater than the other set" is a false statement. They still have the exact same number. That is what being an infinite set means: there is an embedding into a proper subset of itself.

That's nonsense. We are free to relabel any number of times. Every real function* you learned in school does this. In other words you are claiming that taking a function $f(x)=x$ and defining a new function $g(x) = f(x)+1$ is an invalid procedure.
*well, every real function that is a bijection.

Now if you mean, define a function, and then claim it is something else? Yeah, that's not allowed. But that is also true for finite sets as well. But Hilbert's Hotel doesn't do that. It defines a different function (in the function model), or changes state (in the dynamical system model). In the pairs model I gave above the Hotel has changed from one infinte set to another set, but those two sets have the same cardinality because it's clear there is a bijection between them.

Edit: To add to this, you are using the word "pair" in two ways.
On one hand you are talking about a set of pairs, that is the Cartesian product of two sets.
On the other you are talking about pairing two sets, which means to define a function (specifically a bijection) between them.
Those are two separate things.

Last edited: Jan 20, 2014
5. Jan 20, 2014

Sissoev

Lets keep it simple for you, pwsnafu; imagine that two guests came in the hotel and in order to accommodate them the manager orders all guests to get out of their rooms and move in front of the room with two numbers up.
Then №1 moves in front of room №3, #2 in front of room №4 and so on.
Then one of the new guests goes in front of room №2, but the other guest suddenly decides that the hotel is too dirty and leaves it. Room №1 remains without guest in front of it.
Now the empty rooms ready to accommodate the guests waiting in front of them are with one more, which makes the infinity false.
To avoid such stupid situations, two infinite sets can be paired only once

6. Jan 20, 2014

Office_Shredder

Staff Emeritus
Sissoev, at that point the hotel manager could, if he wanted to, ask all the guests to move one room back, making all the rooms matched up with guests again.

It is true that given two countably infinite sets, you can make a function from one to the other that does not create a perfect pairing, but that doesn't change the fact that you can also pair them up perfectly.

It doesn't even make sense to say "can only be paired once'. A pairing mathematically is just a function $f:X\to Y$ which is both one-to-one and onto. I can come up with tons of functions $\mathbb{N} \to \mathbb{N}$ which are pairings, and you could cycle through and apply them however you want.

7. Jan 20, 2014

Sissoev

Sure, but that wouldn't make the set infinite again.
That would just make the last room empty ;)

8. Jan 20, 2014

Office_Shredder

Staff Emeritus
Which set? The set of people and the set of rooms are always infinite.

There is no last room, just as there is no last natural number.

9. Jan 20, 2014

Staff: Mentor

For an infinite number of rooms (or an infinite number of anything), there is no "last" room.

10. Jan 20, 2014

Staff: Mentor

I think you have a basic misunderstanding of what infinity means. An infinite set doesn't become finite just by removing one element from it.
No, not at all.

For a simple example, assume that the hotel is completely booked, with a person in each room. We have a pairing between the set of hotel patrons and rooms, both of which are infinite sets. If the manager asks each person to move to a room whose number is one higher, then room 1 will be empty. In no way does this somehow imply that the set of rooms is now finite. What we have now is a one-to-one pairing between the hotel patrons and rooms 2, 3, 4, ..., N, ...
It's clear that you don't understand...

11. Jan 20, 2014

Sissoev

Come on, guys!
I know that there is no last room in an infinity set, but you don't read carefully.
Both the rooms and the guests are infinite as a pairs.
Once you take the guests out of the rooms, and try to pair them again, you loose the infinity, and that's why it is wrong to do it.
The rooms became with one more than the guests, the moment we moved them out with two numbers up.
Remember?
So, as long as there is no infinity, we can have last room.

12. Jan 20, 2014

jcsd

The point is that the definition of an infinite set is one for which there is a bijection from itself to a proper subset. You can't get around the fact there's always a way to make more room as it's trivial from the assumption that the number of guests and the number of rooms are both |N|.

13. Jan 20, 2014

Office_Shredder

Staff Emeritus
Sissoev, so your claim is that as soon as the guests shift around, the number of rooms in the hotel changes from being infinite to finite?

14. Jan 20, 2014

Staff: Mentor

No, you don't "lose the infinity" so it's not wrong.
There's a big difference between two finite sets and two infinite sets that you're missing. Consider these finite sets: A = {1, 2, 3, 4, 5} and B = {2, 4, 6, 8}. Clearly there is one more element in set A than in set B, so set A is larger.

With infinite sets things don't work this way. Suppose C = {1, 2, 3, 4, ...} and D = {2, 3, 4, ... }. If we pair 2 in C with 2 in D, and 3 in C with 3 in D, and so forth, it would appear that C has more elements than D, but this is not true. With infinite sets, all you have to do is to show that there is a one-to-one mapping between the two sets. If there is, the sets have the same cardinality.
For my example, the mapping from set C to set D is 1 --> 2, 2 --> 3, 3 --> 4, and so on. If you tell me any number in set C, I can tell you what it maps to in set D. Conversely, if you tell me a number in set D, I can tell you the corresponding element in set C.

15. Jan 20, 2014

Sissoev

Hahaha :rofl:
No, Shredder, my claim is that two infinite sets can be paired only once, because if you try to do second pairing, you'll fall in to paradoxes like rooms appearing from nowhere and breaking the infinity.
How about, emptying all the odd number rooms?
We'll get infinite occupied rooms + infinite empty rooms from two sets which were perfectly paired.
Don't you find it disturbing?

16. Jan 20, 2014

Office_Shredder

Staff Emeritus
When you say things like
it sounds like you think the number of rooms is finite.

Let's stop talking about the hotel problem, because it is an analogy that apparently causing you trouble. The point is that infinite sets are kind of weird if you don't think about them the right way. Consider the set of all natural numbers, and the set of all even numbers. On the one hand, the natural numbers are "obviously" bigger. But now suppose that I have a set X, and I multiply every element in X by 2 to get a new set Y. All I've done is re-label the elements in my set X, so "obviously" X has the same size as Y. So from one perspective it is obvious that the evens and natural numbers are a different size, from another perspective they are the same size. Which is correct?

It turns out they are the same size. The best mathematical way of comparing two infinite sets is to figure out if there is a function from one to the other that is one-to-one and onto, i.e. a perfect pairing between them. It is well known that if two sets have a perfect pairing, there are also lots of ways to give a non-perfect pairing (in fact, a set is infinite if and only if it has a non-perfect pairing, i.e. a one-to-one but not onto function, with itself). A lot of people have trouble wrapping their heads around this but it is the fundamental tool in set theory for comparing sets, and leads to a very rich theory of sets.

In the hotel example, the guests are the natural numers, and the rooms are also the set of natural numbers, and describing how guests stay in rooms is the same as describing a function from the natural numbers to the natural numbers. Sometimes these functions are not onto, sometimes they are not one-to-one, but it doesn't change the fact that both copies of the natural numbers are the same size and can be paired up in a lot of ways.

17. Jan 20, 2014

Staff: Mentor

There is no requirement that a pairing be unique.
Again, this is what makes infinite sets fundamentally different from finite sets.
No, I don't.

If you read further about the Hilbert Grand Hotel, you'll see that the story continues when a very large bus (containing an infinite number of passengers) arrives.

The hotel is already full, but the manager comes up with a plan to accommodate the new arrivals. He asks each of the current guests to move from their room to the room whose number is two times their old room number. So the guest in room 1 moves to room 2, the guest in room 2 moves to room 4, and so on. This frees up rooms 1, 3, 5, ..., and the new arrivals can be given the odd-numbered rooms.

18. Jan 20, 2014

jcsd

But your missing the point, the definition of an infinite set is a set for which there exists a bijection between itself and a proper subset. Or other words an infinite set by definition is one in which it is possible to remove some members from the set to create a new set, but to still be able to pair the old set and the new set so that every member is paired. This trivially leads to the conclusion that given two infinite sets where every member of one set can be paired to a single member of the other set without leaving any unpaired members, it is possible to remove some members from one set and to still be able to pair them without leaving any unpaired members.

This is slightly counterintuitive as we can't do the same thing with finite sets, but if there was no difference between the properties of finite and infinite sets then we wouldn't be able make the distinction between the two.

19. Jan 20, 2014

Sissoev

I understand, Mark, but in the example I gave you, I mapped the rooms with the guests in front of them, and we still had one empty room.
You'll tell me to move the guests one room back, in order to fix the infinity, but I'll say NO, I've already mapped them and I have one extra room.
Who is right then, you or I?

20. Jan 20, 2014

Staff: Mentor

Infinity is not being "broken" so it doesn't need to be "fixed."
In this thread, pwsnafu, Office_Shredder, jcsd, and I are all telling you that you're wrong. We are also telling you why you are wrong. Please go back and carefully reread what we have been saying.

21. Jan 20, 2014

phinds

Sounds to me like you are still insisting, despite having been told repeatedly that it's wrong, that infinity plus 1 is not the same as infinity and infinity minus one is not the same as infinity, whereas they are both exactly the same.

22. Jan 20, 2014

Sissoev

OK, I understand and thank you all
Now my question is: Why Hilbert didn't give the simplest answer; unpair the set, add as much as you want and pair it again?

23. Jan 20, 2014

Staff: Mentor

That's exactly what happens. Each time there is a pairing between the occupants and the hotel rooms.

Person1 --> Room 1
Person2 --> Room 2
...
PersonN --> Room N
etc.
There is a one-to-one pairing between occupants and rooms.

Another guest arrives. Where should he go? The hotel manager asks each person who already has a room to move to the next higher numbered room. The pairing is now like so:
New person --> Room 1
Person1 --> Room 2
Person2 --> Room 3
...
PersonN --> Room N+1
etc.
This is also a one-to-one pairing between occupants and rooms. For each person I can say what room he or she is in, and for each room, I can say who is in the room.

Now for the sake of simplicity in the next step, let's renumber the people: Person1, Person2, etc.

At this time a bus with an infinite number of people arrives. What to do? As already mentioned, the manager asks each room occupant to move to the room whose number is two times his/her current room number. This frees up rooms 1, 3, 5, ..., all the odd-numbered rooms. The people from the bus file in and each person is assigned one of the odd-numbered rooms.

The pairing is now (BP - person from bus, P = person already present):
BP1 --> Room 1
P1 --> Room 2
BP2 --> Room 3
P2 --> Room 4
...
BP_N --> Room 2N-1
P_N --> Room 2N
etc.
This too is a one-to-one pairing. For each person I can say what room he or she is in, and for each room, I can say who is in the room.

24. Jan 20, 2014

Sissoev

Thanks Mark!
Very good explanation.

Now, I understand that the result of infinity minus any number is still infinity, but I still cannot wrap my mind around subtracting from paired sets.
Although infinity as number has infinite value, when paired it's bound to the other side as equal value (size).
Let's take Galileo's argument that S = {1,4,9,16,25,...} is the same size as N = {1,2,3,4,5,...} because there is a one-to-one correspondence: 1 ⇔ 1, 2 ⇔ 4, 3 ⇔ 9, 4 ⇔ 16, 5 ⇔ 25, ...
If we subtract 1,2,3,4,5 from N it will still be infinite on its own, but it will be with 5 less than S (smaller size), which will brake the pairing.
I wonder how to deal with that

25. Jan 20, 2014

Staff: Mentor

No, it won't be a smaller set with 5 numbers removed. You're still thinking along the lines of finite sets.

It doesn't matter if we break a pairing when we remove or add some elements to one of the sets. All that we need to do is to establish a new pairing that is also one-to-one. Here's a pairing of the set {6, 7, 8, 9, ...} with {1, 4, 9, 16, ...}.
6 ⇔ 1
7 ⇔ 4
8 ⇔ 9
9 ⇔ 16
....
n ⇔ (n - 5)2
...