Hilbert's paradox of the Grand Hotel - An easier solution?

[Mark44]

Unless you add quantum physics to the mix, then I might observe that, statistically, you've suddenly crossed the threshold :D Okay, I'm not making much sense.

No need for physics here, quantum or otherwise.

 

[valenumr]

Moving all of the current occupants to a room one number higher will take some finite, nonzero amount of time, so if you have to do this operation for an infinite number of new arrivals, it will take an infinite amount of time. The simpler way, moving each current occupant to the room number that is twice their previous room number, also takes a finite amount of time, but it happens only once.

Why not? Tell me a positive integer room number, and I'll tell you whether it has an occupant. Repeat until you get tired.
There is a trivial isomorphism between the set of current occupants and the set of positive integral hotel room numbers. Each person has a room, and each room has a person. That's what the statement "the hotel is full" means.

I still don't see how time applies to the question. Its not really a ln element of the "paradox" as far as I can see.

But to the latter point, I would saying implying "each" to infinite sets is sketchy. It implies the rooms and guests are finitely enumerable. We can't really say infinity == infinity. What's the difference between 3*inf / inf vs. 100*inf / inf?

 

[valenumr]

Moving all of the current occupants to a room one number higher will take some finite, nonzero amount of time, so if you have to do this operation for an infinite number of new arrivals, it will take an infinite amount of time. The simpler way, moving each current occupant to the room number that is twice their previous room number, also takes a finite amount of time, but it happens only once.

Why not? Tell me a positive integer room number, and I'll tell you whether it has an occupant. Repeat until you get tired.
There is a trivial isomorphism between the set of current occupants and the set of positive integral hotel room numbers. Each person has a room, and each room has a person. That's what the statement "the hotel is full" means.

There is a trivial isomorphism of (R>=0, +) and (R, *). How is that relevant?

 

[PeroK]

I'm not sure how time comes into play with the thought experiment. I hadn't thought about that previously.

Let's assume we have an empty hotel with a room for every positive integer and an ordered list of a countably infinite set of guests. If it takes one minute to accommodate each guest, then each guest gets their room sometime. The 60th guest gets their room after an hour; the 1440th guest after one day; and the millionth guest in less than two years.

Everyone on the list knows when they will get their room. Everyone gets a room eventually. Although, of course, there is never a time when everyone has a room!

Alternatively, the hotel has a process where they may accommodate the first guest in a minute, the next guest in 30 seconds, the next in 15 seconds, and they can continue getting faster and faster indefinitely. Now, everyone will be accommodated within 2 minutes.

 

[valenumr]

Let's assume we have an empty hotel with a room for every positive integer and an ordered list of a countably infinite set of guests. If it takes one minute to accommodate each guest, then each guest gets their room sometime. The 60th guest gets their room after an hour; the 1440th guest after one day; and the millionth guest in less than two years.

Everyone on the list knows when they will get their room. Everyone gets a room eventually. Although, of course, there is never a time when everyone has a room!

Alternatively, the hotel has a process where they may accommodate the first guest in a minute, the next guest in 30 seconds, the next in 15 seconds, and they can continue getting faster and faster indefinitely. Now, everyone will be accommodated within 2 minutes.

I guess I've never seen the question formulated with time as a parameter. I always saw it as a comparison of infinities and nothing more. I'm not sure how much it changes things with constant time, I'll have to think about it. But in the immediate, I suppose it could be divergent timewise.

 

[PeroK]

But to the latter point, I would saying implying "each" to infinite sets is sketchy. It implies the rooms and guests are finitely enumerable. We can't really say infinity == infinity. What's the difference between 3*inf / inf vs. 100*inf / inf?

This is not about normal addition. Infinity is not a real number subject to the laws of arithemtic. That's a critical point.

This is about mappings between infinite sets. And, that mappings between infinite sets are much more conceptually rich than mappings between finite sets.

For example, the set of positive even numbers is clearly a proper subset of the set of all positive integers. But, there exists a bijection (one-to-one and onto map) from one set to the other between them. In mathematical terms, two sets have the same cardinality if there exists a bijection between them. It's not the case that they must have different cardinality because one has a bijection to a proper subset of the other.

With finite sets it doesn't matter how you count. With infinite sets, you need to be more careful.

The example I gave was that if everyone is outside the hotel and they decide that the women should go in first, then it's clear that none of the men will ever get a room. As the infinite set of women will fill the hotel.

But, if we alternate between the sets of men and women, then everyone gets a room.

 

[valenumr]

This is not about normal addition. Infinity is not a real number subject to the laws of arithemtic. That's a critical point.

