13 Infinity
13.1 Hilbert’s Grand Hotel
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Let me tell you the parable of Hilbert’s Grand Hotel. The
hotel has infinitely many rooms, each a luxurious full-floor
suite, numbered like the natural numbers: 0, 1, 2, and so on,
endlessly. Each room has a guest, and the hotel is completely
full, with infinitely many guests. But meanwhile, a new guest
has just arrived, wanting a room. What is the manager to do?
The manager says coolly, “No problem.” He sends an
announcement up to all the current guests: everyone must
change rooms up to the next higher room.
Room n → Room n + 1
There was fine print in the agreement that everyone had
signed at check-in, you see, stipulating that guests might have
to change rooms under the management’s direction. So ev-
eryone complies, with the result, you will notice, that room
0 now becomes vacant, available for the new guest.
Over the next several days, more guests arrive, and although the hotel is completely full,
the manager is able to accommodate them each time by having all the current guests move
up again, freeing up an additional room.
On the weekend, a crowd shows up all at once—1000 guests—and the manager accom-
modates them all in one migration by having all the current guests move up 1000 rooms:
Room n → Room n + 1000.
This makes available, in one step, all the rooms from 0 to 999, which accommodates the
crowd.