Hilbert's hotel: Difference between revisions
imported>Peter Schmitt (→Introduction: rewriting (reduce to essentials)) |
imported>Peter Schmitt (explanation added) |
||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
'''Hilbert's hotel''' is | '''Hilbert's hotel''' is an often used popular illustration of some properties of infinite sets | ||
like the set of [[natural number|natural numbers]] ( | like the set of [[natural number|natural numbers]] (or any other [[countable set|countably infinite set]]). | ||
The story — which is usually attributed to [[David Hilbert]] — appears | In particular, it shows that infinite subsets of countably infinite sets have as many elements as the set, | ||
in a book (''One two three ... infinity'', 1947) by [[George Gamow]] (in Chapter 1, ''Big | and that the "sum" of two countable sets is also countable. | ||
The story — which is usually attributed to the German mathematician [[David Hilbert]] — appears | |||
in a book (''One two three ... infinity'', 1947) by [[George Gamow]] (in Chapter 1, ''Big Numbers'', pp.17-18) | |||
with the following footnote: | with the following footnote: | ||
<blockquote> | <blockquote> | ||
From the unpublished, and even never written, but widely circulating volume: | From the unpublished, and even never written, but widely circulating volume: | ||
"The Complete Collection of Hilbert Stories" by R. Courant | "The Complete Collection of Hilbert Stories" by R. Courant. | ||
</blockquote> | </blockquote> | ||
== | == The story == | ||
Imagine a hotel with | Imagine a hotel with infinitely many rooms, the room numbers being all natural numbers. | ||
Assume further that the hotel is fully booked — all rooms are occupied. | Assume further that the hotel is fully booked — all rooms are occupied. | ||
| Line 24: | Line 27: | ||
Thus room number '''1''' will become free for the new guest. | Thus room number '''1''' will become free for the new guest. | ||
Imagine now the arrival of a bus with infinitely many tourists. | |||
They still can be accommodated: This time the manager asks the guests to move from '''1''' to '''2''', | |||
from '''2''' to '''4''',from '''3''' to '''6''', and so on, namely from ''n'' to 2''n''. | |||
After this, only the rooms with even numbers are occupied, | |||
and the tourists can be put in the rooms with odd numbers. | |||
Curiously, in the many circulating versions of the story it usually is not mentioned | |||
that the manager could exclude some (even infinitely many) VIPs from moving and, | |||
more interesting, that he could spare ''all'' guests the inconvenience of moving | |||
by good advance planning: | |||
He simply must — when assigning rooms to arriving guests — leave free every second available room. | |||
Latest revision as of 09:07, 17 June 2009
Hilbert's hotel is an often used popular illustration of some properties of infinite sets like the set of natural numbers (or any other countably infinite set).
In particular, it shows that infinite subsets of countably infinite sets have as many elements as the set, and that the "sum" of two countable sets is also countable.
The story — which is usually attributed to the German mathematician David Hilbert — appears in a book (One two three ... infinity, 1947) by George Gamow (in Chapter 1, Big Numbers, pp.17-18) with the following footnote:
From the unpublished, and even never written, but widely circulating volume: "The Complete Collection of Hilbert Stories" by R. Courant.
The story
Imagine a hotel with infinitely many rooms, the room numbers being all natural numbers. Assume further that the hotel is fully booked — all rooms are occupied.
Nevertheless, if a new guest arrives he need not be sent away because the manager can provide a room by asking all guests to move: the guest in room 1 into room 2, the guest in room 2 into room 3, the guest in 3 into 4, and so on, i.e., each guest moving from room number n to room number n+1. Thus room number 1 will become free for the new guest.
Imagine now the arrival of a bus with infinitely many tourists. They still can be accommodated: This time the manager asks the guests to move from 1 to 2, from 2 to 4,from 3 to 6, and so on, namely from n to 2n. After this, only the rooms with even numbers are occupied, and the tourists can be put in the rooms with odd numbers.
Curiously, in the many circulating versions of the story it usually is not mentioned that the manager could exclude some (even infinitely many) VIPs from moving and, more interesting, that he could spare all guests the inconvenience of moving by good advance planning: He simply must — when assigning rooms to arriving guests — leave free every second available room.