Gui Ruiyan

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

Study journals ·

Gödel's Incompleteness Theorems — Session 2026‑07‑31

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 V, Part II: Σ₀‑Completeness (pp. 66–74) — closing Theorem G, and the ω‑Incompleteness Theorem C

This session completes the arc from the two prior Chapter‑V sessions (Part I abstract theorems, 07‑30; the ω‑consistency prelude, 07‑29). We proved Theorem B (all true Σ₀‑sentences are provable — in fact in the tiny systems (R₀), (Q₀)), which is the last girder of Theorem G (Gödel for P.A.), and then extracted Theorem C, the ω‑incompleteness theorem "most mathematicians miss."

Reading order below follows the order understanding was actually built (blocker first), not the book's order.


Part 0 — The opening blocker: three different "inductions"

The proof kept saying "by induction" and the reader half‑remembered an induction axiom from earlier P.A. sessions. Untangling this was the key that unlocked the chapter.

# Where it appears Inducts on Is it the P.A. axiom?
(I) Prop 1 proof (p. 66–67) the degree (logical complexity) of a Σ₀‑sentence No — ordinary induction in the metatheory
(II) (R₀) ⊆ (Q₀) proof (p. 70–71) the number n (proving numeral facts) No — meta‑induction; object‑axioms N₃–N₈ supply base/step
(III) the scheme dropped to build (Q) the P.A. induction scheme Yes — the one the reader remembered

Punchline of the whole section: Σ₀‑completeness never uses (III). It survives in the finite system (Q₀) = P.A. minus induction, and in the weaker (R₀). The "induction hypothesis" in Prop 1 is (I): the metatheoretic assumption that every lower‑degree Σ₀‑sentence is already correctly decidable.


Part I — GOAL and the reduction chain

GOAL. Prove Theorem B: all true Σ₀‑sentences are provable in P.A. — in fact in (R₀), (R), (Q₀), (Q). (Earlier arc needs this to turn "S enumerates P*" into a working object; Theorems A + B ⟹ Theorem G.)

Reduction pipeline:

Prop 1:  C₁ & C₂            ⟹ Σ₀-complete        (meta-induction on DEGREE)
Prop 2:  D₁ & D₂ & D₃       ⟹ C₁ & C₂
Prop 3:  (R₀) satisfies D₁,D₂,D₃  ⟹ (R₀) Σ₀-complete
Prop 4/5: (R₀) ⊆ (Q₀) ⊆ (Q) ⊆ P.A.,  (R₀) ⊆ (R)   (meta-induction on n, via N₁–N₉)
⟹ Theorem B*:  (R₀),(R),(Q₀),(Q),P.A. all Σ₀-complete

