[KongchangAI]
· 4 min read· 2,049 words

Gödel's Second Incompleteness Theorem: Why Theories Cannot Prove Their Own Consistency

Gödel's Second Incompleteness Theorem: Why Theories Cannot Prove Their Own Consistency

Gödel's Second Incompleteness Theorem shows that a consistent theory containing arithmetic cannot prove its own consistency, relying on provability conditions formalizing the First Theorem; Löb's Theorem reveals that T only vouches for already-proven sentences.

Starting from the "0=1 panic," the article explains Gödel's Second Incompleteness Theorem: a consistent theory containing Peano Arithmetic cannot prove its own consistency internally. The key to the proof is formalizing the First Theorem inside the theory, relying on three provability conditions D1, D2, D3, with D3 being the core black box. The article also introduces Löb's Theorem—T only vouches for sentences it has proven—and answers Henkin's question. By constructing the theory T' = T + "T is inconsistent," it shows that consistency is not soundness, and a consistent theory can prove falsehoods. Finally, it clarifies the theorem's applicability conditions, strength requirements, and common misunderstandings, and notes that the Second Theorem does not prevent stronger systems like ZFC from proving the consistency of PA.

Starting from the "0=1" Panic

If someone were to derive 0 = 1 from the axioms of Peano Arithmetic, step by step, the entire edifice of arithmetic would collapse—because from a contradiction, any proposition can be derived. Hilbert certainly did not believe such a thing would happen, but he wanted a proof: using the most plain, least controversial methods, prove that arithmetic will never yield a contradiction.

The question arises: Can Peano Arithmetic (PA) prove, within itself, that it cannot derive 0=1? The answer in this episode is no. And this "no" is almost a direct corollary of the Gödel sentence from the previous episode.

Consistency: A Sentence That "Never Halts"

Writing the consistency of a theory T as an arithmetic sentence gives "there is no code for a proof of a contradiction in T," denoted Con(T). You can imagine it as a machine: it continually checks natural numbers to see whether each is a code for a proof of a contradiction. What Con(T) says is—this machine never halts.

Halting has finite evidence; non-halting does not. Every specific number can be checked, but the difficulty lies in "all numbers." If T is truly consistent, Con(T) is a true sentence. Because "a contradiction is provable" is true if and only if T actually proves a contradiction, and when T is consistent the latter is false.

Third, third.

Gödel coding is the key technique for understanding Con(T). It maps the symbols, formulas, and proof sequences of a formal system T to natural numbers. Specifically, each symbol corresponds to a number, formulas correspond to sequences of numbers, and proof sequences (sequences of formulas) are encoded as a single natural number via techniques such as prime factorization. Thus, "there exists a proof of a contradiction in T" becomes a Σ₁ proposition about natural numbers: "There exists a natural number x such that x encodes a proof sequence starting from the axioms of T and ending in a contradiction." Since the correctness of a proof can be mechanically checked in finitely many steps, this proposition is formalizable in PA. Con(T) is the negation of this proposition, a Π₁ proposition.

Provability Conditions: Letting T Hold Up a Mirror

To transplant the proof of the First Theorem inside T, T needs to know enough about its own provability, namely three provability conditions (D1, D2, D3):

  • D1: If T proves φ, then T also proves "φ is provable." Every theorem outside the mirror is visible inside the mirror.
  • D2: T can prove "if φ is provable implies ψ is provable, and φ is provable, then ψ is provable." Reasoning inside the mirror also obeys modus ponens.
  • D3: If φ is provable, then "φ is provable" is provable. There is a mirror inside the mirror.

D3 does not hold for arbitrary sentences. Take the Gödel sentence G: if T proves "G implies G is provable," and together with "G implies G is not provable," then T proves G is false—but a consistent T will not prove G is false. D3 holds because of the specific form of the sentence "φ is provable": it says "there exists a proof," and once an existing thing is found, it can be checked step by step.

