If God is all-powerful, then He can jump
over any wall He can build. Therefore,
God is not all-powerful because He can't
build a wall that He cannot jump.
___________________________________

 
Contents

Catch-22

A paradoxical notice

Some proofs:
Happiness or a ham sandwich?
Proof that either Tweedledum or Tweedledee exists
Proof that Tweedledoo exists
Proofs that Santa Claus exists
Proof that there exists a unicorn
Proof that you are either conceited or inconsistent
Proof that I am Dracula

Liars and truthtellers:
Epimenides the Cretan
The liar paradox
Hanging or beheading
Knights and knaves
The visiting logician
Cellini and Bellini

Berry's paradox

Infinity:
Hilbert's hotel paradox
Infinite income-tax

Schrödinger's cat

The unexpected hanging

Sets and subsets:
The barber paradox
"Interesting" and "uninteresting" numbers
Russell's paradox of classes

Arithmetic and algebraic paradoxes:
Proving that 2 = 1
Proving that 3 + 2 = 0
Proving that n = n + 1

Bibliography

Catch-22

There was only one catch and that was Catch-22, which specified that concern for one's own safety in the face of dangers that were real and immediate was the process of a rational mind. Orr was crazy and could be grounded. All he had to do was ask; and as soon as he did, he would no longer be crazy and would have to fly more missions. Orr would be crazy to fly more missions and sane if he didn't, but if he was sane he had to fly them. If he flew them he was crazy and didn't have to; but if he didn't want to he was sane and had to.

Joseph Heller, Catch-22

A paradoxical notice

Hughes & Brecht, p. 2

Some proofs

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.

Smullyan (1), p. 219

Proof that either Tweedledum or Tweedledee exists

Proof that Tweedledoo exists

Proofs that Santa Claus exists

Proof that there exists a unicorn

I wish to prove to you that there exists a unicorn. To do this it obviously suffices to prove the (possibly) stronger statement that there exists an existing unicorn. (By an existing unicorn I of course mean one that exists.) Surely if there exists an existing unicorn, then there must exist a unicorn. So all I have to do is prove that an existing unicorn exists. Well, there are exactly two possibilities:

(1) An existing unicorn exists.

(2) An existing unicorn does not exist.

Possibility (2) is clearly contradictory: How could an existing unicorn not exist? Just as it is true that a blue unicorn is necessarily blue, an existing unicorn must necessarily be existing.

Proof that you are either conceited or inconsistent

A human brain is but a finite machine, therefore there are only finitely many propositions which you believe. Let us label these propositions p1, p2, ..., pn, where n is the number of propositions you believe. So you believe each of the propositions p1, p2, ..., pn. Yet, unless you are conceited, you know that you sometimes make mistakes, hence not everything you believe is true. Therefore, if you are not conceited, you know that at least one of the propositions, p1, p2, ..., pn is false. Yet you believe each of the propositions p1, p2, ..., pn.

Proof that I am Dracula

(1) Everyone is afraid of Dracula.

(2) Dracula is afraid of only me.

Therefore I am Dracula.

Doesn't that argument sound like just a silly joke? Well it isn't; it is valid. Since everyone is afraid of Dracula, then Dracula is afraid of Dracula. So Dracula is afraid of Dracula, but also is afraid of no one but me. Therefore I must be Dracula!

Smullyan (1), pp. 213-18, 224

Liars and truth-tellers

The following is often given as the "liar paradox":

Epimenides the Cretan

Eubulides, the Megarian sixth century B.C. Greek philosopher, and successor to Euclid, invented the paradox of the liar. In this paradox, Epimenides, the Cretan, says, "All Cretans are liars." If he is telling the truth he is lying; and if he is lying, he is telling the truth.

Hughes & Brecht, p.7

This is not in fact a paradox at all. Epimenides cannot be telling the truth, but he may be lying: the truth may be that some Cretans, including Epimenides, are liars, but not all.

The liar paradox

The following version is the version which we will refer to as the liar paradox. Consider the statement in the following box:

Is that sentence true or false? If it is false then it is true, and if it is true then it is false...

The following version of the liar paradox was first proposed by the English mathematician P. E. B. Jourdain in 1913. It is sometimes referred to as "Jourdain's Card Paradox". We have a card on one side of which is written:

Then you turn the card over, and on the other side is written:

... Another popular version of the liar paradox is given by the following three sentences written on a card.

Smullyan (1), p. 227

Hanging or beheading

