Hilbert's paradox of the Grand Hotel

From Wikipedia, the free encyclopedia

Hilbert's paradox of the Grand Hotel is a mathematical paradox about infinity presented by German mathematician David Hilbert (1862 – 1943):

In a hotel with a finite number of rooms, it is clear that once it is full, no more guests can be accommodated. Now, imagine a hotel with an infinite number of rooms. One might assume that the same problem will arise when all the rooms are occupied. However, in an infinite hotel, the situations "every room is occupied" and "no more guests can be accommodated" do not turn out to be equivalent. There is a way to solve the problem: if you move the guest occupying room 1 to room 2, the guest occupying room 2 to room 3, etc., you can fit the newcomer into room 1. Unlike a finite hotel, in an infinite hotel, being "full" in the sense that every room contains a person is not the same as being "full" in the sense that there is no space for another person.

It is also possible to make room for a countably infinite number of new clients: just move the person occupying room 1 to room 2, occupying room 2 to room 4, occupying room 3 to room 6, etc., and all the odd-numbered rooms will be free for the new guests.

Now imagine a countably infinite number of coaches arrive, each with a countably infinite number of passengers. Still, the hotel can accommodate them: first empty the odd numbered rooms as above, then put the first coach's load in rooms 3ⁿ for n = 1, 2, 3, ..., the second coach's load in rooms 5ⁿ for n = 1, 2, ... and so on; for coach number i we use the rooms pⁿ where p is the i+1-st prime number. You can also solve the problem by looking at the license plate numbers on the coaches and the seat numbers for the passengers (if the seats are not numbered, number them). Regard the hotel as coach #0. Interleave the digits of the coach numbers and the seat numbers to get the room numbers for the guests. The guest in room number 1729 moves to room 1070209. The passenger on seat 8234 of coach 56719 goes to room 5068721394 of the hotel.

Some find this state of affairs profoundly counterintuitive. The properties of infinite "collections of things" are quite different from those of ordinary "collections of things". In an ordinary hotel (with more than one room), the number of odd-numbered rooms is obviously smaller than the total number of rooms. However, in Hilbert's aptly named Grand Hotel, the "number" of odd-numbered rooms is as "large" as the total "number" of rooms. In mathematical terms, this would be expressed as follows: the cardinality of the subset containing the odd-numbered rooms is the same as the cardinality of the set of all rooms. In fact, infinite sets are characterized as sets that have proper subsets of the same cardinality. For countable sets, this cardinality is called (aleph-null).

An even stranger story regarding this hotel shows that mathematical induction only works in one direction. No cigars may be brought into the hotel. Yet each of the guests (all rooms had guests at the time) got a cigar while in the hotel. How is this? The guest in Room 1 got a cigar from the guest in Room 2. The guest in Room 2 had previously received two cigars from the guest in Room 3. The guest in Room 3 had previously received three cigars from the guest in Room 4, etc. Each guest kept one cigar and passed the remainder to the guest in the next-lower-numbered room.

Contents 1 The cosmological argument 2 References in fiction 3 See also 4 External links

[edit] The cosmological argument

A number of defenders of the cosmological argument for the existence of God, such as William Lane Craig, have attempted to use Hilbert's hotel as an argument for the physical impossibility of the existence of an actual infinity. Their argument is that, although there is nothing mathematically impossible about the existence of the hotel (or any other infinite object), intuitively (they claim) we know that no such hotel could ever actually exist in reality, and that this intuition is a specific case of the broader intuition that no actual infinite could exist. They argue that a temporal sequence receding infinitely into the past would constitute such an actual infinite.

However, the paradox of Hilbert's hotel involves not just an actual infinite, but also supertasks; it is unclear whether this claimed intuition is really the physical impossibility of an actual infinite, or merely the physical impossibility of a supertask. A causal chain receding infinitely into the past need not involve any supertasks. See Thomas Aquinas' Summa Theologica for details about infinite regressions and the existence of God.

[edit] References in fiction

• The novel White Light by mathematician/science fiction writer Rudy Rucker includes a hotel based on Hilbert's paradox, and where the protagonist of the story meets Georg Cantor.

• Stephen Baxter's science fiction novel Transcendent has a brief discussion on the nature of infinity, with an explanation based on the paradox, modified to use starship troopers rather than hotels.

• Geoffrey A. Landis' Nebula Award-winning short story "Ripples in the Dirac Sea" uses the Hilbert hotel as an explanation of why an infinitely-full Dirac sea can nevertheless still accept particles.

• In Peter Hoeg's novel Smilla's Sense of Snow, the titular heroine reflects that it is admirable for the hotel's manager and guests to go to all that trouble so that the latecomer can have his own room and some privacy.

• The booklet The Cat in Numberland by mathematician/philosopher Ivar Ekeland presents Hilbert’s paradox as a tale for children, in the tradition of Lewis Carroll. It is illustrated by John O’Brien.

[edit] See also

• Pigeonhole principle

[edit] External links

• Welcome to the Hotel Infinity! — The paradox told as a humorous narrative, featuring a hotel owner and a building contractor based on the feuding 19th-century mathematicians Georg Cantor and Leopold Kronecker