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
- Orientation — what this chapter is for, and why it's short
- Part 0 — the one shift from Chapter VIII, and what carries over
- Part I — the dependency map (the whole chapter on one page)
- Part II — Citable glossary
- Part III — §1 The three box laws: what each one says, and why P.A.'s P obeys them
- Part IV — The derived rules (Part III's laws, repackaged for use)
- Part V — §2 The Second Theorem, proved in three moves
- Theorem 1 — G is unprovable (the First‑Theorem half, over the honest P)
- Consistency sentences — and the crucial "we don't need P correct"
- Theorem 2 — the internalization. S ⊢ consis ⊃ G.
- Theorem 3 — Gödel's Second Theorem (abstract form). If S is diagonalizable and consistent, then consis is not provable in S.
- Part VI — §2 Discussion: why this is no cause to doubt P.A.
- Part VII — §3 Henkin sentences and Löb's Theorem
- Part VIII — Capstone: the whole book as one arc
- Distinctions Ledger
- Self‑Test
- References & cross‑links
- What's ahead — you've reached the summit
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:
- Chapter VIII gave the fixed point over the honest
P: a sentenceGwithS ⊢ G ≡ ~P(Ḡ)— the equivalence provable inS, not merely true. (That "provable‑in‑S" was the whole point of the strong‑definability upgrade.) - This chapter's §1 isolates exactly what
Pmust satisfy for the internalization to go through — the three derivability conditionsP₁, 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 (Gunprovable, First‑Theorem half, internalP) → Thm 2 (S ⊢ consis ⊃ G, the internalization) → Thm 3 (Second Theorem: consistent ⟹consisunprovable) → Thm 4 = Löb (and the Second Theorem re‑derived as Löb'sY = ⊥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 formulaP(v₁)satisfying, for all sentencesX,Y: P₁(necessitation / D1):S⊢X ⟹ S⊢P(X̄). "If I actually proveX, I can prove that I proveX."P₂(distribution / D2):S⊢ P(X̄⊃Y) ⊃ (P(X̄) ⊃ P(Ȳ)). "Sknows modus ponens about its own proofs."P₃(provable‑D1 / D3):S⊢ P(X̄) ⊃ P(P(X̄)‾). "Sproves thatP₁holds — it can internally verify its own necessitation."- correct provability predicate:
P(v₁)additionally expresses the true setP(P(X̄)is true iffXreally is provable). The Second‑Theorem results below do NOT need correctness — only the three lawsP₁,P₂,P₃. Correctness is only used to sayconsismeans consistency. - diagonalizable
S: every formulaF(v₁)has a fixed point — a sentenceXwithS⊢ X ≡ F(X̄). (Ch. VIII Thm 4; P.A. qualifies because it extends (R).) - consistency sentence
consis:= ~P(f̄),fany refutable sentence (S⊢~f; e.g.f = 0=1). Reads "fis not provable." IfPis correct:consistrue ⟺funprovable ⟺Sconsistent (an inconsistentSproves everything, in particularf). - Gödel sentence
G: a fixed point of~P(v₁),S⊢ G ≡ ~P(Ḡ). Reads "I am not provable." - Henkin sentence
H: a fixed point ofP(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'sP₆, 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(Ȳ)— "Sproves 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 — "ifGis provable thenP(Ḡ)is provable" (an outside use ofP₁) — be replayed insideS. WithoutP₃,Scouldn't run its own necessitation, and the internalization (Theorem 2) would stall.P₃is the hinge between "we can see it" and "Scan 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 ponensS⊢ G. But by Theorem 1, ifSis consistent thenS⊬G. SoSwould 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 getS⊢ P(f̄)⊃f. That is exactly Löb's hypothesis withY=f, so by LöbS⊢f. Butfis refutable (S⊢~f) —Sis 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⊢XandS⊢~X, then for anyQ: fromXinferX∨Q(a weaker claim — safe for anyQ); but~Xkills theXbranch, soX∨Qcan only stand asQ; henceS⊢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.
answer
P₁: ⊢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(Ȳ).
answer
By 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 (★).
answer
Fixed 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.
answer
Diagonalizable ⟹ 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.
answer
Lö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).
answer
Take 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?
answer
An 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.
References & cross‑links
| 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), whereP₃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).
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
第九章:一致性的不可证明性(第106–110页)——抽象化的第二定理,以及勒布定理
最后一块实质性内容。第八章就是为本章做准备的。你8月5日的前瞻笔记准确猜中了内容:三个可推导性条件D1/D2/D3、勒布定理,以及作为“X=⊥情形”的第二定理。三者都在这里落地。本文就是收获。
导览——本章的目的,以及它为什么简短
第一定理是元定理:站在S的外面,我们论证“如果S一致,那么G不可证明”。第二定理只做一件事:把这个论证拉进S内部。一旦“一致⟹G不可证明”的推理本身成为S中的证明,陷阱就合上了:S不能证明自己一致,因为如果能,它就能完成内部化的论证,证明G,而由第一定理,它做不到。
本章如此紧凑,是因为斯穆里安已在别处完成两件困难的工作,在这里只需把它们接起来:
- 第八章给出了针对诚实的
P的不动点:语句G满足S ⊢ G ≡ ~P(Ḡ);等价关系在S中可证明,不只是为真。(这个“在S中可证明”,就是升级到强可定义性的全部意义。) - 本章§1精确分离出内部化所需的
P必须满足的条件,即三个可推导性条件P₁, P₂, P₃。它没有重新证明P.A.的可证明性公式满足这些条件(尤其P₃很深:可证明的Σ₁完备性,交给布洛斯/希尔伯特–伯奈斯处理)。它假定这些条件,追问:对任何可证明性谓词服从这三条规则的系统,能推出什么?
这种抽象才是本章的真正内容。一切——哥德尔第二定理、勒布定理,以及由此生长的整个模态逻辑领域——都从关于盒算子P的三条公理加上一个不动点中导出。具体的P.A.陈述,只是P为P.A.实际可证明性公式时的特例。
从头到尾的主线:
P₁,P₂,P₃(盒算子规则)→导出的工作规则(★)→定理1(G不可证明,第一定理的半边,使用内部P)→定理2(S ⊢ consis ⊃ G,内部化)→定理3(第二定理:一致⟹consis不可证明)→定理4=勒布定理(再把第二定理作为勒布的Y = ⊥情形导出)。
按这个顺序读,下文逐步展开它。
第零部分——相较第八章唯一的转变,以及保留的内容
| 第八章 | 第九章 | |
|---|---|---|
| 对象 | 针对诚实的P的可证明不动点S⊢G≡~P(Ḡ) |
同一个G,现在投入使用 |
对P已知什么 |
只知道它表示P(来自第七章的Σ₁) |
三条结构规则P₁,P₂,P₃=可推导性条件 |
| 依靠的东西 | “≡在S中可证明” |
这个可证明的≡,经盒算子规则运作,把第一定理内部化 |
| 结果 | 通过不动点重新导出第一定理 | 第二定理(S⊬Con(S))+勒布定理 |
原样保留的内容。不动点S⊢G≡~P(Ḡ)直接来自第八章定理4(通过其推论:P.A.扩张(R),所以P.A.可对角化)。谓词P是第七章可表示的可证明性集合。第八章§5的真/可证明性区分,为公式P(v₁)的存在提供了许可。不再需要第五至第七章任何手工构造的对角化步骤,一切已被打包。
8月5日的预告,现在兑现。你上一条笔记预言第二定理还欠“关于P的D2, D3+逐行形式化,预计会有勒布,第二定理=X=⊥情形”。对照如下:
| 8月5日的预言 | 第九章的兑现 |
|---|---|
D1: S⊢X ⟹ S⊢P(X̄) |
原样的P₁ |
D2: S⊢ P(X̄⊃Y) ⊃ (P(X̄)⊃P(Ȳ)) |
原样的P₂ |
D3: S⊢ P(X̄) ⊃ P(⌜P(X̄)⌝) |
原样的P₃ |
勒布:S⊢P(X̄)⊃X ⟹ S⊢X |
原样的定理4 |
“第二定理=勒布的X=⊥情形” |
克赖塞尔的推论(取Y = f,即可反驳的语句) |
第一部分——依赖图(用一页呈现整章)
§1 盒算子规则(对P作假定;对P.A.在别处证明)
P₁ ⊢X ⟹ ⊢P(X̄) [必然化 / D1]
P₂ ⊢ P(X̄⊃Y) ⊃ (P(X̄) ⊃ P(Ȳ)) [内部肯定前件 / D2]
P₃ ⊢ P(X̄) ⊃ P(P(X̄)‾) [可证明的D1 / D3]
│
├─ 导出 ─▶ P₄ ⊢X⊃Y ⟹ ⊢P(X̄)⊃P(Ȳ) [单调性:主力规则]
│ P₅ ⊢X⊃(Y⊃Z) ⟹ ⊢P(X̄)⊃(P(Ȳ)⊃P(Z̄))
│ (★) ⊢X⊃(P(X̄)⊃Y) ⟹ ⊢P(X̄)⊃P(Ȳ) [核心引擎:斯穆里安的P₆]
▼
§2 第二定理 + 不动点 G: S⊢ G ≡ ~P(Ḡ) (第八章)
定理1 S一致 ⟹ G不可证明 [用P₁] ——第一定理的半边
定理2 S ⊢ consis ⊃ G [用(★)] ——内部化
定理3 S一致 ⟹ consis不可证明 [定理1+定理2] ——第二定理
│
§3 亨金+勒布 + 不动点 X: S⊢ X ≡ (P(X̄)⊃Y)
定理4(勒布) ⊢P(Ȳ)⊃Y ⟹ ⊢Y [用(★)、P₁]
├─▶ 亨金语句H≡P(H̄)可证明(Y:=H)
└─▶ 克赖塞尔:第二定理=Y:=f时的勒布定理(⊥情形)
consis := ~P(f̄),其中f是任意可反驳的语句(⊢~f);常用的f是0=1。
第二部分——可供引用的术语表
记号(沿用并在本章固定):对语句X,⌜X⌝=其哥德尔数,X̄=⌜X⌝的数码。P(X̄)读作“X在S中可证明”。对复合式,斯穆里安写P(X̄⊃Y)来表示P(⌜X⊃Y⌝)=“X⊃Y可证明”;P(P(X̄)‾)表示P(⌜P(X̄)⌝)=“语句P(X̄)可证明”。可以把P(·)看作一个盒算子□:P(X̄) = □X,“X可证明”。
S的可证明性谓词:公式P(v₁),对所有语句X,Y满足:P₁(必然化/D1):S⊢X ⟹ S⊢P(X̄)。“如果我实际证明了X,就能证明我证明了X。”P₂(分配/D2):S⊢ P(X̄⊃Y) ⊃ (P(X̄) ⊃ P(Ȳ))。“S知道关于自身证明的肯定前件规则。”P₃(可证明的D1/D3):S⊢ P(X̄) ⊃ P(P(X̄)‾)。“S证明P₁成立:它能在内部验证自身的必然化。”- 正确的可证明性谓词:
P(v₁)还表达真正的集合P(P(X̄)为真,当且仅当X确实可证明)。下文第二定理的结果不需要正确性,只需P₁,P₂,P₃三条规则。正确性只用来说明consis意指一致性。 - 可对角化的
S:每个公式F(v₁)都有不动点,即某语句X满足S⊢ X ≡ F(X̄)。(第八章定理4;P.A.因扩张(R)而满足。) - 一致性语句
consis:= ~P(f̄),f是任意可反驳的语句(S⊢~f;例如f = 0=1)。读作“f不可证明”。如果P正确:consis真⟺f不可证明⟺S一致(不一致的S证明一切,尤其证明f)。 - 哥德尔语句
G:~P(v₁)的不动点,S⊢ G ≡ ~P(Ḡ)。读作“我不可证明”。 - 亨金语句
H:P(v₁)的不动点,S⊢ H ≡ P(H̄)。读作“我可证明”。
导出的工作规则(第四部分从三条规则证明):
P₄(单调性):S⊢X⊃Y ⟹ S⊢ P(X̄)⊃P(Ȳ)。盒算子保持可证明的蕴涵。处处使用。P₅:S⊢X⊃(Y⊃Z) ⟹ S⊢ P(X̄)⊃(P(Ȳ)⊃P(Z̄))。(★)(核心引擎,即斯穆里安的P₆,也是习题1):S⊢ X⊃(P(X̄)⊃Y) ⟹ S⊢ P(X̄)⊃P(Ȳ)。这一条规则同时驱动定理2与勒布定理。
第三部分——§1三条盒算子规则:每条说什么,以及P.A.的P为什么服从它们
这里应该放慢,因为整章都是“运用盒算子规则”。把P(X̄)读成□X。
P₁——必然化。S⊢X ⟹ S⊢P(X̄)。
“如果X有一个实际证明,那么S能证明陈述P(X̄),即‘X可证明’。”这是容易的一半。在P.A.中,P(v₁)是一个Σ₁公式,表示可证明性集合P(的某个超集);表示超集已经足以给出S⊢X ⟹ S⊢P(X̄)。对P₁而言,简单一致性就足够,不需要使P恰好表示P的完整ω一致性。(斯穆里安指出:在简单一致性下,P(v₁)可能表示P的某个超集,“但这已经足以蕴涵”P₁。)
P₂——分配(内部肯定前件)。S⊢ P(X̄⊃Y) ⊃ (P(X̄)⊃P(Ȳ))。
“S证明:如果X⊃Y可证明,且X可证明,那么Y可证明。”它的真显而易见,只是说肯定前件是S的一条有效规则,现在应用于证明。P₂的内容是,这个显然的真本身在S中可证明:在算术内部形式化“把X⊃Y的证明、X的证明,再加一步MP拼接起来”。斯穆里安说:“形式化并不很困难。”
P₃——可证明的必然化(深刻的那条)。S⊢ P(X̄) ⊃ P(P(X̄)‾)。
“S证明:如果X可证明,那么‘X可证明’也可证明。”注意,这就是在P₁外面加上一个证明号:P₁从外部说“⊢X ⟹ ⊢P(X̄)”;P₃则说S在内部证明这个蕴涵。这是真正困难的条件,是以下事实的特例:
对每个Σ₁语句
Y,都有S⊢ Y ⊃ P(Ȳ),即“S证明每个真的Σ₁事实都可证明”(可证明的Σ₁完备性)。
由于P(X̄)本身是Σ₁,取Y := P(X̄)便得到P₃。斯穆里安没有证明它:“相当繁复,超出本书范围”,而是指向Boolos [1979]第二章、Hilbert–Bernays [1934–39]、Shoenfield [1967]。这是本章公开保留的一笔欠账。(它与你在第五章§6尚未补上的Σ₁完备性欠账相接:同一个事实的可证明版本。)
这对第二定理为什么重要。
P₃恰恰使定理1的元步骤——“如果G可证明,那么P(Ḡ)可证明”(在外部使用P₁)——能够在S内部重演。没有P₃,S就不能执行自身的必然化,内部化(定理2)会停滞。P₃是“我们看得出来”与“S证明得出来”之间的枢纽。
抽象的动作。从这里起,斯穆里安说:忘掉P来自P.A.这件事。只假定P₁,P₂,P₃。下文一切都是关于任意具有可证明性谓词的可对角化S的定理。最后只需指出P.A.的P满足三条规则,就能还原具体的哥德尔第二定理。
第四部分——导出规则(将第三部分的规则重新包装以便使用)
三个推论。P₄是主力规则;(★)是两个大定理真正依靠的核心引擎。
P₄——单调性。如果S⊢X⊃Y,那么S⊢P(X̄)⊃P(Ȳ)。
| 步骤 | 理由 |
|---|---|
S⊢X⊃Y |
假设 |
S⊢P(X̄⊃Y) |
对X⊃Y使用P₁ |
S⊢P(X̄⊃Y)⊃(P(X̄)⊃P(Ȳ)) |
P₂ |
S⊢P(X̄)⊃P(Ȳ) |
对上两行使用肯定前件 |
∎ “盒算子保持可证明的蕴涵”,即□是单调的。 |
P₅。如果S⊢X⊃(Y⊃Z),那么S⊢P(X̄)⊃(P(Ȳ)⊃P(Z̄))。
| 步骤 | 理由 |
|---|---|
S⊢X⊃(Y⊃Z) |
假设 |
S⊢P(X̄)⊃P(Ȳ⊃Z) |
P₄ |
S⊢P(Ȳ⊃Z)⊃(P(Ȳ)⊃P(Z̄)) |
P₂ |
S⊢P(X̄)⊃(P(Ȳ)⊃P(Z̄)) |
命题逻辑的链式推导 |
| ∎ |
(★)——核心引擎(斯穆里安的P₆;=习题1)。如果S⊢ X⊃(P(X̄)⊃Y),那么S⊢ P(X̄)⊃P(Ȳ)。
这是必须记住的规则:有了它,定理2与勒布定理的关键都只需一行。
| 步骤 | 理由 |
|---|---|
| S⊢ X⊃(P(X̄)⊃Y) | 假设 |
| S⊢ P(X̄) ⊃ P(⌜P(X̄)⊃Y⌝) | 对假设应用P₄ |
| S⊢ P(⌜P(X̄)⊃Y⌝) ⊃ (P(P(X̄)‾) ⊃ P(Ȳ)) | P₂(让P(X̄)充当前件) |
| S⊢ P(X̄) ⊃ (P(P(X̄)‾) ⊃ P(Ȳ)) | 串联上两行 |
| S⊢ P(X̄) ⊃ P(P(X̄)‾) | P₃(用于X) |
| S⊢ P(X̄) ⊃ P(Ȳ) | 命题逻辑:用上一行消去P(P(X̄)‾) |
∎
用普通语言读(★):如果S证明“X连同X的可证明性推出Y”,那么S证明“X的可证明性推出Y的可证明性”。三条盒算子规则都在这里发挥作用:P₄(由P₁+P₂构成)给假设加盒,P₂作分配,P₃把双盒P(P(X̄)‾)收拢下来。这就是斯穆里安为什么说P₄与P₆“发挥关键作用”。
第五部分——§2第二定理:三步证明
固定一个哥德尔语句G:S⊢ G ≡ ~P(Ḡ)(第八章)。把G读作“我不可证明”。
定理1——G不可证明(针对诚实的P,第一定理的半边)
陈述。如果S一致,G在S中不可证明。
证明。反证,假定S⊢G。
| 事实 | 理由 |
|---|---|
| S⊢P(Ḡ) | 对假定的S⊢G应用P₁ |
| S⊢G⊃~P(Ḡ) | 不动点G≡~P(Ḡ)的正向一半 |
| S⊢~P(Ḡ) | 对S⊢G与S⊢G⊃~P(Ḡ)使用肯定前件 |
现在S⊢P(Ḡ)且S⊢~P(Ḡ),所以S不一致,与假设矛盾。故S⊬G。∎
这是第五章定理1(G的不可证明性)的重生,使用诚实的P,只要求简单一致性。没有新东西:这是外部论证。本章全部新意在于,现在可以把这个论证推入S内部。这就是定理2。
一致性语句,以及关键的“我们不需要P正确”
f=任意可反驳的语句(S⊢~f),例如f = 0=1。consis := ~P(f̄)=“f不可证明”。如果P正确,consis就是一个真正的算术语句,为真当且仅当S一致(不一致系统证明f,一致系统不证明)。但结果微妙的稳健性在于:定理2与3只假定P是可证明性谓词,不假定它正确。它们是关于consis的句法行为的定理,与它是否“真正意指”一致性无关。第二定理由此成为抽象的定理。
定理2——内部化。S ⊢ consis ⊃ G。
这是全章的核心:S自己证明“如果我一致,那么G不可证明”(回想G就是“G不可证明”,故~P(Ḡ)=G;陈述为S⊢ ~P(f̄) ⊃ G)。这是定理1的元论证,经(★)转写进S。
证明。
| 步骤 | 理由 |
|---|---|
| (1) S⊢ G ⊃ ~P(Ḡ) | 不动点的正向一半 |
| (2) S⊢ G ⊃ (P(Ḡ) ⊃ f) | (1)+重言式~A ⊃ (A ⊃ f)(A = P(Ḡ)):“有了~P(Ḡ),P(Ḡ)便推出任何东西” |
| (3) S⊢ P(Ḡ) ⊃ P(f̄) | 对(2)使用(★),令X := G、Y := f |
| (4) S⊢ ~P(f̄) ⊃ ~P(Ḡ) | (3)的逆否命题 |
| (5) S⊢ ~P(Ḡ) ⊃ G | 不动点的反向一半 |
| (6) S⊢ ~P(f̄) ⊃ G,即S⊢ consis ⊃ G | 依次串联(4)、(5) |
∎
刚才发生了什么。第(3)行S⊢P(Ḡ)⊃P(f̄),恰好就是定理1元步骤的内部化:定理1论证“G可证明⟹P(Ḡ)可证明⟹(连同G⊃~P(Ḡ))S不一致,即f可证明”。第(3)行说S证明这个蕴涵本身:“如果G可证明,那么f可证明”。完成内部化的是(★),而在(★)内部,正是P₃使S能自行执行P₁步骤(“G可证明⟹P(Ḡ)可证明”)。之后第(4)–(6)行只是重新包装:“G可证明迫使不一致”⟺“一致性迫使G(不可证明)”。
定理3——哥德尔第二定理(抽象形式)。如果S可对角化且一致,那么consis在S中不可证明。
证明。S可对角化⟹存在哥德尔语句G(~P的不动点)。由定理2,S⊢ consis ⊃ G。
假定
S⊢ consis。肯定前件给出S⊢ G。但由定理1,若S一致,则S⊬G。所以S会不一致。
取逆否:如果S一致,那么S⊬ consis。∎
具体的哥德尔第二定理(主要结论)。P.A.可对角化(扩张(R);第八章定理4推论),其标准可证明性公式P(v₁)是可证明性谓词(P₁,P₂,P₃成立,其中P₃通过可证明的Σ₁完备性得到)。因此:
如果P.A.一致,那么P.A. ⊬
Con(P.A.):P.A.不能证明自身的一致性。
注意证明“知道”的东西有多少:它从不打开consis的意义,只让consis通过(★)与不动点运作。因此结果可推广到任何服从三条盒算子规则的S,整个可证明性逻辑研究纲领由此起源。
第六部分——§2讨论:为什么这不是怀疑P.A.的理由
第二定理是逻辑中最常被误读的结果。斯穆里安预先阻止这种误读。天真的读法——“P.A.连自己一致都证明不了,也许它并不一致”——恰好颠倒。关键观察是:
一个不一致的系统能够证明自身一致性,而且轻而易举,因为它证明一切,包括
consis。
因此,“S ⊢ consis”作为保证毫无价值:健康的一致系统不能证明consis(定理3),坏掉的不一致系统却能够(它证明所有语句)。自证一致性是警讯,不是放心的信号。斯穆里安的比喻:因为某人保证“我从不说谎”就相信他诚实,而说谎者也会这么说。这句话无论哪种情况下都不具有证据分量。
所以P.A.无法证明Con(P.A.),恰恰是一致系统应有的样子。我们对P.A.一致性的信心来自P.A.外部(例如标准模型ℕ,或更强的元理论),从不来自P.A.给自己签发的证书;第二定理说,这种自我证书恰恰在其内容诚实时无法取得。
第七部分——§3亨金语句与勒布定理
哥德尔语句说“我不可证明”,它真而不可证明。亨金(1952)提出镜像问题:P(v₁)本身的不动点,即满足S⊢ H ≡ P(H̄)的语句H,说的是“我可证明”。H是真还是假?可证明还是不可证明?
天真的推理停住了。如果H可证明,那么P(H̄)真,故H≡P(H̄)使H真,一致。如果H不可证明,那么P(H̄)假,故H假(~H真),内部也一致。自指是对称的,两种情形表面上都不荒谬。需要一个真正的定理才能解决。
定理4——勒布定理。如果S可对角化,且S⊢ P(Ȳ)⊃Y,那么S⊢Y。
读作:“只有在Y实际可证明时,S才能证明‘Y可证明⟹Y’。”不能通过断言自身可证明性蕴涵自身,免费获得Y,除非Y原本就可证明。
证明。假定S⊢ P(Ȳ)⊃Y。对公式P(v₁)⊃Y作对角化,得到不动点X,满足S⊢ X ≡ (P(X̄)⊃Y)。
| 步骤 | 理由 |
|---|---|
| (1) S⊢ X ⊃ (P(X̄)⊃Y) | 不动点的正向一半 |
| (2) S⊢ P(X̄) ⊃ P(Ȳ) | 对(1)应用(★),令X := X、Y := Y |
| (3) S⊢ P(Ȳ) ⊃ Y | 假设 |
| (4) S⊢ P(X̄) ⊃ Y | 串联(2)、(3) |
| (5) S⊢ (P(X̄)⊃Y) ⊃ X | 不动点的反向一半 |
| (6) S⊢ X | 肯定前件:(4)就是P(X̄)⊃Y,代入(5) |
| (7) S⊢ P(X̄) | 对(6)应用P₁ |
| (8) S⊢ Y | 肯定前件:把(7)代入(4) |
∎
与定理2使用同一引擎:第(2)行干净地用了一次(★)。额外步骤利用了现在的不动点属于P(v₁)⊃Y,因此语句X就是(P(X̄)⊃Y),使第(4)行能直接送入不动点,产生X,再由P₁闭合循环。
亨金问题解决。取Y := H。由于H≡P(H̄),特别有S⊢ P(H̄)⊃H。满足勒布定理的假设,所以S⊢H。亨金语句可证明(因而为真)。“我可证明”事实上可证明,朝着诚实的方向自我实现。
克赖塞尔推论——第二定理就是Y = f时的勒布定理(“⊥情形”)
这是你8月5日笔记预言的优雅重述。取Y := f,即可反驳的语句。
假定
S⊢ consis,即S⊢ ~P(f̄)。由重言式~P(f̄) ⊃ (P(f̄)⊃f),得到S⊢ P(f̄)⊃f。这恰是Y=f时勒布定理的假设,故由勒布,S⊢f。但f可反驳(S⊢~f),于是S不一致。
取逆否:S一致⟹S⊬ consis。定理3从勒布定理中三行导出。第二定理正是把勒布定理应用于一个假语句(类似⊥):“不能证明‘⊥可证明蕴涵⊥’”,就是“不能证明自身一致性”。
直觉——为什么勒布定理不会证明一切(化解柯里式担忧)
担忧。勒布说“S⊢P(Ȳ)⊃Y ⟹ S⊢Y”。所以只要能证明看似温和的承诺“如果Y可证明,那么Y”,就能免费获得Y,而且是任意Y:圣诞老人存在、0=1,什么都行。这样系统岂不是证明一切?为什么没有?
化解:路线A/路线B。要证明任意条件句“如果A,那么B”,只有两道诚实的门:
- 路线A:交付后件。证明B。对这个承诺,就是证明Y(推导语句本身,是一个证明行为,不是“Y为真”;真而不可证明的Y不能打开这道门)。
- 路线B:否掉前件。证明¬A。对这个承诺,就是证明“Y不可证明”。
路线B已被砖封死,而这块砖就是第二定理。证明“Y永远不可证明”,就是保证在无穷多个可能证明中,没有任何一个产生Y。这个保证其实是一张伪装的一致性证书,原因是爆炸原理:
爆炸原理(ex falso quodlibet)。不一致系统证明每个语句。证明:若
S⊢X且S⊢~X,那么对任意Q:从X推出X∨Q(一个更弱的主张,对任何Q都安全);但~X排除了X分支,所以X∨Q只能以Q成立;故S⊢Q。∎
所以不一致系统不留下任何不可证明的东西。反过来读:哪怕有一个语句Y不可证明,系统就一致,即部分⟹整体,因为不一致不放过任何东西。(想象一台被附身的打印机:一旦卡纸,就打印每一页;“它永不打印圣诞老人那页”已经证明“它从没卡过纸”。)而且S自己证明这个蕴涵:从逻辑真理⊢ ⊥⊃Y与单调性P₄,得到S ⊢ P(⊥)⊃P(Ȳ),即S ⊢ ~P(Ȳ) ⊃ Con(S)。因此证明路线B就会证明Con(S),被第二定理禁止。对每个Y,路线B都关闭。
只剩路线A:实际证明Y。所以证明承诺=证明Y,始终是可证明性,没有偷带真。承诺从不是捷径,只是披着伪装的Y。对系统不能证明的Y(圣诞老人、0=1),承诺本身就不可证明,勒布定理无从启动。勒布只作用于原本就是定理的Y,没有免费午餐,也没有爆炸。
目标Y |
路线A(证明Y) |
路线B(证明Y不可证明) |
承诺可证明? |
|---|---|---|---|
定理(0=0) |
开放 | — | 是(但多余) |
| 真而不可证明 | 关闭 | 关闭(=一致性主张) | 否 |
假/0=1 |
关闭 | 关闭(就是Con(S)) |
否,这就是第二定理 |
以及背后的三重等价。对任意Y:S⊢Y ⟺ S⊢P(Ȳ)⊃Y ⟺ S⊢Y≡P(Ȳ)。(⟹:由P₁,两侧均可证明⟹双条件可证明。中⟹右⟹左:勒布。)所以,可证明、反思可证明与亨金形式是同一个集合的三个名称,即定理集合。没有某种稀有的“自指形状”可以解锁可证明性;三者选出的恰好都是定理。
克里普克的观察,以及接下来的方向
索尔·克里普克指出反方向:勒布定理本身也可作为第二定理的推论得到(应用于适当扩张的S)。所以在这里,勒布与哥德尔第二定理可以相互推导。斯穆里安最后指向现代后继:盒算子规则P₁,P₂,P₃恰好是模态可证明性逻辑GL(哥德尔–勒布)的公理,其中勒布定理成为单一模态公理□(□Y⊃Y)⊃□Y。他推荐后续阅读布洛斯《一致性的不可证明性》(The Unprovability of Consistency),整个主题会在那里以模态逻辑重新出现。
习题1(唯一的习题):证明若S⊢ X⊃(P(X̄)⊃Y),则S⊢ P(X̄)⊃P(Ȳ)。这就是(★)本身;证明见第四部分的表格。亲手做一遍,才能真正掌握两个大定理共同依靠的引擎。
第八部分——收束:把全书看作一条完整弧线
你即将读完,值得把三周的攀登看成一条线。每个阶段都是把握自指的不同方式:
| 章节 | 动作 | 自指 | 结果 |
|---|---|---|---|
| II–IV | 真与可定义性;算术化 | — | 塔斯基:真不可定义;使“可证明”成为公式的编码 |
| V | 手工构造对角句G=∀y~A(h̄,y),从外部推理 |
通过E_n(n̄)位于P*中 |
第一定理(哥德尔形式):ω一致⟹不完备 |
| VI | ≤竞赛ρ,分离而非表示 |
位于P*中 |
罗瑟:简单一致性⟹不完备 |
| VII | 反转罗瑟的机制 | 位于P*中 |
谢泼德森表示:简单一致性下Σ₁集合可表示 |
| VIII | 把自指打包成一条引理,针对诚实的P,≡在S中可证明 |
不动点引理(定理4) | 哥德尔、罗瑟、塔斯基成为推论;可证明性可表示,真则不可 |
| IX | 给P三条盒算子规则,运行内部化的论证 |
~P(以及P)的不动点 |
第二定理S⊬Con(S);勒布定理 |
贯穿一切的一句话:
第五至第七章构造自指语句,从外部对它推理→第一定理。 第八章使自指成为针对真正可证明性谓词的可证明不动点。 第九章赋予该谓词三条盒算子规则,在
S内部重演第一定理→第二定理,勒布定理则是它的反照。
最深的贯穿线索——你8月5日笔记中的三个层次——使这个结尾成为可能:真不可表达,可证明性却可表示。正是这种不对称,使S能形成语句consis并对自己的证明推理(第二定理),却永远不能对自己的真推理(塔斯基)。第二定理是系统针对中间层次能说出的最锋利的话:S无法证明关于自身可证明性最想证明的那个事实,即它从不证明假话。
区分清单
| 困惑 | 一行解决 |
|---|---|
P₁与P₃? |
P₁=从外部必然化(⊢X ⟹ ⊢P(X̄))。P₃=S在内部证明该蕴涵(⊢ P(X̄)⊃P(P(X̄)‾))。P₃=“可证明的P₁”。 |
为什么P₃困难? |
它是可证明的Σ₁完备性(对Σ₁的Y,⊢ Y⊃P(Ȳ))在Y=P(X̄)处的实例。斯穆里安不证明,交给布洛斯/希尔伯特–伯奈斯。这是本章唯一未结欠账。 |
(★)能做什么,而单靠P₄不能? |
P₄给普通蕴涵加盒。(★)处理前件已含盒子的蕴涵(X⊃(P(X̄)⊃Y)),通过P₃收拢所得的双盒。它是“自指的肯定前件”。 |
| 定理1与定理2? | 定理1=外部的第一定理论证(G不可证明),只用P₁。定理2=同一论证的内部化,S⊢consis⊃G,使用(★)(因而用到P₂,P₃,P₄)。 |
为什么第二定理不需要P正确? |
定理2、3纯属句法,让consis经过(★)与不动点运作。只有把consis解释为“S一致”时才需要正确性。 |
不能证明Con是怀疑P.A.的理由吗? |
不,恰好相反。不一致系统能证明自身一致性(它们证明一切),一致系统不能。自证一致性是警讯。 |
| 哥德尔语句与亨金语句? | G≡~P(Ḡ)(“我不可证明”)真且不可证明。H≡P(H̄)(“我可证明”)由勒布定理可证明且真。 |
| 第二定理与勒布定理? | 第二定理=Y=f(可反驳)时的勒布定理:“不能证明P(f̄)⊃f”=“不能证明~P(f̄)”=“不能证明一致性”。克里普克:两者在这里可相互推导。 |
P₁,P₂,P₃“究竟”是什么? |
模态可证明性逻辑GL的公理;P(·)=□。勒布定理=模态公理□(□Y⊃Y)⊃□Y。 |
自测
Q1. 陈述可证明性谓词的三个定义条件P₁,P₂,P₃,说明哪一个深刻,为什么。
答案
P₁:⊢X ⟹ ⊢P(X̄)(必然化)。P₂:⊢ P(X̄⊃Y)⊃(P(X̄)⊃P(Ȳ))(分配/内部MP)。P₃:⊢ P(X̄)⊃P(P(X̄)‾)(可证明的必然化)。P₃深刻:它是可证明的Σ₁完备性(对Σ₁的Y,⊢ Y⊃P(Ȳ))在Y=P(X̄)处的特例;斯穆里安没有证明它。P₁,P₂容易/可以形式化。
Q2. 证明(★):若S⊢ X⊃(P(X̄)⊃Y),则S⊢ P(X̄)⊃P(Ȳ)。
答案
对假设用P₄:⊢ P(X̄)⊃P(⌜P(X̄)⊃Y⌝)。由P₂:⊢ P(⌜P(X̄)⊃Y⌝)⊃(P(P(X̄)‾)⊃P(Ȳ))。串联:⊢ P(X̄)⊃(P(P(X̄)‾)⊃P(Ȳ))。由P₃:⊢ P(X̄)⊃P(P(X̄)‾)。命题逻辑收拢双盒:⊢ P(X̄)⊃P(Ȳ)。
Q3. 从不动点与(★)证明定理2(S⊢ consis⊃G)。
答案
不动点:⊢ G⊃~P(Ḡ),故⊢ G⊃(P(Ḡ)⊃f)(重言式~A⊃(A⊃f))。令X=G,Y=f,应用(★):⊢ P(Ḡ)⊃P(f̄)。取逆否:⊢ ~P(f̄)⊃~P(Ḡ)。再结合不动点另一半⊢ ~P(Ḡ)⊃G,串联得到⊢ ~P(f̄)⊃G,即⊢ consis⊃G。
Q4. 从定理1与2证明定理3。
答案
可对角化⟹存在~P的不动点G。定理2:⊢ consis⊃G。如果⊢ consis,那么(MP)⊢G;但定理1说一致的S满足⊬G,所以S会不一致。故S一致⟹⊬ consis。
Q5. 陈述勒布定理,并用它解决亨金语句。
答案
勒布:如果S可对角化且⊢ P(Ȳ)⊃Y,那么⊢Y。亨金语句H≡P(H̄)给出⊢ P(H̄)⊃H;由勒布,⊢H。所以亨金语句(“我可证明”)可证明且真。
Q6. 把第二定理作为勒布定理的推论导出(克赖塞尔)。
答案
取可反驳的Y=f。如果⊢ consis = ~P(f̄),那么由~P(f̄)⊃(P(f̄)⊃f)得到⊢ P(f̄)⊃f,即Y=f时勒布定理的假设。所以⊢f,与⊢~f矛盾。故一致⟹⊬consis。
Q7. 为什么P.A.不能证明自身一致性,不是P.A.可能不一致的证据?
答案
不一致系统证明一切,包括consis。所以能证明自身一致性,恰恰是坏掉的系统的表现;不能取得这种证明,才是健康的系统的表现(定理3)。自己签发的一致性证书没有任何证据分量,就像说谎者说“我从不说谎”。对P.A.的信心来自外部(标准模型),而不是自我证明。
参考与交叉链接
| 引入的结果 | 用于 | 来源 |
|---|---|---|
| 不动点(对角化)引理;P.A.可对角化 | §1(可对角化的定义),以及每次取不动点之处 | 8月5日定理4+推论 |
P可表示(Σ₁),真不可表达:使P(v₁)得以存在的区分 |
§1(P(v₁)何以存在) |
8月5日§5,三个层次的教训 |
D1/D2/D3预告;勒布+“X=⊥情形”的预言 |
第零部分对照 | 8月5日第九部分前瞻 |
第一定理(G不可证明),简单一致性 |
定理1(“外部”的一半) | 7月30日定理3、8月3日罗瑟 |
可证明的Σ₁完备性(对Σ₁的Y,⊢ Y⊃P(Ȳ)) |
P₃(假定,而非证明) |
Boolos [1979]第二章;Hilbert–Bernays [1934–39];Shoenfield [1967]:本章未结的欠账 |
| 塔斯基(真不可定义) | 第八部分收束 | 第二章;8月5日§5 |
本次阅读范围:斯穆里安《哥德尔不完备性定理》,第九章,第106–110页:§1(P₁–P₃;导出的P₄,P₅,P₆),§2(定理1、一致性语句、定理2、定理3、讨论),§3(亨金问题、定理4=勒布、克赖塞尔推论、克里普克观察、习题1)。
接下来——你已抵达顶峰
- 第九章是全书最后一个主要结果。第一定理(第五至第七章)、其简洁的打包(第八章)、第二定理+勒布(第九章),是三个峰顶,现在都已攀登。
- 若要基础严密,诚实地说还有一笔欠账:
P₃(可证明的Σ₁完备性)。这里只陈述而未证明;它也是你尚未完成的第五章§6习题10–12/习题11Σ₁完备性欠账背后的同一事实。自然的下一本书是布洛斯《一致性的不可证明性》(斯穆里安本人的推荐),或布洛斯与杰弗里《可计算性与逻辑》(Computability and Logic)第16章(脚注所引);那里会证明P₃,并发展模态逻辑GL,以□(□Y⊃Y)⊃□Y为勒布定理的公理形式。 - 值得做的巩固练习:习题1(=亲手重新导出核心引擎
(★));并列重写定理2与勒布定理,确认两者共有的恰好是(★)步骤;最后,以纲要形式验证克里普克的反方向(从哥德尔第二定理导出勒布),完成收尾。
前序学习文件:7月26日 · 7月27日 · 7月28日 · 7月29日 · 7月30日 · 7月31日 · 8月3日 · 8月4日 · 8月5日 · 8月6日(本文)。