Poaching on the hunting preserves of a powerful prince was punishable by death, but the prince further decreed that anyone caught poaching was to be given the privilege of deciding whether he should be hanged or beheaded. The culprit was permitted to make a statement - if it were false, he was to be hanged; if it were true, he was to be beheaded. One logical rogue availed himself of this dubious prerogative - to be hanged if he didn't and to be beheaded if he did - by stating: "I shall be hanged." Here was a dilemma not anticipated. For, as the poacher put it, "If you now hang me, you break the laws made by the prince, for my statement is true, and I ought to be beheaded, but if you behead me, you are also breaking the laws, for then what I said was false and I should therefore be hanged."

Kasner & Newman, pp. 187-8

Kasner & Newman, p.189

Knights and knaves

There is a wide variety of puzzles about an island in which certain inhabitants called "knights" always tell the truth, and others called "knaves" always lie. It is assumed that every inhabitant of the island is either a knight or a knave...

Suppose A says, "Either I am a knave or else two plus two equals five." What would you conclude.?

If A is a knight, then two plus two equals five, which is not true. If A is a knave, then he is speaking the truth, which is not possible.

Smullyan comments:

The only valid conclusion is that the author of this problem is not a knight. The fact is that neither a knight nor a knave could make such a statement.

The visiting logician

We are back on the Island of Knights and Knaves, where the following three propositions hold: (1) knights make only true statements; (2) knaves make only false ones; (3) every inhabitant is either a knght or a knave. These three propositions will be collectively referred to as the "rules of the island."

We recall that no inhabitant can claim that he is not a knight, since no knight would make the false statement that he isn't a knight and no knave would make the true statement that he isn't a knight.

Now suppose a logician visits the island and meets a native who makes the following statement to him: "You will never know that I am a knight."

Do we get a paradox? Let us see. The logician starts reasoning as follows: "Suppose he is a knave. Then his statement is false, which means that at some time I will know that he is a knight, but I can't know that he is a knight unless he really is one. So, if he is a knave, it follows that he must be a knight, which is a contradiction. Therefore he can't be a knave; he must be a knight."

So far so good - there is as yet no contradiction. But then he continues reasoning: "Now I know that he is a knight, although he said that I never would. Hence his statement was false, which means that he must be a knave. Paradox!"

Question. Is this a genuine paradox?

Smullyan (2), pp.67-8

Cellini and Bellini

... whenever Cellini made a sign, he inscribed a false statement on it, and whenever Bellini made a sign, he inscribed a true statement on it. Also, we shall assume that Cellini and Bellini were the only sign-makers of their time...

You come across the following sign:

Who made the sign? If Cellini made it, then he wrote a true sentence on it - which is impossible. If Bellini made it, then the sentence on it is false - which is again impossible. So who made it?

Now, you can't get out of this one by saying that the sentence on the sign is not well-grounded! It certainly is well-grounded; it states the historical fact that the sign was made by Cellini; if it was made by Cellini then the sign is true, and if it wasn't, the sign is false. So what is the solution?

The solution, of course, is that I gave you contradictory information. If you actually came across the above sign, then it would mean either that Cellini sometimes wrote true inscriptions on signs (contrary to what I told you) or that at least one other sign-maker sometimes wrote false statements on signs (again, contrary to what I told you). So this is not really a paradox, but a swindle.

Smullyan (1), pp. 230-31

Berry's paradox

(Devised by G G Berry of the Bodleian Library)

The number of syllables in the English names of finite integers tend to increase as the integers grow larger, and must gradually increase indefinitely, since only a finite number of names can be made with a given finite number of syllables. Hence the names of some integers must consist of at least nineteen syllables, and among them there must be a least. Hence "the least integer not nameable in fewer than nineteen syllables" must denote a definite integer; in fact, it denotes 111,777. But "the least integer not nameable in fewer than nineteen syllables" is itself a name consisting of eighteen syllables; hence the least integer not nameable in fewer than nineteen syllables can be named in eighteen syllables.

Russell & Whitehead, p. 61

Infinity

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.

Gamow, p. 17

The proprietor's "just wait a minute" seems optimistic; it would surely take him an infinite time to shift the guests around.

Infinite income-tax

Now if a man had an unlimited income, it is an immediate inference that, however low income-tax may be, he would have to pay annually to the Exchequer of his nation a sum equal in value to his whole income. Further, if his income was derived from a capital invested at a finite rate of interest (as is usual), the annual payments of income-tax would each be equal in value to the man's whole capital. If, then, the man with an unlimited income chose to be discontented, he would be sure of a sympathetic audience among philosophers and business acquaintances; but discontent could not last long, for the thought of the difficulties he would put in the way of the Chancellor of the Exchequer, who would find the drawing up of his budget most puzzling, would be amusing. Again, the discovery that, after paying an infinite income-tax, the income would be quite undiminished, would obviously afford satisfaction, though perhaps the satisfaction might be mixed with a slight uneasiness as to any action the Commissioners of Income Tax might take in view of this fact.