This is about mappings between infinite sets. And, that mappings between infinite sets are much more conceptually rich than mappings between finite sets.

For example, the set of positive even numbers is clearly a proper subset of the set of all positive integers. But, there exists a bijection (one-to-one and onto map from one set to the other) between them. In mathematical terms, two sets have the same cardinality if there exists a bijection between them. It's not the case that they must have different cardinality because one has a bijection to a proper subset of the other.

With finite sets it doesn't matter how you count. With infinite sets, you need to be more careful.

The example I gave was that if everyone is outside the hotel and they decide that the women should go in first, then it's clear that none of the men will ever get a room. As the infinite set of women will fill the hotel.

But, if we alternate between the sets of men and women, then everyone gets a room.

I sort of? Get your gist, but it still shouldn't matter. You can apply your relation to the set of men and the set of women as well as to the rooms recursively.

On point, if we call men odd and women even, but only have even rooms, we can just multiply both groups by two, and still have enough rooms for all.

 

[PeroK]

I sort of? Get your gist, but it still shouldn't matter.

It does matter. Not every 1-1 mapping between countable sets is onto. And not every onto mapping is 1-1.

If you're not careful you end up with two or more people to a room; or people with no room. Of course, you can always fix your process. But, the point is that not all processes work.

Unlike a finite hotel where you can ask the guests just to grab a room and it'll sort itself out.

 

[valenumr]

I sort of? Get your gist, but it still shouldn't matter. You can apply your relation to the set of men and the set of women as well as to the rooms recursively.

On point, if we call men odd and women even, but only have even rooms, we can just multiply both groups by two, and still have enough rooms for all.

Well, that's not exactly correct.

 

[valenumr]

Yeah, my example totally put two people in every other room.

 

[valenumr]

Yeah, my example totally put two people in every other room.

Oh, I should go sleep now. The analogy was just fine. 1 -> 2, 2 -> 4, 3 -> 6, etc, etc.

 

[Lars Krogh-Stea]

Heres a link to a Youtube video that tries to explain how the hotel can become full when a bus with infinite number of people with names consisting of infinite combinations of the letters A.and B (uncountable).

How An Infinite Hotel Ran Out Of Room - Veritasium

At the point where he says to flip letters from the table diagonally, to make a name that is not in the list. Wouldn't that just be the next name on the list? An so on, infinitely? I feel it's like counting the first part of an countable infinity, and being interrupted by someone saying "Hey, you haven't said this (higher) number yet!"
Or is that exactly the point of an uncountable infinity, that you can always add to it. It seems you can also always add to a countable infinity? I mean, if you make a list of all countable numbers and flip single digits diagonally too..

 

[PeroK]

Heres a link to a Youtube video that tries to explain how the hotel can become full when a bus with infinite number of people with names consisting of infinite combinations of the letters A.and B (uncountable).

How An Infinite Hotel Ran Out Of Room - Veritasium

At the point where he says to flip letters from the table diagonally, to make a name that is not in the list. Wouldn't that just be the next name on the list? An so on, infinitely? I feel it's like counting the first part of an countable infinity, and being interrupted by someone saying "Hey, you haven't said this (higher) number yet!"
Or is that exactly the point of an uncountable infinity, that you can always add to it. It seems you can also always add to a countable infinity? I mean, if you make a list of all countable numbers and flip single digits diagonally too..

The point is that if two sets have the same cardinality then there exists a bijection between them. The diagonal proof shows that if we assume a bijection, then we reach a contradiction in terms of a name that is not on the list. You can't turn round and say: let's use a different bijection where that name is on the list. If a bijection exists, then you can use it and stick to it.

 

[jbriggs444]

If you built a hotel with a room for every real number, what would you put on each door to identify the room?

A scratch of an exact length.

 

[Mark44]

But to the latter point, I would saying implying "each" to infinite sets is sketchy. It implies the rooms and guests are finitely enumerable.

No, not sketchy. The rooms and guests are infinite in number, but they are countably infinite. I already demonstrated how to determine whether the hotel was full; i.e., each room as a guest in it, and each guest has a room.

We can't really say infinity == infinity.

Right, and I am not doing this.

What's the difference between 3*inf / inf vs. 100*inf / inf?

None, really, as both are not well defined.

There is a trivial isomorphism of (R>=0, +) and (R, *). How is that relevant?

I have no idea what you're trying to say here.

 

[Mark44]

How I remember Hilbert's Hotel being presented is with these scenarios:

