Hilbert's paradox of the Grand Hotel

It helps a lot to be precise and use concrete examples. "Hilbert has an infinite hotel. We have to be careful with infinities, though, so I'll tell you what that means. If you think of a number zero or bigger, any number at all, Hilbert's hotel has a room with that number on it. Think of a number. ('2 million!') Yep, he's got that room. ('Six googolpillion!') Yep, he's got that room."

"A guest comes into the hotel and asks, 'Mr. Hilbert, do you have one more room?' Mr. Hilbert says, 'Sure!' He picks up his magic phone that calls everyone in the hotel at the same time and gives all the guests exactly the same message. After they do what he says, there's one room empty. What does he tell them to do?"

When they invariably come up with "Move up one room," it helps to belabor a couple of points. First, reformulate it as, "Look at your room number, add 1, and go to that room." (This helps them figure out "Multiply your room number by 2" as the answer to the second problem.) Second, dwell on who goes where, and whether it's a problem. "Where does the guest in room 0 go? ('Room 1.') Doesn't that have someone in it? ('Yes. Oh, no it doesn't, because he went to room 2!')"

No child has figured out my favorite fourth problem, but then it took mathematics until Cantor to figure it out, too.

"An uncountable group of people shows up at the hotel. Let me tell you what that means. They all have infinite name tags, all filled with As and Bs. Every possible name tag is in the group. [Give example names. Blow raspberries to do it.] The head of the group, whose name is 'AAAAAAAAAAAAAA...' [said with a blank look, trailing off] asks Mr. Hilbert if he has room in his hotel. Mr. Hilbert says 'No!' Why does he say that?"

Let them stew for a bit, and ask questions. Going on: "Mr. Hilbert says, 'OK, tell you what. If you give me a room assignment, I can always find someone you left out.' How does Mr. Hilbert do that?"

You can illustrate this with a game, using only four-letter names. Write down something like

AAAA BBAA BABA AABA

"Can you find a four-letter name that's missing?" Play this a few times, and then ask, "Can you come up with an easier way that doesn't make you think of all the names in turn?" Show them how to flip the letters along the diagonal, and then extend to infinite names.

I've had 2 kids and 1 adult follow this to the end. It's always mind-blowing for them, though, no matter how far they get. I follow up with this:

"That stuff they taught you in school, that stuff a lot of people say they hate, is arithmetic. This is math."

EDIT: Come to think of it, I actually helped a friend's 11-year-old daughter decide that she didn't hate math using these problems. She's probably still bummed about being stuck doing arithmetic for now, though...

One way of (somewhat) formalizing this is to say that you have a set containing infinitely many rooms, and another set containing infinitely many tenants. Intuitively, it does not seem unreasonable that you can give every room its own tenant. Once you do this, then the hotel is "full" in the sense it is impossible to find an empty room.

Of course, we can also think about giving each tenant her own room, which also seems possible. If we can do both of these things, we say that the set of rooms is the same size (or cardinality) as the set of tenants. It is worth noting, that not all infinite sets are the same size [0]. For the purpose of Hilbert's paradox, I believe it is far to assume that we are dealing with countably infinite sets [1]. The mathematical result in Hilbert's paradox is that if you add elements to a countably infinite set, the result is still countable infitite.

[0] https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

[1] That is to say, sets which are as large as the set of natural numbers.

N1 = { 1, 2, 3, 4, 5,... }

can be set into a one-to-one relationship with the set

N2 = { 2, 3, 4, 5, 6,... }

by the function

f(n1:N1) -> N2 = { n1 + 1 }

(Using a notation I pulled out of my flying monkeys right at this moment.)

The first set, N1, is the state of the hotel with one guest in every room, i.e. { n | room n is occupied }. The second set is the state of the hotel after Mr. Hilbert's operation, with room 1 empty.

The meta-trick is that an infinite set can be put into a one-to-one relationship with some proper subsets of itself (that's one definition of "infinite", by the way).

Imagine: how could the proprietor even communicate with those infinite guests?

I usually interpret the first steps in Hilbert's hotel as the first steps in the ordinal hierarchy (https://en.wikipedia.org/wiki/Ordinal_number).

"Proof some infinities are bigger than other infinities" (w/ Cantor's diagonal proof)

https://www.youtube.com/watch?v=lA6hE7NFIK0

"How many kinds of infinity are there?" (a very good list including surreals, P-adic, the long line, others)

http://vihart.com/how-many-kinds-of-infinity-are-there/

Also, I support her suggestion in "Infinite Trees Are Super Weird" that since we call uncountable line segments the "long line", we should call the uncountably-branching tree the "big tree".

https://www.youtube.com/watch?v=BEz-vGJvaik

Let's say your hotel is filled with even numbers. There are plenty of numbers not in the hotel that you could add.

The hotel could have someone in everyone room if every person with an even number as their ID was staying there. That is, for every room number, twice the room number is a unique even number, so there's a 1-to-1 correspondence between the number of rooms and the even integers.

You could then have someone with an odd number ID show up looking for a room, and would have to rearrange from a stay-in-half-your-ID lineup.

It's a (arguably defining) property of infinite sets that they contain a strict subset (at least one guy not in the subset) with the same "size" as the whole set.

So the evens and the integers are an example of this, with both having the same "size", even though the evens are contained in the integers.

Suppose first the people labeled with even integers show up, and they each go in the room with half their number. Then each room will have a person.

Then the person with number one shows up, and none of the rooms are empty.

If there are א people that exist, not all collections of א people have all people.

I think I don't have an intuitive understanding of how your intuition works.