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.
The major problem here is the excluded middle. It’s clear that there are at least three classes of statements: true ones, false ones, and ones which produce a contradiction if regarded as either true or false.
There are other statements that fall into the middle in practical terms because of limited rationality on on the part of real intelligence. When you make a statement involving things like “you’ll be surprised” or “you won’t know” you have to take implicit account of the depth of ratiocination the listener will bring to bear on the statement.
First, note that the professor can always surprise the students simply by lying to them: “You won’t get an exam tomorrow,” and then giving one.
So, is the professor lying to the students in the surprise exam scenario? Clearly if they are too dumb to do any logic at all on his statement, he isn’t; they’ll be surprised any day, even Friday. If they do the logic as described, they will believe that no surprise exam can be given, which turns out not to be true. If this is the level of analysis the prof expects from them, he is clearly lying, i.e. saying something that he knows will cause them to have a false belief. On the third hand, if the students go through the logic of the entire post, and realize the prof can give them the exam when he wants even though they’ve deduced he couldn’t, they are in yet a different state of belief.
The reason for noting that the prof could have said something that was incontrovertibly true was to point out that what he did say might just have been a subtle form of a lie.
Steve: Here is a disturbing multiple-choice question that I saw somewhere recently:
—-
What is the probability that a random selection will answer this question correctly?
a) 50%
b) 25%
c) 25%
d) 0%
—-
Is this in the same category as your paradoxes, or is this something completely different?
Thanks.
^The answer to that test question is 33%.
@TB: The joke is both clever and funny but there is no paradox here. I certainly imagined 4 choices, one for each and then … Down the rabbit hole. However that is NOT the population. It is one member of the population. The population with N persons answering is the 4^N choice vectors each scored for accuracy. [Preumably it is scored ‘against itself’ but that is not clearly stated] So the final result might not be any of a,b,c,d.
To elaborate on a point I think Steve elides a bit. Part of the Godel’s achievement in his numbering scheme is making ‘This’ precise. All the paradoxes in English is the squishiness of “This” or “that”. What PRECISELY does it point to? In Godel’s numbering scheme there is no squish.
I wrote on my own blog (search for an article called “The Paradox Paradox”):
“Paradoxes always come down to either a problem of definition or a problem of perception. Either the language used in our definitions is not precise or accurate enough to encapsulate what we’re trying to describe, or we are attempting to describe something universally, when its definition is entirely arbitrary.”
The Liar’s Paradox and Berry’s Paradox are examples of a problem of definition, i.e. defining truth with self-referential statements.
The Surprise Hanging paradox is an example of the second case. Really, this isn’t a “new” paradox, it’s a retelling of the distance paradox. (You can’t reach your destination because you must first travel halfway; from there, you must travel half the rest of the way, and so on. Because you must always first travel halfway, you never arrive at the destination.)
So the Surprise Hanging is basically a problem of arbitrary definitions. The hanged man chooses an arbitrary “stopping point” and then asks whether at that point in time he “knows” he’ll be hanged that day. Of course, when they finally put the noose on him, he also “knows” he’s being hanged – does that mean it didn’t happen?
For that matter, perhaps we never die (or fall asleep) because we never perceive the exact moment at which it occurs…
The point in time is arbitrary, though. I can just as easily choose Monday as the “exam date” and the whole argument dries up.
Ken B: Thanks for this useful elaboration.
Steve,
My attempt at an answer as to “why” the hanging paradox is flawed logic… When the final results/conclusions of your logic rule out your initial assumptions then you have faulty logic.
When I go back to your example, the exam, finally, (according to the logic of the students) COULD be given Friday. Why? Because now the students believed that it couldn’t really be given at all. Our entire logical thread started with ruling out Friday.
Steve, you say that the Liar Paradox demonstrates that there are sentences in English which are neither true nor false. But famously the liar paradox can be reworded as “This statement is not true.” If the statement is neither true nor false, then it is not true, and hence it is true, and we return to the paradox.
Others try to argue that the statement is both true and false, but this can be countered with “This statement is only true.”
@Keshav: “Truth is yellow.” True or false? I’d say meaningless. Those are your choices. Now “This statement is not true” could be meaningless. Assume it is. You do not get a contradiction. You are trying to extract a truth from a statement which is by assumption meaningless, and that’s where you INJECT a problem. And this is not a minor point. All these “This statement …” puzzles suffer from the problems with identifing WHICH statement. Let X be a proposition. Then in math-speak “|= X” is a different proposition meaning “X is true” (in the current model). These are not the same syntactic object. It is not clear how you get this self-reference if you are careful and precise. Sticking |= on the front always changes a sentence of fionite length so that won’t work. You need something else and that something is not obvious. Godel’s proof does this but for a particular sentence (and not with the equivalent of “this sentence is true” either but with the sentence ‘this entgence has no proof’.)
Not all sentences you can form are actually meaningful propositions with a truth value. “Truth is yellow”. If you want to claim to have shown a real paradox you must first show that you have a meanigful proposition first.
Ken B:
Godel’s theorem is actually pretty hard.
Well, Godel’s proof is pretty hard, but other proofs are much easier. Let me know what you think after I try to fully explain one of those proofs tomorrow.
“For the masochists here — I’m looking at you Thomas Bayes!”
So the sadist says to masochist, “I’m not going to hurt you one day next week, but you won’t know exactly which day until I don’t.”
Ken: Personally, I think that the liar statement is perfectly meaningful. My preferred resolution of the paradox is the same as that of many thinkers, including Charles Sanders Peirce and Arthur Prior. It goes as follow. Every sentence implicitly asserts it’s own truth. To say “Snow is white” is the same as saying “‘Snow is white’ is true” or “It is true that snow is white” or even “This statement is true and snow is white.” The key point is that the liar statement asserts its own falsehood, but like all statements it must also assert its own truth. So it is saying “This statement is true and false”, and is thus simply false.
Is Kurt Godel’s “true but not provable” a proof for God? And is that another paradox?
My favorite variations on this theme:
“People shave themselves if and only if they are not shaved by the barber. Who shaves the barber?”
“This sentence is false, and the person uttering it is not a genius.” True or false?
@ Keshav
“This statement is true and 2+2=5” ???
Scott: Yes, I do think that if someone asserts “2+2=5”, they are implicitly asserting “This statement is true and 2+2=5” or equivalently “2+2=5 and I’m telling the truth.”
Is Steve playing games with self-reference? I see a comment labelled Ken B addressed to Ken B quoting Ken B that is not in fact by Ken B.
RPLong: I thought of the distance paradox as well (which I learned as “Xeno’s Paradox”), not so much as a language problem but an example of SL’s suggestion that the backward induction is a trap. We can get lost in the ‘logic’, or step back and ‘know’ that there are plenty of point Bs we can reach with a single step (and in that case my recollection is that encountering the idea of a mathematical limit allows one to see through the supposed contradiction?). Likewise a student can step back and realize the simple fact (in plain English) is that the teacher announces (s)he is going to pick a day, and we don’t know which one. Do we just fool ourselves by making it more complicated than that? I suppose we can quibble over whether there is still any “surprise” around a Friday exam by Thursday evening, but until then it seems the students should be on pins and needles (certainly if Monday rolls around with no exam they should realize all bets are off).