• Hotel is full, and one new guest arrives. Solution: each current guest is asked to move from room N to room N+ 1, thus freeing room 1 for the new arrival.
• Hotel is full, and M new guests arrive. Solution: each current guest is asked to move from room N to room N+ M, thus freeing rooms 1 through M for the new arrivals.
• Hotel is full, and a bus with an infinite number (countably infinite) of passengers arrives. Solution: each current guest is asked to move from room N to room 2N, thus freeing rooms 1, 3, 5, etc. for the new arrivals.

 

[Lars Krogh-Stea]

How I remember Hilbert's Hotel being presented is with these scenarios:

• Hotel is full, and one new guest arrives. Solution: each current guest is asked to move from room N to room N+ 1, thus freeing room 1 for the new arrival.
• Hotel is full, and M new guests arrive. Solution: each current guest is asked to move from room N to room N+ M, thus freeing rooms 1 through M for the new arrivals.
• Hotel is full, and a bus with an infinite number (countably infinite) of passengers arrives. Solution: each current guest is asked to move from room N to room 2N, thus freeing rooms 1, 3, 5, etc. for the new arrivals.

I follow you on these steps, but in the video from Veritasium they present a bus with infite number of people whose name is an infinite combination of the letter A and B. This is presented as an uncountably infinite group of people (trying to stay focused here..). Let's assume their names consisted of an infinite combination of the numbers 0 and 1 instead of A nd B. The buildup of that list would be exactly the same. Then let's use binary to count the rooms and put "digital" room numbers over the door. Doors would be named 00...000, 00...001, 00...010, 00...011, 00...100 and so on. I can't imagine a scenario where there is a person who can't find a hotel room where the number over the door matches his name. Surely the size of the hotel can not change, depending on what number system you use to count/name the rooms?

 

[PeroK]

I follow you on these steps, but in the video from Veritasium they present a bus with infite number of people whose name is an infinite combination of the letter A and B. This is presented as an uncountably infinite group of people (trying to stay focused here..). Let's assume their names consisted of an infinite combination of the numbers 0 and 1 instead of A nd B. The buildup of that list would be exactly the same. Then let's use binary to count the rooms and put "digital" room numbers over the door. Doors would be named 00...000, 00...001, 00...010, 00...011, 00...100 and so on. I can't imagine a scenario where there is a person who can't find a hotel room where the number over the door matches his name. Surely the size of the hotel can not change, depending on what number system you use to count/name the rooms?

We have had a lot of threads here started by people who disbelieve/don't understand the diagonal proof.

If you really want to debate the foundations of set theory and mathematical logic, then you should perhaps have started a new thread.

The diagonal proof has always seemed very simple to me. If you understand the basics of mathematical logic, there's not much to explain.

Note that for an infinite sequence, there is no last number. That's the definition of its being infinite. If there is a last digit, then (by definition) it's a finite sequence.

 

[Mark44]

I haven't watched the video, but the distinction they're making is that it's impossible to get a 1-to-1, onto pairing (i.e., an isomorphism) between a countably infinite set (the hotel rooms) and an uncountably infinite set of new guests. This is the same as the difference between the set of positive integers and the set of real numbers in, say, the interval [0, 1].

 

[valenumr]

How I remember Hilbert's Hotel being presented is with these scenarios:

• Hotel is full, and one new guest arrives. Solution: each current guest is asked to move from room N to room N+ 1, thus freeing room 1 for the new arrival.
• Hotel is full, and M new guests arrive. Solution: each current guest is asked to move from room N to room N+ M, thus freeing rooms 1 through M for the new arrivals.
• Hotel is full, and a bus with an infinite number (countably infinite) of passengers arrives. Solution: each current guest is asked to move from room N to room 2N, thus freeing rooms 1, 3, 5, etc. for the new arrivals.

Right. So is there any question that any of these cases are problem? Seems fine to me!

 

[Mark44]

Right. So is there any question that any of these cases are problem? Seems fine to me!

Right, no problem. My point was that instead of dealing with new arrivals from a bus with an infinite number of passengers, one at a time, it makes more sense to deal with them in one operation. Namely, moving each current guest in room N to room 2N, which I described in the third bullet point.

 

[PeroK]

Right. So is there any question that any of these cases are problem? Seems fine to me!

Once you strip away the baggage of the Hilbert Hotel, you find that all we are saying is that the following are well-defined 1-1 functions from $\mathbb N$ into $\mathbb N$:
$$f(n) = n + m \ \ (\text{for some fixed} \ m)$$$$f(n) = 2n$$
And these are fairly basic mathematical constructions.

 

[Lars Krogh-Stea]

Okay, I'm not disbelieving anything you said. And I really appreciate the time you've spent enlightening me about infinite numbers. Thank you!
I just had an extra question, after seeing the video. You don't have to answer it of course, but i'd be grateful if you did.

They present this scenario as an uncountable infinte:

An infinitely long bus with an infinite amount of passengers. This bus doesn't have numbered seats as in the example where you draw a diagonal line back and forth across the spreadsheet and "pull the string straight". Instead people have an infinitely long name that consists of the letters A and B. It would best if you saw the video.. I can't understand why a list of infinitely long series of A and B is different (not countable) from a list of infinitely long series of 0 and 1 (which is countable). Is it just by definition? Or is it so that a binary number can not be infinitely long, by definition?

 

[PeroK]

I can't understand why a list of infinitely long series of A and B is different (not countable) from a list of infinitely long series of 0 and 1 (which is countable). Is it just by definition? Or is it so that a binary number can not be infinitely long, by definition?

They are the same set, just with different labels. The set of all binary infinite sequences is uncountable. That's what the diagonal argument proves.

 

[Lars Krogh-Stea]

They are the same set, just with different labels. The set of all binary infinite sequences is uncountable. That's what the diagonal argument proves.

Okay, just so I'm sure I understand (remember, I'm scandinavian, english is not my native language). You can count to infinity in ordinary numbers, like this:
1
2
3
4
5
6
But not in binary numbers, like this (the 00...00 in the start is there because each line should be infinitely long, but this doesn't matter when counting as leading zeros in a binary number doesn't affect the number it represents)
00...00001
00...00010
00...00011
00...00100
00...00101
00...00110

How is this set not countable, when you actually do count, but in binary notation?

If it's more pertinent to start a new thread, I'll do so :)

 

[PeroK]

00...00001
00...00010
00...00011
00...00100
00...00101
00...00110

How is this set not countable, when you actually do count, but in binary notation?

If it's more pertinent to start a new thread, I'll do so :)

First, those strings are all finite, not infinite.

Second, you cannot map all infinite decimals to integers. E.g.

$0.333 \dots$ would map to $333\dots$, which is not an integer - unless the string is finite.

In other words, the decimal representation of each positive integer is a finite string. Whereas, the set of all real numbers between $0$ and $1$ involves infinite strings of digits.

 

[Lars Krogh-Stea]

First, those strings are all finite, not infinite.

But how can a string of A's and B's be infinite, but a string of 1's and 0's can not, when you literally just replace the A's with 0's and the B's with 1's? If you have an infinite number of strings made of 0's and 1's, one of the strings would be an infinite number of 0's with a 1 at the end. This would code as decimal 1. Another string would be an infinite number of 0's with two 1's at the end, and this would code as decimal 3. The calculation would be; 1*1+1*2+0*4+0*8+0*16...to infinity. No matter how many leading 0's you add, this number would never be anything other than 3.
If it's the "with a 1 at the end" that is the problem, think of a binary number as written from right to left. The 1 is at the start, and the number extends infitely to the left.

 

[PeroK]

But how can a string of A's and B's be infinite, but a string of 1's and 0's can not, when you literally just replace the A's with 0's and the B's with 1's?

That's not what I'm saying:

$0.010101 \dots$ is an infinite string of ones and zeros. But, if you remove the $0.$, you are not left with an integer:

$010101 \dots$ is not an integer. All integers are represented by finite strings; whether it's $0$ and $1$ or $A$ and $B$.

 

[Nugatory]

The hotel paradox is full of insights when presented to the academic audience, but is presented like a hard riddle when presented by common people to common people.

That's a problem with the presentation, not the audience. In the hands of a competent presenter, Hilbert's Hotel is the best tool I've seen for explaining infinity to laypeople (loosely speaking, the intellectually curious who find the concept fascinating and don't talk the language of @PeroK's spot-on #54 above).

Just apropos of nothing... I find myself missing Martin Gardner...

 

[Lars Krogh-Stea]

That's not what I'm saying:

$0.010101 \dots$ is an infinite string of ones and zeros. But, if you remove the $0.$, you are not left with an integer:

$010101 \dots$ is not an integer. All integers are represented by finite strings; whether it's $0$ and $1$ or $A$ and $B$.

But 010101 is a binary representation of an integer (1*1+0*2+1*4+0*8+1*16+0*32=21). So if you order an infinite set of infinite binary strings, from low binary value value to high binary value, you will in fact be counting by integers, to infinity. Thats why they will map directly to the number of hotelrooms, to infinity. If I'm still not getting it, I'll give up.. As I've previously said, I have no prior knowledge of numbers. Just thought it would be fun to have a little dive into it.