Can a Sentence Say It Is False?

In the widget, the first card never fits. Call it true: then what it says, “this is false”, must be right, so it is false, and your call was wrong. Call it false: then what it says is wrong, so it is not false, and your call was wrong again. No call fits.

Now try the truthful card: “The sentence on this card is true.” Here the trouble is the opposite. Call it true and it agrees: it says it is true, and it is. Call it false and it agrees too: it says it is true, which is wrong, so it is false, as you said. Both calls fit, and nothing in the sentence picks one.

The two cards are sneakier. Neither talks about itself. Card 1 says only that card 2 is true; card 2 says only that card 1 is false. Each sentence is perfectly ordinary on its own. Put them together and follow the chain: if card 1 is true, card 2 is true, so card 1 is false. If card 1 is false, card 2 is false, so card 1 is true. The loop goes all the way round and comes back turned over. This puzzle is the card paradox, made up by the English mathematician Philip Jourdain in 1913, who wrote the two sentences on the two sides of one card.

Most sentences that mention themselves are harmless: “This sentence has five words” is simply true. In these cards, the trouble needs two things together: a sentence that talks about its own truth, and a “not” in the loop.

“This sentence is false” is called the liar paradox, and it is about 2,400 years old. A paradox, in the strict sense mathematicians use, is an argument in which every step looks correct but the end is a contradiction.

The liar is built from self-reference: a sentence that refers to itself (or, like Jourdain’s cards, a ring of sentences that refer round to themselves). Here is the reasoning laid out, with L standing for the liar sentence.

• Suppose L is true. Then what it says is so, and it says L is false. So L is false. Contradiction.
• Suppose L is false. Then what it says is not so. It says L is false, so L is not false: L is true. Contradiction.

This looks like proof by contradiction (assume something, reach a contradiction, conclude the assumption was wrong), the way mathematicians prove √2 is not a fraction. But here both assumptions break. If every sentence must be true or false, then L must be one of them, and each one is impossible. Something we took for granted has to give.

What gives? Philosophers still argue. Some say the liar is neither true nor false. But then “This sentence is not true” is not true, which is what it says, so it is true after all. Others, following the Polish logician Alfred Tarski, say a language must not talk about the truth of its own sentences: that takes a second language, one level up. No answer satisfies everyone.

Not every ring of self-reference is hopeless. Some have exactly one way that fits, and finding it is a real puzzle. Here are ten sentences, each about all ten:

1. Exactly one of these ten sentences is false.
2. Exactly two of these ten sentences are false.

…and so on, down to

10. Exactly ten of these ten sentences are false.

Which are true?

The “At least” version has a different answer. Say f sentences are false. Sentence k says “at least k are false”, so it is true exactly when k ≤ f: sentences 1 to f are true and the rest are false. That makes 10 − f false sentences, and that must equal f. So f = 5: sentences 1 to 5 are true and 6 to 10 are false.

Now the twist. The same argument, with nine sentences, needs f = 9 − f, so $f = 4\tfrac12$. No number of sentences can be four and a half. With nine sentences no calls fit at all: an innocent-looking list has become a liar paradox (a computer check of all 512 ways agrees). Whether a ring of sentences is a puzzle or a paradox can depend on whether there are ten of them or nine.

Here is a puzzle that sounds like a paradox and isn’t. In a village there is a barber who shaves exactly those men of the village who do not shave themselves: every man who doesn’t shave himself is shaved by the barber, and the barber shaves no one who shaves himself. Who shaves the barber?

If he shaves himself, he is a man who shaves himself, and the barber never shaves such men, so he doesn’t. If he doesn’t shave himself, he is a man who doesn’t, and the barber shaves every such man, so he does. The same flip as the liar.

But this time there is a calm way out: there is no such barber. Nobody can follow that rule and live in that village. The contradiction doesn’t break logic; it proves that something we described can’t exist, the way “a square with three corners” can’t. Here is why, in a table.

In the first village, Gopal and Bikash don’t shave themselves (their shaded squares are empty), so the barber must shave those two and nobody else. Now compare his row with each man’s row. Ram shaves himself and the barber doesn’t shave Ram: they differ in Ram’s shaded square. Gopal doesn’t shave himself and the barber does shave Gopal: they differ in Gopal’s shaded square. Every man’s row differs from the barber’s in that man’s own square, because the barber’s rule is to do the opposite of what each man does there. So the barber’s row can’t be anyone’s row, and the barber can’t be one of the men.

This trick has a name: the diagonal argument. The shaded squares run along a diagonal of the table. Turn every one of them over, and you get a row that differs from every row of the table. It works for any table at all.

