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
- Part 0 — The opening blocker: three different "inductions"
- Part I — GOAL and the reduction chain
- Part II — Citable glossary
- Part III — Proposition 1: C₁ & C₂ ⟹ Σ₀‑complete (induction on degree)
- Part IV — Proposition 2: D₁ & D₂ & D₃ ⟹ C₁ & C₂
- Part V — Proposition 3: (R₀) is Σ₀‑complete (+ the Ω₄ subtlety)
- Part VI — Proposition 4/5: the embedding, and Theorem B*
- Part VII — Closing Theorem G
- Part VIII — Theorem C: the ω‑Incompleteness Theorem (the one mathematicians miss)
- Part IX — Exercise 9: a system consistent but not ω‑consistent
- Distinctions Ledger
- Self‑Test
- References & cross‑links
- What's ahead
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̄=0followed bykprimes;(k+1)‾ = k̄'. Compound(m+n)‾= numeral of the numberm+n. - atomic Σ₀‑sentence —
t₁ = t₂ort₁ ≤ t₂, closed terms; after evaluating closed terms to numerals, reduces tom̄ = n̄orm̄ ≤ n̄. - degree — count of
~,⊃, bounded∀in the formula; atomic ⟹ degree 0. In(∀w ≤ n̄)F(w), the bodyFhas degree one lower; numeral substitution for a variable adds no logical symbol, sodeg 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=0N₆v₁·v₂'=(v₁·v₂)+v₁N₇v₁≤0 ≡ v₁=0N₈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?
answer
C₂, 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?
answer
The 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?
answer
N₂ (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.
answer
Shared 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?
answer
Consistent 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.
References & cross‑links
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).
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
第五章第二部分:Σ₀完备性,第66–74页——完成定理G,以及ω不完备定理C
这次学习完成前两次第五章学习所开启的路线:7月30日第一部分的抽象定理,以及7月29日的ω一致性前奏。我们证明了定理B,所有真的Σ₀句子均可证,事实上在极小的系统(R₀)、(Q₀)中就可证,这是定理G,P.A.的哥德尔定理,最后一根支柱;然后提取出定理C,那个“大多数数学家都忽略了”的ω不完备定理。
下面的阅读顺序依理解实际建立的顺序,先处理阻碍,而不依书中顺序。
第零部分——开头的阻碍:三种不同的“归纳”
证明不断说“通过归纳”,而读者隐约记得此前P.A.学习中的一个归纳公理。理清这一点是打开本章的钥匙。
| # | 出现位置 | 对什么归纳 | 是P.A.公理吗? |
|---|---|---|---|
| (I) | 命题1的证明,第66–67页 | Σ₀句子的度,即逻辑复杂度 | 不是,是元理论中的普通归纳 |
| (II) | (R₀)⊆(Q₀)的证明,第70–71页 | 数n,证明数码事实 |
不是,是元归纳;对象公理N₃–N₈提供基础与递推步骤 |
| (III) | 构建(Q)时被删去的模式 | P.A.的归纳模式 | 是,读者记得的就是它 |
整节的关键: Σ₀完备性从不使用(III)。它在有限系统(Q₀),即P.A.减去归纳,以及更弱的(R₀)中仍然成立。命题1中的“归纳假设”是(I):元理论中假设每个更低度的Σ₀句子都已经可正确判定。
第一部分——目标与归约链
目标。 证明定理B:所有真的Σ₀句子都在P.A.中可证,事实上在(R₀)、(R)、(Q₀)、(Q)中就可证。此前的路线需要它把“S枚举P*”变成可用的对象;定理A+B⟹定理G。
归约流程:
命题1:C₁ & C₂ ⟹ Σ₀完备 (对度作元归纳)
命题2:D₁ & D₂ & D₃ ⟹ C₁ & C₂
命题3:(R₀)满足D₁,D₂,D₃ ⟹ (R₀)为Σ₀完备
命题4/5:(R₀)⊆(Q₀)⊆(Q)⊆P.A.,(R₀)⊆(R) (通过N₁–N₉对n作元归纳)
⟹ 定理B*:(R₀)、(R)、(Q₀)、(Q)、P.A.均为Σ₀完备
第二部分——可供引用的术语表
- 数码
k̄=0后接k个撇号;(k+1)‾ = k̄'。复合记号(m+n)‾=数m+n的数码。 - 原子Σ₀句子,
t₁ = t₂或t₁ ≤ t₂,其中是闭项;把闭项求值为数码后,归约为m̄ = n̄或m̄ ≤ n̄。 - 度,公式中
~、⊃、有界∀的个数;原子式⟹度为0。在(∀w ≤ n̄)F(w)中,主体F的度低一;用数码替换变量不增加逻辑符号,因此deg F(m̄) = deg F(w)。 - 在S中可反驳,
S ⊢ ~X。 - 在S中可正确判定,corr‑dec,
(X为真 ∧ S⊢X) ∨ (X为假 ∧ S⊢~X)。元理论中的桥梁谓词,不是S内部的性质。 - Σ₀完备,每个真的Σ₀句子都可证,弱于所有Σ₀句子均可正确判定,而归纳实际给出的是后者。
- C₁,每个原子Σ₀句子均可正确判定。C₂,若
F(0̄),…,F(n̄)全部可证,则(∀w≤n̄)F(w)可证。 - D₁,真的原子Σ₀句子可证。D₂,
m≠n ⟹ S⊢ m̄≠n̄。D₃,S ⊢ w ≤ n̄ ⊃ (w=0̄∨…∨w=n̄)。 - (Q₀)=N₁–N₈,有限;(Q)添加N₉;P.A.添加归纳模式:
- N₁
v₁'=v₂' ⊃ v₁=v₂N₂0≠v₁'N₃v₁+0=v₁N₄v₁+v₂'=(v₁+v₂)' - N₅
v₁·0=0N₆v₁·v₂'=(v₁·v₂)+v₁N₇v₁≤0 ≡ v₁=0N₈v₁≤v₂' ≡ (v₁≤v₂ ∨ v₁=v₂') - N₉
v₁≤v₂ ∨ v₂≤v₁,线性,属于(Q),不属于(Q₀) - (R₀)=Ω₁–Ω₄,(R)添加Ω₅:
- Ω₁
m̄+n̄=k̄,其中m+n=k;Ω₂m̄·n̄=k̄,其中m·n=k;Ω₃m̄≠n̄,其中m≠n - Ω₄
v₁≤n̄ ≡ (v₁=0̄∨…∨v₁=n̄),是双条件式,见第五部分;Ω₅v₁≤n̄ ∨ n̄≤v₁
第三部分——命题1:C₁ & C₂ ⟹ Σ₀完备,对度归纳
任务。 对度作归纳,证明更强的主张“每个Σ₀句子均可正确判定”;Σ₀完备性是其中“真”的一半。
基础,原子式,度为0: 由C₁可正确判定。
~X步骤,归纳假设IH:X可正确判定:
~X是… |
X是… |
IH给出 | 结果 | 如何得到 |
|---|---|---|---|---|
| 真 | 假 | S ⊢ ~X |
~X可证 |
S⊢~X就是“~X可证”,依据定义 |
| 假 | 真 | S ⊢ X |
~X可反驳 |
逻辑X ⊃ ~~X |
X ⊃ Y步骤,IH:X、Y可正确判定:
X⊃Y是… |
真值表理由 | IH给出 | 结果 | 重言式 |
|---|---|---|---|---|
| 真 | X为假 |
S⊢~X |
可证 | ~X ⊃ (X⊃Y) |
| 真 | Y为真 |
S⊢Y |
可证 | Y ⊃ (X⊃Y) |
| 假 | X真∧Y假 |
S⊢X、S⊢~Y |
可反驳 | (X ∧ ~Y) ⊃ ~(X⊃Y) |
(∀w ≤ n̄)F(w)步骤,唯一需要非逻辑输入的情形。IH:每个F(k̄),k≤n,均可正确判定。
情形A,为真:
| 步骤 | 主张 | 理由 |
|---|---|---|
| A1 | 每个F(0̄),…,F(n̄)都为真 |
有界∀的真理递归 |
| A2 | 每个F(k̄)都是更低度的句子 |
主体少一个有界∀;数码不增加逻辑符号 |
| A3 | ∴每个F(k̄)可正确判定 |
IH |
| A4 | ∴每个F(k̄)可证 |
A3,可正确判定,+A1,真 |
| A5 | (∀w≤n̄)F(w)可证 |
将C₂用于A4 |
情形B,为假:
| 步骤 | 主张 | 理由 |
|---|---|---|
| B1 | 存在m≤n使F(m̄)为假 |
真理递归 |
| B2 | F(m̄)是更低度的句子 |
同A2 |
| B3 | ∴F(m̄)可正确判定 |
IH |
| B4 | S ⊢ ~F(m̄) |
B3+B1 |
| B5 | S ⊢ m̄ ≤ n̄ |
原子式→C₁,由于m≤n为真 |
| B6 | S ⊢ ~(m̄≤n̄ ⊃ F(m̄)),该实例可反驳 |
将B5、B4送入重言式(A∧~B)⊃~(A⊃B) |
| B7 | S ⊢ (∀w≤n̄)F(w) ⊃ (m̄≤n̄ ⊃ F(m̄)) |
逻辑有效,整体⊃其实例 |
| B8 | S ⊢ ~(∀w≤n̄)F(w),整体可反驳 |
否定后件式:B7+B6 |
对度的有限、良基阶梯⟹每个Σ₀句子可正确判定。∎
分工,即要点: C₁=基础;纯逻辑免费处理~与⊃;C₂恰好只在一个阶梯上使用,即A5,从实例组装有界全称句。有意不为无界∀设置阶梯;真理与可证性正是在那里分道扬镳,哥德尔句G在那里逃脱。
本次学习获得的两项概念成果
(1)为什么不变量是可正确判定,而非“真⟹可证”。 ~X情形需要另一方向,即“X假⟹X可反驳”,所以单向不变量不能在否定下保持。两个方向合起来=可正确判定。不变量是特意设计出来的。
(2)真理外在于字符串时,它如何“传播”。 它不在S内部传播。整个归纳是元理论的。真理沿着塔斯基递归前进,即我们执行的组合式计算;可证性沿着C₁/C₂前进,即关于S的事实。归纳使这两种外部计算在各个度上保持同步。不发生偏移的保证来自S中的经典逻辑是布尔完备的:真值表的每一行都有一个可证重言式见证,因此“部分的判定⟹整体的判定”这一映射是全定义的,没有复合式能变得“沉默”。一般说来,真理与可证性确实会分离,那就是不完备性;命题1表明它们只在Σ₀上被迫一致,恰恰因为Σ₀在那些具有同步事实的操作下封闭:~、⊃免费,有界∀由C₂补上。
(3)IH与C₁之间没有循环。 归纳证明一个条件句:假设严格更低的度上可正确判定,推出当前的度上也如此。没有对象的状态证明它自己的状态。C₁建立底层,即原子式;IH是当前度以下累积的结果,已经把C₁的输出包含为其度为0的层次。因此一般的~X/X⊃Y步骤引用IH,它包含C₁;只有子公式本身是原子式时,才直接是C₁。
第四部分——命题2:D₁ & D₂ & D₃ ⟹ C₁ & C₂
把C₁、C₂重新包装为可检查的条件。注意不对称性:D₃单独⟹C₂;三个合起来⟹C₁。
第一部分,C₁,真原子式由D₁;假原子式可反驳:
| 原子式 | 状态 | 需证明 | 如何得到 |
|---|---|---|---|
| 任意真原子式 | 真 | 可证 | D₁ |
m̄=n̄,假,m≠n |
假 | S⊢~(m̄=n̄) |
D₂:m̄≠n̄就是~(m̄=n̄) |
m̄≤n̄,假,m>n |
假 | S⊢~(m̄≤n̄) |
下面的链条↓ |
m̄≤n̄为假的链条:
| # | 主张 | 理由 |
|---|---|---|
| 1 | S ⊢ m̄≤n̄ ⊃ (m̄=0̄∨…∨m̄=n̄) |
D₃取w:=m̄ |
| 2 | 每个k≤n:S ⊢ ~(m̄=k̄) |
m>n≥k所以m≠k;D₂ |
| 3 | S ⊢ ~(m̄=0̄∨…∨m̄=n̄) |
对2用德摩根律 |
| 4 | S ⊢ ~(m̄≤n̄) |
对1、3用否定后件式 |
复合闭项先通过D₁化为数码,因为m̄+n̄=(m+n)‾是一个真的原子式;因此归约到两种形状不失一般性。
第二部分,由D₃得到C₂。 假设S⊢F(0̄),…,S⊢F(n̄):
| # | 主张 | 理由 |
|---|---|---|
| 1 | S ⊢ w≤n̄ ⊃ (w=0̄∨…∨w=n̄) |
D₃ |
| 2 | 每个k≤n:S ⊢ w=k̄ ⊃ F(w) |
等号替换:w=k̄ ⊃ (F(k̄)⊃F(w))有效,与S⊢F(k̄)接续 |
| 3 | S ⊢ w≤n̄ ⊃ F(w) |
对1+2用∨消去,分情况证明 |
| 4 | S ⊢ ∀w(w≤n̄ ⊃ F(w)) |
全称化规则,w自由,没有未解除的假设 |
| 5 | S ⊢ (∀w≤n̄)F(w) |
那个公式按定义就是有界∀ |
D条件⟹C条件;由命题1,S是Σ₀完备的。∎
第五部分——命题3:(R₀)是Σ₀完备的,以及Ω₄的细节
Ω₄是双条件式≡,不是⊃。 练习8确认了这一点,它把单向⊃版本命名为Ω₄′,并称之为更弱。这一区分承担实质作用:
- D₃使用Ω₄的⊃一半。
- D₁的≤情形使用⟸一半。
证明。 验证D₁、D₂、D₃,然后用命题2。其中两个直接就是公理:
| 条件 | 由什么满足 |
|---|---|
| D₂ | 模式Ω₃,逐字相同 |
| D₃ | Ω₄的⊃一半,将v₁全称化,再实例化为任意w |
D₁,真原子式,四种形状:
| 真原子式 | 条件 | 如何可证 |
|---|---|---|
m̄=n̄ |
m=n |
带等号的一阶逻辑,它就是n̄=n̄ |
m̄+n̄=k̄ |
m+n=k |
Ω₁ |
m̄·n̄=k̄ |
m·n=k |
Ω₂ |
m̄≤n̄ |
m≤n |
下面的链条↓,Ω₄的⟸一半 |
≤情形: S⊢ m̄≤n̄ ≡ (m̄=0̄∨…∨m̄=n̄),由Ω₄;由于m≤n,S⊢ m̄=m̄,等号同一律,是其中一个析取项;所以析取式可证;⟸一半给出S⊢ m̄≤n̄。∎
设计洞见: 双条件式Ω₄分担职责:⊃一半服务于D₃,“是≤n̄就必须是0̄…n̄之一”;⟸一半服务于D₁,“是0̄…n̄之一就必须是≤n̄”。(R₀)极小,因为D₂与D₃的一半逐字就是它的公理。
第六部分——命题4/5:嵌入,以及定理B*
对象事实,在没有归纳公理的系统中,通过对n作元归纳来证明。 每个n都从N₁–N₈产生一个单独的有限(Q₀)证明;(Q₀)证明每个实例,却不能把它们捆绑为一个∀定理,这恰恰是ω不完备性的间隙。
命题4——(R₀)⊆(Q₀):每个Ω模式都是(Q₀)定理
Ω₁,m̄+n̄=(m+n)‾,对n归纳:
| 实例 | 如何得到 | |
|---|---|---|
基础n=0 |
m̄+0̄=m̄=(m+0)‾ |
N₃ |
| 步骤 | m̄+(n+1)‾=(m+n+1)‾ |
m̄+n̄' =,N₄,(m̄+n̄)' =,IH,(m+n)‾' =(m+n+1)‾ |
Ω₂,m̄·n̄=(m·n)‾,对n归纳:
| 实例 | 如何得到 | |
|---|---|---|
基础n=0 |
m̄·0̄=0̄=(m·0)‾ |
N₅ |
| 步骤 | m̄·(n+1)‾=(m(n+1))‾ |
m̄·n̄' =,N₆,(m̄·n̄)+m̄ =,IH,(m·n)‾+m̄ =,Ω₁,(m·n+m)‾ |
Ω₃,m̄≠n̄,其中m≠n,逐层剥去后继。不失一般性取m<n,差d=n−m>0;对j归纳证明j̄≠(j+d)‾:
| 实例 | 如何得到 | |
|---|---|---|
基础j=0 |
0̄≠d̄ |
d̄=(d−1)‾',所以就是0≠(·)',N₂ |
| 步骤 | (j+1)‾≠(j+1+d)‾ |
N₁的逆否命题,v₁≠v₂ ⊃ v₁'≠v₂':给IH两侧加撇号 |
m̄≠n̄=取j=m, d=n−m的实例。N₂在0处种下差异;N₁把它向上传递。
Ω₄,v₁≤n̄ ≡ (v₁=0̄∨…∨v₁=n̄),对n归纳:
| 实例 | 如何得到 | |
|---|---|---|
基础n=0 |
v₁≤0̄ ≡ v₁=0̄ |
N₇,已经是≡ |
| 步骤 | v₁≤(n+1)‾ ≡ (…∨v₁=(n+1)‾) |
N₈,v₁≤n̄' ≡ (v₁≤n̄ ∨ v₁=n̄');用IH替换v₁≤n̄ |
由于N₇、N₈本身就是双条件式,归纳免费传递完整的≡,书中只强调⊃方向。∎⟹(R₀)⊆(Q₀)。
命题5——(R)⊆(Q)
Ω₅,v₁≤n̄ ∨ n̄≤v₁,=N₉取v₂:=n̄的实例;结合(R₀)⊆(Q₀)⊆(Q)。∎
定理B*
每个系统都是(R₀)的扩张系统:(R₀)⊆(Q₀)⊆(Q)⊆P.A.且(R₀)⊆(R)⊆(Q)。扩张系统证明其子系统能证明的一切;(R₀)证明所有真的Σ₀句子,命题3,所以:
定理B*。 (R₀)、(R)、(Q₀)、(Q)、P.A.均为Σ₀完备。∎
这就是定理B。结合定理A,定理G,即P.A.的哥德尔定理,完成了。
并列比较两种元归纳:
| 命题1 | 命题4 | |
|---|---|---|
| 归纳对象 | 公式的度 | 数n |
| 不变量 | 可正确判定,真理↔可证性的桥梁 | “这个数码等式是(Q₀)定理” |
| 对象层提供 | C₁、C₂ | N₁–N₈,每一阶一个公理 |
| 对象理论自己的归纳 | 没有 | 没有 |
两者都不是P.A.的归纳模式;两者都是普通数学从外部对弱系统进行推理。
第七部分——完成定理G
| 步骤 | 主张 | 理由 |
|---|---|---|
| 步骤 | 主张 | 理由 |
| --- | --- | --- |
| 1 | 所有真的Σ₀句子都在P.A.中可证 | 定理B |
| 2 | P*在P.A.中被一个Σ₀公式A(v₁,v₂)枚举 |
下面的子链2a–2d |
| 3 | G := ∀v₂~A(h̄,v₂),h=∀v₂~A(v₁,v₂)的哥德尔编号;由P*的定义,G可证⟺h∈P* |
对角化,引理1 |
| 4 | G不可证,只需简单一致性 |
定理3,成本较低的一半 |
| 5 | G不可反驳,需要ω一致性 |
定理3,成本较高的一半 |
| 6 | G不可判定⟹P.A.不完备 |
4+5 |
| — | G为真 |
G不可证⟹h∉P*⟹每个~A(h̄,m̄)为真⟹∀v₂~A(h̄,v₂)为真 |
展开步骤2——“可公理化+定理B”如何产生Σ₀枚举公式A
原先的一行理由既有错误,应该是Σ₁而非Σ₀,又过于压缩。真正的推导有两个独立成分,最后才汇合。回忆7月29日前奏的词汇:集合被一个公式枚举,条件1是成员使某个实例可证,条件2是非成员使每个实例可反驳;这弱于表示,即⟺可证,而且只需定理B,不需ω一致性。
| # | 主张 | 理由 |
|---|---|---|
| 2a | 定理B⟹每个Σ₁集合都在P.A.中被一个Σ₀公式枚举。 对Σ₁集合X = {n : ∃m R(n,m)},其中R为Σ₀:若n∈X,某个R(n̄,m̄)是真的Σ₀句子,故可证,条件1✓;若n∉X,每个~R(n̄,m̄)都是真的Σ₀句子,故可证,条件2✓。 |
把定理B,Σ₀完备性,逐实例应用于Σ₀矩阵R |
| 2b | P,P.A.可证句子的哥德尔数集合,是Σ₁。 |
P.A.可公理化=形式的=递归可枚举;可证性谓词为∃y Pf(y,x),其中Pf,“y编码了x的一个证明”,是递归的;见7月28日/7月26日的算术化,由定理D给出界限 |
| 2c | P*为Σ₁。 P* = {n : E_n(n̄)可证} = d⁻¹(P),其中d(n)=E_n(n̄)的哥德尔编号,是递归的代入函数。 |
Σ₁集合,2b,在递归函数下的原像为Σ₁;Σ₁对递归代入封闭,见7月28日命题C |
| 2d | ∴P*在P.A.中被一个Σ₀公式A(v₁,v₂)枚举。 |
把2c,P*为Σ₁,送入2a,每个Σ₁集合都可被Σ₀公式枚举 |
所以链条是:可公理化使P以及对角集合P*成为Σ₁,2b、2c;定理B使每个Σ₁集合可被Σ₀公式枚举,2a;两者结合给出枚举公式A,2d。注意分工与此前路线对应:步骤2只需枚举,单靠定理B;跳到表示,让G变得不可判定,才在后面使用ω一致性,步骤4–5,通过定理3。
所以P.A.留下一个真的句子不可证;我们知道它是真的,尽管这项论证不能在P.A.中形式化,见第九章第二定理。
第八部分——定理C:ω不完备定理,数学家忽略的那个定理
现象: 存在公式F(v₂),使P.A.证明每个数值实例F(0̄), F(1̄), F(2̄), …,却不能证明∀v₂F(v₂)。直觉上比“某个句子不可判定”更令人震惊:P.A.似乎“知道”每个数都有F,却不能推出全称句。
见证就是哥德尔句本身,换个方向阅读。设置:A枚举P*;条件1:n∈P* ⟹ ∃m [S⊢A(n̄,m̄)];条件2:n∉P* ⟹ ∀m [S⊢~A(n̄,m̄)]。
| # | 主张 | 理由 |
|---|---|---|
| 1 | G=∀v₂~A(h̄,v₂)不可证 |
简单一致性,定理3成本较低的一半:若G可证,则h∈P*,条件1给出某个A(h̄,m̄)可证,但G可证⟹~A(h̄,m̄)可证⟹不一致 |
| 2 | h ∉ P* |
“G可证⟺h∈P*”的逆否命题,结合(1) |
| 3 | 每个~A(h̄,m̄)可证,m=0,1,2,… |
由(2)用条件2 |
| 4 | ∀v₂~A(h̄,v₂)不可证 |
=(1) |
| 5 | F(v₂):=~A(h̄,v₂):所有F(m̄)可证,(3);∀v₂F(v₂)不可证,(4) |
按定义是ω不完备 |
定理C。 任何简单一致、可公理化、并且所有真的Σ₀句子都可证的系统,都是ω不完备的。
定理A与定理C——拆开这次“换位”
表面上看:在假设中交换ω一致↔简单一致,在结论中交换不完备↔ω不完备。但这不是对称的对偶,而存在成本不对称:
| 定理A,不完备性 | 定理C,ω不完备性 | |
|---|---|---|
| 假设 | 可公理化+所有真的Σ₀可证+ω一致 | 相同条件+简单一致 |
| 结论 | 存在不可判定句G |
存在F:所有F(m̄)可证,∀vF不可证 |
关于G证明了什么 |
不可证,简单一致,且不可反驳,ω一致 | 不可证,简单一致;实例可证,h∉P* |
| ω一致性用于 | 使G不可反驳 |
没有用途,不需要 |
真正的区别。 两者都依靠同一个低成本核心:仅由简单一致性,得到G不可证且所有实例~A(h̄,m̄)可证。不完备性随后付出额外代价,即ω一致性,也封闭可反驳的可能,使G不可判定。ω不完备性跳过这笔支付,直接读取实例与全称之间的间隙。因此,ω不完备性是更原初、成本更低的事实;不完备性则是加上ω一致性之后买到的东西。
为什么两个概念确实分离。 系统可以以两种方式ω不完备:
- 良性的,ω一致: ∀vF不可判定,即哥德尔不完备性。
- 病态的,ω不一致: ∀vF可反驳,而所有F(m̄)可证,见下面练习9。
ω一致性恰好是禁止病态分支的假设,即禁止在所有F(m̄)可证的同时证明∃v~F(v)。因此它是定理A需要而定理C不需要的额外成分。
第九部分——练习9:一个一致但不ω一致的系统
任务。 假设P.A.一致,构造P.A. + {~G},把哥德尔句的否定作为新公理加入。证明它简单一致却ω不一致。这是具体的“简单一致但ω不一致”例子,即第八部分的病态分支,也是证明两个概念不同的标准方法。7月29日前奏中的定义:简单一致=没有句子既可证又可反驳;ω不一致=存在公式B(v),∃v B(v)可证,但每个B(m̄)可反驳。
| # | 主张 | 理由 |
|---|---|---|
| 1 | P.A. ⊬ G |
P.A.简单一致⟹定理3成本较低的一半,即第八部分步骤1,给出G不可证 |
| 2 | P.A.+{~G}简单一致 |
元定理:T+{~σ}一致⟺T ⊬ σ。取σ = G、T = P.A.,使用(1)。 |
| 3 | 对每个m = 0,1,2,…,P.A.+{~G} ⊢ ~A(h̄,m̄) |
每个~A(h̄,m̄)已经是P.A.定理,第八部分步骤1–3:G不可证⟹h∉P*⟹条件2;而增加公理只会增加定理 |
| 4 | P.A.+{~G} ⊢ ∃v₂ A(h̄,v₂) |
新公理~G就是~∀v₂~A(h̄,v₂),逻辑上等价于∃v₂ A(h̄,v₂) |
| 5 | P.A.+{~G}ω不一致 |
取B(v₂) := A(h̄,v₂):(4)给出∃v₂ B(v₂)可证,(3)给出每个B(m̄)可反驳,恰好符合定义 |
| 6 | 简单一致+ω不一致 | (2)+(5),所需例子 |
为什么步骤2的元定理成立,这是唯一不明显的引理。如果T+{~σ}不一致,它就证明一切,因此T + {~σ} ⊢ σ;由演绎定理,T ⊢ (~σ ⊃ σ),而(~σ ⊃ σ) ⊃ σ是重言式,所以T ⊢ σ。逆否命题:T ⊬ σ ⟹ T+{~σ}一致。反向,T⊢σ ⟹ T+{~σ}不一致,显然成立。因此扩张的一致性等价于G不可证,而这恰是P.A.的简单一致性在(1)中买到的。
为什么这是第八部分的病态分支。 在P.A.+{~G}中,ω不完备性的见证F(v₂)=~A(h̄,v₂)具有全部实例F(m̄)可证,(3),但∀v₂F(v₂) = G不只是不可证,而是明确可反驳,它的否定~G就是公理。对比两个分支:
∀vF,即G,的状态 |
哪个定理 | |
|---|---|---|
| P.A.自身,ω一致 | 不可判定,不可证且不可反驳 | 定理A:不完备性 |
P.A.+{~G},ω不一致 |
可反驳,而所有F(m̄)可证 |
练习9:ω不一致性 |
因此P.A.+{~G}是具有可反驳见证的ω不完备系统,而它在G处并不不完备,G在此可判定,即被反驳。这恰好展示ω不完备性如何与不完备性分离:去掉ω一致性,便允许全称句∀vF假而可反驳,即使每个实例都可证。
区分清单
| 提出的困惑 | 一行解答 |
|---|---|
| “归纳假设是哪条公理?” | 不是公理,而是元理论归纳,对度或n归纳;P.A.的归纳模式是(Q₀)去掉的那个。 |
| 元归纳与幂运算的情形 | 两者都让对象系统保持贫乏,而元理论自由推理;但幂运算限制可表达性,可通过Σ₁关系恢复;归纳限制全称句的可证性,不能恢复,那个间隙就是ω不完备性。 |
| “归纳如何传递外在的真理?” | 它不通过S传递真理;整个归纳是外部的,真理沿塔斯基递归,可证性沿C₁/C₂,依度保持同步。 |
| 为什么不变量是双向的可正确判定,而非“真⟹可证”? | ~情形需要反方向;单向不变量在否定下不保持。 |
| 为什么两台“机器”在复合式处不会偏离? | S中的经典逻辑是布尔完备的:真值表每一行都有可证重言式见证,因此“部分的判定⟹整体的判定”是全定义的,没有沉默的复合式。 |
| “X假⟹S⊢~X”来自C₁还是IH?使用IH不是循环吗? | 一般来自IH,只有X是原子式才来自C₁。不循环:IH量化遍及严格更低的度,并且已包含C₁的底层;基础直接证明。 |
Ω₄是⊃还是≡? |
≡,双条件式。练习8把⊃版本命名为Ω₄′,称之为更弱。D₃用⊃一半,D₁的≤情形用⟸一半。 |
| 命题1的B5/B6中,可反驳的“实例”是什么意思? | 实例Q=(m̄≤n̄⊃F(m̄))可反驳,前件可证,后件的否定可证,对应⊃唯一为假的一行;然后P⊃Q有效+~Q,由否定后件式得到~P。 |
| 定理A与定理C只是换位吗? | 表面是,深层不是。两者共享低成本核心,即简单一致性。A额外付出ω一致性,使G不可反驳/不可判定;C不付出,ω不完备性是更低成本、更原初的事实。 |
| ω一致性“位于”何处? | 它禁止ω不完备性的病态分支,即∀vF可反驳而所有F(m̄)可证。练习9展示了这个分支。 |
自测
问题1。 命题1的有界∀为真情形中,恰好使用一个超出纯逻辑的假设。是哪一个,在哪一步?
答案
C₂,在A5步骤,从所有实例的证明组装(∀w≤n̄)F(w)。其余都是IH+语义+全称化。
问题2。 为什么整个方法停在Σ₀,再上升一个量词就失败?
答案
同步事实只存在于~、⊃,通过重言式免费获得,以及有界∀,C₂。对于无界∀没有C₂的对应物,你得把无限多个实例捆成一个定理,而这恰是会失败的地方。哥德尔的真而不可证句G通过这条裂隙逃脱。
问题3。 命题3中,双条件式Ω₄的哪一半支持D₁,哪一半支持D₃?
答案
⟸一半支持D₁的≤情形,从v₁=k̄推出v₁≤n̄;⊃一半支持D₃,从v₁≤n̄推出析取式。
问题4。 在Ω₃逐层剥去后继的证明中,N₂做什么,N₁做什么?
答案
N₂,0≠v₁',种下基础差异0̄≠d̄;N₁的逆否命题,v₁≠v₂ ⊃ v₁'≠v₂',通过两侧各加一个撇号把已知不等式提升,将0̄≠d̄传递为m̄≠(m+d)‾。
问题5。 陈述定理A与定理C共同依靠的单一事实,以及A额外需要的那一项。
答案
来自简单一致性的共同低成本核心:G不可证,且每个实例~A(h̄,m̄)可证。A额外需要ω一致性,仅用来使G不可反驳,从而不可判定。C不需要更多。
问题6。 为什么P.A.+{~G}一致,又为什么它ω不一致?
答案
一致,因为T+{~σ}一致当且仅当T⊬σ,而P.A.⊬G。ω不一致,因为它证明∃v₂A(h̄,v₂),即新公理~G,同时继承P.A.对每个~A(h̄,m̄)的证明,这恰好是ω不一致的形状。
参考与交叉链接
本次学习引入的结果,以及它们建立的位置:
| 引入结果 | 使用位置 | 来源 |
|---|---|---|
| 定理A,可公理化+ω一致+所有真的Σ₀可证⇒不完备;定理A* | 第八部分,以及A与C比较表 | 第五章第一部分——2026‑07‑30 |
定理3,哥德尔句G;两种强度分离,不可证←简单一致,不可反驳←ω一致 |
第七部分4、5,第八部分1,第九部分1 | 2026‑07‑30 |
引理1,对角化:G可证⟺h∈P*;引理ω |
第七部分3 | 2026‑07‑30 |
| 枚举、表示、表达的区别;ω一致/ω不一致/简单一致的定义;可公理化=形式的=递归可枚举 | 第七部分2a,第八、九部分 | 第五章前奏——2026‑07‑29 |
P为Σ₁,可证性谓词∃y Pf(y,x),Pf递归;定理D,约束见证;命题C,Σ₁的封闭性,包括递归代入 |
第七部分2b、2c | 第四章“Σ₁的进一步讨论”——2026‑07‑28 |
算术化:Pf、Seq、句法谓词;Num = Pow₁₃ |
第七部分2b | 第三章算术化——2026‑07‑26 |
定理E,x^y=z为Σ₁,不使用幂运算的编码 |
第零/一部分的类比,元归纳与幂运算 | 第四章——2026‑07‑27 |
本次学习的书页范围:Smullyan《哥德尔不完备定理》,第五章§II,第66–74页,§3命题1–2;§4系统(Q)、(Q₀)、(R)、(R₀),加命题3–5、定理B*;§5收束;§6定理C与练习9–12。
后续内容
第五章完成:第一部分,抽象定理A、A*、1–3、引理1/ω,见7月30日记录;ω一致性前奏,见7月29日;以及现在的第二部分,Σ₀完备性→定理B→定理G,再加定理C与练习9。P.A.的哥德尔第一定理及其ω不完备性细化,均已完全掌握。
接下来要处理的未完线索:
- §6练习10–12,P(X̄)可证性谓词:每个Σ₀句子,练习10,及Σ₁句子,练习11,X都有X ⊃ P(X̄)可证,但并非每个句子都如此,练习12。Smullyan把练习11完整的Σ₁情形留给Boolos [1979];自7月28日起待完成的Σ₁完备性事项,只由定理B,即Σ₀,部分完成,Σ₁层次仍未解决。
- 第九章,后续,哥德尔第二定理:为什么“G为真”的非形式证明不能在P.A.中形式化。
- 练习8,(R′)从更弱的Ω₄′恢复整个(R)。