Jourdain, pp. 66-7

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.

Gribbin, pp. 2-3

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.

Gardner (3), pp. 11-13.

Here is a version from Raymond Smullyan, with his solution:

On a Monday morning, a professor says to his class, "I will give you a surprise examination someday this week. It may be today, tomorrow, Wednesday, Thursday, or Friday at the latest. On the morning of the examination, when you come to class, you will not know that this is the day of the examination."

Well, a logic student reasoned as follows: "Obviously I can't get the exam on the last day, Friday, because if I haven't gotten the exam by the end of Thursday's class, then on Friday morning I'll know that this is the day, and the exam won't be a surprise. This rules out Friday, so I now know that Thursday is the last possible day. And, if I don't get the exam by the end of Wednesday, then I'll know on Thursday morning that this must be the day (because I have already ruled out Friday), hence it won't be a surprise. So Thursday is also ruled out."

The student then ruled out Wednesday by the same argument, then Tuesday, and finally Monday, the day on which the professor was speaking. He concluded: "Therefore I cannot get the exam at all; the professor cannot possibly fulfil his statement." Just then, the professor said: "Now I will give you your exam." The student was most surprised!

... Let me put myself in the student's place. I claim that I could get a surprise examination on any day, even on Friday! Here is my reasoning: Suppose Friday morning comes and I haven't got the exam yet. What would I then believe? Assuming I believed the professor in the first place (and this assumption is necessary for the problem), could I consistently continue to believe the professor on Friday morning if I hadn't gotten the exam yet? I don't see how I could. I could certainly believe that I would get the exam today (Friday), but I couldn't believe that I'd get a surprise exam today. Therefore, how could I trust the professor's accuracy? Having doubts about the professor, I wouldn't know what to believe. Anything could happen as far as I'm concerned, and so it might well be that I could be surprised by getting the exam on Friday.

Actually, the professor said two things: (1) You will get an exam someday this week; (2) You won't know on the morning of the exam that this is the day. I believe it is important that these two statements should be separated. It could be that the professor was right in the first statement and wrong in the second. On Friday morning, I couldn't consistently believe that the professor was right about both statements, but I could consistently believe his first statement. However, if I do, then his second statement is wrong (since I will then believe that I will get the exam today.) On the other hand, if I doubt the professor's first statement, then I won't know whether or not I'll get the exam today, which means that the professor's second statement is fulfilled (assuming he keeps his word and gives me the exam). So the surprising thing is that the professor's second statement is true or false depending respectively on whether I do not or do believe his first statement. Thus the one and only way the professor can be right is if I have doubts about him; if I doubt him, that makes him right, whereas if I fully trust him, that makes him wrong!

Smullyan (2), pp. 8-9

Sets and subsets

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.

Quine, p.4

Quine disarms the paradox thus:

What are we to say to the argument that goes to prove this unacceptable conclusion? Happily it rests on assumptions. We are asked to swallow a story about a village and a man in it who shaves all and only those men in the village who do not shave themselves. This is the source of our trouble; grant this and we end up saying, absurdly, that the barber shaves himself only if he does not. The proper conclusion to draw is just that there is no such barber. We are confronted with nothing more than what logicians have been referring to for a couple of thousand years as a reductio ad absurdum. We disprove the barber by assuming him and deducing the absurdity that he shaves himself if and only if he does not. The paradox is simply a proof that no village can contain a man who shaves all and only those men in it who do not shave themselves.

Another "swindle", like Cellini and Bellini above.

"Interesting" and "uninteresting" numbers

The question arises: 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."

Gardner (1), p. 131

Russell's paradox of classes

Most sets, it would seem, are not members of themselves - for example, the set of walruses is not a walrus, the set containing only Joan of Arc is not Joan of Arc (a set is not a person) - and so on. In this respect, most sets are rather "run-of-the-mill". However, some "self-swallowing" sets do contain themselves as members, such as the set of all sets, or the set of all things except Joan of Arc, and so on. Clearly, every set is either run-of-the-mill or self-swallowing, and no set can be both. Now nothing prevents us from inventing R: the set of all run-of-the-mill sets. At first, R might seem rather a run-of-the-mill invention - but that opinion must be revised when you ask yourself, "Is R itself a run-of-the-mill set or a swallowing set?" You will find that the answer is: "R is neither run-of-the-mill nor self-swallowing, for either choice leads to paradox."

