HILBERT'S HOTEL

A hotel has rooms numbered 1, 2, 3, and so on without end. Every room is occupied — the sign says NO VACANCY and the sign is telling the truth. A guest arrives anyway. The manager asks each occupant to move from room n to room n+1. Room 1 is now empty and the new guest checks in. Nobody was evicted, nobody is sharing, and every original guest still has a room of their own.

The trick is that no room was left over at the far end, because there is no far end. In a finite hotel the shift fails immediately: the occupant of the last room has nowhere to go. An infinite corridor has no last room, so the shift is defined for every guest at once, and the map n → n+1 sends the occupants onto rooms 2, 3, 4, … without collision.

It scales past one guest. An infinite bus arrives with passengers numbered 1, 2, 3, … The manager moves each existing occupant from room n to room 2n, which frees every odd-numbered room — infinitely many of them — and the bus takes the odd rooms. Infinitely many buses, each with infinitely many passengers, can also be accommodated by pairing rooms with prime powers or by any of the standard bijections between the natural numbers and their pairs.

What the story actually demonstrates is a definition, not a magic trick. Two sets have the same size when their members can be paired off one to one with nothing left over on either side. For finite sets that matches counting exactly. For infinite sets it produces the result that a set can be the same size as a proper part of itself — the naturals are the same size as the even naturals — which Galileo noticed in 1638 and set aside as an argument that size simply does not apply to infinite collections. Cantor took the same fact and made it the definition instead.

David Hilbert introduced the hotel in lectures around 1924, and it reached print through George Gamow's One Two Three… Infinity in 1947. It is a teaching device rather than a puzzle with a hidden flaw: nothing about it is contradictory, and every step is a legitimate operation on a countably infinite set. The discomfort it produces is the point. It is the moment where finite intuition and the actual definition of cardinality part company.

The limit is worth naming, because it is what stops this from proving too much. Not every infinity absorbs new arrivals this way. Cantor showed in 1891 that the real numbers cannot be paired off with the naturals at all — a bus carrying one passenger per real number could not be accommodated, however the manager shuffled the rooms.