Relation between Hilbert's hotel and Cantor's proof of the uncountability of the continuum

Question

I am reading the wikipedia page about Hilbert's Grand hotel. There it says:

Hilbert's paradox is a veridical paradox: it leads to a counter-intuitive result that is provably true. The statements "there is a guest to every room" and "no more guests can be accommodated" are not equivalent when there are infinitely many rooms. An analogous situation is presented in Cantor's diagonal proof.

Now I wonder what Hilbert's Grand hotel has to do with Cantor's diagonal proof, since Cantor's diagonal proof is concerned with showing that the continuum has bigger cardinality than the natural numbers, but Hilbert's hotel seems to be about showing that certain countable sets are equinumerous. Could you clarify?

Answer 1

Cantor's diagonal proof can be imagined as a game: Player 1 writes a sequence of Xs and Os, and then Player 2 writes either an X or an O:

Player 1: XOOXOX

Player 2: X

Player 1 wins if one or more of his sequences matches the one Player 2 writes. Player 2 wins if Player 1 doesn't win.

Cantor's diagonal proof basically says that if Player 2 wants to always win, they can easily do it by writing the opposite of what Player 1 wrote in the same position:

Player 1:

XOOXOX

OXOXXX

OOOXXX

OOXOXO

OOXXOO

OOXXXX

Player 2: OOXXXO

You can scale this 'game' as large as you want, but using Cantor's diagonal proof Player 2 will still always win. For number of turns equals infinity ($T_{n}=\infty$):

Player 1:

XOOXOX...

OXOXXX...

OOOXXX...

OOXOXO...

OOXXOO...

OOXXXX...

...

Player 2: OOXXXO...

Since $T_{n}=\infty$, and $\left | T_{n} \right |=\left | P_{1} \right |$, $\left | P_{1} \right |=\infty$ (please note that the lines are the notation for cardinality, not absolute value). However, by using the tactic described earlier, Player 2 ensures that $P_{2}\notin P_{1}$.

We can extend this to Hilbert's paradox by assigning a company to the hotel to clean the rooms. This company has an infinite number of workers, but the way it trains them is strange. If rooms 2, 57, and 2,246 needed cleaning, the company would send the employee whose job it is to clean rooms 2, 57, and 2,246. Each cleaner would have a different set of rooms to be cleaned, including the worker who gets called when none of the rooms need cleaning.

Assume now that hotel wishes to throw a party for its cleaners and give them all a free room on the same night. Since you have already read the Wikipedia article, you know that you can add an infinite group to an already full hotel without kicking anybody out. Since the cleaning schedules of the workers are infinite strings, we can try to use Cantor's diagonal proof for $T_{n}=\infty$. Replacing Xs with no and Os with yes (for whether or not a worker cleans a room), we get this:

Rooms:

Room 1: No, Yes, Yes, No, Yes, No, ...

Room 2: Yes, No, Yes, No, No, No, ...

Room 3: Yes, Yes, Yes, No, No, No, ...

Room 4: Yes, Yes, No, Yes, No, Yes, ...

Room 5: Yes, Yes, No, No, Yes, Yes, ...

Room 6: Yes, Yes, No, No, No, No, ...

...

Excluded Worker: Yes, Yes, No, No, No, Yes, ...

So, the relationship between Hilbert's paradox and Cantor's diagonal proof is that Cantor's diagonal proof is an exception to the rule of Hilbert's paradox that $\infty+\infty=\infty$, and it establishes that there are different, unequal versions of infinity; the transfinite numbers.