Now, if T could also prove I am consistent, then T could prove G.

Transplanting the First Theorem into T

Recall the argument of the First Theorem: if T proves G, by D1, T also proves "G is provable"; but G says precisely "G is not provable," and together they make T inconsistent. Condensed into one sentence: if T proves G, then T proves a contradiction.

Now replace every "proves" in this sentence with the formalized provability predicate Prov_T, and we obtain a sentence inside T: "if G is provable, then a contradiction is provable." T itself can prove this sentence, in the following steps:

  1. By the construction of G, T proves "G implies not P" (where P is "G is provable"). Note that not P is an abbreviation for P implies a contradiction.
  2. Apply D1 to the first line, then D2, obtaining "P implies (P implies a contradiction) is provable."
  3. Apply D2 again, obtaining "if (P implies a contradiction) is provable and P is provable, then a contradiction is provable."
  4. Apply D3 to G, obtaining "P implies P is provable."
  5. Assume P inside T, chain the second, fourth, and third steps, and finally obtain "a contradiction is provable."

Finally, take the contrapositive: if a contradiction is not provable, then G is not provable, which by the construction of G means G holds. T can prove "if I am consistent, then G." If T could also prove its own consistency, T could prove G—but the First Theorem says a consistent T cannot prove G, a contradiction. This is Gödel's Second Incompleteness Theorem: a consistent theory containing Peano Arithmetic cannot prove its own consistency. Read in reverse, it is even more striking: a theory that can prove its own consistency is precisely an inconsistent theory.

Löb's Theorem: T Only Vouches for Sentences It Has Proven

In 1952, Henkin asked the reverse question: using the diagonal lemma to construct a sentence H that says "I am provable," is H provable or not? Neither answer seems contradictory. In 1955, Löb gave the answer: H is provable. He proved a more general theorem: if T can prove "if φ is provable, then φ holds," then T can already prove φ. Note that no assumption of T's consistency is made here.

Löb's Theorem has another intriguing reading: "if φ is provable, then φ holds" is T vouching for φ. The theorem says T only dares to vouch for sentences it has already proven. Therefore, the true sentences T cannot prove are far more than just G.

The sentence H in Henkin's question is constructed via the diagonal lemma: there exists a sentence H such that T proves H ↔ Prov_T(⌜H⌝). Intuitively, H claims "I am provable." This construction contrasts with the Gödel sentence G (which claims "I am not provable"). Löb's Theorem shows that H is actually provable; its proof can be obtained directly by formalizing in T the condition "if H is provable then H" and using the construction of H. This resolves Henkin's question: of the two seemingly possible answers, only "H is provable" holds, and this does not conflict with the Second Theorem, because H itself does not claim that T is consistent.

Consistency Is Not Soundness: A Theory That Firmly Believes It Is Inconsistent

The Second Theorem has a seemingly absurd corollary: since T cannot prove Con(T), would adding its negation "T is inconsistent" as an axiom lead to a contradiction? No. If adding it led to a contradiction, T could prove Con(T) by reductio ad absurdum, which is impossible. Thus we obtain a consistent theory T' that firmly believes its base theory T is inconsistent—it proves "there exists a proof of a contradiction in T," but this sentence is false.

Because in the standard natural numbers, the sentence 'a contradiction is provable' is false.

The model of T' cannot be the standard natural numbers. In the standard natural numbers, "a contradiction is provable" is false; but in the model of T', there is indeed a nonstandard number b that the model believes encodes a proof of a contradiction. But from outside the model, the length of this "proof" is not finite; it is not a real proof at all. T's belief is wrong, but it can never refute this belief itself. This example clearly draws the distance between "consistency" and "soundness."

