Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter III Opening: The Axiom System P.E., Interpretations, and the Adequacy/Incompleteness Divide
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 to use this document
- Part I — The Axiom System P.E.: what an axiom is
- Part II — The material conditional, and the meanings of L₁–L₇
- Part III — Interpretations, and the two orders of logic
- Part IV — Adequacy vs incompleteness: the glossary and the three theorems
- Part V — Chain 1: the second-order sentence A pins down ℕ (Dedekind)
- Part VI — The syllogism, the corollary, and the consolidation
- Part VII — The rebuilt chain: first-order Σ does not compress ℕ
- Part VIII — Distinctions Ledger
- Part IX — Self-Test
- Part X — Position, pending items, debts, and the method
- Part XI — Second continuation (July 25): the N₁₂ brackets are the July 22 wrapper; replacement vs substitution
Study session of July 24, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter III §1 (book pp. 28–30) · Companion to the sessions of July 15, 17, 19, 20, 21, 22, and 23, 2026 · Chapter III begun: §1 conceptually consolidated; the chapter's formal work (§2 arithmetization onward) untouched · Second continuation of July 25, recorded as Part XI: the Group II–IV strings corrected against the book's page, the Discussion paragraph's substitution-avoidance claim unpacked, and the N₁₂ brackets recognized as the July 22 wrapper
How to use this document
Not an exercise session — a consolidation session, and the first one driven entirely by the reader's questions rather than the book's sequence. The opening pages of Chapter III display nineteen "axiom schemes," and the session began from an honest confession: these don't look like universally true axioms; they look like sentence structures one can judge about. That instinct turned out to be exactly right, and pulling on it unspooled the whole day: what an axiom is here (a chosen correct formula, not a self-evident truth) — in what sense correct (two different senses for two different groups) — what the material conditional ⊃ actually means (a table, not English "if–then") — what an interpretation is (the load-bearing term that had been used undefined) — what "first-order" means and what second-order grammar adds — and then the long excursus: why the 1930 adequacy theorem and the 1931 incompleteness theorem, despite their colliding names, not only don't contradict but compose, and why second-order logic can have no adequate machine at all. The excursus was won in stages, with several failed explanation attempts recorded in Part X, and ended with the session's structural discovery, made by the reader: the entire apparatus built to answer "why can't first-order compress?" is dispensable — Chain 1 (Dedekind), a six-step syllogism, and a four-line corollary satisfy the need, and the rest folds away into one line ("first-order lacks ∀P").
And then a post-session continuation un-dropped it, in improved form. The reader returned to "why is R not carved?", challenged an apparent circularity in the answer, and demanded the arrow directions of the whole argument. The resolution became Part VII: a single chain with a stated objective, two checkboxed verdicts, and every justification a citation — replacing the dropped scaffolding with something owned. Cross-references throughout this file are live links: every justification points at the rule, definition, theorem, or step it uses.
A second continuation followed on July 25, triggered by the reader holding this file against the book's own pages 29–30. It is recorded as Part XI: three misstatements in Parts I–II caught and corrected in place (marked), the book's claim that substitution — and even free/bound occurrences — are circumvented, unpacked (replacement vs substitution), and the square brackets of the induction scheme recognized — by the reader, before being told — as the July 22 wrapper returning for a harder job.
Everything here is aerial commentary: a second vantage point on the mountain the book climbs by a different route. Smullyan's Chapter III never mentions interpretations, survivors, or machines-as-printers; his proof is strings and diagonalization. Nothing in this file is a prerequisite for the book — but the axioms of P.E. can now be seen for what they are: the best a first-order system can do, chosen correct and shape-recognizable, with no pretense of pinning down ℕ.
Scorecard, for honesty. No book exercises were attempted. The reader's contributions: (i) before being told, identified the axiom schemes as templates rather than truths — the scheme/instance distinction, found independently; (ii) caught the term "interpretation" doing load-bearing work while undefined, and forced the glossary; (iii) produced his own account of the first-/second-order divide, graded piece by piece — core correct, two errors fixed; (iv) located the exact stalling joint of Chain 1's first draft (Steps 2→4→5), which exposed an unstated evaluation rule; (v) the consolidation itself — recognizing which parts of a week's scaffolding are load-bearing and which can be dropped; (vi) in the continuation, challenged the R-uncarved argument as circular — forcing the separation of the conditional theorem from the existence theorem — and proposed his own chain for grading, which exposed that adequacy had been misplaced as a conclusion when it is a premise; (vii) rejected a metaphor-laden anatomy paragraph ("credentials," "inflates," "the wall"), whose forced expansion caught a genuine error in the argument (see B18). Three owed answers are still outstanding (Part X). The July 25 continuation added three more contributions: (viii) caught this file misstating L₅, L₇, and N₁₂ by comparing it against the book's own page; (ix) recalled the July 22 wrapper unprompted ("we had our own version of substitution via a wrapper — what is different here?"), which became the organizing question of Part XI; (x) pressed a precise objection against the double-guarded string ("it still reads like v₁ = v₁′ — a contradiction?") whose resolution — the regions analysis — is the sharpest item in Part XI.
Part I — The Axiom System P.E.: what an axiom is
The system. P.E. = Peano Arithmetic with Exponentiation (standard PA has only + and ·; Smullyan adds E to smooth the Gödel argument, and later shows how to eliminate it). Axioms come in nineteen mechanically recognizable forms, in four groups: Group I (L₁–L₃, propositional logic), Group II (L₄–L₇, first-order logic with identity), Group III (N₁–N₁₁, eleven arithmetic axioms), Group IV (the induction scheme). Count: 3 + 4 + 11 + 1 = 19. Two inference rules: modus ponens (from F and F ⊃ G, get G) and generalization (from F, get ∀vᵢF). Provable = reachable from axioms by rules.
Scheme vs axiom — the session's first correction, made by the reader before it was taught. L₁ is displayed as (F ⊃ (G ⊃ F)). This is not a formula of the language: F and G are not symbols of P.E. It is a stencil at the level where we talk about formulas — the same metalanguage level where r, d, f lived in Chapter II. The axioms are the instances: plug in actual formulas (e.g. F := (0̄ = 0̄), G := (0̄ ≤ 0̄)) and a genuine axiom appears. Groups I, II, IV are stencils with infinitely many instances each; Group III's odd title ("schemes having only one axiom apiece") means N₁–N₁₁ are ordinary single formulas — stencils with nothing to fill.
"Correct" in what sense. Exactly the Chapter II sense, nothing more mystical: a sentence is correct iff true in the intended interpretation; a formula with free variables is correct iff true for every value of them. So (v₁ + 0̄) = v₁ is correct because 0+0=0, 1+0=1, 2+0=2, … — end of story. "Axiom" here means "designated correct starting formula," chosen under three constraints: (a) correct — else the engine generates falsehoods; (b) recognizable by shape alone — a dumb procedure can check axiomhood, which is what §II's arithmetization will feed on; (c) strong enough for the chapter's purpose. The choice is a toolkit, not a discovery — Smullyan credits Groups I–II to Kalish–Montague 1965; other books choose different equivalent lists.
Two senses of correct, for two kinds of group. Every instance of Groups I–II is true in every interpretation whatsoever — true by the meaning of ⊃, ∼, ∀, = alone, subject matter irrelevant ("valid"). Groups III–IV are true of ℕ specifically and can fail elsewhere: on a twelve-hour clock, ∼(0̄ = v₁′) is false (11′ = 0). Each arithmetic axiom is a filter that disqualifies rival interpretations.
The ladder (Dedekind–Peano). The idea behind the arithmetic axioms: ℕ is a ladder — a bottom rung 0; every rung has a unique next (′); 0 is nobody's next; different rungs have different nexts; and induction — anything holding at 0 and climbing holds everywhere (no side-branches, no unreachable rungs). Then +, ·, E, ≤ are not extra assumptions but recursion recipes riding on the ladder: n + 0 = n and n + m′ = (n + m)′ pin down every addition fact. Worked in session:
3 + 2 = 3 + 0′′ = (3 + 0′)′ = ((3 + 0)′)′ = ((3)′)′ = 5
— each equality by one of the two addition axioms. Multiplication is repeated addition (n·0 = 0, n·m′ = n·m + n), E is repeated multiplication (n E 0 = 1, n E m′ = (n E m)·n), and ≤ is characterized stepwise (n ≤ 0 iff n = 0; n ≤ m′ iff n ≤ m or n = m′; any two numbers comparable). Group IV is the domino principle, one instance per formula F(v₁):
N₁₂ : (F[0̄] ⊃ (∀v₁(F(v₁) ⊃ F[v₁′]) ⊃ ∀v₁ F(v₁)))
[Corrected July 25 — an earlier draft of this file displayed the scheme with literal substitution, F(0̄) and F(v₁′). The book's axiom uses the bracketed F[0̄] and F[v₁′] — the July 22 wrapper — precisely so that F rides unopened; the substitution version is the equivalent the brackets are proved to match, not the axiom. See Part XI.]
Engine vs subject matter. Groups I–II are a subject-neutral reasoning engine (they'd be identical in a formalization of geometry); Groups III–IV are the arithmetic seed. The rules preserve correctness, so everything provable is correct (soundness). The theorem the chapter drives toward is the converse failing: some correct sentence is unprovable. The magic is not in the axioms; it is in the gap between what they generate and what is true.
Part II — The material conditional, and the meanings of L₁–L₇
The table, and why it is forced. F ⊃ G is defined by: false when F true and G false; true in the other three cases. This is not a claim about English — it is the price of making "for every n: F(n) ⊃ G(n)" mean "there is no counterexample." Check "if n is divisible by 4 then n is even" at n = 8 (T,T), n = 6 (F,T), n = 3 (F,F): none of these should break the universal claim; only a divisible-by-4 odd number (T,F) would. So rows 1, 3, 4 must count as true. Consequences the reader resisted, rightly, as clashing with everyday "if–then": whenever the consequent is true, the conditional is true; whenever the antecedent is false, the conditional is true ("if 1 = 0 then 0 = 0" is true). The clash is famous — the paradoxes of material implication — and does not go away; ⊃ deliberately drops the English connection-requirement and keeps only truth-value bookkeeping, because bookkeeping is what a machine can check.
The logical schemes, each with its job:
- L₁ : (F ⊃ (G ⊃ F)) — "a truth is implied by anything." Verified by two cases: F true → G ⊃ F has a true consequent, so true, so the whole is T⊃T; F false → false antecedent, true outright. Every instance true regardless of what F, G mean: a tautology.
- L₂ : ((F ⊃ (G ⊃ H)) ⊃ ((F ⊃ G) ⊃ (F ⊃ H))) — distribution: modus ponens under a standing assumption. If from F you can get G ⊃ H, and from F you can get G, then from F you can get H. What lets the engine chain steps inside "suppose F…".
- L₃ : ((∼F ⊃ ∼G) ⊃ (G ⊃ F)) — contraposition: teaches the engine how ∼ interacts with ⊃; ancestor of proof by contradiction. [Case-check still owed by the reader — Part X.]
- These three plus modus ponens generate all tautologies (propositional adequacy — accepted, not proved).
- L₄ : (∀vᵢ(F ⊃ G) ⊃ (∀vᵢF ⊃ ∀vᵢG)) — ∀ distributes over ⊃.
- L₅ : (F ⊃ ∀vᵢF), provided vᵢ does not occur in F — vacuous quantification adds nothing. The side condition is essential: without it, (v₁ = 0̄ ⊃ ∀v₁(v₁ = 0̄)) would be an axiom — and it is false at v₁ = 0. [Corrected July 25 — an earlier draft said "not free in F." The book's condition is "does not occur at all," and the strengthening is deliberate: occurrence is a bare symbol-scan, freeness needs scope-parsing, and avoiding the latter is the system's design theme — Part XI.]
- L₆ : ∃vᵢ(vᵢ = t), provided vᵢ not in t — every term has a value. Side condition blocks ∃v₁(v₁ = v₁′).
- L₇ : (vᵢ = t ⊃ (X₁vᵢX₂ ⊃ X₁tX₂)), where X₁vᵢX₂ is an atomic formula (replacement of equals): if the variable vᵢ equals the term t, replacing one occurrence of vᵢ by t inside an atomic formula preserves truth — what makes = mean identity. Instance: (v₁ = 0̄′ ⊃ (v₁ ≤ 0̄′′ ⊃ 0̄′ ≤ 0̄′′)). [Corrected July 25 — an earlier draft wrote "if t₁ = t₂, swapping them inside an atomic statement," which is the derivable general form, not the axiom; the variable-not-term, one-occurrence, and atomic restrictions are each load-bearing — Part XI.]
Part III — Interpretations, and the two orders of logic
Interpretation — the term that had been undefined. A formula by itself is ink. An interpretation assigns: (1) a domain D — what ∀v₁ ranges over; (2) which object 0̄ names; (3) what ′, +, ·, E do to objects and when ≤ holds. Only then does every sentence become true or false. The intended interpretation: domain 0, 1, 2, …, symbols standard; correct (all of Ch. II) = true here. Rivals evaluated in session: the twelve-hour clock (passes (v₁ + 0̄) = v₁, fails ∼(0̄ = v₁′) since 11′ = 0) and the one-object world (even 0̄ = 0̄′ comes out true). Valid = true in every interpretation (Groups I–II). Logical consequence of given axioms = true in every interpretation that passes them.
Orders = what the quantifiers range over. Zeroth order: no quantifiers (propositional). First order: quantify over the domain's objects. ∀v₁((v₁ + 0̄) = v₁) covers all numbers — first-order universality over objects is total. Second order: additionally quantify over properties (= subsets of the domain): new variables P, Q; new atomic shape P(v₁); quantifier ∀P. The one thing first-order grammar cannot say is "for every property" — and that is where induction bites: Peano's own induction postulate is naturally second-order ("for every property: …"), and P.E. must fake it with a scheme, one axiom per formula-expressible property. The substitution is quietly lossy: formulas are listable (finite strings, finite alphabet — the Ch. II listing), sets of numbers are not (the Ch. II diagonal), so the scheme covers a countable slice of an uncountable totality of properties.
Corrected error (the reader's own formulation, graded): first-order logic does not fail to "cover all natural numbers" — it covers all numbers and cannot cover all properties. The entire divide between the orders is that one grammar clause.
Part IV — Adequacy vs incompleteness: the glossary and the three theorems
The names "completeness theorem" (1930) and "incompleteness theorem" (1931) collide by historical bad luck; the session renamed the first adequacy and kept "complete" for whole systems. The glossary, as fixed:
- Machine — a finite instruction list that mechanically emits ("prints") strings forever, by shape-checking alone. Every proof system determines one (print the axioms, apply the rules to what's printed). Prove = print. Mechanical = runnable by such a finite instruction list — no oracle, no infinite lookup.
- T — the set of sentences true in the intended interpretation.
- Passes / survivor — an interpretation passes axioms if it makes them all true.
- Copy of ℕ — ℕ with objects renamed; makes exactly the same sentences true.
- Impostor — a survivor that is not a copy of ℕ.
- Sound (for a target set) — prints nothing outside the target.
- Adequate — the engine prints every logical consequence of whatever axioms it is fed: print-set = consequence-set, exactly.
- Duty (of the engine, fed a stock of axioms) — the consequence-set itself: the sentences true in every survivor of that stock. So "adequate" = print list coincides with duty.
- Complete / incomplete (for a sound system) — prints all of T / misses some truth.
- Categorical — axioms whose only survivors are copies of one single world.
The three theorems, one line each:
- Dedekind 1888: the second-order Peano axioms are categorical. (A theorem about interpretations only — proof, machines, printing do not occur in it; those concepts didn't exist yet.)
- Gödel 1930 (adequacy): an adequate engine exists for first-order logic — Groups I–II plus the two rules. Whatever logically follows from your axioms, the machine prints; adding more valid logical axioms shortens proofs but never yields a new theorem. (For logic, the toolkit is provably finished — the answer to "are these 19 the only schemes?": the logical ones provably suffice; the arithmetic ones provably never can.)
- Gödel 1931 (incompleteness): no machine sound for T prints all of T. Equivalently, in the form Part VII uses (the machine limit): no mechanical machine prints exactly T — printing exactly T would be soundness plus completeness at once. (The book's theorem; Chapter III proves it for the specific system P.E., and the fully general machine form is earned in the later abstract chapters — same construction, widening radius.)
Why no contradiction — the see-saw. The engine's obligation is fixed by definition: print everything true in all survivors of the axioms — the duty. The duty's size therefore depends on the survivor pool: many survivors → few sentences true in all → small duty; few survivors → large duty. First-order axioms cannot drain the pool to copies of ℕ (B6 proves this outright), so the duty sits strictly below T — and the 1930 theorem shows that smaller duty is exactly machine-doable. The leak is not a bug adequacy overcomes; the leak is why the finish is reachable. Second-order axioms drain the pool to copies of ℕ (Dedekind = Chain 1), the duty inflates to all of T, and 1931 forbids any machine from covering it. Hence: the first-order engine is complete because its language is too weak to ask for the impossible; strong language or strong engine — never both. The deficiency of P.E. is never the engine's: unprovable truths are unprovable because they do not logically follow from the axioms — each is false in some surviving impostor.
Three ledgers, kept apart (a distinction won in the continuation): the survivor pool is a set of worlds; the duty and the print list are sets of sentences. "Impostors survive" is a pool-fact; "provables sit below truths" is a print-list-fact; adequacy is the weld making print list = duty. And only a loud impostor — one that disagrees with ℕ about some sentence — shrinks the duty; a quiet impostor (not a copy, yet agreeing with ℕ on every sentence) shrinks nothing. The arrow runs from the print-gap to the loud impostor (the four-line corollary), never backward.
Two attributions corrected in session: Dedekind did not prove "every truth is provable" (his theorem has no proof-concept in it); and 1930 does not say "all machines are adequate" (almost none are — it says at least one adequate engine exists, for first-order).
Part V — Chain 1: the second-order sentence A pins down ℕ (Dedekind)
The session's one fully-owned formal result, in the July 23 format: evaluation rules and definitions stated first as citable items, every string parsed before use, every step justified by name. The chain's first draft stalled at the reader's exact question — how does Step 2 lead to Step 4, and does Ind's content matter? — which exposed an unstated rule (R3, the instance rule). Stated, the stall dissolved.
Evaluation rules. A world M = (D, z, s): domain D, object z named by 0̄, operation s meant by ′.
- R1 (dictionary): 0̄ → z; t′ → s(t's value); t₁ = t₂ asserts sameness of objects; ∼, ∧, ⊃ by their tables.
- R2 (∀ over objects): ∀v₁φ true in M ⟺ for every object x of D, the instance at x (φ with v₁ read as x) is true. Uses: (i) one false instance falsifies the universal; (ii) a true universal may be cashed out at any chosen instance.
- R3 (∀ over properties): ∀Pφ true in M ⟺ for every subset S of D, the instance at S (φ with P(t) read as "t's value ∈ S") is true. R2 with subsets replacing objects as the index set; same two uses.
- R4 (the ⊃ row): true conditional + true antecedent ⇒ true consequent.
Definitions.
- D1 (passes/survivor), D2 (copy of ℕ), D3 (impostor) — as in Part IV.
- D4 (compresses): an axiom stock compresses ℕ if it is a single finite sentence whose survivors are exactly the copies of ℕ. (Extended in Part VII to infinite lists.)
- D5 (reachable part, junk/aliens): in (D, z, s): R := {z, s(z), s(s(z)), …} — the objects reached from z in finitely many s-steps. Objects outside R are junk, called aliens in Part VII. R is defined by us, in the metatheory — like r, d, f of July 22–23, it exists whether or not any formula describes it.
The strings, parsed.
S1 := ∀v₁ ∼(v₁′ = 0̄) — in M: "z is nobody's successor" (R1, R2)
S2 := ∀v₁∀v₂(v₁′ = v₂′ ⊃ v₁ = v₂) — in M: "different objects, different successors"
Ind := ∀P( (P(0̄) ∧ ∀v₁(P(v₁) ⊃ P(v₁′))) ⊃ ∀v₁ P(v₁) )
A := S1 ∧ S2 ∧ Ind — one finite string
Parse of Ind via R3 — the instances are indexed by subsets S of D:
Instance(S): "if z ∈ S and S climbs (x ∈ S ⇒ s(x) ∈ S, all x ∈ D), then every object of D is in S"
Ind in M: "for every subset S of D: Instance(S)"
First-order substitute — the scheme, one sentence per formula F(v₁):
Ind_F := (F(0̄) ∧ ∀v₁(F(v₁) ⊃ F(v₁′))) ⊃ ∀v₁ F(v₁)
Parse: with the carved set C_F := {x ∈ D : F is true of x in M} — set-builder notation: the set of all x in D such that F holds of x, a membership test, not an assertion; it is Chapter II's "the set F expresses," relativized from ℕ to the world M on trial — Ind_F in M says exactly Instance(C_F). So the scheme guarantees the conditional only at carved sets (one per formula, listably many); Ind guarantees it at every subset. C_F depends on both F and M: (v₁ = v₁) carves D, ∼(v₁ = v₁) carves ∅, and the Ch. II evenness formula carves the evens in ℕ. "R is carved in M" means: some formula F has C_F = R — coinciding exactly, not merely ⊆ or ⊇.
Chain 1. Given: the sentence A. Goal: every survivor of A is a copy of ℕ (D4).
Step 1. Let M = (D, z, s) survive A: S1, S2, Ind each true in M. (D1.)
Step 2. For every subset S of D, Instance(S) is true in M. (R3 applied to Ind's parse — this unpacking is all that "Ind true in M" means.)
Step 3. Let R := {z, s(z), s(s(z)), …}. (D5; metatheoretic — no formula describes R and none is needed.)
Step 4. R is a subset of D. (Step 3 — members produced by s inside D. The entry ticket: Step 2's guarantee is indexed by subsets, and subsethood is the sole qualification; describability appears nowhere.)
Step 5. z ∈ R. (Step 3 — reachable in zero steps.)
Step 6. R climbs. (Step 3 — one more s preserves reachability.)
Step 7. Instance(R) is true in M. (Step 2 cashed out at S := R, licensed by Step 4 — direction (ii) of R3. The sole step where second-order grammar acts.)
Step 8. Instance(R)'s antecedent is true: z ∈ R and R climbs. (Steps 5, 6 — facts about R from its definition; the axiom contributed nothing to them.)
Step 9. Instance(R)'s consequent is true: every object of D is in R — M has no junk. (R4 on Steps 7, 8 — modus ponens at the semantic level.)
Step 10. The map 0 ↦ z, 1 ↦ s(z), 2 ↦ s(s(z)), … is onto D. (Step 9 with Step 3.)
Step 11. The map is one-to-one. (If sⁿ(z) = sᵐ(z), n < m: peel n times with S2 to get z = s^(m−n)(z), making z a successor — contradicting S1. Both true in M by Step 1.)
Step 12. M is ℕ renamed — a copy; M was arbitrary: A compresses ℕ. ∎ (Steps 10–11; D2, D4.)
The mechanics run backward — how Ind convicts. In the alien world M (domain = 0, 1, 2, … plus a two-way ladder of aliens …a₋₁, a₀, a₁…, never touching the numbers): S1, S2 hold (no loops, no merges — the successor axioms cannot see junk). But R = the numbers only; Instance(R) has true antecedent, false consequent (aliens ∉ R) — false; one false instance falsifies Ind (R3, direction (i)); M fails A. Same string, same table: in a survivor it forces junklessness; in a junk world it detects the junk by borrowing the world's own reachable part as evidence. The first-order scheme cannot make the kill: its guaranteed conditionals sit only at carved sets, and nothing guarantees R is carved — an observation upgraded in Part VII to a theorem: in any alien survivor of the first-order list, no formula carves R (B13).
Part VI — The syllogism, the corollary, and the consolidation
The six-step syllogism (no adequate machine for second-order logic):
- Definition: consequence of axioms = true in all survivors (= the duty).
- Dedekind (= Chain 1): survivors of the second-order Peano axioms = copies of ℕ only.
- 1 + 2: consequence of those axioms = true in all copies of ℕ = true in ℕ = T. (Copies make the same sentences true — D2; the consequence-set and T are literally the same set.)
- Definition of adequate: an adequate second-order machine, fed the Peano axioms, would print exactly their consequences — by 3, exactly T: all truths, no falsehoods.
- Gödel 1931: no machine does that.
- Therefore no adequate machine for second-order logic exists. ∎
Every step is a definition, Chain 1, or 1931. (The concrete mechanism behind step 3, from the session: the finitely many second-order Peano axioms conjoin into one sentence A, and for any arithmetic S, "(A ⊃ S) is valid ⟺ S ∈ T" — every arithmetic question folded, one by one, into a validity question about a finite string.)
The four-line impostor corollary — replacing the heavier machinery. Given: G true in ℕ, unprovable in P.E. (Gödel 1931 — the book's own theorem). Goal: P.E. has an impostor survivor.
- Provable from P.E.'s axioms = true in all their survivors. (Adequacy 1930 — the standing debt.)
- G unprovable ⇒ G not true in all survivors ⇒ some survivor M makes G false. (Step 1, contraposed.)
- ℕ is a survivor (the axioms are correct) and G is true in ℕ.
- M and ℕ disagree about G, so M is no copy (D2): M is an impostor — a loud one. ∎
Attribution kept straight: impostors are a corollary of the first incompleteness theorem (via adequacy), not its content — the book's work is strings and diagonalization; interpretations never appear in it.
The consolidation — the reader's structural discovery, then the rebuild. A further apparatus was built in session to answer "why can't first-order compress, essentially?" — a diagnosis chain (where Chain 1's proof jams for the scheme) and an exhaustion chain (via a new constant c and compactness). The reader recognized that none of it was load-bearing as built: the syllogism needs only Chain 1, the definitions, and 1931; impostor-existence follows from the four-line corollary; and the essence question closes with one line — first-order lacks ∀P. The apparatus was dropped. In the post-session continuation, however, the reader's own questions — why exactly is R not carved? isn't assuming R ≠ D circular? — pulled the dropped material back, and it was rebuilt as Part VII: one chain, compactness-free, with the arrow directions audited. The final ledger:
| Claim | Status |
|---|---|
| A's survivors = copies of ℕ | Proved outright — Chain 1, no debts |
| No adequate machine for second-order logic | Six-step syllogism, given 1931 |
| First-order arithmetic incomplete; impostors exist | The book's theorem + four-line corollary; debt: adequacy 1930 |
| First-order Σ does not compress ℕ; in its impostors R is uncarved | Proved — Part VII, ☑ G1 + ☑ G2; debts: adequacy 1930, machine limit, operation-agreement |
| Why first-order can't compress (essence) | "Lacks ∀P" — now with the mechanism visible: the guarantee's index set changed from subsets to carved sets, and the sets that would convict are exactly the ones no alien world lets any formula carve (B19) |
Part VII — The rebuilt chain: first-order Σ does not compress ℕ
Post-session continuation, same day. Triggered by the reader's "why is R not carved?" and his circularity challenge; his own proposed chain was graded (adequacy found misplaced as a conclusion — it is a premise), and the corrected version below entered the see-saw from the opposite end to Part VI: the syllogism holds compression fixed (Chain 1) and concludes adequacy must give; this chain holds adequacy fixed (the 1930 theorem) and concludes compression must give. One see-saw, entered from both ends. Compactness appears nowhere.
Objective.
- G1: some world passes every sentence of Σ yet is not a copy of ℕ — Σ does not compress ℕ.
- G2: in that world, no formula carves R — which is exactly how it passes every induction axiom while keeping its aliens.
The chain ends when both verdicts are announced; the steps after them are anatomy.
Terms. Part IV–V's items are in force: machine, duty, adequate, T, survivor (D1), copy (D2), impostor (D3), carve / C_F, Instance(S), and the parse "Ind_F in M says exactly Instance(C_F)" — all quoted from Part V and used verbatim. New:
- Σ := the first-order axiom list — S1, S2, the arithmetic axioms, and every instance Ind_F. Induction is a scheme, so the candidate compressor is an infinite list, not one sentence; D4 extends: Σ compresses ℕ iff every survivor of all of Σ is a copy of ℕ.
- Alien := D5's junk: a member of D outside the reached part R — an object no numeral names; counting up from z by s-steps never lands on it.
Given. (i) the adequacy theorem — first-order logic has an adequate machine, print list = duty; (ii) the machine limit — no mechanical machine prints exactly T. Both aerial, on the debt register (items 5 and 6).
The chain.
B1. Load the adequate machine with Σ. Its print list = duty(Σ) = the set of sentences true in every survivor of Σ. (Given i; duty.)
B2. Suppose Σ compresses ℕ: every survivor of Σ is a copy of ℕ. (Assumption to refute; Σ.)
B3. ℕ itself is a survivor of Σ — every axiom on the list is correct, i.e. true of ℕ. (Part I; D1.)
B4. Then duty(Σ) = T. One direction: a sentence true of ℕ is true in every copy (D2), hence in every survivor (B2), so it is in the duty. Other direction: a sentence in the duty is true in every survivor, in particular in ℕ (B3), so it is in T. (B2, B3.)
B5. So the machine's print list is exactly T. (B1, B4.)
B6. A mechanical machine printing exactly T contradicts the machine limit. So B2's assumption fails: ☑ Verdict G1 — Σ does not compress ℕ. Fix a survivor M = (D, z, s, …) that is not a copy: an impostor. (Given ii; D3.)
B7. Note what did not break: the machine still prints exactly its duty — the contradiction executed the assumption, not the adequacy. Impostors and adequacy coexist; M's survival simply holds duty(Σ) strictly below T. (B6; the see-saw.)
B8. M has aliens. For if R = D — every object of M reached — M would be a copy of ℕ: the numerals name distinct objects forming a successor chain (S1, S2 — the argument of Chain 1's Steps 10–11), and the arithmetic axioms pin +, ·, E, ≤ to ℕ's tables on named objects (operation-agreement: aerial, debt 7). A copy contradicts B6. So R ≠ D. (B6; D5.)
B9. Toward G2: suppose some formula F carves R — C_F = R. (Assumption to refute; carve.)
B10. Ind_F is on the list Σ and M survives Σ, so Ind_F is true in M; and Ind_F in M says exactly Instance(C_F) — by B9, Instance(R). (D1; the parse, quoted from Part V.)
B11. Instance(R)'s antecedent is true in M: z ∈ R, and R climbs. (D5 — reached in zero steps; one more s preserves reachability. Chain 1's Steps 5–6, verbatim.)
B12. So Instance(R)'s consequent is true: every object of D is in R — R = D. (R4 on B10, B11.)
B13. That contradicts B8 (R ≠ D). So B9's assumption fails: ☑ Verdict G2 — no formula carves R in M. (B8, B12.)
Both verdicts are in. What follows is the anatomy: how M survives every induction axiom while keeping its aliens, and why Chain 1's proof was never transferable. (This stretch was first delivered in metaphor — "credentials," "inflates," "the wall" — and rejected; the expansion below replaced it, and caught an error in the process: see B18.)
B14. Name the two conditions Instance(S)'s antecedent tests, for any set S: (a) z ∈ S; (b) S climbs. (The antecedent of Instance(S), split for reuse.)
B15. Any set S satisfying (a) and (b) contains all of R. (By (a), the object reached in zero steps is in S; by (b), if the object reached in n steps is in S, so is the one reached in n+1; R's members are exactly the objects reached in finitely many steps — D5.)
B16. Call S a breaker if S satisfies (a) and (b) yet S ≠ D. A breaker is exactly what makes Instance(S) false: true antecedent, false consequent — the one false row of the table. By B15, every breaker contains all of R and misses at least one alien. And R itself is a breaker: (a) and (b) by B11, R ≠ D by B8.
B17. Take any formula F and ask what M's survival of Ind_F requires. Two cases, split by the table: Case 1 — C_F fails (a) or (b): Instance(C_F) has a false antecedent, so it is true in M automatically, whatever else C_F looks like. Case 2 — C_F satisfies (a) and (b): then Instance(C_F) is true only if C_F = D; M survives, so C_F = D. (D1; the table.)
B18. So M survives every induction axiom because no formula carves a breaker: every carved set falls under Case 1 (true for free) or Case 2 (equals D — not a breaker). Breakers exist in M — R is one, and so is any set containing R that misses an alien — but the argument of B9–B13 runs verbatim with any breaker in place of R: were it carved, its own instance would force it to equal D, contradicting "misses an alien." The sets that would falsify induction are sets no axiom of Σ ever speaks about. (B13, B16, B17.) — Correction the expansion caught: an earlier draft said "R alone has the credentials without being D." False — every breaker does. The argument needs, and has, all of them uncarved.
B19. Why Chain 1's proof does not transfer — the actual strings side by side. The second-order axiom is the single sentence Ind := ∀P(…), and by R3, "Ind true in M" unpacks to Chain 1's guarantee, quoted:
Step 2. For every subset S of D, Instance(S) is true in M.
— one true conditional per subset, no exceptions — which Chain 1 cashed out at R in two moves (Step 4: R ⊆ D, subsethood the sole ticket; Step 7: Instance(R), the cash-out). Σ contains no sentence Ind — the string ∀P is not in its grammar; in its place stand the separate axioms Ind_F, and what survival of Σ guarantees is only:
For every formula F, Instance(C_F) is true in M.
The index set changed: subsets of D → carved sets of M. R's subsethood buys nothing; to reproduce Chain 1's Step 7 you would need R in the new index set — some F with C_F = R — and B13 says there is no such F in M. Instance(R), the one conditional whose truth forces R = D and kills the aliens (Chain 1, Steps 7–9), is in M false — true antecedent by B11, false consequent by B8 — a false instance sitting in the world, asserted by no axiom on the list. Σ never says the one thing that would convict M. ∎
The picture.
R (reached) ‖ aliens (unreached)
z → s(z) → s(s(z)) → ⋯ ‖ ⋯ → a → s(a) → s(s(a)) → ⋯
‖
the boundary ‖ is drawn by NO formula (B13):
carved + (a) + (b) → the set is all of D (B17, Case 2)
R has (a) + (b) and is not all of D (B16: a breaker)
→ R is not carved — nor is any other breaker (B18)
Coda — the ticket change, and a named pitfall (not load-bearing).
second-order Ind: guarantee indexed by SUBSETS — R's ticket: R ⊆ D ✓ (Chain 1, Step 4)
first-order Σ: guarantee indexed by CARVED SETS — R's ticket: some C_F = R ✗ (B13)
Counting makes the ticket change costly — formulas are finite strings, so only listably many carved sets, against unlistably many subsets (the Ch. II diagonal). But the pitfall, named once: "uncarved sets exist, therefore aliens exist" is invalid. ℕ itself has unlistably many uncarved subsets and zero aliens. Sparse coverage merely fails to forbid alien worlds; what produces one is B1–B6 — adequacy plus the machine limit, nothing else. Nor is the reverse route circular: "alien world ⇒ R uncarved" (B9–B13) is a conditional theorem whose hypothesis is discharged by the existence theorem (B1–B8); the arrows never close a loop. In copies, R is carved — by (v₁ = v₁).
Part VIII — Distinctions Ledger
| Confusion raised | One-line resolution |
|---|---|
| "These axioms don't look like universal truths — more like sentence structures" | Correct, twice over: the schemes are metalanguage stencils (instances are the axioms), and "correct" means true in the intended interpretation — chosen truths, not self-evident ones. |
| "If F is true, 'G ⊃ F' isn't automatically true, is it?" | Under the table it is: G ⊃ F is false only at (G true, F false), excluded by F's truth. ⊃ is the table, not English "if–then"; the discomfort is the paradoxes of material implication, and the table is forced by wanting ∀-claims to mean "no counterexample." |
| Why exactly these 19 schemes — could more be discovered? | Chosen toolkit, not discovered totality: constraints are correctness + shape-recognizability + sufficiency. Logic side: provably finished (adequacy 1930). Arithmetic side: provably never finishable (1931) — the impossibility of ending the search is the theorem. |
| "Completeness theorem" vs "incompleteness theorem" | Different objects: 1930 is about the engine (prints all logical consequences — renamed adequacy); 1931 is about systems aiming at T. They compose: the engine is perfect; no axiom stock ever makes consequence reach T. |
| "Interpretation" used but never defined | Domain + referent for 0̄ + meanings for ′, +, ·, E, ≤. Truth exists only relative to one. Rivals evaluated: clock-12, one-object world. |
| "First-order never claims truth covering all natural numbers" | Inverted: ∀v₁ covers all numbers; what first-order cannot say is "for all properties." The divide is that one grammar clause. |
| First-order's smaller obligation as a post-Gödel "retreat" | No agency, no timeline: the duty was always "true in all survivors" by definition; impostors surviving is what keeps it below T. The leak is why the finish is reachable. |
| "Dedekind proved second-order logic complete (every truth provable)" | He proved categoricity — a statement about interpretations only; no proof-concept occurs in it. |
| "Gödel proved all machines are adequate" | 1930 says one adequate engine exists, for first-order. Almost no machine is adequate. |
| What forbids second-order truths being finite strings? | Nothing — they are finite strings, and second-order proof machines exist and run fine. What is impossible is one machine printing exactly the valid set: its duty contains all of T. |
| Why does ∀P inflate the duty to all of T? | See-saw + drain: duty = true-in-all-survivors; ∀P lets induction test every subset of any world, draining survivors to ℕ-copies; then true-in-all-survivors = T by definition, not by ambition. |
| How does Step 2 lead to Step 4 — which instance? Does Ind's content matter? | Missing rule, now stated (R3): ∀P's instances are indexed by subsets; subsethood is R's entry ticket (Step 4); Instance(R) is the specific conditional "z ∈ R and R climbs ⇒ R is everything" — the content is everything, and R4 turns it into no-junk. |
| C_F := {x ∈ D : F true of x in M} — "x belongs to D and F is true"? | Set-builder: a membership test, not a conjunction — the set of those x passing it. It is Ch. II's "set F expresses," relativized to M; depends on both F and M. |
| "Gödel's first theorem establishes that impostors exist" | Corollary, not content: book proves the unprovable truth; impostors follow in four lines given adequacy. |
| "First-order logic is incomplete" | Terminology: the logic (engine) is adequate — flawless; first-order arithmetic systems are incomplete. |
| "Impostors survive" vs "provables sit below truths" — same claim? | Different ledgers: worlds vs sentences. Pool-fact vs print-list-fact, welded by adequacy (print = duty). And only loud impostors (disagreeing with ℕ on a sentence) shrink the duty; quiet ones don't. The arrow runs print-gap → loud impostor, never backward. |
| "Why is R not carved? Assuming R ≠ D looks circular" | No circle: "alien world ⇒ R uncarved" is a conditional theorem (B9–B13); alien-existence has its own proof (B1–B8); neither cites the other's conclusion. In copies R is carved (v₁ = v₁). |
| "Uncarved sets exist (counting), so aliens exist" | Invalid — the named pitfall: ℕ has unlistably many uncarved subsets and zero aliens. Counting explains the stall; only adequacy + the machine limit produce an impostor. |
| "…so first-order can't compress, so an adequate machine exists" | Reversed arrow: adequacy is a theorem proved outright — a premise (B1). With adequacy fixed, the see-saw forces compression to give (B6), not the other way. |
| "Credentials," "inflates," "the wall" (tutor's shorthand, rejected) | Cashed out: credentials = the antecedent pair (a) z ∈ S, (b) S climbs (B14); inflate = forced to equal D by the set's own instance (B17); the wall = the R/alien boundary no formula draws (B13). Expansion caught a real error — see next row. |
| A stalled proof vs a refuted claim | Chain 1's non-transfer (B19) diagnoses; it demonstrates nothing about survivors. "R alone is the dangerous set" was also false — every breaker (B16) is dangerous, and B18 shows none is carved. |
Part IX — Self-Test
Answer before peeking.
- Scheme vs axiom: what is L₁, what are its axioms, and which groups' schemes have exactly one instance?
- The two senses in which P.E.'s axioms are correct — and one concrete rival interpretation with the axiom it falsifies.
- State the table for ⊃ and derive it from the "no counterexample" reading of a universal claim. Then verify L₁ by cases.
- Define: interpretation, survivor, copy, impostor, logical consequence, duty, adequate, complete, categorical.
- The three theorems (Dedekind 1888, Gödel 1930, Gödel 1931), one line each — and what each is about (interpretations? engines? systems?).
- State R3. What exactly is Instance(S) for Ind, and what are the two directions of use of a universal?
- Reproduce Chain 1 (twelve steps with justifications). At which single step does second-order grammar act, and what is R's "entry ticket"?
- Run the conviction backward: in the alien world, show Instance(R) is false and conclude Ind fails there. Why can't S1, S2 see the aliens?
- In the alien world, evaluate Instance(S) at S = the whole domain. True or false? What does the answer say about why the conviction had to use R? (Also still owed from session — see Part X.)
- The six-step syllogism: why no adequate machine for second-order logic. Which steps are definitions, which are theorems?
- The four-line impostor corollary: derive impostor-existence for P.E. from 1931. Which debt does it carry?
- Why does the first-order induction scheme cover only "a countable slice of an uncountable totality"? Cite the two Ch. II facts doing the work.
- State Part VII's two verdicts G1 and G2, and give the chain to G1 (B1–B6). Which two aerial debts does it lean on, and at which steps?
- Define breaker. Show every breaker contains all of R, and explain — with the two cases of B17 — how M survives every Ind_F despite containing breakers.
- Grade this inference: "there are countably many formulas but uncountably many subsets, therefore impostors exist." Then grade: "R is uncarved, therefore aliens exist."
Answers
- L₁ = (F ⊃ (G ⊃ F)), a metalanguage stencil, not a formula; its axioms are the instances with actual formulas plugged in. Group III's eleven schemes have one instance each (they contain no placeholders); Groups I, II, IV have infinitely many.
- Groups I–II: valid — true in every interpretation, by the meaning of the logical symbols alone. Groups III–IV: correct — true in the intended interpretation specifically. Rival: the twelve-hour clock falsifies ∼(0̄ = v₁′) (11′ = 0) while passing (v₁ + 0̄) = v₁.
- F ⊃ G false only at (T, F). Forced because "for every n: F(n) ⊃ G(n)" must mean "no counterexample": instances (T,T), (F,T), (F,F) must not break it — check divisible-by-4/even at n = 8, 6, 3. L₁: F true → G ⊃ F has true consequent, true, whole is T⊃T; F false → false antecedent, true.
- Interpretation: domain + referent for 0̄ + meanings for ′, +, ·, E, ≤. Survivor: makes all axioms true. Copy: ℕ renamed, same sentences true. Impostor: survivor, not a copy. Consequence: true in all survivors. Duty: the consequence-set of the fed axioms. Adequate: print list = duty, exactly. Complete: sound and prints all of T. Categorical: survivors = copies of one world.
- Dedekind: second-order Peano axioms are categorical — about interpretations only. 1930: an adequate engine exists for first-order logic — about the engine. 1931: no machine sound for T prints all of T (equivalently: no machine prints exactly T) — about every system aiming at arithmetic truth.
- R3: ∀Pφ true in M ⟺ for every subset S of D, φ with P(t) read as "t's value ∈ S" is true. Instance(S) = "if z ∈ S and S climbs, then every object of D is in S." Uses: one false instance falsifies; a true universal cashes out at any chosen instance.
- Part V verbatim. Second-order grammar acts only at Step 7 (the cash-out at S := R, licensed by R3). Entry ticket: subsethood alone (Step 4) — describability appears nowhere in R3's index set.
- R = the numbers; antecedent of Instance(R) true (0 ∈ R, successors of numbers are numbers); consequent false (aliens ∉ R); Instance(R) = T ⊃ F = false; by R3(i) Ind is false in M*. S1, S2 police only loops and merges — the alien ladder has neither; junk is invisible to the successor axioms.
- True — vacuously informative: at S = D, the consequent "every object is in D" is automatically true, so Instance(D) holds. The conviction needed a subset whose antecedent holds while its consequent fails — only the world's own reachable part R does that in a junk world; easy subsets prove nothing.
- Part VI. Steps 1 and 4 are definitions; Step 2 is Chain 1 (Dedekind); Step 5 is 1931; Steps 3 and 6 are combinations.
- Provable = true in all survivors (adequacy — the debt); G unprovable ⇒ false in some survivor M; ℕ survives with G true; M ≠ copy ⇒ impostor.
- Formulas are listable (finite strings over a finite alphabet — Ch. II listing); sets of numbers are not (Ch. II diagonal: any list of sets misses D = {n : n ∉ Sₙ}). One axiom per formula ⇒ induction guaranteed only at listably many properties out of unlistably many.
- G1: Σ does not compress ℕ (some survivor is not a copy). G2: in that survivor, no formula carves R. Chain to G1: adequate machine loaded with Σ prints its duty (B1, debt: adequacy); suppose compression (B2); ℕ survives (B3); then duty = T (B4); machine prints exactly T (B5); contradicting the machine limit (B6, debt: general machine form of 1931) — so compression fails. Debts at B1 and B6.
- Breaker: a set with (a) z ∈ S and (b) S climbs, yet S ≠ D — exactly what makes Instance(S) false. Contains R: by (a) the zero-step object is in, by (b) each further step stays in, and R is exactly the finitely-reached objects. B17: for each F, either C_F fails (a)/(b) — Instance(C_F) true by false antecedent — or C_F has both and, since M survives, C_F = D. Either way no carved set is a breaker; the breakers (R among them) are sets no axiom speaks about.
- Both invalid. First: ℕ has uncountably many uncarved subsets and zero aliens — counting explains the stall, never produces an impostor; impostors come from adequacy + the machine limit (B1–B6). Second: reversed — "R uncarved" is proved from alienhood (B9–B13, a conditional theorem); in copies R is carved by (v₁ = v₁).
Part X — Position, pending items, debts, and the method
Position: Chapter III begun. §1 (the axiom system P.E.) read and conceptually consolidated — what the nineteen schemes are, why correct, how they cohere. (July 25 update: the meaning-by-meaning walk deferred below is now substantially done — Part XI records N₁–N₁₁ under their official numbers, corrects the L₅/L₇/N₁₂ strings against the page, and unpacks the Discussion paragraph's claim that substitution and free/bound are circumvented.) The chapter's formal work is untouched: the meaning-by-meaning walk through the remaining axioms was deferred for the excursus, and §2 (arithmetization of the axiom system — "x is a proof of y" becoming an arithmetic relation) is where the book resumes. Part XI makes the connection concrete: the axioms were engineered — occurrence-scans and one-cut replacement instead of substitution — so that "x is an axiom" will cost §2 only concatenation. Note the connection already visible: the arithmetization is exactly what makes any machine describable inside arithmetic, which is what powers 1931's diagonal — the engine under every candidate truth-printer.
Owed by the reader, three items: (1) the L₃ case-check — ((∼F ⊃ ∼G) ⊃ (G ⊃ F)) across the four truth-value combinations, using only the table; (2) the ancestor interpretation — find an interpretation falsifying (v₁ ≤ v₂ ∨ v₂ ≤ v₁) (hint on record: domain = people, ≤ read as "is an ancestor of"); (3) the whole-domain instance — Self-Test 9.
Debt register: the standing four (E-elimination; prime base 13; property 1 ⇒ property 2; mechanical ⇒ Arithmetic) plus three new, all confined to the aerial commentary and not on the book's route: (5) the 1930 adequacy theorem — load-bearing for the four-line corollary, the see-saw, and B1; (6) the general machine form of 1931 (the machine limit) — Chapter III proves it for P.E.; the widening to all machines comes in the later abstract chapters; now load-bearing for B6; (7) operation-agreement — that a survivor with R = D is a full copy (the numerals' successor chain is Chain 1's Steps 10–11; that +, ·, E, ≤ agree with ℕ's tables on named objects is asserted, not derived) — load-bearing for B8. A former eighth — the existence of worlds where no formula carves R — is no longer a debt: it is theorem B13. The July 25 continuation adds one: (8) instantiation from L₆ + L₇ — that the missing axiom ∀v₁F ⊃ F(t) is recoverable as a theorem from L₆, L₇, Groups I–II and the two rules (asserted in Part XI §7, not derived; it is part of what the Kalish–Montague formulation's adequacy amounts to).
The method — a third failure mode, a new tool, and the continuation's lessons. July 22: vivid coinages doing load-bearing work stall explanations. July 23: both over-compression and natural-language paraphrase fail; the channel is symbols + justified chains. Today found the third failure mode: metaphor stacking — "treadmill," "finish line," "blueprint," several per paragraph, each carrying real content but none cashed out ("I don't know what it is, maybe your language, maybe your analogies — I find your explanation hard to comprehend"). What worked, in order of discovery: (a) plain single-vocabulary restatement (machines/printing) — partial; (b) the reader stating his own understanding for piece-by-piece grading — effective, and errors localized precisely; (c) a glossary of citable definitions fixed before any argument, then theorems, then chains — the reader's own prescription, and the turning point; (d) full expansion with evaluation rules stated as numbered citable items — the diagnosis that a chain stalls when a justification silently uses a rule never stated (R3, the instance rule, was the entire Step 2→4→5 gap). New tool for the kit: when a learner cannot cross a step, look for the unstated rule before adding more prose. The continuation added two more: (e) audit the arrow directions — the reader's circularity challenge was resolved only by separating a conditional theorem from an existence theorem, and grading his proposed chain exposed a premise (adequacy) sitting in the conclusion slot; (f) expand every metaphor into steps, because the expansion is a checker — cashing out "credentials/inflates/the wall" surfaced a genuine error ("R alone") that the imagery had hidden. And the complementary reader's-side skill, displayed twice: tracking the dependency structure of an argument — first to drop what was not load-bearing, then to demand the rebuilt version stand as one chain with stated objective and verdicts.
The July 25 continuation added two more tools. (g) Teach new material as a delta against an owned result. The first explanation of the Kalish–Montague system, built from scratch, failed ("your way of elucidation doesn't really help me"); what landed was the reader's own anchor — "we had our own substitution via a wrapper on July 22 — what is different here?" — after which everything became one comparison: same trick, one precondition-failure, one repair. New material that echoes an owned result should be taught as the diff, not as a fresh subject. (h) A felt contradiction is data — locate the invalid step, then find where the instinct is right. "It still reads like v₁ = v₁′" dissolved not by reassurance but by (i) naming the exact invalid move (transitivity across a re-binding: no single context holds both guards) and (ii) showing the string on which the instinct is correct (the single-wrapper attempt, where the guard genuinely is contradictory). An objection traced to the diseased neighbor it correctly diagnoses is worth more than an objection merely answered.
Part XI — Second continuation (July 25): the N₁₂ brackets are the July 22 wrapper; replacement vs substitution
Triggered by the reader holding this file against the book's pages 29–30 and finding it short: (i) not all schemes were recorded — N₁–N₁₁ never stated, L₅/L₇/N₁₂ misstated (now corrected in place, marked); (ii) the Discussion paragraph claims substitution — "indeed, even the notions of free and bound occurrences of variables are circumvented" — how?; (iii) the reader's own recall, which became the key to everything: "on July 22 we had our own version of substitution via a wrapper — what is different here?"; (iv) a precise objection to the answer: "the double-guarded string still reads like v₁ = v₁′ — a contradiction?" A first explanation, built from scratch, failed ("your way of elucidation doesn't really help me"); the one that landed is below, organized around (iii). All July 22 items (Φ_lit, Φ_wrap, the three layers, the four hazards, r, sub) are used under their own names.
N₁–N₁₁, recorded under their official numbers — exactly Part I's ladder and recipes, now tied to the strings:
N₁ : (v₁′ = v₂′ ⊃ v₁ = v₂) — different rungs, different nexts
N₂ : ∼(0̄ = v₁′) — 0 is nobody's next
N₃ : (v₁ + 0̄) = v₁ ┐
N₄ : (v₁ + v₂′) = (v₁ + v₂)′ ┘ the addition recipe
N₅ : (v₁ · 0̄) = 0̄ ┐
N₆ : (v₁ · v₂′) = ((v₁ · v₂) + v₁) ┘ multiplication = repeated addition
N₇ : (v₁ ≤ 0̄ ≡ v₁ = 0̄) ┐
N₈ : (v₁ ≤ v₂′ ≡ (v₁ ≤ v₂ ∨ v₁ = v₂′)) │ ≤ characterized stepwise
N₉ : ((v₁ ≤ v₂) ∨ (v₂ ≤ v₁)) ┘ any two numbers comparable
N₁₀ : (v₁ E 0̄) = 0̄′ ┐
N₁₁ : (v₁ E v₂′) = ((v₁ E v₂) · v₁) ┘ E = repeated multiplication
(N₁, N₂ are Part V's S2, S1 up to the outer ∀ — supplied by the generalization rule — and the order of the equation.)
§1. The brackets are the July 22 brackets — and the wrapper's real precondition. F[0̄] = ∀v₁(v₁ = 0̄ ⊃ F) is Φ_wrap(F, 0) verbatim (July 22, Part IV). And rereading Φ_wrap(F, t) = ∀v₁(v₁ = t ⊃ F) with fresh eyes: its precondition was never "t is a numeral." It is: t contains no v₁ — nothing for the added quantifier to grab. Numerals satisfy this trivially (they contain no variables at all), and Chapter II never tested the boundary, because diagonalization only ever plugs specific codes.
§2. The boundary tested: plugging v₁′, and capture. Induction's climbing slot must evaluate F at v₁′ — a term containing v₁. Feed it to the single wrapper and watch:
∀v₁(v₁ = v₁′ ⊃ F)
The new ∀v₁ grabs every v₁ in its scope — including the one inside the term, which was supposed to keep pointing at the outside number. (Standard name: capture — a variable meant to stay free is seized by an added quantifier.) Run on F := ∃v₂(v₁ = v₂ + v₂), "v₁ is even": the string says "every number that equals its own successor is even" — guard false of everything, sentence vacuously true, content destroyed.
§3. The repair: reduce the new case to the old one.
F[v₁′] := ∀vᵢ( vᵢ = v₁′ ⊃ ∀v₁( v₁ = vᵢ ⊃ F ) ) (vᵢ any variable not occurring in F)
A fresh variable vᵢ satisfies the precondition — a term containing no v₁, the same property the numeral had. The outer guard sits outside the inner ∀v₁'s scope, so its v₁ still points outside: it stores v₁′'s value under the fresh name. The inner string is Φ_wrap(F, vᵢ) verbatim. So the double wrapper is not a new trick: trade the dangerous term for a harmless fresh variable, then run the old machine unchanged. The freshness condition is the same disease one level up (if vᵢ occurred in F, the outer ∀vᵢ would grab those occurrences) — and it is checked by a bare symbol-scan, not a scope-parse.
§4. The semantic parse — Claim A, and N₁₂ = the domino principle. (This also retro-earns Part V's parse "Ind_F in M says exactly Instance(C_F)," which was stated there in substitution notation; the chain below establishes it for the book's actual bracketed string, so every use in Parts V–VII stands.)
Claim A: F[v₁′] is true at n ⟺ F is true at n+1 ("true at k" = true with v₁ read as k). Evaluate at v₁ := n:
- The inner ∀v₁ re-binds only its own scope, (v₁ = vᵢ ⊃ F); the v₁ inside the term v₁′ sits outside that scope, so v₁′ denotes n+1. (R1; the whole reason the guard is placed outside.)
- Outer ∀vᵢ: true ⟺ for every m, the instance (m = n+1 ⊃ ∀v₁(v₁ = m ⊃ F)) is true. (R2.)
- m ≠ n+1: false antecedent, instance true, no information. (Table.)
- m = n+1: instance true ⟺ ∀v₁(v₁ = n+1 ⊃ F) is true. (Table.) The stored value has been handed over; vᵢ is gone.
- That string is Φ_wrap(F, n+1): by R2 and the table, k ≠ n+1 passes vacuously, k = n+1 says: F is true at n+1. (July 22's equivalence, re-derived.) ∎
Concrete run, F := 0̄ ≤ v₁, n = 4: v₁′ denotes 5; only vᵢ = 5 survives Step 2–4; only k = 5 survives Step 5; verdict "0 ≤ 5". F consulted once, at the end, unopened — the two wrappers are a delivery pipe for the value n+1. Claim B: F[0̄] is true ⟺ F is true at 0. (Step 5 with 0 in place of n+1.)
Assembling N₁₂ (a sentence — every v₁ ends up bound): by Claim B, block 1 = "F holds at 0"; by R2 with Claim A inside every instance, block 2 = "for every n: F at n implies F at n+1" — F climbs; block 3 = "F holds at every number." Reading the two ⊃'s by the table:
(F at 0) ⊃ ((F climbs) ⊃ (F everywhere))
— false in exactly one situation: F holds at 0, F climbs, yet F fails somewhere. The domino principle for the set carved by F; in a world M, exactly Instance(C_F). And each instance is true of ℕ (the ladder has no side-branches and no unreachable rungs), so constraint (a) of Part I holds. ∎
§5. The transitivity objection, and regions. The reader: "it still reads like v₁ = v₁′ — v₁ = vᵢ and vᵢ = v₁′ chain to a contradiction." The resolution, with the run at v₁ := 4 on the table:
| region of the string | v₁ denotes | v₁′ denotes | vᵢ denotes |
|---|---|---|---|
| outside everything | 4 | 5 | — |
| inside ∀vᵢ only (guard 1 lives here) | 4 | 5 | 5 |
| inside both quantifiers (guard 2 and F live here) | re-bound to each k; weight at 5 | 6 — unused; guard 1 does not live here | 5 |
At the moments they are checked, guard 1 says 5 = 5 and guard 2 says 5 = 5; the alarming "4 = 5" is asserted by no part of the string. Transitivity chains equations that hold in one context — and between the guards, ∀v₁ re-points the letter, so no single context holds both. (Re-read inside the inner region, guard 1 would even be false — 5 = 6 — harmlessly: it lives outside, was checked with v₁ meaning 4, and its work, pinning vᵢ to 5, is done. vᵢ is the one letter with constant denotation: it is the pipe.) And the instinct is the correct diagnosis of the single-wrapper string (§2), where both sides of v₁ = v₁′ share one region and the guard genuinely is contradictory — the cure works precisely by making the transitivity chain unrunnable.
Why reuse the letter v₁ at all? Because the transparent alternative — rename F's free variable and write ∀vᵢ(vᵢ = v₁′ ⊃ ∀w(w = vᵢ ⊃ F⟨w⟩)) — requires editing every free v₁ inside F into w: renaming is substitution, the forbidden operation. F arrives with its free variable unchangeably named v₁, so the delivery pipe must terminate in a quantifier over that exact letter, and the letter serves two masters, disambiguated by scope alone. A shape-checking machine never stumbles (which quantifier owns which occurrence is fixed mechanically by nesting); only human reading trips, because it wants one letter to mean one thing.
§6. Why v₁′ and not a numeral — essential vs circumstantial. The reader asked whether the whole apparatus is an accident of this one axiom. Split verdict:
The v₁-containing plug is essential. The climbing slot asserts infinitely many climb-steps at once — (0,1), (1,2), (2,3), … — and the numeral alternative, the infinite list F[0̄] ⊃ F[0̄′], F[0̄′] ⊃ F[0̄′′], …, fails on the definition of proof itself: (1) a proof is a finite sequence of formulas; (2) so any one proof uses finitely many climb-sentences; (3) so it reaches F[n̄] for some n and no further; (4) ∀v₁F(v₁) — the thing induction exists to deliver — would never be provable, though every instance would be. One finite quantified sentence, evaluating F at v₁′ under the binder, is the only shape that works. And Group IV is the only plugging site among the nineteen schemes — the only scheme parameterized by an arbitrary formula. (Group III mentions v₂′ constantly — N₄ — but those are honest terms written into fixed atomic equations as they are composed, not plugs into a pre-existing formula.)
The delivery device is the choice. Gödel states the same content with literal substitution F(v₁′) and pays with the sub ladder; Smullyan's guards are the alternative implementation — forced for him by the standing refusal to build sub.
§7. Replacement vs substitution — the July 22 hazard list, walked. Two string operations (layer 1 of July 22's three layers):
- Substitution (Φ_lit): open F; find the occurrences of v₁; determine which are free (parse parenthesis scope); replace each of them; reassemble. The four hazards; the ~31-rung ladder for sub.
- Replacement (L₇'s notion): one cut, one splice, in an atomic formula: X₁vᵢX₂ ↦ X₁tX₂.
The hazards die one by one: find all occurrences — gone (one occurrence, any one you like); which are free — gone (atomic = no ∀ inside = nothing bound, nothing to parse); capture — impossible (no quantifier in the string to do the grabbing); the code function — one concatenation, a ∗ b ∗ d ↦ a ∗ c ∗ d, Corollary 1 territory. Slogan: substitution must be parsed; replacement only cut.
And the system has no instantiation axiom ∀v₁F ⊃ F(t) — the usual home of "substitute t for the free v₁," with its capture-avoidance side condition. Its work is done by L₆ (the term has a value: ∃vᵢ(vᵢ = t)) plus L₇ transferring atomic facts across vᵢ = t one occurrence at a time — instantiation becomes a theorem to derive, not an axiom to state (asserted, not derived here — debt 8). With that, the Discussion paragraph is fully cashed: "substitution for free occurrences" avoided = no instantiation axiom + brackets in N₁₂; "free and bound circumvented" = every side condition (L₅, L₆, Group IV's freshness) is an occurs-at-all scan; "the simpler notion of replacement" = L₇'s one cut in an atomic formula. L₆'s own side condition is the grabbing disease once more: without "vᵢ not in t," ∃v₁(v₁ = v₁′) — "some number is its own successor" — would be an axiom, and false.
§8. Who the customer is — the same economy, twice. July 22's three layers: string operation → code function → naming formula; all cost lives in layer 3. In Chapter II the operation needing a named code function was diagonalization: the wrapper bought r(x, y) = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3 — x riding unopened, layer 3 one line — and sub was never built. In Chapter III the thing needing a layer-3 formula is "x is the code of an axiom" — the first ingredient of "x is a proof of y," which is §2's whole burden. Under the bracket definition, an induction axiom's code is fixed blocks ∗ F's code ∗ fixed blocks — F an unopened parcel in every slot; the occurrence-scans are substring conditions; L₇'s replacement is the concatenation statement above. Had the schemes been stated with literal substitution, the axiom-recognizer would need sub Arithmetic — the ladder. Same refusal, new beneficiary: the wrapper protected the diagonal's address in Chapter II; it protects the axiom-checker in Chapter III. sub is never built anywhere in the book.
Ledger additions (July 25).
| Confusion raised | One-line resolution |
|---|---|
| "Isn't this just our July 22 wrapper?" | Yes — F[0̄] is Φ_wrap(F, 0) verbatim. New is only the plug: v₁′ contains v₁, violating the wrapper's real precondition (plug free of v₁ — "numeral" was never the condition); repair = outer guard trades v₁′ for a fresh variable, inner wrapper unchanged. |
| "Replacement as opposed to substitution?" | Substitution: parse F, find free occurrences, replace all — four hazards, the sub ladder. Replacement: one cut-and-splice in an atomic formula — nothing bound, capture impossible, code function one concatenation. Parsed vs cut. |
| "v₁ = vᵢ and vᵢ = v₁′ — so v₁ = v₁′, contradiction?" | The inner ∀v₁ re-points v₁ between the guards (4 → 5 in the run); each guard, when checked, says 5 = 5; no single context holds both, so transitivity cannot fire. The instinct correctly diagnoses the single-wrapper string, where the guard genuinely is contradictory. |
| "Why reuse the letter v₁ at all?" | Renaming F's free variable = opening F = substitution. The pipe must end in ∀ over the exact letter F uses; scope disambiguates mechanically. |
| "Is the double wrapper circumstantial?" | Split: plugging a v₁-containing term is essential (finite proofs — a numeral climb-list yields every instance but never ∀v₁F); the guards-vs-surgery delivery is the design choice (Gödel pays the ladder instead). |
| "How exactly are free/bound circumvented?" | No instantiation axiom to state; every side condition an occurs-at-all scan; the one replacement site atomic, where nothing is bound. |
Self-Test additions (16–21). Answer before peeking; these extend Part IX.
- State the wrapper's real precondition, and exhibit the capture failure of the single wrapper at F := ∃v₂(v₁ = v₂ + v₂).
- Reproduce Claim A's five-step parse. Where exactly is "vᵢ does not occur in F" spent?
- At v₁ := 4, give the three regions of F[v₁′] and what v₁, v₁′, vᵢ denote in each. Which letter is constant, and what does that constancy express?
- Why can induction not climb by numerals? Four steps, starting from the definition of proof.
- Walk replacement through the four-hazard list, and say why atomicity alone kills capture.
- Which axiom does the system not have, what pair does its work, and which false sentence does L₆'s side condition exclude?
Answers
- The plug t must contain no v₁ — nothing for the added ∀v₁ to grab; numerals satisfy it vacuously. ∀v₁(v₁ = v₁′ ⊃ ∃v₂(v₁ = v₂ + v₂)) says "every number equal to its own successor is even" — guard false everywhere, sentence vacuously true, content gone.
- §4. Spent at Step 5's "F is true at n+1": reading F's truth as depending only on v₁ presupposes no occurrence of vᵢ in F — otherwise the outer ∀vᵢ would have re-bound those occurrences to n+1, corrupting F before it was consulted.
- Outside: v₁ → 4, v₁′ → 5, vᵢ undefined. Inside ∀vᵢ only: 4, 5, 5. Inside both: v₁ re-bound (weight at 5), v₁′ → 6 (unused — guard 1 lives outside), vᵢ → 5. Constant: vᵢ, always 5 — the stored value; the pipe carrying 5 from the region where v₁ means 4 into the region where v₁ has been re-bound.
- Proofs are finite sequences → any proof uses finitely many of F[0̄] ⊃ F[0̄′], F[0̄′] ⊃ F[0̄′′], … → it reaches F[n̄] for some n and no further → ∀v₁F(v₁) is never provable though every instance is. The climbing clause must be one quantified sentence, hence F evaluated at v₁′ under the binder.
- One occurrence (no iteration); atomic = no ∀ = no bound occurrence to identify; no quantifier inside = nothing can seize the spliced t; code function a ∗ b ∗ d ↦ a ∗ c ∗ d. Atomicity kills capture because capture is seizure by a quantifier, and an atomic formula contains none.
- Missing: instantiation, ∀v₁F ⊃ F(t). Its work: L₆ (∃vᵢ(vᵢ = t) — the term has a value) + L₇ (one-occurrence transfer across vᵢ = t), a derivation rather than an axiom (debt 8). L₆'s condition "vᵢ not in t" excludes ∃v₁(v₁ = v₁′) — "some number is its own successor," false.
End of session review · Smullyan, "Gödel's Incompleteness Theorems," Chapter III §1 conceptually consolidated (with the Part VII rebuild and the July 25 continuation, Part XI); formal work pending · Previous files: Godel-Incompleteness-Session-2026-07-15.md (Chapter 1 framework & machine puzzle), Godel-Incompleteness-Session-2026-07-17-Answer-Sheet.md (Chapter 1 exercises 1–7), Godel-Incompleteness-Session-2026-07-19.md (Chapter II §1–§2), Godel-Incompleteness-Session-2026-07-20.md (Chapter II §3, Exercises 2–5), Godel-Incompleteness-Session-2026-07-21.md (Chapter II §4–§5), Godel-Incompleteness-Session-2026-07-22.md (Chapter II §6, Theorem 1 & Tarski), Godel-Incompleteness-Session-2026-07-23.md (Chapter II Exercises 6–8, complete) · Next: Chapter III proper — the L₃ check, the ancestor interpretation, Self-Test 9, then §2 arithmetization.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月24日学习记录 · 斯穆里安《哥德尔不完备定理》第三章§1(书中第28–30页)· 配合2026年7月15、17、19、20、21、22、23日记录 · 第三章已开始:§1的概念已整理巩固;本章的形式工作(§2算术化及以后)尚未触及 · 7月25日第二次续谈记于第十一部分:依书页纠正第二至第四组字符串,展开Discussion段落中避免代入的主张,并认出N₁₂的方括号就是7月22日的封装式
如何使用本文
这不是习题课,而是整理巩固课,也是第一次完全由读者问题、而非书中次序驱动的课。第三章开头展示十九个“公理模式”,本次从一个诚实的坦白开始:这些看起来不像普遍为真的公理,而像可以对之判断的句子结构。这一感觉完全正确,顺着它便展开了整天的讨论:这里的公理是什么(选定的正确公式,而非自明真理)——在哪个意义上正确(两类组有两种意义)——实质条件式⊃到底意味着什么(一张表,而非日常语言的“如果—那么”)——什么是解释(此前未经定义却承担关键作用的术语)——“一阶”是什么意思,二阶语法增加什么——然后是长篇旁论:1930年的恰切性定理与1931年的不完备性定理,名称虽相撞,却为何不仅不矛盾,反而相互结合;以及为何二阶逻辑根本不可能有恰切的机器。这篇旁论分阶段取得进展,第十部分记录了几次失败的解释尝试,最后由读者作出本次的结构性发现:为回答“为什么一阶不能压缩?”而搭建的整套装置都可舍弃——链1(戴德金)、六步三段论、四行推论已满足需要,其余可收成一句话(“一阶缺少∀P”)。
然后,课后续谈又以改进形式把它拾了回来。读者回到“为什么R不能被刻画?”,质疑回答中似乎存在的循环,并要求明确整个论证的箭头方向。解答成为第七部分:一条写明目标的链、两个带复选框的结论,每项理由都是引用——以真正掌握的内容替代被丢弃的脚手架。全文交叉引用都是可用链接:每项理由都指向其使用的规则、定义、定理或步骤。
7月25日又有第二次续谈,由读者拿本文对照书中第29–30页引发。它记于第十一部分:发现第一、二部分三处错误陈述并就地纠正(已标记);展开书中绕过代入、甚至自由/约束出现的主张(替换与代入之别);并由读者在被告知之前认出归纳模式的方括号——这是7月22日封装式回来承担更难的任务。
这里的一切都是俯瞰式评论:从第二个角度看书中沿另一条路攀登的山。斯穆里安第三章从不谈解释、幸存者,或作为打印机的机器;他的证明是字符串与对角化。本文没有任何内容是阅读该书的前提——但现在可以看清P.E.公理是什么:一阶系统能做到的最好者,被选为正确且形状可识别,并不自称能钉死ℕ。
如实记录学习成果。没有尝试书中习题。读者的贡献:(i) 在被告知之前认出公理模式是模板而非真理——独立发现模式/实例区分;(ii) 抓住“解释”这一术语未经定义却承担关键作用,促成术语表;(iii) 自行说明一阶/二阶区分,逐项评估——核心正确,纠正两处错误;(iv) 精确定位链1初稿卡住的关节(步骤2→4→5),暴露未陈述的求值规则;(v) 整理本身——认出一周脚手架中哪些承重、哪些可舍弃;(vi) 在续谈中质疑“R不可刻画”的论证循环,迫使区分条件性定理与存在性定理,并提出自己的链供评估,暴露恰切性本为前提、却被误放成结论;(vii) 拒绝充满比喻的剖析段落(“资格”“膨胀”“墙”),迫使展开时发现论证中的真正错误(见B18)。仍欠三个回答(第十部分)。7月25日续谈又增加三项贡献:(viii) 通过对照书页,发现本文误述L₅、L₇、N₁₂;(ix) 未经提示想起7月22日封装式(“我们通过封装式已经有自己的代入版本——这里有什么不同?”),成为第十一部分的组织问题;(x) 对双重守卫字符串提出精确异议(“读起来仍像v₁ = v₁′——不是矛盾吗?”),其解答——区域分析——是第十一部分最锋利的一项。
第一部分——公理系统P.E.:公理是什么
系统。P.E. = 带指数运算的皮亚诺算术(标准PA只有+与·;斯穆里安添加E以使哥德尔论证顺畅,之后说明如何消去它)。公理有十九种可机械识别的形式,分四组:第一组(L₁–L₃,命题逻辑),第二组(L₄–L₇,带同一性的一阶逻辑),第三组(N₁–N₁₁,十一条算术公理),第四组(归纳模式)。计数:3+4+11+1=19。两条推理规则:肯定前件(由F与F ⊃ G得到G)与概括(由F得到∀vᵢF)。可证 = 从公理经规则可达。
模式与公理——本次第一次纠正,由读者在受教之前作出。L₁写作(F ⊃ (G ⊃ F))。这不是该语言的公式:F、G不是P.E.的符号。它是我们谈论关于公式之事的层次上的模板——与第二章r、d、f所处的元语言层次相同。公理是实例:填入实际公式(如F := (0̄ = 0̄),G := (0̄ ≤ 0̄)),便出现真正公理。第一、二、四组是模板,各有无限多个实例;第三组奇怪的标题(“各只有一个公理的模式”)意味着N₁–N₁₁是普通的单个公式——没有空位待填的模板。
在哪个意义上“正确”。恰是第二章的意义,没有更多神秘之处:句子正确,当且仅当在预期解释中为真;有自由变量的公式正确,当且仅当对变量的每个值都为真。所以(v₁ + 0̄) = v₁正确,是因为0+0=0、1+0=1、2+0=2……仅此而已。这里“公理”意指“指定的正确起始公式”,选择受三个约束:(a)正确,否则机制会生成假话;(b)仅凭形状可识别,笨程序也能检查是否公理,这正是§II算术化将依赖的内容;(c)足以满足本章目的。选择的是工具箱,而非发现真理——斯穆里安把第一、二组归功于Kalish–Montague 1965;别的书选择不同的等价列表。
两类组,两种正确意义。第一、二组的每个实例在任意解释中都为真——仅凭⊃、∼、∀、=的含义为真,与题材无关(“有效”)。第三、四组特定地对ℕ为真,别处可以失败:在十二小时钟面上,∼(0̄ = v₁′)为假(11′ = 0)。每条算术公理都是一个过滤器,淘汰竞争解释。
阶梯(戴德金—皮亚诺)。算术公理背后的想法:ℕ是一架阶梯——底阶0;每阶有唯一下一阶(′);0不是任何一阶的下一阶;不同阶有不同下一阶;以及归纳——凡在0成立且可逐阶上升者,在所有地方都成立(没有侧枝,没有不可达的阶)。然后,+、·、E、≤不是额外假设,而是搭在阶梯上的递归配方:n + 0 = n与n + m′ = (n + m)′钉定每个加法事实。课中算例:
3 + 2 = 3 + 0′′ = (3 + 0′)′ = ((3 + 0)′)′ = ((3)′)′ = 5
——每个等式都来自两条加法公理之一。乘法是重复加法(n·0 = 0,n·m′ = n·m + n),E是重复乘法(n E 0 = 1,n E m′ = (n E m)·n),≤逐步刻画(n ≤ 0当且仅当n = 0;n ≤ m′当且仅当n ≤ m或n = m′;任意两个数可比较)。第四组是多米诺原则,每个公式F(v₁)对应一个实例:
N₁₂ : (F[0̄] ⊃ (∀v₁(F(v₁) ⊃ F[v₁′]) ⊃ ∀v₁ F(v₁)))
[7月25日纠正——本文初稿以字面代入F(0̄)、F(v₁′)展示该模式。书中公理用的是方括号F[0̄]与F[v₁′]——7月22日的封装式——恰为使F保持未拆开;代入版本是被证明与方括号相合的等价式,而非公理本身。见第十一部分。]
机制与题材。第一、二组是题材中立的推理机制(几何形式化中也会完全相同);第三、四组是算术种子。规则保持正确性,所以一切可证者都正确(可靠性)。本章要达到的定理是逆向不成立:某些正确句子不可证。奇妙之处不在公理,而在它们生成者与真者之间的缺口。
第二部分——实质条件式,以及L₁–L₇的含义
真值表,以及为何被迫如此。F ⊃ G的定义是:F真、G假时为假;其他三种情况为真。这不是关于日常语言的主张,而是让“对每个n:F(n) ⊃ G(n)”意指“没有反例”所付的代价。检查“如果n可被4整除,则n是偶数”:n = 8(真、真),n = 6(假、真),n = 3(假、假),这些都不应破坏全称主张;只有可被4整除的奇数(真、假)才会。所以第1、3、4行必须算真。读者有理由抗拒的后果是它与日常“如果—那么”冲突:后件为真,条件式就真;前件为假,条件式就真(“如果1 = 0,那么0 = 0”为真)。这一冲突很著名——实质蕴涵悖论——不会消失;⊃刻意放弃日常语言对关联的要求,只保留真值记账,因为机器能检查的就是记账。
各逻辑模式及其任务:
- L₁ : (F ⊃ (G ⊃ F))——“真话被任何东西蕴涵”。分两种情况验证:F真→G ⊃ F后件真,因而真,所以整体是真⊃真;F假→前件假,直接为真。不论F、G意味着什么,每个实例都真:一个重言式。
- L₂ : ((F ⊃ (G ⊃ H)) ⊃ ((F ⊃ G) ⊃ (F ⊃ H)))——分配:在持续假设下的肯定前件。若由F可得G ⊃ H,且由F可得G,则由F可得H。它使机制能在“假设F……”内部串联步骤。
- L₃ : ((∼F ⊃ ∼G) ⊃ (G ⊃ F))——换质换位:教机制如何让∼与⊃交互;反证法的前身。[读者仍欠逐情况检查——第十部分。]
- 这三条加肯定前件,生成所有重言式(命题恰切性——接受,未证明)。
- L₄ : (∀vᵢ(F ⊃ G) ⊃ (∀vᵢF ⊃ ∀vᵢG))——∀对⊃分配。
- L₅ : (F ⊃ ∀vᵢF),条件是vᵢ不在F中出现——空量化不增加任何东西。附加条件不可少:否则,(v₁ = 0̄ ⊃ ∀v₁(v₁ = 0̄))就会是公理,而它在v₁ = 0时为假。[7月25日纠正——初稿写成“不自由出现于F”。书中的条件是“根本不出现”,加强是有意的:出现只需扫描符号,自由性需解析作用域,避免后者是系统的设计主题——第十一部分。]
- L₆ : ∃vᵢ(vᵢ = t),条件是vᵢ不在t中——每个项都有值。附加条件阻止∃v₁(v₁ = v₁′)。
- L₇ : (vᵢ = t ⊃ (X₁vᵢX₂ ⊃ X₁tX₂)),其中X₁vᵢX₂是原子公式(等者替换):若变量vᵢ等于项t,在原子公式内以t替换vᵢ的一次出现保持真——这使=意指同一性。实例:(v₁ = 0̄′ ⊃ (v₁ ≤ 0̄′′ ⊃ 0̄′ ≤ 0̄′′))。[7月25日纠正——初稿写“若t₁ = t₂,在原子陈述内互换它们”,那是可导出的一般形式,而非公理;变量而非项、一次出现、原子性这些限制各自都承重——第十一部分。]
第三部分——解释与逻辑的两个阶
解释——此前未定义的术语。公式本身只是墨迹。解释指定:(1)论域D,即∀v₁遍历什么;(2)0̄命名哪个对象;(3)′、+、·、E对对象做什么,以及何时≤成立。只有这样,每个句子才变为真或假。预期解释:论域0、1、2……,符号按标准含义;正确(整个第二章)=在这里为真。课中评估的竞争者:十二小时钟面(通过(v₁ + 0̄) = v₁,却不通过∼(0̄ = v₁′),因为11′ = 0)以及单对象世界(甚至0̄ = 0̄′也为真)。有效=在每个解释中真(第一、二组)。给定公理的逻辑后果=在每个通过它们的解释中真。
阶 = 量词遍历什么。零阶:没有量词(命题逻辑)。一阶:量化论域的对象。∀v₁((v₁ + 0̄) = v₁)覆盖所有数——一阶对对象的全称性是完全的。二阶:额外量化性质(=论域的子集):新变量P、Q;新原子形式P(v₁);量词∀P。一阶语法不能说的唯一一件事是“对每个性质”——归纳正卡在这里:皮亚诺自己的归纳公设天然是二阶的(“对每个性质:……”),P.E.必须用一个模式模拟它,每个可由公式表达的性质一条公理。这种替代悄悄有损:公式可列举(有限字符串、有限字母表——第二章的枚举),数的集合不可列举(第二章的对角论证),所以模式只覆盖不可数性质总体中的可数一片。
已纠正的错误(读者自己的表述,经评估):一阶逻辑不是不能“覆盖所有自然数”——它覆盖所有数,却不能覆盖所有性质。阶之间的全部区分,就在这一条语法规则。
第四部分——恰切性与不完备性:术语表及三个定理
“完备性定理”(1930)与“不完备性定理”(1931)的名称碰撞,只是历史上的不巧;本次把前者改称恰切性,把“完备”保留给整个系统。确定的术语如下:
- 机器——一份有限指令表,仅凭形状检查,永远机械地产出(“打印”)字符串。每个证明系统决定一台机器(打印公理,对已打印者应用规则)。证明=打印。机械的=可由这样的有限指令表运行——没有预言机,没有无限查表。
- T——在预期解释中为真的句子集合。
- 通过/幸存者——解释若使全部公理为真,就通过它们。
- ℕ的副本——仅把对象改名的ℕ;恰使同样句子为真。
- 冒牌者——不是ℕ副本的幸存者。
- 可靠(对于目标集合)——不打印目标之外的任何东西。
- 恰切——无论喂入哪些公理,机制打印其每个逻辑后果:打印集=后果集,精确相等。
- 职责(喂入一批公理的机制)——后果集本身:在这批公理的每个幸存者中为真的句子。所以“恰切”=打印列表与职责重合。
- 完备/不完备(对可靠系统)——打印全部T/遗漏某些真理。
- 范畴的——公理的唯一幸存者是同一个世界的各个副本。
三个定理,各一句话:
- 戴德金1888:二阶皮亚诺公理是范畴的。(只关于解释的定理——其中不出现证明、机器、打印;那些概念当时还不存在。)
- 哥德尔1930(恰切性):一阶逻辑存在恰切机制——第一、二组加两条规则。凡从公理逻辑地推出者,机器都打印;增加更多有效逻辑公理会缩短证明,却从不产生新定理。(对逻辑而言,工具箱被证明已经完成——回答“只有这十九个模式吗?”:逻辑模式被证明足够;算术模式被证明永远不够。)
- 哥德尔1931(不完备性):没有对T可靠的机器打印全部T。等价地,用第七部分采用的形式(机器界限):没有机械机器精确打印T——精确打印T将同时具有可靠性与完备性。(书中定理;第三章为特定系统P.E.证明它,完全一般的机器形式将在后面的抽象章节取得——同一构造,覆盖范围扩大。)
为何不矛盾——跷跷板。机制的义务由定义固定:打印在公理的所有幸存者中为真的一切,即职责。所以,职责大小取决于幸存者群:幸存者多→在全部幸存者中为真的句子少→职责小;幸存者少→职责大。一阶公理不能把幸存者筛到只剩ℕ副本(B6直接证明),所以职责严格小于T——而1930年定理说明,这较小职责恰好是机器可做的。漏洞不是恰切性要克服的错误;正因存在漏洞,才有可达的终点。二阶公理把幸存者筛到只剩ℕ副本(戴德金=链1),职责扩大为整个T,1931年定理禁止任何机器覆盖它。因此:一阶机制之所以完备,是因为其语言太弱,提不出不可能的要求;强语言与强机制不可兼得。P.E.的不足从来不在机制:不可证真理之所以不可证,是因为它们并不从公理逻辑地推出——每个都在某个幸存的冒牌者中为假。
三个分开的账本(续谈取得的区分):幸存者群是世界的集合;职责与打印列表是句子的集合。“有冒牌者幸存”是关于群的事实;“可证者少于真者”是关于打印列表的事实;恰切性把打印列表=职责焊在一起。只有有异议的冒牌者——就某个句子与ℕ不一致者——才缩小职责;无异议的冒牌者(不是副本,却在每个句子上都与ℕ一致)什么也不缩小。箭头从打印缺口指向有异议的冒牌者(四行推论),绝非反向。
课中纠正的两项归属:戴德金没有证明“每个真理都可证”(他的定理里没有证明概念);1930年定理也没有说“所有机器都恰切”(几乎没有机器如此——它说一阶逻辑至少存在一个恰切机制)。
第五部分——链1:二阶句子A钉定ℕ(戴德金)
这是本次唯一完全掌握的形式结果,采用7月23日格式:先陈述可引用的求值规则与定义,使用前解析每个字符串,每一步按名称给出理由。链的初稿卡在读者的精确问题上——步骤2如何通向步骤4,Ind的内容重要吗?——由此暴露未陈述的规则(R3,实例规则)。一旦陈述,卡点便消解。
求值规则。世界M = (D, z, s):论域D,由0̄命名的对象z,′意指的运算s。
- R1(字典):0̄ → z;t′ → s(t的值);t₁ = t₂断言对象相同;∼、∧、⊃按其真值表解释。
- R2(对象上的∀):∀v₁φ在M中真 ⟺ 对D的每个对象x,在x处的实例(把φ中的v₁读作x)为真。用途:(i)一个假实例使全称式为假;(ii)真全称式可在任何所选实例处兑现。
- R3(性质上的∀):∀Pφ在M中真 ⟺ 对D的每个子集S,在S处的实例(把φ中的P(t)读作“t的值∈S”)为真。即把R2的指标集从对象换成子集;两种用途相同。
- R4(⊃的那一行):真条件式+真前件 ⇒ 真后件。
定义。
- D1(通过/幸存者)、D2(ℕ副本)、D3(冒牌者)——同第四部分。
- D4(压缩):一批公理若是一个有限句子,其幸存者恰为ℕ副本,就压缩ℕ。(第七部分扩展到无限列表。)
- D5(可达部分、杂项/异类):在(D, z, s)中:R := {z, s(z), s(s(z)), …}——从z经有限多个s步骤到达的对象。R外的对象是杂项,第七部分称为异类(aliens)。R由我们在元理论中定义——如7月22–23日的r、d、f,无论是否有公式描述它,它都存在。
字符串及其解析。
S1 := ∀v₁ ∼(v₁′ = 0̄) — 在M中:“z不是任何对象的后继”(R1、R2)
S2 := ∀v₁∀v₂(v₁′ = v₂′ ⊃ v₁ = v₂) — 在M中:“不同对象有不同后继”
Ind := ∀P( (P(0̄) ∧ ∀v₁(P(v₁) ⊃ P(v₁′))) ⊃ ∀v₁ P(v₁) )
A := S1 ∧ S2 ∧ Ind — 一个有限字符串
通过R3解析Ind——实例以D的子集S为指标:
Instance(S):“若z ∈ S,且S可攀升(x ∈ S ⇒ s(x) ∈ S,对所有x ∈ D),则D的每个对象都在S中”
M中的Ind:“对D的每个子集S:Instance(S)”
一阶替代——模式,每个公式F(v₁)对应一个句子:
Ind_F := (F(0̄) ∧ ∀v₁(F(v₁) ⊃ F(v₁′))) ⊃ ∀v₁ F(v₁)
解析:取被刻画的集合C_F := {x ∈ D : F在M中对x为真}——集合构造记法:D中使F对之成立的所有x的集合,是成员资格检验,而非断言;它是第二章“F表达的集合”,从ℕ相对化到正在受检的世界M——M中的Ind_F恰好说Instance(C_F)。所以模式只在被刻画的集合上保证条件式(每公式一个,可列举地多);Ind则在每个子集上保证它。C_F依赖F与M两者:(v₁ = v₁)刻画D,∼(v₁ = v₁)刻画∅,第二章的偶性公式在ℕ中刻画偶数。“M中R可被刻画”意指:某个公式F满足C_F = R——精确重合,而非仅仅⊆或⊇。
链1。已知:句子A。目标:A的每个幸存者都是ℕ副本(D4)。
步骤1。设M = (D, z, s)通过A:S1、S2、Ind各自在M中真。(D1。)
步骤2。对D的每个子集S,Instance(S)在M中真。(把R3应用于Ind的解析——这一展开就是“Ind在M中真”的全部含义。)
步骤3。令R := {z, s(z), s(s(z)), …}。(D5;元理论层面——没有公式描述R,也不需要。)
步骤4。R是D的子集。(步骤3——成员由D内部的s产生。入场条件:步骤2的保证以子集为指标,子集资格是唯一要求;完全没有提及可描述性。)
步骤5。z ∈ R。(步骤3——零步可达。)
步骤6。R可攀升。(步骤3——再作一步s保持可达性。)
步骤7。Instance(R)在M中真。(由步骤4许可,把步骤2在S := R处兑现——R3的方向(ii)。二阶语法唯一发挥作用的一步。)
步骤8。Instance(R)前件真:z ∈ R,且R可攀升。(步骤5、6——从R定义得出的事实;公理对此毫无贡献。)
步骤9。Instance(R)后件真:D的每个对象都在R中——M没有杂项。(把R4用于步骤7、8——语义层面的肯定前件。)
步骤10。映射0 ↦ z、1 ↦ s(z)、2 ↦ s(s(z))……满射到D。(步骤9与步骤3。)
步骤11。该映射一一对应。(若sⁿ(z) = sᵐ(z),n < m:用S2剥去n层,得z = s^(m−n)(z),使z成为后继——与S1矛盾。两者由步骤1在M中真。)
步骤12。M是改名的ℕ——一个副本;M任意:A压缩ℕ。∎ (步骤10–11;D2、D4。)
机制反向运行——Ind如何检出不合格者。在异类世界M中(论域 = 0、1、2……,加上一架从不触及数字的异类双向阶梯……a₋₁、a₀、a₁……):S1、S2成立(无环、无合流——后继公理看不到杂项)。但R仅为数字;Instance(R)前件真、后件假(异类∉R),所以假;一个假实例使Ind为假(R3,方向(i));M不通过A。同一字符串,同一真值表:在幸存者中迫使没有杂项;在有杂项的世界中,借用该世界自身的可达部分作为证据而检出杂项。一阶模式无法完成排除:它保证的条件式只落在被刻画的集合上,没有什么保证R可被刻画——第七部分把这一观察升级为定理:在一阶列表的任何带异类幸存者中,没有公式刻画R(B13)。
第六部分——三段论、推论与整合
- 定义:公理的后承 = 在所有幸存者中真(= 职责)。
- 戴德金(= 链条1):二阶皮亚诺公理的幸存者 = 仅有ℕ的副本。
- 1 + 2:这些公理的后承 = 在ℕ的所有副本中真 = 在ℕ中真 = T。(副本使相同语句为真——D2;后承集与T实实在在就是同一集合。)
- 恰切的定义:把皮亚诺公理交给一台恰切的二阶机器,它就应恰好打印它们的后承——由3,恰好是T:全部真理,没有假话。
- 哥德尔1931:没有机器能做到这一点。
- 因此,不存在恰切的二阶逻辑机器。∎
每一步不是定义,就是链条1或1931。(本次学习中步骤3背后的具体机制:有限多个二阶皮亚诺公理合取成一个语句A,对任意算术S,“(A ⊃ S)有效 ⟺ S ∈ T”——每个算术问题都逐一折入一个关于有限字符串的有效性问题。)
四行冒牌者推论——取代更沉重的机制。已知:G在ℕ中真,在P.E.中不可证(哥德尔1931——本书自身的定理)。目标:P.E.有冒牌者幸存者。
- 从P.E.公理可证 = 在它们的所有幸存者中真。(恰切性1930——尚未偿还的债。)
- G不可证 ⇒ G并非在所有幸存者中真 ⇒ 某幸存者M使G为假。(步骤1的逆否。)
- ℕ是幸存者(公理正确),G在ℕ中真。
- M与ℕ就G有分歧,所以M不是副本(D2):M是冒牌者——一个有异议的冒牌者。∎
明确归属:冒牌者是第一不完备定理的推论(经恰切性),不是其内容——本书处理字符串与对角化;解释从未在其中出现。
整合——读者对结构的发现,以及随后的重建。本次学习另建了一套机制,回答“一阶为何在本质上不能压缩?”——一条诊断链(把链条1用于模式时,证明在哪里卡住),以及一条穷尽链(经新常元c与紧致性)。读者意识到,搭好的这套结构没有一处是承重的:三段论只需链条1、定义和1931;冒牌者存在由四行推论得出;本质问题一句便可结束——一阶缺少∀P。这套机制被舍弃。然而,在课后延续中,读者自己的问题——究竟为什么R没有被刻画?假定R ≠ D不循环吗?——又把它拉了回来,并重建为第七部分:一条链,无需紧致性,且审核了箭头方向。最终记录:
| 主张 | 状态 |
|---|---|
| A的幸存者 = ℕ的副本 | 已直接证明——链条1,没有债 |
| 二阶逻辑没有恰切的机器 | 给定1931,由六步三段论得出 |
| 一阶算术不完备;冒牌者存在 | 本书定理 + 四行推论;债:恰切性1930 |
| 一阶Σ不压缩ℕ;其冒牌者中的R未被刻画 | 已证明——第七部分,☑ G1 + ☑ G2;债:恰切性1930、机器界限、运算一致性 |
| 一阶为什么不能压缩(本质) | “缺少∀P”——现在机制可见:保证所覆盖的指标集从子集变为被刻画的集合,而会检出不合格者的集合,恰好就是任何带异类世界都不让任何公式刻画的集合(B19) |
第七部分——重建的链条:一阶Σ不压缩ℕ
同日课后延续。由读者的“为什么R未被刻画?”及循环性挑战触发;他自己提出的链条接受了逐步评定(发现恰切性被误放在结论位置——它是前提),下述修正版从与第六部分相反的一端进入跷跷板:三段论固定压缩(链条1),推出恰切性必须让步;本链条固定恰切性(1930定理),推出压缩必须让步。同一个跷跷板,从两端进入。紧致性全程不出现。
目标。
宣布两个判定时,链条即告结束;之后的步骤是剖析。
术语。第四至第五部分各项继续有效:机器、职责、恰切、T、幸存者(D1)、副本(D2)、冒牌者(D3)、刻画 / C_F、Instance(S),以及解析“M中的Ind_F恰好在说Instance(C_F)”——都援引第五部分,原样使用。新增:
- Σ := 一阶公理列表——S1、S2、算术公理及每一个实例Ind_F。归纳是模式,所以候选压缩器是无限列表而非单一语句;D4扩展为:Σ压缩ℕ,当且仅当整个Σ的每个幸存者都是ℕ的副本。
- 异类 := D5的杂项:D中位于可达部分R之外的成员——没有数码为它命名;从z逐次施行s计数,永远到不了它。
已知。(i) 恰切性定理——一阶逻辑有恰切机器,打印列表 = 职责;(ii) 机器界限——没有机械式机器恰好打印T。两者都是俯瞰层面的结论,列在债务表中(第5、6项)。
链条。
B1。将Σ载入恰切机器。其打印列表 = duty(Σ) = 在Σ的每个幸存者中真的语句集。(已知i;职责。)
B2。假设Σ压缩ℕ:Σ的每个幸存者都是ℕ的副本。(待反驳的假设;Σ。)
B3。ℕ自身是Σ的幸存者——列表上的每条公理都正确,即对ℕ为真。(第一部分;D1。)
B4。那么duty(Σ) = T。一个方向:对ℕ真的语句对每个副本真(D2),因而对每个幸存者真(B2),所以在职责中。反方向:职责中的语句在每个幸存者中真,尤其在ℕ中真(B3),所以在T中。(B2、B3。)
B6。一台恰好打印T的机械机器与机器界限矛盾。所以B2的假设不成立:☑ 判定G1——Σ不压缩ℕ。固定一个不是副本的幸存者M = (D, z, s, …):一个冒牌者。(已知ii;D3。)
B7。留意什么没有失效:机器依旧恰好打印其职责——矛盾处决的是假设,不是恰切性。冒牌者与恰切性共存;M的幸存只是让duty(Σ)严格低于T。(B6;跷跷板。)
B8。M有异类。因为若R = D——M每个对象都可达——M便是ℕ的副本:数码命名的不同对象组成后继链(S1、S2——链条1步骤10–11的论证),算术公理将已命名对象上的+、·、E、≤固定为ℕ的运算表(运算一致性:俯瞰层面,债7)。副本与B6矛盾。所以R ≠ D。(B6;D5。)
B9。朝G2推进:假设某公式F刻画R——C_F = R。(待反驳的假设;刻画。)
B10。Ind_F在Σ列表上,M幸存于Σ,所以Ind_F在M中真;而M中的Ind_F恰好在说Instance(C_F)——由B9,即Instance(R)。(D1;援引第五部分的解析。)
B11。Instance(R)的前件在M中真:z ∈ R,且R可攀升。(D5——零步可达;多施一次s保持可达性。原样沿用链条1步骤5–6。)
B12。所以Instance(R)的后件真:D每个对象都在R中——R = D。(把R4用于B10、B11。)
B13。这与B8(R ≠ D)矛盾。所以B9假设不成立:☑ 判定G2——没有公式在M中刻画R。(B8、B12。)
两项判定已得出。以下是剖析:M如何既通过每条归纳公理又保留异类,以及为什么链条1的证明从来不能直接迁移。(这一段起初用隐喻——“资格”“膨胀”“墙”——讲述,被拒绝;下述展开取代了它,并在过程中抓出一个错误:见B18。)
B14。给Instance(S)前件对任意集合S检验的两个条件命名:(a) z ∈ S;(b) S可攀升。(拆开Instance(S)的前件,以便复用。)
B15。满足(a)和(b)的任何集合S都包含整个R。(由(a),零步可达对象在S中;由(b),若n步可达对象在S中,则n+1步可达对象也在S中;R的成员恰好是有限步可达对象——D5。)
B16。若S满足(a)和(b)但S ≠ D,称S为破坏者。破坏者恰好就是使Instance(S)为假的集合:前件真、后件假——真值表唯一为假的一行。由B15,每个破坏者都包含整个R,并漏掉至少一个异类。而R自身就是破坏者:由B11满足(a)(b),由B8知R ≠ D。
B17。任取公式F,问M幸存于Ind_F要求什么。依真值表分两种情况:情况1——C_F不满足(a)或(b):Instance(C_F)前件假,故在M中自动为真,不论C_F的其它情况。情况2——C_F满足(a)和(b):则Instance(C_F)仅当C_F = D才真;M幸存,所以C_F = D。(D1;真值表。)
B18。所以M幸存于每条归纳公理,是因为没有公式刻画破坏者:每个被刻画的集合都属于情况1(无条件为真)或情况2(等于D——不是破坏者)。M中存在破坏者——R是一个,任何包含R却漏掉某异类的集合也是——但把B9–B13中的R换成任何破坏者,论证原样成立:若它被刻画,其自身实例便迫使它等于D,与“漏掉异类”矛盾。会使归纳为假的那些集合,没有任何Σ公理谈到。(B13、B16、B17。)——展开时发现的修正:早稿说“只有R有资格却不是D”。错——每个破坏者都是。论证要求它们全都未被刻画,也确实证明了这一点。
B19。为什么链条1的证明不能迁移——把实际字符串并排放置。二阶公理是单一语句Ind := ∀P(…),由R3,“Ind在M中真”展开为链条1的保证,援引如下:
步骤2。对D的每个子集S,Instance(S)在M中真。
——每个子集对应一个真的条件式,无例外——链条1用两步在R兑现了它(步骤4:R ⊆ D,子集资格是唯一门票;步骤7:Instance(R),兑现)。Σ不包含语句Ind——字符串∀P不在其语法中;取而代之的是各条独立公理Ind_F,幸存于Σ只保证:
对每个公式F,Instance(C_F)在M中真。
指标集变了:D的子集 → M中被刻画的集合。R的子集资格换不来任何东西;要重现链条1的步骤7,需要R属于新指标集——某F使C_F = R——而B13说M中不存在这样的F。Instance(R)这个一旦为真就迫使R = D并排除异类的条件式(链条1,步骤7–9),在M中为假——前件由B11为真,后件由B8为假——一个存在于该世界中的假实例,却不由列表上的任何公理断言。Σ从未说出那句会判M不合格的话。∎
图示。
R(可达) ‖ 异类(不可达)
z → s(z) → s(s(z)) → ⋯ ‖ ⋯ → a → s(a) → s(s(a)) → ⋯
‖
没有公式画出边界 ‖(B13):
被刻画 + (a) + (b) → 该集合是整个D (B17,情况2)
R有(a) + (b)且不是整个D (B16:一个破坏者)
→ R未被刻画——其它破坏者也一样 (B18)
尾声——门票变化,以及一处明示的陷阱(不承重)。
二阶Ind:保证以子集为指标 ——R的门票:R ⊆ D ✓ (链条1,步骤4)
一阶Σ: 保证以被刻画的集合为指标 ——R的门票:某C_F = R ✗ (B13)
计数使门票变化代价高昂——公式是有限字符串,所以被刻画的集合仅有可列多个,对应的子集却有不可列多个(第二章的对角线)。但明确指出这处陷阱:“存在未被刻画的集合,因此异类存在”无效。ℕ自身有不可列多个未被刻画的子集,异类却为零。覆盖稀疏只是未能禁止带异类世界;真正产生一个这种世界的是B1–B6——恰切性加机器界限,仅此而已。反向路径也不循环:“带异类世界 ⇒ R未被刻画”(B9–B13)是条件定理,其假设由存在定理(B1–B8)落实;箭头从未闭合成环。在副本中,R确实被刻画——由(v₁ = v₁)。
第八部分——区分记录
| 提出的困惑 | 一行解答 |
|---|---|
| “这些公理不像普遍真理——更像语句结构” | 两方面都对:模式是元语言模板(实例才是公理);“正确”指在预期解释中真——选定的真理,而非不证自明的真理。 |
| “即使F真,‘G ⊃ F’也不是自动真吧?” | 在真值表下就是:G ⊃ F仅当G真、F假才假,F真已排除这情况。⊃就是真值表,不是自然语言的“如果—那么”;不适来自实质蕴涵悖论,而希望∀断言意为“没有反例”,就迫使采用这张表。 |
| 为什么恰好这19个模式——会不会发现更多? | 选定的工具箱,不是发现的全体:约束是正确性 + 形状可识别性 + 充分性。逻辑方面:可证明已完成(恰切性1930)。算术方面:可证明永远不可能完成(1931)——不可能结束搜寻正是定理。 |
| “完备性定理”与“不完备性定理” | 对象不同:1930关于机制(打印全部逻辑后承——改称恰切性);1931关于以T为目标的系统。它们组合起来:机制完美;任何公理库存都无法让后承达到T。 |
| 使用了“解释”却从未定义 | 论域 + 0̄的指称 + ′、+、·、E、≤的意义。真只相对于某个解释存在。检验过的竞争解释:十二小时钟、单对象世界。 |
| “一阶从不声称真理覆盖所有自然数” | 说反了:∀v₁覆盖所有数;一阶不能说的是“对所有性质”。界线就是这一条语法规则。 |
| 一阶较小的义务是哥德尔之后的“退却” | 没有意志主体,也没有时间线:职责从定义上一直是“在所有幸存者中真”;冒牌者幸存才使它低于T。泄漏使终点可达。 |
| “戴德金证明二阶逻辑完备(每个真理都可证)” | 他证明的是范畴性——仅关于解释的陈述;其中没有证明概念。 |
| “哥德尔证明所有机器都恰切” | 1930说,一阶有一台恰切机制。几乎没有机器是恰切的。 |
| 什么禁止二阶真理是有限字符串? | 没有——它们就是有限字符串,二阶证明机器也存在且正常运行。不可能的是一台机器恰好打印有效集:其职责包含全部T。 |
| ∀P为什么将职责扩大到全部T? | 跷跷板 + 排水:职责 = 在所有幸存者中真;∀P让归纳检验任意世界的每个子集,把幸存者排到只剩ℕ副本;于是“在所有幸存者中真” = T,这是定义使然,不是志向使然。 |
| 步骤2如何通向步骤4——哪个实例?Ind内容要紧吗? | 缺失的规则现已声明(R3):∀P实例以子集为指标;子集资格是R的入场券(步骤4);Instance(R)是具体条件式“z ∈ R且R可攀升 ⇒ R是一切”——内容至关重要,R4把它变成没有杂项。 |
| C_F := {x ∈ D : F在M中对x真}——“x属于D而且F真”? | 集合构造式:成员检验,不是合取——由通过检验的x组成的集合。它是第二章“F表达的集合”相对于M的版本;依赖F和M二者。 |
| “哥德尔第一定理确立了冒牌者存在” | 推论,不是内容:本书证明不可证的真理;给定恰切性,冒牌者由四行得出。 |
| “一阶逻辑不完备” | 术语问题:逻辑(机制)恰切——无缺陷;一阶算术系统不完备。 |
| “冒牌者幸存”与“可证者低于真理”——同一主张? | 两本不同的账:世界与语句。幸存者群的事实与打印列表的事实,由恰切性(打印 = 职责)焊接起来。且只有有异议的冒牌者(就某语句与ℕ分歧)才缩小职责;无异议者不会。箭头从打印缺口指向有异议的冒牌者,从不反过来。 |
| “为什么R未被刻画?假定R ≠ D看来循环” | 不循环:“带异类世界 ⇒ R未被刻画”是条件定理(B9–B13);异类存在有独立证明(B1–B8);两者都不引用对方结论。在副本中,R被刻画(v₁ = v₁)。 |
| “未被刻画的集合存在(计数),所以异类存在” | 无效——已指出的陷阱:ℕ有不可列多个未被刻画的子集,异类却为零。计数解释停滞;只有恰切性 + 机器界限才产生冒牌者。 |
| “……所以一阶不能压缩,所以恰切机器存在” | 箭头颠倒:恰切性是直接证明的定理——一个前提(B1)。固定恰切性,跷跷板迫使压缩让步(B6),不是反过来。 |
| “资格”“膨胀”“墙”(被拒绝的导师简语) | 兑现为:资格 = 前件对(a) z ∈ S、(b) S可攀升(B14);膨胀 = 该集合自己的实例迫使它等于D(B17);墙 = 没有公式画出的R/异类边界(B13)。展开抓出了真实错误——见下一行。 |
| 证明停滞与主张被反驳 | 链条1不能迁移(B19)只是诊断;它并未证明关于幸存者的任何事。“只有R是危险集合”也错了——每个破坏者(B16)都危险,B18说明它们都未被刻画。 |
第九部分——自测
先答再看。
- 模式与公理:L₁是什么,其公理是什么,哪些组的模式恰好只有一个实例?
- P.E.公理正确的两种意义——以及一个具体的竞争解释与它使之为假的公理。
- 写出⊃的真值表,从普遍断言“无反例”的读法推出它。随后分情况验证L₁。
- 定义:解释、幸存者、副本、冒牌者、逻辑后承、职责、恰切、完备、范畴的。
- 三个定理(戴德金1888、哥德尔1930、哥德尔1931),各用一行——以及各自关于什么(解释?机制?系统?)。
- 陈述R3。对Ind而言,Instance(S)究竟是什么?使用全称命题的两个方向是什么?
- 重现链条1(十二步,附理由)。二阶语法在哪唯一一步起作用?R的“入场券”是什么?
- 反向运行判定:在异类世界中,说明Instance(R)为假,推出Ind在那里失败。S1、S2为什么看不到异类?
- 在异类世界中,令S = 整个论域,求Instance(S)的真值。真还是假?这对为何必须用R来判定不合格说明了什么?(也是本次学习仍欠的项目——见第十部分。)
- 六步三段论:二阶逻辑为何没有恰切机器。哪些步骤是定义,哪些是定理?
- 四行冒牌者推论:从1931推出P.E.的冒牌者存在。它带着哪项债?
- 一阶归纳模式为什么仅覆盖“不可数全体的一个可数切片”?指出发挥作用的两个第二章事实。
- 陈述第七部分两项判定G1、G2,并给出通往G1的链条(B1–B6)。它依赖哪两项俯瞰层面的债,分别在哪一步?
- 定义破坏者。证明每个破坏者都包含整个R,并用B17的两个情况解释:M虽然包含破坏者,仍如何幸存于每个Ind_F?
- 评定这一推理:“公式可数而子集不可数,因此冒牌者存在。”再评定:“R未被刻画,因此异类存在。”
答案
- L₁ = (F ⊃ (G ⊃ F)),是元语言模板,不是公式;其公理是代入实际公式后的实例。第三组的十一个模式各有一个实例(没有占位符);第一、二、四组各有无限多个。
- 第一至二组:有效——单凭逻辑符号的意义,在每个解释中真。第三至四组:正确——特定地在预期解释中真。竞争解释:十二小时钟使∼(0̄ = v₁′)为假(11′ = 0),却通过(v₁ + 0̄) = v₁。
- F ⊃ G仅在(T, F)为假。必须如此,因为“对每个n:F(n) ⊃ G(n)”必须意为“没有反例”:实例(T,T)、(F,T)、(F,F)不能使它失败——用“被4整除/偶数”在n = 8、6、3处检查。L₁:F真 → G ⊃ F后件真,所以真,整个为T⊃T;F假 → 前件假,所以真。
- 解释:论域 + 0̄的指称 + ′、+、·、E、≤的意义。幸存者:使所有公理真。副本:改名的ℕ,相同语句真。冒牌者:幸存者,但非副本。后承:在所有幸存者中真。职责:所载入公理的后承集。恰切:打印列表恰好等于职责。完备:可靠且打印全部T。范畴的:幸存者 = 某一个世界的副本。
- 戴德金:二阶皮亚诺公理范畴——仅关于解释。1930:一阶逻辑存在恰切机制——关于机制。1931:没有对T可靠的机器能打印全部T(等价地:没有机器恰好打印T)——关于每个以算术真理为目标的系统。
- R3:∀Pφ在M中真 ⟺ 对D每个子集S,把P(t)读作“t的值∈S”的φ为真。Instance(S) = “若z ∈ S且S可攀升,则D每个对象都在S中”。用法:一个假实例使全称命题为假;真的全称命题在任意选定实例处兑现。
- 原样复述第五部分。二阶语法只在步骤7起作用(在S := R处兑现,由R3许可)。入场券:仅是子集资格(步骤4)——R3的指标集中全无可描述性。
- R = 数字;Instance(R)前件真(0 ∈ R,数字的后继仍是数字);后件假(异类∉R);Instance(R) = T ⊃ F = 假;由R3(i),Ind在M*中假。S1、S2仅监管环与合流——异类阶梯两者皆无;后继公理看不到杂项。
- 真——信息空洞:S = D时,后件“每个对象在D中”自动真,所以Instance(D)成立。判定不合格需要前件成立而后件失败的子集——在有杂项的世界中,只有世界自身的可达部分R做到这一点;轻易的子集证明不了什么。
- 第六部分。步骤1、4是定义;步骤2是链条1(戴德金);步骤5是1931;步骤3、6是组合。
- 可证 = 在所有幸存者中真(恰切性——债);G不可证 ⇒ 在某幸存者M中假;ℕ幸存且G真;M不是副本 ⇒ 冒牌者。
- 公式可列(有限字母表上的有限字符串——第二章列表);数集不可列(第二章对角线:任意集合列表都漏掉D = {n : n ∉ Sₙ})。每个公式一条公理 ⇒ 归纳仅在不可列多个性质中的可列多个性质上得到保证。
- G1:Σ不压缩ℕ(某幸存者不是副本)。G2:该幸存者中没有公式刻画R。通往G1的链条:装入Σ的恰切机器打印其职责(B1,债:恰切性);假设压缩(B2);ℕ幸存(B3);于是职责 = T(B4);机器恰好打印T(B5);与机器界限矛盾(B6,债:1931的一般机器形式)——所以压缩失败。债在B1、B6。
- 破坏者:满足(a) z ∈ S和(b) S可攀升,但S ≠ D的集合——恰好使Instance(S)为假。包含R:由(a),零步对象在其中;由(b),每多走一步仍在其中;R恰好是有限步可达对象。B17:对每个F,或C_F不满足(a)/(b)——Instance(C_F)因前件假而真——或C_F两者都满足,且因M幸存,C_F = D。不论哪种,被刻画的集合都不是破坏者;破坏者(包括R)是任何公理都未谈到的集合。
- 两者都无效。第一:ℕ有不可数多个未被刻画的子集,异类却为零——计数解释停滞,从不产生冒牌者;冒牌者来自恰切性 + 机器界限(B1–B6)。第二:方向反了——“R未被刻画”是从异类性证明的(B9–B13,条件定理);副本中的R由(v₁ = v₁)刻画。
第十部分——进度、待办、债与方法
进度:已开始第三章。已阅读并在概念上整合§1(公理系统P.E.)——十九模式是什么、为何正确、如何配合。(7月25日更新:下述暂缓的逐义梳理现已大体完成——第十一部分按正式编号记录N₁–N₁₁,对照书页修正L₅/L₇/N₁₂字符串,并展开“讨论”段所称绕开代入与自由/约束的含义。)本章形式工作尚未动手:其余公理的逐义梳理因旁论暂缓;回到书中要从§2(公理系统的算术化——“x是y的证明”成为算术关系)继续。第十一部分把联系具体化:这些公理经过设计——用出现扫描与单切替换代替代入——使§2的“x是公理”只需付出连接的成本。留意已经可见的联系:恰是算术化使任意机器可在算术内部描述,而这驱动1931的对角化——每台候选真理打印机背后的机制。
读者欠下三项:(1) L₃分情况检验——((∼F ⊃ ∼G) ⊃ (G ⊃ F)),只用真值表检查四个真值组合;(2) 祖先解释——找一个使(v₁ ≤ v₂ ∨ v₂ ≤ v₁)为假的解释(已记提示:论域 = 人,≤读作“是……的祖先”);(3) 整个论域的实例——自测9。
债务表:原有四项(消去E;素数基底13;性质1 ⇒ 性质2;机械的 ⇒ 算术的),新增三项,都只限于俯瞰评述,不在本书路线中:(5) 1930恰切性定理——四行推论、跷跷板及B1的承重前提;(6) 1931的一般机器形式(机器界限)——第三章为P.E.证明它;推广到所有机器在后面抽象章节;现为B6的承重前提;(7) 运算一致性——R = D的幸存者是完整副本(数码的后继链是链条1步骤10–11;+、·、E、≤在已命名对象上与ℕ运算表一致,只是断言,尚未推出)——为B8承重。原先第八项——存在没有公式刻画R的世界——不再是债:它是定理B13。7月25日延续新增一项:(8) 从L₆ + L₇得到实例化——缺失的公理∀v₁F ⊃ F(t)可从L₆、L₇、第一至二组及两条规则恢复为定理(在第十一部分§7断言,未推导;这是卡利什–蒙塔古表述恰切性的部分内容)。
方法——第三种失败方式、新工具与延续部分的教训。7月22日:生动的新造词承担实质工作,会阻滞解释。7月23日:过度压缩与自然语言改述都失败;有效通道是符号 + 附理由的链条。今日发现第三种失败方式:隐喻堆叠——“跑步机”“终点线”“蓝图”,每段多个,各含实际内容,却全未兑现(“我不知道是哪里的问题,也许是你的语言,也许是你的类比——我觉得你的解释很难理解”)。按发现顺序,起效的是:(a) 朴素、单一词汇的重述(机器/打印)——部分奏效;(b) 读者说出自己的理解,逐块评定——有效,且错误被精确定位;(c) 任何论证前先固定一份可援引的定义表,然后定理,再链条——读者自己的处方,也是转折点;(d) 完整展开,并将求值规则声明为有编号、可援引的项目——诊断发现,链条停滞是因为理由暗中使用从未声明的规则(R3实例规则就是整个步骤2→4→5缺口)。工具箱新增:学习者过不去一步时,先找未声明的规则,再考虑增加文字。延续又新增两项:(e) 审核箭头方向——只有区分条件定理与存在定理,才解决读者的循环性挑战;评定其自拟链条时发现前提(恰切性)坐在结论位置;(f) 把每个隐喻展开成步骤,因为展开本身就是检查器——兑现“资格/膨胀/墙”揭出了意象隐藏的真实错误(“只有R”)。与之配套的读者技能出现两次:追踪论证的依赖结构——先舍弃不承重的部分,再要求重建版本以目标与判定明确的单一链条成立。
7月25日延续又新增两项工具。(g) 把新材料当作相对于已掌握结果的差异来教。从零搭建的卡利什–蒙塔古系统第一版解释失败了(“你的阐明方式没怎么帮到我”);起效的是读者自己的锚点——“7月22日我们有自己的封装式代入版本——这里有什么不同?”——随后一切成为一次比较:同一技巧,一个前提条件失败,一项修复。与已掌握结果呼应的新材料,应作为差异来教,而非一个全新主题。(h) 感到矛盾就是数据——定位无效步骤,再找出直觉在哪正确。“读起来还是像v₁ = v₁′”不是靠安慰化解,而是(i) 指明确切无效步骤(跨越重新绑定使用传递性:没有单一语境同时持有两个守卫条件),(ii) 展示直觉确实正确的字符串(单封装尝试,其守卫条件真的矛盾)。把异议追到它所正确诊断的邻近病例,比仅仅回答异议更有价值。
第十一部分——第二次延续(7月25日):N₁₂的方括号就是7月22日的封装式;替换与代入
读者把本文件与书中29–30页对照,发现不足,因而触发:(i) 没有记录全部模式——N₁–N₁₁从未陈述,L₅/L₇/N₁₂有误(现已原位修正并标明);(ii) “讨论”段声称绕开代入——“事实上,甚至变量的自由与约束出现这些概念也被绕开”——如何做到?(iii) 读者自己的回忆,成为一切的关键:“7月22日我们有自己通过封装式实现代入的版本——这里有什么不同?”(iv) 对答案的精确异议:“双重守卫的字符串读起来仍像v₁ = v₁′——一个矛盾?”从零搭建的第一版解释失败(“你的阐明方式没怎么帮到我”);起效的版本在下文,围绕(iii)组织。7月22日各项(Φ_lit、Φ_wrap、三层、四项隐患、r、sub)都沿用原名。
N₁–N₁₁,按正式编号记录——就是第一部分的阶梯与配方,现与字符串对应:
N₁ : (v₁′ = v₂′ ⊃ v₁ = v₂) ——阶梯不同,后继不同
N₂ : ∼(0̄ = v₁′) ——0不是任何对象的后继
N₃ : (v₁ + 0̄) = v₁ ┐
N₄ : (v₁ + v₂′) = (v₁ + v₂)′ ┘ 加法配方
N₅ : (v₁ · 0̄) = 0̄ ┐
N₆ : (v₁ · v₂′) = ((v₁ · v₂) + v₁) ┘ 乘法 = 重复加法
N₇ : (v₁ ≤ 0̄ ≡ v₁ = 0̄) ┐
N₈ : (v₁ ≤ v₂′ ≡ (v₁ ≤ v₂ ∨ v₁ = v₂′)) │ 逐步刻画≤
N₉ : ((v₁ ≤ v₂) ∨ (v₂ ≤ v₁)) ┘ 任意两数可比较
N₁₀ : (v₁ E 0̄) = 0̄′ ┐
N₁₁ : (v₁ E v₂′) = ((v₁ E v₂) · v₁) ┘ E = 重复乘法
(除外层∀——由概括规则提供——及等式次序外,N₁、N₂就是第五部分的S2、S1。)
§1。方括号就是7月22日的方括号——封装式的真实前提条件。F[0̄] = ∀v₁(v₁ = 0̄ ⊃ F)原封不动就是Φ_wrap(F, 0)(7月22日,第四部分)。重新审视Φ_wrap(F, t) = ∀v₁(v₁ = t ⊃ F):它的前提条件从来不是“t是数码”,而是:t不含v₁——新添量词无从抓取。数码当然满足(完全不含变量),而第二章从未试探这一边界,因为对角化始终只填入具体编码。
§2。试探边界:填入v₁′,以及捕获。归纳的攀升位置必须在v₁′处求F的值——这个项包含v₁。把它送入单封装式,看看:
∀v₁(v₁ = v₁′ ⊃ F)
新的∀v₁抓住其辖域内每个v₁——包括项内部本该继续指向外部数的那个。(标准名称:捕获——本应保持自由的变量被新添量词抓住。)令F := ∃v₂(v₁ = v₂ + v₂),即“v₁是偶数”:字符串说“每个等于自身后继的数都是偶数”——守卫条件对一切为假,语句空真,内容被毁。
F[v₁′] := ∀vᵢ( vᵢ = v₁′ ⊃ ∀v₁( v₁ = vᵢ ⊃ F ) ) (vᵢ是F中不出现的任意变量)
新变量vᵢ满足前提——不含v₁的项,与数码所具有的性质相同。外层守卫位于内层∀v₁辖域之外,所以其中v₁仍指向外部:它把v₁′的值存到新名字下。内部字符串原样就是Φ_wrap(F, vᵢ)。所以双封装不是新技巧:以无害的新变量换掉危险项,再原样运行旧机器。新鲜性条件是同一种病在上一层的表现(若vᵢ在F中出现,外层∀vᵢ就会抓住那些出现)——而检查它只需符号扫描,不需辖域解析。
§4。语义解析——主张A,以及N₁₂ = 多米诺原则。(这也回头证成第五部分的解析“在M中的Ind_F恰好在说Instance(C_F)”,那里以代入记号陈述;下述链条为书中实际的方括号字符串确立它,所以第五至七部分的每次使用都成立。)
主张A:F[v₁′]在n处真 ⟺ F在n+1处真(“在k处真” = 把v₁读作k时真)。令v₁ := n求值:
- 内层∀v₁只在自己的辖域(v₁ = vᵢ ⊃ F)内重新绑定;项v₁′中的v₁在该辖域外,所以v₁′指称n+1。(R1;将守卫置于外部的全部理由。)
- 外层∀vᵢ:真 ⟺ 对每个m,实例(m = n+1 ⊃ ∀v₁(v₁ = m ⊃ F))真。(R2。)
- m ≠ n+1:前件假,实例真,无信息。(真值表。)
- m = n+1:实例真 ⟺ ∀v₁(v₁ = n+1 ⊃ F)真。(真值表。)储存的值已交接;vᵢ消失。
- 该字符串就是Φ_wrap(F, n+1):由R2与真值表,k ≠ n+1空泛通过,k = n+1说:F在n+1处真。(重新推出7月22日的等价。)∎
具体运行,F := 0̄ ≤ v₁,n = 4:v₁′指称5;仅vᵢ = 5幸存于步骤2–4;仅k = 5幸存于步骤5;判定“0 ≤ 5”。F仅在最后被查询一次,未被拆开——两层封装是运送n+1这个值的管道。主张B:F[0̄]真 ⟺ F在0处真。(步骤5以0替换n+1。)
组装N₁₂(一个语句——每个v₁最终都被约束):由主张B,块1 = “F在0成立”;由R2加上每个实例内部的主张A,块2 = “对每个n:F在n成立蕴涵F在n+1成立”——F可攀升;块3 = “F对每个数成立”。按真值表读取两个⊃:
(F在0成立)⊃((F可攀升)⊃(F处处成立))
——恰好一种情况为假:F在0成立、F可攀升,但F在某处失败。F所刻画集合的多米诺原则;在世界M中,恰好是Instance(C_F)。每个实例对ℕ真(阶梯无旁枝,也无不可达阶级),所以第一部分的约束(a)成立。∎
§5。传递性异议,以及区域。读者:“读起来还是像v₁ = v₁′——v₁ = vᵢ与vᵢ = v₁′串成矛盾。”用v₁ := 4的运行表来解决:
| 字符串区域 | v₁指称 | v₁′指称 | vᵢ指称 |
|---|---|---|---|
| 一切之外 | 4 | 5 | — |
| 仅在∀vᵢ内(守卫1在此) | 4 | 5 | 5 |
| 两个量词内(守卫2与F在此) | 重新绑定为每个k;重点在5 | 6——未使用;守卫1不在此 | 5 |
在各自被检查时,守卫1说5 = 5,守卫2也说5 = 5;令人不安的“4 = 5”没有被字符串任何部分断言。传递性连接的是在同一语境中成立的等式——两个守卫之间,∀v₁重新指派了字母,所以没有单一语境同时持有两者。(在内层区域重读守卫1,它甚至为假——5 = 6——但无碍:它位于外部,以v₁意为4时检查过;其工作,即把vᵢ钉在5,已经完成。vᵢ是指称保持不变的唯一字母:它就是管道。)而这一直觉确实正确诊断了单封装字符串(§2):那里v₁ = v₁′两边共享一个区域,守卫真正矛盾——修复恰是让传递链无法运行。
为什么还要复用字母v₁?因为透明的替代方案——重命名F的自由变量,写∀vᵢ(vᵢ = v₁′ ⊃ ∀w(w = vᵢ ⊃ F⟨w⟩))——要求把F内部每个自由v₁改成w:重命名就是代入,正是禁止的操作。F送来时,自由变量已不可变更地叫v₁,所以输送管道必须终止于对同一字母的量化;这个字母服务两个主人,单凭辖域消歧。检查形状的机器从不绊倒(哪个量词拥有哪个出现,由嵌套机械确定);只有人类阅读会绊倒,因为它希望一个字母只意味着一件事。
§6。为什么是v₁′而非数码——本质与偶然。读者问,这整套机制是否只是这一公理的偶然。分开判断:
填入含v₁的项是本质要求。攀升位置同时断言无限多个攀升步骤——(0,1)、(1,2)、(2,3)……——而数码方案,即无限列表F[0̄] ⊃ F[0̄′]、F[0̄′] ⊃ F[0̄′′]……,败在证明定义本身:(1) 证明是公式的有限序列;(2) 所以任一证明只使用有限多个攀升语句;(3) 所以它只能到某个n的F[n̄],无法更远;(4) ∀v₁F(v₁)——归纳所要提供的东西——将永远不可证,尽管每个实例都可证。一个在绑定符下于v₁′处求F值的有限量化语句,是唯一行得通的形状。第四组是十九模式中唯一填入位置——唯一由任意公式参数化的模式。(第三组不断提及v₂′——N₄——但那些是在组成固定原子等式时直接写入的真正项,不是填进已有公式的东西。)
输送装置才是选择。哥德尔用字面代入F(v₁′)陈述相同内容,以sub阶梯为代价;斯穆里安的守卫是另一实现——对他而言,坚持拒绝构造sub迫使如此。
§7。替换与代入——逐项走过7月22日的隐患表。两个字符串操作(7月22日三层中的第一层):
- 代入(Φ_lit):打开F;找出v₁的出现;判断哪些是自由的(解析括号辖域);替换它们中的每一个;重新组装。四项隐患;sub约31级的阶梯。
- 替换(L₇的概念):在原子公式中,一次切开,一次拼接:X₁vᵢX₂ ↦ X₁tX₂。
隐患逐一消失:找全所有出现——不必(一个出现,任取一个);哪些自由——不必(原子 = 内部无∀ = 无约束,无须解析);捕获——不可能(字符串中没有量词来抓取);编码函数——一次连接,a ∗ b ∗ d ↦ a ∗ c ∗ d,属于推论1范围。口号:代入必须解析;替换只需切开。
而系统没有实例化公理∀v₁F ⊃ F(t)——通常“以t代入自由v₁”及其避免捕获的附加条件所在之处。其工作由L₆(项有一个值:∃vᵢ(vᵢ = t))与L₇逐个出现地沿vᵢ = t传递原子事实来完成——实例化成为待推导的定理,而非待陈述的公理(此处仅断言,未推导——债8)。至此,“讨论”段完全兑现:“避免对自由出现的代入” = 无实例化公理 + N₁₂中的方括号;“绕开自由与约束” = 每个附加条件(L₅、L₆、第四组新鲜性)都是“是否曾出现”的扫描;“更简单的替换概念” = L₇在原子公式中的单切。L₆自身附加条件又是同一种抓取病:没有“vᵢ不在t中”,∃v₁(v₁ = v₁′)——“某数是自身的后继”——就会成为公理,却是假的。
§8。谁是受益者——相同的节省,两次出现。7月22日三层:字符串操作 → 编码函数 → 命名公式;全部成本在第三层。第二章中,需要命名编码函数的操作是对角化:封装式换来r(x, y) = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3——x未拆封地乘载,第三层一行——从未构造sub。第三章中,需要第三层公式的是“x是某公理的编码”——“x是y的证明”的第一项原料,这正是§2全部负担。在方括号定义下,归纳公理的编码是固定块 ∗ F的编码 ∗ 固定块——F在每个位置都是未拆封块;出现扫描是子串条件;L₇替换是上面的连接陈述。若模式以字面代入陈述,公理识别器就需要sub为算术的——那架阶梯。同样的拒绝,新的受益者:封装式在第二章保护对角线的地址,在第三章保护公理检查器。全书任何地方都未构造sub。
记录补充(7月25日)。
| 提出的困惑 | 一行解答 |
|---|---|
| “这不就是我们7月22日的封装式?” | 是——F[0̄]原样就是Φ_wrap(F, 0)。新的只有填入项:v₁′含v₁,违反封装式真实前提(填入项不含v₁——“数码”从来不是条件);修复 = 外层守卫以新变量换掉v₁′,内层封装不变。 |
| “替换与代入有何区别?” | 代入:解析F,找自由出现,全替换——四项隐患,sub阶梯。替换:原子公式中单次切开拼接——无约束,捕获不可能,编码函数仅一次连接。解析与切开之别。 |
| “v₁ = vᵢ且vᵢ = v₁′——所以v₁ = v₁′,矛盾?” | 内层∀v₁在守卫之间重新指派v₁(示例中4 → 5);每个守卫被检查时都说5 = 5;没有单一语境同时持有两者,所以不能启动传递性。这一直觉正确诊断的是单封装字符串,其守卫确实矛盾。 |
| “为什么还要复用字母v₁?” | 重命名F自由变量 = 打开F = 代入。管道必须结束于对F所用确切字母的∀;辖域机械消歧。 |
| “双封装是偶然安排吗?” | 分开看:填入含v₁的项是本质要求(有限证明——数码攀升列表可得每个实例,永远得不到∀v₁F);守卫与内部操作两种输送方式才是设计选择(哥德尔改付阶梯代价)。 |
| “究竟怎样绕开自由/约束?” | 没有实例化公理需要陈述;每个附加条件只是出现扫描;唯一替换位置是原子公式,其中无约束。 |
自测补充(16–21)。先答再看;续接第九部分。
- 陈述封装式真实前提条件,并在F := ∃v₂(v₁ = v₂ + v₂)上展示单封装的捕获失败。
- 重现主张A的五步解析。“vᵢ不在F中出现”究竟在哪里被使用?
- 令v₁ := 4,给出F[v₁′]三个区域,以及各区v₁、v₁′、vᵢ所指。哪个字母不变,这一不变表达什么?
- 归纳为什么不能用数码攀升?从证明定义出发,分四步。
- 对照四项隐患表逐项检验替换,并说明为何单凭原子性就消灭捕获。
- 系统没有哪条公理,哪一对公理做它的工作,L₆附加条件排除哪句假话?
答案
- 填入项t必须不含v₁——新添∀v₁无物可抓;数码空泛地满足。∀v₁(v₁ = v₁′ ⊃ ∃v₂(v₁ = v₂ + v₂))说“每个等于自身后继的数都是偶数”——守卫处处假,语句空真,内容消失。
- §4。在步骤5“F在n+1处真”使用:把F的真读作只依赖v₁,预设F没有vᵢ出现——否则外层∀vᵢ早已将这些出现重新绑定到n+1,在查询F之前就污染它。
- 外部:v₁ → 4,v₁′ → 5,vᵢ未定义。仅在∀vᵢ内:4、5、5。两者内:v₁重新绑定(重点在5),v₁′ → 6(未使用——守卫1在外部),vᵢ → 5。不变者:vᵢ,始终5——储存的值;把5从v₁意为4的区域送进v₁已重新绑定区域的管道。
- 证明是有限序列 → 任意证明仅用有限多个F[0̄] ⊃ F[0̄′]、F[0̄′] ⊃ F[0̄′′]…… → 到达某n的F[n̄],无法更远 → ∀v₁F(v₁)永远不可证,尽管每个实例可证。攀升子句必须是一个量化语句,因而F在绑定符下于v₁′处求值。
- 一个出现(不迭代);原子 = 无∀ = 无须识别约束出现;内部无量词 = 无物抓取拼入的t;编码函数a ∗ b ∗ d ↦ a ∗ c ∗ d。原子性消灭捕获,因为捕获就是量词的抓取,而原子公式不含量词。
- 缺失:实例化,∀v₁F ⊃ F(t)。其工作:L₆(∃vᵢ(vᵢ = t)——项有值)+ L₇(沿vᵢ = t的单出现传递),成为推导而非公理(债8)。L₆条件“vᵢ不在t中”排除∃v₁(v₁ = v₁′)——“某数是自身的后继”,假。
本次复习结束 · 斯穆里安《哥德尔不完备定理》,第三章§1已在概念上整合(含第七部分重建与7月25日延续,即第十一部分);形式工作待办 · 先前文件:Godel-Incompleteness-Session-2026-07-15.md(第一章框架与机器谜题)、Godel-Incompleteness-Session-2026-07-17-Answer-Sheet.md(第一章练习1–7)、Godel-Incompleteness-Session-2026-07-19.md(第二章§1–§2)、Godel-Incompleteness-Session-2026-07-20.md(第二章§3,练习2–5)、Godel-Incompleteness-Session-2026-07-21.md(第二章§4–§5)、Godel-Incompleteness-Session-2026-07-22.md(第二章§6,定理1与塔斯基)、Godel-Incompleteness-Session-2026-07-23.md(第二章练习6–8,完成)· 下一步:第三章正式内容——L₃检验、祖先解释、自测9,然后§2算术化。