Breaking logic with self-referential sentences

I don’t especially like people who talk a lot about themselves, but I have a soft spot for sentences that do. Case in point: the self-referential sentence “This sentence is false.” I really like that one. You may think you’ve seen this sentence before, but in fact you’ve seen other sentences, each made of the exact same words in the exact same order. I admit it’s hard to tell apart all those sentences, each separately subverting its own lonely self!

(If you think that two sentences that have the same words in the same order must really be the same sentence, consider the following two-sentence passage: The other sentence in this passage is lying! The other sentence in this passage is lying! The two sentences have the same words in the same order, but they’re saying very different things. And now that I’ve written down those two mutually-referential sentences, I have to say I don’t like them at all. They’re kind of shrill and unpleasant, and they remind me too much of current events.)

SELF-REFERENCE BREAKS LOGIC

So let’s get back to sentences that, instead of asserting the falsity of other sentences, assert their own falsity. They’re little logic landmines, blowing up the whole true/false dichotomy. In case you haven’t stepped on one of these explosive cuties before, here’s what happens when you do: If the sentence is true, it must be false (because that’s what it tells you to believe, and you trust it), while if it’s false, it must be true (because it’s telling you that it’s false but you aren’t dumb enough to fall for that). So it can’t be true but it also can’t be false. Got that? It’s confusing even if you’re not a robot from Star Trek or Joey from Friends.

New Eternal Scream, by Josh Sommers. Used with permission. Check out https://joshsommers.smugmug.com/ for lots of other cool images.

Self-referential sentences need to be handled with care. If two ordinary sentences are both true, you can stick the word “and” between them and get a sentence that’s still true (though long-winded). But that need not be the case when self-reference is involved: the sentence “This sentence contains exactly six words and this sentence contains exactly thirteen syllables” is false, even though its two halves, treated as sentences in and of themselves, are both true.

Of course you see the shabby trick I’m pulling: the two-word phrase “This sentence” has different meanings, and potentially different truth values, according to what sentence it sits inside. “This sentence” is an example of a deictic phrase — a phrase whose meaning is tied to something outside itself (in this case, the rest of the sentence). Ordinary language is full of deictic phrases, in which language grabs onto the world; in sentences like the ones we’re exploring today we take deixis a step further, letting language grab onto language.

Attending to the weaselly way the referent of the deictic phrase “this sentence” keeps shifting, we see that the ungainly sentence “This sentence contains exactly six words and this sentence contains exactly thirteen syllables” isn’t really the logical conjunction of the sentence “This sentence contains exactly six words” and the sentence “This sentence contains exactly thirteen syllables”; it’s what one might call the literal conjunction of those two self-referential sentences — and it’s no contradiction for two true self-referential sentences to have a literal conjunction that’s false.

YOU BETTER WATCH OUT