Part II — Citable glossary

  • numeral k̄ = 0 followed by k primes; (k+1)‾ = k̄'. Compound (m+n)‾ = numeral of the number m+n.
  • atomic Σ₀‑sentence — t₁ = t₂ or t₁ ≤ t₂, closed terms; after evaluating closed terms to numerals, reduces to m̄ = n̄ or m̄ ≤ n̄.
  • degree — count of ~, ⊃, bounded ∀ in the formula; atomic ⟹ degree 0. In (∀w ≤ n̄)F(w), the body F has degree one lower; numeral substitution for a variable adds no logical symbol, so deg F(m̄) = deg F(w).
  • refutable in S — S ⊢ ~X.
  • correctly decidable (corr‑dec) in S — (X true ∧ S⊢X) ∨ (X false ∧ S⊢~X). A metatheoretic bridge predicate, not a property inside S.
  • Σ₀‑complete — every true Σ₀‑sentence is provable (weaker than corr‑dec of all Σ₀‑sentences, which is what the induction actually delivers).
  • C₁ every atomic Σ₀‑sentence is corr‑dec. C₂ if F(0̄),…,F(n̄) all provable then (∀w≤n̄)F(w) provable.
  • D₁ true atomic Σ₀‑sentences provable. D₂ m≠n ⟹ S⊢ m̄≠n̄. D₃ S ⊢ w ≤ n̄ ⊃ (w=0̄∨…∨w=n̄).
  • (Q₀) = N₁–N₈ (finite; (Q) adds N₉; P.A. adds the induction scheme):
  • N₁ v₁'=v₂' ⊃ v₁=v₂ N₂ 0≠v₁' N₃ v₁+0=v₁ N₄ v₁+v₂'=(v₁+v₂)'
  • N₅ v₁·0=0 N₆ v₁·v₂'=(v₁·v₂)+v₁ N₇ v₁≤0 ≡ v₁=0 N₈ v₁≤v₂' ≡ (v₁≤v₂ ∨ v₁=v₂')
  • N₉ v₁≤v₂ ∨ v₂≤v₁ (linearity; in (Q), not (Q₀))
  • (R₀) = Ω₁–Ω₄ ((R) adds Ω₅):
  • Ω₁ m̄+n̄=k̄ (m+n=k) Ω₂ m̄·n̄=k̄ (m·n=k) Ω₃ m̄≠n̄ (m≠n)
  • Ω₄ v₁≤n̄ ≡ (v₁=0̄∨…∨v₁=n̄) — a biconditional (see Part V) Ω₅ v₁≤n̄ ∨ n̄≤v₁

Part III — Proposition 1: C₁ & C₂ ⟹ Σ₀‑complete (induction on degree)

Load. Prove the stronger claim "every Σ₀‑sentence is corr‑dec," by induction on degree; Σ₀‑completeness is the "true" half.

Base — atomic (degree 0): corr‑dec by C₁.

Step ~X (IH: X corr‑dec):

~X is… X is… IH gives finish how
true false S ⊢ ~X ~X provable S⊢~X is "~X provable" — definitional
false true S ⊢ X ~X refutable logic X ⊃ ~~X

Step X ⊃ Y (IH: X, Y corr‑dec):

X⊃Y is… truth‑table reason IH gives finish tautology
true X false S⊢~X provable ~X ⊃ (X⊃Y)
true Y true S⊢Y provable Y ⊃ (X⊃Y)
false X true ∧ Y false S⊢X, S⊢~Y refutable (X ∧ ~Y) ⊃ ~(X⊃Y)

Step (∀w ≤ n̄)F(w) — the only case needing non‑logical input. IH: each F(k̄), k≤n, corr‑dec.

Case A — true:

Step Claim Justification
A1 each F(0̄),…,F(n̄) true truth recursion for bounded ∀
A2 each F(k̄) a lower‑degree sentence body drops one bounded ∀; numeral adds no logical symbol
A3 ∴ each F(k̄) corr‑dec IH
A4 ∴ each F(k̄) provable A3 (corr‑dec) + A1 (true)
A5 (∀w≤n̄)F(w) provable C₂ on A4

Case B — false:

Step Claim Justification
B1 ∃ m≤n, F(m̄) false truth recursion
B2 F(m̄) lower‑degree sentence as A2
B3 ∴ F(m̄) corr‑dec IH
B4 S ⊢ ~F(m̄) B3 + B1
B5 S ⊢ m̄ ≤ n̄ atomic → C₁, true since m≤n
B6 S ⊢ ~(m̄≤n̄ ⊃ F(m̄)) — the instance is refutable tautology (A∧~B)⊃~(A⊃B), fed by B5, B4
B7 S ⊢ (∀w≤n̄)F(w) ⊃ (m̄≤n̄ ⊃ F(m̄)) logically valid (whole ⊃ its instance)
B8 S ⊢ ~(∀w≤n̄)F(w) — the whole is refutable modus tollens: B7 + B6

Finite, well‑founded ladder on degree ⟹ every Σ₀‑sentence corr‑dec. ∎

Labor split (the moral): C₁ = base; pure logic does ~ and ⊃ for free; C₂ is spent at exactly one rung — A5 (assembling a bounded universal from its instances). There is deliberately no rung for the unbounded ∀ — that is where truth and provability part ways and Gödel's G escapes.

Two conceptual results earned this session

(1) Why the invariant is corr‑dec, not "true ⟹ provable." The ~X case needs the other direction ("X false ⟹ X refutable"), so a one‑directional invariant isn't preserved under negation. Both directions together = corr‑dec. The invariant is engineered.

(2) How truth "propagates" when truth is external to strings. It does not propagate inside S. The whole induction is metatheoretic. Truth rides the Tarski recursion (a compositional computation we perform); provability rides C₁/C₂ (facts about S). The induction keeps the two external computations synchronized across degree. Anti‑drift is guaranteed because classical logic in S is Boolean‑complete: every truth‑table row has a provable‑tautology witness, so the map "parts' verdicts ⟹ whole's verdict" is total — no compound can go "silent." In general truth and provability do diverge (that is incompleteness); Prop 1 shows they are forced to agree only on Σ₀, precisely because Σ₀ is closed under the operations that have a syncing fact (~,⊃ free; bounded ∀ patched by C₂).

(3) IH vs C₁ is not circular. Induction proves a conditional: assume corr‑dec for strictly lower degree, conclude it for the current one. No object's status proves its own. C₁ establishes the ground floor (atoms); the IH is the accumulated result below the current degree and already contains C₁'s output as its degree‑0 layer. So a general ~X/X⊃Y step cites the IH (which subsumes C₁); it is C₁ only when the subformula is itself atomic.


Part IV — Proposition 2: D₁ & D₂ & D₃ ⟹ C₁ & C₂

Repackages C₁, C₂ into checkable conditions. Note the asymmetry: D₃ alone ⟹ C₂; all three ⟹ C₁.

Part 1 — C₁ (true atoms by D₁; false atoms refutable):

atomic status show how
any true atomic true provable D₁
m̄=n̄, false (m≠n) false S⊢~(m̄=n̄) D₂: m̄≠n̄ is ~(m̄=n̄)
m̄≤n̄, false (m>n) false S⊢~(m̄≤n̄) chain ↓

m̄≤n̄‑false chain:

# Claim Justification
1 S ⊢ m̄≤n̄ ⊃ (m̄=0̄∨…∨m̄=n̄) D₃ at w:=m̄
2 for each k≤n: S ⊢ ~(m̄=k̄) m>n≥k so m≠k; D₂
3 S ⊢ ~(m̄=0̄∨…∨m̄=n̄) De Morgan on 2
4 S ⊢ ~(m̄≤n̄) modus tollens 1,3

(Compound closed terms collapse to numerals first via D₁ — m̄+n̄=(m+n)‾ is a true atomic — so the two‑shape reduction is WLOG.)

Part 2 — C₂ from D₃. Assume S⊢F(0̄),…,S⊢F(n̄):

# Claim Justification
1 S ⊢ w≤n̄ ⊃ (w=0̄∨…∨w=n̄) D₃
2 for each k≤n: S ⊢ w=k̄ ⊃ F(w) equality‑substitution: w=k̄ ⊃ (F(k̄)⊃F(w)) valid, chained with S⊢F(k̄)
3 S ⊢ w≤n̄ ⊃ F(w) ∨‑elimination (proof by cases) on 1 + 2
4 S ⊢ ∀w(w≤n̄ ⊃ F(w)) generalization rule (w free, no open hypothesis)
5 S ⊢ (∀w≤n̄)F(w) that formula is the bounded ∀ by definition

D's ⟹ C's; by Prop 1, S is Σ₀‑complete. ∎


Part V — Proposition 3: (R₀) is Σ₀‑complete (+ the Ω₄ subtlety)

Ω₄ is a biconditional ≡, not ⊃. Confirmed by Exercise 8, which names the one‑way ⊃ version Ω₄′ and calls it weaker. This split is load‑bearing: - D₃ uses the ⊃ half of Ω₄. - D₁'s ≤‑case uses the ⟸ half.

Proof. Verify D₁, D₂, D₃, then Prop 2. Two are axioms outright:

condition discharged by
D₂ scheme Ω₃ verbatim
D₃ ⊃ half of Ω₄ (generalize v₁, re‑instantiate to any w)

D₁ (true atomics), four shapes:

true atomic condition provable by
m̄=n̄ m=n first‑order logic with identity (it is n̄=n̄)
m̄+n̄=k̄ m+n=k Ω₁
m̄·n̄=k̄ m·n=k Ω₂
m̄≤n̄ m≤n chain ↓ (⟸ half of Ω₄)

≤‑case: S⊢ m̄≤n̄ ≡ (m̄=0̄∨…∨m̄=n̄) (Ω₄); S⊢ m̄=m̄ (identity) is one disjunct since m≤n; so the disjunction is provable; ⟸ half gives S⊢ m̄≤n̄. ∎

Design insight: the biconditional Ω₄ splits its duties — ⊃ half serves D₃ ("being ≤n̄ forces being one of 0̄…n̄"), ⟸ half serves D₁ ("being one of 0̄…n̄ forces being ≤n̄"). (R₀) is minimal because D₂ and half of D₃ are literally its axioms.


Part VI — Proposition 4/5: the embedding, and Theorem B*

Object facts, proved by meta‑induction on n, in a system with no induction axiom. Each n yields a separate finite (Q₀)‑proof from N₁–N₈; (Q₀) proves every instance but cannot bundle them into a ∀‑theorem — the exact ω‑incompleteness gap.

Prop 4 — (R₀) ⊆ (Q₀): each Ω‑scheme is a (Q₀)‑theorem

Ω₁ m̄+n̄=(m+n)‾, induction on n:

instance how
base n=0 m̄+0̄=m̄=(m+0)‾ N₃
step m̄+(n+1)‾=(m+n+1)‾ m̄+n̄' =(N₄)(m̄+n̄)' =(IH)(m+n)‾' =(m+n+1)‾

Ω₂ m̄·n̄=(m·n)‾, induction on n:

instance how
base n=0 m̄·0̄=0̄=(m·0)‾ N₅
step m̄·(n+1)‾=(m(n+1))‾ m̄·n̄' =(N₆)(m̄·n̄)+m̄ =(IH)(m·n)‾+m̄ =(Ω₁)(m·n+m)‾

Ω₃ m̄≠n̄ (m≠n), successor‑peeling. WLOG m<n, gap d=n−m>0; prove j̄≠(j+d)‾ by induction on j:

instance how
base j=0 0̄≠d̄ d̄=(d−1)‾', so it's 0≠(·)' — N₂
step (j+1)‾≠(j+1+d)‾ contrapositive of N₁ (v₁≠v₂ ⊃ v₁'≠v₂'): prime both sides of IH

m̄≠n̄ = instance j=m, d=n−m. (N₂ plants the difference at 0; N₁ carries it up.)

Ω₄ v₁≤n̄ ≡ (v₁=0̄∨…∨v₁=n̄), induction on n:

instance how
base n=0 v₁≤0̄ ≡ v₁=0̄ N₇ (already ≡)
step v₁≤(n+1)‾ ≡ (…∨v₁=(n+1)‾) N₈ v₁≤n̄' ≡ (v₁≤n̄ ∨ v₁=n̄'); sub IH for v₁≤n̄