Nonstandard models are the key to explaining T''s behavior. A first-order arithmetic theory can have models not isomorphic to the standard natural numbers, called nonstandard models. These models contain all standard natural numbers 0, 1, 2, ..., but also contain "nonstandard integers" larger than any standard natural number. In the model of T' = T + ¬Con(T), although from the outside T is consistent, inside the model there exists a nonstandard number b that the model believes encodes a proof of a contradiction in T. Since b is nonstandard, its "length" is not finite, so it is not actually a real proof. However, T''s internal perspective cannot distinguish standard from nonstandard numbers, and thus firmly believes "T is inconsistent" is true. This reveals the limitations of first-order logic: a consistent theory can have nonstandard models in which false sentences are "proven."

Three Details That Must Be Clarified

Formulation: Con(T) depends on the specific formulation of Prov_T. The Second Theorem targets the "standard formulation," i.e., formulations satisfying D1 to D3. With an unnatural formulation, PA can even prove the corresponding consistency—so the statement of the theorem must be precise.

Strength: T is required to contain PA, not just Robinson Arithmetic Q, because the proofs of D2 and D3 require induction inside T.

Scope: It applies not only to arithmetic. Set theory ZFC can define natural numbers internally, so as long as ZFC is consistent, ZFC cannot prove its own consistency either.

What does this mean for Hilbert's program? It is usually thought that finitary methods can all be formalized in PA, so the Second Theorem shows that the consistency of PA has no finitary proof. But this does not mean the consistency of PA cannot be proven—ZFC can prove it, and Gentzen also gave a proof using transfinite induction. These proofs do not conjure confidence out of thin air; they merely transfer trust from PA to elsewhere; their real value is to precisely measure how strong the means must be to prove the consistency of PA.

It becomes a tiny modal wheel.

Writing "provable" as a box operator, D1 to D3 plus Löb's Theorem constitute a small modal logic, namely GL. In 1976, Solovay proved that all propositional logical laws of PA concerning its own provability are exactly the theorems of GL.

Gentzen's proof is an important complement to the Second Theorem. In 1936, Gentzen gave a proof of the consistency of PA, but used transfinite induction (up to the ordinal ε₀), a method that cannot be formalized inside PA. This precisely confirms the Second Theorem: any method sufficient to prove the consistency of PA must exceed the expressive power of PA. On the other hand, ZFC can prove the consistency of PA because ZFC is far stronger than PA. But these proofs do not "generate confidence out of thin air"; rather, they transfer trust from PA to a stronger system. The true significance of the Second Theorem is to precisely characterize the minimal strength required to prove the consistency of PA, thereby delineating the limits of finitistic methods, rather than denying the possibility of consistency proofs.

Four Common Misunderstandings

  1. "The Second Theorem shows we can never know whether mathematics is consistent"—Incorrect. The theorem only says T cannot prove its own consistency internally; the consistency of PA can be proven in ZFC.
  2. "If a system can prove its own consistency, it must be consistent"—Quite the opposite: for T satisfying the conditions, being able to prove its own consistency is equivalent to being inconsistent.
  3. "A consistent theory only tells the truth"—Incorrect. T plus "T is inconsistent" is a theory that is consistent yet proves falsehoods. Consistency only rules out self-contradiction, not false statements.
  4. "The Second Theorem applies to any formal system"—Also incorrect. It requires that the axioms can be listed by a machine, contain sufficient arithmetic, and that consistency is written in a natural way.

Opening the Last Black Box

What we did today is essentially to let T hold up a mirror: the provability conditions D1, D2, D3 allow T to talk about its own provability internally; transplanting the proof of the First Theorem into T, T proves "if I am consistent, then G"; thus, a consistent T cannot prove its own consistency. Löb's Theorem is the generalization of this picture, and the Second Theorem is its special case. And "T plus I am inconsistent" remains consistent, reminding us: consistency is not the same as telling the truth.

All six black boxes owed from the first episode are now repaid; the third provability condition is newly revealed. The next episode will examine each condition of the theorem and see what happens when each is removed.

#Gödel's Second Incompleteness Theorem#provability conditions#Löb's Theorem#Peano Arithmetic consistency#Hilbert's program
Share:

Related articles