This is a tale of three paradoxes and why they matter.
- First, the ancient Liar Paradox: “This sentence is false”. If this sentence is true, it must be false. If it’s false, it must be true.
- Next, the century-old Berry Paradox: Call a phrase “short” if it contains fewer than 13 words. The English language contains a finite number of words, and hence a finite number of short phrases. Hence there must be some natural numbers that can’t be described by any short phrase. Among these natural numbers, there must be a smallest. What is that natural number? Why, it’s the smallest natural number that can’t be described by any short phrase, of course. Except that this number is in fact described by the short phrase in boldface.
- Finally, the more modern Paradox of the Surprise Examination (or the Unexpected Hanging), which we discussed yesterday.
The paradoxes are slippery, because they are stated in the imprecise language of English. But each of them has inspired a precise mathematical counterpart that is central to a brilliant argument in mathematical logic.
Start with the liar: “This sentence is false” can’t be true, or it would be false — and can’t be false, or it would be true. This tells us that there’s such a thing as an English sentence that’s neither true nor false, which comes at first as a considerable surprise, but isn’t devastating.
One of Kurt Godel’s great insights was that you can go a lot deeper by considering a slightly different sentence: “This sentence is not provable”. If that statement is false, then it’s provable. But surely no false statement should be provable! So maybe the statement is true. In that case, it’s true but not provable, which says something about the limits of logic. It says that not every true statement can be proved.
At one level, this is still just wordplay. What makes it profound is Godel’s discovery of a code that converts certain English sentences into statements of pure arithmetic (that is, statements of the form “Every number is the sum of four squares” or “Every prime number is divisible by 2″) in such a way that true statements are matched with true statements and false statements are matched with false statements. The code is cleverly constructed so that there’s a statement in pure arithmetic (say, for illustration, that it’s the statement “every even number is the sum of two primes”) that corresponds to the English sentence “The statement that every even number is the sum of two primes cannot be proven.” These statements are either both false, in which case it’s possible to prove a false statement, which we believe (and hope to God!) is not the case — or they’re both true, in which case we’ve found a true statement in pure arithmetic that can’t be proven.
Much brilliant work goes into constructing the code, but the brilliant idea is to adapt the Liar Paradox to a context where you can’t just say “Well, I suppose it’s neither true nor false” — because statements like “Every even number is the sum of two primes” must be either true or false.
(The above intentionally sacrifices a little precision in the interest of readability; the linked post is more carefully worded.)
So that’s why mathematicians care about the Liar Paradox. More on the Berry Paradox and the Surprise Exam (and how all three tie together) as the week goes on.