If you allow self-referential sentences to have their way, you can be quickly led to absurdities, such as Curry’s Paradox, which I learned about from one of Raymond Smullyan’s books. Consider the sentence “This sentence is false or Santa Claus exists”. (Here I’m using “or” in the inclusive sense, as logicians say; people sometimes say “and/or” to mean the same thing.) Call this sentence S. Could S be false? If S is false, then, since the first of the two alternative conditions S offers (“This sentence is false”) becomes true, S must be true. But that’s impossible, since we assumed S was false! So S must be true. But then, since the first of the two alternative conditions S offers is false, the only way S can still be true is if the second condition is true, which is to say, if Santa Claus exists. So Santa Claus must exist. (If that was confusing, see Endnote #2 for a different way to analyze the paradox.)

For even more fun, set the “This sentence is false or Santa Claus exists” train of thought in motion and, on the exact same track, fifty yards ahead and going the other way, set in motion a train that says “This sentence is false or Santa Claus DOESN’T exist.” The same logic drives them both. At the instant the two trains collide, if you look carefully, you can catch a glimpse of Santa Claus simultaneously existing AND nonexisting — that is, before the contradiction creates a bubble of pure nothingness expanding at the speed of light, consuming Santa, the absence of Santa, you, and everything else in the universe.

IMPLICATION, CONTRAPOSITIVES, AND SELF-REFERENCE

Under ordinary logic, “P is false or Q is true” is equivalent to “if P is true then Q is true”. So another version of the proof that Santa Claus exists (and in fact I think this is Smullyan’s version) arises from the sentence S‘: “If this sentence is true, then Santa Claus exists.”

Yet another way to use self-reference to prove the existence of Santa is via the self-referential sentence S“: “If Santa Claus doesn’t exist, then this sentence is not true.” I’ll leave it to you to check the details.

These last two sentences, S‘ and S“, are what logicians call contrapositives of one another. Or are they? Recall (or learn) that the contrapositive of the proposition “If P then Q” (with premise P and conclusion Q) is the proposition “If not-Q then not-P“.  Logicians define “If P then Q” to be another way of saying “Not-P or Q“, so “If not-Q then not-P” is another way of saying “Not-not-Q or not-P“, which in turn is just a really annoying way to say “Q or not-P“, which is synonymous with “not-P or Q“. So in ordinary logic, an if-then statement and its contrapositive always have the same truth value as each other: they’re either both true or both false.

But does that last dictum apply to self-referential sentences, when we treat them literally? Consider that the phrase “this sentence” in S‘ has a different referent than the phrase “this sentence” in S” (one refers to S‘, the other to S“). So it’s not immediately clear that they must have the same truth value.

In fact, I know of a true sentence of the form “If P then Q” whose literal contrapositive “If not-Q then not-P” is false! Can you think of one? See Endnote #1.

VARIATIONS ON THE THEME

The sentence “This sentence is false” has its roots in the ancient Liar Paradox. (The ancient Paradox of the Liar is not to be confused with the modern paradox of the liar, which is that the more someone says “You can trust me” the more you can’t.) I suppose some would say that the Liar Paradox can in turn be traced back to the ouroboros, the image of the self-devouring snake that the Greeks imported from Egypt.

The Liar Paradox has other incarnations. For instance, there’s the famous Barber Paradox, concerning a town whose barber shaves all those men in the town who don’t shave themselves, and shaves nobody else; is the barber a self-shaver? (If you answer “No she isn’t”, I reply “Okay, but what if we stipulate that the barber is a man?”) There’s also Cantor’s famous diagonal construction of a real number that’s missing from a purportedly complete encyclopedia of all real numbers, which some non-mathematicians find hard to accept, in part because it just seems so unfair to take the encyclopedist’s infinite amount of hard work and facilely use it against him.

There are a number of songs that refer to themselves. In the children’s music vein, there’s The Song That Never Ends and The Song That Gets on Everybody’s Nerves. In adult music, there’s James Taylor’s Fire and Rain (“I walked out this morning and I wrote down this song”) and Carly Simon’s You’re So Vain (“You probably think this song is about you”). The second of these has always confused me, because it sure sounds as if the song is (at least in part) about the person it’s addressed to, so why is he vain to think it’s about him? And I can never decide whether Melanie’s Look What They Done To My Song is self-referential; if it is, then what did the song say originally?

A pop song that doesn’t refer to itself directly, but takes a distinctly ouroboran turn, is One Direction’s What Makes You Beautiful; Stephen Colbert has pointed out that if what makes the singer’s girlfriend beautiful is the fact that she doesn’t know she’s beautiful, then him telling her she’s beautiful could lead to … well, Colbert explains it better than I can.

I once composed a puzzle, the Self-Referential Aptitude Test, consisting of twenty self-referential and inter-referential sentences, each of which could be completed in one of five ways. The solver of this multiple-choice logic puzzle has to find the unique set of answers that makes all twenty assertions mutually consistent. For instance, here’s the first of the twenty questions:

1. The first question whose answer is B is question 

(A) 1
(B) 2
(C) 3
(D) 4
(E) 5

You can immediately rule out A as a possible answer. That still leaves 4 possible answers, none of which can be immediately ruled out. But the mere wording of question 1 gives you useful information: at least one of the first five questions must have “B” as an answer. This information can help you answer other questions on the test. But which? If there’s ever been a test in which it’s a bad idea to try to answer the questions in order, this has got to be it!

One way to try to solve such a puzzle is to start with a random set of answers and then improve them, making them more inter-consistent. However, there’s no guarantee that this procedure will converge on a valid solution; you could enter into an infinite loop, oscillating between several self-inconsistent near-solutions, never arriving at the sole self-consistent true solution. To see what I mean by an infinite loop, try to complete the following sentence: “This sentence has exactly ___ syllables.” Guess the right number to put into the blank and then count the syllables. If your guess was correct, you win! If your guess was incorrect, replace your old guess by a new guess, namely, the number of syllables you counted.

Here’s a self-referential sentence I have a lot of trouble with: “Jim Propp cannot consistently believe this sentence.” My friends say that it’s true but that I’ll never understand it. “It’s an everyone-but-Jim thing,” they tell me consolingly.

GÖDELS ALL THE WAY DOWN

It might be tempting to try to banish self-reference from mathematics and logic, but it has a way of sneaking in. A long time ago, I wrote the sentence “Cette phrase se réfère à elle-même, mais d’une manière peu évidente à la plupart des Américains” and Douglas Hofstadter published it in one of his columns. (Actually, I wrote something else and Hofstadter fixed it for me, to make it say “This sentence refers to itself but in a manner that’s not very evident to most Americans” in idiomatic French.) What I was pointing at is that some sentences refer to themselves in a covert way (for instance, by being in an unfamiliar language). There is, in particular, a gigantically long proposition about whole numbers that is covertly asserting “This sentence cannot be proved from the Peano Axioms” (a small collection of widely accepted assumptions about the counting numbers). The Austrian logician Kurt Gödel (pronounced like “girdle” but with a softened “r”) devised the back door that lets propositions-about-propositions-about-numbers enter the house of arithmetic disguised as propositions-about-numbers. You can’t keep them out, and in particular, you can’t keep out the Gödel sentence that asserts “This sentence cannot be proved from the Peano Axioms.” Just as you can be sure that “Jim Propp cannot consistently believe this” is a true proposition whose truth I can’t encompass, the Gödel sentence is a truth that Peano Arithmetic cannot prove. (To be precise, under the assumption that the Peano Axioms are consistent, the Gödel sentence is a true sentence that can’t be proved from the Peano Axioms. Hereafter I’ll omit this caveat about consistency because it gets tiresome to repeat it, but it should be borne in mind. See Endnote #4 for more on this.)

You might think “Well, since the Gödel sentence G is true, why don’t we just add it as a new axiom, the way the ancient Greeks added the parallel postulate to their geometry because they weren’t able to prove it from their other, more basic axioms?” That’s good thinking, but not good enough. A new Godel G‘ sentence can be contrived, asserting “This sentence cannot be derived from the Peano Axioms even if you include G as an extra axiom.” Your enhanced version of Peano’s system won’t be able to prove G‘. You could try to add G‘ as an extra axiom, but I think you can see the infinite regress we’re heading towards. “It’s Gödels all the way down.” (Or up, or whatever.) You keep building a bigger house, but bigger and badder wolves keep finding their way in. And, while they don’t blow the house down (the way some sensationalist popularizers would have you believe), these uninvited house-guests and unwelcome party-crashers do make us piggies nervous. See Endnotes #3 and #4 for more on this.

You can learn about self-referential sentences and Gödel’s incompleteness theorems and much besides from Douglas Hofstadter and Raymond Smullyan‘s classic books. A more recent novelistic treatment, focusing on the lives and deaths of Kurt Gödel and Alan Turing, is Janna Levin‘s book. Check out the RadioLab podcast (In)completely Loopy featuring Levin and mathematician Steve Strogatz.

If you’re a fan of self-referential sentences, check out Alexander Bogomolny’s “Self-reference” page and James Franklin’s “Self-Reference Jokes” page. And if any of you have favorite self-referential sentences of your own, please post them as comments!

Here’s a final thought for you all: Some sentences are written in plain English but are too well-bred to refer to themselves directly.

Thanks to Stuart Anderson, John Baez, Joel David Hamkins, Evelyn Lamb, Michael Larsen (who taught me about “silly” contrapositives), Mike Lawler, Brent Meeker, Shecky Riemann, Josh Sommers, James Tanton, Allan Wechsler (who taught me the word “deictic”), and Glen Whitney.

Next month (Dec. 17): Will ’17 be the Year of the Pig?

ENDNOTES

#1: My solution is the sentence “If 2+2 equals 4, then the premise of this sentence does not contain the letter Z.” Its  literal contrapositive is “If it is false that the premise of this sentence does not contains the letter Z, then it is false that 2+2 equals 4.” The former is true, the latter false. (The latter may be easier to think about if replaced by “If the premise of this sentence contains the letter Z, then 2+2 does not equal 4.”)

One need not resort to self-reference to come up with a true sentence whose formal contrapositive is, if not downright false, then at least silly. Consider the sentence “If x has a reciprocal, then the reciprocal of x has a reciprocal.” It’s an unimpeachable result about real numbers. But its formal contrapositive “If the reciprocal of x doesn’t have a reciprocal, then neither does x” is a bit silly. An analogue in the world of human relationships might be the unimpeachable sentence “If a woman is married to a man, then that man is married to her” and its silly formal contrapositive “If a woman’s husband isn’t married to her, then she isn’t married to him” (which on reconsideration doesn’t seem silly at all but worldly-wise in a French sort of way).

#2: If my earlier explanation of Curry’s Paradox confused you, here’s an explanation you might like better. It’s hard to think about a sentence that talks about itself, so let’s temporarily switch to a sentence that’s talking about a different sentence. Let S be the sentence “Sentence B is false or sentence C is true”, where B is some sentence and C is the sentence “Santa Claus exists”. We make a table that systematically shows, for each possible combination of truth-values of B and C, what the truth value for “B is false or C is true” must be:

This table applies regardless of what B is, so we can apply it in the case where B is the sentence S itself:

While we’re at it, we can replace the heading of the last column, formerly “S is false or C is true”, by just “S“, since the two are equivalent when S is the proposition “This sentence is false or C is true”:

But now we see that three of the four rows of the table lead to inconsistencies, where S has one truth-value in the first column and the opposite truth-value in the last column. The only self-consistent possibility is the first row: S is true and C is true.

So C must be true!

#3: Gödel’s First Incompleteness Theorem says (more or less) that there are propositions in Peano Arithmetic that are true but cannot be proved within Peano Arithmetic (PA for short). The way Gödel constructed such propositions was to encode the liar paradox in propositions that effectively say “This proposition is not provable in PA”. In a way, he treated Peano’s system as a sort of computer and programmed it to check mathematical proofs about Peano’s system. Gödel’s feat is all the more impressive because it predated the modern computer!

It should be stressed that PA is just about numbers and the four operations of arithmetic; it does not contain any linguistic apparatus for letting sentences talk about other sentences, let alone talk about themselves. So if you’ve never heard about this stuff before, you should be boggling about two separate things: how Gödel could possibly have hacked PA to make it talk about sentences and proofs, and how he could have made it possible for a sentence to talk not just about smaller, simpler sentences (which it could quote), but about itself. I don’t have the space to go into how Gödel did it, but Hofstadter’s 1979 book is a great source of information.

Gödel never wrote down his proposition G; he merely showed how, with patience and meticulous attention to detail, it could be done. The result would be about as illuminating as the assembly code for a program that compiles a high-level computer language into assembly code. (Maybe some interested reader with a knowledge of Gödel’s methods could write a computer program that would create such a sentence as an on-line document! If so, I’d happily create a link to it.)

In his recipe for G, Gödel had to make a lot of design choices (such as a choice of a numerical code for converting mathematical assertions about numbers into plain old numbers), and these choices could easily have been made other ways. So you could say that what he did was generate not just a single undecideable proposition G but a whole host of unprovable propositions G₁, G₂, G₃, …, each of which is unprovable in PA because each one, in its own way, is covertly asserting “This proposition is not provable in PA.”

But in an important (and nonobvious) sense, all of these propositions are equivalent to each other. Even though PA doesn’t afford a proof of G₁ or a proof of G₂, it does afford a proof of the proposition “G₁ is true if and only if G₂ is true”. And likewise for any two propositions in the list G₁, G₂, G₃, … So, on a logical level, there is really only one Gödel sentence for PA. See Joel Hamkins’ blog post, listed in the References.

(This may remind you of the whimsical provocation at the top of this article: my assertion that different instances of “This sentence is false”, even though they look identical, were actually different propositions. But now we see that, in the context of Gödel’s First Incompleteness Theorem, the many different ways for a sentence to arithmetically assert “This sentence is not provable in PA”, even though they look different, are actually equivalent.)

#4: Gödel’s First Incompleteness Theorem is bad news for those who would hope for an ultimate theory in mathematics that would let us prove everything about the counting numbers we might ever want to know; but it’s Gödel’s Second Incompleteness Theorem that bothers me more. This is the one that says “PA cannot prove its own consistency”. Unlike the artificial self-referential proposition Gödel concocted in his proof of his First Incompleteness Theorem, the consistency of Peano Arithmetic is something mathematicians really care about. We believe PA is consistent — it’s over a century old, and no snags have turned up yet — but it’d be nice to be sure, or at least to show that the consistency of PA follows from the consistency of some simpler theory of arithmetic. Gödel’s Second Incompleteness Theorem tells us that we’ll never receive that reassurance. If there were a way for a simpler theory than PA to prove the consistency of PA, there’d be a way to imbed this proof in PA, obtaining a proof of “PA is consistent” within PA. Gödel showed that this would lead to a fatal system crash; PA would turn out be inconsistent after all (and its “proof” of its own consistency would be worthless).

The relationship between Gödel’s two incompleteness theorems also sheds interesting light on the role of self-reference in the incompleteness phenomenon. Gödel’s first unprovable sentence “This sentence cannot be proved” and his second unprovable sentence “PA is consistent” are actually equivalent, in much the same way as the propositions G₁, G₂, G₃, … were equivalent in Endnote #3: you can prove inside PA that if either of them is true, then so is the other. The sentence “This sentence cannot be proved” talks about itself, but the sentence “PA is consistent” is not self-referential in the same way. In Gödel’s Second Incompleteness Theorem, it’s not an individual sentence that’s referring to itself; it’s the entire structure of Peano Arithmetic that, in a roundabout way, is able to reflect upon itself.

#5: We can also consider the self-referential sentence “This sentence is true”, and its fancier cousin “This sentence is provable in PA” (obscurely expressed as a gargantuan proposition in PA). The former could be true or could be false, but surprisingly, the second one (often called the “Henkin sentence”) is a theorem in PA! See Michael O’Connor’s webpage and the article by Halbach and Visser, both listed in the References.

#6: If you’re inclined to say that the proposition “This sentence is false” is neither true nor false but rather has no truth-value, trying sticking the following sentence into your brain instead: “This sentence either is false or has no truth-value.” Is it true, or is it false, or does it have no truth value? If it’s true, then it’s false; if it’s false, then it’s true; so it must have no truth-value. But if it has no truth-value, then since it admits as much, shouldn’t it be deemed true?

REFERENCES

Volker Halbach and Albert Visser, “The Henkin Sentence“, January 2014.

Joel David Hamkins, “Are All Gödel Sentences Equivalent?“, November 2016. See also his answer to the question “Nontrivial circular arguments?” on MathOverflow, January 2011.

Douglas Hofstadter, “Gödel, Escher, Bach: An Eternal Golden Braid”. 1979.

Douglas Hofstadter, “Metamagical Themas: Questing for the Essence of Mind and Pattern.” 1985.

Janna Levin, “A Madman Dreams of Turing Machines.” 2007.

Michael O’Connor, “Löb’s Theorem: Santa Claus and Provability“, August 2008.

Raymond Smullyan, “What Is The Name of This Book?”. 1978.

Raymond Smullyan, “Forever Undecided”. 1987.