Sometimes your gut feelings lead you astray—particularly in mathematics, in which one constantly comes across results that seem impossible. For example, infinity does not always equal infinity, and tortoises may outpace human athletes—at least from a certain mathematical point of view.

There are also many scenarios that appear contradictory at first glance (or second or third). These paradoxes can be explained, however. They are not errors but rather reminders that we should not rely too heavily on our intuition in mathematics. Here are three of the strangest paradoxes in the field.

## Hilbert’s Hotel

## On supporting science journalism

If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

Imagine you are traveling to a city and have forgotten to book a room beforehand. Fortunately, you come across a beautiful hotel named after the famous mathematician David Hilbert, whose work you greatly appreciate. You step up to reception and see that the hotel has an infinite number of rooms: the room numbers correspond to the natural numbers 1, 2, 3, 4, … without ever coming to an end.

The receptionist tells you that the hotel is fully booked, however. But you know your way around math, so you don’t let yourself be fobbed off so easily. You know a trick that will allow you—and all the other endless guests—to find a room, too. You suggest to the receptionist that each guest move to the room numbered one higher than their current lodging. So the person from room 1 goes to room 2, the person from room 2 to room 3, and so on.

Because Hilbert’s hotel has an unlimited number of rooms available, even when fully booked, there is still room for more guests. And that’s not just the case for one person: they could have brought a whole busload of people who also wanted a room. In this case, the hotel guests would have to move not just one but several room numbers away.

It gets even stranger. Even if you bring an infinite number of people to Hilbert’s hotel, you can still accommodate them in the fully booked hotel. To do this, the guest in room 1 would have to move to room 2, the guest in room 2 to room 4, the guest in room 3 to room 6, and so on. As each person moves into a room with a number that is twice their current room number, an infinite number of odd-numbered rooms become available.

German mathematician David Hilbert presented this supposed paradox during a 1925 lecture on infinity. The example illustrates how not all concepts can be transferred from finite to infinite cases: the statements “every room is occupied” and “the hotel cannot take any more guests” are synonymous in the real world—but not in a world with infinities.

## The Birthday Paradox

The next paradox is more familiar to many. When I was at school, it was not uncommon for several of my classmates to have their birthday on the same day. In fact, I also shared a birthday with a classmate. At first, this seems like a huge coincidence. After all, a year has 365 days (or 366 in leap years, but we’ll ignore that for the sake of simplicity), and a school class consists of around 20 to 30 students. Our gut feeling therefore tells us that it is unlikely that two children were born on the same day.

But that’s not true. In fact, the probability that two people in a group of 23 have a birthday on the same day is more than 50 percent. To better understand this, it helps to look not at the number of people but at the number of pairs of people. From 23 people, (23 x 22) / 2 = 253 pairs can be formed—and this number exceeds half of all the days in a year. If we look at the probability that one of the pupils in a school class of 23 was born on a particular date, however, the probability is only 1- ((365-1) /365)^23=6.1 percent.

The birthday paradox therefore arises from the fact that looking at pairs of students gives you a greater number of possibilities than if you only look at individuals.

This fact has tangible effects in cryptography, for example. If you want to sign a digital contract, for example, “hash functions” are used: The document is converted into a character string (a “hash”) of a fixed length when it is signed. If even the smallest change is made to the original document, the hash that is formed from it is completely different. By keeping their hash, the signatory can prove what they originally signed—making the process tamper-proof. There is an extremely low probability that two completely different documents will generate one and the same hash, however, and that poses a security risk.

As a rule, the length of the hash function is chosen so that such “collisions” (where two different data records produce the same hash) are extremely rare. A hacker can carry out a “birthday attack,” however: they can generate many different documents and compare their hash functions in pairs—just as a teacher compares the birthdays of classmates instead of focusing on a specific date and a single student.

In practice, a birthday attack could look like this: I first create two contracts, V1 and V2. V1 is a fair contract, but V2 has wording that is in my favor. Then I change both contracts in various places: I add spaces, tabs and line breaks to create variations of V1 and V2. These changes are virtually invisible to a reader, but they drastically change the hash function of the documents.

If I compare the individual hash functions of the modified contracts V1 and V2 in pairs, I will find a matching hash much more quickly than if I specifically try to reproduce a particular hash (such as that of V1). If I find a matching pair of V′1 and V′2, I can give you the contract V′1 to sign but claim afterward that you signed V′2. Because both generate the same hash, the fraud cannot be detected by digital signature software.

## Russell’s Antinomy

British philosopher Bertrand Russell formulated a paradox in 1901 sometimes called Russell’s antinomy—a term for a statement that describes two seemingly contradictory ideas. Unlike Hilbert’s hotel and the birthday paradox, Russell’s antinomy is not a result that merely eludes our intuition. It contradicts the rules of logic per se. The antinomy produces statements that can be neither false nor true.

There are several examples that can illustrate Russell’s antinomy, but one famous case is the “barber paradox.” Suppose a barber shaves all the men in town who do not shave themselves—and *only* those men. Does the barber shave himself? If he shaves himself, then he no longer belongs to the group of people who do not shave themselves. But if he does not shave himself, then, by definition, he would have to shave himself (because all residents who do not shave themselves go to him).

This problem arises because of poorly defined sets. At the time that Russell presented his antinomy, a set generally referred to a collection of things: The natural numbers, for example, form a set, as does the set of all inhabitants that do not shave themselves. This also allows sets to contain themselves or refer to themselves as a whole—and these properties lead to contradictions. This antinomy therefore led to the end of what mathematicians call “naive set theory.”

The foundation of mathematics continues to rely on set theory. But sets in this construct are no longer mere collections and instead must fulfill certain conditions. For example, sets must be composed of already existing sets and must not refer to themselves. This rules out antinomies such as the barber paradox.

To put this in mathematical notation: people in town who can grow a beard and are men form a set *M*. That set includes the men who shave themselves and those who do not. Next, the set *C* includes all the barber’s customers. To form *C*, you have to follow the rules of modern set theory: If the barber is a man with a beard, or part of *M*, then the set of customers cannot be defined as “*all* male residents who do not shave themselves”—because in this case the definition would refer to itself with both the barber and the customers as part of *M*. Set theory simply does not permit such a definition. But if the barber is not part of *M*—for instance, if the barber is a woman or unable to grow a beard—then the definition is permitted.

We can now breathe a sigh of relief: the paradoxes have been solved, and mathematics is not doomed to failure. There is no guarantee that the mathematical rules will not at some point produce a unresolvable contradiction, however. Logician Kurt Gödel proved this in the 1930s—and in doing so made it clear that there is no certainty that mathematics will work forever in a self-contained way. The best we can do is hope that an unsolvable contradiction never arises.

*This article originally appeared in *Spektrum der Wissenschaft* and was reproduced with permission.*

Source link

## Leave a Comment