Gui Ruiyan

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

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 in S, then every formula F(v₁) has a fixed point: a sentence X with S ⊢ 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:

  1. From P* to P. The bespoke diagonal set P* = {n : E_n(n̄) provable} is retired. Now that a general fixed‑point lemma exists, the chapter works with the honest provability set P = {Gödel numbers of provable sentences} and its representing formula. Exercises 5–7 redo Gödel and Rosser with P, not P*, plus a fixed point. This is the provability predicate the Second Theorem will formalize.
  2. From "provable ⟺ true" (metatheory) to "≡ is provable in S" (object theory). Every headline of this chapter is a provable‑in‑S equivalence — Theorem 2's H(n̄) ≡ G(f(n)‾), the fixed point's X ≡ F(X̄), the truth‑predicate's X ≡ T(X̄). Chapters V–VII mostly reasoned about S from outside; Chapter VIII manufactures equivalences S proves 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).

  • F defines R (a relation) in S: R(ā) ⟹ S⊢F(ā) and ~R(ā) ⟹ S⊢~F(ā). = F separates R from its complement R̄ (provable on R, refutable off it). One‑directional.
  • F completely represents R: F represents R and ~F represents ~R — i.e. define's two clauses with ⟹ upgraded to ⟺. = exactly separates R from R̄ (the A∪B = everything case of Ch. VII exact separation — no "undecidable" band).
  • recursive set/relation: R and R̄ are both Σ₁. (The self‑dual core of Σ₁; equivalently "decidable.")
  • F weakly defines a function f: F(v₁,v₂) defines the graph relation f(x)=y. (Clauses (1)(2) below.)
  • F strongly defines (= defines) f: weakly defines plus a provable uniqueness clause. For 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 itself proves the value is unique."
  • recursive function: the graph f(x)=y is a recursive relation.
  • fixed point of F(v₁): a sentence X with S⊢ X ≡ F(X̄).
  • Gödel sentence for A w.r.t. S: a sentence X that is provable in S iff ⌜X⌝∈A. (One‑directional — no provable biconditional demanded.)
  • f acceptable in S: for every set A representable in S, f⁻¹(A) is representable in S.
  • truth‑predicate for S: a formula T(v₁) with S⊢ X ≡ T(X̄) for every sentence X. (A fixed‑point lemma uniform over all X, 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 ) — "y satisfies F, and is the least such."

Proof (f(n)=m; verify the three strong clauses):

  • (1) S⊢G(n̄,m̄). For k≤m: S⊢ F(n̄,k̄) ⊃ m̄≤k̄ (if k<m, F(n̄,k̄) refutable; if k=m, m̄≤k̄ by Ω₅). Ω₄ bundles z≤m̄ ⊃ (F(n̄,z)⊃m̄≤z); the case m̄≤z is trivial; Ω₅ merges them ⟹ ∀z(F(n̄,z)⊃m̄≤z). With S⊢F(n̄,m̄) (weak clause 1) ⟹ G(n̄,m̄).
  • (2) k≠m ⟹ S⊢~G(n̄,k̄). F(n̄,k̄) refutable (weak clause 2) and G⊃F, so G(n̄,k̄) refutable.
  • (3) S⊢ ∀y(G(n̄,y) ⊃ y=m̄). First G(n̄,y) ⊃ y≤m̄ (instantiate the ∀z at m̄, use S⊢F(n̄,m̄)). Then for k≤m, S⊢ G(n̄,k̄) ⊃ k̄=m̄ (if k<m, G(n̄,k̄) refutable; if k=m, trivial); Ω₄ bundles y≤m̄ ⊃ (G(n̄,y)⊃y=m̄); combine with G(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: X provable ⟺ ⌜X⌝∈A. A one‑directional coincidence.
  • A fixed point of F: S⊢ X ≡ F(X̄). The biconditional is proved inside S.

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 ) — S itself proves "if I am consistent, G is unprovable." This is assembled from two provable‑in‑S facts: the fixed point S ⊢ G ≡ ~P(Ḡ) (Chapter VIII) and the formalized First Theorem S ⊢ Con(S) ⊃ ~P(Ḡ) (the next chapter's labor). Combining them gives S ⊢ Con(S) ⊃ G; so S ⊢ Con(S) would force S ⊢ G, contradicting G's unprovability (which holds whenever S is consistent). Hence S ⊬ 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): give P its derivability conditions and formalize the First Theorem inside S → 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.

answerH(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.

answerThm 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?

answerG(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?

answerThe 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?

answerThe 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.


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 on P and the formalization of the First Theorem inside S, yielding S ⊬ 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 the X=⊥ case.
  • Chapter VIII drills open: Ex 3 (representability vs. definability coincide in N, fail in P.A. — the P* 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).