« 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. » [1]
But we can prove that, if the hotel is full, accommodating new guests is actually impossible.
Indeed, to say that the hotel is fully 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.
In other words, by the simply-inductive definition of the natural numbers (a sequence), the hotel can never be full; conversely, there can be no such thing as a hotel (a set) that is potentially infinite. Bottom line, the simply endless is just not of the same logical quality as the actually infinite. Consequently, nothing peculiar about infinite sets can be proved via plain finite induction on sequences.
[1] 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.