Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter V, Part I: the abstract incompleteness theorems and Exercises 1–7
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 — Glossary (definitions + the diagonal lemma)
- Part II — The arc: from the diagonal lemma to Theorem A(*)
- Part III — Exercises 1–7 as chains
- Exercise 1 — direct undecidability (no double-negation)
- Exercise 2 — P̃* is never representable (consistency irrelevant)
- Exercise 3 — P̃* representable in a consistent extension ⇒ S incomplete
- Exercise 4 — truth values in a correct system (S ⊆ N)
- ★ Exercise 5 — all true Σ₀ provable and ω-consistent ⇒ every Σ₁-set representable ★
- Exercise 6 — the abstract mechanism behind Ex 5
- Exercise 7 — the self-strengthening (worked in full in Part IV)
- Part IV — Exercise 7 in depth: the A-versus-A* "last step"
- Part V — Conceptual deep-dives
- V.1 — Inconsistency (object, contingent) vs contradiction (meta, necessary) — why Ex 2 needs no consistency
- V.2 — Ex 3: the hidden index (self- vs cross-representation)
- V.3 — Ex 6: decidability's one job
- V.4 — Ex 5/Ex 6 are the same proof twice
- V.5 — enumeration ≠ representation (a one-way, gated implication)
- Part VI — Corrections made this session (errors caught, on the record)
- Part VII — Distinctions Ledger
- Part VIII — Self-Test
- Part IX — Position, owed items, debts
Study session of July 30, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter V ("Gödel's Proof Based on ω-Consistency"), Part I "Some Abstract Incompleteness Theorems," book pp. 58–65 · Companion to July 15–29 · Character: a working session — the full arc from the diagonal lemma to the pinnacle Theorem A and its self-strengthening Theorem A* mapped as a pipeline, then Exercises 1–7 worked as justified chains, then five conceptual deep-dives (the A/A* "last step", inconsistency-vs-contradiction, self-vs-cross representation, decidability's role, enumeration≠representation). Two tutor errors were caught mid-session against the book's exact wording of Ex 5 and Ex 6; the versions recorded here are the corrected ones.**
Cross-references are clickable: citations like L1a, Lemma ω, Thm 1, Ex 5 jump to the definition or result being invoked.
How this document is organized
Part I is the glossary — every definition, plus the diagonal Lemma 1, as link targets. Part II is the arc: the pipeline of abstract theorems climbing to Theorem A/A* (task 1 of the session). Part III works Exercises 1–7 as chains, each with its start (hypotheses) and finish (conclusion) matched to the book, citing only owned labels. Part IV is Exercise 7 in depth — the A-versus-A* "last step" that opened the session. Part V collects the five conceptual deep-dives. Part VI records the two corrections made mid-session (errors on file). Part VII is the Distinctions Ledger, VIII the Self-Test, IX the position and debts.
Notation: plain Unicode. n̄ = the numeral naming n. S⊢X = "X provable in S". Everything is relative to a system S unless subscripted otherwise.
Part I — Glossary (definitions + the diagonal lemma)
- Σ₀ = bounded quantifiers only (decidable; a true/false
Σ₀-sentence is recognizably so). Carried from July 29. - Σ₁ =
∃y(Σ₀ body). - P* =
{ n : Eₙ(n̄) is provable in S }— the diagonal provability set (Eₙ= the formula, one free variable, with Gödel numbern). - R* =
{ n : Eₙ(n̄) is refutable in S }— the diagonal refutability set. - represents (a set/relation in S):
F(v₁)representsAiff for alln,S⊢F(n̄) ⟺ n∈A. A provability notion. - expresses (a set in the standard model):
F(v₁)expressesAiff for alln,F(n̄)true ⟺n∈A. A truth notion. (Ch. II; contrast with represents.) - enumerates:
F(v₁,v₂)enumeratesAiff (clause 1)n∈A ⇒for somem,S⊢F(n̄,m̄); (clause 2)n∉A ⇒for everym,F(n̄,m̄)is refutable inS. - axiomatizable (= formal = r.e.): the provable-formula codes form a Σ₁ set. Then P* is Σ₁ (last chapter:
AΣ₁ ⇒A*Σ₁). - simply consistent: no sentence with both itself and its negation provable.
- ω-consistent: no
F(v₁)withS⊢∃v₁F(v₁)yet everyF(n̄)refutable. (ω-consistent ⟹ simply consistent, July 29.) - correct: every provable sentence is true (Ch. IV's hypothesis;
S ⊆ N).
Lemma 1 — the diagonal bookkeeping (pure; no consistency assumed)
For any formula H(v₁) with Gödel number h:
Ground: H(h̄) and H[h] = E_h[h] are provably equivalent (first-order logic with identity, inside S), and h∈P* means exactly S⊢E_h(h̄). This one lemma drives every theorem below.
The theorems as link targets
- Theorem 1 (diagonal incompleteness):
Ssimply consistent + someH(v₁)whose negation represents P* ⟹H(h̄)undecidable. - Corollary: P* representable +
Sconsistent ⟹Sincomplete. - Theorem 1′ (dual): R* representable +
Ssimply consistent ⟹Sincomplete. - Lemma ω (the ω-Consistency Lemma):
Sω-consistent +FenumeratesA⟹∃v₂F(v₁,v₂)representsA. - Theorem 2: P* or R* enumerable +
Sω-consistent ⟹Sincomplete. - Theorem 3 (Gödel's sentence, sharpened):
A(v₁,v₂)enumerates P*;h= Gödel number of∀v₂~A(v₁,v₂);G := ∀v₂~A(h̄,v₂). Then (1) simple consistency ⟹Gnot provable; (2) ω-consistency ⟹Gnot refutable. - Theorem 3′ (dual for R*).
- Theorem A: axiomatizable + ω-consistent + all true Σ₀ provable ⟹ incomplete.
- Theorem A*: axiomatizable + ω-consistent + no false Σ₀ provable ⟹ incomplete. (Strictly stronger — weaker hypothesis.)
- Theorem B: all true Σ₀-sentences are provable in P.A. (Part II; the owed Σ₁-completeness bridge.)
- Theorem G: P.A. ω-consistent ⟹ incomplete. = apply A to P.A. via B + axiomatizability.
Part II — The arc: from the diagonal lemma to Theorem A(*)
The chapter's goal chain.
Theorem G ⟸ Theorem A + Theorem B + "P.A. axiomatizable"
Theorem A ← Part I (this session)
Theorem B ← Part II (next: Σ₀-completeness)
Part I's whole job is Theorem A, reached by steadily more concrete abstract theorems. The skeleton, each step naming what it adds:
Step 1 — Theorem 1: what makes a system incomplete at all. If the negation of H represents P*, then H(h̄) refutable ⟺ h∈P*; (L1a) gives H(h̄) provable ⟺ h∈P*. So provable ⟺ refutable — impossible under simple consistency unless neither holds. The sentence falls into the gap. Yields the Corollary (P* representable ⇒ incomplete) and its dual Theorem 1′.
Step 2 — the obstacle. Theorem 1 needs P* representable — a hard, provability-side condition. What comes cheaply is the weaker enumerable. We need a bridge.
Step 3 — Lemma ω: the bridge, and where ω-consistency enters the whole edifice. ω-consistency upgrades enumerable → representable. The n∉A direction is the crux: then every F(n̄,m̄) is refutable, so if ∃v₂F(n̄,v₂) were also provable, S would be ω-inconsistent. This is a one-directional, gated implication, not an equivalence (see Part V.5).
Step 4 — Theorem 2. Combine 1+3: P* or R* enumerable + ω-consistent ⟹ incomplete.
Step 5 — Theorem 3: the two-strength split (Gödel's actual sentence). With A enumerating P*, ∀v₂~A(v₁,v₂) is a formula whose negation represents P*; its diagonal is G = ∀v₂~A(h̄,v₂). The payoff is the asymmetry: (1) G unprovable needs only simple consistency; (2) G unrefutable needs ω-consistency. Half the theorem is cheap — this is what later lets Rosser drop to simple consistency.
Step 6 — feed Σ₀ in, get Theorem A. axiomatizable ⇒ P* is Σ₁; Ex 5 (all true Σ₀ provable ⇒ Σ₁ enumerable, then Lemma ω) ⇒ P* representable; Theorem 3 ⇒ undecidable G. ∎
Step 7 — the self-strengthening Theorem A*. Its hypothesis "no false Σ₀ provable" is strictly weaker than "all true Σ₀ provable" (given consistency, the latter implies the former). Proved directly by Ex 7; Theorem A then falls out as a corollary. See Part IV.
One-line map: representability is what Theorem 1 needs; enumerability is what you can get; ω-consistency (Lemma ω) is the toll that converts one into the other; Σ₀-provability (Ex 5) is what makes the axiomatizable P* enumerable in the first place.
Part III — Exercises 1–7 as chains
Each starts and finishes as the book states it (Ex 5, 6 verbatim from the p. 62 crop; the rest from pp. 60–65).
Exercise 1 — direct undecidability (no double-negation)
Start: S consistent; H(v₁) represents P*; h = Gödel number of ~H(v₁). Finish: H(h̄) undecidable.
- (L1a) applied to the formula
~H(v₁)(own Gödel numberh):S⊢~H(h̄) ⟺ h∈P*, i.e.H(h̄)refutable ⟺h∈P*. - represents at
n=h:S⊢H(h̄) ⟺ h∈P*.
So H(h̄) provable ⟺ refutable ⟺ h∈P*. If h∈P*, both hold — barred by consistency. Hence h∉P*, both fail, undecidable. ∎ (No double-negation law — the advantage over the Theorem 1 route.)
Exercise 2 — P̃* is never representable (consistency irrelevant)
Start: F(v₁) represents P̃* (complement of P*), any S. Finish: impossible.
Let f = Gödel number of F. (L1a): S⊢F(f̄) ⟺ f∈P*. represents P̃*: S⊢F(f̄) ⟺ f∉P*. Chain: f∈P* ⟺ f∉P* — a metatheoretic contradiction. No consistency consumed (both sides are provability biconditionals). ∎ Answers the Question after Theorem 1: a formula that represents P* (rather than one whose negation does) yields only (L1a) twice — a tautology; forcing a contradiction would need P̃* representable, which is exactly this impossibility. Deeper reading: Part V.1.
Exercise 3 — P̃* representable in a consistent extension ⇒ S incomplete
Start: P̃* of S represented in a consistent S′ ⊇ S. Finish: S incomplete.
Contrapositive: assume S complete (consistent, inside consistent S′). Then S and S′ prove the same sentences: S⊢X ⇒ S′⊢X; and S′⊢X ⇒ S⊢X (else completeness gives S⊢~X, so S′⊢~X alongside S′⊢X — S′ inconsistent). Representation depends only on which F(n̄) are provable, so "represents P̃* in S′" = "in S" — contradicting Ex 2. Hence S incomplete. ∎ Relation: the robust form of Ex 2/the Corollary. Index-tracking subtlety: Part V.2.
Exercise 4 — truth values in a correct system (S ⊆ N)
h = Gödel number of H(v₁); correct ⟹ consistent.
- (1)
~Hrepresents P*. As in Ex 1:h∉P*, soH(h̄)unprovable.H(h̄)is the fixed point assertingh∉P* = its own unprovability, which is correct ⟹H(h̄)true. - (2)
Hrepresents and expresses R*. (L1a)+represents:S⊢H(h̄) ⟺ h∈P* ⟺h∈R*; (L1b): refutable ⟺h∈R*. Consistency ⟹h∉R* ⟹ undecidable. expresses R*:H(h̄)true ⟺h∈R*;h∉R* ⟹H(h̄)false.
(Contrast: (1) pins truth via correctness on the unprovability fixed point; (2) via explicit expression — opposite value.)
★ Exercise 5 — all true Σ₀ provable and ω-consistent ⇒ every Σ₁-set representable ★
The load-bearing lemma for Theorem A. (Book verbatim: "if all true Σ₀-sentences are provable in S and S is ω-consistent, then all Σ₁-sets are representable in S." The conclusion is representability, and ω-consistency is a hypothesis — the whole point.)
Start: (P) all true Σ₀ provable; (ω) S ω-consistent. Finish: every Σ₁-set representable.
Let A be Σ₁: A = {n : ∃m R(n,m)}, R a Σ₀-relation; A(v₁,v₂) a Σ₀-formula expressing R.
- Step 1 — enumerate (spends P).
n∈A⇒ someR(n,m)⇒A(n̄,m̄)true Σ₀ ⇒ (P) provable. → enum clause 1.n∉A⇒ everyR(n,m)false ⇒ every~A(n̄,m̄)true Σ₀ ⇒ (P) provable ⇒ everyA(n̄,m̄)refutable. → enum clause 2.- Step 2 — represent (spends ω). By Lemma ω,
∃v₂A(v₁,v₂)representsA. ∎
Why it's the crux. axiomatizable ⇒ P* is Σ₁; this exercise then makes P* representable, feeding Theorem 3. Both hypotheses are load-bearing in different steps — P buys enumeration, ω buys the lift (Lemma ω). Hypothesis P is exactly what Theorem B supplies for P.A.
Exercise 6 — the abstract mechanism behind Ex 5
(Book verbatim: "Suppose F(v₁,v₂) represents in S the same relation that it expresses and for all n,m the sentence F(n̄,m̄) is either provable or refutable. Prove that if S is ω-consistent, then ∃v₂F(v₁,v₂) represents in S the same set that it expresses.")
Start: (a) for all n,m: S⊢F(n̄,m̄) ⟺ F(n̄,m̄) true (represents = expresses, on the relation); (b) every F(n̄,m̄) decidable; (c) S ω-consistent. Finish: ∃v₂F represents the set it expresses.
Let A = {n : ∃m F(n̄,m̄) true} = set expressed by ∃v₂F.
- Step 1 —
FenumeratesA. n∈A⇒ someF(n̄,m̄)true ⇒ (a) someS⊢F(n̄,m̄). → clause 1.n∉A⇒ everyF(n̄,m̄)false ⇒ (a) every not provable ⇒ (b) every refutable. → clause 2.- Step 2 — Lemma ω (spends c).
∃v₂FrepresentsA. ∎
Where each hypothesis goes: (a) both clauses (the true⟺provable bridge); (b) only clause 2, converting unprovable → refutable — its sole job; (c) the Lemma ω lift. Ex 6 = Ex 5 in the abstract: same two-step shape, "represents=expresses on instances" abstracting "all true Σ₀ provable," decidability abstracting Σ₀-decidability.
Exercise 7 — the self-strengthening (worked in full in Part IV)
Start: S axiomatizable; A(v₁,v₂) enumerates P* and expresses a Σ₀-relation R; h = Gödel number of ∀v₂~A(v₁,v₂); G := ∀v₂~A(h̄,v₂). Finish: (1) G provable ⇒ some false Σ₀ provable; (2) G refutable + ω-consistent ⇒ some true Σ₀ not provable; (3) Theorem A follows.
Anchor via (L1a): S⊢G ⟺ h∈P* ⟺ ∃y R(h,y) true. Full derivation and the A/A* resolution: Part IV.
Part IV — Exercise 7 in depth: the A-versus-A* "last step"
The session opened here. The confusion: the printed Solution, step 3 begins "Suppose now all true Σ₀-sentences are provable in S" — which is Theorem A's hypothesis, not A*'s. Resolution below.
(1) G provable ⇒ a false Σ₀ provable. S⊢G ⇒ h∈P* ⇒ some n with R(h,n) true ⇒ A(h̄,n̄) a true Σ₀ ⇒ ~A(h̄,n̄) false. But G=∀v₂~A(h̄,v₂) provable ⇒ instance ~A(h̄,n̄) provable. A false Σ₀ is provable. ∎ (Uses expression + anchor only — no provability hypothesis.)
(2) G refutable + ω-consistent ⇒ a true Σ₀ unprovable. G refutable ⇒ ~G = ∃v₂A(h̄,v₂) provable. Also G refutable + simple consistency ⇒ G unprovable ⇒ h∉P* ⇒ every R(h,n) false ⇒ every ~A(h̄,n̄) a true Σ₀. ω-consistency on the provable ∃v₂A(h̄,v₂): not all A(h̄,n̄) refutable ⇒ some A(h̄,n̄) not refutable ⇒ that ~A(h̄,n̄) not provable — a true Σ₀, unprovable. ∎
(3) as printed = Theorem A (the corollary). Assume all true Σ₀ provable + ω-consistent:
| step | move | ground |
|---|---|---|
| all true Σ₀ provable ⇒ no false Σ₀ provable | a false Σ₀ has a true Σ₀ negation, provable; consistency bars both | simple consistency |
⇒ G not provable |
contrapositive of (1) | Ex 7(1) |
all true Σ₀ provable ⇒ (G refutable ⇒ ω-inconsistent) |
contrapositive of (2) | Ex 7(2) |
With ω-consistency: G not provable and not refutable ⟹ undecidable ⟹ Theorem A. ∎
Why this is not A*, and where A* actually lives. The printed step 3 assumes the strong hypothesis, so it proves A; the surrounding prose ("A* directly, A as corollary") is carried by parts (1)+(2) themselves:
- (1) is the A*-native step: "no false Σ₀ provable" ⇒
Gunprovable, directly. - The refutable branch is where A and A* diverge:
- A (strong hyp.): (2)'s conclusion "some true Σ₀ unprovable" is impossible, so the branch is excluded and the witness stays
G. - A* (weak hyp.): (2) hands you a true Σ₀ sentence
Yunprovable; then~Yis a false Σ₀, so A*'s hypothesis makes~Yunprovable too —Yis the undecidable witness.
The exact trap: step 3's phrase "some true Σ₀ is not provable" (from (2)) is the negation of A's hypothesis derived as an output, not A's hypothesis assumed as input. The word "provable" appears; the polarity is reversed. Under A* that unprovable Y, paired with its unprovable false negation, is the incompleteness — so the proof is genuinely direct and "more informative": under A*'s hypotheses, either G is undecidable or some Σ₀-sentence is, with a concrete witness in every case.
Part V — Conceptual deep-dives
V.1 — Inconsistency (object, contingent) vs contradiction (meta, necessary) — why Ex 2 needs no consistency
Model-counting. Theorem 1 derives p ⟺ q with p="S⊢H(h̄)", q="H(h̄) refutable" — two independent statements. p=q has two solutions: (T,T) = inconsistent, (F,F) = undecidable. Consistency is the premise that deletes (T,T), leaving (F,F). Ex 2 derives b ⟺ ¬b for a single b="f∈P*" — zero solutions. Nothing to prune; the hypothesis is self-annihilating.
Where consistency lives. Consistency is the principle "refutable ⇒ not provable" (P* ∩ R* = ∅). An argument needs it iff it plays refutability against provability. Theorem 1 uses "negation represents P*" (refutability) — must buy disjointness. Ex 2 uses only provability and its Boolean complement — the metalogic's own non-contradiction suffices.
The tell: Ex 2 holds even of inconsistent S (then P*=all, P̃*=∅, unrepresentable since everything is provable). A theorem true of inconsistent systems cannot have used consistency — it is a claim about the metalanguage, not the object system. (Equipollence framing: the provable/refutable biconditional is a genuine balance needing an external tie-breaker; b⟺¬b is not a balance but a self-cancellation.)
V.2 — Ex 3: the hidden index (self- vs cross-representation)
P* is relative to a system: P*_T = {n : Eₙ(n̄) provable in T}. Ex 2 forbids only P̃*_T representable in T — set and representing system locked to the same T, because (L1a)'s self-reference needs one system in both roles. Ex 3 asks about P̃*_S representable in S′ — a different system; the indices don't match, so Ex 2 does not apply. A stronger S′ can know more about S's non-provability than S does, so cross-representation is a priori possible. Completeness re-locks the indices (S, S′ prove the same sentences), collapsing cross → self, where Ex 2 finally bites. Net, strictly stronger than Ex 2: no consistent extension can represent S's P̃* unless S is incomplete.
One-line taxonomy: Ex 2 = "A can't represent A's own P̃*" (unconditional); Ex 3 = "if a consistent extension B⊇A represents A's P̃*, then A is incomplete" (conditional; contrapositive is the "impossibility" reading, and only under completeness).
V.3 — Ex 6: decidability's one job
∃v₂F(n̄,v₂) provable is weaker than some instance F(n̄,m̄) provable — a system can prove an existential with no provable witness. ω-consistency forbids that pathology; decidability's sole role is to turn "n∉A ⇒ no instance provable" into "every instance refutable" (enum clause 2), which the Lemma ω contradiction then consumes.
V.4 — Ex 5/Ex 6 are the same proof twice
Both are enumerate, then Lemma ω. Ex 6 states the mechanism abstractly ("provable-agrees-with-true on all instances, all decidable"); Ex 5 is its Σ₀/Σ₁ instance ("all true Σ₀ provable" makes A(v₁,v₂) provable-agree with true on Σ₀-instances; Σ₀-decidability is automatic). Both live or die on the enumeration→representation lift.
V.5 — enumeration ≠ representation (a one-way, gated implication)
Not an equivalence. enumerable ⇒ representable holds only under ω-consistency (Lemma ω — ω-consistency is load-bearing). representable ⇒ enumerable is also not free: representability gives F(n̄) unprovable for n∉A, but enumeration clause 2 demands refutable — strictly stronger. Collapsing the two would hide exactly where ω-consistency enters the incompleteness proof — the one simplification to resist in a chapter whose subject is that entry point.
Part VI — Corrections made this session (errors caught, on the record)
- Ex 5 mis-stated as concluding only "enumerable." Working from a mistranscription, the tutor first claimed Ex 5 stops at enumerability and does not use the enumeration→representation link — and "corrected" the reader who had said it does. The book's Ex 5 concludes representable and carries ω-consistency as a second hypothesis. The reader was right: Ex 5 is genuinely two-step (enumerate via P, then Lemma ω via ω). Corrected in Part III.
- Ex 6's hypothesis invented. The tutor supplied a fabricated "(★)
n∈A ⟺ some F(n̄,m̄) provable." The book's actual hypothesis is "represents inSthe same relation it expresses" (i.e.S⊢F(n̄,m̄) ⟺ F(n̄,m̄)true) plus decidability; conclusion "∃v₂Frepresents the same set it expresses." Corrected in Part III; decidability's role re-derived in V.3.
The method that caught both: holding the recap against the exact characters of the page (the standing July-25/26/29 lesson). Both fixes surfaced from the reader's own scrutiny ("how do we know F enumerates A?"; "Ex 5 relies on enumeration≡representation, right?").
Part VII — Distinctions Ledger
| raised | resolution |
|---|---|
| Why does Theorem 1 need "negation represents P*", not "represents"? | Represents-P* gives only (L1a) twice (tautology); the refutability side (negation represents) is what makes provable⟺refutable. Represent-P* directly would need P̃* representable — impossible (Ex 2). |
| Why does Ex 2 use no consistency? | It derives b⟺¬b (a meta-contradiction, zero models), not p⟺q (an object-inconsistency, two models). Consistency = "refutable⇒unprovable"; Ex 2 never touches refutability. Holds even of inconsistent S. (V.1) |
| Why isn't Ex 3 already covered by Ex 2? | P* is indexed to a system. Ex 2 locks set and representer to the same T; Ex 3 is cross-system (P̃*_S in S′). Completeness re-locks them. (V.2) |
The S′⊢X ⇒ S⊢X line in Ex 3 |
Completeness of S + consistency of S′: if S⊬X then S⊢~X so S′⊢~X, clashing with S′⊢X. Special to complete S — incomplete S grows under extension. |
| Ex 7 step 3 seems to assume A's hypothesis | Because it is proving A (the corollary). "Some true Σ₀ unprovable" in (2) is A's hypothesis negated as an output, not assumed. A* lives in (1)+(2) with the Y-shift. (Part IV) |
| Is enumeration ≡ representation? | No — one-way, ω-gated (Lemma ω); converse also unfree (unprovable ≠ refutable). (V.5) |
| What is decidability for in Ex 6? | Only to turn "no instance provable" into "every instance refutable"; ω-consistency does the representation lift. (V.3) |
How do we know F enumerates A in Ex 6? |
Not given — derived from (a) represents=expresses + (b) decidability. Enumeration is the first thing you prove. |
| Theorem 3's two clauses split by strength | (1) unprovable ← simple consistency; (2) unrefutable ← ω-consistency. The cheap half is what Rosser later keeps. |
Part VIII — Self-Test
1. State (L1a) and why it needs no consistency.
Answer
S⊢H(h̄) ⟺ h∈P*. It's the definition of P* plus the provable equivalence of H(h̄) and E_h(h̄) — pure syntax, no consistency.
2. Why does Theorem 1 need "negation represents P*" while Ex 2 needs no consistency at all?
Answer
Theorem 1 pits refutable against provable (p⟺q, two models — consistency prunes the inconsistent one). Ex 2 pits provable against its complement (b⟺¬b, zero models — self-refuting in the metatheory). (V.1)
3. Give the two-step structure of Ex 5 and which hypothesis powers each.
Answer
Step 1 enumerate — powered by "all true Σ₀ provable"; Step 2 Lemma ω lift to representable — powered by ω-consistency.
4. In Ex 6, what single thing does decidability do?
Answer
Converts "n∉A ⇒ no instance provable" into "every instance refutable" (enum clause 2); ω-consistency does the rest.
5. Why is Ex 3 not a restatement of Ex 2?
Answer
Ex 2 forbids a system representing its own P̃*; Ex 3 concerns a consistent extension representing S's P̃*. Completeness collapses the second to the first. (V.2)
6. Where in Ex 7 does the proof of A* actually diverge from A?
Answer
The refutable branch: under A it's excluded (witness stays G); under A* part (2)'s true-unprovable Y, with ~Y a false Σ₀ (unprovable by A*'s hypothesis), is the witness. (Part IV)
7. State Theorem 3's two clauses and the consistency strength each needs.
Answer
(1) G not provable — simple consistency; (2) G not refutable — ω-consistency.
8. Reconstruct the pipeline axiomatizable ⟶ incomplete.
Answer
axiomatizable ⇒ P* Σ₁; Ex 5 ⇒ P* representable (needs all-true-Σ₀-provable + ω-consistency); Theorem 3 ⇒ G undecidable = Theorem A.
Part IX — Position, owed items, debts
Position: Chapter V, Part I complete (pp. 58–65). Owned: Lemma 1, Theorem 1/1′ + Corollary, Lemma ω, Theorem 2, Theorem 3/3′, Theorem A and its self-strengthening Theorem A*; Exercises 1–7 worked (5 & 6 corrected against the page). The arc G ⟸ A+B+axiomatizability is mapped end-to-end for Part I.
Next in the book: Chapter V, Part II — "Σ₀-Completeness" (Proposition 1's conditions C₁ "every atomic Σ₀-sentence correctly decidable" and C₂, jointly sufficient for Σ₀-completeness) ⟶ Theorem B, and its strengthening to true-Σ₁-provable — the Σ₁-completeness bridge owed since July 28, expected paid there. That closes Theorem G.
Owed, standing (unchanged, July 24–29): 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 (start/finish matched to the page, labelled steps citing owned glossary anchors only); the arc as a significance pipeline; five conceptual deep-dives recorded because they carried the session's real weight (the A/A* polarity trap and the object-vs-meta account of Ex 2 especially). Two tutor errors caught by the reader's scrutiny and 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), 29 (Ch. IV Appendix Ex 1–8 + Ch. V prelude pp. 56–58). This file: Ch. V Part I pp. 58–65 — the abstract incompleteness theorems, Theorem A/A*, Exercises 1–7.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月30日学习记录 · Smullyan《哥德尔不完备定理》第五章,“哥德尔基于ω一致性的证明”,第一部分“若干抽象不完备定理”,书第58–65页 · 7月15–29日记录的续篇 · 性质:一次实作学习,将从对角引理到顶点定理A及其自我加强版定理A*的完整路线梳理为流程,然后把练习1–7做成有理由支持的链条,再深入五项概念问题:A/A*的“最后一步”、不一致与矛盾、自身表示与交叉表示、可判定性的作用、枚举≠表示。本次学习中,对照原书练习5、6的准确措辞发现了两处辅导者错误;这里记录的是纠正后的版本。**
交叉引用可点击:L1a、引理ω、定理1、练习5等引文会跳到正在引用的定义或结果。
本文的组织方式
第一部分是术语表,所有定义,加上对角引理1,作为链接目标。第二部分是路线:抽象定理逐步上升到定理A/A*的流程,本次学习的任务1。第三部分以链条完成练习1–7,每题的起点,假设,与终点,结论,都对应原书,只引用已掌握标号。第四部分深入练习7,即开启本次学习的A与A*之“最后一步”。第五部分收集五项概念深入讨论。第六部分记录学习过程中作出的两处纠正,错误在案。第七部分为区分清单,第八部分为自测,第九部分为进度与未清事项。
记号: 普通Unicode。n̄=命名n的数码。S⊢X=“X在S中可证”。除非另加下标,一切都相对于系统S。
第一部分——术语表:定义与对角引理
- Σ₀=只含有界量词,可判定;真/假的
Σ₀句子能被识别为真/假。承接7月29日。 - Σ₁=
∃y(Σ₀主体)。 - P*=
{ n : Eₙ(n̄)在S中可证 },即对角可证性集合;Eₙ=哥德尔数为n、具有一个自由变量的公式。 - R*=
{ n : Eₙ(n̄)在S中可反驳 },对角可反驳性集合。 - 表示,在S中表示集合/关系:
F(v₁)表示A,当且仅当对所有n,S⊢F(n̄) ⟺ n∈A。可证性概念。 - 表达,在标准模型中表达集合:
F(v₁)表达A,当且仅当对所有n,F(n̄)真⟺n∈A。真理概念。第二章,与表示对照。 - 枚举:
F(v₁,v₂)枚举A,当且仅当条件1,n∈A⇒对某个m,S⊢F(n̄,m̄);条件2,n∉A⇒对每个m,F(n̄,m̄)在S中可反驳。 - 可公理化=形式的=递归可枚举:可证公式编码组成一个Σ₁集合。那么P*是Σ₁,上一章:
A为Σ₁⇒A*为Σ₁。 - 简单一致:没有句子与其否定都可证。
- ω一致:没有
F(v₁)使S⊢∃v₁F(v₁),却每个F(n̄)都可反驳。ω一致⟹简单一致,见7月29日。 - 正确:每个可证句子都为真,第四章的假设,
S ⊆ N。
引理1——对角记账,纯粹的,不假设一致性
对任意哥德尔数为h的公式H(v₁):
根据: H(h̄)与H[h] = E_h[h]在S内部由带等号的一阶逻辑可证等价,而h∈P*恰好意味着S⊢E_h(h̄)。下面每个定理都由这一个引理驱动。
作为链接目标的各定理
- 定理1,对角不完备性:
S简单一致,且某个H(v₁)的否定表示P*⟹H(h̄)不可判定。 - 推论:P*可表示且
S一致⟹S不完备。 - 定理1′,对偶:R*可表示且
S简单一致⟹S不完备。 - 引理ω,ω一致性引理:
Sω一致,且F枚举A⟹∃v₂F(v₁,v₂)表示A。 - 定理2:P*或R*可枚举,且
Sω一致⟹S不完备。 - 定理3,哥德尔句的精细版本:
A(v₁,v₂)枚举P*;h=∀v₂~A(v₁,v₂)的哥德尔数;G := ∀v₂~A(h̄,v₂)。则(1)简单一致⟹G不可证;(2)ω一致⟹G不可反驳。 - 定理3′,关于R*的对偶。
- 定理A:可公理化+ω一致+所有真的Σ₀可证⟹不完备。
- 定理A*:可公理化+ω一致+没有假的Σ₀可证⟹不完备。严格更强,假设更弱。
- 定理B:所有真的Σ₀句子都在P.A.中可证。第二部分,即待完成的Σ₁完备性桥梁。
- 定理G:P.A.ω一致⟹不完备。=通过B+可公理化,把A应用于P.A.。
第二部分——路线:从对角引理到定理A(*)
本章的目标链条。
定理G ⟸ 定理A + 定理B + “P.A.可公理化”
定理A ← 第一部分,本次学习
定理B ← 第二部分,下一步:Σ₀完备性
第一部分的全部工作就是定理A,通过逐渐更具体的抽象定理抵达它。骨架如下,每一步命名其增加的内容:
步骤1,定理1:究竟什么使系统不完备。 若H的否定表示P*,则H(h̄)可反驳⟺h∈P*;(L1a)给出H(h̄)可证⟺h∈P*。因此可证⟺可反驳;在简单一致性下,除非两者皆不成立,否则不可能。句子落入间隙。得到推论,P*可表示⇒不完备,以及其对偶定理1′。
步骤2,障碍。 定理1需要P*可表示,这是可证性一侧的困难条件。低成本获得的是更弱的可枚举。我们需要桥梁。
步骤3,引理ω:桥梁,也是ω一致性进入整座建筑的位置。 ω一致性把可枚举升级为可表示。关键在n∉A方向:此时每个F(n̄,m̄)可反驳,因此若∃v₂F(n̄,v₂)也可证,S就ω不一致。这是单向、带条件的蕴含,不是等价,见第五部分5。
步骤4,定理2。 结合1+3:P*或R*可枚举+ω一致⟹不完备。
步骤5,定理3:两种强度的分离,哥德尔实际的句子。 用A枚举P*,∀v₂~A(v₁,v₂)就是否定表示P*的公式;其对角句为G = ∀v₂~A(h̄,v₂)。收获在于不对称性:(1)G不可证只需简单一致;(2)G不可反驳需要ω一致。定理的一半成本低,这使Rosser后来能够降到简单一致性。
步骤6,输入Σ₀,得到定理A。 可公理化⇒P*为Σ₁;练习5,所有真的Σ₀可证⇒Σ₁可枚举,再用引理ω,⇒P*可表示;定理3⇒不可判定的G。∎
步骤7,自我加强的定理A*。 其假设“没有假的Σ₀可证”严格弱于“所有真的Σ₀可证”;给定一致性,后者蕴含前者。由练习7直接证明;定理A随后作为推论得出。见第四部分。
一行地图:可表示性是定理1所需;可枚举性是你能得到的;ω一致性,即引理ω,是将后者转成前者的通行费;Σ₀可证性,即练习5,则是首先让可公理化的P*变得可枚举的东西。
第三部分——练习1–7的链条
每题按原书的表述开始和结束,练习5、6逐字来自第62页裁图,其余来自第60–65页。
练习1——直接得到不可判定性,不用双重否定
起点: S一致;H(v₁)表示P*;h=~H(v₁)的哥德尔数。终点: H(h̄)不可判定。
因此H(h̄)可证⟺可反驳⟺h∈P*。若h∈P*,两者都成立,一致性禁止。因此h∉P*,两者都失败,不可判定。∎ 不用双重否定律,是相对于定理1路线的优势。
练习2——P̃*永远不可表示,一致性无关
起点: F(v₁)表示P̃*,即P*的补集,任意S。终点: 不可能。
令f=F的哥德尔数。(L1a):S⊢F(f̄) ⟺ f∈P*。表示P̃*:S⊢F(f̄) ⟺ f∉P*。连接:f∈P*⟺f∉P*,元理论矛盾。未使用一致性,两侧都是可证性双条件式。∎ 这回答定理1后的问题:表示P*的公式,而非其否定表示该集合的公式,只会给出两遍(L1a),即重言式;要强行得到矛盾,需要P̃*可表示,而这恰恰是不可能的。深入阅读:第五部分1。
练习3——P̃*在一致扩张中可表示⇒S不完备
起点: S的P̃*在一致的S′ ⊇ S中被表示。终点: S不完备。
逆否命题:假设S完备,且一致,位于一致的S′内部。那么S与S′证明相同句子:S⊢X ⇒ S′⊢X;以及S′⊢X ⇒ S⊢X,否则完备性给出S⊢~X,于是S′⊢~X与S′⊢X并存,S′不一致。表示只依赖哪些F(n̄)可证,因此“在S′中表示P̃*”=“在S中表示”,与练习2矛盾。故S不完备。∎ 关系: 这是练习2/推论的稳健形式。下标追踪的细节见第五部分2。
练习4——正确系统中的真值,S ⊆ N
h=H(v₁)的哥德尔数;正确⟹一致。
- (1)
~H表示P*。如练习1:h∉P*,所以H(h̄)不可证。H(h̄)是不动点,断言h∉P*,即自身的不可证性,这正确⟹H(h̄)为真。 - (2)
H表示并且表达R*。(L1a)+表示:S⊢H(h̄) ⟺ h∈P*⟺h∈R*;(L1b):可反驳⟺h∈R*。一致性⟹h∉R*⟹不可判定。表达R*:H(h̄)真⟺h∈R*;h∉R*⟹H(h̄)为假。
对照:(1)通过正确性,在不可证性不动点上固定真值;(2)通过明确的表达固定真值,值相反。
★练习5——所有真的Σ₀可证并且ω一致⇒每个Σ₁集合可表示★
定理A中承担关键作用的引理。 原书原文意为:“若所有真的Σ₀句子都在S中可证,并且Sω一致,则所有Σ₁集合都在S中可表示。”结论是可表示性,ω一致性是一个假设,这就是全部要点。
起点: P,所有真的Σ₀可证;ω,Sω一致。终点: 每个Σ₁集合可表示。
令A为Σ₁:A = {n : ∃m R(n,m)},R为Σ₀关系;A(v₁,v₂)是表达R的Σ₀公式。
- 步骤1,枚举,使用P。
n∈A⇒某个R(n,m)⇒A(n̄,m̄)为真的Σ₀⇒由P可证。→枚举条件1。n∉A⇒每个R(n,m)为假⇒每个~A(n̄,m̄)为真的Σ₀⇒由P可证⇒每个A(n̄,m̄)可反驳。→枚举条件2。- 步骤2,表示,使用ω。 由引理ω,
∃v₂A(v₁,v₂)表示A。∎
为什么这是关键。 可公理化⇒P*为Σ₁;本练习随后使P*可表示,送入定理3。两个假设在不同步骤承担作用:P买到枚举,ω买到提升,即引理ω。假设P恰好是定理B为P.A.提供的。
练习6——练习5背后的抽象机制
原书原文意为:“假设F(v₁,v₂)在S中表示与它所表达的相同关系,且对所有n,m,句子F(n̄,m̄)或者可证或者可反驳。证明,若Sω一致,则∃v₂F(v₁,v₂)在S中表示与它所表达的相同集合。”
起点: (a)对所有n,m:S⊢F(n̄,m̄) ⟺ F(n̄,m̄)真,即对该关系而言表示=表达;(b)每个F(n̄,m̄)可判定;(c)Sω一致。终点: ∃v₂F表示它所表达的集合。
令A = {n : ∃m F(n̄,m̄)真}=∃v₂F所表达的集合。
- 步骤1,
F枚举A。 n∈A⇒某个F(n̄,m̄)真⇒由(a),某个S⊢F(n̄,m̄)。→条件1。n∉A⇒每个F(n̄,m̄)假⇒由(a),每个都不可证⇒由(b),每个都可反驳。→条件2。- 步骤2,引理ω,使用c。
∃v₂F表示A。∎
各假设去向:(a)用于两个条件,真⟺可证的桥梁;(b)仅用于条件2,把不可证→可反驳,这是它唯一的工作;(c)用于引理ω的提升。练习6=抽象化的练习5:相同的两步形状,“实例上表示=表达”抽象“所有真的Σ₀可证”,可判定性抽象Σ₀可判定性。
练习7——自我加强,完整解答见第四部分
起点: S可公理化;A(v₁,v₂)枚举P*,并表达一个Σ₀关系R;h=∀v₂~A(v₁,v₂)的哥德尔数;G := ∀v₂~A(h̄,v₂)。终点: (1)G可证⇒某个假的Σ₀可证;(2)G可反驳+ω一致⇒某个真的Σ₀不可证;(3)定理A随之成立。
通过(L1a)固定关系:S⊢G ⟺ h∈P*⟺∃y R(h,y)真。 完整推导与A/A*问题的解决见第四部分。
第四部分——深入练习7:A与A*的“最后一步”
本次学习从这里开始。困惑是,印出的解答步骤3以“现在假设所有真的Σ₀句子都在S中可证”开头,这是定理A的假设,而非A*的。解决如下。
(1)G可证⇒一个假的Σ₀可证。 S⊢G⇒h∈P*⇒某个n使R(h,n)真⇒A(h̄,n̄)为真的Σ₀⇒~A(h̄,n̄)假。但G=∀v₂~A(h̄,v₂)可证⇒实例~A(h̄,n̄)可证。一个假的Σ₀可证。∎ 只用表达+已固定关系,没有可证性假设。
(2)G可反驳+ω一致⇒一个真的Σ₀不可证。 G可反驳⇒~G = ∃v₂A(h̄,v₂)可证。而且G可反驳+简单一致⇒G不可证⇒h∉P*⇒每个R(h,n)假⇒每个~A(h̄,n̄)为真的Σ₀。对可证的∃v₂A(h̄,v₂)用ω一致性:并非所有A(h̄,n̄)可反驳⇒某个A(h̄,n̄)不可反驳⇒那个~A(h̄,n̄)不可证,即一个真的Σ₀不可证。∎
(3)按印出版本=定理A,即推论。 假设所有真的Σ₀可证+ω一致:
| 步骤 | 动作 | 根据 |
|---|---|---|
| 所有真的Σ₀可证⇒没有假的Σ₀可证 | 假Σ₀有一个真的Σ₀否定,可证;一致性禁止两者并存 | 简单一致 |
⇒G不可证 |
(1)的逆否命题 | 练习7(1) |
所有真的Σ₀可证⇒G可反驳⇒ω不一致 |
(2)的逆否命题 | 练习7(2) |
为什么这不是A*,A*究竟在哪里。 印出的步骤3假设了强条件,因此证明A;周围文字所说的“A*直接证明,A作为推论”,由(1)+(2)自身承担:
- (1)是A*原生的步骤:“没有假的Σ₀可证”⇒
G不可证,直接得到。 - 可反驳分支是A与A*分歧的地方:
- A,强假设:(2)的结论“某个真的Σ₀不可证”不可能,因此该分支被排除,见证仍为
G。 - A*,弱假设:(2)交给你一个真的Σ₀句子
Y,不可证;那么~Y是假的Σ₀,所以A*的假设也使~Y不可证,Y就是不可判定的见证。
准确的陷阱: 步骤3中的“某个真的Σ₀不可证”,来自(2),是作为输出推导出的A假设的否定,并非作为输入假设A的条件。“可证”一词出现了,但极性相反。在A*下,那个不可证的Y配上其不可证的假否定,就是不完备性,因此证明确实直接而且“提供更多信息”:在A*的假设下,或者G不可判定,或者某个Σ₀句子不可判定,每种情形都有具体见证。
第五部分——概念深入讨论
V.1——不一致,对象层、偶然的,与矛盾,元层、必然的:为什么练习2不需要一致性
模型计数。 定理1推出p ⟺ q,其中p=“S⊢H(h̄)”、q=“H(h̄)可反驳”,是两个独立陈述。p=q有两个解:(T,T)=不一致,(F,F)=不可判定。一致性是删除(T,T)的前提,留下(F,F)。练习2对单个b=“f∈P*”推出b ⟺ ¬b,零个解。无须剪枝,假设自我消灭。
一致性位于何处。 一致性就是“可反驳⇒不可证”原则,即P*∩R*=∅。一个论证当且仅当让可反驳性与可证性相对抗时才需要它。定理1使用“否定表示P*”,即可反驳性,必须购买不相交性。练习2只用可证性及其布尔补集,元逻辑自身的不矛盾律就足够。
识别标志: 练习2甚至对不一致的S也成立,此时P*=全部,P̃*=∅,不可表示,因为一切都可证。对不一致系统也为真的定理,不可能使用过一致性;它是关于元语言的主张,而非对象系统。用等势框架说:可证/可反驳双条件式是真正的平衡,需要外部裁决;b⟺¬b不是平衡,而是自我取消。
V.2——练习3:隐藏的下标,自身表示与交叉表示
P*相对于某个系统:P*_T = {n : Eₙ(n̄)在T中可证}。练习2只禁止P̃*_T在T中可表示,集合与表示系统锁定在同一个T,因为(L1a)的自指需要一个系统同时担任两个角色。练习3问的是P̃*_S在S′中可表示,不同的系统;下标不匹配,因此练习2不适用。更强的S′可以比S更了解S的不可证性,因此交叉表示先验地可能。完备性重新锁定下标,S、S′证明相同句子,使交叉坍缩为自身,练习2终于发挥作用。总的结论严格强于练习2:除非S不完备,否则没有一致扩张能表示S的P̃*。
一行分类: 练习2=“A不能表示A自己的P̃*”,无条件;练习3=“若一致扩张B⊇A表示A的P̃*,则A不完备”,有条件,其逆否命题才是“不可能性”读法,而且仅在完备性之下。
V.3——练习6:可判定性唯一的工作
∃v₂F(n̄,v₂)可证弱于某个实例F(n̄,m̄)可证;系统可以证明存在句,而没有可证见证。ω一致性禁止这一病态;可判定性唯一的角色是把“n∉A⇒没有实例可证”变成“每个实例可反驳”,即枚举条件2,然后由引理ω的矛盾论证使用。
V.4——练习5/练习6是同一证明运行两遍
两者都是先枚举,再用引理ω。练习6抽象陈述机制,“所有实例上可证与真一致,且全部可判定”;练习5是其Σ₀/Σ₁实例,“所有真的Σ₀可证”使A(v₁,v₂)在Σ₀实例上可证与真一致;Σ₀可判定性自动成立。两者成败都取决于枚举→表示的提升。
V.5——枚举≠表示,单向且带条件的蕴含
不是等价。可枚举⇒可表示只在ω一致性下成立,即引理ω,ω一致性承担实质作用。可表示⇒可枚举同样不是免费的:可表示性对n∉A给出F(n̄)不可证,但枚举条件2要求可反驳,严格更强。混同两者会恰好隐藏ω一致性进入不完备证明的位置;在主题就是这一入口的章节中,这正是必须抵制的简化。
第六部分——本次学习中的纠正:把发现的错误记录在案
- 把练习5误述为只得出“可枚举”。 依据错误抄录,辅导者起初声称练习5停在可枚举性,不使用枚举→表示联系,还“纠正”了说会使用它的读者。原书练习5结论是可表示,并以ω一致性为第二假设。读者是对的:练习5确实分两步,通过P枚举,然后通过ω用引理ω。已在第三部分纠正。
- 编造练习6的假设。 辅导者给出虚构的“(★)
n∈A ⟺某个F(n̄,m̄)可证”。原书实际假设是“在S中表示与其所表达的相同关系”,即S⊢F(n̄,m̄) ⟺ F(n̄,m̄)真,再加可判定性;结论是“∃v₂F表示与其所表达的相同集合”。已在第三部分纠正;可判定性的作用在V.3重新推导。
发现两者的方法:把回顾与页面的准确字符对照,这是7月25/26/29日持续适用的教训。 两项修正都从读者自身的仔细检查中浮现:“我们怎么知道F枚举A?”;“练习5依赖枚举≡表示,对吧?”
第七部分——区分清单
| 提出的问题 | 解答 |
|---|---|
| 为什么定理1需要“否定表示P*”,而不是“表示”? | 表示P*只给出两遍(L1a),重言式;可反驳性一侧,即否定表示,才使可证⟺可反驳。直接表示P*的路线需要P̃*可表示,不可能,见练习2。 |
| 为什么练习2不用一致性? | 它推出b⟺¬b,元矛盾、零模型,而非p⟺q,对象不一致、两个模型。一致性=“可反驳⇒不可证”;练习2从不触及可反驳性。甚至对不一致的S成立。见V.1。 |
| 为什么练习3没有被练习2涵盖? | P*以系统为下标。练习2把集合与表示者锁定在同一个T;练习3跨系统,P̃*_S在S′中。完备性重新锁定两者。见V.2。 |
练习3的S′⊢X ⇒ S⊢X一行 |
S的完备性+S′的一致性:若S⊬X,则S⊢~X,所以S′⊢~X,与S′⊢X冲突。完备S特有,不完备S在扩张下增长。 |
| 练习7步骤3似乎假设了A的条件 | 因为它就是在证明A,即推论。(2)中的“某个真的Σ₀不可证”是A的假设作为输出被否定,而非被假设。A*位于(1)+(2),并转移到Y。见第四部分。 |
| 枚举≡表示吗? | 不是,单向且以ω为条件,见引理ω;反向也不免费,不可证≠可反驳。见V.5。 |
| 练习6中的可判定性有什么用? | 只把“没有实例可证”变为“每个实例可反驳”;ω一致性完成到表示的提升。见V.3。 |
怎么知道练习6中F枚举A? |
不是给定,而是从(a)表示=表达+(b)可判定性推导出来。枚举是你首先要证明的东西。 |
| 定理3的两个条件按强度分离 | (1)不可证←简单一致;(2)不可反驳←ω一致。成本低的一半是Rosser后来保留的。 |
第八部分——自测
1.陈述(L1a),并说明为什么它不需要一致性。
2.为什么定理1需要“否定表示P*”,而练习2完全不需要一致性?
3.给出练习5的两步结构,以及每一步由哪个假设支持。
4.练习6中,可判定性只做哪一件事?
7.陈述定理3的两个条件,以及各自需要的一致性强度。
8.重构可公理化⟶不完备的流程。
第九部分——进度、待办与未清事项
进度:第五章第一部分完成,第58–65页。已掌握:引理1、定理1/1′+推论、引理ω、定理2、定理3/3′、定理A及其自我加强版定理A*;练习1–7已完成,5与6对照页面纠正。路线G⟸A+B+可公理化,其第一部分已从头到尾梳理。
书中下一步:第五章第二部分,“Σ₀完备性”,命题1的条件C₁,“每个原子Σ₀句子可正确判定”,与C₂,合起来足以得到Σ₀完备性,⟶定理B,以及加强为真的Σ₁可证;自7月28日起待完成的Σ₁完备性桥梁,预计在那里完成。这会完成定理G。
持续待办,7月24–29日以来未变: 7月27日原书核对,纯1框架引理K的连续段合并、w=1时的因子刻画、§5中x=0的措辞;更早项目,L₂/L₃字符串、N₁₂子关系、L₃分情况检查、祖先解释的证伪、全论域实例问题、7月26日字符核对。未清事项登记:性质1⇒性质2、机械性⇒算术性、1930年的恰切性、1931年一般机器形式、操作一致、从L₆+L₇得到实例化。β函数证明,评注2,仍搁置。
方法说明。 练习按已经确定的链式格式完成,起点/终点对应页面,带标号步骤只引用已掌握术语表锚点;路线作为阐明意义的流程;记录五项概念深入讨论,因为它们承担了本次学习真正的分量,尤其A/A*的极性陷阱,以及对练习2的对象层与元层解释。通过读者的仔细检查,以及把草稿与页面对照,发现两处辅导者错误;记录版本已纠正。
此前学习:7月15日,第一章;17日,答案;19–22日,第二章;20日与23日,练习;24日及25日续篇,第三章§1;26日,第三章§§2–4;27日,第四章第40–50页、定理E;28日,第四章第50–55页;29日,第四章附录练习1–8与第五章前奏第56–58页。本文件:第五章第一部分第58–65页,抽象不完备定理、定理A/A*、练习1–7。