Infinite liars
Regrettably, this chapter consists entirely of lies—every sentence in it, including this one, is false.
When my daughter Hypatia was very young, she liked to greet visitors to our home at the door with a friendly challenge:
Answer yes or no: will you answer no?
The guest would return her cheerful smile, yet stand flustered in the doorway with ponderous uncertainty. They were stymied by her question, for if they should answer yes, they would be saying that they should instead have said no, and if they should answer no, then it would mean that they should have said yes. My daughter had trapped them in an impossible logical labyrinth.
Epimenides paradox
A much earlier logical labyrinth occurred on the island of Crete in the 6th century BC, when Epimenides announced
All Cretans are liars.
Being a Cretan himself, you see, Epimenides was in particular calling himself a liar. Does this mean that the statement itself is a lie?
Well, for someone to be a liar, must everything they say be a lie? I don't think so. If someone tells lies only some of the time, then I would call them a liar, even if at other times they tell the truth. (I don't feel similarly about describing someone as honest or as a truth-teller—they must be reliably honest for this designation.) So it seems that Epimenides could consistently be telling the truth with this particular statement, even if, as seems dubious, every Cretan including Epimenides himself has told a lie at some point.
Some accounts of Epimenides have him saying:
Cretans are always liars.
Does this change things? I don't think so, not much. After all, a musician is still a musician when the song has ended; an artist remains an artist when the brush is put down. And so also with liars. If all Cretans have told a lie, then they will always be liars from now on, even if they sometimes assert truths.
Consider, in contrast, the more extreme statement:
All Cretans always lie.
This is a totally different situation. Epimenides cannot truthfully make this statement, for if he is truthful here, then in virtue of the meaning, since he is Cretan, his statement must also be a lie. But can the statement be a lie? Well, it certainly seems so, and in fact I find it very likely that the statement is not true, since I believe that most Cretans are good honest people, who seldom lie. This statement could merely be one regrettable case of a Cretan untruth, with the truth being that only some Cretans lie and even then only sometimes.
The liar paradox
The liar paradox refers to the troubling conundrum we face when trying to assign a coherent truth value for the following sentence, known as the liar sentence or sometimes personified simply as the liar.
This sentence is false.
The liar thus asserts its own falsity.
The central problem is that if the sentence were true, then precisely because of what it asserts, it would also have to be false, contrary to the assumption; but if it were false, then again precisely because of what it asserts, it would have to be true. It seems that the sentence, therefore, can be neither true nor false, posing a fundamental challenge for a complete and successful theory of truth.
The no-truth-value solution strategy
Perhaps one might hope to resolve the liar paradox by saying simply that the liar sentence has no truth value. It expresses a proposition that is neither true nor false, a gap in the truth values. Can one dissolve the liar paradox this way?
The liar's revenge
Some philosophers rebut that response by introducing the following sentence, known as the liar's revenge:
Either this sentence is false or it has no truth value.
If the liar's revenge were true, then in light of what it asserts, it would either be false or have no truth value, but both of those contradict the assumption that it is true. If it were false, in contrast, then in light of the first clause it would have to be true, which is again a contradiction. Finally, if the liar's revenge had no truth value, then precisely because of what it asserts in the second clause, it would be true, which would contradict the assumption that it had no truth value. So it seems wrong to say of the liar's revenge that it is true, wrong to say that it is false, and also wrong to say that it has no truth value. Crazy!
The liar's revenge thus seems to undermine the no-truth-value strategy of answering the original liar paradox. If that strategy were robust, then we should expect it also to work for the liar's revenge, which doesn't seem to be the case.
False versus not true
Some philosophers prefer to state the liar sentence as the assertion:
This sentence is not true.
That is, they prefer to take the liar to assert its own untruth as opposed to its own falsity. They do so in order to avoid a possible objection that could be made by someone who finds a distinction between “not true” and “false.”
A straightforward approach to truth and falsity might take false just to mean not true, especially when applied to sentences with a definite meaning, and with this account the need for a modified statement of the paradox may seem less urgent. But meanwhile, if there will be question of meaningfulness, then perhaps it will be better to use “not true” in place of “false.” For example, would you say that the following sentence is false?
'Twas brillig, and the slithy toves
Did gyre and gimble in the wabe.
Or how about this one—would you say it is a false sentence?
Shillyhumph ghghx88shhs.
It would seem reasonable to say instead that these assertions are nonsense, without any meaning—they are neither true nor false, because they do not express any proposition. But in this case, the sentences would reveal a distinction between falsity and untruth, for we have said that these sentences are not false and yet they are not true. The sentences thus show that being false is not the same as being untrue.
But notice how the not-true formulation of the liar paradox thus seems to take on board much of the liar's revenge reasoning. Namely, if the sentence were true, then it should not be true; and if it were not true, then it should be true. This latter reasoning seems to work whether or not the sentence has a truth value, since if the sentence had no truth value, then in particular it wouldn't be true, and so what it says would be the case. So it would be true after all. For this reason, the not-true formulation of the liar sentence can be seen already as an efficient form of the liar's revenge.
Obvious truth
Meanwhile, if you should reflect on the matter, the following sentence
This sentence is not obviously true.
does seem indeed to be true. If it were obviously true, then in particular, it would also be true, which in virtue of what it says would mean that it is not obviously true, a contradiction. So it isn't obviously true, which is just what it says. So it is true, but not obviously true.
Consider in contrast the sentence:
This sentence is obviously not true.
It cannot be true, since then it wouldn't be. That is obvious. So it is obviously not true. But that is just what it asserts!
I find it interesting to consider the obvious operator and how it interacts with logic. For example, it seems clear that “obviously not φ” implies “not obviously φ,” but not always conversely, since perhaps the question of φ or not φ is confusing—not obvious either way—in which case we would have both “not obviously φ” and “not obviously not φ.” It seems reasonable to claim that obviously (A and B) is equivalent to (obviously A) and (obviously B), but the similar claim for disjunction “or” seems wrong. That is, obviously (A or B) can be true even when neither A nor B is obvious. What is the logic of obviousness?
The both-true-and-false solution strategy
Some philosophers embrace a solution strategy for the liar paradox by declaring that it is both true and false. In paraconsistent logic, for example, there can be true contradictions, statements that are both true and false. These would be truth-value gluts, as opposed to gaps, as in the no-truth-value solution strategy we considered earlier. In the paraconsistent approach to a theory of truth, one develops not only the theory of truth, but also a simultaneous theory of falsity, with the idea in mind that these designations might overlap. And indeed they do overlap in the liar sentence, which is declared both true and false. Does this resolve the paradox? To my way of thinking, no, it does not bring us insight, but can be seen rather merely as pointing at the paradox, underlining it and taking it fully on board by incorporating it into the very foundations of the logic, but not resolving it in any way. Paraconsistent logic itself, after all, is as paradoxical as the liar paradox—it does not seem to help us find our way out of paradox.
Avoiding self-reference
People often observe that the liar sentences exhibit a self-referential nature, with each sentence making an assertion about itself. And perhaps it is natural to become suspicious of self-reference when it seems to be featured prominently in such paradoxes. Is self-reference itself the source of paradoxicality?
The twin liars
Some philosophers attempt to eliminate the self-reference from the liar paradox by various means. Consider, for example, the following pair of sentences, which I dub the twin liars.
The next sentence is true.
The previous sentence is not true.
Each sentence refers only to the other sentence and not directly to itself, and so in this way they might plausibly be described as having avoided self-reference. Meanwhile, these sentences together exhibit the liar paradox logic. Namely, if the first sentence is true, then the second must be true, which means the first sentence is not true after all. And if the first sentence is not true, then in light of what it asserts, the second sentence must not be true, in which case the first sentence is true. We have thus reached a contradiction in any case.
Indirect self-reference
Another attempt to avoid self-reference, which I have heard from philosopher Hartry Field, is to describe a situation where the liar agent does not refer directly to himself. For example, imagine that someone is walking on the street and sees a live television broadcast in a store window of a person talking, and he says,
What that person on the television is saying right now is not true.
But actually the person being shown on the television is himself right in that moment, and what he was saying just then is the very same utterance. Does this avoid self-reference?
My own considered view is that self-reference is not especially worrisome or problematic, and there is no urgent need to avoid it. Indeed, we shall discuss in a later section a remarkable mathematical theorem showing that any sufficiently strong mathematical language admits the capacity for self-referential assertions, even just in the formal language of arithmetic. The basic idea is that formal mathematical assertions can be represented with numbers, by encoding their syntactic symbols into the digits of the number, for example, and since arithmetic assertions can make assertions about these numbers, they can thus refer to themselves and even express their own provability or consistency. The fact of the matter is that self-reference is inextricably a part of every minimally sufficient mathematical theory.
Meanwhile, my view also is that the attempts we have mentioned to avoid self-reference in the liar are not actually successful—self-reference remains—and yet self-reference is not ultimately the source of paradox. I do not place the blame on self-reference, but rather on mistaken ideas concerning the nature of truth.
The infinite liar
Let us now consider another attempt to avoid self-reference in the liar paradox by constructing an infinite list of sentences, a system of assertions I call the infinite liar.
This scheme of sentences is also known as the Visser-Yablo paradox, discovered by Albert Visser and Stephen Yablo. Each sentence asserts the falsity of all the later sentences on the list.
If any of the sentences in the list were true, than all subsequent sentences below it would be false; but in this case, in light of what they assert, they should all be true, contrary to what we just said. So none of the sentences can be true, and so they are all false. But given this, in light of what they assert, they should all be true. We reach a contradiction in any case.
Here is a variant dual form of the infinite liar.
If any of the sentences were to be false, then in virtue of what that sentence asserts, there would be no false sentences subsequently. But then all the subsequent sentences, in virtue of what they assert, would be false, contrary to our conclusion that none of them are. So none of the sentences can be false. And therefore, in virtue of what they assert, all of them are false. Contradiction.
Part of the explicit motivation for constructing the infinite liar was to find a version of the liar paradox that avoided self-reference. Although each sentence in the infinite liar refers only to the later sentences and not to itself, in my view the infinite liar still partakes of self-reference. Each sentence in the infinite liar refers in effect to its own place in the system, since the sentences it refers to directly are “below” the given sentence, and this is a form of self-reference. We cannot, for example, rearrange the sentences to have an upward oriented structure or another arrangement entirely and preserve the referents.
The infinite liar is often presented as an indexed family of sentences s0, s1, s2, and so on, with a sentence sn for each natural number n:
Here, the sentence sn refers most directly to the sentences sk for k > n. But to my way of thinking, the mention of n here in the sentence sn is already a form of self-reference. Furthermore, one naturally regards the scheme of sentences in parametric form s(n), with the sentence s(x) in general form having a free variable x not yet specified, asserting
And this formula s is clearly self-referential.
We can adapt the revenge idea also to the infinite liar as follows:
If any of the sentences lacks a truth value, then all the sentences above it would be true. So there can't be two sentences lacking a truth value. From some point on, therefore, all of the sentences must have truth values. If any of them below that point were true, then every sentence below that must be false, but in that case, in light of what those sentences assert, all the sentences below would be true, contrary to what we just said. So eventually, the sentences all have a truth value, but none are true. So they are all false. But in this case, in light of what they assert about the later sentences, they must be true. So there is no way for them to be true or false or to lack a truth value.
Or perhaps one prefers the “not true” formulation, which as we argued previously is a form of the liar's revenge.
If any of them is true, then all subsequent sentences are not true; but in this case, in light of what they assert, they should all be true. Contradiction. Thus, none of them is true. But in this case, they should all be true. This reasoning seems to work even when one entertains the possibility that the sentences might be neither true nor false.
The Liar (a logic song)
A logical music video made in collaboration with the supremely talented Hannah Hoffman.
For more math/philosophy/logic videos, see my Music Videos section.
The disquotational theory of truth
The disquotational theory of truth consists of the idea that what it means to assert that a sentence is true is simply to assert the sentence itself.
“Snow is white” is true if and only if snow is white.
More generally,
Thus, according to this theory making a truth assertion amounts simply to removing the quotation marks—it is disquotational.
The disquotational theory of truth is sometimes described as a deflationary account of truth, in that it deflates what might otherwise be an overblown complicated approach to truth—a sentence is true, in the disquotational theory, simply if the proposition that it asserts is the case. In this sense, every particular use of the truth concept for a specific assertion is eliminable, since we can instead assert the content of that sentence.
The use/mention distinction
The disquotational theory of truth builds a bridge between use and mention, crossing the use/mention dichotomy, the distinction between using a word and merely mentioning it. In an earlier chapter, I had related the story of my Oxford colleague who at high table had announced that he generally uses pants as trousers, or perhaps merely “pants” as “trousers,” which would be much less shocking; and we discussed my daughter's question concerning whether everything rhymes with itself—or was it whether “everything” rhymes with itself? Or whether everything rhymes with “itself”? By convention we typically indicate a mention as opposed to a use of a word by enclosing it within quotation marks.
According to the disquotational theory, truth assertions amount to a traversal from mention to use. On the left of the disquotational biconditional we are merely mentioning the sentence “Snow is white,” because we are talking about this sentence, asserting of it that it has the property of being true, while on the right we are using the sentence, asserting the propositional content that the sentence expresses. According to this theory of truth, to make a truth assertion—in effect to remove the quotation marks—is to transition from mention to use with the same expression.
Not every mention of a sentence need explicitly involve quotation marks, of course, since I can refer to the first sentence of Moby Dick as I am doing just now without actually asking you to call me Ishmael.
The Grelling-Nelson paradox
A word is autological if the word describes itself, if the word itself is or has the property that the word expresses. The standard example is “polysyllabic,” which does indeed have several syllables. Other examples include “adjectival,” which is indeed an adjective; “unhyphenated” is unhyphenated; and “pronounceable” is pronounceable. All these words are therefore autological.
A word is heterological, in contrast, if it fails to describe or hold of itself. The word “monosyllabic” is not monosyllabic; “unwritable” is writable and therefore not unwritable; the word “explosive” is not literally explosive. So these words are heterological.
Is “red” red? Well, that particular copy of the word, written here in this chapter, is black, not red, but we could have written the word with red ink—would that make it red? Which of the following words is autological and which heterological?
Or is there a category error here? When we talk about a certain word, do we mean a particular instance of the word, written on a piece of paper or carved into the brick wall under a bridge, or is it instead an abstraction of all those particular instances of it? The word “combustible” might seem combustible, if you are reading this book in a format printed on paper, since you could ignite the book (but of course...uh...you would never do that...right?). If you were reading an electronic copy of the book, however, or perhaps as I expect in the near future (ha!), reading the copy of my book that is engraved into stone at the Smithsonian, then you would say that it is not combustible.
Perhaps all this confuses type with token, for a given word has many instantiations. There is arguably just one word “tenacious” in the English language, even though it could be written many times. If words are indeed abstractions in this sense, then it would seem that they have no color at all, and so every color name word is colorless. On this view, despite naive appearances, what I claim is that even
is heterological, while also
is autological, since the word referred to is an abstraction beyond the color used in representing it.
Incidentally, the mental confusion that arises from confusing the meaning of a word with the manner of writing it, such as in the color examples above, is called the Stroop effect, discovered by John Ridley Stroop in the 1930s. Here are other kinds of examples:
But let me finally get to the point with heterologicality. Consider the question whether “heterological” might be autological or heterological.
Is “heterological” heterological?
The question is asking in effect whether the word “heterological” applies to itself, and therefore this question, perhaps confusingly, seems to be the same as asking:
Is “heterological” autological?
The paradox here is that if “heterological” is heterological, then what this means is that it does not apply to itself, and so it should not be heterological. And if it isn't heterological, then “heterological” does not apply to itself and so it should be heterological. In either case we reach a contradiction. This is known as the Grelling-Nelson paradox, introduced in 1908 by Kurt Grelling and Leonard Nelson.
Iterated truth predicates
Suppose that we are considering a mathematical structure M of some kind, perhaps a group or a graph or an order of interest. The essential structural features of M can be expressed in a formal language associated with the atomic structure of M, a language allowing reference to that structure and the quantifiers ∀x and ∃x ranging over the domain of individuals of the structure M. The features of an order structure, for example, such as transitivity and reflexivity, can be expressed in terms of the order relation ≤ employed in it; the features of a group are expressed in terms of the algebraic group operation and the identity element and inverses; the features of a graph are expressed in terms of the adjacency edge relation.
In any such mathematical context, it is straightforward and unproblematic for us to add a truth predicate T(φ) for making truth claims about such an assertion φ in that original language, asserting that it holds in M, even allowing the reference of arbitrary individuals from the domain of M. That is, we do not make nested application of the truth predicate T, but rather apply it only to assertions in the original language of the structure.
This is merely the first layer of what will become a very tall hierarchy of iterated truth predicates. Let us denote the original language of the structure by ℒ0, and let us use T0 for the truth predicate we just mentioned, fulfilling the disquotational truth scheme
but only for assertions φ in the original language ℒ0. We now form a new larger language ℒ1 by expanding the original language ℒ0 of the structure with this truth predicate T0, which is interpreted in the corresponding expansion of M.
But the main point is that we can simply do it again, adding another truth predicate T1 for making truth claims in the language ℒ1. That is, T1(ψ) will hold of any ℒ1 assertion ψ if and only if ψ holds in M. The predicate T1 in effect enables us to make truth-about-truth assertions, but perhaps it is more accurate to say that T1 makes T1-truth assertions about assertions involving T0-truth. Adding T1 to the language forms a new larger language ℒ2.
In this way, we iteratively expand the language with additional truth predicates Tn in a sequence of layers. At the bottom level, we have the truth-free assertions of the original language, and each next layer is formed by adding a truth predicate for assertions of the previous layers. The construction proceeds infinitely, even transfinitely, achieving a coherent system of truth predicates Tα for every ordinal α, each referring to the truth of assertions at lower levels of the hierarchy. Every assertion in the accumulating language falls under the truth predicates of higher levels. Such is the unproblematic nature of the theory of well-founded iterated truth, the completely clear gold-standard case for a theory of iterated truth.
Although the theory of well-founded iterated truth is precisely designed for making truth assertions about truth, and truth-about-truth-about-truth and so on, nevertheless the liar sentence will not arise in this account of iterated truth. At no stage do we achieve a self-applicable truth predicate, a predicate Tα that applies to assertions in a language including the predicate Tα itself. Rather, what makes this account well-founded is that each level of the truth predicate Tα applies only to assertions in the language ℒα, which includes all earlier truth predicates Tβ for β < α, but not Tα itself.
The liar sentence, in contrast, is making a claim about the truth not of an assertion using only truth predicates from an earlier level of the hierarchy, but rather of an assertion employing the very same truth predicate about which the claim is made.
The no-proposition solution strategy
These ideas lead to another resolution strategy for the liar paradox. Namely, because the liar makes a truth assertion about itself, the very same assertion, the truth predicate in play is self-applicable in a way that does not and cannot occur with any well-founded truth predicate. The sentence is therefore not meaningful on the basis of the well-founded theory of truth. Indeed, because of this self-nesting of the truth predicate, the liar sentence is not even syntactically well-formed for well-founded iterated truth predicates. What is the theory of truth, then, to which it does refer?
One way to answer this question is that the paradox itself can be taken as an argument that there is no satisfactory theory of truth available for it—the contradiction at the heart of the liar paradox shows that there is no coherent theory of truth in play. And if there is no relevant theory of truth being employed in the liar sentence, then the liar sentence's use of the concept of truth and falsity is groundless, without meaning. In this sense, the liar sentence is not meaningful—it does not express a proposition.
The proposal here is that the liar sentence offers only an illusion of meaning. Perhaps because we are used to making truth assertions and even truth-about-truth assertions in the unproblematic case of the well-founded iterated theory of truth, the liar sentence conveys a superficial appearance of being meaningful. But since ultimately there is no coherent theory of truth underlying the liar usage, the sentence is not actually meaningful. In particular, despite appearances, it does not assert its own falsity.
Is this account subject to the liar's revenge? If we take the liar as not meaningful, then the revenge strategy might call for us to form the sentence:
This sentence is either false or not meaningful.
The revenge line of reasoning would then proceed: if we say that this sentence like the liar is not meaningful, then precisely in light of what the sentence asserts, it would be true, since we would fulfill the second clause of the disjunction. So it would be meaningful after all.
But is that analysis correct? Consider the following sentence
This sentence is either globharbash or not meaningful.
Is this sentence meaningful? Does it express a coherent proposition? I don't think it does. It seems to express a disjunction, but the first clause is gibberish and we would seem unable to say exactly what meaning the disjunction has that the sentence asserts. Because of this, I find no coherent proposition expressed here. Nevertheless, one can seem to carry out the revenge analysis here by saying that if the sentence were not meaningful, then the second disjunctive clause would be fulfilled and therefore the sentence would be true (and hence meaningful). One can also take that alternatively as an indictment of the revenge analysis itself. Since we said that this sentence does not have a coherent meaning, the fact that the revenge analysis leads us to a wrong conclusion tends to pour cold water on the revenge analysis itself.
Ultimately, the no-proposition response to the liar regards both the liar sentence and the liar's revenge sentence as not expressing propositions. There is no meaning to be found in them, despite their superficial appearance as expressing one.
And yet, a critic of the position will point out that this solution attempt of the liar amounts to the claim that the liar sentence is not meaningful and therefore, in particular, the claim that it is not true. In short, on this view we seem to ascent to the following proposition.
The liar sentence is not true.
But now the critics shout in unison: This is exactly what the liar sentence itself asserts! This is difficult trouble for the no-proposition position, which seems to be in the ridiculous position of holding that “this sentence is not true” is not true, even though that is what the sentence itself appears to assert. On the no-proposition account, one must bite the bullet, insisting that the liar sentence “this sentence is not true” does not express a proposition, and so despite appearances it is wrong to say that it expresses its own untruth. On this view, the liar sentence doesn't express anything at all.
Lia This sentence is not meaningful.
Tru What twaddle nonsense! That sentence has no meaning.
Lia But darling, that is what I just said.
Was Lia's statement meaningless or not? The trouble for Tru is that to assert that Lia's sentence is meaningless appears to be the very same sentence she asserted. He will have to say, no, Lia, your sentence did not have that meaning, because it had no meaning at all.
Liar paradox is a form of Buroli-Forti paradox
Consider the following sentence, which I shall call the well-founded liar's revenge:
This sentence is not true according to any well-founded theory of truth.
What are we saying here? The sentence seems to be saying that it will not be declared true by any particular truth predicate Tα arising in the well-founded hierarchy of iterated truth. Thus, the sentence in effect quanties over all the levels Tα of the hierarchy of well-founded truth. For this reason, the sentence is not expressible in the language ℒα at any ordinal level of the hierarchy, since those languages have the predicates Tβ only for β < α. Thus, the sentence is not of the form that could be declared true by any predicate Tα in the hierarchy. In this sense, we might therefore judge that the proposition asserted by the sentence indeed seems to be the case. This makes the sentence rather similar to the “this sentence is not obviously true” case.
Perhaps one is tempted to say that the sentence is true, meaning that it is true according to a continuation of the hierarchy beyond all the ordinals. We can naturally form the truth predicate TOrd, after all the ordinals, for assertions in the union of the languages ℒα. In this way, the liar paradox is revealed as a form of the Buroli-Forti paradox, the paradox that the class of ordinals is a transitive well-ordered class of ordinals, but is not itself an ordinal, since indeed it would be larger than every ordinal—it is a proper class and not a set. The point is that the concept of truth in play for saying that the well-founded liar's revenge is true would similarly be a proper-class continuation of the hierarchy of truth beyond every ordinal stage.
Russell paradox
We saw in an earlier chapter how Bertrand Russell, with a surprisingly simple argument, refuted the general comprehension principle, the principle asserting that every property φ determines a set, the set of all objects with that property.
Russell shows that for some properties, this principle is simply inconsistent. Specifically, if the principle were correct we could form the set R of all sets x that are not self-membered:
The problem is that it now follows immediately that R∈ R if and only if R ∉ R, a contradiction.
There is a clear parallel with the liar sentence here, for we had observed that R is a member of itself if and only if it is not a member of itself, not as the result of an elaborate argument, but rather directly because of the defining property of the Russell set itself.
Similarly, the Russellian barber shaves all and only those in town who do not shave themselves, and so, directly because of this, the barber shaves himself if and only if he doesn't. And the barista, who makes coffee for all and only those in town who do not make coffee for themselves, makes coffee for herself if and only if she doesn't. In each case, we are defining a certain feature that will hold in a certain case if and only if it doesn't, which is exactly the situation of the liar paradox.
Berry's paradox revenge
Let us also recall Berry's number b, defined as the following number:
The smallest number not definable in fewer than a dozen words.
Since there are only finitely many English expressions using fewer than a dozen words, they can define only finitely many numbers, and so it seems that there must be some smallest number not being definable in that manner. The paradoxical situation, however, is that this very definition itself uses fewer than a dozen words. Our earlier analysis of Berry's paradox pointed to subtle difficulties in the notion of definability, opening the possibility that some expressions which seem to define numbers might not actually succeed.
Berry's revenge
In light of this, consider now a revenge version of Berry's paradox:
Let n be the number specified by this definition, plus 1, if the definition succeeds, otherwise 0.
Does the definition succeed? If it specifies a number n, then because of what it says, it should specify n + 1, which would contradict the previous specification. So it seems that the definition cannot succeed. But in this case, it specifies 0 by the default clause. But then it should specify 1, and therefore 2, and so on; around and around we go.
Here is another variant:
Let B be the smallest number that this definition couldn't possibly define, if there is such a number, otherwise 0.
Has the definition succeeded in specifying a number? If not, then it would seem to revert to the default case, and so it would specify 0. So it seems that in any case it should succeed in specifying a number. But if it specifies a number n, then because of what it says, it should not specify n after all. So it seems there is no number that it can possibly specify. But in this case, it should specify 0. Around and around again.
The Gödel sentence
Finally we come now to the Gödel sentence, fruitfully viewed as a provability version of the liar paradox.
This sentence is not provable.
Remarkably, Gödel explained how such a self-referential sentence can be expressed in the purely mathematical formal language of arithmetic. How strange and wonderful it is. In one respect the formal Gödel sentence asserts that every number has a certain definite numerical property expressed in terms of addition and multiplication of that number in combination with smaller numbers, but in another respect the sentence is also naturally interpreted as expressing the nonprovability of the very same statement.
To specify the Gödel sentence, we fix a particular axiomatic formal system, such as the axiomatic framework of Peano arithmetic, and then regard provability to mean provability in that formal system. Ultimately, the analysis will lead to Gödel's incompleteness theorem, one of the most profound developments of twentieth-century mathematics, marking the coming of age of the subject of mathematical logic. I should like to provide an accessible soft account of it for the rest of this chapter.
Arithmetization
One of Gödel's key insights was the concept of arithmetization, the idea that any given finite mathematical structure can be encoded with numbers in such a way that the natural combinatorial processes we might employ with it become arithmetic manipulations on the corresponding numerical codes.
Each of us is familiar, for example, with the fact that when we type our documents into a computer—perhaps writing the great American novel—the information is stored ultimately in the computer's memory. While composing the document, we naturally conceive of it in high-level terms; it consists of chapters and paragraphs, perhaps written in certain fonts with certain formatting. These components in turn consist of words, and ultimately individual characters, supplemented with control codes for the fonts and spacing; ultimately, each atomic piece of information is represented simply by a number, such as in the extended ASCII system, which has 256 distinct symbols and control characters, that is, 28, so that each character can be represented in binary by exactly eight digits of 0 or 1. (Current systems tend to be based on Unicode, which allows for a far larger symbol set.) Thus, the entire document is represented as a gigantic sequence of 0s and 1s, with each bit represented via the presence of low or high voltage, respectively, in certain transistors on the circuit board. In this way, the entire document can be thought of as a single enormous binary number, the Gödel code of the entire document.
Similarly, we may undertake arithmetization of other mathematical structures, such as graphs or finite partials orders or what have you. And indeed, the formal language of arithmetic itself amounts to such a combinatorial structure, with the syntax of formal expressions via parse trees and so on. Every assertion φ in the formal language of arithmetic thus admits a Gödel code ⌜φ⌝, which is a number representing φ, and all the various syntactic operations that we might like to undertake with φ will be themselves expressible in the language of arithmetic. In this way, the formal language of arithmetic admits the capacity to make assertions about the formal language of arithmetic.
Self-reference in arithmetic
Using arithmetization, let us explore a logical enigma—the fixed-point lemma, a mathematical mystery, a logical labyrinth that shows how self-reference, the stuff of nonsense and confusion, sneaks explicitly into our beautiful number theory. It continually amazes me.
The fixed-point lemma is the claim that for any assertion φ(x) in the formal language of arithmetic, there is a sentence ψ such that in the standard Peano axioms of arithmetic one can prove the equivalence
Thus, the sentence ψ asserts that “φ holds of my Gödel code.”
For those willing to dive into some technical details, let me briefly give the proof. Consider the subsitution function, sub, defined so as to return the Gödel code after substituting a free variable with a specific numerical value, like this:
where the underlined m is the syntactic term 1 + ··· + 1, with m many 1s. The sub function is a primitive recursive function, representable in the formal language of arithmetic. Consider now any formula φ(x) with one free variable x. Let
and let
Finally, let
which is a sentence in the language of arithmetic. Putting all this together, we observe in Peano arithmetic the following equivalences:
Thus, the sentence ψ has the desired fixed-point property as claimed. So every arithmetically expressible property φ(x) admit a fixed-point sentence ψ.
First incompleteness theorem
Let us now use the Gödel sentence to prove the first incompleteness theorem, establishing that every consistent formal system of arithmetic will admit true but unprovable sentences. In short, arithmetic truth is not the same as provability in any such system.
Consider the Gödel sentence, which asserts its own nonprovability in the formal system of Peano arithmetic. If it were provable in that system, then we could formalize that proof and then prove that the proof indeed was a proof. In short, every provable statement is provably provable. But in proving the Gödel sentence, however, we would also be proving that it is not provable, since that is precisely what the sentence asserts. So we will have proved both that it is provable and that it is not provable, which would be proving a contradiction. If the theory is consistent, then this is impossible, and so the Gödel sentence cannot be provable.
But that is precisely what the Gödel sentence asserts! And so the Gödel sentence is a true statement that is not provable in the Peano theory.
This argument generalizes beyond Peano arithmetic to work with any formal system whose fundamental axioms we can in principle write down. The general conclusion is that every consistent arithmetic theory with a computably enumerable list of axioms will admit true but unprovable sentences. Indeed, the resulting theory will necessarily be incomplete, admitting statements that can be neither proved nor refuted.
The success of the Gödel sentence analysis, culminating not in paradox and confusion but rather in those profound mathematical theorems established with precision and rigour, to my way of thinking identifies the problem with the liar. The two sentences are fundamentally similar, merely replacing truth with proof, but otherwise having exactly the same self-referential form. The paradoxical nature of the liar therefore cannot be blamed on that self-referential nature, since this feature is shared by the Gödel sentence. Rather, the paradox of the liar seems to arise from the theory of truth it employs, a theory that is not spelled out and ultimately perhaps cannot be. Whereas the Gödel sentence employs a fully specified and precise notion of formal proof, there seems to be no coherent notion of truth underlying the liar sentence.
Tarski's theorem on the nondefinability of truth
Next, let us prove Tarski's remarkable theorem on the nondefinability truth. The theorem asserts that there is no arithmetically expressible property that picks out exactly the true arithmetic sentences, that is, a predicate that holds exactly of the numerical codes of the true arithmetic assertions. More precisely, there is no arithmetic formula T(y), such that
for every arithmetic sentence ψ. Let us call this the truth scheme for the predicate T.
Tarski's theorem is an immediate consequence of the fixed-point lemma, by using the liar paradox logic. Namely, if T(y) were arithmetically expressible, then we may consider the formula ¬T(x), which must admit a fixed point ψ, so that
But this equivalence means that ψ asserts its own untruth with respect to T, a form of the liar sentence, and consequently
which would prevent T from fulfilling the truth scheme. So there can be no such expressible truth predicate.
Alternative proof via Russell
I should like also to give an alternative proof of Tarski's theorem that avoids the fixed-point lemma, by appealing directly to the central idea of the Russell paradox, and without the need for much arithmetization, beyond the idea that every formal assertion φ is represented by a numerical code ⌜φ⌝. The claim will be that there is no arithmetically expressible formula T that expresses what it means for a formula φ(x) to be true at its argument x, like this:
So this is a parametric version of Tarski's theorem.
Suppose toward contradiction that there were such a truth predicate T. Using this predicate, let R(x) = ¬T(x,x), which is the formula expressing, “it is not the case that x is a formula that is true of itself.” Let r = ⌜R⌝, and consider the sentence R(r), which asserts ¬T(r,r), which is ¬T(⌜R⌝,r), which by the truth-predicate requirement is equivalent to ¬R(r), a contradiction. That's it. So there can be no arithmetically expressible account of truth.
In effect, the formula R(x) expresses that x is the code of a heterological formula:
The point is that in the context here of a formal language, the notion of heterologicality becomes a completely rigorous mathematical definition. Namely, a formula φ(x) in the language of arithmetic is heterological if ¬φ(⌜φ⌝). Our proof of Tarski's theorem via Russell amounts to exactly the same logic of the Grelling-Nelson paradox of heterologicality, except that here it is about precise assertions in the formal language of arithmetic. Thus we are led to a fundamental unity of all these paradoxes.
The infinite Gödel sentences
Let us consider the Gödelian version of the infinite liar, a provability version of the Visser-Yablo paradox.
We can formalize this more precisely with the fixed-point lemma, to find a formula γ(k) in one free variable that asserts the nonprovability of all later sentences.
If any specific instance γ(k) were provable, then we will have proved that no later instance γ(n) is provable. But every such later instance γ(n) makes a weaker claim than γ(k) itself, since every number above n is also above k, and so in proving γ(k) we are also able to prove γ(n). So we can prove that γ(n) is provable and also prove that γ(n) is not provable, which is impossible if the theory is consistent. Thus, no specific instance γ(k) can be provable. And so in virtue of what they assert, these are all true but unprovable sentences.
The speed-up phenomenon for lengths of proof
Consider the following sentence, a hybrid of the Gödel sentence with Berry's paradox.
This sentence is not provable in Peano arithmetic with a proof using fewer than a billion symbols.
Remarkable as it may seem, we can express such a sentence in the formal language of arithmetic by using the usual fixed-point tricks as with the Gödel sentence. That is, there is a formal assertion β in the language of arithmetic that expresses the fact that the very sentence itself is not provable by a formal proof in that language using fewer than one billion symbols.
Is it true? Well, if it were provable using fewer than one billion symbols, then we would be able to prove that that proof was a proof with fewer than one billion symbols (this proof that it is such a proof might be longer, but this is no matter). But then we will have proved that the sentence is false. So we will have proved the sentence and its negation, which would mean that our axioms are inconsistent. So if the axioms are consistent, then indeed the sentence is not provable using fewer then one billion symbols. And so the sentence β is true.
Indeed, though, the sentence is also provable, since we can verify that none of the proofs using fewer than one billion symbols is a proof of this sentence. That is a very long proof. What we have, in short, is a sentence that is true and provable, but necessarily, every proof of it is very long. Meanwhile, if we assume the consistency of the theory, then we have a very short proof.
This situation provides a simple proof of the second incompleteness theorem! Let me explain.
The second incompleteness theorem
The second incompleteness theorem is the assertion that no consistent theory of arithmetic with a computable set of axioms extending some basic axioms can prove its own consistency. For example, the theory of Peano arithmetic, if consistent, does not prove itself consistent.
Let me give a self-contained proof of this using the simple ideas from the speed-up phenomenon we just discussed. Suppose toward contradiction that PA proves its own consistency. This proof has some size, and let N be much larger, but with a small description, such as the exponential of the proof size. Consider the corresponding Gödel-Berry hybrid sentence β asserting that it has no proof of size less than N. The speedup analysis shows both that β has no proof in PA of size less than N, but it does have a very short proof in PA + Con(PA). Since PA proves Con(PA) in much less than size N, we can combine that proof with the proof of β in PA + Con(PA) and still have a proof of size less than N. So PA does admit a short proof of β, after all, a contradiction. Therefore PA does not prove its own consistency, which establishes the second incompleteness theorem.
The argument adapts to whatever other sufficient theory you want to use instead of Peano arithmetic.
The truth-teller and Löb's theorem
If the Liar sentence asserts its own falsity, let us consider the truth-teller sentence, which asserts its own truth.
This sentence is true.
Is it true?
Perhaps you think it can be either true or false, but I shall have something more to say about that momentarily. Meanwhile, just as the Gödel sentence asserts its own unprovability, let us also consider the Löb sentence, asserting its own provability.
This sentence is provable.
So we have four sentences forming a two-dimensional symmetric array:
Many people undertake the analysis of the Liar sentence by arguing that if the Liar sentence is true, then it must be false; and if it is false, then it must be true. And so, they conclude, the sentence is paradoxical. Meanwhile, the corresponding analysis of the truth-teller sentence seems to go nowhere: if it is true, then it is true; and if it is false, then it is false. Sometimes people conclude from this that the truth-teller sentence could be either true or false; it is somehow not determined.
But that analysis is not actually a proof of the claim; just because one does not immediately find a contradiction does not mean that there is not a deeper conclusion to be made. It is like saying that you searched for the keys and did not find them, therefore, they could be anywhere! But they are actually in a specific place, and they probably could not be on the Moon or inside Grant's Tomb. Can the truth-teller really be either true or false?
If you think so, and this is my main point here, then perhaps you might be inclined to expect a similar situation for the Löb sentence. But that conclusion would be wrong in light of Löb's theorem, which shows, remarkably, that the Löb sentence, the sentence asserting its own provability, is actually provable. The Löb sentence is provable and therefore true.
Let me sketch a soft proof. Let λ be the Löb sentence, and by the fixed-point lemma, let σ be a sentence that asserts the implication, that if σ is provable, then λ holds.
Suppose that σ were provable. Then we could prove that σ is provable, and because the biconditional above is provable, we would therefore be able to prove that λ is provable. But this is provably equivalent to λ. And so we have argued: if σ is provable, then λ is true. But that is just what σ asserts, and so by formalizing our argument, we see that σ is in fact provable. And so it is provably provable, and so λ is provable. Thus, the Löb sentence is true.
In short, the sentence asserting “this sentence is provable” is in fact provable. That is fascinating and surprising. But moreover, I should like to take this fact as a warning for us not to be too quick in our analysis of the sentence, “this sentence is true.”
The infinite truth-teller and infinite Löb sentences
Consider finally the infinite truth-teller sentences:
And similarly the infinite Löb sentences:
Let me argue for these latter sentences as in Löb's theorem that they are in fact provable. We construct the sentences by the fixed-point lemma, finding sentences τ(k) that assert the provability of all τ(n) for n>k.
To see that this is in fact true, apply the fixed-point lemma again to find a sentence σ asserting
Now, we argue as in Löb's theorem. If σ were provable, then it would be provably provable, and from that, using the previous characterization of σ as the implication on the right-hand side, it would follow that τ(0) is provable. Using this defining characterization of τ(0), we would therefore be able to prove that every τ(n) for n > 0 is provable, and using the other direction of that biconditional, we could prove every τ(n) for n > 0. Thus, each τ(n) would be not merely provable, but true. So we have argued that if σ is provable, then τ(0) holds. But this implication is just what σ asserts, and so we have now actually proved σ. And so τ(0) is true. And this implies all later τ(n), since the scope of the quantifier is descending.
Questions for further thought
Does the liar sentence express a meaningful proposition?
What is your analysis of the sentence:
This sentence does not express a meaningful proposition.
Do the twin liars and the infinite liar avoid self-reference?
What is your analysis of the following sentences?
What of these?
And these?
Construct further versions of the infinite liar with other order types. What happens if the infinite list goes up instead of down? What if the sentences have the order type of the rational numbers? What if the list is transfinite?
What is your analysis of an infinite collection of sentences, each asserting that all the other sentences is provable? [Hint: mount a Löb style analysis.]
Further reading
My book, Lectures on the Philosophy of Mathematics, 2021 MIT Press. In chapter 7, I give a thorough account of the incompleteness theorems and their role in the Hilbert program.
Credits
The quotation “‘Twas brillig…” is from Jabberwocky by Lewis Caroll. Some of the material on Gödel's theorem and Löb’s theorem was adapted from my book, Lectures on the Philosophy of Mathematics. The illustrations of the Liar and the infinite Liar was created by the author via DALL·E and is available in the collection at https://labs.openai.com/sc/QJC44RJTdvvy6dLDk62dTYLt.