Very cool. I'm still trying to wrap my head around what makes ABAB uncountable though. I understand the diagonal bit (its excluding them one by one), but it almost feels like that uncountable infinity is defined by a rule ("every combination") while the doors are defined by a different rule ("every item going upwards in count")
Ye. It is quite bogus to claim to be able to accommodate new guests even though the hotel is full, no matter how many rooms there are. In that case the hotel is not full ...
That's the paradox! There are no empty rooms, and yet the hotel can accommodate arriving guests. Whether the hotel is full depends on your definition of "full". This is quite different from the finite hotel case.
Well, if the hotel isn’t full then there must be a vacant room. But the first room is occupied, the second room is occupied, … If you can’t find a vacant room then the hotel must be full!
I think this is a fair point - if there's a one person to one room correlation, then moving people around isn't exposing any additional empty rooms.
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?
If collisions can happen they will happen with probability 1, since there is infinite opportunity. There's also the issue of there not existing a uniform distribution on the integers, so it's hard to get the chances of collision low in the first place.
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.
Infinity (both the "cardinality of sets" kinds and the "limit of an increasing/decreasing function" kind) are generalizations, not abstractions; and both have proven extremely fruitful generalizations both theoretically and practically.
Anything that deals with calculus has infinities underneath. Much of the modern technology wouldn’t exist if we wouldn’t know calculus.
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.
The infinity is an important concept which appears in most areas of the maths and physics. The maths is full of ideas that may seem counterintuitive (eg. "imaginary unit" - the square root value of -1), but as long as they are precisely defined, they can be used in reasoning that gives practical results.
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.
Calculus, differential equations, integrals, all rely on iterating towards infinite sums of infinitesimal values. It seems a bit dodgy at first but can be made rigourous by giving precise, consistent definitions of different infinite values and the operations between them. These are used extensively in many fields. This can be done by using limits "towards infinity / towards zero", but it can also be done more directly with precise defintions of infinities and infinitesimals: https://en.wikipedia.org/wiki/Nonstandard_calculus
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.
There is a precise, consistent definition of what it means for a set to be infinite. How is this a bad abstraction more than other mathematical definition?
Precision doesn't matter. Software abstractions, once coded, are precise. The problem is with human thinking. If the mind can't grasp at all times all the relevant technicalities that come with an abstraction, then the abstraction is bad.
This is a very anthropocentric view of mathematics. Why should we expect mathematics to be amenable to a puny human mind grasping all relevant technicalities of a concept?
Most of mathematics is abstractions invented by humans to make math more comprehensible by humans. E.g. you can do differential equations without complex numbers, but they make life so much easier. Infinity is a mathematical concept invented by humans to make thinking about large numbers easier in some cases, but it's deceptive in other cases.
Which cases? Is there mathematics of infinity that you're privy to that are unknown to mathematicians?
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.
The set theoretic definition of infinity did not come about in order to make thinking about large numbers easier. You are wrong in your perception on this.
The set-theoretic definition of infinity came about to make thinking about small numbers easier.
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.
What technicalities with the definition of an infinite set can't be grasped by the mind? The definition is quite simple and easy to understand (for a mathematician).
Infinity actually pops up in the context of stream processing, since often times real computers need to process arbitrary amounts of data with finite memory resources. Sometimes the data is too big to fit into memory all at once, or maybe the data moves too slowly to all be available immediately. Because there is no upper bound to how long a stream may be, streaming algorithms tend to be designed to be able to handle infinite amounts of data which is a property that comes in handy surprisingly often.
I find it somehow interesting that the reordering procedure also never terminates (as is of course expected for an iteration over an infinite set)
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.
This depends on if you count "information propagation" time or not. For example, if you inform every guest about the pairing function when they check in, and moving from one room to any other takes finite time, all you need is a single "please move now" bit and each guest can move simultaneously.
(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.)
You’re the manager, and you know an infinite number of guests are checking in tomorrow. how many receptionists do you schedule to be on duty when they arrive?
> moving every guest from their current room n to room n+1
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.
That's sort of the entire point of the paradox. Every room is full at the start. Not "somehow at least one is not", but every single room is full. Then, by having guests move to different rooms, you can rearrange such that there is an empty room.
The guests are markers to indicate a bijective function between room numbers. Each guest represents a (before, after) tuple.
A point of a paradox can also be to invalidate the assumptions made. I mean, mathematicians are getting away with way too much nonsense by using diffucult words.
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.
I think I would call that a contradiction rather than a paradox. A conclusion that is a contradiction means that one of your starting assumptions is incorrect. A conclusion that is a paradox means that your intuition about the problem was incorrect.
No, you are trying to use your intuition for finite sets on infinite sets. Subsets of infinite sets can have the same size as the entire set. There are as many odd natural numbers as there are natural numbers even if your intuition tries to tell you that this can not be true because the natural numbers additionally contain all the even natural numbers.
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 ...
Which number are you adding? In the problem, you are adding 1 to the set, but it's already there, so you remove it by replacing it by adding 2, and n by n+1 for all n
Ye well my point is there is no number to add that is not allrady in the set and that the hotel clerk can't change that by rearranging guests. I.e. there are no guests that are not allready checked in (each guest need a room with a natural number on the door).
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.
Just imagine all the even numbers are currently in the hotel, zero is in room zero, two is in room one, four is in room two...2n is in room n. Now all the odd numbers arrive at the hotel, maybe one after another, maybe all at the same time, but you can apply one of the procedure to fit them in. You must not confuse the numbers occupying each room with the numbers of the rooms, the room numbers are all the natural numbers but they can all be occupied by the even numbers alone. Because, as I said, there are as many odd numbers as there are even numbers as there are natural numbers.
It's not really a paradox, just some things that work for finite sets no longer work for infinite sets. The sets { A, B, C, D } and { 1, 2, 3, 4 } have the same size because they both have four elements. Another way to see that they have the same size is that you can provide a one to one mapping between them, for example A - 4, B - 3, C - 2, D - 1.
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.
No, there is no reordering wave, it happens all in parallel. Everyone steps out of his room at the same time, everyone walks to his new room, whether it is n + 1, n + k, 2n, or whatever, and everyone steps into his new room at the same time. So it is not what you probably imagined, that the person steps out of room 1, knocks on the door of room two, tells the person in there to move to room three, and so on.
There is a screen in each room that shows you a message when to move where. Or you get a call from the receptionist, but not an individual call but one broadcasted to all rooms, announcing the formula for your new room number. Make up whatever you want, its a thought experiment.
It's a very unique universe that quite a bit different that ours - It would require an infinite amount of energy to communicate that call leading to infinite entropy. Given that the moves happen instantaneously, the first guest to arrive would instantly cause the heat-death of this universe.
They all hear an announcement at the same time via the hotel’s speaker system. (And we’re already ignoring so many laws of physics that the speed of light is the least of our problems.)
What kind of waves? I guess you could at least have a light source that periodically gets brighter and dimmer and a detector at the other end of the universe would detect the brightness oscillation and it would not really make any difference whether the light propagates with an finite or infinite speed besides of course the propagation time.
> 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?
Can you explain how all of that would follow? Naively, if we take the limit of c to infinity, aren’t we simply back to Newtonian physics? Why wouldn’t a pendulum work, for example?
Just make each room half the size of the preceding one and you can fit all the rooms in twice the length of the first room. Also solves the problem that, when moving from room n to 2n, the guy in room one has only to walk to next room while the poor guy in room Graham's number has quite a journey ahead of him. Please address complaints about narrow rooms that can not even fit a single proton to the manager.
I don't see an issue if you want the communication to not be instantaneous. The only requirements i see are that it has to be faster than the guests, so that everyone's room is empty when they get there.
Why assume that the hotel's hallway is strait? Maybe it has an infinite number of rooms all around a circular lobby, a lobby that grows in diameter/circumference every time someone books a room. The message from the desk (in the middle of the lobby) then hits every room at the same time. No waves. Just instant simultaneous movement in every room.
As soon as the hotel has taken in even a small infinity of patrons, this layout is not possible - a circle must have a finite circumference (and if we did try to generalize our definition of circle it would result also in an infinite radius).
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.
Maybe someone can help me understand, not a mathematician or engineer. It seems like the hotel is “full” but because there are infinite rooms, when new guests arrive they just move everyone to their room + 1 and make space at room 0.
I don’t think I understand the significance here, since it seems logical.
It is logical, and that's the point. It's simply explaining various properties of infinite sets and techniques for doing operations on them that are provably correct.
There are two ways you can define the hotel as being full:
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.
Stranger still is that one can find a rational number between any two irrational numbers, yet the irrationals vastly outnumber (are not countably infinite) the rationals (which are countably infinite).
When I was much younger this was the source of a lot of wonder for me. Both the rationals and the irrationals are dense in the reals, and yet the irrationals greatly outnumber the rationals.
I find this hard to follow. The "first" guest (who was in room 1, in the article) moves over one room. The "last" guest (showed as being in 'room n') has no room to go to; the hotel is full.
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.
That’s the difference between all the integers (from negative infinity to positive infinity) vs just the natural numbers (from 0 to positive infinity). You can have infinitely many guests starting from a particular first guest.
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..
Yep, this is what makes Hilbert's hotel (and infinity in general) counterintuitive. When we try to apply reasoning that's correct for finite sets to infinite sets, very often it becomes incorrect.
A similar observation is that there's exactly as many natural numbers [0, 1, 2, 3, ...) as integer numbers (the same, but with negatives: ..., -2, -1, 0, 1, 2, ...).
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:
Since this mapping ("bijective function") exists, we know that every number in one set has exactly one representative in the other set - so the set counts are identical.
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.
> "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
Now work diagonally through the digits:
0.[1] 1 1
0. 2 [2] 2
0. 3 3 [3]
and change those selected ones to other digits:
0.[2] 1 1
0. 2 [3] 2
0. 3 3 [4]
And pull those diagonals out into their own new number 0.[2][3][4] or 0.234, and add that in to the list:
0.111
0.222
0.234 <- new number
0.333
That number differs from the first entry in the first decimal position, from the second number in the second position, from the third number in the third position, ... and the Nth number in the Nth position, because those are the positions you changed in each one to make sure of it.
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. ]
Do you also see the First Incompleteness Theorem, or Halting Problem, as sleights of hand?
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.
"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."
The "paradox" stems from thinking of "infinity" as an amount, and treating it as somehow logically finite. Once you toss away the "logic" of the finite, there is no paradox at all.
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.
> 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.
> This is neither true nor false as it has no meaning. Whether countable or not, infinite sets do not have sizes to compare.
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.
> in a manner which corresponds pretty well to what people mean when they colloquially say "more" or "fewer"
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.
112 comments
[ 4.3 ms ] story [ 198 ms ] threadhttps://youtu.be/Uj3_KqkI9Zo
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.
[1] https://en.m.wikipedia.org/wiki/Ultrafinitism
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:
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.
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.
Cantor’s diagonal argument is an easy foray into uncountable cardinalities https://en.m.wikipedia.org/wiki/Cantor's_diagonal_argument
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..
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:
Since this mapping ("bijective function") exists, we know that every number in one set has exactly one representative in the other set - so the set counts are identical.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:
Now work diagonally through the digits: and change those selected ones to other digits: And pull those diagonals out into their own new number 0.[2][3][4] or 0.234, and add that in to the list: That number differs from the first entry in the first decimal position, from the second number in the second position, from the third number in the third position, ... and the Nth number in the Nth position, because those are the positions you changed in each one to make sure of it.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? :)
"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."
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.