Paradoxes

This sentence is false

The sentence is either true or false; it cannot be partially true or partially false. But if it's true, then what it says is true, namely, it's false. However, if it's false, then it's not false - contrary to what it says. So it's false - which is what it says. So it's true... There are many variations on this theme. For example:

The next sentence is true

The previous sentence is false

The Barber paradox

In a certain village there is a man, so the paradox runs, who is a barber; this barber shaves all and only those men in the village who do not shave themselves. Query: Does the barber shave himself?

Any man in this village is shaved by the barber if and only if he is not shaved by himself. Therefore in particular the barber shaves himself if and only if he does not. We are in trouble if we say the barber shaves himself and we are in trouble if we say he does not.

The Barber paradox is a paradox with importance to mathematical logic and set theory. This paradox is attributed to the British logician Bertrand Russell, who in 1901 constructed Russell's paradox to demonstrate the self-contradictory nature of Cantor's elementary set theory by formalizing the Barber paradox. The paradox also underlies the proof of Gödel's incompleteness theorem as well as Alan Turing's proof of the undecidability of the halting problem.

Achilles and the Tortoise

Imagine that Achilles, the fleetest of Greek warriors, is to run a footrace against a tortoise. It is only fair to give the tortoise a head start. And under these circumstances, Zeno argues, Achilles can never catch up with the tortoise, no matter how fast he runs!

In order to overtake the tortoise, Achilles must run from his starting point to the tortoise's starting point, T-0 ('Tortoise at zero'). While he is doing that, the tortoise will have moved ahead to T-1 ('Tortoise at distance one'). Now Achilles must reach the point T-1. While Achilles is covering this new distance, the tortoise moves still farther to T-2.

Again, Achilles must reach this new position of the tortoise. And so it continues; whenever Achilles arrives at a point where the tortoise was, the tortoise has already moved a bit ahead. Achilles can narrow the gap, but he can never catch up with him.

"Interesting" and "uninteresting" numbers

Are there any uninteresting numbers? We can prove that there are none by the following simple steps. If there are dull numbers, then we can divide all numbers into two sets - interesting and dull. In the set of dull numbers there will be only one number that is the smallest. Since it is the smallest uninteresting number it becomes, ipso facto, an interesting number. We must therefore remove it from the dull set and place it in the other. But now there will be another smallest uninteresting number. Repeating this process will make any dull number interesting.

The Berry Paradox

The Berry paradox arises from considering definitions of the form

The smallest positive integer not nameable in under eleven words.

It is reasonable to assume that this is a specification for a number: after all, there are a finite number of sentences of less than eleven words, and some finite subset of them specify unique positive integers, so there is clearly some positive number that is the smallest integer not in that finite set.

But the Berry sentence itself is a specification for that number in only ten words!

This is clearly paradoxical, and seems to indicate that "nameable in under ten words" is not cleanly enough defined. Using programs or proofs of bounded lengths, one may in fact construct a rigorous version of the paradox; this has been done by Gregory Chaitin in order to produce an incompleteness theorem similar in spirit to Gödel's incompleteness theorem.

The Berry paradox was actually created by Bertrand Russell, who named it after G. G. Berry. Berry had provided the original idea in a letter to Russell about the less specific "the first ordinal that cannot be named in a finite number of words".

• Charles H. Bennett, "On Random and Hard-to-Describe Numbers", IBM Report RC7483 (1979)
• A discussion by Gregory Chaitin
• http://www.cs.yorku.ca/~peter/Berry.html

Epimenides paradox

The Greek philosopher Epimenides relates in the 6th century BC that "All Cretans are liars... One of their own poets has said so." Another version can be found in the Bible, Titus 1, verse 12-13: "One of themselves, even a prophet of their own, said, The Cretians are always liars, evil beasts, slow bellies. This witness is true. Wherefore rebuke them sharply, that they may be sound in the faith;"

The poet's (or prophet's) statement is sometimes wrongly considered to be paradoxical because he himself is a Cretan; it is not. It should not be confused with the Liar paradox, which is in fact paradoxical.

Common usage defines a "liar" as someone who occasionally produces answers that differ from the known truth. This presents no problem at all: the poet, while lying occasionally, this time spoke the truth.

However, most formulations of logic define a "liar" as an entity that always produces the negation of the true answer, that is, someone who lies always. Thus, the poet's statement cannot be true: if it were, then he himself would be a liar who just spoke the truth, but liars don't do that. However, no contradiction arises if the poet's statement is taken to be false: the negation of "All Cretans are liars" is "Some Cretans aren't liars", in other words: some Cretans sometimes speak the truth. This does not contradict the fact that our Cretan poet just lied.