Since N₇, N₈ are themselves biconditionals, the induction carries the full ≡ for free (the book highlights only the ⊃ direction). ∎ ⟹ (R₀) ⊆ (Q₀).

Prop 5 — (R) ⊆ (Q)

Ω₅ (v₁≤n̄ ∨ n̄≤v₁) = instance of N₉ at v₂:=n̄; with (R₀)⊆(Q₀)⊆(Q). ∎

Theorem B*

Every system is a supersystem of (R₀): (R₀) ⊆ (Q₀) ⊆ (Q) ⊆ P.A. and (R₀) ⊆ (R) ⊆ (Q). A supersystem proves everything its subsystem proves; (R₀) proves all true Σ₀‑sentences (Prop 3), so:

Theorem B*. (R₀), (R), (Q₀), (Q), P.A. are all Σ₀‑complete. ∎

This is Theorem B. With Theorem A, Theorem G (Gödel for P.A.) is complete.

Two meta‑inductions, side by side:

Prop 1 Prop 4
inducts on degree of a formula the number n
invariant corr‑dec (truth↔provability bridge) "this numeral equation is a (Q₀)‑theorem"
object side supplies C₁, C₂ N₁–N₈, one axiom per rung
object theory's own induction none none

Neither is the P.A. induction scheme; both are ordinary mathematics reasoning about a weak system from outside.