Now the barber in the language of sets. In the school books a set is a collection of things, written in braces: {2, 4, 6}, or by a rule, {x:x is a student in your class}. Sets can contain sets, too: the set of the sections of Grade 10 in a school is a set whose members are sets of students.

Could a set be a member of itself? Most are not. The set of students in your class is not a student, so it doesn’t contain itself. But the set of all sets with more than three members has plenty more than three members, so it is one of them: it contains itself. Nothing seems wrong yet.

In 1901 the English philosopher Bertrand Russell asked about the set of all sets that are not members of themselves:

$$R = \{x : x \notin x\}$$

Is R a member of itself? If R ∈ R, then R is one of the sets that are not members of themselves, so R ∉ R. If R ∉ R, then R meets the rule, so R ∈ R. The barber again: R is the barber, and “contains” is “shaves”.

Why not simply answer “there is no such set”, as for the barber? Because mathematicians then believed, as you probably do, that any clear rule makes a set: whatever property you name, there is the set of all things that have it. That belief was written into the foundations of mathematics, and Russell showed it leads to a contradiction. From a contradiction anything at all can be proved, so the whole building was at risk.

The repair came in 1908 from the German mathematician Ernst Zermelo. In his rules you can no longer make a set out of a property alone. You may only pick out members from a set you already have: from a set A, the set {x ∈ A:x ∉ x} exists. Run Russell’s argument on that and the contradiction is gone: it now proves only that this set is not a member of A. So no set A can contain every set: there is no set of all sets (nor, it turns out, a set of all sets with more than three members, which seemed so harmless above). Zermelo’s rules, extended by Abraham Fraenkel and others, became Zermelo–Fraenkel set theory, and with one more rule, the axiom of choice (ZFC), they are the foundations most mathematicians use today. School maths is careful in the same way: its universal set U is always the set of things under discussion (the students of one school, the numbers up to 20), never “everything”.

The liar seemed a party trick until mathematicians pointed it at mathematics itself. Twice in the 1930s, a sentence modeled on the liar, with one word changed, gave not a paradox but a proof.

“This statement cannot be proved.” In 1931 the Austrian logician Kurt Gödel wrote a statement about whole numbers that says, in a code of numbers, “this statement cannot be proved from the rules of arithmetic”. Call it G. Now think like the liar. If G could be proved, then arithmetic would prove something false, since G says it can’t be proved. So, as long as the rules never prove falsehoods, G cannot be proved, and then what G says is true. That is no contradiction: G is a true statement that the rules can’t prove. This is Gödel’s first incompleteness theorem: any consistent set of rules for arithmetic, of the kind that can be checked mechanically, leaves some true statements unproved. (The argument above assumed a little more, that the rules never prove anything false; Gödel needed less than that, and in 1936 Barkley Rosser showed that “consistent”, never proving a contradiction, is enough.)

A program that does the opposite. In a paper of 1936, the English mathematician Alan Turing showed, in effect and with the barber’s trick, that no program CHECK can look at any program and its input and say whether it will ever stop or run forever. Suppose CHECK existed. Build a program CONTRARY that, given any program P, asks CHECK what P does when given its own text, and then does the opposite: if CHECK says “P stops”, CONTRARY runs forever; if CHECK says “P runs forever”, CONTRARY stops. Now give CONTRARY its own text. Whatever CHECK says it will do, it does the opposite. So CHECK is wrong about CONTRARY, and no program can be the perfect CHECK. This is the halting problem, and it is the diagonal argument again: the programs are the men, “stops when given this program’s text” is “shaves”, and CONTRARY is the barber.

• Can You Prove √2 Is Not a Fraction? Proof by contradiction, where one assumption fails and so the other must hold.
• What’s Wrong with This Proof That 1 = 2? Every step looks right and the end is absurd: find the broken step.
• Are Some Infinities Bigger Than Others? Cantor’s diagonal argument in full: why the points on a line can’t be listed.
• Who Is Telling the Truth? (Grades 6–8) Puzzles of people who always tell the truth or always lie, where sentences about each other do have an answer.
• Is There Room at a Full Hotel with Endless Rooms? (Grades 6–8) Endless sets that behave strangely, but without contradiction.
• Grade 10 Math: Sets Sets, subsets and the universal set, the language Russell’s paradox is written in.
• Grade 12 Computing: The Limits of Computing Turing’s halting problem worked out with real programs.
• Computing, Going Further (Grades 9–12): How Long Can a Tiny Machine Run Before It Stops? The busy beaver, where the halting problem bites. (Coming soon.)