Therefore, the statement "All Cretans are liars", if uttered by a Cretan, is necessarily false, but not paradoxical.

Even the statement "I am a liar" is not paradoxical; depending on the definition of "liar" it may be true or false.

Happiness or a ham sandwich?

Which is better, eternal happiness or a ham sandwich? It would appear that eternal happiness is better, but this is really not so! After all, nothing is better than eternal happiness, and a ham sandwich is certainly better than nothing. Therefore a ham sandwich is better than eternal happiness.

Hilbert's hotel paradox

Imagine a hotel with a finite number of rooms, and assume that all the rooms are occupied. A new guest arrives and asks for a room. "Sorry" - says the proprietor - "but all the rooms are occupied." Now let us imagine a hotel with an infinite number of rooms, and all the rooms are occupied. To this hotel, too, comes a new guest and asks for a room. "But of course!" - exclaims the proprietor, and he moves the person previously occupying room N1 into room N2, the person from room N2 into room N3, the person from room N3 into room N4, and so on... And the new customer receives room N1, which becomes free as a result of these transpositions.

Let us imagine now a hotel with an infinite number of rooms, all taken up, and an infinite number of new guests who come in, and ask for rooms.

"Certainly, gentlemen," says the proprietor, "just wait a minute." He moves the occupant of N1 into N2, the occupant of N2 into N4, the occupant of N3 into N6, and so on, and so on...

Now all odd numbered rooms become free and the infinity of new guests can easily be accommodated in them.

The Unexpected Hanging

A man condemned to be hanged was sentenced on Saturday. "The hanging will take place at noon," said the judge to the prisoner, "on one of the seven days of next week. But you will not know which day it is until you are so informed on the morning of the day of the hanging."

The judge was known to be a man who always kept his word. The prisoner, accompanied by his lawyer, went back to his cell. As soon as the two men were alone, the lawyer broke into a grin. "Don't you see?" he exclaimed. "The judge's sentence cannot possibly be carried out."

"I don't see," said the prisoner.

"Let me explain They obviously can't hang you next Saturday. Saturday is the last day of the week. On Friday afternoon you would still be alive and you would know with absolute certainty that the hanging would be on Saturday. You would know this before you were told so on Saturday morning. That would violate the judge's decree."

"True," said the prisoner.

"Saturday, then is positively ruled out," continued the lawyer. "This leaves Friday as the last day they can hang you. But they can't hang you on Friday because by Thursday only two days would remain: Friday and Saturday. Since Saturday is not a possible day, the hanging would have to be on Friday. Your knowledge of that fact would violate the judge's decree again. So Friday is out. This leaves Thursday as the last possible day. But Thursday is out because if you're alive Wednesday afternoon, you'll know that Thursday is to be the day."

"I get it," said the prisoner, who was beginning to feel much better. "In exactly the same way I can rule out Wednesday, Tuesday and Monday. That leaves only tomorrow. But they can't hang me tomorrow because I know it today!"

... He is convinced, by what appears to be unimpeachable logic, that he cannot be hanged without contradicting the conditions specified in his sentence. Then on Thursday morning, to his great surprise, the hangman arrives. Clearly he did not expect him. What is more surprising, the judge's decree is now seen to be perfectly correctly. The sentence can be carried out exactly as stated.

Schrödinger's cat

In the world of quantum mechanics, the laws of physics that are familiar from the everyday world no longer work. Instead, events are governed by probabilities. A radioactive atom, for example, might decay, emitting an electron, or it might not. It is possible to set up an experiment in such a way that there is a precise fifty-fifty chance that one of the atoms in a lump of radioactive material will decay in a certain time and that a detector will register the decay if it does happen. Schrödinger, as upset as Einstein about the implications of quantum theory, tried to show the absurdity of these implications by imagining such an experiment set up in a closed room, or box, which also contains a live cat and a phial of poison, so arranged that if the radioactive decay does occur then the poison container is broken and the cat dies. In the everyday world, there is a fifty-fifty chance that the cat will be killed, and without looking inside the box we can say, quite happily, that the cat inside is either dead or alive. But now we encounter the strangeness of the quantum world. According to the theory, neither of the two possibilities open to the radioactive material, and therefore to the cat, has any reality unless it is observed. The atomic decay has neither happened nor not happened, the cat has neither been killed nor not killed, until we look inside the box. Theorists who accept the pure version of quantum mechanics say that the cat exists in some indeterminate state, neither dead nor alive, until an observer looks into the box to see how things are getting on. Nothing is real unless it is observed.