Hilbert's Paradox of the Grand Hotel
en.wikipedia.org
en.wikipedia.org
So, if you stay in the hotel analogy, each additionally arriving guest will create a unique "reordering wave" that ripples through all the infinite rooms. This wave would keep going for all eternity.
So if the hotel had k additional guests check in at any time in the past, it will have k reorderings going on forever.
(That also makes the difference between finitely many additional guests and infinitely many more remarkable: you can also accomodate infinitely many additional guests with a single wave of reorderings)
Not sure if this is in any way a useful observation, but it made the whole hotel scenario somehow even weirder for me than it already was.
(If you don't assume you have instantaneous transmission and finite travel time, our unintuition about this also collides with unintuitive, unrelated, and very physically-real concepts like light cones - so I think it's within the spirit of the problem to assume we have them.)
They still haven't finished checking in the initial round of guests!
The whole setup of the paradox is bad. There a infinit amount of rooms, all are full, but somehow atleast one room is not. The guests and rooms operate under different rules.
The guests are markers to indicate a bijective function between room numbers. Each guest represents a (before, after) tuple.
The hotel paradox is essentially equivalent to:
I can add a natural number to the set of all natural numbers which is not in the set allready.In the hotel case, it would be like claiming I can add a natural number to the set of all natural numbers which is not in the set allready. All guest are allready at the hotel ...
Edit: I.e. the error in the paradox is assuming that there can be any more guests to check in when the hotel is full.
Hmm ... that is an interesting take on it. I.e. guests with even customer id:s can have all rooms.
Maybe I just have to accept the paradox to be a property of infinite sets by definition.
For infinite sets the first option no longer works, you can not write down a specific number for the number of elements in a set and then see that two sets have the same size because you wrote down the same number for both of them. But the second option still works, you can provide a one to one mapping between the elements of two sets, for example n - 2n to match all natural numbers with all even numbers. Each natural number n has an associated even number 2n and each even number 2n has an associated natural number n.
And this is then just the definition of what it means for two sets to have the same size, there is a one to one mapping between their elements. And this works for finite sets as well as for infinite sets. Everything else are consequences of that. Take the natural numbers and take the natural numbers with the first k of them removed, the two sets still have the same size because you can pair n with n + k even if it is against your intuition that the size of a set does not change when you remove some of its elements.
Any wave! Including sound waves.
> I guess you could at least have a light source that periodically gets brighter and dimmer
Would it even be possible to make a timer that periodically gets brighter and dimmer in a world with an infinite speed of light? Would the crystal oscillators in CPUs still work?
I believe that some processes (like nuclear decay) stop happening when there's an infinite speed of light. I guess my overall question is: does time still exist in a world with an infinite speed of light?
Maybe a hypersphere with finite bounds but infinite dimensions? My geometry is fairly poor but I think this is what is called, for reasons not directly related to the hotel paradox, a Hilbert sphere.
Normally we'd need to count things to say there's "as many" X as Y. But with infinities counting is a bit tricky. So, is the infinite count of natural numbers the same kind of infinity as count for integer numbers?
To check this, we need to see if for every number in one set we can assign exactly one number in the other set (and the other way around). It's actually pretty simple:
0 -> 0
1 -> -1
2 -> 1
3 -> -2
4 -> 2
5 -> -3
6 -> 3
...
What's interesting, if we look into real numbers (think: double in C, but without problems with approximation), there's much, much more of them. The infinite count of real numbers is much larger than the infinite count of integers. But let's keep it for another comment.
That is, beautifully, Cantor's diagonal argument, which goes: write some decimal numbers between two integers 0 and 1:
0.111
0.222
0.333
0.[1] 1 1
0. 2 [2] 2
0. 3 3 [3]
0.[2] 1 1
0. 2 [3] 2
0. 3 3 [4]
0.111
0.222
0.234 <- new number
0.333
If it's different from every existing decimal in at least the one place, it cannot be a duplicate entry seen before in the list you wrote down, it must be a new entry.
You can always change the first number in the first position because there's only a single digit there and nine more to choose from. You can always change the Nth number in the Nth position because 0.2 is really 0.20000000... so changing 0.2 in the 5th decimal place makes 0.2 into 0.20007 or etc. This makes the decimals longer, sub-dividing into increasingly tiny pieces, without end - infinitely.
Therefore with an infinity of integers, you can subdivide infinitely between any two of them.
You can take your infinite list of decimals between 0 and 1 and map the integers to them, 1 for the first entry, 2 for the second, 3 for the third, and pair up both infinities 1:1. And then have no integers leftover to map onto the infinity of decimals between 2 and 3, and again none left over for the decimals between 3 and 4, etc.
Conclusion: there are infinite integers, and infinite decimals, and there are more decimals than integers. The infinity of decimals is the larger infinity.
(Which makes some intuitive sense looking at single digit integers 0-9 on the left of a decimal point, fan-out to single digit 0-9 for each of those on the right of the decimal point. 10× more 2-digit decimals than 1-digit integers (of course). Infinite permutations of digits on the left of the decimal point, an infinite permutation of digits on the right for each starting permutation on the left, means infinity× more decimals than integers).
[ I wrote this more for the practise of pulling it out of memory and going over it, because doing that cements it more in my memory. It is one of the few bits of math I can more or less remember. It would surely be more beneficial and correct for you to read it elsewhere. This is the paradox of internet comments written for the author, not the reader. ]
Are there any other roads to “sizes of infinity” that are more palatable than the diagonalization argument?
Informally, the answer to your question is no - the Schröder-Bernstein theorem, which lets us order the size of sets, is sufficient to derive the law of the excluded middle. Therefore if you don't like the "trick" i.e. proof by contradiction (even given the contradiction is "actually constructed" in this case), and instead demand constructive mathematics, you will not be able to say much about relative cardinality.
"Much larger," or just barely, the smallest possible amount, larger? :)
Cantor’s diagonal argument is an easy foray into uncountable cardinalities https://en.m.wikipedia.org/wiki/Cantor's_diagonal_argument
ETA: For instance: One infinite set does not have "as many" or "more" or "less" members than any other infinite set. You cannot compare amounts, there are not "amounts" to compare.
Not exactly true - there are different infinities. For example, the number of integers is infinite, and the number of real numbers is infinite, but there are more real numbers than integers.
The number of integers is "countably infinite" and the real numbers are "uncountably infinite".
This is neither true nor false as it has no meaning. Whether countable or not, infinite sets do not have sizes to compare.
Granted, I know many mathematicians still prefer to understand uncountable sets to be those "that contains too many elements to be countable" which implies size. But the statement is still meaningless. Countability vs uncountability is really about something a bit more subtle with the axioms that we use to define sets in the first place.
Infinite sets do have cardinality, and cardinalities can be compared, in a manner which corresponds pretty well to what people mean when they colloquially say "more" or "fewer".
If you want to split hairs between "size" and "cardinality", that's your choice, but even Cantor himself used the term "size" in this manner.
I would argue that it does not correspond very well to what people mean when they say "more" or "fewer", and hence the apparent paradox of Hilbert's Hotel. That is, my original point was that thinking of infinite sets as having comparable sizes is the precise confusion that leads to the supposed paradox.
If you're specifically comparing cardinalities, "more" or "fewer" lose their "colloquial" meaning.
"Twice a week, Ken Jennings and John Roderick add a new entry to the OMNIBUS, an encyclopedic reference work of strange-but-true stories that they are compiling as a time capsule for future generations."
I don’t think I understand the significance here, since it seems logical.
1) The hotel is “full” if all the rooms are occupied.
2) The hotel is “full” if there is no way to rearrange the existing guests to leave an empty room.
These two definitions of “full” are equivalent for finite hotels. The ‘paradox’ is illustrating that these two definitions are not the same for infinite hotels. It serves as a useful reminder that there might be more “space” in infinite sets than we are used to in the finite case, and that if we are dealing with infinite sets we should keep in mind the fact that (1) and (2) (or whatever analogues are relevant for our problem) might be different, despite seeming the same based on our real-world experience.
I can only see a shift of guests being possible if you momentarily ignore the initial constraints.
I have trouble with that, though - if there's a "first guest", then I don't see there can't be a "last guest".. "room 1" and "room n" (as the article labels them) are equally arbitrary if there are infinitely many.
In that case I'd probably rephrase my original objection to say the "next guest" has nowhere to go, except when the they depend on the "next next" (etc.) guest finding a room in a "full" hotel - but I can see how that situation "never" comes up since they can pass the burden along infinitely.
I just feel like someday at the end of time, this poor unassuming new guest is gonna get cheated out of a room..
It seems we're using the 'hey-everybody-move' as a buffer to accommodate new guests.
Two questions:
Is it ok to think because there's an infinite amount of moving, this buffer is infinitely large?
Why can't we tell guests to just keep moving to random rooms? Would that also solve the problem? If you say no - random moves don't work - then I would propose that some of those random moves would fall into the outcomes of Hilbert's formula. Is that not sufficient?
It's an unphysical model, that only exists in abstract mathematics.
Any idea on if directing guests to move randomly would work as well as directing them to move in patterns?
For example you can assign an integer to each guest, and an integer to each room, and the "move" is just the function: guests --> rooms.
As long as this function is injective, then you do not put more than 1 guest in each room.
Then this is just the observation that you can put every guest in a room and still have some empty rooms (rooms not in the range of the function). For example, the deep and paradoxical function f(n) = n+1 corresponds to an assignment of every guest that used to be in room n to room n+1.
I guess if you want, you can think of a description of the function as a sequence of "moves" with people in an actual hotel, but then since the domain of the function is infinite you have to think of an infinite "number" of moves. Then you add time to the mix and carpet hallways or whatever, you start getting lost and saying the whole thing doesn't make sense, but that's only because you are stretching these metaphors beyond the breaking point when what is really being described by the "paradox" is that you can have an injective function from an infinite set to itself that is not surjective.
By the way, once you realize that, for example, when dealing with positive real numbers there exists functions of the form: f(x) = x + 1, then you see that this "hotel" doesn't even need countably infinite moves, it can have uncountably infinite moves. Just please stop trying to worry about the weight of the hotel or how the HVAC works and getting all tangled up in stretching metaphors past their breaking point.
Also, check out Fourier transform and try to rewrite it without infinities - https://bookdown.org/vshahrez/lecture-notes/fourier-transfor... . Without fourier transform we wouldn’t have mp3, and the whole field of signal processing if I’m not mistaken.
Without signal processing we would not have long distance digital communication.
But you can also make calculus without limits, using explicit definitions of infinitesimals (called non-standard analysis or non-standard calculus), and in some ways this is simpler to use.
You can approach it either way. As limits, or by extending the number system with particular consistent definitions of infinitesimals and infinities.
In practice using infinitesimals is often what people actually do when using calculus anyway, even when mentioning the limit in a sloppy hand-wave in the background, so it's good that non-standard analysis shows that the simpler method people actually use is usually logically coherent and gives the same answers as limits.
And even if some math concepts can't be applied to anything practical yet, we never know what will be used to formulate another theory about the stock market behaviour or processes inside the black hole.
Coming back to your question, here's an example: many math constants (pi, e) and functions (sin, cos) can be defined as infinite sums (series). They converge, getting closer and closer to the limit, but they never achieve it.
Using these series it's possible to calculate (in a calculator, Excel, Quake or CAD) values of these functions with any required precision.
Infinite series, where an infinite sequence is summed (or multiplied, or ...). Many useful things fell out of reasoning about entire infinite sequences as if they are a single unit. I like this video about a method Newton found how to calculate pi efficiently, from playing with infinite series: https://www.youtube.com/watch?v=gMlf1ELvRzc
Again it's possible to define everything about infinite series in terms of limits, but sometimes it's just a more useful thinking aid to think of infinite series as themselves. In a way, it's like dropping some unnecessary syntax sugar (the limits) as you realise you can still do useful things without it. And in fact it's possible to reason consistently about some kinds of divergent infinite series, where limits don't work but they are still logically consistent.
Complex exponentials. The discovery and proof of Euler's formula, eⁱˣ=cos(x)+i⋅sin(x) comes out of reasoning about infinite series, showing that it's a consistent and useful definition of a complex exponential. Nowadays we use these exponentials to calculate all sorts of things in engineering and physics, we just take them for granted because they work and everything fits together consistently.
Projective geometry, for example used in computer graphics. There is the concept of "point at infinity", which is actually represented by real values in a vector but in some respects you can think of it as representing "x/0" in the context of that geometry, and finding that further calculations using it still work out consistently to non-infinite results. Including the point at infinity as a value simplifies the system. Unlike with natural numbers where "infinity" is a complication that obeys different rules to numbers, the point at infinity in projective geometry removes edge cases and simplifies the rules.
Elliptic curve cryptography also uses the "point at infinity" concept which arises from a geometrical or algebraic interpretation of the elliptic curve operations, and like in projective geometry it's a useful and consistent value to include, which is done because it simplifies the system to include it.
Also I disagree that thinking about infinity is useful when thinking about large numbers. That seems to me to be a fallacy. Any finite large number is inconsequential, and might as well be a 'small' number for any practical purposes, compared to any infinity.
As trivial examples, if we reject this definition of cardinality, we can no longer speak of the natural numbers as a set (nor therefore even finite subsets of them), we would lose key set-theoretic definitions of both natural and real numbers, we could not talk set-theoretically about the domain/range of most interesting functions, etc. Honestly, that would be a much more confusing mathematical world than one with Hilbert's hotel or Banach-Tarski spheres.