Hilbert's Hotel

Definition Hilbert’s Hotel is an imaginary hotel with one room for each positive integer $1, 2, 3, \dots$ and no last room, in which every room holds exactly one guest. When new people arrive, the manager announces a rule that names one room for every person, old guests and newcomers alike, and everyone moves to their room at the same moment. A rule works when every person gets exactly one room and no two people get the same room. Rooms may be left empty. The paradox is that the hotel is full, since no room is empty, and yet working rules exist for one new guest, for a bus with one passenger for each positive integer, and even for one such bus for each positive integer. The resolution is that “full” only says that every room is taken. In a hotel with finitely many rooms, a rule that gives the guests different rooms uses as many rooms as there are guests, so it uses every room and leaves none for a newcomer. With infinitely many rooms the old guests can be given different rooms that leave some rooms free, because after every room $n$ there is a room $n + 1$. The hotel is a model of assignments between sets of numbers. It says nothing about a real building or about how long the moves would take. It is named after David Hilbert, who described it in a lecture in 1924.

Definition A one-to-one correspondence, also called a bijection, between two sets $A$ and $B$ is a rule $f$ that gives each element $a$ of $A$ one partner $f(a)$ in $B$ so that two conditions hold. First, no two elements share a partner, which means that $f(a) = f(a')$ only when $a = a'$. Second, every element of $B$ is the partner of some element of $A$. A rule with the first property is called injective, and in some books one-to-one, while a rule with the second property is called onto, or surjective. So a one-to-one correspondence is a rule that is both injective and onto. Two sets have the same size, or the same cardinality, when there is a one-to-one correspondence between them. For finite sets this means exactly that they have the same number of elements.

Definition A set is countably infinite when there is a one-to-one correspondence between it and the set of positive integers $\{1, 2, 3, \dots\}$. Equivalently, its elements can be written as an endless list $a_1, a_2, a_3, \dots$ in which every element appears exactly once, each at some finite position. Some books start counting at $0$, and that changes nothing, because $n \mapsto n + 1$ is a one-to-one correspondence between $\{0, 1, 2, \dots\}$ and the positive integers. A countably infinite set that gains one new element, or finitely many, or a whole countably infinite set of new elements, is still countably infinite, which is what the hotel shows. This does not make infinity a number that can be subtracted from itself. Removing a countably infinite set from the positive integers can leave infinitely many numbers, just one number or none, depending on which numbers are removed.

Definition A set $A$ is a subset of a set $B$ when every element of $A$ is also an element of $B$, and a proper subset when in addition $B$ has at least one element that is not in $A$. A finite set is never in one-to-one correspondence with a proper subset of itself, because a proper subset of a set with $N$ elements has fewer than $N$ elements. A countably infinite set always is. If $a_1, a_2, a_3, \dots$ lists it, the rule $a_n \mapsto a_{n+1}$ is a one-to-one correspondence between the whole set and the proper subset that leaves out $a_1$.

Definition A pairing function is a one-to-one correspondence between the set of ordered pairs $(b, s)$ of positive integers, in which $(1, 2)$ and $(2, 1)$ count as different pairs, and the set of positive integers. The diagonal pairing used here orders the pairs by their sum $b + s$, smallest sum first, and pairs with the same sum by increasing $b$. The pairs with sum $d$ are $(1, d - 1), (2, d - 2), \dots, (d - 1, 1)$, which makes $d - 1$ of them, and the smaller sums $2, 3, \dots, d - 1$ account for $1 + 2 + \dots + (d - 2) = (d - 2)(d - 1)/2$ pairs. So the pair $(b, s)$ with sum $d = b + s$ gets the position

The pairs with sums $2, 3, 4, \dots$ fill the positions in consecutive blocks of lengths $1, 2, 3, \dots$, so every positive integer is the position of exactly one pair. This is a version of the Cantor pairing function, shifted to start at $1$. Listing the pairs one row at a time does not work, because the pairs $(1, 1), (1, 2), (1, 3), \dots$ alone would take up every position, and $(2, 1)$ would never get one.