4

Sometimes the basic Gödel sentence is said to mean something like, "This sentence is unprovable in system F." Perhaps more correctly, it is sometimes said to mean something like, "There is a sentence unprovable in system F," with the caveat that that sentence itself turns out to satisfy that very claim.

But the Gödel sentence isn't absolutely unprovable, is it? Because we will note that it can be proven in a higher system; it's just that the higher system will go on to have its own Gödel sentence, and so on and on. If a Gödel sentence were really supposed to be self-referential, wouldn't it be doubly so, as something like both, "I am unprovable in system F," but also, "I am provable in system F+"?

C.f. what the SEP article on the incompleteness theorems says:

  1. In the section on diagonalization and "self-reference": It is often said that given a property denoted by A(x), the sentence D is a self-referential sentence which “says of itself” that it has the property A. Such figures of speech may be heuristically useful, but they are also easily misleading and suggest too much.

  2. In the next section: In informal explanations of the first incompleteness theorem, it is often said that the Gödel sentence GF “says of itself that it is not provable”. Such imprecise statements, however, should be taken at least with a grain of salt. There are a number of reasons to conclude that, at least in general, Gödel sentences do not really say anything substantial about themselves (Milne 2007 is a careful analysis of such issues); for example, as was previously noted in the case of the Diagonalization Lemma, one is usually operating here with mere material equivalences.

  3. In a much later section: Heuristically, one may view the Gödel sentence GF as expressing its own unprovability—saying “I am not provable”—though, as was already emphasized, such claims should be taken with a grain of salt. Leon Henkin put forward the question whether the sentence expressing its own provability (“I am provable”) is true or false, and provable or not (Henkin 1952). Georg Kreisel soon pointed out that this depends vitally on how provability is expressed; with different choices, one gets opposite answers (Kreisel 1953).

