The limits of formal proof › Constructing the Sentence

Michael BrenndoerferUpdated May 25, 20263 min read
PhilosophyAll chapters
Reading tools Notes & comments
Notes & comments
Part 8 of 12Logic, Language, and Interpretation
Chapter 96The limits of formal proof › Constructing the Sentence
Reading section 4 of 8 · Constructing the Sentence · 3 minSection 4 of 8 · 3 min

Section 4 of 8 · 3 min read

The limits of formal proof › Constructing the SentenceSection view · Sections in this chapter4 / 8 ↓

How can a sentence make a claim about its own proof code? Suppose we begin with a formula that says of a number that it is not the code of a theorem. We cannot simply add the words “this sentence” to the formula. Gödel exploits the substitution operation to achieve the effect inside arithmetic. The method, often explained today through the diagonal lemma, produces a sentence G whose equivalence to “there is no proof of the sentence with G's code” is itself provable in the theory.

A useful distinction is between a number and the numeral for it. The number is the code assigned to a formula. The numeral is a term in the formal language designating that number. When the construction feeds a numeral into a formula, it can refer to the code of an expression without using that expression as a literal part of itself. In particular, the finished sentence can be finite. The construction works through a relation between numerical descriptions. It does not require the sentence to reprint itself anywhere.

We can now ask what would happen if the theory proved G. There would be an actual finite derivation, with a particular code p. Verification of the concrete derivation yields an arithmetical certificate that p is a proof of G, one the theory can recognize. But proving G also gives a proof of the claim that there is no such code. The theory would thus prove conflicting assertions. Consistency suffices to exclude a proof of G in this construction.

What if the theory proves the negation of G? This is the other half of the argument and has a different logical shape. Given consistency, there is no actual proof of G. For each particular numeral, the theory can check that the numeral does not code a proof of G. A proof of the negation of G would nevertheless establish that some number is a proof code. It would thereby assert that an instance of a condition exists while denying that each particular numeral satisfies it. That combination can occur in a merely consistent theory. To rule it out by this route, Gödel appeals to ω-consistency. This is the stronger assumption in his original Proposition VI.

This point is easy to miss if the construction is told only as a story about the liar paradox. G says something specific about provability under a fixed set of rules. The proof treats the positive and negative cases separately, and the historical version needs different resources for them. J. Barkley Rosser's 1936 paper changes the construction and obtains undecidability from ordinary consistency, with the other relevant hypotheses on the theory. The common modern statement is stronger than the 1931 argument for Gödel's original G.

Comments

Add to the conversation

A question, a correction, or an example from your own work.

No comments yet. Be the first to share your thoughts!

Newsletter

Stay up to date

Get new articles, book updates, and notes on AI and technology.

Unsubscribe at any time. Privacy policy