Hofstadter, p. 20

Arithmetic and algebraic paradoxes

Proving that 2 = 1

Here is the version offered by Augustus De Morgan: Let x = 1. Then x² = x. So x² - 1 = x -1. Dividing both sides by x -1, we conclude that x + 1 = 1; that is, since x = 1, 2 = 1.

Quine, p.5

Assume that

a = b.    (1)

Multiplying both sides by a,

a² = ab.     (2)

Subtracting b² from both sides,

a² - b² = ab - b² .    (3)

Factorizing both sides,

(a + b)(a - b) = b(a - b).    (4)

Dividing both sides by (a - b),

a + b = b.    (5)

If now we take a = b = 1, we conclude that 2 = 1. Or we can subtract b from both sides and conclude that a, which can be taken as any number, must be equal to zero. Or we can substitute b for a and conclude that any number is double itself. Our result can thus be interpreted in a number of ways, all equally ridiculous.

Northrop, p. 85

The paradox arises from a disguised breach of the arithmetical prohibition on division by zero, occurring at (5): since a = b, dividing both sides by (a - b) is dividing by zero, which renders the equation meaningless. As Northrop goes on to show, the same trick can be used to prove, e.g., that any two unequal numbers are equal, or that all positive whole numbers are equal.

Here is another example:

Proving that 3 + 2 = 0

Assume A + B = C, and assume A = 3 and B = 2.

Multiply both sides of the equation A + B = C by (A + B).

We obtain A² + 2AB + B² = C(A + B)

Rearranging the terms we have

A² + AB - AC = - AB - B² + BC

Factoring out (A + B - C), we have

A(A + B - C) = - B(A + B - C)

Dividing both sides by (A + B - C), that is, dividing by zero, we get A = - B, or A + B = 0, which is evidently absurd.

Kasner & Newman, p. 183

Proving that n = n + 1

(a)   (n + 1)² = n² + 2n + 1

(b)   (n + 1)² - (2n + 1) = n²

(c)   Subtracting n(2n + 1) from both sides and factoring, we have

(d)   (n + 1)² - (n + 1)(2n + 1) = n² - n(2n +1)

(e)   Adding ¼(2n + 1)² to both sides of (d) yields

(n + 1)² - (n + 1)(2n + 1) + ¼(2n + 1)² = n² - n(2n + 1) + ¼(2n + 1)²

This may be written:

(f)   [(n + 1) - ½(2n + 1)]² = [(n - ½(2n + 1)]²

Taking square roots of both sides,

(g)   n + 1 - ½(2n + 1) = n - ½(2n + 1)

and, therefore,

(h)   n = n + 1

Kasner & Newman, p. 184

The trick here is to ignore the fact that there are two square roots for any positive number, one positive and one negative: the square roots of 4 are 2 and -2, which can be written as ±2. So (g) should properly read:

±(n + 1 - ½(2n + 1)) = ±(n - ½(2n + 1))

Bibliography

Gamow: George Gamow, One, Two, Three ... Infinity, 1967

Gardner (1): Martin Gardner, Mathematical Puzzles and Diversions, 1959

Gardner (2): Martin Gardner, Further Mathematical Diversions, 1969

Gribbin: John Gribbin, In Search of Schrödinger's Cat, 1984

Hofstadter: Douglas R Hofstadter, Godel, Escher Bach: An Eternal Golden Braid, 1979

Hughes & Brecht: Patrick Hughes and George Brecht, Vicious Circles and Infinity: An Anthology of Paradoxes, 1975

Jourdain: P E B Jourdain, The Philosophy of Mr B*rtr*nd R*ss*ll, 1918.

Kasner & Newman: Edward Kasner and James Newman, Mathematics and the Imagination, 1940

Morris: Ivan Morris, The Ivan Morris Puzzle Book, 1972

Norththrop: Eugene P Northrop, Riddles in Mathematics, revised edition, 1961

Quine: W V Quine, The Ways of Paradox, and Other Essays, revised edition, 1976

Russell & Whitehead: Bertrand Russell and A N Whitehead, Principia Mathematica, 1910

Smullyan (1): Raymond Smullyan, What Is the Name of This Book?, 1978

Smullyan (2): Raymond Smullyan, Forever Undecided: A Puzzle Guide to Gödel, 1987