Paradoxes of infinity — Math brief | Tangente

--------------------------

Hilbert's hotel ----------------------

In a lecture on infinity that he gave in 1925, David Hilbert invented the imaginary hotel that now bears his name to explain that infinity could not be encountered in reality. The hotel has infinitely many rooms, numbered 1, 2, 3, and so on. This creation would probably have been forgotten by now had George Gamow not popularized it in his book Un, deux, trois… l'infini, published in 1947.

Hilbert's hotel is full when a new guest arrives. The receptionist gives the newcomer room 1 while simultaneously calling every guest and asking them to move to the next room up (the guest in room n moves to room n + 1, thereby freeing room 1 without leaving anyone without a room). Even when Hilbert's hotel is full, it can still accommodate one more guest—and hence any finite number of guests!

Hilbert's hotel is still full when countably infinitely many guests arrive. The receptionist gives them the odd-numbered rooms and calls every existing guest, asking them to move to the room whose number is twice that of their current room (the guest in room n moves to room 2n + 1, thereby freeing all the even-numbered rooms without leaving anyone without a room). Even when Hilbert's hotel is full, it can still accommodate infinitely many more guests!

-

The pigeonhole principle ---------------------------

If four socks are distributed among three drawers, at least one drawer contains two or more. In 1834, J. P. G. Lejeune-Dirichlet named this the pigeonhole principle and used it to study rational approximations to a real number. He is generally credited with originating it. Yet Jean Leurechon had used it two centuries earlier in his book Récréation mathématique composée de plusieurs problèmes plaisants et facétieux. Leurechon's puzzle concerns hair and coins. He states it as follows: "\[Show\] that it is absolutely necessary for two men to have as many hairs or pistoles as each other."

The statement is easier to understand in the following form: "Each person has at most 150,000 hairs. Given that Angers has a population of 150,125, show that at least two of its inhabitants have the same number of hairs."

The proof has a surreal quality: put all the bald people in the first drawer, those with one hair in a second, and so on up to the last drawer, containing those with 150,000 hairs. If no drawer contains more than one person, the population of Angers can be at most 150,001, which is absurd; therefore, one of the drawers contains two people.

There is something unsettling about this proof: it does not tell us who those two people are. In the early 20^th century, mathematicians such as Luitzen Brouwer decided that this type of existence proof was unacceptable unless accompanied by an algorithm for constructing a solution. This is why they are called constructivists. This school of thought did not convince most mathematicians: following its precepts makes arguments unspeakably cumbersome.

-

Condorcet's paradox ------------------------

It is not always straightforward to order a set. In his Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix (1785), Nicolas de Condorcet showed that asking voters to rank three candidates, A, B and C, in an election could lead to a contradictory situation. Ask sixty voters for their preferences; a poll produces the following breakdown:

Thus, the voters prefer A to B by 33 votes to 27. They prefer B to C by 42 votes to 18, and C to A by 35 votes to 25. In short, a majority considers A better than B, B better than C, and C better... than candidate A!