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

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

 

[PeroK]

But 010101 is a binary representation of an integer (1*1+0*2+1*4+0*8+1*16+0*32=21).

That's a finite string. They represent integers.

We are interested in infinite strings! They don't represent integers.

 

[valenumr]

I'm kind of hating the way the internet works, but this just popped up in my news feed: https://www.cantorsparadise.com/hilberts-hotel-an-ingenious-explanation-of-infinity-1d1a79932080

 

[Lars Krogh-Stea]

That's a finite string. They represent integers.

We are interested in infinite strings! They don't represent integers.

I understand all this.. But are you also saying that in an infinitely large set of infinitely long strings (containing only 1's and 0's) the string 100000000... wouldn't exist, and the string 1010000000... wouldn't exist?

 

[PeroK]

I understand all this.. But are you also saying that in an infinitely large set of infinitely long strings (containing only 1's and 0's) the string 100000000... wouldn't exist, and the string 1010000000... wouldn't exist?

Those are infinite strings all right, but they are not integers.

I suspect the root of the problem is that you don't realize that those are not numbers.

 

[valenumr]

That's a finite string. They represent integers.

We are interested in infinite strings! They don't represent integers.

Oh, I think I once again get the gist of your statement. I was missing the flow of your argument.

 

[Mark44]

But are you also saying that in an infinitely large set of infinitely long strings (containing only 1's and 0's) the string 100000000... wouldn't exist, and the string 1010000000... wouldn't exist?

Every integer has its own place on the number line. Where would these go? The thing is, it's impossible to say, because we don't know how many zeroes are represented by the ellipses (...).

 

[PeroK]

And really, any binary string can be interpreted as a number.

Not as an integer. Only as a real number with a decimal point somewhere.

Every integer, $k$, has a decimal representation of the form:
$$k = k_0 + (k_1 \times 10) + (k_2 \times 10^2) + \dots + (k_n \times 10^n)$$For some finite $n$, where the $k_i$ are the digits (binary or otherwise).

And, therefore, the integers are represented by finite strings of digits.

Every real number, $x$, between $0$ and $1$ has a decimal representation of the form:
$$x = x_1 \times 10^{-1} + x_2 \times 10^{-2} + \dots$$Where $x_i$ form an infinite sequence of digits.

Therefore, the real numbers are represented by infinite strings of digits.

The OP's problem, I believe, is that he considers the following
$$k = k_0 + (k_1 \times 10) + (k_2 \times 10^2) + \dots$$To be an integer. Whereas, it is a divergent series and does not represent any finite number. Unless, of course, the $k_i$ are all zero after some finite value $n$. But, then we only have the equivalent of the finite strings. We don't have every infinite sequence.

 

[Lars Krogh-Stea]

Every integer has its own place on the number line. Where would these go? The thing is, it's impossible to say, because we don't know how many zeroes are represented by the ellipses (...).

I wrote them from left to right, so you would get what I mean. You say it's impossible to say how many 0's come after 1. But mirror the number and you would see that it doesn't matter. Written from right to left, they would be easy to order and map to room numbers. And thus, for every passenger on the infinitely large bus, you can find a room. One gets off the bus, his name is AABBBBBB... (or 11000000...) He will get room number 3 (the digits are flipped so it reads from right to left). If somewhere along the line of digits more 1's appear, a room number will be given accordingly. Next passengers name is ABABABBBBBB... He will get room number 13 and so on. You will need to repeat the process infinitely of course, but that applies to the other methods too. The point is that it is possible to map these names to room numbers. For every passenger that gets off the bus, you will have to read as many letters as you need to differentiate them and assign a room.

 

[PeroK]

I wrote them from left to right, so you would get what I mean. You say it's impossible to say how many 0's come after 1. But mirror the number and you would see that it doesn't matter. Written from right to left, they would be easy to order and map to room numbers. And thus, for every passenger on the infinitely large bus, you can find a room. One gets off the bus, his name is AABBBBBB... (or 11000000...) He will get room number 3 (the digits are flipped so it reads from right to left). If somewhere along the line of digits more 1's appear, a room number will be given accordingly. Next passengers name is ABABABBBBBB... He will get room number 13 and so on. You will need to repeat the process infinitely of course, but that applies to the other methods too. The point is that it is possible to map these names to room numbers. For every passenger that gets off the bus, you will have to read as many letters as you need to differentiate them and assign a room.

The digit 1 followed by infinitely many zeroes is not a (finite) number. We've been through all this so many times.

Veritasium is right. Georg Cantor was right. Every mathematician of the 20th and 21st Centuries was right. And you, I'm afraid, are wrong. No matter how many times you tell us that we cannot count, ultimately you are the one making the elementary errors.

 

[Lars Krogh-Stea]

The digit 1 followed by infinitely many zeroes is not a (finite) number. We've been through all this so many times.

Veritasium is right. Georg Cantor was right. Every mathematician of the 20th and 21st Centuries was right. And you, I'm afraid, are wrong. No matter how many times you tell us that we cannot count, ultimately you are the one making the elementary errors.

I'm not saying that.. I'm saying the digit 1 with infinitely many zeroes before it can be read as a binary number that you can map to room number 1. The digits 11 with infinitely many zeroes before it can be read as a binary number that you can map to room number 3.. And so on. You have already answered yes to the question, when I asked if these combinations would occur in the list. Thats why I said that if you mirror the list, so it reads from right to left, then it's possible to map the passengers to their rooms.