5
  • 2
    Why would you expect that. In general, a sentence that expresses something of x does not express everything about x. Dec 25, 2023 at 14:06
  • @DavidGudeman based on the SEP article, I wouldn't really expect that the sentence expresses its own unprovability or provability on whichever level. OTOH I do need to situate sentences like, "I'm provable," and, "I'm unprovable," somewhere in my theory. A sentence that flips back and forth between those based on which level we're on would be an interesting phenomenon (I have in mind an application of this article about fuzzy logic and liar sentences that Conifold linked for me some while ago). Dec 25, 2023 at 14:12
  • 1
    Gödel sentences themselves "assert" even less than their own unprovability. Aside from dependence on the proof system F, this "assertion" relies on external interpretation of Gödel numbering which is what creates the "self"-reference. It is Gödel's construction of such sentences that implicates more, meta-semantically. Namely, that they are "true" (provable in a semantically natural extension, like ω-logic), which is more than just provable in some F+ (that would be trivial), and that the effect is reproducible in any extension of F of a delineated sort, including by adding the sentence.
    – Conifold
    Dec 25, 2023 at 17:06
  • 1
    Aside from Milne's paper, I recommend Matthíasson's thesis, Interpretations of Wittgenstein's Remarks on Gödel, pp. 42-49 for a discussion of the interplay between internal and external/informal semantics of Gödel sentences that initially misled many smart people, including Russell, Wittgenstein and Zermelo.
    – Conifold
    Dec 25, 2023 at 17:22
  • Would this be a correct interpretation of the Gödel sentence? Gödel Number N. 1. N = A (true) mathematical theorem in axiomatic system A. 2. N = T or N is unprovable in axiomatic system A. Gödel numbers, mission critical to Gödel's proofs, serve the dual purpose of a) being a true mathematical theorem AND b) asserting its own (the mathemtical theorem it is) unprovability. Yet, it's odd that (suppose) the math theorem 4 > 0 in axiomatic system A is also saying (surprise, surprise) "I can't be proven in axiomatic system A". By the transitivity property of equality (supposing T is t
    – Hudjefa
    Dec 26, 2023 at 18:19

3 Answers 3

3

Here's one way of understanding this. If you take the sentence "this sentence is not provable", it is objectionable in just the same way that the liar paradox is. It refers to itself in a non-well-founded fashion. Tarski's response is to introduce a hierarchy of object language, metalanguage, metametalanguage, etc. A simple way to eliminate both the liar paradox and the difficulties attending "this sentence is not provable" is to impose a rule that sentences may not violate the hierarchy.

It helps when illustrating the distinction to use a different language between the object language and metalanguage. Consider:

La neige est noir.

The above is a sentence that I have selected to be in my object language. It is in French.

"La neige est noir" is false.

The above is a metalevel sentence in English that says of the object language sentence that it is false. Both of these are unproblematic: they do not refer to themselves. Now consider:

This sentence is false. This sentence is not provable.

These sentences violate the Tarskian hierarchy by trying to be both an object language sentence and a statement about an object language sentence. One of the simplest responses to such sentences is just to say they are not permitted, because of this violation. There are many other sophisticated ways of handling the liar paradox, but this is not the place for that.

Now Gödel comes along and does something ingenious. He shows how we can take a formal system of arithmetic, with its precisely defined language and provability relation, and formulate an arithmetical predicate in the object language that is satisfied by a number n if and only if n is the Gödel number of a provable sentence. This arithmetical predicate is abbreviated Bew(n) but it is a formula in arithmetic that can be written out using the language of first order logic.

If G is a sentence in the object language, it would not do to write:

G if and only if ⊬ G

since that violates the hierarchy. G is in the object language and ⊬ G is in the metalanguage. But thanks to Gödel we can instead write

G ↔ ¬Bew(⌜G⌝)

which lies entirely within the object language. (Where ↔ is the material biconditional and the corner quotes indicate Gödel number.) Gödel's proof shows that for formal systems that are consistent, recursively axiomatisable and sufficiently strong, there exists such a G. A Gödel sentence G is long and complicated, but it is not self-referential and it is not self-contradictory. For an example of what one looks like, see this answer on MathSE.

So, when your quoted passages say, quite correctly, that we should take with a grain of salt the idea that a Gödel sentence asserts its own unprovability, this is why. A Gödel sentence is literally just a sentence in the object language of arithmetic. It is only connected to a statement about unprovability via a material biconditional and an encoding of sentences into the language of arithmetic.

4
  • I just read through a note from Kripke about how to construct a version of G that is "'directly' self-referential" (I'm not sure why he uses the scare quotes), so should I say that it is possible but not necessary for G-sentences to assert both their own relative unprovability and provability? Dec 26, 2023 at 2:00
  • I also found, but can only read part of, this essay about the Yablo paradox which seems relevant (esp. since it is often contended that the Yablo sentences aren't self-referential). If you have access to the full article, and have the time to look through it, would you be able to tell if it's really relevant to my question? Dec 26, 2023 at 13:55
  • Oh nm on the access thing, I just have to scroll down in the window. Dec 26, 2023 at 14:40
  • The focus on the sentence G is a bit of a red herring if one's goal is to understand the phenomenon of incompleteness. A better sentence is simply the consistency of PA. See this question for a discussion: mathoverflow.net/questions/459481/… @K Dec 26, 2023 at 14:43
0

Turning David Gudeman's comment into an answer: what it means for a sentence to be self-referential is that it says something about itself, not that it says everything that could be said about itself. It's enough for GF to assert the unprovability-in-F of GF for it to be self-referential—dodging the question of whether it really does assert that, which I think is not relevant to the bolded part of your question.

Still dodging that question, GF definitely doesn't assert its own unprovability in any other formal system than F, or in any broader sense of provability at all. The provability predicate encoded in GF is specific to F.

0

The correct conclusion is: The Gödel sentence is either true but has no proof, or it is false and has a proof. A mathematical system powerful enough to express the Gödel sentence is either incomplete (true sentences without proof) or contradictory (false sentences without a proof).

Of course having a contradiction would be quite unfortunate and fatal.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .