Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness Theorems — Session 2026‑08‑05
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 VIII: Definability and Diagonalization (pp. 97–105) — the self‑reference engine packaged as one lemma, and the bridge to the Second Theorem
- Orientation — what this chapter is for
- Part 0 — the one‑sentence shift, and what carries over
- Part I — the dependency map (the whole chapter on one page)
- Part II — Citable glossary
- Part III — §1 Definability and complete representability (the vocabulary)
- Part IV — §2 Strong definability of functions: the composition engine
- Part V — §3 Strong definability of recursive functions in (R)
- Part VI — §4 THE FIXED‑POINT LEMMA (the centerpiece)
- Part VII — §5 Truth predicates (Tarski, twice)
- Part VIII — Connection backward: how Chapter VIII re‑packages Ch. V–VII
- Part IX — Connection forward: the bridge to Gödel's Second Incompleteness Theorem
- Distinctions Ledger
- Self‑Test
- References & cross‑links
- What's ahead
Chapter VIII: Definability and Diagonalization (pp. 97–105) — the self‑reference engine packaged as one lemma, and the bridge to the Second Theorem
Orientation — what this chapter is for
Read this first; everything below is its unfolding.
Chapters V–VII each built a self‑referential sentence by hand. Gödel's G = ∀y~A(h̄,y), Rosser's ρ = ∀y[A(h̄,y)⊃(∃z≤y)B(h̄,z)], Shepherdson's φ — every one was hand‑diagonalized through the substitution function, its self‑reference engineered ad hoc for the single job at hand. The whole apparatus (E_n(n̄), the wrapper E[m̄,n̄], the coding function Π, the diagonal set P*) existed to fold self‑reference into one specific set so that no general fixed‑point machinery was needed.
Chapter VIII stops doing this by hand. It proves, once and for all, the Fixed‑Point (Diagonalization) Lemma —
Theorem 4. If the diagonal function
d(x)is strongly definable inS, then every formulaF(v₁)has a fixed point: a sentenceXwithS ⊢ X ≡ F(X̄).
— and then harvests Gödel (Ex 5), Rosser (Ex 6–7), and Tarski (§5) as immediate corollaries. Self‑reference is no longer a construction; it is a service: name any property F(v₁) in the language and you get a sentence that provably asserts "I have property F."
Two quieter retoolings ride along, and they are the ones that matter for what comes next:
- From
P*toP. The bespoke diagonal setP* = {n : E_n(n̄) provable}is retired. Now that a general fixed‑point lemma exists, the chapter works with the honest provability setP= {Gödel numbers of provable sentences} and its representing formula. Exercises 5–7 redo Gödel and Rosser withP, notP*, plus a fixed point. This is the provability predicate the Second Theorem will formalize. - From "provable ⟺ true" (metatheory) to "
≡is provable inS" (object theory). Every headline of this chapter is a provable‑in‑Sequivalence — Theorem 2'sH(n̄) ≡ G(f(n)‾), the fixed point'sX ≡ F(X̄), the truth‑predicate'sX ≡ T(X̄). Chapters V–VII mostly reasoned aboutSfrom outside; Chapter VIII manufactures equivalencesSproves of itself. That "provable‑in‑S" is the entire currency of the Second Theorem.
The chapter's spine is a short dependency chain that ends in the fixed‑point lemma:
strong definability of functions (Thm 2, the provable composition lemma) →
d(x)strongly definable in extensions of (R) (Prop 4) → every formula has a fixed point (Thm 4) → Gödel, Rosser, Tarski fall out.
Reading order follows that spine.
Part 0 — the one‑sentence shift, and what carries over
| Chapters V–VII | Chapter VIII | |
|---|---|---|
| self‑reference | hand‑built per sentence, via E_n(n̄) / Π |
one lemma: every F(v₁) has a fixed point (Thm 4) |
| the set in play | P* (diagonal set — self‑reference pre‑folded in) |
P (honest provability set) + a fixed point supplied separately |
| currency | mostly metatheoretic biconditionals ("n∈A ⟺ F(n̄) provable") |
object‑theoretic — the equivalence itself provable in S |
| new tool | — | strong definability of functions (Thm 2) |
What carries over unchanged: the ≤‑machinery Ω₄, Ω₅ (Ch. VI/VII) reappears — this time to prove a function's value is provably unique (the least‑witness minimization inside §3's Lemma); Ch. VII's Rosser‑system results (representability of Σ₁ sets, exact separation of disjoint Σ₁ pairs) are consumed wholesale by §1 (Prop 2, Thm 1); Σ₀‑completeness and (R)=Ω₁–Ω₅ from Ch. V underlie every "provable in (R)."
Part I — the dependency map (the whole chapter on one page)
§2 STRONG DEFINABILITY OF FUNCTIONS
Theorem 2 ── provable composition:
f strongly definable ⟹ for any G(v₁) there is H(v₁) with
S ⊢ H(n̄) ≡ G(f(n)‾)
│ │
│ (Corollary) │ (take f := d, G := F)
▼ ▼
f⁻¹ preserves §4 Theorem 4 ── THE FIXED-POINT LEMMA
rep / exact-sep / def every F(v₁) has X with S ⊢ X ≡ F(X̄)
│
§3 supplies the hypothesis: ├─▶ Cor 1: holds in every extension of (R)
Lemma (weak→strong, │
least witness, Ω₄,Ω₅) ├─▶ Ex 5 → GÖDEL (fixed pt of ∀y~F, F enum P)
Theorem 3: all recursive ├─▶ Ex 6,7 → ROSSER (fixed pt of the ≤-race on P,R)
functions strongly ├─▶ Ex 8 → TARSKI (P not definable)
definable in (R) │
Prop 3 + Prop 4: └─▶ §5 Theorems 6,7 → NO TRUTH PREDICATE
d(x) strongly definable
in every extension of (R) §1 the vocabulary this all runs on:
define / completely represent;
Prop 1,2; Theorem 1
Everything upstream exists to discharge Theorem 4's single hypothesis — d(x) is strongly definable — and everything downstream is Theorem 4 fired at a chosen F.
Part II — Citable glossary
Carried: E_x = expression with Gödel number x; P = Gödel numbers of provable sentences, R = Gödel numbers of refutable sentences; P*, R* = the diagonal sets of Ch. V–VII. Numeral conventions: n̄ = numeral for n; for an expression X, X̄ = numeral for ⌜X⌝ (its Gödel number); f(n)‾ = numeral for the value f(n).
FdefinesR(a relation) inS:R(ā) ⟹ S⊢F(ā)and~R(ā) ⟹ S⊢~F(ā). =FseparatesRfrom its complementR̄(provable onR, refutable off it). One‑directional.Fcompletely representsR:FrepresentsRand~Frepresents~R— i.e. define's two clauses with⟹upgraded to⟺. = exactly separatesRfromR̄(theA∪B = everythingcase of Ch. VII exact separation — no "undecidable" band).- recursive set/relation:
RandR̄are bothΣ₁. (The self‑dual core ofΣ₁; equivalently "decidable.") Fweakly defines a functionf:F(v₁,v₂)defines the graph relationf(x)=y. (Clauses (1)(2) below.)Fstrongly defines (= defines)f: weakly defines plus a provable uniqueness clause. Forf(a)=b:- (1)
f(a)=b ⟹ S⊢F(ā,b̄); - (2)
f(a)≠b ⟹ S⊢~F(ā,b̄); - (3)
f(a)=b ⟹ S⊢ ∀v₂(F(ā,v₂) ⊃ v₂=b̄)— "Sitself proves the value is unique." - recursive function: the graph
f(x)=yis a recursive relation. - fixed point of
F(v₁): a sentenceXwithS⊢ X ≡ F(X̄). - Gödel sentence for
Aw.r.t.S: a sentenceXthat is provable inSiff⌜X⌝∈A. (One‑directional — no provable biconditional demanded.) facceptable inS: for every setArepresentable inS,f⁻¹(A)is representable inS.- truth‑predicate for
S: a formulaT(v₁)withS⊢ X ≡ T(X̄)for every sentenceX. (A fixed‑point lemma uniform over allX, with the equivalence provable — the thing §5 shows cannot exist.)
The three tiers to keep straight (this ordering is the moral of the chapter):
| tier | object | status in S |
why |
|---|---|---|---|
| truth | the true sentences | not expressible | Tarski (§5, Ch. II) |
| provability | P |
representable, not definable | P is Σ₁ but ~P is not (P not recursive — Church) |
| recursive sets | R with R̄ also Σ₁ |
definable / completely representable | Ch. VII exact separation of the disjoint Σ₁ pair R, R̄ |
The First Theorem lives in the middle tier; the Second Theorem is about S's inability to prove one particular fact about that middle tier (its own consistency).
Part III — §1 Definability and complete representability (the vocabulary)
Proposition 1. If F defines R in S and S is consistent, then F completely represents R.
Proof. Need the converses of define's two clauses. If S⊢F(ā): by consistency F(ā) is not refutable, so by clause (2) ~R(ā) fails, i.e. R(ā). If S⊢~F(ā): not provable, so by (1) R(ā) fails, i.e. ~R(ā). ∎ — consistency is the single hinge: it turns "refutable ⟹ not provable" into the missing backward arrows. (Same one‑dose‑of‑consistency move as Ch. VI Lemma 1.)
Proposition 2. (i) If S is a Rosser system, all recursive relations are definable in S. (ii) If also consistent, all recursive relations are completely representable.
Why. F defines R iff F separates R from R̄ (def). A recursive R has R, R̄ both Σ₁ and disjoint — exactly a disjoint Σ₁ pair — so a Rosser system separates them (Ch. VII). (ii) is (i) + Prop 1.
Theorem 1. All recursive relations are definable in (R) — because (R) is a Rosser system (Ch. VII). And definability transfers to every extension, so recursive relations are definable in (Q), P.A., and any consistent extension of (R).
Exercises. Ex 1: F defines R(x₁,x₂) ⟹ F enumerates dom R. Ex 2 (T/F): "all true Σ₀ provable ⟹ all Σ₀ relations definable" — true (Σ₀ relations are recursive, and Σ₀‑completeness separates them directly). Ex 3: in the complete theory N, representability = definability = complete representability all coincide; not so in P.A. — hint: P* is representable but not completely representable (that would make it recursive/decidable, contradicting undecidability). Ex 3 is the sharpest statement of the middle‑tier gap.
Part IV — §2 Strong definability of functions: the composition engine
Theorem 2 — provable composition (the workhorse)
Statement. If f(x) is strongly definable in S, then for any formula G(v₁) there is a formula H(v₁) such that for every n, S⊢ H(n̄) ≡ G(f(n)‾).
Construction. With F(v₁,v₂) strongly defining f, set
H(v₁) := ∃v₂( F(v₁,v₂) ∧ G(v₂) ).
Proof (fix n, let m=f(n); show S⊢ H(n̄) ≡ G(m̄)):
| direction | argument | clause used |
|---|---|---|
G(m̄) ⊃ H(n̄) |
S⊢F(n̄,m̄) (clause 1), so G(m̄) ⊃ (F(n̄,m̄)∧G(m̄)) ⊃ ∃v₂(F(n̄,v₂)∧G(v₂)) = H(n̄). |
(1) |
H(n̄) ⊃ G(m̄) |
S⊢ F(n̄,v₂) ⊃ v₂=m̄ (clause 3), so (F(n̄,v₂)∧G(v₂)) ⊃ (v₂=m̄ ∧ G(v₂)) ⊃ G(m̄); generalize/∃‑eliminate ⟹ H(n̄) ⊃ G(m̄). |
(3) |
Conjoin: S⊢ H(n̄) ≡ G(m̄). ∎
Why "strongly" — clause (3) is the whole point. Weak definability gives only the graph‑matching clauses (1)(2); it cannot deliver H(n̄) ⊃ G(m̄), because inside S some other v₂ might satisfy F(n̄,v₂) and drag along a false G(v₂). Clause (3) — S proves the value unique — is exactly what collapses the ∃v₂ back onto m̄. Weak = right extension; strong = provable substitution. Every "provable‑in‑S" downstream (fixed points, and ultimately the Second Theorem's internalized reasoning) rests on this upgrade.
Corollary — f⁻¹ preserves representability, exact separation, definability
If f is strongly definable, then (via H(n̄) provable ⟺ G(f(n)‾) provable, and likewise refutable):
1. A representable ⟹ f⁻¹(A) representable;
2. (A,B) exactly separable ⟹ (f⁻¹(A), f⁻¹(B)) exactly separable;
3. A definable ⟹ f⁻¹(A) definable.
(Ex 4: if f is only weakly definable but S is ω‑consistent, then A definable ⟹ f⁻¹(A) representable — ω‑consistency buys back what the missing clause (3) lost. The old ω‑consistency crutch, re‑appearing exactly where strong definability is absent.)
Part V — §3 Strong definability of recursive functions in (R)
Lemma — weak ⟹ strong, by the least‑witness ≤‑minimization
Statement. If S proves Ω₄, Ω₅, then any function weakly definable in S is strongly definable.
Construction. Given F weakly defining f, set
G(x,y) := F(x,y) ∧ ∀z( F(x,z) ⊃ y≤z )— "ysatisfiesF, and is the least such."
Proof (f(n)=m; verify the three strong clauses):
- (1)
S⊢G(n̄,m̄). Fork≤m:S⊢ F(n̄,k̄) ⊃ m̄≤k̄(ifk<m,F(n̄,k̄)refutable; ifk=m,m̄≤k̄byΩ₅).Ω₄bundlesz≤m̄ ⊃ (F(n̄,z)⊃m̄≤z); the casem̄≤zis trivial;Ω₅merges them ⟹∀z(F(n̄,z)⊃m̄≤z). WithS⊢F(n̄,m̄)(weak clause 1) ⟹G(n̄,m̄). - (2)
k≠m ⟹ S⊢~G(n̄,k̄).F(n̄,k̄)refutable (weak clause 2) andG⊃F, soG(n̄,k̄)refutable. - (3)
S⊢ ∀y(G(n̄,y) ⊃ y=m̄). FirstG(n̄,y) ⊃ y≤m̄(instantiate the∀zatm̄, useS⊢F(n̄,m̄)). Then fork≤m,S⊢ G(n̄,k̄) ⊃ k̄=m̄(ifk<m,G(n̄,k̄)refutable; ifk=m, trivial);Ω₄bundlesy≤m̄ ⊃ (G(n̄,y)⊃y=m̄); combine withG(n̄,y)⊃y≤m̄. ∎
This is the Ch. VI/VII ≤‑race in a new job. There it broke proof‑vs‑refutation ties to separate; here it selects the least F‑witness to make the value provably unique. Same Ω₄ (unpack bounded ∀ into a finite disjunction) + Ω₅ (linearity) — now serving functionhood.
Theorem 3. All recursive functions are strongly definable in (R) (= Theorem 1's weak definability + the Lemma).
Proposition 3. If the graph f(x)=y is Σ₁, then f is recursive — because f(x)≠y ≡ ∃w(f(x)=w ∧ w≠y) is also Σ₁, so the complement of the graph is Σ₁ too.
Proposition 4 (the payoff). The diagonal function d(x) — d(⌜H(v₁)⌝) = ⌜H(H̄)⌝ — is Σ₁, hence recursive (Prop 3), hence strongly definable in every extension of (R) (Thm 3 + transfer to extensions). This is precisely Theorem 4's hypothesis, now discharged for all the systems we care about.
Part VI — §4 THE FIXED‑POINT LEMMA (the centerpiece)
Theorem 4 — every formula has a fixed point
Statement. If d(x) is strongly definable in S, then every F(v₁) has a fixed point X: S⊢ X ≡ F(X̄).
Proof (three lines, and every earlier gadget is now inside them):
1. Apply Theorem 2 with f := d, G := F: get H(v₁) with S⊢ H(n̄) ≡ F(d(n)‾) for all n.
2. Let h = ⌜H(v₁)⌝ and instantiate at n=h: S⊢ H(h̄) ≡ F(d(h)‾).
3. But d(h) = ⌜H(h̄)⌝. So with X := H(h̄) we have d(h)‾ = X̄, giving S⊢ X ≡ F(X̄). ∎
The self‑reference that Ch. V–VII carried in Π's slots and the double‑duty index h is now compressed into one equation: d(h) = ⌜H(h̄)⌝ — the diagonal function is the act of a formula naming its own diagonalization.
Corollary 1. Every formula has a fixed point in every extension of (R) (Prop 4).
Gödel sentences vs fixed points — Theorem 5 and the strength ladder
- A Gödel sentence for
A:Xprovable ⟺⌜X⌝∈A. A one‑directional coincidence. - A fixed point of
F:S⊢ X ≡ F(X̄). The biconditional is proved insideS.
Theorem 5. If d(x) is acceptable in S, then every representable A has a Gödel sentence. (Proof: exercise.)
Discussion — incomparable to Theorem 4, both ends weaker.
- Hypothesis: strongly definable ⟹ acceptable (Cor stmt 1), but not conversely — so Thm 5's hypothesis is weaker.
- Conclusion: a fixed point of F is automatically a Gödel sentence for the set F represents (a provable X ≡ F(X̄) forces "X provable ⟺ F(X̄) provable"), but generally more (the equivalence is provable, not merely true). So Thm 4's conclusion is stronger. Weaker hypothesis + weaker conclusion = incomparable (neither theorem implies the other) — the same sideways relation as Ch. VI's Theorem R vs. Theorem A (weaken one axis, pay on another) and as Theorems 6/7 below. (Not the A*‑vs‑A relation of Ch. V — that was a strict strengthening, hence comparable.)
Part VII — §5 Truth predicates (Tarski, twice)
Theorem 6. If S is correct (a subsystem of N), there is no truth‑predicate for S.
Proof. A truth‑predicate gives S⊢ X ≡ T(X̄) for all X; correctness makes each such equivalence true, so X true ⟺ T(X̄) true — i.e. T(v₁) expresses the set of true sentences, contradicting Tarski's theorem for L_A (Ch. II). ∎ (Semantic route: uses truth, no diagonalization.)
Theorem 7. If S is simply consistent and d(x) is strongly definable, there is no truth‑predicate.
Proof. Take X a fixed point of ~T(v₁) (Thm 4): S⊢ X ≡ ~T(X̄). If T were a truth‑predicate, also S⊢ X ≡ T(X̄). Chain: S⊢ T(X̄) ≡ ~T(X̄) — S inconsistent. ∎ (Syntactic route: uses diagonalization + consistency, no semantics.)
The two are incomparable in exactly the Gödel‑vs‑Rosser way: Thm 6 spends correctness (strong, semantic) and skips diagonalization; Thm 7 spends consistency (weak, syntactic) and pays with a fixed point. This is the whole book's dialectic — semantic vs. syntactic hypotheses — in one facing pair.
The asymmetry that powers the next chapter. Put §5 beside Ch. VII: truth is not even expressible, but provability P is representable. That gap is not a curiosity — it is the precondition for formalizing metamathematics. "X is provable" can be coded as a formula P(X̄) (Ch. VII); "X is true" cannot. So S can talk about its own proofs but never about its own truth — and the Second Theorem is precisely a statement about what S can prove about its own provability.
Part VIII — Connection backward: how Chapter VIII re‑packages Ch. V–VII
Everything the earlier chapters did by hand is now a named lemma fired at a chosen F. The exercises make this explicit — each is a one‑line diagonalization where before there was a chapter.
| earlier result | built there by… | now (Ch. VIII) |
|---|---|---|
Gödel G = "I am unprovable" |
hand‑diagonalizing ∀y~A(h̄,y) over P* |
Ex 5: fixed point of ∀y~F(x,y), F enumerating P. Consistent ⟹ X unprovable; ω‑consistent ⟹ X unrefutable ⟹ (P.A.) incomplete. |
Rosser ρ (simple consistency) |
hand‑diagonalizing the ≤‑race over P*, R* |
Ex 6: fixed point of ∀y(F(x,y) ⊃ (∃z≤y)G(x,z)), F,G enumerating P, R; undecidable on simple consistency. (The book prints G(x,y), leaving z vacuous; the ≤‑race needs the bound z — read G(x,z).) Ex 7: any fixed point of a formula representing a superset of R disjoint from P is undecidable — Ch. VI Theorem 1 restated for genuine P, R (no Ω₄,Ω₅ needed). |
| Tarski undefinability | Ch. II, semantic | Ex 8 / Thm 7: d strongly definable + consistent ⟹ P not definable / no truth‑predicate — Tarski via the fixed‑point lemma. |
Three structural upgrades underlie the table:
1. Self‑reference is now hypothesis‑free at point of use. You no longer construct a self‑referential sentence; you cite Theorem 4. The construction lives once, in d's strong definability (Prop 4).
2. P* → P. The diagonal set was a device to avoid needing a fixed‑point lemma. With the lemma in hand, the exercises drop P* and use the real provability set P — the object of genuine interest, and the one the Second Theorem is about.
3. Metatheory → object theory. Ch. V–VII delivered biconditionals we verified from outside. Ch. VIII delivers biconditionals S proves. That is not a stylistic change; it is the precondition for internalizing an argument, which is what the Second Theorem does.
Part IX — Connection forward: the bridge to Gödel's Second Incompleteness Theorem
This is why the chapter exists. The Second Theorem says: if S is consistent (and strong enough), then S ⊬ Con(S) — S cannot prove its own consistency. Its standard proof is the First Theorem's argument, formalized inside S, and that formalization consumes exactly what Chapter VIII builds: a provable fixed point, the honest predicate P, the truth/provability split, and the provable‑composition discipline behind them (the four rows below).
The methodological leap. The First Theorem (Ch. V–VII) is a metatheorem: "if S is consistent, then G is unprovable" — a sentence we assert about S. The Second Theorem internalizes it:
S ⊢ ( Con(S) ⊃ G )—Sitself proves "if I am consistent,Gis unprovable." This is assembled from two provable‑in‑Sfacts: the fixed pointS ⊢ G ≡ ~P(Ḡ)(Chapter VIII) and the formalized First TheoremS ⊢ Con(S) ⊃ ~P(Ḡ)(the next chapter's labor). Combining them givesS ⊢ Con(S) ⊃ G; soS ⊢ Con(S)would forceS ⊢ G, contradictingG's unprovability (which holds wheneverSis consistent). HenceS ⊬ Con(S). Everything turns on being able to run the First Theorem's reasoning with the turnstile on the outside. Chapter VIII is what makes that legal.
What the Second Theorem borrows from Chapter VIII, item by item:
| the Second Theorem needs… | Chapter VIII supplies it as… |
|---|---|
the sentence G with S ⊢ G ≡ ~P(Ḡ) — "I am not provable," equivalence provable in S** |
Theorem 4 (fixed point of ~P(v₁)). Not merely a true self‑reference (Ch. V) but a provable one — the strong‑definability upgrade (clause 3 / §3 Lemma) is exactly what puts the ≡ under the turnstile. |
a provability predicate P(v₁) representing the honest set P (so Con(S) := ~P(⌜0=1⌝) is a real sentence, and "S⊢X" formalizes as P(X̄)) |
the P* → P retooling (Ex 5–7) and Ch. VII's representability of P. The Second Theorem is about this P, not P*. |
the license to formalize metatheory at all — to code "X is provable" inside S |
§5's asymmetry: provability is representable though truth is not (Thm 6/7). S can reason about its proofs (hence about Con(S)), never about its truth. This is why the Second Theorem is a theorem about provability of consistency, not truth of consistency. |
provable substitution / composition — to push equivalences like G ≡ ~P(Ḡ) through the derivability steps S‑internally |
Theorem 2 (provable composition) and the insistence throughout on provable‑in‑S equivalences. The Second Theorem's derivability conditions are the continuation of this same "keep the ≡ under the turnstile" discipline. |
What Chapter VIII does not yet supply — and hence what the next chapter must add. Chapter VIII gives a G with S ⊢ G ≡ ~P(Ḡ) and a representable P, but the Second Theorem also needs P to satisfy the Hilbert–Bernays–Löb derivability conditions:
- D1: S⊢X ⟹ S⊢P(X̄) (this is just clause 1 of "enumerates P," already here);
- D2: S⊢ P(⌜X⊃Y⌝) ⊃ (P(X̄) ⊃ P(Ȳ)) (P respects modus ponens, provably);
- D3: S⊢ P(X̄) ⊃ P(⌜P(X̄)⌝) (P proves its own D1, provably).
D2 and D3 are the genuinely new labor of the Second‑Theorem chapter — they are what let the metatheoretic proof of the First Theorem be transcribed line‑by‑line into S. Chapter VIII hands that chapter a fully abstract self‑reference engine (Theorem 4) and the correct object (P), so the only remaining work is verifying D2, D3 and running the formalized First‑Theorem argument. In short: Ch. VIII proves you can build "I am not provable" as a provable fixed point over the real provability predicate; the Second‑Theorem chapter proves that predicate is well‑behaved enough to let S see the First Theorem's proof — at which point G (and with it Con(S), which entails G) is exactly what S cannot prove.
A clean way to hold the whole trajectory:
Ch. V–VII: build a self‑referential sentence and reason about it from outside → First Theorem. Ch. VIII: package self‑reference as a lemma, over the honest
P, with the equivalence provable inside; separate provability (expressible) from truth (not). Ch. IX (next): givePits derivability conditions and formalize the First Theorem insideS→ Second Theorem (S ⊬ Con(S)), and Löb's theorem as its reflection.
Distinctions Ledger
| Confusion | One‑line resolution |
|---|---|
| define vs. represent vs. completely represent? | define = separate R from R̄ (one‑directional). represent = provable ⟺ ∈A. completely represent = represent R and ~F represents ~R = exactly separate R from R̄. |
| Why does complete representability need consistency (Prop 1)? | To get the backward arrows: "refutable ⟹ not provable" is the one consistency‑fed step turning define into completely‑represent. |
| weak vs. strong definability of a function? | Weak = defines the graph f(x)=y (right extension). Strong = weak + clause (3): S proves the value unique. Strong is needed for provable substitution. |
| Why is clause (3) load‑bearing in Theorem 2? | Without it, H(n̄)=∃v₂(F∧G) could be satisfied by a rogue v₂≠m̄ inside S, breaking H(n̄) ⊃ G(m̄). (3) collapses the ∃ onto m̄. |
| What discharges Theorem 4's hypothesis? | Prop 4: d(x) is Σ₁ ⟹ recursive (Prop 3) ⟹ strongly definable in (R) (Thm 3) ⟹ in every extension. |
| fixed point vs. Gödel sentence? | Fixed point: S ⊢ X ≡ F(X̄) (provable biconditional). Gödel sentence: X provable ⟺ ⌜X⌝∈A (a coincidence, not proved in S). Fixed point ⟹ Gödel sentence, not conversely. |
Why P* in Ch. V–VII but P now? |
P* pre‑folds the diagonal so no fixed‑point lemma is needed. Once Thm 4 exists, use the honest P — the object the Second Theorem formalizes. |
| Theorem 6 vs. 7 — why "incomparable"? | Thm 6 spends correctness (semantic), no diagonalization. Thm 7 spends consistency (syntactic) + a fixed point. Neither hypothesis implies the other. |
Is P definable? |
No — that needs P recursive, i.e. ~P also Σ₁, contradicting undecidability (Church). P is representable but not definable — the middle tier. |
| What does the Second Theorem still need beyond Ch. VIII? | The derivability conditions D2, D3 on P, plus the formalized First‑Theorem argument. Ch. VIII gives the fixed point + the predicate P + the truth/provability split. |
Self‑Test
Q1. State the three clauses of strong definability and say which one weak definability lacks.
answer
(1) f(a)=b ⟹ S⊢F(ā,b̄); (2) f(a)≠b ⟹ S⊢~F(ā,b̄); (3) f(a)=b ⟹ S⊢∀v₂(F(ā,v₂)⊃v₂=b̄). Weak definability = (1)+(2) only (it defines the graph). (3) — provable uniqueness — is the strong‑only clause.
Q2. Write H(v₁) in Theorem 2 and say where each of clauses (1) and (3) is used.
answer
H(v₁)=∃v₂(F(v₁,v₂)∧G(v₂)). Clause (1) (S⊢F(n̄,m̄)) gives G(m̄) ⊃ H(n̄). Clause (3) (S⊢F(n̄,v₂)⊃v₂=m̄) gives H(n̄) ⊃ G(m̄). Together: S⊢H(n̄)≡G(m̄).
Q3. Prove Theorem 4 from Theorem 2 in three lines.
answer
Thm 2 with f=d, G=F: S⊢H(n̄)≡F(d(n)‾). Put n=h=⌜H⌝: S⊢H(h̄)≡F(d(h)‾). Since d(h)=⌜H(h̄)⌝, set X=H(h̄); then d(h)‾=X̄, so S⊢X≡F(X̄).
Q4. In §3's Lemma, what is G(x,y), and what role do Ω₄, Ω₅ play?
answer
G(x,y)=F(x,y)∧∀z(F(x,z)⊃y≤z) — the least F‑witness. Ω₄ unpacks bounded ∀z≤m̄/∀y≤m̄ into finite disjunctions (so finitely many refutable/trivial instances bundle into a provable universal); Ω₅ (linearity y≤m̄ ∨ m̄≤y) makes the two case‑splits exhaustive. Same ≤‑machinery as Ch. VI/VII, here proving provable uniqueness.
Q5. Why is truth's inexpressibility (§5) a prerequisite rather than an obstacle for the Second Theorem?
answer
The Second Theorem formalizes reasoning about provability, which IS representable (P(v₁)), so Con(S) and "S⊢X" are genuine formulas. Truth is not representable (Tarski), so the metatheory S can internalize is exactly the provability‑theory — which is what Con(S) lives in. The asymmetry is what makes internalization possible and bounds what it can reach.
Q6. What exactly does the Second Theorem still need that Chapter VIII does not provide?
answer
The derivability conditions D2 (P respects modus ponens, provably) and D3 (P proves its own D1), plus the transcription of the First Theorem's proof inside S. Ch. VIII supplies the provable fixed point G ≡ ~P(Ḡ) and the representable predicate P; the next chapter certifies P is well‑behaved enough to formalize the argument.
References & cross‑links
| Imported result | Used in | Source |
|---|---|---|
(R) is a Rosser system; representability of Σ₁ sets; exact separation of disjoint Σ₁ pairs |
§1 (Prop 2, Thm 1) | 08‑04 Thm S₁/S₂, Thm 1/2 |
Ω₄, Ω₅, the ≤‑race machinery |
§3 Lemma (least witness) | 08‑03 Ex 3/4, Lemma S |
| Σ₀‑completeness, (R)=Ω₁–Ω₅ | §3 (Thm 3), everywhere "provable in (R)" | 07‑31 Theorem B* |
P, R, P*, R*; enumerate/represent/express |
Parts II, VIII (Ex 5–8) | 07‑30, 08‑03 |
Tarski's theorem for L_A; Gödel sentence for a set |
§5 (Thm 6), §4 (Thm 5) | Ch. II |
G (Gödel), ρ (Rosser) as hand‑built diagonals |
Part VIII (re‑derivations) | 07‑30 Thm 3, 08‑03 Part VI |
Book span this session: Smullyan, Gödel's Incompleteness Theorems, Ch. VIII, pp. 97–105 — §1 (Prop 1, Prop 2, Thm 1, Ex 1–3), §2 (Thm 2 + Corollary, Ex 4), §3 (Lemma, Thm 3, Prop 3, Prop 4, Ex —), §4 (Thm 4, Cor 1, Thm 5, Ex 5–8), §5 (Thm 6, Thm 7).
What's ahead
- Next chapter — the Second Incompleteness Theorem. The three prerequisites are now in hand (fixed‑point lemma, representable
P, truth/provability split). The new work is the derivability conditions D2, D3 onPand the formalization of the First Theorem insideS, yieldingS ⊬ Con(S); expect Löb's theorem (S⊢ P(X̄)⊃X ⟹ S⊢X) as the reflection of the same machinery, with the Second Theorem as theX=⊥case. - Chapter VIII drills open: Ex 3 (representability vs. definability coincide in
N, fail in P.A. — theP*gap); Ex 5–8 (Gödel, Rosser, Tarski re‑derived via fixed points — worth doing in full, as they are the template for the Second Theorem's sentence); Theorem 5's proof (left as exercise). - Still owed from Ch. V: §6 Ex 10–12 (the
P(X̄)provability predicate; Ex 11's fullΣ₁case) — the Σ₁‑completeness debt, which now dovetails directly with the provability predicate the next chapter formalizes.
Prior session files: 07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 · 08‑03 · 08‑04 · 08‑05 (this file).
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
第八章:可定义性与对角化,第97–105页——把自指引擎封装为一个引理,以及通往第二定理的桥梁
导引——本章用来做什么
先读这里;下面的一切都是其展开。
第五至七章每章都手工构造一个自指句。 哥德尔的G = ∀y~A(h̄,y)、Rosser的ρ = ∀y[A(h̄,y)⊃(∃z≤y)B(h̄,z)]、Shepherdson的φ,每个都通过代入函数手工对角化,其自指都是为眼前单项工作专门设计的。整套装置,E_n(n̄)、封装式E[m̄,n̄]、编码函数Π、对角集合P*,都是为了把自指折进一个特定集合,从而无须一般的不动点机器。
第八章不再手工做这件事。 它一劳永逸地证明不动点引理,亦即对角化引理:
定理4。 若对角函数
d(x)在S中强可定义,则每个公式F(v₁)都有一个不动点:句子X满足S ⊢ X ≡ F(X̄)。
然后把哥德尔,练习5、Rosser,练习6–7、塔斯基,§5,作为直接推论收获。自指不再是一次构造,而是一项服务:在语言中命名任意性质F(v₁),你就得到一个可证地断言“我具有性质F”的句子。
同时还有两项不那么显眼的改造,而它们对接下来的内容至关重要:
- 从
P*到P。 专用对角集合P* = {n : E_n(n̄)可证}退场。既然现在有了一般不动点引理,本章使用直接的可证性集合P={可证句子的哥德尔数}及其表示公式。练习5–7用P,而非P*,加上一个不动点重新完成哥德尔和Rosser。这就是第二定理将要形式化的可证性谓词。 - 从“可证⟺真”,元理论,到“
≡在S中可证”,对象理论。 本章每个主要结果都是一个在S中可证的等价关系:定理2的H(n̄) ≡ G(f(n)‾)、不动点的X ≡ F(X̄)、真谓词的X ≡ T(X̄)。第五至七章主要从外部关于S推理;第八章制造S关于自身所证明的等价关系。这个“在S中可证”就是第二定理的全部货币。
本章主干是一条以不动点引理结束的简短依赖链:
函数的强可定义性,定理2,可证复合引理→
d(x)在(R)的扩张中强可定义,命题4→每个公式都有不动点,定理4→哥德尔、Rosser、塔斯基随之得出。
阅读顺序沿这条主干展开。
第零部分——用一句话说转移,以及哪些东西保持不变
| 第五至七章 | 第八章 | |
|---|---|---|
| 自指 | 逐句手工构建,通过E_n(n̄)/Π |
一个引理:每个F(v₁)都有不动点,定理4 |
| 使用的集合 | P*,对角集合,自指预先折入其中 |
P,直接的可证性集合,另行提供一个不动点 |
| 货币 | 主要是元理论双条件关系,“n∈A ⟺ F(n̄)可证” |
对象理论,等价关系自身在S中可证 |
| 新工具 | — | 函数的强可定义性,定理2 |
保持不变的内容: ≤机器Ω₄, Ω₅,第六/七章,再次出现;这次用来证明函数值可证地唯一,即§3引理中的最小见证极小化。第七章的Rosser系统结果,Σ₁集合的可表示性、不相交Σ₁对的精确分离,被§1的命题2、定理1整套使用。第五章的Σ₀完备性与(R)=Ω₁–Ω₅,支撑每一处“在(R)中可证”。
第一部分——依赖图:一页看完整章
§2 函数的强可定义性
定理2 ── 可证复合:
f强可定义 ⟹ 对任意G(v₁),存在H(v₁)使
S ⊢ H(n̄) ≡ G(f(n)‾)
│ │
│ (推论) │ (取f := d,G := F)
▼ ▼
f⁻¹保持 §4 定理4 ── 不动点引理
表示/精确分离/定义 每个F(v₁)都有X,使S ⊢ X ≡ F(X̄)
│
§3 提供假设: ├─▶ 推论1:在(R)的每个扩张中成立
引理(弱→强, │
最小见证,Ω₄,Ω₅) ├─▶ 练习5 → 哥德尔(∀y~F的不动点,F枚举P)
定理3:所有递归 ├─▶ 练习6,7 → ROSSER(P,R上的≤竞赛的不动点)
函数在(R)中 ├─▶ 练习8 → 塔斯基(P不可定义)
强可定义 │
命题3+命题4: └─▶ §5 定理6,7 → 不存在真谓词
d(x)在(R)的
每个扩张中强可定义 §1 这一切依靠的词汇:
定义/完全表示;
命题1,2;定理1
所有上游内容都为满足定理4的单一假设,即d(x)强可定义而存在;所有下游内容都是将定理4应用于所选的F。
第二部分——可供引用的术语表
承接:E_x=哥德尔数为x的表达式;P=可证句子的哥德尔数,R=可反驳句子的哥德尔数;P*, R*=第五至七章的对角集合。数码约定:n̄=n的数码;对表达式X,X̄=⌜X⌝的数码,后者是它的哥德尔数;f(n)‾=值f(n)的数码。
F在S中定义R,关系:R(ā) ⟹ S⊢F(ā),且~R(ā) ⟹ S⊢~F(ā)。=F将R与其补集R̄分离,在R上可证,在其外可反驳。单向。F完全表示R:F表示R,并且~F表示~R,即把定义的两个条件中的⟹升级为⟺。=精确分离R与R̄,第七章精确分离的A∪B=全部情形,没有“不可判定”地带。- 递归集合/关系:
R与R̄都是Σ₁。Σ₁的自对偶核心,等价于“可判定”。 F弱定义函数f:F(v₁,v₂)定义图关系f(x)=y。下面条件(1)(2)。F强定义,即定义,f:弱定义加上可证的唯一性条件。对f(a)=b:- (1)
f(a)=b ⟹ S⊢F(ā,b̄); - (2)
f(a)≠b ⟹ S⊢~F(ā,b̄); - (3)
f(a)=b ⟹ S⊢ ∀v₂(F(ā,v₂) ⊃ v₂=b̄),“S自身证明该值唯一。” - 递归函数:图
f(x)=y是递归关系。 F(v₁)的不动点:句子X,满足S⊢ X ≡ F(X̄)。- 相对于
S的、集合A的哥德尔句:句子X,在S中可证,当且仅当⌜X⌝∈A。单向,不要求可证的双条件式。 f在S中可接受:对每个在S中可表示的集合A,f⁻¹(A)在S中可表示。S的真谓词:公式T(v₁),对每个句子X,都有S⊢ X ≡ T(X̄)。一个对所有X统一、等价关系可证的不动点引理,§5将表明它不可能存在。
必须分清的三个层级,这个排序是本章要旨:
| 层级 | 对象 | 在S中的状态 |
原因 |
|---|---|---|---|
| 真理 | 真句子 | 不可表达 | 塔斯基,§5、第二章 |
| 可证性 | P |
可表示,不可定义 | P为Σ₁,但~P不是,P不递归,即丘奇定理 |
| 递归集合 | R,且R̄也为Σ₁ |
可定义/完全可表示 | 第七章对不相交Σ₁对R, R̄的精确分离 |
第一定理位于中间层级;第二定理关乎S不能证明一个关于中间层级的特定事实,即它自身的一致性。
第三部分——§1可定义性与完全可表示性:词汇
命题1。 若F在S中定义R,且S一致,则F完全表示R。
证明。 需要定义的两个条件的反向。若S⊢F(ā):由一致性,F(ā)不可反驳,因此由条件(2),~R(ā)不成立,即R(ā)。若S⊢~F(ā):不可证,因此由(1),R(ā)不成立,即~R(ā)。∎ 一致性是唯一枢纽:它把“可反驳⟹不可证”转化为缺少的反向箭头。与第六章引理1相同,只需一剂一致性。
命题2。 (i)若S是Rosser系统,所有递归关系在S中可定义。(ii)若还一致,则所有递归关系完全可表示。
原因。 F定义R当且仅当F分离R与R̄,见定义。递归R满足R, R̄都是Σ₁且不相交,恰好是不相交Σ₁对,因此Rosser系统将它们分离,第七章。(ii)就是(i)+命题1。
定理1。 所有递归关系都在(R)中可定义,因为(R)是Rosser系统,第七章。可定义性传递到每个扩张,因此递归关系在(Q)、P.A.以及(R)的任何一致扩张中可定义。
练习。练习1:F定义R(x₁,x₂)⟹F枚举dom R。练习2,判断真伪:“所有真的Σ₀可证⟹所有Σ₀关系可定义”,真,Σ₀关系递归,且Σ₀完备性直接分离它们。练习3:在完备理论N中,可表示性=可定义性=完全可表示性,全部重合;P.A.中并非如此,提示:P*可表示,但不能完全表示,否则它递归/可判定,与不可判定性矛盾。练习3是对中间层级间隙最鲜明的陈述。
第四部分——§2函数的强可定义性:复合引擎
定理2——可证复合,核心工具
陈述。 若f(x)在S中强可定义,则对任意公式G(v₁),存在公式H(v₁),使每个n都有S⊢ H(n̄) ≡ G(f(n)‾)。
构造。 以F(v₁,v₂)强定义f,设
H(v₁) := ∃v₂( F(v₁,v₂) ∧ G(v₂) )。
证明,固定n,令m=f(n),证明S⊢ H(n̄) ≡ G(m̄):
| 方向 | 论证 | 使用的条件 |
|---|---|---|
G(m̄) ⊃ H(n̄) |
S⊢F(n̄,m̄),条件1,因此G(m̄) ⊃ (F(n̄,m̄)∧G(m̄)) ⊃ ∃v₂(F(n̄,v₂)∧G(v₂)) = H(n̄)。 |
(1) |
H(n̄) ⊃ G(m̄) |
S⊢ F(n̄,v₂) ⊃ v₂=m̄,条件3,因此(F(n̄,v₂)∧G(v₂)) ⊃ (v₂=m̄ ∧ G(v₂)) ⊃ G(m̄);全称化/∃消去⟹H(n̄) ⊃ G(m̄)。 |
(3) |
合取:S⊢ H(n̄) ≡ G(m̄)。∎
为什么是“强”:条件(3)就是全部要点。 弱可定义性只给出图匹配条件(1)(2);它无法给出H(n̄) ⊃ G(m̄),因为在S内部,某个其他v₂可能满足F(n̄,v₂),并拖带一个假的G(v₂)。条件(3),S证明该值唯一,恰好把∃v₂坍缩回m̄。弱=外延正确;强=可证代入。 每个下游的“在S中可证”,不动点,以及最终第二定理的内在化推理,都依靠这次升级。
推论——f⁻¹保持可表示性、精确分离、可定义性
若f强可定义,则通过H(n̄)可证⟺G(f(n)‾)可证,以及可反驳的相同关系:
1. A可表示⟹f⁻¹(A)可表示;
2. (A,B)可精确分离⟹(f⁻¹(A), f⁻¹(B))可精确分离;
3. A可定义⟹f⁻¹(A)可定义。
练习4*:若f只弱可定义,但Sω一致,则A可定义⟹f⁻¹(A)可表示*;ω一致性买回了缺少条件(3)所失去的东西。旧的ω一致性拐杖,恰好在强可定义性缺席的位置再次出现。
第五部分——§3递归函数在(R)中的强可定义性
引理——通过最小见证的≤极小化,从弱到强
陈述。 若S证明Ω₄, Ω₅,则任何在S中弱可定义的函数都强可定义。
构造。 给定弱定义f的F,设
G(x,y) := F(x,y) ∧ ∀z( F(x,z) ⊃ y≤z ),“y满足F,且是满足它的最小者。”
证明,f(n)=m,验证三个强条件:
- (1)
S⊢G(n̄,m̄)。 对k≤m:S⊢ F(n̄,k̄) ⊃ m̄≤k̄;若k<m,F(n̄,k̄)可反驳;若k=m,由Ω₅得m̄≤k̄。Ω₄捆绑出z≤m̄ ⊃ (F(n̄,z)⊃m̄≤z);m̄≤z情形显然;Ω₅合并它们⟹∀z(F(n̄,z)⊃m̄≤z)。结合弱条件1的S⊢F(n̄,m̄)⟹G(n̄,m̄)。 - (2)
k≠m ⟹ S⊢~G(n̄,k̄)。F(n̄,k̄)由弱条件2可反驳,且G⊃F,所以G(n̄,k̄)可反驳。 - (3)
S⊢ ∀y(G(n̄,y) ⊃ y=m̄)。 首先G(n̄,y) ⊃ y≤m̄,把∀z在m̄处实例化,使用S⊢F(n̄,m̄)。然后对k≤m,S⊢ G(n̄,k̄) ⊃ k̄=m̄;若k<m,G(n̄,k̄)可反驳;若k=m,显然。Ω₄捆绑出y≤m̄ ⊃ (G(n̄,y)⊃y=m̄);与G(n̄,y)⊃y≤m̄结合。∎
这是第六/七章的≤竞赛承担新工作。 那里,它打破证明与反驳之间的僵局,以完成分离;这里,它选择最小F见证,使值可证地唯一。相同的Ω₄,把有界∀展开为有限析取,与Ω₅,线性,现在为函数性服务。
定理3。 所有递归函数都在(R)中强可定义,即定理1的弱可定义性+此引理。
命题3。 若图f(x)=y为Σ₁,则f递归,因为f(x)≠y ≡ ∃w(f(x)=w ∧ w≠y)也为Σ₁,所以图的补集同样为Σ₁。
命题4,收获。 对角函数d(x),d(⌜H(v₁)⌝) = ⌜H(H̄)⌝,为Σ₁,因此递归,命题3;因此在(R)的每个扩张中强可定义,定理3+传递到扩张。这恰好是定理4的假设,现在对我们关心的所有系统都已满足。
第六部分——§4不动点引理:核心
定理4——每个公式都有不动点
陈述。 若d(x)在S中强可定义,则每个F(v₁)都有不动点X:S⊢ X ≡ F(X̄)。
证明,三行,而此前每个工具现在都在其中:
1. 应用定理2,取f := d、G := F:得到H(v₁),对所有n,S⊢ H(n̄) ≡ F(d(n)‾)。
2. 令h = ⌜H(v₁)⌝,在n=h处实例化:S⊢ H(h̄) ≡ F(d(h)‾)。
3. 但d(h) = ⌜H(h̄)⌝。因此取X := H(h̄),有d(h)‾ = X̄,得到S⊢ X ≡ F(X̄)。∎
第五至七章中由Π的槽位与承担双重职责的下标h承载的自指,现在压缩为一个等式:d(h) = ⌜H(h̄)⌝,对角函数就是公式命名其自身对角化的行动。
推论1。 每个公式在(R)的每个扩张中都有不动点,命题4。
哥德尔句与不动点——定理5及强度阶梯
定理5。 若d(x)在S中可接受,则每个可表示的A都有哥德尔句。证明留作练习。
讨论:与定理4不可比较,两端都更弱。
- 假设: 强可定义⟹可接受,推论第1项,但反之不然,所以定理5的假设更弱。
- 结论: F的不动点自动是F所表示集合的哥德尔句,可证的X ≡ F(X̄)迫使“X可证⟺F(X̄)可证”,但通常包含更多内容,等价关系可证,而不仅是真。因此定理4的结论更强。更弱假设+更弱结论=不可比较,两个定理都不蕴含另一个;与第六章定理R和定理A的横向关系相同,在一个轴上弱化,在另一个轴上付出代价,也与下面定理6/7相同。不是第五章A*与A的关系,那是严格加强,因此可比较。
第七部分——§5真谓词:两遍塔斯基
定理6。 若S正确,即N的子系统,则不存在S的真谓词。
证明。 真谓词对所有X给出S⊢ X ≡ T(X̄);正确性使每个这样的等价关系为真,因此X真⟺T(X̄)真,即T(v₁)表达真句子的集合,与第二章关于L_A的塔斯基定理矛盾。∎ 语义路线:使用真理,不用对角化。
定理7。 若S简单一致,且d(x)强可定义,则不存在真谓词。
证明。 取X为~T(v₁)的不动点,定理4:S⊢ X ≡ ~T(X̄)。若T是真谓词,也有S⊢ X ≡ T(X̄)。连接:S⊢ T(X̄) ≡ ~T(X̄),S不一致。∎ 句法路线:使用对角化+一致性,不用语义。
两者不可比较,方式恰同哥德尔与Rosser:定理6付出正确性,强、语义的,跳过对角化;定理7付出一致性,弱、句法的,再以一个不动点支付代价。整本书的辩证关系,语义假设与句法假设,在这一对相向定理中呈现。
推动下一章的不对称性。 把§5放在第七章旁边:真理甚至不可表达,而可证性P可表示。 这一间隙不是奇闻,而是形式化元数学的前提。“X可证”可以编码为公式P(X̄),第七章;“X为真”不可以。因此S能谈自身的证明,却永远不能谈自身的真理;第二定理恰好是关于S能够就自身的可证性证明什么的陈述。
第八部分——向后的联系:第八章如何重新封装第五至七章
此前章节手工做的一切,现在都是一个应用于所选F的具名引理。练习把这一点明确化:每道题都是一行对角化,此前却需要一章。
| 先前结果 | 先前如何构建 | 现在,第八章 |
|---|---|---|
哥德尔G=“我不可证” |
在P*上手工对角化∀y~A(h̄,y) |
练习5:∀y~F(x,y)的不动点,F枚举P。一致⟹X不可证;ω一致⟹X不可反驳⟹P.A.不完备。 |
Rosser的ρ,简单一致性 |
在P*, R*上手工对角化≤竞赛 |
练习6:∀y(F(x,y) ⊃ (∃z≤y)G(x,z))的不动点,F,G枚举P,R;由简单一致性得到不可判定。书中印作G(x,y),让z空置;≤竞赛需要被约束的z,应读作G(x,z)。练习7:任何表示与P不相交的R之超集的公式,其任意不动点都不可判定;用真正的P,R重述第六章定理1,无需Ω₄,Ω₅。 |
| 塔斯基不可定义性 | 第二章,语义的 | 练习8/定理7:d强可定义+一致⟹P不可定义/没有真谓词,通过不动点引理得到塔斯基。 |
表格背后有三项结构升级:
1. 自指在使用时不再需要额外假设。 你不再构造自指句,而是引用定理4。构造只存在一次,在d的强可定义性中,命题4。
2. P*→P。 对角集合是一种避免需要不动点引理的装置。有了引理,练习就放下P*,使用真正的可证性集合P,这是真正关心的对象,也是第二定理的对象。
3. 元理论→对象理论。 第五至七章交付我们从外部验证的双条件关系。第八章交付S证明的双条件式。这不是文风变化,而是论证内在化的前提,第二定理所做的正是这一点。
第九部分——向前的联系:通往哥德尔第二不完备定理的桥梁
这就是本章存在的理由。第二定理说:若S一致,并且足够强,则S ⊬ Con(S),S不能证明自身的一致性。其标准证明就是在S内部形式化第一定理的论证,而该形式化使用的恰好是第八章构建的东西:可证的不动点、直接的谓词P、真理/可证性区分,以及支撑它们的可证复合原则,下面四行。
方法上的跃迁。 第一定理,第五至七章,是元定理:“若S一致,则G不可证”,一个我们所断言的关于S的句子。第二定理把它内在化:
S ⊢ ( Con(S) ⊃ G ),S自身证明“如果我一致,G就不可证。” 它由两个在S中可证的事实组装:不动点S ⊢ G ≡ ~P(Ḡ),第八章,以及形式化的第一定理S ⊢ Con(S) ⊃ ~P(Ḡ),下一章的工作。结合两者得到S ⊢ Con(S) ⊃ G;因此S ⊢ Con(S)会强迫S ⊢ G,与G的不可证性矛盾,而只要S一致,后者就成立。故S ⊬ Con(S)。一切取决于能够把推导符号放在外面来运行第一定理的推理。 第八章使这一做法合法。
第二定理逐项从第八章借用什么:
| 第二定理需要…… | 第八章如何提供…… |
|---|---|
句子G,满足S ⊢ G ≡ ~P(Ḡ),“我不可证”,等价关系在S中可证** |
定理4,~P(v₁)的不动点。不只是真的自指,第五章,而是可证的自指;强可定义性升级,条件3/§3引理,恰好把≡放到推导符号之内。 |
可证性谓词P(v₁),表示直接的集合P,使Con(S) := ~P(⌜0=1⌝)成为实际句子,而“S⊢X”形式化为P(X̄) |
P*→P的改造,练习5–7,与第七章P的可表示性。第二定理关于这个P,而非P*。 |
能够形式化元理论的许可,在S内部编码“X可证” |
§5的不对称性:可证性可表示,尽管真理不可表示,定理6/7。S能推理自身的证明,因此也能推理Con(S),却永远不能推理自身的真理。这就是第二定理为何是关于一致性的可证性,而非一致性的真理的定理。 |
可证代入/复合,把G ≡ ~P(Ḡ)之类等价式通过S内部的可推导性步骤传递 |
定理2,可证复合,以及全章对在S中可证之等价关系的坚持。第二定理的可推导性条件是这一“让≡保持在推导符号之内”原则的继续。 |
第八章尚未提供什么,因此下一章必须增加什么。 第八章给出满足S ⊢ G ≡ ~P(Ḡ)的G,以及可表示的P,但第二定理还需要P满足Hilbert–Bernays–Löb可推导性条件:
- D1:S⊢X ⟹ S⊢P(X̄),这只是“枚举P”的条件1,此处已有;
- D2:S⊢ P(⌜X⊃Y⌝) ⊃ (P(X̄) ⊃ P(Ȳ)),P可证地遵循肯定前件式;
- D3:S⊢ P(X̄) ⊃ P(⌜P(X̄)⌝),P可证地证明其自身的D1。
D2、D3是第二定理章节真正的新工作;它们使第一定理的元理论证明能逐行转录进S。第八章交给该章一台完全抽象的自指引擎,定理4,以及正确对象P,因此剩余工作只是验证D2、D3,并运行形式化的第一定理论证。简言之:第八章证明,你能在真正的可证性谓词上,把“我不可证”构建为可证不动点;第二定理章节证明该谓词足够规整,让S看见第一定理的证明;到那时,G,连同蕴含G的Con(S),恰好就是S不能证明的东西。
一种清晰把握整条路线的方式:
第五至七章:构建自指句,从外部推理它→第一定理。 第八章:在直接的
P上把自指封装为引理,等价关系在内部可证;区分可表达的可证性与不可表达的真理。 第九章,下一步:赋予P可推导性条件,并在S内部形式化第一定理→第二定理,S ⊬ Con(S),以及作为其反照的Löb定理。
区分清单
| 困惑 | 一行解答 |
|---|---|
| 定义、表示、完全表示? | 定义=分离R与R̄,单向。表示=可证⟺∈A。完全表示=表示R,并且~F表示~R=精确分离R与R̄。 |
| 为什么完全可表示性需要一致性,命题1? | 为得到反向箭头:“可反驳⟹不可证”是唯一由一致性支持的步骤,把定义转为完全表示。 |
| 函数的弱可定义与强可定义? | 弱=定义图f(x)=y,外延正确。强=弱加上条件(3),S证明值唯一。可证代入需要强。 |
| 为什么条件(3)在定理2中承担关键作用? | 没有它,H(n̄)=∃v₂(F∧G)可能被S内部一个异常的v₂≠m̄满足,破坏H(n̄) ⊃ G(m̄)。(3)把∃坍缩到m̄上。 |
| 什么满足定理4的假设? | 命题4:d(x)为Σ₁⟹递归,命题3⟹在(R)中强可定义,定理3⟹在每个扩张中如此。 |
| 不动点与哥德尔句? | 不动点:S ⊢ X ≡ F(X̄),可证双条件式。哥德尔句:X可证⟺⌜X⌝∈A,一种重合,未在S中证明。不动点⟹哥德尔句,反之不然。 |
为什么第五至七章用P*,现在用P? |
P*预先折入对角化,因此不需要不动点引理。一旦有了定理4,就使用直接的P,第二定理形式化的对象。 |
| 定理6与7,为什么“不可比较”? | 定理6付出正确性,语义的,不用对角化。定理7付出一致性,句法的,加不动点。两者假设互不蕴含。 |
P可定义吗? |
不能,那需要P递归,即~P也为Σ₁,与不可判定性,丘奇定理,矛盾。P可表示而不可定义,中间层级。 |
| 超出第八章,第二定理还需要什么? | P上的可推导性条件D2、D3,加形式化的第一定理论证。第八章给出不动点+谓词P+真理/可证性区分。 |
自测
问题1。 陈述强可定义性的三个条件,并说明弱可定义性缺少哪一个。
答案
(1)f(a)=b ⟹ S⊢F(ā,b̄);(2)f(a)≠b ⟹ S⊢~F(ā,b̄);(3)f(a)=b ⟹ S⊢∀v₂(F(ā,v₂)⊃v₂=b̄)。弱可定义性只有(1)+(2),它定义图。(3),可证的唯一性,是强可定义性独有的条件。
问题2。 写出定理2中的H(v₁),说明条件(1)与(3)分别在哪里使用。
答案
H(v₁)=∃v₂(F(v₁,v₂)∧G(v₂))。条件(1),S⊢F(n̄,m̄),给出G(m̄) ⊃ H(n̄)。条件(3),S⊢F(n̄,v₂)⊃v₂=m̄,给出H(n̄) ⊃ G(m̄)。结合:S⊢H(n̄)≡G(m̄)。
问题3。 用三行从定理2证明定理4。
答案
定理2取f=d、G=F:S⊢H(n̄)≡F(d(n)‾)。令n=h=⌜H⌝:S⊢H(h̄)≡F(d(h)‾)。因为d(h)=⌜H(h̄)⌝,设X=H(h̄);那么d(h)‾=X̄,所以S⊢X≡F(X̄)。
问题4。 §3引理中的G(x,y)是什么,Ω₄、Ω₅各有什么作用?
答案
G(x,y)=F(x,y)∧∀z(F(x,z)⊃y≤z),最小的F见证。Ω₄把有界∀z≤m̄/∀y≤m̄展开为有限析取,让有限多个可反驳/显然实例捆绑为可证全称句;Ω₅,线性y≤m̄ ∨ m̄≤y,使两种分情况穷尽所有可能。与第六/七章相同的≤机器,此处证明可证唯一性。
问题5。 为什么真理的不可表达性,§5,是第二定理的前提而非障碍?
答案
第二定理形式化关于可证性的推理,而可证性确实可表示,P(v₁),所以Con(S)与“S⊢X”是真正公式。真理不可表示,塔斯基,因此S能内在化的元理论恰好是可证性理论,Con(S)正位于其中。这种不对称性使内在化成为可能,并限定其可及范围。
问题6。 第二定理还需要什么是第八章没有提供的?
答案
可推导性条件D2,P可证地遵循肯定前件式,以及D3,P证明自身的D1,再加把第一定理的证明转录到S内部。第八章提供可证不动点G ≡ ~P(Ḡ)与可表示谓词P;下一章确认P足够规整,能够形式化论证。
参考与交叉链接
| 引入结果 | 使用位置 | 来源 |
|---|---|---|
(R)是Rosser系统;Σ₁集合的可表示性;不相交Σ₁对的精确分离 |
§1,命题2、定理1 | 08‑04定理S₁/S₂、定理1/2 |
Ω₄, Ω₅,≤竞赛机器 |
§3引理,最小见证 | 08‑03练习3/4、引理S |
| Σ₀完备性,(R)=Ω₁–Ω₅ | §3,定理3,以及每处“在(R)中可证” | 07‑31定理B* |
P、R、P*、R*;枚举/表示/表达 |
第二、八部分,练习5–8 | 07‑30、08‑03 |
关于L_A的塔斯基定理;集合的哥德尔句 |
§5,定理6;§4,定理5 | 第二章 |
手工构造的对角句G,哥德尔,与ρ,Rosser |
第八部分,重新推导 | 07‑30定理3、08‑03第六部分 |
本次学习书页范围:Smullyan《哥德尔不完备定理》,第八章,第97–105页,§1,命题1、命题2、定理1、练习1–3;§2,定理2+推论、练习4;§3,引理、定理3、命题3、命题4、练习—;§4,定理4、推论1、定理5、练习5–8;§5,定理6、定理7。
后续内容
- 下一章,第二不完备定理。 三项前提现已掌握,不动点引理、可表示的
P、真理/可证性区分。新工作是P上的可推导性条件D2、D3,以及在S内部形式化第一定理,得到S ⊬ Con(S);预期出现Löb定理,S⊢ P(X̄)⊃X ⟹ S⊢X,作为同一机器的反照,第二定理则是X=⊥的情形。 - 第八章尚待完成的操练:练习3,可表示性与可定义性在
N中重合,在P.A.中失败,即P*间隙;练习5–8,通过不动点重新推导哥德尔、Rosser、塔斯基,值得完整做一遍,因为它们是第二定理句子的模板;定理5的证明,留作练习。 - 第五章仍待完成: §6练习10–12,
P(X̄)可证性谓词,练习11的完整Σ₁情形,即Σ₁完备性事项;它现在直接衔接下一章将形式化的可证性谓词。
此前学习文件:07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 · 08‑03 · 08‑04 · 08‑05,本文件。