John Derbyshire explains the paradox of Hilbert's Hotel:

I had just got my Aleph-Null mug from MathematiciansPictures and I was explaining to my wife about Hilbert's Hotel.

Aleph-Null is the name of the first transfinite cardinal number. (A cardinal number tells you how many things there are in a set. The cardinal number of the set {Larry, Curly, Moe} is 3.) It is the number of all whole numbers, the number of this set: {1, 2, 3, 4, 5, ...}, where the three dots indicate that the set keeps going for ever.

The story of Hilbert's hotel goes like this. The point of it is to illustrate the key difference between finite cardinal numbers and transfinite ones, viz., that a set may have the same number as a subset of itself, if its number is transfinite.

A traveler comes to a hotel late at night. Goes to the desk clerk. Asks: "How many rooms in this hotel?" The clerk says: "47, and every one is occupied." The traveler says: "Can you give me a room?" The clerk says: "No, sorry. Every room is occupied. I already told you."

The traveler drives a few more miles, then comes to Hilbert's hotel. [David Hilbert was a great German mathematician.] Goes to the desk clerk. Asks: "How may rooms in this hotel?" The clerk says: "Aleph-Null, and every one is occupied." The traveler says: "Can you give me a room?" The clerk says: "Certainly."

The traveler says: "How is that possible, since every room is occupied?" The clerk explains: "No problem! I move the occupant of room number 1 to room number 2. I move the occupant of room number 2 to room numer 3. I move the occupant of room number 3 to room number 4. I move the occupant of room number 4 to room number 5. I move the occupant of room numer 5 to room number 6. I move the occupant of room number 6 to room number 7. I move the occupant of room number 7 to room number 8. I move the occupant of room number 8 to room number 9. I move the occupant of room number 9 to room number 10. I move the occupant of room number 10 to room number 11. I move the occupant of room number 11 to room number 12. I move the occupant of room number 12 to room number 13. I move the occupant of room number 13 to room number 14. I move the occupant of room number 14 to room number 15. I move the occupant of room number 15 to room number 16. I move the occupant of room number 16 to room number 17. I move the occupant of room number 17 to room number 18. I move the occupant of room number 18 to room number 19. I move the occupant of room number 19 to room number 20. I move the occupant of room number 20 to room number 21. I move..."

"I get the idea," says the traveler hastily. "And when you've got through doing that, everyone has a room, and room number 1 is empty." "Precisely," says the clerk. "It just takes a while. But everybody ends up with a room!"

A little later that night, the desk clerk at Hilbert's hotel is greeted by some more arrivals—a bus party. This party is riding a very large bus—an infinitely large one, in fact, with Aleph-Null passengers. The director of this party goes to the desk clerk. Asks: "How many rooms in this hotel?" The clerk says: "Aleph-Null, and every one is occupied." The director says: "Can you give rooms to all the Aleph-Null people in my party?" The clerk says: "Certainly."

The director says: "How is that possible, since every room is occupied?" The clerk explains: "No problem! I move the occupant of room number 1 to room number 2. I move the occupant of room number 2 to room number 4. I move the occupant of room number 3 to room number 6. I move the occupant of room number 4 to room number 8. I move the occupant of room number 5 to room number 10. I move the occupant of room number 6 to room number 12. I move the occupant of room number 7 to room number 14. I move the occupant of room number 8 to room number 16. I move the occupant of room number 9 to room number 18. I move the occupant of room number 10 to room number 20. I move the occupant of room number 11 to room number 22. I move the occupant of room number 12 to room number 24. I move..."

"I get the idea," says the tour director hastily. "And when you've got through doing that, everyone has a room, and all the odd-numbered rooms are empty." "Precisely," says the clerk. "And as you know, there is an infinity of odd numbers. In fact, there are Aleph-Null of them!"