Gui Ruiyan

Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理

Study journals ·

Gödel's Incompleteness Theorems — Session 2026‑08‑06

Reflections · Study sessions

AI-prepared recaps of study sessions; these are working notes, not verbatim transcripts. / AI 整理的学习记录,并非逐字实录。

Reading / 研读:Raymond Smullyan / 雷蒙德·斯穆里安 · Gödel’s Incompleteness Theorems 哥德尔不完备性定理

In this note / 篇目

Chapter IX: The Unprovability of Consistency (pp. 106–110) — the Second Theorem, made abstract, and Löb

The last meaty chunk. This is the chapter Chapter VIII was built to feed. Your 08‑05 forward‑note guessed its exact contents — the three derivability conditions D1/D2/D3, Löb's theorem, and the Second Theorem as the "X=⊥ case." All three land here. This doc is the payoff.


Orientation — what this chapter is for, and why it's short

The First Theorem was a metatheorem: standing outside S, we argued "if S is consistent, then G is unprovable." The Second Theorem does one thing: it drags that argument inside S. Once the reasoning "consistent ⟹ G unprovable" is itself a proof in S, a trap springs shut — S cannot prove its own consistency, because if it could, it could finish the internalized argument and prove G, which (by the First Theorem) it can't.

The chapter is compressed because Smullyan has already done the two hard jobs elsewhere and here only has to bolt them together:

  1. Chapter VIII gave the fixed point over the honest P: a sentence G with S ⊢ G ≡ ~P(Ḡ) — the equivalence provable in S, not merely true. (That "provable‑in‑S" was the whole point of the strong‑definability upgrade.)
  2. This chapter's §1 isolates exactly what P must satisfy for the internalization to go through — the three derivability conditions P₁, P₂, P₃. It does not re‑prove that P.A.'s provability formula satisfies them (P₃ in particular is deep — provable Σ₁‑completeness, punted to Boolos / Hilbert–Bernays). It assumes them and asks: what follows for any system whose provability predicate obeys these three rules?

That abstraction is the chapter's real content. Everything — Gödel's Second Theorem, Löb's theorem, the whole modal‑logic industry that grew out of it — falls out of three axioms about a box‑operator P plus one fixed point. The concrete P.A. statement is then just the special case where P is P.A.'s actual provability formula.

The spine, end to end:

P₁,P₂,P₃ (the box laws) → derived working rule (★) → Thm 1 (G unprovable, First‑Theorem half, internal P) → Thm 2 (S ⊢ consis ⊃ G, the internalization) → Thm 3 (Second Theorem: consistent ⟹ consis unprovable) → Thm 4 = Löb (and the Second Theorem re‑derived as Löb's Y = ⊥ case).

Read in that order; everything below unfolds it.


Part 0 — the one shift from Chapter VIII, and what carries over

Chapter VIII Chapter IX
the object a provable fixed point S⊢G≡~P(Ḡ) over the honest P the same G, now put to work
what we knew about P only that it represents P (Σ₁, from Ch. VII) three structural laws P₁,P₂,P₃ = the derivability conditions
the currency "the ≡ is provable in S" that provable ≡, run through the box laws to internalize the First Theorem
the result First Theorem, re‑derived via fixed points Second Theorem (S⊬Con(S)) + Löb

What carries over unchanged. The fixed point S⊢G≡~P(Ḡ) is imported verbatim from Ch. VIII Theorem 4 (via its Corollary: P.A. extends (R), so P.A. is diagonalizable). The predicate P is Ch. VII's representable provability set. The truth/provability split from Ch. VIII §5 is the license to have a formula P(v₁) at all. Nothing from Ch. V–VII's hand‑built diagonalization is needed — it's all been packaged.

The 08‑05 forecast, now discharged. Your last note predicted the Second Theorem still owed "D2, D3 on P + line‑by‑line formalization, expect Löb, 2nd Thm = X=⊥ case." Reconciliation:

08‑05 predicted Chapter IX delivers
D1: S⊢X ⟹ S⊢P(X̄) P₁ verbatim
D2: S⊢ P(X̄⊃Y) ⊃ (P(X̄)⊃P(Ȳ)) P₂ verbatim
D3: S⊢ P(X̄) ⊃ P(⌜P(X̄)⌝) P₃ verbatim
Löb: S⊢P(X̄)⊃X ⟹ S⊢X Theorem 4 verbatim
"2nd Thm = X=⊥ case of Löb" Kreisel's corollary (take Y = f, the refutable sentence)

Part I — the dependency map (the whole chapter on one page)

 §1  THE BOX LAWS (assumed of P; proved for P.A. elsewhere)
      P₁  ⊢X  ⟹  ⊢P(X̄)                         [necessitation / D1]
      P₂  ⊢ P(X̄⊃Y) ⊃ (P(X̄) ⊃ P(Ȳ))            [internal modus ponens / D2]
      P₃  ⊢ P(X̄) ⊃ P(P(X̄)‾)                     [provable-D1 / D3]
             │
             ├─ derive ─▶ P₄  ⊢X⊃Y ⟹ ⊢P(X̄)⊃P(Ȳ)              [monotonicity — workhorse]
             │            P₅  ⊢X⊃(Y⊃Z) ⟹ ⊢P(X̄)⊃(P(Ȳ)⊃P(Z̄))
             │            (★) ⊢X⊃(P(X̄)⊃Y) ⟹ ⊢P(X̄)⊃P(Ȳ)     [THE engine — Smullyan's P₆]
             ▼
 §2  THE SECOND THEOREM        + fixed point  G:  S⊢ G ≡ ~P(Ḡ)   (Ch. VIII)
      Thm 1  S consistent ⟹ G not provable            [uses P₁]        — First-Theorem half
      Thm 2  S ⊢ consis ⊃ G                            [uses (★)]       — THE internalization
      Thm 3  S consistent ⟹ consis not provable        [Thm 1 + Thm 2]  — SECOND THEOREM
             │
 §3  HENKIN + LÖB           + fixed point  X:  S⊢ X ≡ (P(X̄)⊃Y)
      Thm 4 (Löb)  ⊢P(Ȳ)⊃Y  ⟹  ⊢Y                    [uses (★), P₁]
             ├─▶ Henkin sentence H≡P(H̄) is PROVABLE (Y:=H)
             └─▶ Kreisel: Second Theorem = Löb at Y:=f  (the ⊥ case)

consis := ~P(f̄), where f is any refutable sentence (⊢~f); a common f is 0=1.


Part II — Citable glossary

Notation (carried + fixed for this chapter): for a sentence X, ⌜X⌝ = its Gödel number, X̄ = the numeral of ⌜X⌝. P(X̄) reads "X is provable in S." For a compound, Smullyan writes P(X̄⊃Y) to mean P(⌜X⊃Y⌝) = "X⊃Y is provable"; P(P(X̄)‾) means P(⌜P(X̄)⌝) = "the sentence P(X̄) is provable." Think of P(·) as a box □: P(X̄) = □X, "X is provable."

  • provability predicate for S: a formula P(v₁) satisfying, for all sentences X,Y:
  • P₁ (necessitation / D1): S⊢X ⟹ S⊢P(X̄). "If I actually prove X, I can prove that I prove X."
  • P₂ (distribution / D2): S⊢ P(X̄⊃Y) ⊃ (P(X̄) ⊃ P(Ȳ)). "S knows modus ponens about its own proofs."
  • P₃ (provable‑D1 / D3): S⊢ P(X̄) ⊃ P(P(X̄)‾). "S proves that P₁ holds — it can internally verify its own necessitation."
  • correct provability predicate: P(v₁) additionally expresses the true set P (P(X̄) is true iff X really is provable). The Second‑Theorem results below do NOT need correctness — only the three laws P₁,P₂,P₃. Correctness is only used to say consis means consistency.
  • diagonalizable S: every formula F(v₁) has a fixed point — a sentence X with S⊢ X ≡ F(X̄). (Ch. VIII Thm 4; P.A. qualifies because it extends (R).)
  • consistency sentence consis := ~P(f̄), f any refutable sentence (S⊢~f; e.g. f = 0=1). Reads "f is not provable." If P is correct: consis true ⟺ f unprovable ⟺ S consistent (an inconsistent S proves everything, in particular f).
  • Gödel sentence G: a fixed point of ~P(v₁), S⊢ G ≡ ~P(Ḡ). Reads "I am not provable."
  • Henkin sentence H: a fixed point of P(v₁), S⊢ H ≡ P(H̄). Reads "I am provable."

The derived working rules (proved in Part IV from the three laws):

  • P₄ (monotonicity): S⊢X⊃Y ⟹ S⊢ P(X̄)⊃P(Ȳ). The box respects provable implication. Used everywhere.
  • P₅: S⊢X⊃(Y⊃Z) ⟹ S⊢ P(X̄)⊃(P(Ȳ)⊃P(Z̄)).
  • (★) (the engine — Smullyan's P₆, and Exercise 1): S⊢ X⊃(P(X̄)⊃Y) ⟹ S⊢ P(X̄)⊃P(Ȳ). This single rule drives both Theorem 2 and Löb.

Part III — §1 The three box laws: what each one says, and why P.A.'s P obeys them

This is the part to slow down on, because the whole chapter is "run the box laws." Read P(X̄) as □X.

P₁ — necessitation. S⊢X ⟹ S⊢P(X̄).

"If X has an actual proof, then S can prove the statement P(X̄) = 'X is provable'." This is the easy half. In P.A., P(v₁) is a Σ₁ formula representing (a superset of) the provability set P; representing a superset already gives S⊢X ⟹ S⊢P(X̄). Simple consistency is enough for P₁ — you do not need the full ω‑consistency that makes P represent P exactly. (Smullyan flags this: under simple consistency P(v₁) may represent a superset of P, "but that is enough to imply" P₁.)

P₂ — distribution (internal modus ponens). S⊢ P(X̄⊃Y) ⊃ (P(X̄)⊃P(Ȳ)).

"S proves: if X⊃Y is provable and X is provable, then Y is provable." Its truth is obvious — it just says modus ponens is a valid rule of S, applied to proofs. The content of P₂ is that this obvious truth is itself provable in S (you formalize "concatenate the proof of X⊃Y, the proof of X, and one MP step" inside arithmetic). Smullyan: "not very difficult to formalize."

P₃ — provable necessitation (the deep one). S⊢ P(X̄) ⊃ P(P(X̄)‾).

"S proves: if X is provable, then it's provable that X is provable." Note this is P₁ with a turnstile wrapped around it — P₁ says "⊢X ⟹ ⊢P(X̄)" from outside; P₃ says S proves that implication internally. This is the genuinely hard condition. It is a special case of the fact:

for every Σ₁‑sentence Y, S⊢ Y ⊃ P(Ȳ) — "S proves that every true Σ₁‑fact is provable" (provable Σ₁‑completeness).

Since P(X̄) is itself Σ₁, take Y := P(X̄) and you get P₃. Smullyan does not prove this — "somewhat elaborate, beyond the scope of this volume" — and points to Boolos [1979] Ch. 2, Hilbert–Bernays [1934–39], Shoenfield [1967]. This is the one debt the chapter openly carries. (It dovetails with your outstanding Σ₁‑completeness debt from Ch. V §6 — same fact, provable version.)

Why this matters for the Second Theorem. P₃ is precisely what lets Theorem 1's meta‑step — "if G is provable then P(Ḡ) is provable" (an outside use of P₁) — be replayed inside S. Without P₃, S couldn't run its own necessitation, and the internalization (Theorem 2) would stall. P₃ is the hinge between "we can see it" and "S can prove it."

The abstraction move. From here Smullyan says: forget that P came from P.A. Assume only P₁,P₂,P₃. Everything below is a theorem about any diagonalizable S with a provability predicate. The concrete Gödel Second Theorem is recovered at the end by noting P.A.'s P satisfies the three laws.


Part IV — The derived rules (Part III's laws, repackaged for use)

Three consequences. P₄ is the workhorse; (★) is the engine that both big theorems actually turn on.

P₄ — monotonicity. If S⊢X⊃Y then S⊢P(X̄)⊃P(Ȳ).

step justification
S⊢X⊃Y hypothesis
S⊢P(X̄⊃Y) P₁ applied to X⊃Y
S⊢P(X̄⊃Y)⊃(P(X̄)⊃P(Ȳ)) P₂
S⊢P(X̄)⊃P(Ȳ) modus ponens on the last two
∎ "The box preserves provable implications" — □ is monotone.

P₅. If S⊢X⊃(Y⊃Z) then S⊢P(X̄)⊃(P(Ȳ)⊃P(Z̄)).

step justification
S⊢X⊃(Y⊃Z) hypothesis
S⊢P(X̄)⊃P(Ȳ⊃Z) P₄
S⊢P(Ȳ⊃Z)⊃(P(Ȳ)⊃P(Z̄)) P₂
S⊢P(X̄)⊃(P(Ȳ)⊃P(Z̄)) propositional chaining
∎

(★) — the engine (Smullyan's P₆; = Exercise 1). If S⊢ X⊃(P(X̄)⊃Y) then S⊢ P(X̄)⊃P(Ȳ).

This is the one rule to memorize — Theorem 2 and Löb are both one line once you have it. | step | justification | |---|---| | S⊢ X⊃(P(X̄)⊃Y) | hypothesis | | S⊢ P(X̄) ⊃ P(⌜P(X̄)⊃Y⌝) | P₄ applied to the hypothesis | | S⊢ P(⌜P(X̄)⊃Y⌝) ⊃ (P(P(X̄)‾) ⊃ P(Ȳ)) | P₂ (with P(X̄) playing the antecedent role) | | S⊢ P(X̄) ⊃ (P(P(X̄)‾) ⊃ P(Ȳ)) | chain the last two | | S⊢ P(X̄) ⊃ P(P(X̄)‾) | P₃ (at X) | | S⊢ P(X̄) ⊃ P(Ȳ) | propositional logic: discharge P(P(X̄)‾) using the previous line | ∎

Read (★) in English: if S proves "X, together with the provability of X, yields Y," then S proves "the provability of X yields the provability of Y." All three box laws pull their weight here — P₄ (built from P₁+P₂) to box the hypothesis, P₂ to distribute, P₃ to collapse the double box P(P(X̄)‾) back down. This is why Smullyan says P₄ and P₆ "play the key roles."


Part V — §2 The Second Theorem, proved in three moves

Fix a Gödel sentence G: S⊢ G ≡ ~P(Ḡ) (Ch. VIII). Read G as "I am not provable."

Theorem 1 — G is unprovable (the First‑Theorem half, over the honest P)

Statement. If S is consistent, G is not provable in S. Proof. Suppose, for contradiction, S⊢G. | fact | why | |---|---| | S⊢P(Ḡ) | P₁ applied to the assumed S⊢G | | S⊢G⊃~P(Ḡ) | forward half of the fixed point G≡~P(Ḡ) | | S⊢~P(Ḡ) | modus ponens: S⊢G and S⊢G⊃~P(Ḡ) |

Now S⊢P(Ḡ) and S⊢~P(Ḡ) — S is inconsistent, contradicting the hypothesis. Hence S⊬G. ∎

This is Chapter V's Theorem 1 (unprovability of G) reborn with the honest P and only simple consistency. Nothing new — it's the outside argument. The whole novelty of the chapter is that this argument can now be pushed inside S. That is Theorem 2.

Consistency sentences — and the crucial "we don't need P correct"

f = any refutable sentence (S⊢~f), say f = 0=1. consis := ~P(f̄) = "f is not provable." If P is correct, consis is a genuine arithmetic sentence that is true iff S is consistent (an inconsistent system proves f; a consistent one doesn't). But — and this is the subtle robustness of the result — Theorems 2 and 3 assume only that P is a provability predicate, not that it is correct. They are theorems about the syntactic behaviour of consis, independent of whether it "really means" consistency. That's what makes the Second Theorem abstract.

Theorem 2 — the internalization. S ⊢ consis ⊃ G.

This is the heart of the chapter: S itself proves "if I am consistent, then G is unprovable" (recall G is "G is unprovable," so ~P(Ḡ) = G; the statement is S⊢ ~P(f̄) ⊃ G). It is Theorem 1's meta‑argument, transcribed into S via (★).

Proof. | step | justification | |---|---| | (1) S⊢ G ⊃ ~P(Ḡ) | forward half of the fixed point | | (2) S⊢ G ⊃ (P(Ḡ) ⊃ f) | (1) + tautology ~A ⊃ (A ⊃ f) (with A = P(Ḡ)): "from ~P(Ḡ), P(Ḡ) yields anything" | | (3) S⊢ P(Ḡ) ⊃ P(f̄) | apply (★) to (2), with X := G, Y := f | | (4) S⊢ ~P(f̄) ⊃ ~P(Ḡ) | contrapositive of (3) | | (5) S⊢ ~P(Ḡ) ⊃ G | backward half of the fixed point | | (6) S⊢ ~P(f̄) ⊃ G, i.e. S⊢ consis ⊃ G | chain (4) then (5) | ∎

What just happened. Line (3), S⊢P(Ḡ)⊃P(f̄), is exactly Theorem 1's meta‑step, internalized: Theorem 1 argued "G provable ⟹ P(Ḡ) provable ⟹ (with G⊃~P(Ḡ)) S inconsistent, i.e. f provable." Line (3) says S proves that very implication — "if G is provable then f is provable." (★) is what does the internalizing, and inside (★) it was P₃ that let S run the P₁ step ("G provable ⟹ P(Ḡ) provable") on its own. Then lines (4)–(6) just repackage: "provability of G forces inconsistency" ⟺ "consistency forces G (unprovable)."

Theorem 3 — Gödel's Second Theorem (abstract form). If S is diagonalizable and consistent, then consis is not provable in S.

Proof. S diagonalizable ⟹ a Gödel sentence G exists (fixed point of ~P). By Theorem 2, S⊢ consis ⊃ G.

Suppose S⊢ consis. Then by modus ponens S⊢ G. But by Theorem 1, if S is consistent then S⊬G. So S would be inconsistent.

Contrapositive: if S is consistent, then S⊬ consis. ∎

Concrete Gödel Second Theorem (the headline). P.A. is diagonalizable (extends (R); Ch. VIII Thm 4 Cor) and its standard provability formula P(v₁) is a provability predicate (P₁,P₂,P₃ hold — P₃ via provable Σ₁‑completeness). Therefore:

If P.A. is consistent, then P.A. ⊬ Con(P.A.) — P.A. cannot prove its own consistency.

Notice how little the proof "knows." It never opens up what consis means; it only pushes consis through (★) and the fixed point. That is why the result generalizes to any S obeying the three box laws — the origin of the whole provability‑logic program.


Part VI — §2 Discussion: why this is no cause to doubt P.A.

The Second Theorem is the most mis‑read result in logic. Smullyan heads that off. The naïve reading — "P.A. can't even prove it's consistent, so maybe it isn't" — is backwards. The key observation:

An inconsistent system can prove its own consistency — trivially, because it proves everything, including consis.

So "S ⊢ consis" is worthless as reassurance: a healthy consistent system fails to prove consis (Theorem 3), while a broken inconsistent one succeeds (it proves all sentences). Provability of one's own consistency is a red flag, not a green one. Smullyan's analogy: trusting someone's honesty because they assure you "I never lie" — a liar says that too. The sentence carries no evidential weight either way.

So P.A.'s inability to prove Con(P.A.) is exactly what a consistent system is supposed to look like. Our confidence in P.A.'s consistency comes from outside P.A. (e.g. the standard model ℕ, or a stronger metatheory), never from a certificate P.A. issues to itself — and the Second Theorem says such a self‑certificate is unavailable precisely when it would be honest.


Part VII — §3 Henkin sentences and Löb's Theorem

The Gödel sentence says "I am not provable" and is true‑but‑unprovable. Henkin (1952) asked the mirror question: the fixed point of P(v₁) itself — a sentence H with S⊢ H ≡ P(H̄), saying "I am provable." Is H true or false? Provable or not?

Naïve reasoning stalls. If H is provable, then P(H̄) is true, so H≡P(H̄) makes H true — consistent. If H is unprovable, then P(H̄) is false, so H is false (~H true) — also internally consistent. The self‑reference is symmetric, so neither scenario is absurd on its face. It took a real theorem to settle it.

Theorem 4 — Löb's Theorem. If S is diagonalizable and S⊢ P(Ȳ)⊃Y, then S⊢Y.

Read it as: "S can only prove 'Y is provable ⟹ Y' in the case where Y is actually provable." You cannot get Y for free by asserting its own provability implies it — unless Y was provable all along.

Proof. Assume S⊢ P(Ȳ)⊃Y. Diagonalize the formula P(v₁)⊃Y: get a fixed point X with S⊢ X ≡ (P(X̄)⊃Y). | step | justification | |---|---| | (1) S⊢ X ⊃ (P(X̄)⊃Y) | forward half of the fixed point | | (2) S⊢ P(X̄) ⊃ P(Ȳ) | apply (★) to (1) — with X := X, Y := Y | | (3) S⊢ P(Ȳ) ⊃ Y | hypothesis | | (4) S⊢ P(X̄) ⊃ Y | chain (2),(3) | | (5) S⊢ (P(X̄)⊃Y) ⊃ X | backward half of the fixed point | | (6) S⊢ X | modus ponens: (4) is P(X̄)⊃Y, feed into (5) | | (7) S⊢ P(X̄) | P₁ applied to (6) | | (8) S⊢ Y | modus ponens: (7) into (4) | ∎

Same engine as Theorem 2 — line (2) is one clean use of (★). The extra moves exploit that the fixed point is now of P(v₁)⊃Y, so the sentence X is (P(X̄)⊃Y), letting line (4) feed straight into the fixed point to produce X, and then P₁ closes the loop.

Henkin resolved. Take Y := H. Since H≡P(H̄), in particular S⊢ P(H̄)⊃H. Löb's hypothesis is met, so S⊢H. The Henkin sentence is provable (hence true). "I am provable" is, in fact, provable — self‑fulfilling in the honest direction.

Kreisel's corollary — the Second Theorem is Löb at Y = f (the "⊥ case")

This is the elegant repackaging your 08‑05 note predicted. Take Y := f, a refutable sentence.

Suppose S⊢ consis, i.e. S⊢ ~P(f̄). By the tautology ~P(f̄) ⊃ (P(f̄)⊃f), we get S⊢ P(f̄)⊃f. That is exactly Löb's hypothesis with Y=f, so by Löb S⊢f. But f is refutable (S⊢~f) — S is inconsistent.

Contrapositive: S consistent ⟹ S⊬ consis. Theorem 3 falls out of Löb in three lines. The Second Theorem is precisely Löb's theorem applied to a false (⊥‑like) sentence: "you can't prove '⊥ is provable implies ⊥'" is just "you can't prove your own consistency."

Intuition — why Löb does not prove everything (the Curry worry, defused)

The fear. Löb says "S⊢P(Ȳ)⊃Y ⟹ S⊢Y." So if you could just prove the modest‑looking Promise "if Y is provable, then Y," you'd get Y for free — for any Y: Santa exists, 0=1, anything. That would make the system prove everything. Why doesn't it?

The defusing — Route A / Route B. To prove any conditional "if A then B," there are only two honest doors: - Route A — deliver the consequent: prove B. For the Promise this means prove Y (derive the sentence itself — a provability act, not "Y is true"; a true‑but‑unprovable Y does not open this door). - Route B — kill the antecedent: prove ¬A. For the Promise this means prove "Y is not provable."

Route B is bricked shut — and that brick is the Second Theorem. To prove "Y is never provable" is to guarantee that, out of infinitely many possible proofs, none ever yields Y. That guarantee is a full consistency certificate in disguise, because of explosion:

Explosion (ex falso quodlibet). An inconsistent system proves every sentence. Proof: if S⊢X and S⊢~X, then for any Q: from X infer X∨Q (a weaker claim — safe for any Q); but ~X kills the X branch, so X∨Q can only stand as Q; hence S⊢Q. ∎

So an inconsistent system leaves nothing unprovable. Read backwards: if even one sentence Y is unprovable, the system is consistent — part ⟹ whole, because inconsistency spares nothing. (Possessed‑printer image: a printer that, once jammed, prints every page; "it never prints the Santa page" already certifies "it never jammed.") And S proves this implication itself — from the logical truth ⊢ ⊥⊃Y and monotonicity P₄, S ⊢ P(⊥)⊃P(Ȳ), i.e. S ⊢ ~P(Ȳ) ⊃ Con(S). So proving Route B would prove Con(S) — forbidden by the Second Theorem. Route B is shut for every Y.

That leaves only Route A: actually prove Y. So proving the Promise = proving Y — provability throughout, no truth smuggled in. The Promise is never a shortcut; it is Y wearing a disguise. For a Y the system can't prove (Santa, 0=1), the Promise is flatly unprovable, so Löb never fires. Löb only ever fires on Y that was a theorem all along — no free lunch, no explosion.

target Y Route A (prove Y) Route B (prove Y unprovable) Promise provable?
a theorem (0=0) open — yes (redundantly)
true but unprovable shut shut (= a consistency claim) no
false / 0=1 shut shut (literally Con(S)) no — this is the Second Theorem

And the triple equivalence behind it all. For any Y: S⊢Y ⟺ S⊢P(Ȳ)⊃Y ⟺ S⊢Y≡P(Ȳ). (⟹: by P₁, both sides provable ⟹ biconditional provable. Middle ⟹ right ⟹ left: Löb.) So provable, reflection‑provable, and Henkin‑shaped are three names for one set — the theorems. No scarce "self‑referential shape" unlocks provability; all three pick out exactly the theorems.

Kripke's observation, and where this goes next

Saul Kripke noted the converse: Löb's theorem can itself be obtained as a corollary of the Second Theorem (applied to S extended appropriately) — so Löb and Gödel‑II are, in this setting, inter‑derivable. Smullyan closes by pointing at the modern descendant: the box laws P₁,P₂,P₃ are exactly the axioms of the modal provability logic GL (Gödel–Löb), where Löb's theorem becomes the single modal axiom □(□Y⊃Y)⊃□Y. He recommends Boolos, The Unprovability of Consistency as the follow‑up — the whole subject reappears as modal logic there.

Exercise 1 (the one exercise): Show that if S⊢ X⊃(P(X̄)⊃Y) then S⊢ P(X̄)⊃P(Ȳ). — This is (★) itself; its proof is the table in Part IV. Doing it by hand is the way to own the engine both big theorems ride on.


Part VIII — Capstone: the whole book as one arc

You're finishing, so it's worth seeing the three‑week climb as a single line. Each stage was a different way of holding self‑reference:

chapters the move the self‑reference the result
II–IV truth vs. definability; arithmetization — Tarski: truth not definable; the coding that makes "provable" a formula
V hand‑built diagonal G=∀y~A(h̄,y), reason from outside in P* via E_n(n̄) First Theorem (Gödel form): ω‑consistent ⟹ incomplete
VI the ≤‑race ρ, separation not representation in P* Rosser: simple consistency ⟹ incomplete
VII invert Rosser's machinery in P* Shepherdson representation: Σ₁ sets representable from simple consistency
VIII package self‑reference as one lemma, over the honest P, ≡ provable in S Fixed‑Point Lemma (Thm 4) Gödel, Rosser, Tarski as corollaries; provability representable but truth not
IX give P its three box laws, run the internalized argument fixed point of ~P (and of P) Second Theorem S⊬Con(S); Löb

The single sentence that threads all of it:

Chapters V–VII build a self‑referential sentence and reason about it from outside → First Theorem. Chapter VIII makes the self‑reference a provable fixed point over the real provability predicate. Chapter IX endows that predicate with the three box laws and replays the First Theorem inside S → the Second Theorem, with Löb as its reflection.

And the deepest through‑line — the three tiers from your 08‑05 note — is what makes the ending possible: truth is not expressible, but provability is representable. That asymmetry is exactly why S can form the sentence consis and reason about its own proofs (Second Theorem) but can never reason about its own truth (Tarski). The Second Theorem is the sharpest thing a system can say about the middle tier: S cannot prove the one fact about its own provability that it would most like to — that it never proves a falsehood.


Distinctions Ledger

Confusion One‑line resolution
P₁ vs P₃? P₁ = necessitation from outside (⊢X ⟹ ⊢P(X̄)). P₃ = S proves that implication internally (⊢ P(X̄)⊃P(P(X̄)‾)). P₃ = "provable P₁."
Why is P₃ the hard one? It is provable Σ₁‑completeness (⊢ Y⊃P(Ȳ) for Σ₁ Y) at Y=P(X̄). Smullyan doesn't prove it — punts to Boolos / Hilbert–Bernays. The chapter's one open debt.
What does (★) do that P₄ alone can't? P₄ boxes a plain implication. (★) handles an implication whose antecedent already contains a box (X⊃(P(X̄)⊃Y)), collapsing the resulting double box via P₃. It's the "self‑referential modus ponens."
Theorem 1 vs Theorem 2? Thm 1 = the First‑Theorem argument (G unprovable) from outside, uses only P₁. Thm 2 = that same argument internalized, S⊢consis⊃G, uses (★) (hence P₂,P₃,P₄).
Why doesn't the Second Theorem need P correct? Theorems 2,3 are purely syntactic — they push consis through (★) and the fixed point. Correctness is only needed to interpret consis as "S is consistent."
Is inability to prove Con a reason to distrust P.A.? No — the opposite. Inconsistent systems can prove their own consistency (they prove everything); consistent ones can't. Self‑certified consistency is a red flag.
Gödel sentence vs Henkin sentence? G≡~P(Ḡ) ("I'm unprovable") is true & unprovable. H≡P(H̄) ("I'm provable") is, by Löb, provable & true.
Second Theorem vs Löb? Second Theorem = Löb at Y=f (refutable): "can't prove P(f̄)⊃f" = "can't prove ~P(f̄)" = "can't prove consistency." Kripke: they're inter‑derivable here.
What are P₁,P₂,P₃ "really"? The axioms of modal provability logic GL; P(·)=□. Löb's theorem = the modal axiom □(□Y⊃Y)⊃□Y.

Self‑Test

Q1. State the three defining conditions P₁,P₂,P₃ of a provability predicate, and say which is the deep one and why.

answerP₁: ⊢X ⟹ ⊢P(X̄) (necessitation). P₂: ⊢ P(X̄⊃Y)⊃(P(X̄)⊃P(Ȳ)) (distribution/internal MP). P₃: ⊢ P(X̄)⊃P(P(X̄)‾) (provable necessitation). P₃ is deep — it is provable Σ₁‑completeness (⊢ Y⊃P(Ȳ) for Σ₁ Y) specialized to Y=P(X̄); Smullyan doesn't prove it. P₁,P₂ are easy/formalizable.

Q2. Prove (★): if S⊢ X⊃(P(X̄)⊃Y) then S⊢ P(X̄)⊃P(Ȳ).

answerBy P₄ on the hypothesis: ⊢ P(X̄)⊃P(⌜P(X̄)⊃Y⌝). By P₂: ⊢ P(⌜P(X̄)⊃Y⌝)⊃(P(P(X̄)‾)⊃P(Ȳ)). Chain: ⊢ P(X̄)⊃(P(P(X̄)‾)⊃P(Ȳ)). By P₃: ⊢ P(X̄)⊃P(P(X̄)‾). Propositional logic collapses the double box: ⊢ P(X̄)⊃P(Ȳ).

Q3. Prove Theorem 2 (S⊢ consis⊃G) from the fixed point and (★).

answerFixed point: ⊢ G⊃~P(Ḡ), so ⊢ G⊃(P(Ḡ)⊃f) (tautology ~A⊃(A⊃f)). Apply (★) with X=G,Y=f: ⊢ P(Ḡ)⊃P(f̄). Contrapose: ⊢ ~P(f̄)⊃~P(Ḡ). With the other fixed‑point half ⊢ ~P(Ḡ)⊃G, chain: ⊢ ~P(f̄)⊃G, i.e. ⊢ consis⊃G.

Q4. Prove Theorem 3 from Theorems 1 and 2.

answerDiagonalizable ⟹ a fixed point G of ~P exists. Thm 2: ⊢ consis⊃G. If ⊢ consis then (MP) ⊢G; but Thm 1 says a consistent S has ⊬G, so S would be inconsistent. Hence S consistent ⟹ ⊬ consis.

Q5. State Löb's theorem and use it to settle the Henkin sentence.

answerLöb: if S diagonalizable and ⊢ P(Ȳ)⊃Y, then ⊢Y. Henkin H≡P(H̄) gives ⊢ P(H̄)⊃H; by Löb ⊢H. So the Henkin sentence ("I am provable") is provable and true.

Q6. Derive the Second Theorem as a corollary of Löb (Kreisel).

answerTake Y=f refutable. If ⊢ consis = ~P(f̄), then by ~P(f̄)⊃(P(f̄)⊃f) we get ⊢ P(f̄)⊃f — Löb's hypothesis at Y=f. So ⊢f, contradicting ⊢~f. Hence consistent ⟹ ⊬consis.

Q7. Why is P.A.'s inability to prove its own consistency not evidence that P.A. might be inconsistent?

answerAn inconsistent system proves everything, including consis; so provability of one's own consistency is exactly what a broken system does, and unavailability of it is what a healthy one does (Thm 3). A self‑issued consistency certificate carries zero evidential weight — like a liar saying "I never lie." Confidence in P.A. comes from outside (the standard model), not from a self‑proof.


Imported result Used in Source
Fixed‑point (diagonalization) lemma; P.A. diagonalizable §1 (def of diagonalizable), everywhere a fixed point is taken 08‑05 Thm 4 + Cor
P representable (Σ₁), truth not expressible — the split licensing P(v₁) §1 (that P(v₁) exists at all) 08‑05 §5, three‑tier moral
D1/D2/D3 forecast; Löb + "X=⊥ case" prediction Part 0 reconciliation 08‑05 Part IX forward‑note
First Theorem (unprovability of G), simple consistency Thm 1 (the "outside" half) 07‑30 Thm 3, 08‑03 Rosser
Provable Σ₁‑completeness (⊢ Y⊃P(Ȳ) for Σ₁ Y) P₃ (assumed, not proved) Boolos [1979] Ch. 2; Hilbert–Bernays [1934–39]; Shoenfield [1967] — the chapter's open debt
Tarski (truth not definable) Part VIII capstone Ch. II; 08‑05 §5

Book span this session: Smullyan, Gödel's Incompleteness Theorems, Ch. IX, pp. 106–110 — §1 (P₁–P₃; derived P₄,P₅,P₆), §2 (Thm 1, consistency sentences, Thm 2, Thm 3, Discussion), §3 (Henkin's question, Thm 4 = Löb, Kreisel corollary, Kripke observation, Exercise 1).


What's ahead — you've reached the summit

  • Chapter IX is the last major result of the book. The First Theorem (Ch. V–VII), its clean packaging (Ch. VIII), and the Second Theorem + Löb (Ch. IX) are the three peaks — all now climbed.
  • The one honest debt to close if you want airtight foundations: P₃ (provable Σ₁‑completeness). It is stated‑not‑proved here and it is the same fact behind your outstanding Ch. V §6 Ex 10–12 / Ex 11 Σ₁‑completeness debt. The natural next book is Boolos, The Unprovability of Consistency (Smullyan's own recommendation) or Boolos & Jeffrey, Computability and Logic Ch. 16 (cited in the footnote), where P₃ is proved and the modal logic GL is developed — Löb's theorem as the axiom □(□Y⊃Y)⊃□Y.
  • Drills worth doing to consolidate: Exercise 1 (= re‑derive (★) by hand — the engine); rewrite Theorem 2 and Löb side by side and confirm they share exactly the (★) step; and, for closure, verify Kripke's converse direction (Löb from Gödel‑II) as a sketch.

Prior session files: 07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 · 08‑03 · 08‑04 · 08‑05 · 08‑06 (this file).