Wednesday 26 February 2014

Hilbert's impossible hotel

"Consider a hypothetical hotel with a countably infinite number of rooms, all of which are occupied. [...] Suppose a new guest arrives and wishes to be accommodated in the hotel. Because the hotel has infinitely many rooms, we can move the guest occupying room 1 to room 2, the guest occupying room 2 to room 3 and so on, and fit the newcomer into room 1." (*)

But we can prove that, if the hotel is full, accommodating new guests is in fact impossible:

Indeed, to say that the hotel is fully occupied is to say that, for all n in N, room n is occupied. Thus, a fortiori, room 1 is occupied and, for all n in N, if room n is occupied, room n+1 is also occupied. Which in turn is equivalent to saying that there is no n in N such that room n+1 is available. Hence, no more guests can be accommodated. QED.

Note that what I am actually showing is that, granted the usual inductive definition for the natural numbers (a sequence), the hotel simply can never be full; conversely, that there can be no such thing as a hotel (a set) that is potentially infinite. In other words, the simply endless is just not of the same (logical) quality of the actually infinite, that is what Hilbert's hotel is showing. Consequently, nothing peculiar about infinite sets can be proven via plain finite induction on sequences.