Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter IV Appendix (Exercises 1–8) + Chapter V prelude (ω-consistency)
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 / 篇目
- How this document is organized
- Part I — The toolkit (Ex 1, Ex 3, and their consequences)
- Part II — The applications (Ex 2, 4, 5, 6, 7, 8)
- Part III — Corrections made this session (errors caught, on the record)
- Part IV — Chapter V prelude: the definitions
- Part V — The consistency hierarchy (the spine)
- Part VI — The arc of Chapter V's proof
- Part VII — Simple inconsistency, ω-inconsistency, and the explosion
- Part VIII — Distinctions Ledger
- Part IX — Self-Test
- Part X — Position, owed items, debts
Study session of July 29, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter IV Appendix (Exercises 1–8, with the definition π(x)=13^(x²+x) and Theorem D) and the opening of Chapter V (§ "Gödel's Proof Based on ω-Consistency," book pp. 56–58) · Companion to July 15–28 · Character: a working session — the eight deferred exercises finally worked as justified chains, then the Chapter V setup read and its two hard spots (simple-inconsistency ⟹ ω-inconsistency, and why a contradiction explodes) elucidated. Several tutor errors were caught and corrected against the book's own pages during the session; the versions recorded here are the corrected ones.
Cross-references are clickable: citations like Ex 3, K3, C d, Theorem D jump to the definition or result being invoked.
How this document is organized
Parts I–II are the exercises: the toolkit (Ex 1, Ex 3, and the closure consequences K0–K4) and then the applications (Ex 2, 4, 5, 6, 7, 8). Part III records the four corrections that were made mid-session, so the errors are on file, not just the fixes. Parts IV–VII are the Chapter V prelude: definitions, the consistency hierarchy, the proof arc, and the explosion elucidation. Part VIII is the Distinctions Ledger, IX the Self-Test, X the position and debts.
Notation: plain Unicode; juxtaposition = ∗₁₃ concatenation; digits per the July-21 table (∀→9, etc.).
Part I — The toolkit (Ex 1, Ex 3, and their consequences)
Owned definitions cited throughout (the glossary — link targets for the chains below).
- Σ₀ = bounded quantifiers only (decidable; closed under ¬, ∧, ∨, bounded ∃/∀).
- Σ₁ = ∃y(Σ₀ body); = "Σ-relation" by Prop C₁.
- recursive relation = R and ~R both Σ₁.
- recursive function = f total with recursive graph.
- Prop C closures — the clauses cited as C(a)–(e): (a) Σ₀⇒Σ₁; (b) absorb an unbounded ∃; (c) ∧, ∨; (d) bounded ∃ and bounded ∀; (e) R⊃S with R Σ₀.
- Pow₁₃ = "u is a power of 13," Σ₀ (July 27).
- L(x) = base-13 length, recursive; 13^m has length m+1.
- K₁₁ = codes omitting digit δ (every ♯-free expression).
- Theorem D: if a₁,…,aₖ ∈ K₁₁ are all ≤ x and k ≤ x, then the sequence number δa₁δ…δaₖδ ≤ π(x) = 13^(x²+x).
- Prop 3, Ch. 3 relations (1)–(17) — strings in the July-26 ledger (
...-2026-07-26.md): (5) Seqt, (6) tm, (9) R₂, (10) Seqf, (11) fm, etc.
Exercise 1 — a function with a Σ₁ graph is recursive
Step 1. A function has one value, so "not y" = "some z ≠ y":
f(x̄) ≠ y ⟺ ∃z ( f(x̄)=z ∧ z≠y )
(⟹ f total, has a value z ≠ y; ⟸ if the value z ≠ y then f(x̄) ≠ y). This step uses functionhood + totality.
Step 2. f(x̄)=z Σ₁ (given), z≠y Σ₀ hence Σ₁ (C a), ∧ Σ₁ (C c), ∃z Σ₁ (C b). So f(x̄)≠y is Σ₁.
Step 3. Graph Σ₁ and complement Σ₁ ⟹ graph recursive ⟹ f recursive. ∎
Exercise 3 — bounded search below a recursive bound is recursive
Claim. R(x,y) recursive, f(x) recursive ⟹ Q(x) := (∃y ≤ f(x))R(x,y) recursive.
Step 1. f total with value f(x):
Q(x) ⟺ ∃z ( f(x)=z ∧ (∃y ≤ z)R(x,y) )
~Q(x) ⟺ ∃z ( f(x)=z ∧ (∀y ≤ z)~R(x,y) )
Step 2 (Q Σ₁). f(x)=z Σ₁ (Ex 1); R Σ₁; (∃y≤z)R Σ₁ (C d); ∧ (C c); ∃z (C b).
Step 3 (~Q Σ₁). f(x)=z Σ₁; ~R Σ₁ — available only because R is recursive (a bare Σ₁ relation need not have a Σ₁ complement); (∀y≤z)~R Σ₁ (C d, bounded ∀); ∧ (C c); ∃z (C b).
Step 4. Both Σ₁ ⟹ Q recursive. ∎ (The negative side is the only place "R recursive" beyond "R Σ₁" is spent, and where bounded ∀ (C d) is used.)
Consequences (from Ex 1, Ex 3, Prop C)
| label | property | proof |
|---|---|---|
| K0 | Σ₀ ⟹ recursive | R, ~R both Σ₀ ⟹ both Σ₁ (C a) |
| K1 | recursive closed under ¬ | definition symmetric in R, ~R |
| K2 | recursive closed under ∧, ∨ | R∧S Σ₁ (C c); ~(R∧S)=~R∨~S Σ₁ (C c); ∨ dual |
| K3 | bounded ∃≤x, ∀≤x over a recursive relation ⟹ recursive | Ex 3 with f = identity; ∀ = ¬∃¬ (K1) |
| K4 | g,f recursive functions ⟹ g∘f recursive; g recursive function, A recursive set ⟹ {x: A(g(x))} recursive | graph ∃z(f(x)=z ∧ g(z)=y) Σ₁, total, Ex 1; inverse image via A(g(x))⟺∃z(g(x)=z ∧ A(z)), complement uses ~A |
Part II — The applications (Ex 2, 4, 5, 6, 7, 8)
Exercise 2 — π(x) = 13^(x²+x) is recursive
Step 1. 13^m has length m+1, so 13^(x²+x) is the unique power of 13 of length x²+x+1:
π(x) = y ⟺ Pow₁₃(y) ∧ L(y) = x²+x+1
Step 2. [Pow₁₃](#g-pow13)(y) Σ₀ (K0); [L](#g-len)(y)=x²+x+1 an equation between recursive functions, recursive; ∧ (K2). Graph recursive, so Σ₁.
Step 3. π total with Σ₁ graph ⟹ recursive (Ex 1). ∎ (Alt: exponentiation is recursive — Theorem E gives its Σ₁ graph, Ex 1 upgrades it — and x²+x recursive, so π recursive by composition, K4.)
Exercise 4 — tm(x) is recursive
Owned: tm(x) ⟺ ∃y(Seqt(y) ∧ x∈y) (rel. 6); Seqt Σ₀ (rel. 5), K0.
Step 1. R₁ satisfies R₁(a,b,c) ⟹ c>a, c>b. Prune a formation sequence for E_x to its ancestors, no repeats. The members are sub-terms of E_x, so: ♯-free (∈ K₁₁); ≤ x (x is the largest); ≥ 1 (every term has a positive code — smallest is the numeral 0̄ = 13⁰ = 1); distinct. Distinct positive integers ≤ x number at most x, so k ≤ x (the corrected count — 0 is excluded because it is not a term-code). Theorem D applies: sequence number ≤ π(x). So tm(x) ⟹ (∃y≤π(x))(…).
Step 2. Converse trivial. So tm(x) ⟺ (∃y≤π(x))(Seqt(y) ∧ x∈y).
Step 3. Body Σ₀ (K0); π recursive (Ex 2); Ex 3 ⟹ tm recursive. ∎
Exercise 5 — formula-codes recursive
R₂ (rel. 9) is strictly length-increasing too, so a pruned formation sequence for E_x has members ♯-free, distinct, positive, ≤ x ⟹ k ≤ x. Theorem D ⟹ fm(x) ⟺ (∃y≤π(x))(Seqf(y) ∧ x∈y). Seqf Σ₀ (rel. 10); π recursive (Ex 2); Ex 3 ⟹ fm recursive. ∎
Exercise 6 — relations (1)–(15) all recursive
- Σ₀, so recursive (K0): (1) Sb, (2) Var, (3) Num, (4) R₁, (5) Seqt, (10) Seqf, (13) M.P.
- Theorem D: (6) tm (Ex 4), (11) fm (Ex 5).
- Built up: (7) f₀ [bounded ∃≤x over tm, K3+K2]; (8) Gen [bounded ∃≤y, K3]; (9) R₂ [∨ of recursive, K2]; (12) A [19 disjuncts, each bounded ∃'s over fm/Var/tm, K3+K2]; (14) Der [∨, K2].
- (15) Pf =
Seq(x) ∧ (∀y∈x)(A(y) ∨ (∃z,w ≺ₓ y)Der(z,w,y)). Here≺ₓdoes double duty: it is Σ₀ (only bounded∃w≤zin its definitionx∈z ∧ y∈z ∧ (∃w≤z)(wBz ∧ x∈w ∧ ~y∈w)), andz ≺ₓ ycontainsz∈x, so z ≤ x (a member never exceeds its sequence number). So the inner∃z,ware bounded over a recursive matrix — recursive by K3;A(y)∨(…)by K2; the outer(∀y∈x)is a bounded ∀≤x over recursive — recursive by K3;Seq(x)Σ₀; ∧ by K2. Pf recursive. ∎
Exercise 7 — Fr(x,y) recursive; sentence-codes recursive
Fr(x, y): E_x is a variable, E_y is a formula, and E_x occurs free in E_y. (Variable = first argument x; formula = second argument y.)
Certificate (Ch. 3 Ex. 1 hint). For w = E_x, "w occurs free in a formula" is generated bottom-up: each member of the witnessing sequence is (1) an atomic formula with w a part of it; (2) ~G₁, G₁ earlier (w free in G₁); (3) G₁ ⊃ G₂ or G₂ ⊃ G₁, G₁ earlier (w free), G₂ any formula — only one side needs w free; (4) ∀vᵢ G′, G′ earlier (w free), vᵢ a variable distinct from w (∀w would bind it). E_y must appear in the sequence. (X in the hint = the target formula E_y; Y = a generic member.)
Step 1. The members are subformulas of E_y — ♯-free, distinct, positive, ≤ y — so k ≤ y; by Theorem D the sequence number ≤ π(y):
Fr(x,y) ⟺ Var(x) ∧ fm(y) ∧ (∃s ≤ π(y))( s is a valid free-occurrence certificate for E_x in E_y, E_y a member )
Step 2. Certificate-check Σ₀; π recursive (Ex 2); fm recursive (Ex 5); bounded ∃≤π(y), Ex 3; K2 ⟹ Fr recursive.
Step 3. A sentence = a formula with no free variable; a free variable has code ≤ y:
Sent(y) ⟺ fm(y) ∧ (∀x ≤ y)( Var(x) ⊃ ~Fr(x,y) )
recursive by K1, K2, K3 ⟹ Sent recursive. ∎
Exercise 8 — closures, and the r.e./recursive transfer
8(1) — Clo(x,y) = "E_x is a formula, E_y is its universal closure" is recursive. With z the prefix (part of E_y before E_x):
Clo(x,y) ⟺ fm(x) ∧ (∃z ≤ y)[ z ∗ x = y ∧ Qpref(z) ∧ (∀v ≤ x)( Var(v) ⊃ ( Fr(v,x) ⟺ 9v P z ) ) ]
z ∗ x = y: z is exactly the prefix (E_x is the tail — the oldxEy).Qpref(z): z is a run of blocks9·(variable)=∀vᵢ, each variable ≤ x, strictly increasing, possibly empty. Σ₀ scan (9's are walls, variables are rooms — the Seq idiom). Increasing order makes the closure unique, so Clo is the graph of a recursive function clos(x).- Last conjunct, spelled out: fusing two demands by ⟺ —
[Fr](#def-fr)(v,x) ⟹ 9v P z("every free variable is quantified" — the result is closed) and9v P z ⟹ [Fr](#def-fr)(v,x)("only free variables are quantified" — no vacuous ∀). Net: the prefix quantifies exactly the free variables.9v P z, not9v P y, because E_x may contain internal (bound) quantifiers that must not count. Bounding quantified variables ≤ x (inside Qpref) rules out vacuous ∀ over variables too big to occur in E_x. - Equivalence proved both directions (the closure prepends ∀ for exactly the free variables; degenerate case: E_x already a sentence ⟹ no free vars ⟹ z empty ⟹ y = x).
8(2) — for any system S: P r.e. ⟺ Pₛ r.e., and P recursive ⟺ Pₛ recursive. (P = provable-formula codes, Pₛ = provable-sentence codes.)
Bridge: a formula is provable iff its closure is (generalize by Rule 2; instantiate back). So
(A) x∈P ⟺ fm(x) ∧ clos(x)∈Pₛ
(B) y∈Pₛ ⟺ y∈P ∧ Sent(y) (Pₛ = P ∩ Sentences)
- r.e.: Pₛ Σ₁ ⟹ P Σ₁ via (A) (fm recursive, clos recursive,
clos(x)∈PₛΣ₁ by C b/c). P Σ₁ ⟹ Pₛ Σ₁ via (B) (Sent recursive, Ex 7). - recursive: P recursive ⟹ Pₛ = P ∩ Sent recursive (K2). Pₛ recursive ⟹ P recursive via (A):
Pₛ(clos(x))recursive (K4), fm recursive (Ex 6), ∧ (K2). ∎
Dependency order: Ex 1, 3 = tools; Ex 2 uses 1; Ex 4/5/7 cap an unbounded ∃ at π (Theorem D) then use Ex 3; Ex 6 collects via K0–K4; Ex 8 uses 6, 7, and clos from 8(1).
Part III — Corrections made this session (errors caught, on the record)
- π was reconstructed, then read exactly. Early draft used a hand-built digit-count bound; the Appendix screenshot gives π(x) = 13^(x²+x) outright. Ex 2 rewritten to prove this recursive (Pow₁₃ + L, or exp∘polynomial).
- "Theorem A" → Theorem D. The witness-bounding lemma (sequence number ≤ π(x)) is the Appendix's Theorem D, not "Theorem A."
- The count step was a genuine non-sequitur. "Distinct and ≤ x, so at most x+1, so k ≤ x" is wrong — at most x+1 gives k ≤ x+1. Fix: term/formula codes are positive (0 is not a term-code; smallest is the numeral 0̄ = 1), so the distinct entries lie in {1,…,x}, at most x of them ⟹ k ≤ x. Same fix in Ex 5, Ex 7.
- Fr's arguments were reversed. The book's Fr(x,y): x is the variable, y is the formula, "E_x occurs free in E_y." The witness bound is π(y) (the formula's size), not π(x). Clo's last conjunct uses
Fr(v,x)accordingly.
The method that caught 1–4: holding the recap against the exact characters of the page (the standing July-25/26 lesson).
Part IV — Chapter V prelude: the definitions
Chapter V redoes incompleteness on a weaker hypothesis than Chapter IV's "correct": Gödel's own ω-consistency.
| term | definition |
|---|---|
| system S (first-order theory over P.A.'s language) | formulas = P.A.'s; axioms include Groups I–II (logical axioms, first-order logic with identity — prove every valid formula); Groups III–IV (the arithmetic axioms) replaced by an arbitrary axiom set; rules = modus ponens + generalization |
| correct | every provable sentence is true (Ch. IV's assumption) |
| refutable | ~X is provable |
| simply consistent | no sentence is both provable and refutable |
| ω-inconsistent | some F(w) (one free variable) has ∃xF(x) provable, yet every F(0̄), F(1̄), … refutable — proves "something is F," refutes each witness |
| ω-consistent | not ω-inconsistent |
| axiomatizable (= formal = r.e.) | the set of provable-formula codes is Σ₁. P.A. is (Ch. III/IV); N (all true arithmetic) is not (not even arithmetic — Tarski, Ch. II) |
| extension / subsystem | S₁ extends S₂ if every S₂-provable formula is S₁-provable |
| represents a set A in S | F(v₁) represents A if n∈A ⟺ F(n̄) provable in S (k-ary for relations) |
| expresses a set A (Ch. II, contrast) | F(v₁) expresses A if n∈A ⟺ F(n̄) true |
Part V — The consistency hierarchy (the spine)
correct ⟹ ω-consistent ⟹ simply consistent
each arrow strict. Chapter IV used the strongest (correct); Gödel's route needs only ω-consistency (weaker hypothesis = stronger theorem); Rosser (later) weakens to simple consistency.
- correct ⟹ ω-consistent (contrapositive). ω-inconsistent gives
∃xF(x)provable, every F(n̄) refutable. If correct:∃xF(x)true ⟹ some F(n̄) true; but F(n̄) refutable ⟹ ~F(n̄) provable ⟹ (correct) F(n̄) false — contradiction. (Top of p. 57.) - ω-consistent ⟹ simply consistent (contrapositive = simply inconsistent ⟹ ω-inconsistent). See Part VII — this is the explosion.
Part VI — The arc of Chapter V's proof
Goal — Theorem G (Gödel's original): P.A. ω-consistent ⟹ P.A. incomplete. Assembled from:
- Theorem A (abstract): axiomatizable + ω-consistent + proves all true Σ₀-sentences ⟹ incomplete.
- Theorem B: P.A. proves all true Σ₀-sentences.
- Known: P.A. is axiomatizable.
Theorem G = apply A to P.A. (axiomatizable ✓, ω-consistent by hypothesis, true-Σ₀ by B).
- Part I: derive Theorem A from still-more-abstract incompleteness theorems (apply to non-axiomatizable systems too). §1 introduces representability.
- Part II: prove Theorem B (stronger: true Σ₁ provable — this is the Σ₁-completeness bridge flagged as owed since July 28, finally paid here).
Conceptual shift: Ch. IV ran on expressing (truth) and needed correctness to link provable↔true. Ch. V runs on representing (provability), so the diagonal argument never invokes truth — which is what lets "correct" drop to "ω-consistent." Incompleteness lives in the gap between the set a formula expresses (true instances) and the set it represents (provable instances).
Part VII — Simple inconsistency, ω-inconsistency, and the explosion
The claim: simply inconsistent ⟹ ω-inconsistent, so ω-consistent ⟹ simply consistent.
The reader's question, resolved. Simple inconsistency, by definition, only says some sentence X is both provable and refutable (X and ~X both provable). But in a system carrying classical first-order logic, one contradiction propagates to every sentence (ex contradictione quodlibet), so "some" collapses to "every sentence is both provable and refutable." The reader's phrasing ("every sentence both provable and refutable") is the correct consequence, equivalent to the definition in these systems — the collapse is the point.
Why the explosion — universal, not one instance. The tautology X ⊃ (~X ⊃ Y) is a schema valid for every Y, hence provable (from Group I logic) for every Y. For any target Y:
- X provable; 2. ~X provable; 3.
X ⊃ (~X ⊃ Y)provable; 4.~X ⊃ Y(MP 1,3); 5. Y (MP 2,4).
Nothing depends on Y — run it once per sentence, every sentence is provable (hence every ~Y provable, so every sentence refutable). Intuitive version: from X, X ∨ Y (or-introduction, any Y); with ~X, disjunctive syllogism gives Y.
Why you cannot contain one contradiction. Provability is closed under the rules — that is what "provable" means. If X and ~X are provable and some Y₀ were to stay out, the derivation above (with the logical axiom X ⊃ (~X ⊃ Y₀), which you cannot exclude, plus closure under MP) forces Y₀ in. So a set holding one contradiction but leaving Y₀ out is not closed under MP — not the provable set of any system with this logic. The contradiction is global, not a local blemish.
Two footnotes: (i) explosion is a feature of classical logic — paraconsistent logics reject exactly these moves to contain contradictions, but Smullyan's S all carry classical logic. (ii) "every sentence provable-or-refutable" is not expected even of good systems — that is completeness, which fails (incompleteness). A healthy system: never both (consistency), sometimes neither (incompleteness).
Part VIII — Distinctions Ledger
| raised | resolution |
|---|---|
| What is π(x)? | 13^(x²+x) — the unique power of 13 of length x²+x+1. Recursive because Pow₁₃ is Σ₀ and L is recursive (Ex 2); or exp∘polynomial (K4). |
| Which theorem bounds the sequence number? | Theorem D: entries ∈ K₁₁, all ≤ x, count k ≤ x ⟹ sequence number ≤ π(x). |
| "distinct and ≤ x, so at most x+1, so k ≤ x" | Non-sequitur: at most x+1 gives k ≤ x+1. Fixed by positivity — term/formula codes are ≥ 1 (0 not a code), so entries ∈ {1,…,x}, at most x ⟹ k ≤ x. |
| What is Fr(x,y)? | E_x a variable, E_y a formula, E_x occurs free in E_y. Variable first, formula second; witness bounded by π(y). |
| Certificate: what are X, Y? | X = the target formula (E_y); Y = a generic member of the witnessing sequence. We exhibit one finite derivation ending at E_y, not an enumeration of the infinite class. |
What is 9zx? |
Concatenation: digit 9 (∀) · variable · body = the code of ∀vᵢ E_x. |
What does xEy mean? |
"x ends y" — E_x is the final segment (suffix) of E_y. (E overloaded: E_x = expression-by-code; xEy = ends; x exp y = exponential symbol.) |
| Clo's last conjunct — what does it constrain? | [Fr](#def-fr)(v,x) ⟺ 9v P z fuses "every free variable is quantified" (result closed) with "only free variables are quantified" (no vacuous ∀). Net: the prefix quantifies exactly the free variables. Search the prefix z, not all of E_y (E_x's internal quantifiers must not count). |
| correct vs ω-consistent vs simply consistent | correct ⟹ ω-consistent ⟹ simply consistent, each strict. Ch. IV used correct; Gödel uses ω-consistent (weaker); Rosser later, simple consistency. |
Is X ⊃ (~X ⊃ Y) one instance or the reason? |
The universal reason — a schema valid/provable for every Y; instantiate per target. |
| Can one contradiction be contained, others clean? | No — provability is closed under MP, and the logical axiom + MP force every Y in. Explosion is global. (Escapable only in paraconsistent logic, not here.) |
| Does simple inconsistency mean every sentence both provable and refutable? | Yes as a consequence: the definition gives one, ex falso blows it up to all. Then ω-inconsistency is automatic (any F: ∃xF(x) provable, every F(n̄) refutable). |
Part IX — Self-Test
1. Why does Ex 1 need f to be total, not just to have a Σ₁ graph?
Answer
The equivalence f(x̄)≠y ⟺ ∃z(f(x̄)=z ∧ z≠y) needs f(x̄) to have a value z; totality supplies it. Uniqueness makes "not y" = "some other value."
2. In Ex 3, which step uses "R recursive" rather than just "R Σ₁," and why?
Answer
The ~Q side: it needs ~R to be Σ₁, which a bare Σ₁ relation does not guarantee. That plus bounded ∀ (Prop C d) keeps ~Q in Σ₁.
3. Give π(x) and prove it recursive in one line.
Answer
π(x)=13^(x²+x); graph [Pow₁₃](#g-pow13)(y) ∧ [L](#g-len)(y)=x²+x+1 is recursive, π total, so recursive by Ex 1.
4. Fix the count: "distinct codes ≤ x, so k ≤ x."
Answer
Distinct ≤ x alone gives k ≤ x+1. Codes are positive (0 is no term/formula code), so entries ∈ {1,…,x}, at most x ⟹ k ≤ x.
5. State Fr(x,y) and the bound used to make it recursive.
Answer
E_x a variable, E_y a formula, E_x free in E_y. Certificate over subformulas of E_y (codes ≤ y), bounded by π(y) via Theorem D; then Ex 3.
6. What does Clo's Fr(v,x) ⟺ 9v P z guarantee?
Answer
The prefix quantifies exactly the free variables of E_x — every free one (⟹, closed) and no others (⟸, no vacuous ∀). Search in the prefix z, not all of E_y.
7. Rank correct / ω-consistent / simply consistent and give the two implications' directions.
Answer
correct ⟹ ω-consistent ⟹ simply consistent. correct⟹ω: ω-inconsistent forces a false-yet-provable F(n̄). ω⟹simple: simply inconsistent explodes to ω-inconsistent.
8. Why can't a system prove one contradiction and keep every other sentence cleanly decided?
Answer
Provability is closed under MP; the logical axiom X ⊃ (~X ⊃ Y) plus X, ~X derives every Y. A set leaving any Y₀ out isn't MP-closed, so isn't a provable set (over classical logic).
9. State Theorem G and how A + B deliver it.
Answer
G: P.A. ω-consistent ⟹ incomplete. A: axiomatizable + ω-consistent + true-Σ₀-provable ⟹ incomplete. B: P.A. proves true Σ₀. P.A. is axiomatizable, so A applies.
10. Express vs represent — the difference, and where incompleteness lives.
Answer
Express: n∈A ⟺ F(n̄) true. Represent: n∈A ⟺ F(n̄) provable. Incompleteness lives in the gap between them; Ch. V works with representing so it never needs truth (hence ω-consistency suffices).
Part X — Position, owed items, debts
Position: Chapter IV complete (text pp. 40–55 owned across July 27–28; Exercises 1–8 now worked, this file). Chapter V begun: prelude pp. 56–58 read — all definitions owned, the consistency hierarchy proved, the proof arc (G ⟸ A + B + axiomatizability) mapped, the explosion elucidated. Next in the book: Chapter V, Part I §1 — "A Basic Incompleteness Theorem" (the representability-based abstract theorems), then Part II (Theorem B / Σ₁-completeness).
Debt finally previewed-as-due: Σ₁-completeness (the decidable ⟹ provable-or-refutable bridge, owed since July 28) is exactly Theorem B + its Part II strengthening — expected to be paid in Part II of this chapter.
Owed, standing (unchanged, July 24–28): the July-27 book-checks (pure-1-frame Lemma K run-merging, divisor characterization at w=1, §5 x=0 wording); older items (L₂/L₃ strings, N₁₂ sub-relation, L₃ case-check, ancestor-interpretation falsification, whole-domain instance question, July-26 spelling checks). Debt register: property 1 ⇒ property 2, mechanical ⇒ Arithmetic, adequacy 1930, general machine form of 1931, operation-agreement, instantiation from L₆+L₇. β-function proof (Remark 2) still deferred.
Method note. Exercises done as the settled chain format (GOAL, glossary, labelled steps citing owned labels only); Chapter V prelude done as a significance/summary piece (definitions table + hierarchy + arc + precise error-diagnosis on the two hard spots). Four tutor errors caught by holding drafts against the page — the recorded versions are corrected.
Previous sessions: July 15 (Ch. 1), 17 (answers), 19–22 (Ch. II), 20 & 23 (exercises), 24 with 25 continuations (Ch. III §1), 26 (Ch. III §§2–4), 27 (Ch. IV pp. 40–50, Theorem E), 28 (Ch. IV pp. 50–55). This file: Ch. IV Appendix exercises + Ch. V prelude.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月29日学习记录 · Smullyan《哥德尔不完备定理》第四章附录,练习1–8,包括定义π(x)=13^(x²+x)与定理D,以及第五章开头,“哥德尔基于ω一致性的证明”一节,书第56–58页 · 7月15–28日记录的续篇 · 性质:一次实作学习,终于把此前搁置的八道练习做成有理由支持的推导链,然后阅读第五章的设置,澄清两处难点,即简单不一致⟹ω不一致,以及矛盾为什么会爆炸。本次学习中发现并对照原书页面纠正了数处辅导者错误;此处记录的是纠正后的版本。
交叉引用可点击:练习3、K3、C d、定理D等引文会跳到正在调用的定义或结果。
本文的组织方式
第一、二部分是练习:先是工具箱,即练习1、练习3,以及封闭性推论K0–K4,再是应用,即练习2、4、5、6、7、8。第三部分记录学习过程中作出的四项纠正,让错误本身也留下记录,而不只留下修正。第四至七部分是第五章的前奏:定义、一致性层级、证明路线,以及对爆炸的澄清。第八部分是区分清单,第九部分是自测,第十部分是进度与待办。
记号: 使用普通Unicode;并置=∗₁₃连接;数位依7月21日的表,∀→9,等等。
第一部分——工具箱:练习1、练习3及其推论
全文引用的已掌握定义,即下面推导链链接所指向的术语表。
- Σ₀=只含有界量词,可判定;对¬、∧、∨、有界∃/∀封闭。
- Σ₁=∃y(Σ₀主体);由命题C₁,等于“Σ关系”。
- 递归关系=R与~R都是Σ₁。
- 递归函数=f是全函数,且其图是递归的。
- 命题C的封闭性,以下引用为C(a)–(e):(a) Σ₀⇒Σ₁;(b)吸收无界∃;(c)∧、∨;(d)有界∃以及有界∀;(e) R⊃S,其中R是Σ₀。
- Pow₁₃=“u是13的幂”,为Σ₀,见7月27日。
- L(x)=十三进制长度,是递归函数;13^m的长度为m+1。
- K₁₁=不含数位δ的编码,即所有不含♯的表达式。
- 定理D:若a₁,…,aₖ ∈ K₁₁均≤x,且k≤x,则序列数δa₁δ…δaₖδ ≤ π(x)=13^(x²+x)。
- 命题3,第三章关系(1)–(17),具体串见7月26日清单,
...-2026-07-26.md:(5) Seqt,(6) tm,(9) R₂,(10) Seqf,(11) fm,等等。
练习1——图为Σ₁的函数是递归函数
步骤1。 函数有唯一值,因此“不是y”=“某个z≠y”:
f(x̄) ≠ y ⟺ ∃z ( f(x̄)=z ∧ z≠y )
⟹:f是全函数,有一个值z≠y;⟸:若其值z≠y,则f(x̄)≠y。这一步使用函数性与全定义性。
步骤2。 f(x̄)=z是Σ₁,已知;z≠y是Σ₀,故为Σ₁,由C a;∧后为Σ₁,由C c;加∃z后为Σ₁,由C b。所以f(x̄)≠y是Σ₁。
步骤3。 图为Σ₁,补集也为Σ₁⟹图是递归关系⟹f是递归函数。 ∎
练习3——在递归界限以下的有界搜索是递归的
主张。 R(x,y)是递归关系,f(x)是递归函数⟹Q(x) := (∃y ≤ f(x))R(x,y)是递归关系。
步骤1。 f是全函数,其值为f(x):
Q(x) ⟺ ∃z ( f(x)=z ∧ (∃y ≤ z)R(x,y) )
~Q(x) ⟺ ∃z ( f(x)=z ∧ (∀y ≤ z)~R(x,y) )
步骤2,Q为Σ₁。 f(x)=z为Σ₁,由练习1;R为Σ₁;(∃y≤z)R为Σ₁,由C d;∧,由C c;∃z,由C b。
步骤3,~Q为Σ₁。 f(x)=z为Σ₁;~R为Σ₁,只有因为R是递归关系才有此条件,单纯的Σ₁关系未必有Σ₁补集;(∀y≤z)~R为Σ₁,由C d的有界∀;∧,由C c;∃z,由C b。
步骤4。 两者均为Σ₁⟹Q是递归关系。 ∎ 否定一侧是唯一用到“R为递归关系”超出“R为Σ₁”之内容的地方,也是使用有界∀即C d的地方。
推论:来自练习1、练习3与命题C
| 标号 | 性质 | 证明 |
|---|---|---|
| K0 | Σ₀⟹递归关系 | R、~R均为Σ₀⟹均为Σ₁,由C a |
| K1 | 递归关系对¬封闭 | 定义对R、~R是对称的 |
| K2 | 递归关系对∧、∨封闭 | R∧S为Σ₁,由C c;~(R∧S)=~R∨~S为Σ₁,由C c;∨的情形对偶 |
| K3 | 对递归关系施加有界∃≤x、∀≤x⟹仍为递归关系 | 练习3取f为恒等函数;∀=¬∃¬,由K1 |
| K4 | g、f是递归函数⟹g∘f是递归函数;g是递归函数、A是递归集合⟹{x: A(g(x))}是递归集合 | 图∃z(f(x)=z ∧ g(z)=y)为Σ₁,函数全定义,由练习1;原像通过A(g(x))⟺∃z(g(x)=z ∧ A(z)),补集使用~A |
第二部分——应用:练习2、4、5、6、7、8
练习2——π(x)=13^(x²+x)是递归函数
步骤1。 13^m的长度为m+1,因此13^(x²+x)是长度为x²+x+1的唯一13的幂:
π(x) = y ⟺ Pow₁₃(y) ∧ L(y) = x²+x+1
步骤2。 [Pow₁₃](#g-pow13)(y)为Σ₀,由K0;[L](#g-len)(y)=x²+x+1是递归函数之间的等式,为递归关系;∧,由K2。图为递归关系,因此是Σ₁。
步骤3。 π是全函数,其图为Σ₁⟹是递归函数,由练习1。∎ 另一证明:幂运算是递归函数,定理E给出其Σ₁图,练习1将其提升;而x²+x是递归函数,因此由复合封闭性K4,π是递归函数。
练习4——tm(x)是递归关系
已掌握:tm(x) ⟺ ∃y(Seqt(y) ∧ x∈y),见关系6;Seqt为Σ₀,见关系5,再用K0。
步骤1。 R₁满足R₁(a,b,c) ⟹ c>a, c>b。把E_x的构造序列剪枝为只含其祖先,且无重复。成员都是E_x的子项,因此:不含♯,即∈K₁₁;≤x,x最大;≥1,每个项都有正编码,最小的是数码0̄=13⁰=1;互不相同。不大于x的互异正整数至多有x个,所以k≤x,这是纠正后的计数;排除0,因为它不是项编码。定理D适用:序列数≤π(x)。所以tm(x) ⟹ (∃y≤π(x))(…)。
步骤2。 反向显然。所以tm(x) ⟺ (∃y≤π(x))(Seqt(y) ∧ x∈y)。
步骤3。 主体为Σ₀,用K0;π为递归函数,由练习2;练习3⟹tm为递归关系。 ∎
练习5——公式编码集合是递归的
R₂,见关系9,也严格增加长度,因此E_x的剪枝构造序列,其成员不含♯、互异、为正数、≤x⟹k≤x。定理D⟹fm(x) ⟺ (∃y≤π(x))(Seqf(y) ∧ x∈y)。Seqf为Σ₀,见关系10;π为递归函数,由练习2;练习3⟹fm为递归关系。 ∎
练习6——关系(1)–(15)全是递归的
- Σ₀,故为递归关系,由K0: (1) Sb、(2) Var、(3) Num、(4) R₁、(5) Seqt、(10) Seqf、(13) M.P.。
- 定理D: (6) tm,见练习4;(11) fm,见练习5。
- 逐步构造: (7) f₀,对tm施加有界∃≤x,用K3+K2;(8) Gen,有界∃≤y,用K3;(9) R₂,递归关系的∨,用K2;(12) A,19个析取项,各自是在fm/Var/tm上施加有界∃,用K3+K2;(14) Der,∨,用K2。
- (15) Pf=
Seq(x) ∧ (∀y∈x)(A(y) ∨ (∃z,w ≺ₓ y)Der(z,w,y))。这里≺ₓ担任双重职务:它是Σ₀,其定义x∈z ∧ y∈z ∧ (∃w≤z)(wBz ∧ x∈w ∧ ~y∈w)中只有有界∃w≤z;并且z ≺ₓ y包含z∈x,因此z≤x,成员从不超过其序列数。所以内部∃z,w是在递归关系矩阵上的有界量词,由K3得到递归关系;A(y)∨(…)由K2;外层(∀y∈x)是在递归关系上的有界∀≤x,由K3得到递归关系;Seq(x)为Σ₀;∧由K2。Pf为递归关系。 ∎
练习7——Fr(x,y)是递归关系;句子编码集合是递归的
Fr(x, y): E_x是变量,E_y是公式,且E_x在E_y中自由出现。变量=第一个自变量x;公式=第二个自变量y。
证书,第三章练习1的提示。 对w=E_x,“w在公式中自由出现”自下而上地生成:见证序列的每个成员是:(1)以w为一部分的原子公式;(2)~G₁,G₁在前面出现,w在G₁中自由;(3)G₁ ⊃ G₂或G₂ ⊃ G₁,G₁在前面出现,w自由,G₂为任意公式,只需一侧有自由的w;(4)∀vᵢ G′,G′在前面出现,w自由,vᵢ是不同于w的变量,∀w会约束它。E_y必须出现在序列中。提示中的X=目标公式E_y;Y=任意一个成员。
步骤1。 成员都是E_y的子公式,不含♯、互异、为正数、≤y,所以k≤y;由定理D,序列数≤π(y):
Fr(x,y) ⟺ Var(x) ∧ fm(y) ∧ (∃s ≤ π(y))( s是E_x在E_y中自由出现的有效证书,且E_y是成员 )
步骤2。 检查证书是Σ₀;π是递归函数,由练习2;fm是递归关系,由练习5;有界∃≤π(y),用练习3;再用K2⟹Fr是递归关系。
步骤3。 句子=没有自由变量的公式;自由变量的编码≤y:
Sent(y) ⟺ fm(y) ∧ (∀x ≤ y)( Var(x) ⊃ ~Fr(x,y) )
练习8——闭包,以及递归可枚举性/递归性的转移
8(1)——Clo(x,y)=“E_x是公式,E_y是它的全称闭包”,是递归关系。 令z为前缀,即E_y中E_x之前的部分:
Clo(x,y) ⟺ fm(x) ∧ (∃z ≤ y)[ z ∗ x = y ∧ Qpref(z) ∧ (∀v ≤ x)( Var(v) ⊃ ( Fr(v,x) ⟺ 9v P z ) ) ]
z ∗ x = y:z恰好是前缀,E_x是尾部,即原来的xEy。Qpref(z):z是一串9·(变量)=∀vᵢ块,每个变量≤x,严格递增,也可能为空。Σ₀扫描,9是墙,变量是房间,即Seq的惯用构造。递增次序使闭包唯一,因此Clo是一个递归函数clos(x)的图。- 最后一个合取项,展开来说:用⟺合并两项要求,即
[Fr](#def-fr)(v,x) ⟹ 9v P z,“每个自由变量都被量化”,结果是封闭的;以及9v P z ⟹ [Fr](#def-fr)(v,x),“只有自由变量被量化”,没有空量化的∀。总之:前缀量化的恰好是自由变量。用9v P z而非9v P y,因为E_x可能含有内部的约束量词,不能把它们计入。在Qpref内部把量化变量限制为≤x,排除了对大到不可能出现在E_x中的变量施加空量化∀。 - 等价关系的两个方向均已证明:闭包在前面添加∀,且恰好针对自由变量;退化情形是E_x已经是句子⟹没有自由变量⟹z为空⟹y=x。
8(2)——对任意系统S:P递归可枚举⟺Pₛ递归可枚举,P递归⟺Pₛ递归。 P=可证公式编码集合,Pₛ=可证句子编码集合。
桥梁: 公式可证,当且仅当其闭包可证;用规则2作全称化,再实例化回来。因此
(A) x∈P ⟺ fm(x) ∧ clos(x)∈Pₛ
(B) y∈Pₛ ⟺ y∈P ∧ Sent(y) (Pₛ = P ∩ 句子集合)
- 递归可枚举: Pₛ为Σ₁⟹P由(A)为Σ₁,其中fm为递归关系,clos为递归函数,
clos(x)∈Pₛ由C b/c为Σ₁。P为Σ₁⟹Pₛ由(B)为Σ₁,其中Sent为递归关系,见练习7。 - 递归: P为递归集合⟹Pₛ=P∩Sent为递归集合,由K2。Pₛ为递归集合⟹P由(A)为递归集合:
Pₛ(clos(x))为递归关系,由K4;fm为递归关系,由练习6;∧,由K2。∎
依赖次序: 练习1、3是工具;练习2使用1;练习4/5/7通过定理D把无界∃截在π处,再用练习3;练习6通过K0–K4汇总;练习8使用6、7,以及8(1)中的clos。
第三部分——本次学习中的纠正:把发现的错误记录在案
- 先重构π,再精确读取。 早期草稿使用手工构造的数位计数界限;附录截图直接给出π(x)=13^(x²+x)。重写练习2,证明这个函数递归,用Pow₁₃+L,或exp∘多项式。
- “定理A”→定理D。 约束见证的引理,序列数≤π(x),是附录的定理D,不是“定理A”。
- 计数步骤确实是不合逻辑的推断。 “互异且≤x,所以至多x+1个,所以k≤x”是错的;至多x+1个只给出k≤x+1。修正:项/公式编码为正数,0不是项编码,最小的是数码0̄=1,因此互异条目位于{1,…,x},至多x个⟹k≤x。练习5、练习7同样修正。
- Fr的自变量被颠倒了。 书中的Fr(x,y):x是变量,y是公式,“E_x在E_y中自由出现”。见证界限是π(y),即公式的大小,而不是π(x)。Clo的最后一个合取项相应使用
Fr(v,x)。
发现1–4的方法:把回顾与页面上的准确字符对照,这是7月25/26日持续适用的教训。
第四部分——第五章前奏:定义
第五章在比第四章的“正确”更弱的假设下重新证明不完备性,即哥德尔本人的ω一致性。
| 术语 | 定义 |
|---|---|
| 系统S,P.A.语言上的一阶理论 | 公式=P.A.的公式;公理包含第一、二组,即带等号的一阶逻辑公理,可证明每个有效公式;第三、四组算术公理被任意公理集替代;规则=肯定前件式与全称化 |
| 正确 | 每个可证句子都为真,第四章的假设 |
| 可反驳 | ~X可证 |
| 简单一致 | 没有句子既可证又可反驳 |
| ω不一致 | 某个具有一个自由变量的F(w),其∃xF(x)可证,但每个F(0̄)、F(1̄)、…均可反驳;证明“有某物是F”,却反驳每个见证 |
| ω一致 | 不是ω不一致 |
| 可公理化=形式的=递归可枚举 | 可证公式编码集合为Σ₁。P.A.是,第三/四章;N,即全部真算术,不是,甚至不是算术的,由第二章塔斯基定理 |
| 扩张/子系统 | 若每个S₂可证公式都在S₁中可证,则S₁扩张S₂ |
| 在S中表示集合A | F(v₁)表示A,若n∈A ⟺ F(n̄)在S中可证;关系则推广为k元 |
| 表达集合A,第二章,对照项 | F(v₁)表达A,若n∈A ⟺ F(n̄)为真 |
第五部分——一致性层级:主干
正确 ⟹ ω一致 ⟹ 简单一致
每个箭头都是严格的。第四章使用最强的正确性;哥德尔路线只需ω一致性,假设更弱=定理更强;Rosser在后面弱化为简单一致性。
- 正确⟹ω一致,用逆否命题。ω不一致给出
∃xF(x)可证,每个F(n̄)都可反驳。若正确:∃xF(x)为真⟹某个F(n̄)为真;但F(n̄)可反驳⟹~F(n̄)可证⟹由正确性,F(n̄)为假,矛盾。见第57页顶端。 - ω一致⟹简单一致,逆否命题=简单不一致⟹ω不一致。见第七部分,这就是爆炸。
第六部分——第五章的证明路线
目标——定理G,哥德尔原始定理:P.A.ω一致⟹P.A.不完备。 由以下内容组装:
定理G=将A应用于P.A.:可公理化✓,ω一致来自假设,真Σ₀可证来自B。
- 第一部分:从更加抽象的不完备定理推导定理A,那些定理也适用于不可公理化的系统。§1引入可表示性。
- 第二部分:证明定理B,更强的是,真的Σ₁可证;这就是自7月28日起标为待完成、终于在此偿还的Σ₁完备性桥梁。
概念转移: 第四章围绕表达,即真理展开,并需正确性来联系可证↔真。第五章围绕表示,即可证性展开,因此对角论证从不调用真理,这才允许“正确”降为“ω一致”。不完备性存在于一个公式所表达的集合,即真实例,与它所表示的集合,即可证实例,之间的间隙。
第七部分——简单不一致、ω不一致与爆炸
读者的疑问得到解决。 简单不一致,按定义,只说某个句子X既可证又可反驳,即X与~X都可证。但在带有经典一阶逻辑的系统中,一个矛盾会传播到每个句子,即ex contradictione quodlibet,因此“某个”坍缩为“每个句子都既可证又可反驳”。读者的措辞,“每个句子都既可证又可反驳”,是正确的后果,在这些系统中与定义等价;坍缩正是要点。
为什么爆炸:普遍性,而非单个实例。 重言式X ⊃ (~X ⊃ Y)是对每个Y都有效的模式,因此对每个Y都可由第一组逻辑公理证明。对任意目标Y:
- X可证;2. ~X可证;3.
X ⊃ (~X ⊃ Y)可证;4.~X ⊃ Y,对1、3用MP;5. Y,对2、4用MP。
没有任何一步依赖Y;每个句子运行一次,每个句子就都可证,因此每个~Y都可证,所以每个句子都可反驳。直观版本:从X得到X ∨ Y,析取引入,对任意Y;再结合~X,由析取三段论得到Y。
为什么不能把一个矛盾限制住。 可证性对规则封闭,这就是“可证”的含义。如果X与~X可证,而某个Y₀仍要留在外面,上面的推导,使用你不能排除的逻辑公理X ⊃ (~X ⊃ Y₀),再加上对MP的封闭性,就会强行把Y₀纳入。因此,一个容纳某个矛盾却把Y₀留在外面的集合,不对MP封闭,也就不是任何具有这种逻辑的系统的可证集合。矛盾是全局性的,不是局部瑕疵。
两条脚注:(i)爆炸是经典逻辑的特点;次协调逻辑恰恰拒绝这些步骤来限制矛盾,但Smullyan的S全都带有经典逻辑。(ii)即使对好的系统,也不应期待“每个句子都可证或可反驳”;那是完备性,而它会失败,即不完备性。健康的系统:永远不兼有两者,一致性;有时两者都没有,不完备性。
第八部分——区分清单
| 提出的问题 | 解答 |
|---|---|
| π(x)是什么? | 13^(x²+x),长度为x²+x+1的唯一13的幂。它是递归函数,因为Pow₁₃为Σ₀,L是递归函数,见练习2;或用exp∘多项式,K4。 |
| 哪个定理给序列数设界? | 定理D:条目∈K₁₁,全部≤x,个数k≤x⟹序列数≤π(x)。 |
| “互异且≤x,所以至多x+1个,所以k≤x” | 推断不成立:至多x+1个只给出k≤x+1。以正性修正:项/公式编码≥1,0不是编码,所以条目∈{1,…,x},至多x个⟹k≤x。 |
| Fr(x,y)是什么? | E_x是变量,E_y是公式,E_x在E_y中自由出现。变量在先,公式在后;见证以π(y)为界。 |
| 证书中X、Y是什么? | X=目标公式E_y;Y=见证序列中的一般成员。我们展示一条以E_y结束的有限推导,而不是枚举无限的类。 |
9zx是什么? |
连接:数位9,即∀·变量·主体=∀vᵢ E_x的编码。 |
xEy是什么意思? |
“x是y的末尾”,E_x是E_y的末段,即后缀。E被复用:E_x=按编码对应的表达式;xEy=位于末尾;x exp y=幂运算符号。 |
| Clo的最后一个合取项约束什么? | [Fr](#def-fr)(v,x) ⟺ 9v P z合并“每个自由变量都被量化”,结果封闭,与“只有自由变量被量化”,没有空量化∀。总之,前缀恰好量化自由变量。搜索前缀z,而不是整个E_y,E_x的内部量词不能计入。 |
| 正确、ω一致、简单一致 | 正确⟹ω一致⟹简单一致,每一步都严格。第四章使用正确;哥德尔使用更弱的ω一致;Rosser后来使用简单一致。 |
X ⊃ (~X ⊃ Y)是单个实例还是理由? |
是普遍理由,对每个Y都有效/可证的模式;针对每个目标实例化。 |
| 能限制一个矛盾,让其他部分保持干净吗? | 不能,可证性对MP封闭,而逻辑公理与MP把每个Y都强行纳入。爆炸是全局的。只有次协调逻辑能逃脱,此处不能。 |
| 简单不一致意味着每个句子都既可证又可反驳吗? | 是,作为后果:定义给出一个,矛盾推出任意命题把它扩大为全部。于是ω不一致自动成立:任意F,∃xF(x)可证,每个F(n̄)可反驳。 |
第九部分——自测
答案
等价关系f(x̄)≠y ⟺ ∃z(f(x̄)=z ∧ z≠y)需要f(x̄)具有一个值z,全定义性提供这一点。唯一性使“不是y”=“某个其他值”。
2. 练习3中哪一步用到“R递归”,而不只是“R为Σ₁”,为什么?
3. 给出π(x),并用一行证明它递归。
4. 修正计数:“互异编码≤x,所以k≤x。”
答案
仅互异且≤x只给出k≤x+1。编码是正数,0不是项/公式编码,所以条目∈{1,…,x},至多x个⟹k≤x。
5. 陈述Fr(x,y),以及使它递归所用的界限。
6. Clo的Fr(v,x) ⟺ 9v P z保证什么?
答案
前缀恰好量化E_x的自由变量,每个自由变量都量化,⟹,封闭;不量化其他变量,⟸,无空量化∀。搜索前缀z,而不是整个E_y。
答案
正确⟹ω一致⟹简单一致。正确⟹ω:ω不一致强迫出现假而可证的F(n̄)。ω⟹简单:简单不一致爆炸为ω不一致。
8. 为什么系统不能证明一个矛盾,同时让其他每个句子都保持清楚的判定?
答案
可证性对MP封闭;逻辑公理X ⊃ (~X ⊃ Y)加上X、~X推出每个Y。任何把某个Y₀留在外面的集合都不对MP封闭,因此在经典逻辑下不是可证集合。
答案
表达:n∈A ⟺ F(n̄)为真。表示:n∈A ⟺ F(n̄)可证。不完备性存在于两者之间的间隙;第五章使用表示,因此从不需要真理,于是ω一致性就足够。
第十部分——进度、待办与未清事项
进度:第四章完成,正文第40–55页已在7月27–28日掌握;练习1–8现已做完,见本文件。第五章已开始:已读前奏第56–58页,所有定义已掌握,一致性层级已证明,证明路线,即G⟸A+B+可公理化,已梳理,爆炸已澄清。书中下一步:第五章第一部分§1,“一个基本不完备定理”,即基于可表示性的抽象定理,然后第二部分,定理B/Σ₁完备性。
终于预告即将偿还的事项:Σ₁完备性,即可判定⟹可证或可反驳的桥梁,自7月28日待完成,恰好就是定理B及第二部分对它的加强,预计将在本章第二部分完成。
持续待办,7月24–28日以来未变: 7月27日的原书核对,纯1框架引理K的连续段合并、w=1时的因子刻画、§5中x=0的措辞;更早项目,L₂/L₃字符串、N₁₂子关系、L₃分情况检查、祖先解释的证伪、全论域实例问题、7月26日的字符核对。未清事项登记:性质1⇒性质2、机械性⇒算术性、1930年的恰切性、1931年一般机器形式、操作一致、从L₆+L₇得到实例化。β函数证明,评注2,仍搁置。
方法说明。 练习按已经确定的链式格式完成:目标、术语表、带标号的步骤,只引用已掌握的标号。第五章前奏按意义/总结文章处理:定义表+层级+路线+对两处难点的准确错误诊断。通过对照页面发现了四处辅导者错误,此处记录的版本已纠正。
此前学习:7月15日,第一章;17日,答案;19–22日,第二章;20日与23日,练习;24日及25日续篇,第三章§1;26日,第三章§§2–4;27日,第四章第40–50页、定理E;28日,第四章第50–55页。本文件:第四章附录练习与第五章前奏。