Part VII — Closing Theorem G

Step Claim Justification
Step Claim Justification
--- --- ---
1 all true Σ₀‑sentences provable in P.A. Theorem B
2 P* is enumerated in P.A. by a Σ₀‑formula A(v₁,v₂) sub‑chain 2a–2d below
3 G := ∀v₂~A(h̄,v₂), h = Gödel# of ∀v₂~A(v₁,v₂); by def of P*, G provable ⟺ h∈P* diagonal (Lemma 1)
4 G unprovable (needs only simple consistency) Theorem 3, cheap half
5 G unrefutable (needs ω‑consistency) Theorem 3, expensive half
6 G undecidable ⟹ P.A. incomplete 4 + 5
— G is true G unprovable ⟹ h∉P* ⟹ every ~A(h̄,m̄) true ⟹ ∀v₂~A(h̄,v₂) true

Step 2 unpacked — how "axiomatizable + Theorem B" yields the Σ₀‑enumerator A

The one‑line justification was both wrong (it's Σ₁, not Σ₀) and too compressed. The real derivation has two independent ingredients that meet at the end. Recall the vocabulary from the 07‑29 prelude: a set is enumerated by a formula (clause 1: members force some instance provable; clause 2: non‑members force every instance refutable) — this is weaker than represented (⟺ provable), and needs only Theorem B, not ω‑consistency.

# Claim Justification
2a Theorem B ⟹ every Σ₁ set is enumerated in P.A. by a Σ₀‑formula. For a Σ₁ set X = {n : ∃m R(n,m)} with R Σ₀: if n∈X, some R(n̄,m̄) is a true Σ₀‑sentence, hence provable (clause 1 ✓); if n∉X, every ~R(n̄,m̄) is a true Σ₀‑sentence, hence provable (clause 2 ✓). Theorem B (Σ₀‑completeness) applied instance‑by‑instance to the Σ₀‑matrix R
2b P (the set of Gödel numbers of P.A.‑provable sentences) is Σ₁. P.A. is axiomatizable = formal = r.e.; the provability predicate is ∃y Pf(y,x) with Pf ("y codes a proof of x") recursive — the 07‑28/07‑26 arithmetization, bounded by Theorem D
2c P* is Σ₁. P* = {n : E_n(n̄) provable} = d⁻¹(P), where d(n) = Gödel# of E_n(n̄) is a recursive substitution function. preimage of a Σ₁ set (2b) under a recursive function is Σ₁ (Σ₁ closed under recursive substitution, Prop C, 07‑28)
2d ∴ P* is enumerated in P.A. by a Σ₀‑formula A(v₁,v₂). 2c (P* is Σ₁) fed into 2a (every Σ₁ set is Σ₀‑enumerable)

So the chain is: axiomatizability makes P — and hence the diagonal P* — Σ₁ (2b, 2c); Theorem B makes every Σ₁ set Σ₀‑enumerable (2a); the two combine to give the enumerator A (2d). Note the division of labor mirrors the earlier arc: enumeration is all step 2 needs (Theorem B alone); the jump to representation — where G becomes undecidable — is what later spends ω‑consistency (steps 4–5, via Theorem 3).

So P.A. leaves a true sentence unprovable — and we know it's true, though the demonstration isn't formalizable in P.A. (Second Theorem, Ch. 9).


Part VIII — Theorem C: the ω‑Incompleteness Theorem (the one mathematicians miss)

Phenomenon: a formula F(v₂) such that P.A. proves every numerical instance F(0̄), F(1̄), F(2̄), … yet cannot prove ∀v₂F(v₂). Viscerally more shocking than "some sentence is undecidable": P.A. seems to "know" F of every number but can't conclude the universal.

The witness is the Gödel sentence itself, read the other way. Setup: A enumerates P* — clause 1: n∈P* ⟹ ∃m [S⊢A(n̄,m̄)]; clause 2: n∉P* ⟹ ∀m [S⊢~A(n̄,m̄)].

# Claim Justification
1 G=∀v₂~A(h̄,v₂) unprovable simple consistency (Thm 3 cheap half): if G provable then h∈P*, clause 1 gives some A(h̄,m̄) provable, but G provable ⟹ ~A(h̄,m̄) provable ⟹ inconsistent
2 h ∉ P* contrapositive of "G provable ⟺ h∈P*" with (1)
3 every ~A(h̄,m̄) provable (m=0,1,2,…) clause 2, from (2)
4 ∀v₂~A(h̄,v₂) unprovable = (1)
5 F(v₂):=~A(h̄,v₂): all F(m̄) provable (3), ∀v₂F(v₂) unprovable (4) ω‑incomplete by definition

Theorem C. Any simply consistent axiomatizable system in which all true Σ₀‑sentences are provable is ω‑incomplete.

Theorem A vs Theorem C — the "transposition," teased apart

Surface reading: swap ω‑consistent ↔ simply consistent in the hypothesis and incomplete ↔ ω‑incomplete in the conclusion. But it is not a symmetric duality — there's a cost asymmetry:

Theorem A (incompleteness) Theorem C (ω‑incompleteness)
hypothesis axiomatizable + all‑true‑Σ₀‑provable + ω‑consistent same + simply consistent
conclusion ∃ undecidable sentence (G) ∃ F: all F(m̄) provable, ∀vF not
shows about G unprovable (simple) and unrefutable (ω) unprovable (simple); instances provable (h∉P*)
ω‑consistency spent on making G unrefutable nothing — not needed

The real difference. Both rest on the same cheap core: G unprovable + all instances ~A(h̄,m̄) provable, from simple consistency alone. Incompleteness then pays extra (ω‑consistency) to also close off refutability and make G undecidable. ω‑incompleteness skips that payment — it reads the instance/universal gap directly. So ω‑incompleteness is the more primitive, cheaper fact; incompleteness is what you buy by adding ω‑consistency.

Why the two notions genuinely come apart. A system can be ω‑incomplete in two ways: - benign (ω‑consistent): ∀vF is undecidable — Gödel incompleteness. - pathological (ω‑inconsistent): ∀vF is refutable while all F(m̄) provable — Exercise 9 below.

ω‑consistency is exactly the assumption that forbids the pathological branch (proving ∃v~F(v) while all F(m̄) provable). That's why it's the extra ingredient Theorem A needs and Theorem C doesn't.


Part IX — Exercise 9: a system consistent but not ω‑consistent

Task. Assuming P.A. consistent, form P.A. + {~G} (add the negation of the Gödel sentence as a new axiom). Show it is (simply) consistent but ω‑inconsistent. (This is the concrete "simply‑consistent‑but‑ω‑inconsistent" example — the pathological branch of Part VIII, and the standard proof that the two notions are not the same. Definitions from the 07‑29 prelude: simply consistent = no sentence both provable and refutable; ω‑inconsistent = there is a formula B(v) with ∃v B(v) provable yet every B(m̄) refutable.)

# Claim Justification
1 P.A. ⊬ G P.A. simply consistent ⟹ (Thm 3 cheap half, = Part VIII step 1) G is unprovable
2 P.A.+{~G} is simply consistent metatheorem: T+{~σ} is consistent ⟺ T ⊬ σ. Apply with σ = G, T = P.A., using (1).
3 P.A.+{~G} ⊢ ~A(h̄,m̄) for every m = 0,1,2,… each ~A(h̄,m̄) is already a P.A.‑theorem (Part VIII steps 1–3: G unprovable ⟹ h∉P* ⟹ clause 2), and adding an axiom only adds theorems
4 P.A.+{~G} ⊢ ∃v₂ A(h̄,v₂) the new axiom ~G is ~∀v₂~A(h̄,v₂), which is logically ∃v₂ A(h̄,v₂)
5 P.A.+{~G} is ω‑inconsistent take B(v₂) := A(h̄,v₂): (4) gives ∃v₂ B(v₂) provable, (3) gives every B(m̄) refutable — exactly the definition
6 simply consistent + ω‑inconsistent (2) + (5) — the required example

Why step 2's metatheorem holds (the one non‑obvious lemma). If T+{~σ} were inconsistent, it proves everything, so T + {~σ} ⊢ σ; by the deduction theorem T ⊢ (~σ ⊃ σ), and (~σ ⊃ σ) ⊃ σ is a tautology, so T ⊢ σ. Contrapositive: T ⊬ σ ⟹ T+{~σ} consistent. (The converse — T⊢σ ⟹ T+{~σ} inconsistent — is immediate.) So consistency of the extension is equivalent to G being unprovable, which is exactly what simple consistency of P.A. bought in (1).

Why this is the pathological branch of Part VIII. In P.A.+{~G} the ω‑incompleteness witness F(v₂)=~A(h̄,v₂) has all instances F(m̄) provable (3), yet ∀v₂F(v₂) = G is not merely unprovable — it is outright refutable (its negation ~G is an axiom). Contrast the two branches:

∀vF (= G) status which theorem
P.A. itself (ω‑consistent) undecidable — unprovable and unrefutable Theorem A: incompleteness
P.A.+{~G} (ω‑inconsistent) refutable while all F(m̄) provable Exercise 9: ω‑inconsistency

So P.A.+{~G} is ω‑incomplete with a refutable witness, and it is not incomplete at G (G is decidable — refuted — here). That is precisely how ω‑incompleteness separates from incompleteness: dropping ω‑consistency lets the universal ∀vF be false‑and‑refutable even though every instance is provable.


Distinctions Ledger

Confusion raised One‑line resolution
"Which axiom is the induction hypothesis?" None — it's metatheoretic induction (on degree / on n); the P.A. induction scheme is the one (Q₀) drops.
Meta‑induction vs the exponential situation Both leave the object system impoverished while the metatheory reasons freely; but exponential limited expressibility (recovered as a Σ₁‑relation), induction limits provability of universals (not recovered — that gap is ω‑incompleteness).
"How can induction pass along truth, which is external?" It doesn't pass truth through S; the whole induction is external — truth rides the Tarski recursion, provability rides C₁/C₂, kept in lockstep by degree.
Why is corr‑dec (both directions) the invariant, not "true⟹provable"? The ~ case needs the reverse direction; a one‑way invariant isn't preserved under negation.
Why can't the two "machines" drift at a compound? Classical logic in S is Boolean‑complete: every truth‑table row has a provable‑tautology witness, so "parts' verdicts ⟹ whole's verdict" is total — no silent compound.
Is "X false ⟹ S⊢~X" by C₁ or IH? Isn't using IH circular? IH in general (C₁ only if X is atomic). Not circular: IH quantifies over strictly lower degree and already contains C₁'s ground floor; the base is proved outright.
Is Ω₄ ⊃ or ≡? ≡ (biconditional). Exercise 8 names the ⊃ version Ω₄′ and calls it weaker. D₃ uses the ⊃ half, D₁'s ≤‑case the ⟸ half.
B5/B6 in Prop 1 — what does the refutable "instance" mean? The instance Q=(m̄≤n̄⊃F(m̄)) is refutable (antecedent provable, consequent's negation provable = the one false row of ⊃); then P⊃Q valid + ~Q ⟹ ~P by modus tollens.
Theorem A vs Theorem C — just a transposition? Surface yes; deep no. Both share the cheap core (simple consistency). A pays extra (ω‑consistency) to make G unrefutable/undecidable; C doesn't — ω‑incompleteness is the cheaper, more primitive fact.
Where does ω‑consistency "live"? It forbids the pathological branch of ω‑incompleteness (∀vF refutable while all F(m̄) provable). Exercise 9 exhibits that branch.

Self‑Test

Q1. In Prop 1's bounded‑∀ true case, exactly one hypothesis beyond pure logic is used. Which, and at which step?

answerC₂, at step A5 — assembling (∀w≤n̄)F(w) from proofs of all its instances. Everything else is IH + semantics + generalization.

Q2. Why does the whole method stop at Σ₀ and fail one quantifier up?

answerThe syncing facts exist only for ~, ⊃ (free, via tautologies) and the bounded ∀ (C₂). There is no C₂‑analogue for the unbounded ∀ — you'd have to bundle infinitely many instances into one theorem, which is exactly what fails. Gödel's true‑unprovable G escapes through that crack.

Q3. In Prop 3, which half of the biconditional Ω₄ backs D₁, and which backs D₃?

answer⟸ half backs D₁'s ≤‑case (from v₁=k̄ conclude v₁≤n̄); ⊃ half backs D₃ (from v₁≤n̄ conclude the disjunction).

Q4. In the Ω₃ successor‑peeling, what does N₂ do and what does N₁ do?

answerN₂ (0≠v₁') plants the base difference 0̄≠d̄; the contrapositive of N₁ (v₁≠v₂ ⊃ v₁'≠v₂') lifts a known inequality up by one prime on both sides, carrying 0̄≠d̄ to m̄≠(m+d)‾.

Q5. State the single fact that both Theorem A and Theorem C rest on, and the one extra thing A needs.

answerShared cheap core (from simple consistency): G is unprovable and every instance ~A(h̄,m̄) is provable. A additionally needs ω‑consistency, solely to make G unrefutable (hence undecidable). C needs nothing more.

Q6. Why is P.A.+{~G} consistent, and why is it ω‑inconsistent?

answerConsistent because T+{~σ} is consistent iff T⊬σ, and P.A.⊬G. ω‑inconsistent because it proves ∃v₂A(h̄,v₂) (the new axiom ~G) while it inherits P.A.'s proofs of every ~A(h̄,m̄) — the exact shape of ω‑inconsistency.


Results imported into this session and where they were established:

Imported result Used in Source
Theorem A (axiomatizable + ω‑consistent + all‑true‑Σ₀‑provable ⇒ incomplete); Theorem A* Parts VIII, and the A‑vs‑C table Ch. V Part I — 2026‑07‑30
Theorem 3 (Gödel G; two‑strength split: unprovable←simple, unrefutable←ω) Parts VII (4,5), VIII (1), IX (1) 2026‑07‑30
Lemma 1 (diagonal: G provable ⟺ h∈P*); Lemma ω Part VII (3) 2026‑07‑30
enumerates vs represents vs expresses; ω‑consistent / ω‑inconsistent / simply consistent defs; axiomatizable = formal = r.e. Parts VII (2a), VIII, IX Ch. V prelude — 2026‑07‑29
P is Σ₁ (provability predicate ∃y Pf(y,x), Pf recursive); Theorem D (witness bounding); Prop C (Σ₁ closure incl. recursive substitution) Part VII (2b, 2c) Ch. IV "More on Σ₁" — 2026‑07‑28
Arithmetization: Pf, Seq, the syntactic predicates; Num = Pow₁₃ Part VII (2b) Ch. III arithmetization — 2026‑07‑26
Theorem E (x^y=z is Σ₁), exponential‑free coding Part 0/I analogy (meta‑induction vs exponentials) Ch. IV — 2026‑07‑27

Book page span for this session: Smullyan, Gödel's Incompleteness Theorems, Ch. V §II, pp. 66–74 (§3 Prop 1–2; §4 systems (Q),(Q₀),(R),(R₀) + Prop 3–5, Theorem B*; §5 wrap‑up; §6 Theorem C + Exercises 9–12).


What's ahead

Chapter V is complete: Part I (abstract theorems A, A*, 1–3, Lemmas 1/ω — session 07‑30), the ω‑consistency prelude (07‑29), and now Part II (Σ₀‑completeness → Theorem B → Theorem G, plus Theorem C and Exercise 9). Gödel's First Theorem for P.A. and its ω‑incompleteness refinement are fully in hand.

Outstanding threads to pick up next: - §6 exercises 10–12 — the P(X̄) provability predicate: every Σ₀ (Ex 10) and Σ₁ (Ex 11) sentence X has X ⊃ P(X̄) provable, but not every sentence (Ex 12). Ex 11's full Σ₁ case is deferred by Smullyan to Boolos [1979] — the Σ₁‑completeness debt (owed since 07‑28) is only partially paid by Theorem B (Σ₀), and stays open at Σ₁. - Chapter 9 (later) — Gödel's Second Theorem: why the informal proof that "G is true" is not formalizable in P.A. - Exercise 8 ((R′) recovers all of (R) from the weaker Ω₄′).

Prior session files: 07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 (this file).