"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.

(*) http://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel

Here is another illustration:

ReplyDeleteSo that guest 1 can move to room 2, guest 2 has to move to room 3; but, so that guest 2 can move to room 3, guest 3 has to move to room 4; but, so that guest 3 can move to room 4... and so on. The result is eventually obvious.

In fact, with a strict moving policy, no one can ever move. With a more relaxed policy, for every new guest in, there is one guest somewhere who is neither here nor there. Bottom line: finite or infinite, a full hotel is just full.