Hacker News Reader

Comment by xg15 | Hacker News Reader

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.

View on HN

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.

And how is everyone supposed to know when to leave their room and where to go?

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

In a universe with an infinite speed of light, can there even be any kind of waves? Do physical waves not also propagate instantly?

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.

> What kind of waves?

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?

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?

The laws of physics get chucked out the window the moment you say "infinitely many rooms".

They always leave their room after 24hrs and go to the room next door?

I know we’re already assuming a hotel with infinite rooms but doesn’t this break causality by assuming FTL information propagation?

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.

We consider different universes with different properties to our own in mathematics, and indeed in physics, all the time.

Oh, I’m not arguing that the thought experiment is wrong. Just extending it in the direction of “reasons this doesn’t work in the real world”

Where would you even find the fuel for the infinitely-long bus! Mathematicians must be idiots.

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.

Distributed synchronisation is lost upon mathematicians.

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.

There’s no requirement for it to be instantaneous. It could be, buy it could also be sequential. The thought experiment works fine either way.

Alternately, the rooms can simply be renumbered with no guest motion.

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

> So if the hotel had k additional guests check in...

They still haven't finished checking in the initial round of guests!

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.

No, the paradox is that there are the same number of even natural numbers and natural numbers, yet the former is a strict subset of the latter.

Ye sorry I was refering to the hotel paradox. Edited.

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.

I am buying that.

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.

> the room numbers are all the natural numbers but they can all be occupied by the even numbers alone

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.

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.

Reply on news.ycombinator.com