Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter IV: Arithmetic Without the Exponential (Theorem E, and Exercise 1)
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 / 篇目
- The punchline of the chapter
- How to use this document
- Part 0 — The format war (method result)
- Part I — Why "without the exponential" is worth a chapter
- Part II — The obstruction: recursion is not definability
- Part III — The circularity scare, and the divisor trick
- Part IV — Delimiters: from ♯ to frames
- Part V — Theorem E: the chain (final format)
- Part VI — Exercise 1: P.A. +
- Part VII — What was actually new today
- Part VIII — Distinctions Ledger (confusions of the day → one-line resolutions)
- Part IX — Self-Test
- Part X — Position, owed items, debts
Study session of July 27, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter IV, book pp. 40–50 (§1 The Incompleteness of P.A., §2 Σ₀/Σ₁/Σ, §3 Concatenation to a Prime Base, §4 The Finite Set Lemma, §5 Proof of Theorem E, §6 sighted) · Companion to the sessions of July 15, 17, 19–24 (with 25 continuations), and 26 · Character: a strategy session that turned into a formalization session. The reader asked why the chapter exists at all, then for the central strategy of the proof of Theorem E, then — through four successive format rejections — forced the chain into a shape now judged the best of the sequence: GOAL + citable glossary + hallmark steps, each step opening with the load it bears, every formula parsed block-by-block into its semantic content, every justification citing labeled grounds. Part V prints that chain in full; Part 0 records the format war, which is itself a result.
The punchline of the chapter
{+, ·} is the exact threshold of incompleteness. Chapter III proved P.E. incomplete, but its Gödel sentence contains the symbol E — the proof says nothing about the weaker system P.A. (P.E. minus E, minus the two E-axioms N₁₀–N₁₁). And the question is genuinely open on both sides, because below the threshold completeness actually happens: arithmetic with + alone (Presburger) and with · alone (Skolem) are each complete and decidable. So "drop E" is not a formality — it is the last step down before incompleteness disappears. Theorem E closes the question from above: x^y = z is Σ₁ — definable from + and · alone — so everything Chapter III built out of E can be rebuilt inside P.A., and P.A. is incomplete (§6). The deeper moral: E was never a source of expressive power, only a convenience; the true source is that + and · together can code finite sequences, and that is where the whole recursion tower (succession → addition → multiplication → exponentiation → …) collapses into definability.
How to use this document
Parts I–IV rebuild, in the order the session built it, why the proof has the shape it has — threshold, obstruction, circularity scare, delimiter problem. Part V is the deliverable: the complete proof of Theorem E as a justified chain in the final format. Part VI is Exercise 1, graded and then done properly. The Ledger (Part VIII) is the refresher; the Self-Test (Part IX) tells you whether it took. One standing flag: Part V's coding deviates from the book's (digit-2 guards instead of pure 1-frames) — the deviation is announced where it starts (S8) and cashed where it pays (S9, S12–S15); the interface to the rest of the proof is identical to the book's Lemma K. The book-check it generates is registered in Part X.
Part 0 — The format war (method result)
Four versions of the same proof were rejected before one stuck; each rejection isolated a rule. The failures, in order:
- Metaphor terms doing load-bearing work — "smearing," "junk-tolerance," "recognized never computed," "the single cut severing E." The reader: "you are to explain things, not to explain terms by other unexplained terms." July 24's third failure mode (metaphor stacking), relapsed and re-caught. Every such phrase either got a definition and a label, or got expanded into the steps it was compressing and deleted.
- A background-facts block (B1–B3) stating positional notation, primes, recursion equations as numbered assumptions. Rejected as clutter: facts of that grade are used inline with a one-line reason at the point of use, not enthroned up front. Only load-bearing, citable items deserve labels.
- Goal-free rigor. The clean version dropped the GOAL/obligations scaffolding, and was rejected for exactly that: rigor without a stated destination is unreadable in a different way.
- Function stated late. Hallmark propositions must open with what load they bear — what the step is for, cited forward — before the formula, not as an afterthought.
The settled shape (the reader: "far superior to earlier shapes and much more intelligible"):
- GOAL first: the theorem, a target shape (what "done" looks like, as checkable conditions T1, T2, …), and a decomposition into obligations G1, G2, … with each chain step tagged by the obligation it serves.
- Glossary of citable definitions before any argument (July 24's tool, kept).
- Hallmark steps S1, S2, … — each opens with its load, then the formula, then a block-by-block parse table: every syntactic chunk of the string on the left, what it says semantically on the right, with the grounds cited. Then the claim and proof, every justification naming earlier labels.
- Arithmetic parsed as strings: expressions like m·w + n, 12·m + 1, 2∗f∗f∗2 are read off at the digit level (what string does this arithmetic build?), since in this chapter numbers are their base-13 strings.
Part I — Why "without the exponential" is worth a chapter
Incompleteness does not transfer downward. A weaker language proves less — but it also says less, so there is less to fail to prove. Chapter III's undecidable sentence H[h̄] is a sentence of L_E; it is not even a sentence of P.A.'s language L_A. To show P.A. incomplete you need a Gödel sentence written without E, which means redoing the arithmetization — the seventeen conditions of July 26 — using + and · only.
The threshold facts that make it interesting (stated by the book's opening, proofs elsewhere): arithmetic with + but not · is complete and decidable (Presburger, 1929); with · but not + likewise (Skolem). So each of +, · alone is too weak to be incomplete. The pair {+, ·} is where the phenomenon switches on — and Theorem E is the proof that it switches on there, with nothing further needed.
Why E was in P.E. at all, and why it can go. E entered as a primitive because Chapter III's coding leaned on it (Num(x) was one Pow₁₃; concatenation's definition used 13^ℓ(y)). It leaves because it is derivable: Theorem E shows the relation x^y = z is Σ₁ in +, · — so E was redundancy, not power. The exclusion is a theorem, not a taste.
Part II — The obstruction: recursion is not definability
The reader's challenge: the tower is uniform — addition is iterated succession, multiplication is iterated addition, exponentiation is iterated multiplication — so why would the language stop at ·? Where does uniformity break?
Answer: "iterate y times" is not a first-order sentence. The recursion equations
x + 0 = x x + (y+1) = (x + y) + 1
x · 0 = 0 x · (y+1) = x·y + x
x ^ 0 = 1 x ^ (y+1) = x^y · x
each define the next floor by an induction whose length is the variable y. A formula of L_A is one fixed finite string; it cannot contain y nested copies of anything. So having + and · as primitives does not automatically yield a formula for x^y = z — the uniformity of the equations lives in the metatheory, not in the language. What Gödel found (and §§3–5 reconstruct with Quine's method) is that + and · suffice to code a finite sequence and check it locally — "there exists a record of the computation, every line of which is correct" — and once sequences are codable, every floor of the tower (and far more) becomes definable at once. That is why the tower of primitives can stop at ·: not because iteration stops mattering, but because two floors are enough to express "finite record," and finite records simulate all iteration.
The vocabulary for "how definable" (D1–D2 of the chain): Σ₀ = bounded quantifiers over +, · only, so truth of a Σ₀ sentence is a terminating finite check; Σ₁ = one unbounded ∃ in front of a Σ₀ formula — "there exists a witness, checkable in bounded time." Theorem E lands x^y = z exactly there.
Part III — The circularity scare, and the divisor trick
The scare. The plan needs record-coding; record-coding needs concatenation; but July 21's concatenation was x ∗ y = x·13^ℓ(y) + y — there is an exponential in it. Are we defining E from E?
The resolution: recognize, don't compute. The formula never needs the graded relation 13^ℓ = w (exponent as a variable). It needs only (a) the set of powers of 13 — recognizable by a divisibility test — and (b) "the least power of 13 exceeding y" — pinned by order tests among numbers ≤ z. Both are Σ₀. The divisibility test is the chapter's one appeal to primality:
w is a power of 13 ⟺ every divisor of w other than 1 is divisible by 13
— true because 13 is prime (a divisor of 13^k has only 13's in its factorization), and false in base 10: 4 divides 100 and 10 does not divide 4. This is why the base must be prime and why Chapter III's base 13 was a lucky necessity, now earned.
The graded/ungraded distinction (the session's recurring cliff). "z belongs to the set of powers of p" (ungraded) has the divisor characterization above — one Σ₀ line. "p^y = z" with y a free variable (graded) has no such static characterization: the exponent counts iterations, and counting iterations is the very thing formulas cannot do (Part II). The whole architecture of the chapter is arranged so that only the ungraded fact is ever needed inside formulas; the graded relation x^y = z is delivered at the very end, by the certificate method, as the theorem itself. The same cliff explains two dead ends below: numeral-coding (Part IV) and the naive "z is a power of x" idea — both secretly demand the graded relation.
Part IV — Delimiters: from ♯ to frames
Chapter III's separator and why it dies here. July 26's sequence numbers were δx₁δx₂δ…δxₙδ — workable because the payload was K₁₁, the δ-free numbers, which covered all Gödel numbers of meaningful expressions. δ was a reserved symbol: banned from members, so walls were unmistakable. But §4's Finite Set Lemma must code sequences of pairs of arbitrary natural numbers — that is the meaning of the book's "any natural numbers whatsoever" — and arbitrary numbers use all thirteen digits. No digit can be reserved; any candidate wall-string might occur inside a member.
The numeral dead end (the reader's proposal, killed by the cliff). Why not code entries as numerals, which use only two symbols, freeing eleven digits for walls? Because the numeral of a is the string 0…0 (a accents), whose Gödel number is g·13^a-shaped: decoding a numeral-code back to a is the graded exponential relation — the thing being defined. Entries must be stored verbatim (positional notation, zero decoding cost), and verbatim entries use every digit.
Quine's repair: reservedness by length, not by symbol. A frame is a number whose string is all 1's (D6). Frames of a fixed length j can occur inside members — that cannot be banned — but it can be out-lengthed: choose the separator scale longer than any 1-run inside any member, and add a maximality clause to the detecting formula ("no frame in the whole code exceeds the separator scale") so that a detected separator is guaranteed genuine. Reservedness becomes a property enforced per-code by an inequality, not globally by an alphabet. (Kripke's alternative, the book's Remark: enlarge the base per table so every entry is a single digit — reservedness by base-choice instead. Not pursued.)
This session's variant (deviation, flagged). The chain below guards each frame with the digit 2 on both ends (separators 2 1…1 2), which confines 1-runs by construction and makes the census argument (S9) one line; the book's pure-1 frames must handle entry-boundary run-merging inside the maximal-frame analysis instead. Interface identical; book-check registered in Part X.
Part V — Theorem E: the chain (final format)
GOAL
Theorem E. The relation x^y = z is Σ₁.
Target shape: exhibit ∃w[M(x,y,z,w)] with
- T1. M Σ₀ — bounded quantifiers over +, · only;
- T2. x^y = z ⟺ ∃w M, both directions proved;
- T3. no E anywhere in the construction.
Obligations: G1 (the tool: Σ₀-detectable coding of finite sets of pairs, entries bounded by their code) — S1–S16. G2 (the reformulation: x^y = z as existence of a certificate) — S17. G3 (the assembly) — S18–S19.
Glossary (citable, before any argument)
- D1. Σ₀-formula: built from +, ·, =, ≤, connectives, and bounded quantifiers (∀v ≤ t), (∃v ≤ t) only.
- D2. Σ₁-relation: expressible as ∃w F, F Σ₀.
- D3. x div y ⟺ (∃v ≤ y)(x·v = y).
- D4. Standing identification: each positive number is its base-13 digit string (unique, leading digit ≠ 0); ℓ(n) = its length. Two digit facts used throughout: multiplying by 13 appends a 0; the strings of length ℓ are exactly the numbers in [13^(ℓ−1), 13^ℓ).
- D5. x P y: x's string occurs as a consecutive block inside y's string.
- D6. Frame: a number whose string is all 1's; 1ⱼ = the frame of j ones. So ℓ(1ⱼ) = j and 1ⱼ ≤ 1ₖ ⟺ j ≤ k.
- D7. Maximal frame of y: a frame that is part of y and not part of any longer frame that is part of y.
- D8. Certificate for (x,y,z): a finite set S of pairs with (α) (y,z) ∈ S; (β) every (a,b) ∈ S is (0,1) or equals (c+1, d·x) for some (c,d) ∈ S.
- D9. m ∗ n (m, n ≥ 1): the number whose string is m's string followed by n's string.
The chain
S1 — the string Pw and its parse. Define
Pw(w) := w ≥ 1 ∧ (∀v ≤ w)[ (v div w ∧ v ≠ 1) → 13 div v ]
| block | says |
|---|---|
| w ≥ 1 | w has a string (D4) |
| (∀v ≤ w)[…] | every v up to w passes the bracketed test — bounded, so a finite check (D1) |
| v div w ∧ v ≠ 1 | v is a divisor of w other than 1 (D3) |
| 13 div v | v is a multiple of 13 — as a string: v ends in the digit 0 (D4: appending 0 = multiplying by 13) |
Whole string says: every divisor of w except 1 ends in the digit 0.
S2. Pw(w) is true ⟺ w ∈ {1, 13, 13², …}. (⟸: 13 is prime, so a divisor of 13^k has only 13 in its factorization — every divisor ≠ 1 is a multiple of 13; w = 1 passes vacuously. ⟹, contraposed: w not a power of 13 gives w = 13^k·m, 13 ∤ m, m > 1; then v := m is a divisor ≠ 1 not ending in 0. The only step in the chain that uses primality; base 10 fails it: 4 div 100, 10 ∤ 4.)
S3. For m, n ≥ 1: m ∗ n = m·u + n, where u is the least power of 13 exceeding n. (D4, D9. Parse of the arithmetic: u = 13^ℓ(n) — by D4's second fact, that is exactly the least power above n; m·u = m's string followed by ℓ(n) zeros — D4's first fact, ℓ(n) times; + n writes n's ℓ(n) digits into those zero positions, no carrying. Result: m's string then n's string, i.e. m ∗ n. Base-10 picture of the mechanism: 95·100 + 25 = 9525.)
S4 — the string Con and its parse. Define
Con(m,n,z) := (∃w ≤ z)[ Pw(w) ∧ n < w ∧ (∀v < w)(Pw(v) → v ≤ n) ∧ z = m·w + n ]
| block | says |
|---|---|
| (∃w ≤ z) | some number up to z… (bound sound: if z = m·w + n, m ≥ 1, then w ≤ z — the true witness is inside the search range) |
| Pw(w) | …which is a power of 13 (S2) |
| n < w | …exceeding n |
| (∀v < w)(Pw(v) → v ≤ n) | …while every smaller power of 13 does not exceed n. With the previous block: w is the least power of 13 exceeding n — pinned by order tests alone, no exponent variable (S2) |
| z = m·w + n | z is m's string followed by n's string (S3, since w is now the u of S3) |
Claim: for m, n ≥ 1: Con(m,n,z) ⟺ m ∗ n = z. (⟸: w := 13^ℓ(n) verifies every block, by S2 and S3. ⟹: powers of 13 are totally ordered, so blocks 2–4 force w = 13^ℓ(n); block 5 and S3 finish. From here on, ∗ inside any formula abbreviates Con.)
S5 — the string Blk and its parse. Define
Blk(m,n) := m = n ∨ (∃u ≤ n)Con(u,m,n) ∨ (∃v ≤ n)Con(m,v,n)
∨ (∃u ≤ n)(∃q ≤ n)(∃v ≤ n)(Con(u,m,q) ∧ Con(q,v,n))
| block | says |
|---|---|
| m = n | m's string is the whole of n's string |
| (∃u ≤ n)Con(u,m,n) | n = u ∗ m: m sits at the right end (S4) |
| (∃v ≤ n)Con(m,v,n) | n = m ∗ v: m sits at the left end |
| (∃u…)(∃q…)(∃v…)(Con(u,m,q) ∧ Con(q,v,n)) | n = (u ∗ m) ∗ v: m sits in the interior; q names the intermediate value u ∗ m |
Claim (a): for m, n ≥ 1, Blk(m,n) ⟺ m P n. (The four blocks enumerate the four possible positions of a consecutive occurrence — D5.) Claim (b): Blk(m,n) → m ≤ n, and each existential witness is ≤ n, so the displayed bounds lose nothing. (S3's identity: u ∗ m = u·w + m ≥ m and m ∗ v = m·w′ + v ≥ m; compose for the interior case. This inequality funds every bounded quantifier below.)
S6 — frame facts. 1ⱼ ∗ 1ₖ = 1_{j+k} (D9: write j ones, then k ones); and Blk(1ⱼ, n) ⟺ some maximal frame of n has length ≥ j. (⟸: j consecutive positions inside that frame are an occurrence of 1ⱼ — S5(a). ⟹: any occurrence of j consecutive 1-digits extends to a maximal frame of length ≥ j — D7. This is the two-way bridge between the number 1ⱼ and the string fact "j consecutive ones.")
S7 — the string OB and its parse. Define OB(m) := m ≥ 1 ∧ Pw(12·m + 1).
Parse of the arithmetic, with c = the digit twelve: if m = 1ⱼ, then 12·m is the string of j c's (each digit 1 becomes 12; no carrying, since 12 < 13), and adding 1 carries through every position: c c…c + 1 = 1 0 0…0 (j zeros) = 13^j. Concretely, j = 3: 12·(1 1 1) = (c c c); (c c c) + 1 = (1 0 0 0).
Claim: OB(m) ⟺ m is a frame. (⟸: computation above + S2. ⟹: 12m + 1 = 13^j, m ≥ 1 forces m = (13^j − 1)/12 = 13^(j−1) + … + 13 + 1 = 1ⱼ.)
S8 — the code layout. Given nonempty Q = {(a₁,b₁), …, (aₙ,bₙ)}: entries may be 0 and 0 has no string (D4), so store a+1, b+1. Let m := 1 + max{ℓ(aᵢ+1), ℓ(bᵢ+1)} — strictly longer than every stored string — and set
s := 2 ∗ 1ₘ ∗ 2 t := 2 ∗ 1₂ₘ ∗ 2
w := t ∗ (a₁+1) ∗ s ∗ (b₁+1) ∗ t ∗ … ∗ t ∗ (aₙ+1) ∗ s ∗ (bₙ+1) ∗ t
String picture of one cell of w:
2 [2m ones] 2 [aᵢ+1] 2 [m ones] 2 [bᵢ+1] 2 [2m ones] 2
(Deviation from the book starts here: the book's s, t are pure frames 1ₘ, 1₂ₘ; the digit-2 endpoints are this session's addition.)
S9 — census of the maximal frames of w. Every maximal frame of w lies wholly inside one entry-string, one s, or one t, with length respectively < m, exactly m, exactly 2m. (A frame occupies consecutive 1-digits, so it cannot cross any position carrying another digit [D6, D7]; by S8 every s and t begins and ends with the digit 2, so separator-ones cannot join entry-ones and conversely. Lengths read off S8. This confinement is the digit 2's entire job.)
S10 — the string K and its parse. Define
K(a,w,b) := (∃f ≤ w)[ OB(f) ∧ ¬Blk(f, a+1) ∧ ¬Blk(f, b+1)
∧ Blk(2∗f∗f∗2 ∗ (a+1) ∗ 2∗f∗2 ∗ (b+1) ∗ 2∗f∗f∗2, w)
∧ (∀h ≤ w)(OB(h) ∧ Blk(h,w) → h ≤ f∗f) ]
| block | says |
|---|---|
| (∃f ≤ w) | some number up to w… (bound sound: the intended f occurs inside w, hence ≤ w by S5(b)) |
| OB(f) | …a frame — call its length k (S7) |
| ¬Blk(f, a+1) | a+1's string nowhere contains k consecutive ones (S6) |
| ¬Blk(f, b+1) | likewise b+1 |
| 2∗f∗f∗2 | the string: 2, then 2k ones, then 2 — a t-shape at scale k (S6: f∗f = 1₂ₖ) |
| 2∗f∗2 | the string: 2, then k ones, then 2 — an s-shape at scale k |
| Blk(2∗f∗f∗2 ∗ (a+1) ∗ 2∗f∗2 ∗ (b+1) ∗ 2∗f∗f∗2, w) | one full cell at scale k, with a+1 and b+1 in the entry slots, occurs somewhere in w (S5(a), S8's picture) |
| (∀h ≤ w)(OB(h) ∧ Blk(h,w) → h ≤ f∗f) | every frame occurring in w is ≤ 1₂ₖ — i.e. no maximal frame of w is longer than 2k (S6, S7, D6) |
(Every ∗ expands through Con [S4]; each intermediate concatenation is itself part of w, hence ≤ w by S5(b) — the internal bounds are sound. So K is Σ₀.)
S11 — every stored pair is detected: (a,b) ∈ Q ⇒ K(a,w,b). Witness f := 1ₘ, so k = m. Block 2: S7. Blocks 3–4: an m-frame inside an entry would contradict S9's length census (< m), via S6. Block 5-group: the cell of the pair (a,b) in S8's layout is literally the required string at scale m. Block 6: every frame in w has length ≤ 2m (S9), hence is ≤ 1₂ₘ = f∗f (S6, D6).
S12 — (only-stored, step 1) any witness f has length m. (Block 5 puts 2k consecutive ones into w, so some maximal frame of w has length ≥ 2k [S6]; census caps it: 2k ≤ 2m [S9]. Conversely 1₂ₘ occurs inside any t of w [S8], so block 6 at h := 1₂ₘ gives 1₂ₘ ≤ 1₂ₖ, i.e. 2m ≤ 2k [D6]. So k = m, f = 1ₘ.)
S13 — (step 2) every occurrence in w of "2, 2m ones, 2" sits exactly at a t. (Its 2m ones lie inside a single maximal frame of length ≥ 2m; by S9 only t-interiors qualify, and those hold exactly 2m ones — so the occurrence's ones fill a t-interior exactly and its flanking 2's are that t's own 2's.)
S14 — (step 3) the cell-occurrence's two t-shaped ends sit at two consecutive t's of w. (They sit at t's by S12+S13. If not consecutive, an entire further t lies strictly inside the middle "(a+1) 2 [m ones] 2 (b+1)"; its 2m ones fit neither in the s-shape [only m ones] nor in a+1 or b+1 — for then that entry contains m consecutive ones, making f = 1ₘ part of it [S6], contradicting blocks 3–4.)
S15 — (step 4) the middle matches one stored pair; hence (a,b) ∈ Q. (Between two consecutive t's, w reads exactly (aᵢ+1) 2 [m ones] 2 (bᵢ+1) [S8]; block 5 says the same stretch reads (a+1) 2 [m ones] 2 (b+1). Locate the occurrence's "2 [m ones] 2": its m ones need a maximal frame of length ≥ m in the stretch; entry-frames are < m [S9], so only s's interior qualifies — length exactly m — forcing coincidence of the ones and of the flanking 2's with s. Left of this shared landmark, the same digit segment is both a+1 and aᵢ+1 — same string, same number [D4]; right likewise. So (a,b) = (aᵢ,bᵢ). S11–S15 together: K(a,w,b) ⟺ (a,b) ∈ Q — G1(i) ✓.)*
S16 — entries bounded by the code: K(a,w,b) → a ≤ w ∧ b ≤ w. (Block 5: a+1 is part of the cell, which is part of w; S5(b) twice gives a+1 ≤ w, so a ≤ w; likewise b. — G1(ii) ✓. Load: this is what will make a bounded sweep (∀a ≤ w)(∀b ≤ w) exhaustive over the coded set.)
S17 — the reformulation: x^y = z ⟺ a certificate for (x,y,z) exists. (⟹: S := {(i, x^i) : i ≤ y} satisfies (α) at i = y and (β) via (0, x⁰) = (0,1) and (i+1, x^(i+1)) = (i+1, x^i·x) [D8]. ⟸: induction on a — every (a,b) ∈ S has b = x^a: at a = 0, (β)'s second alternative is impossible, forcing (0,1) = (0, x⁰); at a > 0, (β) yields (a,b) = (c+1, d·x) with (c,d) ∈ S, so c = a−1, d = x^(a−1) by induction hypothesis, b = x^a. Extra pairs beyond the honest list are thereby forced correct too — why (β) needn't mention order or completeness. Then (α) gives z = x^y. The induction is performed by us, once, about all certificates; no formula performs it. — G2 ✓.)
S18 — the string M and its parse. Define
M := K(y,w,z) ∧ (∀a ≤ w)(∀b ≤ w)[ K(a,w,b) →
(a=0 ∧ b=1) ∨ (∃c ≤ w)(∃d ≤ w)(K(c,w,d) ∧ a = c+1 ∧ b = d·x) ]
Throughout, read "the coded set" as S_w := {(a,b) : K(a,w,b)}.
| block | says |
|---|---|
| K(y,w,z) | (y,z) ∈ S_w — clause (α) of D8 for the coded set |
| (∀a ≤ w)(∀b ≤ w)[K(a,w,b) → …] | "every pair of S_w satisfies …". The bounded sweep is entitled to this reading only because of S16: no member of S_w lies beyond w, so nothing escapes the bounds |
| a = 0 ∧ b = 1 | the pair is the seed (0,1) — (β)'s first alternative |
| (∃c ≤ w)(∃d ≤ w)(K(c,w,d) ∧ …) | S_w contains some pair (c,d)… (bounds sound by S16 again: any member pair sits below w) |
| a = c+1 ∧ b = d·x | …of which (a,b) is the one-step successor: first coordinate up by 1, second multiplied by x — (β)'s second alternative |
Whole string of M says: S_w is a certificate for (x,y,z) (D8).
S19 — Theorem E. x^y = z ⟺ ∃w M; and ∃w M is Σ₁.
(⟹: from x^y = z get a certificate S [S17 ⟹]; code it as w [S8, S11–S15: S_w = S exactly]. Then (α) holds as K(y,w,z), and for each member, (β)'s alternatives transfer: the predecessor (c,d) ∈ S is detected [S11] and reachable by the bounded ∃'s [S16]. ⟸: given w with M true, S18's parse says S_w is a certificate for (x,y,z); S_w is finite [S16: ≤ (w+1)² candidates] and nonempty [(y,z) ∈ S_w]; apply S17 ⟸: z = x^y.
Shape check. T1: K is Σ₀ [S10]; M adds only bounded quantifiers, =, +, · — Σ₀ by D1. T2: both directions above. T3: expand every abbreviation, M → K → OB, Blk → Con → Pw → div — surviving vocabulary: +, ·, =, ≤, the constant 13, connectives, bounded quantifiers; no E. ∃w M is Σ₁ by D2. — G3 ✓, GOAL met. ∎)
Part VI — Exercise 1: P.A. +
The exercise (p. 50). G = H[h̄], true but not provable in P.A. (H(v₁) expresses P̃*). Add G as an axiom; P.A. + {G} is still correct, since G is true. Is it complete?
The reader's answer, graded. Verdict "no, incomplete" — correct. "G is now an axiom, so this is just a patch" — the right frame: the proof was never about one missing axiom. "The formal logic will eventually produce the same consequence all over again" — two repairs: (1) not the same consequence: G itself is now provable in one line (it is an axiom), so G is no longer a witness; what reappears is a new sentence G′, built by the same construction from the new system's provability set. (2) nothing "eventually," and the re-run is not free: the incompleteness argument is a template with two input conditions, and re-applying it requires checking both for the enlarged system — one is handed over by the exercise, the other is the entire mathematical content of the solution.
The chain.
E1 (the theorem as a template). The Ch. III/IV argument takes any system S with (i) S correct, (ii) P̃*_S expressible by some H_S(v₁) — where P*_S := {n : the diagonalization of E_n is provable in S} — and outputs: G_S := H_S[h̄_S] is true but not provable in S. (The owned proof, reread as a function of S: nowhere did it use anything about P.A. beyond (i) and (ii).)
E2 (condition (i)). P.A. + {G} is correct — given (G true, P.A. correct, consequences of truths true).
E3 (condition (ii) — the load-bearing check). The arithmetized provability machinery of P.A. + {G} differs from P.A.'s in exactly one clause: where the axiom-check formula was A(v₁), it becomes A(v₁) ∨ v₁ = ḡ, with g the Gödel number of G — one disjunct, one numeral. Formation sequences, inference steps, proofs, diagonalization: untouched. So P̃*_{P.A.+{G}} is expressible, by some H′. (The step the one-sentence answer skipped; the only thing to verify rather than quote.)
E4 (re-application). E1 at S := P.A. + {G}, inputs E2, E3: G′ := H′[h̄′] is true, not provable in P.A. + {G}. Incomplete. ∎
E5 (G′ ≠ G). G is provable in the new system; G′ is not. Also literally distinct strings: H′ carries the extra disjunct, so h′ ≠ h.
E6 (the boundary the intuition needs). Iterating — P.A. + {G, G′, G″, …} — never closes the gap while E3-style expressibility survives. The extreme patch, adding all true sentences, gives a correct and complete system with no contradiction: condition (ii) is exactly what fails for it (were P̃* expressible there, the diagonal argument would manufacture a true-but-not-true sentence). So the honest slogan: no patch works while the axiom set remains arithmetically expressible — the qualifier is where the theorem lives, and it separates "add one sentence" (E3 goes through) from "add everything" (E3 breaks).
Part VII — What was actually new today
Strip the chapter to its ideas and it bought four:
- A prime base gives a purely multiplicative handle on powers — "every divisor ≠ 1 is divisible by p" recognizes {p⁰, p¹, p², …} in one Σ₀ line (S1–S2), and "least power exceeding n" is then pinned by order tests (S4). Exponentials recognized by divisibility-and-search, never computed — the resolution of the circularity scare.
- Reservedness by length + maximality replaces a reserved symbol — when the payload uses the whole alphabet, a separator can still be guaranteed genuine by out-lengthing every accidental lookalike and asserting maximality inside the detecting formula (S8–S15; Quine). Chapter III's δ was the degenerate case where the payload had a spare digit.
- Unordered certificate sets suffice — condition (β) forces every member of a certificate to be a correct (a, x^a) pair, by one metatheoretic induction over all certificates at once (S17); so the code needn't record order or completeness, only membership. Contrast Ch. III's ordered formation sequences (≺_z): the ordering apparatus was dropped, not rebuilt.
- The incompleteness proof is a template with two typed inputs — correctness + expressibility of P̃* (E1). Exercise 1 is one function-application, and the all-truths system marks the input outside the template's domain.
And the graded/ungraded cliff, met three times in one session: the divisor trick recognizes the set of powers but cannot grade p^y = z; numeral-decoding is the graded relation (why entries are stored verbatim); the naive "z is a power of x" restatement smuggles the graded relation back in. One distinction, three dead ends avoided.
Part VIII — Distinctions Ledger (confusions of the day → one-line resolutions)
| raised | resolution |
|---|---|
| Why does dropping E matter — doesn't incompleteness carry down? | It doesn't: Ch. III's Gödel sentence isn't even in L_A; and below {+,·} completeness actually happens (Presburger +, Skolem ·) — the threshold is real and Theorem E shows {+,·} crosses it. |
| The recursion tower is uniform — why does the language stop at ·? | The equations' uniformity is metatheoretic; "iterate y times" is not a formula. + and · suffice to code finite records, which simulates all iteration at once — so no third primitive is needed. |
| Concatenation uses 13^ℓ(y) — circular dependence on E? | The formula never grades an exponential: it recognizes powers (divisor test, S1–S2) and pins "least power exceeding n" by order tests (S4). No exponent variable anywhere. |
| "'z is a power of x' has no divisor characterization" — meaning? | Ungraded vs graded: the set of powers of a prime has a static divisibility test; the relation p^y = z (exponent free) does not — grading counts iterations, the unformalizable thing. |
| Why not code entries as numerals (only two symbols, digits freed for walls)? | Decoding a numeral-code back to its value is the graded exponential relation. Entries go in verbatim; verbatim uses all thirteen digits. |
| Why not reuse δ as the separator? | Ch. III's payload was K₁₁ — δ-free by construction. §4's payload is "any natural numbers whatsoever" (the book's phrase): all digits occur, no digit is reservable. |
| What do frames do — what load? | They are the separator with reservedness enforced by length + maximality instead of by symbol: out-length every accidental 1-run, then assert in-formula that nothing longer occurs. |
| "Bounded quantifiers matter because we want finite checks for the induction"? | Half right: bounded = terminating check, yes — but the formula never performs the induction. (β) is checked member-by-member; the induction over certificates is ours, in the metatheory, once (S17). |
| "Mystical expressions" — smearing, junk-tolerance, recognized-not-computed | Each cashed or deleted: "recognized not computed" = bounded search + divisibility/order tests (S1, S4); "junk-tolerance" = (β) forces even extra pairs correct (S17); the rest deleted as compression artifacts. Method rule: expand every metaphor into steps or drop it. |
| Exercise 1: "adding G just patches; the same consequence recurs" | Not the same: G becomes provable; a new G′ arises — and only because the axiom-set stays arithmetically expressible (one extra disjunct, E3). The all-truths extension is the patch for which that check fails, and it is complete. |
| Is eliminating E just reductionism — recursion not forbidden as a primitive, but "derived" being more rigorous? (post-session) | Half right: nothing forbidden — P.E. is the system with E primitive (N₁₀–N₁₁ are its recursion equations), and it is exactly as rigorous. What's gained isn't purity but (1) theorem strength — incompleteness doesn't transfer downward, so every discardable primitive widens its scope, and Presburger/Skolem show {+,·} is the floor; (2) a boundary map: E over {+,·} is an abbreviation (definable — Theorem E), · over {+} is genuine power (else Presburger would decide multiplication). Reduction locates the abbreviation/power line; it doesn't purify. And metatheoretic recursion (S17's induction) is never eliminated — only recursion as an object-language primitive. |
| In M, why may (∀a ≤ w)(∀b ≤ w) be read as "every member of the coded set"? | S16: K(a,w,b) → a,b ≤ w — members cannot outrun their code, so the bounded sweep misses nothing. Property (ii) of Lemma K exists precisely to license this reading. |
Part IX — Self-Test
Do these cold; answers follow each.
1. State the divisor characterization of "w is a power of p," and give the exact counterexample for base 10.
Answer
Every divisor of w other than 1 is divisible by p — correct iff p is prime. Base 10: w = 100 has divisor 4; 4 ≠ 1 and 10 ∤ 4, yet 100 = 10². The test wrongly rejects genuine powers (and only primality guarantees it accepts nothing else).
2. Parse Con's third block, (∀v < w)(Pw(v) → v ≤ n). What does it pin, together with n < w, and what variable does it eliminate?
Answer
"No smaller power of 13 exceeds n"; with n < w it makes w the least power of 13 exceeding n, i.e. 13^ℓ(n) — pinned by order tests among numbers ≤ z, eliminating the exponent ℓ(n) (no exponent variable ever appears).
3. Why are entries stored as a+1, b+1 rather than a, b — and why is the shift harmless for the bounds?
Answer
Entries can be 0 — the certificate's seed is (0,1), and b = 0 occurs when x = 0 — and 0 has no base-13 string (leading digit ≠ 0). Harmless: a ≤ a+1 ≤ w still gives a ≤ w (S16).
4. What is the digit 2's entire job, in one sentence, and which step states it?
Answer
It confines 1-runs: a frame cannot cross a non-1 digit, and every separator begins and ends with 2, so each maximal frame of w lies wholly inside one entry, one s, or one t — the census, S9.
5. Show by digit computation that OB(m) := m ≥ 1 ∧ Pw(12m + 1) recognizes frames.
Answer
m = 1ⱼ: 12·m is j copies of the digit twelve (no carrying, 12 < 13); adding 1 carries through every position, giving 1 followed by j zeros = 13^j. Conversely 12m+1 = 13^j forces m = (13^j−1)/12 = 1ⱼ. E.g. j = 3: 12·(111)₁₃ = (ccc)₁₃, +1 = (1000)₁₃.
6. What false match do K's blocks ¬Blk(f, a+1) ∧ ¬Blk(f, b+1) prevent, and at which step are they spent?
Answer
A "wide" match whose middle straddles several genuine cells — a whole t hiding inside the detected a+1 or b+1. Spent at S14: a t inside the middle would put 2m consecutive ones into an entry, making f = 1ₘ part of it, contradicting the blocks.
7. Why is M's bounded sweep (∀a ≤ w)(∀b ≤ w) entitled to mean "every member of S_w"? Name the step.
Answer
S16 (Lemma K property (ii)): K(a,w,b) → a,b ≤ w, so no member lies beyond the bound. Without it the sweep could miss members and M's parse ("S_w is a certificate") would be false.
8. Where does S17's induction happen — inside the formula or outside — and what does the formula do instead?
Answer
Outside: we prove once, about all certificates, that every member is a correct (a, x^a) pair. The formula only checks (α) and (β) member-by-member under bounded quantifiers — a terminating check per member, no induction performed.
9. Why may S_w contain pairs beyond the honest history {(i, x^i)} without harm?
Answer
(β) applies to every member, so S17's induction forces even the extras to satisfy b = x^a. That is why the code needn't record order or completeness — membership plus local correctness suffices.
10. Exercise 1: what single clause changes in the arithmetized provability machinery of P.A. + {G}, and for which extension does the re-run fail?
Answer
The axiom-check: A(v₁) becomes A(v₁) ∨ v₁ = ḡ — one disjunct, one numeral; all else untouched, so P̃ stays expressible and a new G′ arises. The re-run fails for P.A. + all true sentences: correct and complete, because expressibility of P̃ — condition (ii) — is exactly what breaks.
11. The aerial one-liner: why is "P.A. is incomplete" the sharpest possible form of the phenomenon, given Presburger and Skolem?
Answer
Because + alone and · alone are each complete and decidable — remove either symbol and incompleteness vanishes. {+,·} is thus the minimal vocabulary exhibiting it, and Theorem E is what brings the Ch. III machinery down to that minimum.
Part X — Position, owed items, debts
Position: Chapter IV pp. 40–50. §§1–5 done in depth — Theorem E fully owned in chain form (Part V), via §5's certificate proof; §6 (incompleteness of P.A.) read as the corollary it is. Deliberately deferred by the reader's choice: Remark (2)'s alternative proof via β-functions (Gödel's 1931 route: ordered history transcribed by a β(w,i) built from K; historically via the Chinese Remainder Theorem) — available for a future session as a contrast piece: ordered-history vs unordered-set. Next in the book: "More on Σ₁-Relations," p. 50 onward.
Owed by the reader — book checks (new today): 1. The main one: how the book's pure-1-frame Lemma K handles run-merging at separator boundaries — an entry ending in 1's sits flush against a frame, extending the 1-run; Part V's digit-2 guards make the problem vanish by construction (S9), so the book must be doing something else inside the maximal-frame analysis. Find it. (This is the deviation's outstanding obligation.) 2. Two 30-second checks: (a) the divisor characterization at w = 1 — does the book count 1 as a power (13⁰) as S2 does? (b) how §5 words the x = 0 case (0⁰ = 1, 0^y = 0 — Part V's chain handles it via the +1 shift and (β)'s d·x = 0).
Owed, standing (July 24–26, unchanged): L₂(x), L₃(x) strings; N₁₂'s sub-relation (hint sealed in the July 26 file, Part XI); L₃ case-check; the ancestor-interpretation falsification; the whole-domain instance question; July 26's two 30-second spellings checks.
Debt register — two PAID today: E-elimination (the standing debt since July: Part V is the payment in full) and prime base 13 (S2 is where primality is spent; base 13 now earned, not lucky). Remaining: property 1 ⇒ property 2; mechanical ⇒ Arithmetic; adequacy 1930; general machine form of 1931; operation-agreement; instantiation from L₆ + L₇.
Method note — the settled chain format. Today's format war (Part 0) ended in the shape now considered definitive for formal material: GOAL with target shape and obligations → glossary of citable definitions → hallmark steps, each opening with its load, each formula parsed block-by-block into semantic content, each justification citing labels — and arithmetic parsed at the digit level wherever numbers are strings. The negative rules earned along the way: no metaphor doing load-bearing work (expand or delete); no background-facts block (grade-school facts are used inline at the point of use); no rigor without a stated destination; function before formula. This file's Part V is the reference instance.
Previous sessions: July 15 (Ch. 1), 17 (answers), 19–22 (Ch. II), 20 & 23 (exercises), 24 with continuations of 25 (Ch. III §1), 26 (Ch. III §§2–4). This file: Ch. IV.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月27日研读 · 斯穆里安《哥德尔不完备性定理》,第四章,书第40–50页(§1 P.A.的不完备性,§2 Σ₀/Σ₁/Σ,§3 素数底下的连接,§4 有限集引理,§5 定理E的证明,已看到§6)· 与7月15、17、19–24日(含25日续篇)及26日研读配套 · 性质:一次策略研读转变成形式化研读。读者先问为什么需要这一章,再问定理E证明的中心策略,随后——通过连续四次否决格式——迫使链条采用一种如今被判定为这一系列最佳的形式:目标 + 可引用的术语表 + 标志性步骤,每一步开头说明它承担的任务,每个公式逐块解析其语义内容,每个论证都引用已标记的依据。第五部分完整呈现这条链;第0部分记录格式之争,这本身也是一个成果。
本章的关键结论
{+, ·} 是不完备性的精确门槛。 第三章证明 P.E. 不完备,但其哥德尔语句含有符号 E——证明对更弱的系统 P.A.(从 P.E. 删去 E,删去两条 E 公理 N₁₀–N₁₁)没有给出任何结论。问题在两边都确实敞开,因为在门槛以下,完备性确实出现:只有 + 的算术(普雷斯伯格)和只有 · 的算术(斯科伦)各自都是完备且可判定的。因此“去掉E”不是形式手续——它是不完备性消失之前的最后一级下降。定理E从上方解决问题:x^y = z 是 Σ₁——仅从 + 和 · 即可定义——于是第三章用 E 构造的一切都可以在 P.A. 内重建,P.A. 因此不完备(§6)。更深的启示:E 从来不是表达能力的来源,只是便利;真正的来源在于 + 和 · 合起来能够编码有限序列,也正是在这里,整个递归塔(后继 → 加法 → 乘法 → 指数 → ……)坍缩为可定义性。
如何使用本文
第一至四部分按本次研读的推进顺序,重建证明为什么具有这样的形状——门槛、障碍、循环疑虑、分隔符问题。第五部分是交付结果:以最终格式构成有依据的链条,给出定理E的完整证明。第六部分是练习1,先评判回答,再正确完成。区分表(第八部分)用于复习;自测(第九部分)检验是否掌握。一项持续标记:第五部分的编码偏离书中的编码(使用数字2保护的框,而非纯1框)——偏离在起点(S8)声明,在发挥作用之处(S9、S12–S15)兑现;与证明其余部分的接口与书中引理K相同。由此产生的对书核验任务记在第十部分。
第0部分——格式之争(方法上的成果)
同一证明的四个版本被否决,最后才有一个站稳;每次否决都分离出一条规则。失败依次是:
- 让比喻术语承担关键工作——“涂抹”“容忍废料”“只识别不计算”“切断E的唯一切口”。读者说:“你要解释事情,而不是用其他未经解释的术语解释术语。” 7月24日的第三种失败模式(比喻堆叠)复发,又被抓住。每个这样的短语,要么得到定义和标签,要么展开成它压缩的步骤后被删除。
- 一个背景事实块(B1–B3),把位值记数法、素数、递归方程作为编号假设列出。因杂乱被否决:这种层级的事实应在使用处直接使用,并附一句理由,而不是在开头供起来。只有承担关键任务、值得引用的项目才配有标签。
- 无目标的严谨。 清爽版本去掉了“目标/义务”的支架,恰好因此被否决:没有声明目的地的严谨,以另一种方式变得不可读。
- 作用陈述得太晚。 标志性命题必须先说承担什么任务——这一步做什么用,并向前引用——然后才给公式,不能事后补充。
最终定型的格式(读者说:“远优于此前的形式,也易懂得多”):
- 目标在先:定理、一个目标形状(“完成”是什么样子,用可检验的条件T1、T2……表示),以及分解成的义务 G1、G2……,每个链条步骤都标出它服务的义务。
- 任何论证之前,先列可引用定义的术语表(保留7月24日的工具)。
- 标志性步骤 S1、S2……——每步先说明任务,再给公式,然后给逐块解析表:左栏列字符串的每个句法块,右栏解释其语义上说什么,并引用依据。随后给断言及证明,每个理由都点名此前标签。
- 把算术解析成字符串:m·w + n、12·m + 1、2∗f∗f∗2 这样的表达式,从数位层面读出(这段算术构造了什么字符串?),因为本章中数就是其十三进制字符串。
第一部分——为什么“不用指数”值得一章
不完备性不向下传递。 更弱的语言证明得更少——但它也说得更少,所以可能无法证明的东西也更少。第三章的不可判定语句 H[h̄] 是 L_E 的语句;它甚至不是 P.A. 语言 L_A 的语句。要证明 P.A. 不完备,就需要一个不含 E 写成的哥德尔语句,即只用 + 和 · 重做算术化——7月26日的十七个条件。
让问题有趣的门槛事实(书的开头陈述,证明在别处):有 + 而无 · 的算术完备且可判定(普雷斯伯格,1929);有 · 而无 + 的算术同样如此(斯科伦)。所以 +、· 单独都弱得不足以不完备。{+, ·} 这对组合是现象开启之处——定理E证明它确实在那里开启,无须再加什么。
为什么 P.E. 最初有 E,以及为什么能去掉它。 E 作为原始符号进入,是因为第三章的编码依赖它(Num(x) 是一个 Pow₁₃;连接的定义使用 13^ℓ(y))。它能够离开,是因为它可导出:定理E说明关系 x^y = z 在 +、· 中是 Σ₁——所以 E 是冗余,而非能力。排除它是一个定理,不是一种品味。
第二部分——障碍:递归不是可定义性
读者的挑战:这座塔是统一的——加法是迭代后继,乘法是迭代加法,指数是迭代乘法——为什么语言会止步于 ·?统一性在哪里断裂?
回答:“迭代 y 次”不是一阶语句。 递归方程
x + 0 = x x + (y+1) = (x + y) + 1
x · 0 = 0 x · (y+1) = x·y + x
x ^ 0 = 1 x ^ (y+1) = x^y · x
各自通过长度为变量 y 的归纳定义下一层。L_A 的公式是一个固定的有限字符串;它不能包含任何东西的 y 重嵌套副本。因此,把 + 和 · 作为原始符号,并不自动给出 x^y = z 的公式——方程的统一性存在于元理论,而非语言中。哥德尔发现的(§§3–5用奎因方法重构的)是,+ 和 · 足以编码一个有限序列并局部检查它——“存在一份计算记录,其中每行都正确”——而一旦序列可编码,塔的每一层(以及多得多的其他东西)就同时变得可定义。这就是原始符号塔可以止于 · 的原因:不是因为迭代不再重要,而是两层就足以表达“有限记录”,有限记录能模拟一切迭代。
“可定义到什么程度”的术语(链条的D1–D2): Σ₀ = 仅在 +、· 上使用有界量词,所以 Σ₀ 语句的真值是会终止的有限检查;Σ₁ = 在 Σ₀ 公式前加一个无界 ∃——“存在一个可在有界时间内检查的见证”。定理E恰好把 x^y = z 放在这里。
第三部分——循环疑虑与因子技巧
疑虑。 计划需要记录编码;记录编码需要连接;但7月21日的连接是 x ∗ y = x·13^ℓ(y) + y——里面有指数。 我们是在用 E 定义 E 吗?
解决:识别,而非计算。 公式从来不需要带级数的关系 13^ℓ = w(指数作为变量)。它只需要 (a) 13的幂组成的集合——可通过整除测试识别——以及 (b) “大于 y 的最小13的幂”——通过 ≤ z 的数之间的序关系测试钉定。两者都是 Σ₀。整除测试是本章唯一诉诸素性的地方:
w 是13的幂 ⟺ w 除1以外的每个因子都能被13整除
——成立是因为13是素数(13^k 的因子的素因子分解中只有13),在十进制下则为假:4整除100,10却不整除4。这就是底数必须为素数的原因,也说明第三章的底数13是一种幸运的必然性,如今获得了根据。
带级数/不带级数的区分(本次研读反复遇到的断崖)。 “z 属于 p 的幂集”(不带级数)具有上述因子刻画——一行 Σ₀。“p^y = z”且 y 为自由变量(带级数)没有这样的静态刻画:指数数的是迭代次数,而数迭代次数恰恰是公式做不到的(第二部分)。本章整个架构都安排为:在公式内部,始终只需要不带级数的事实;带级数的关系 x^y = z 则在最后通过证书方法,作为定理本身给出。同一个断崖解释了下面两条死路:数码编码(第四部分)以及朴素的“z 是 x 的幂”想法——两者都暗中要求带级数的关系。
第四部分——分隔符:从 ♯ 到框
第三章的分隔符,及它为何在这里失效。 7月26日的序列数是 δx₁δx₂δ…δxₙδ——可行,因为内容是 K₁₁,即不含 δ 的数,它覆盖了所有有意义表达式的哥德尔数。δ 是一个保留符号:成员中禁用它,所以边界不会认错。但§4的有限集引理必须编码任意自然数所成数对的序列——这就是书中“任何自然数,无论什么数”的意思——而任意数使用全部十三个数位符号。没有哪个数位能保留;任何候选边界字符串都可能出现在成员内部。
数码这条死路(读者的建议,被断崖阻断)。 为什么不把条目编码为数码,它只用两个符号,就能空出十一个数位作边界?因为 a 的数码是字符串 0…0(a 个撇号),其哥德尔数形如 g·13^a:从数码编码解码回 a,就是带级数的指数关系——恰好是正在定义的东西。条目必须原样存储(位值记数法,解码成本为零),而原样条目会使用每个数位。
奎因的修补:靠长度保留,而非靠符号。 框是字符串全为1的数(D6)。固定长度 j 的框可能出现在成员内部——这无法禁止——但可以以更长者压过:选择一个分隔尺度,比任何成员内部任何连续1串都长,并在检测公式中添加最大性条款(“整个编码中的任何框都不超过分隔尺度”),保证检测到的分隔符是真的。保留性变成每个编码中由不等式实施的性质,而不再由字母表全局实施。(克里普克的替代方案,见书中说明:对每张表扩大底数,使每个条目都是一位——改为靠底数选择保留。不再追究。)
本次研读的变体(标记偏离)。 以下链条用数字2保护每个框的两端(分隔符为 2 1…1 2),由构造限制连续1串,使统计论证(S9)只需一行;书中的纯1框则必须在最大框分析中处理条目边界处连续1串的合并。接口相同;对书核验记在第十部分。
第五部分——定理E:链条(最终格式)
目标
定理E。 关系 x^y = z 是 Σ₁。
目标形状:给出 ∃w[M(x,y,z,w)],满足
义务: G1(工具:数对有限集的 Σ₀ 可检测编码,条目以其编码为界)——S1–S16。G2(重述:将 x^y = z 表述为存在证书)——S17。G3(组装)——S18–S19。
术语表(可引用,先于任何论证)
- D1。 Σ₀公式:仅由 +、·、=、≤、联结词和有界量词 (∀v ≤ t)、(∃v ≤ t) 构成。
- D2。 Σ₁关系:可表达为 ∃w F,F 为 Σ₀。
- D3。 x div y ⟺ (∃v ≤ y)(x·v = y)。
- D4。 固定认同:每个正数就是其十三进制数位字符串(唯一,首位 ≠ 0);ℓ(n) = 其长度。全文使用两个数位事实:乘以13是在末尾添一个0;长度为 ℓ 的字符串恰是区间 [13^(ℓ−1), 13^ℓ) 内的数。
- D5。 x P y:x 的字符串作为连续块出现在 y 的字符串内部。
- D6。 框:字符串全为1的数;1ⱼ = j 个1的框。所以 ℓ(1ⱼ) = j,且 1ⱼ ≤ 1ₖ ⟺ j ≤ k。
- D7。 y 的最大框:一个框,它是 y 的部分,而不是 y 中任何更长框的部分。
- D8。 (x,y,z) 的证书:数对的有限集 S,满足 (α) (y,z) ∈ S;(β) 每个 (a,b) ∈ S 要么是 (0,1),要么等于某个 (c,d) ∈ S 的 (c+1, d·x)。
- D9。 m ∗ n(m, n ≥ 1):其字符串是 m 的字符串后接 n 的字符串的数。
链条
Pw(w) := w ≥ 1 ∧ (∀v ≤ w)[ (v div w ∧ v ≠ 1) → 13 div v ]
| 块 | 所说内容 |
|---|---|
| w ≥ 1 | w 有字符串(D4) |
| (∀v ≤ w)[…] | 不超过 w 的每个 v 都通过括号中的测试——有界,所以是有限检查(D1) |
| v div w ∧ v ≠ 1 | v 是 w 除1以外的因子(D3) |
| 13 div v | v 是13的倍数——作为字符串:v 以数位0结尾(D4:末尾添0 = 乘以13) |
整个字符串说:w 除1以外的每个因子都以数位0结尾。
S2。 Pw(w) 为真 ⟺ w ∈ {1, 13, 13², …}。(⟸:13是素数,所以13^k 的因子的素因子分解中只有13——每个 ≠ 1 的因子都是13的倍数;w = 1 空洞地通过。⟹,用逆否:w 不是13的幂,给出 w = 13^k·m,13 ∤ m,m > 1;则 v := m 是一个 ≠ 1 且不以0结尾的因子。链条中唯一使用素性的步骤;十进制在此失败:4 div 100,10 ∤ 4。)
S3。 对 m, n ≥ 1:m ∗ n = m·u + n,其中 u 是大于 n 的最小13的幂。(D4、D9。算术解析:u = 13^ℓ(n)——由D4第二个事实,这恰是大于 n 的最小幂;m·u = m 的字符串后接 ℓ(n) 个0——把D4第一个事实用 ℓ(n) 次;+ n 把 n 的 ℓ(n) 个数位写入这些0的位置,无进位。结果:m 的字符串后接 n 的字符串,即 m ∗ n。这一机制的十进制图像:95·100 + 25 = 9525。)
Con(m,n,z) := (∃w ≤ z)[ Pw(w) ∧ n < w ∧ (∀v < w)(Pw(v) → v ≤ n) ∧ z = m·w + n ]
| 块 | 所说内容 |
|---|---|
| (∃w ≤ z) | 有某个不超过 z 的数……(界限合理:若 z = m·w + n,m ≥ 1,则 w ≤ z——真正见证在搜索范围内) |
| Pw(w) | ……它是13的幂(S2) |
| n < w | ……大于 n |
| (∀v < w)(Pw(v) → v ≤ n) | ……而每个更小的13的幂都不大于 n。与上一块合起来:w 是大于 n 的最小13的幂——仅靠序关系测试钉定,不含指数变量(S2) |
| z = m·w + n | z 是 m 的字符串后接 n 的字符串(S3,因为 w 现已是S3的 u) |
断言:对 m, n ≥ 1:Con(m,n,z) ⟺ m ∗ n = z。(⟸:w := 13^ℓ(n) 由S2和S3验证每一块。⟹:13的幂全序排列,所以第2–4块强制 w = 13^ℓ(n);第5块及S3完成。从此以后,任何公式内部的 ∗ 都是 Con 的缩写。)
Blk(m,n) := m = n ∨ (∃u ≤ n)Con(u,m,n) ∨ (∃v ≤ n)Con(m,v,n)
∨ (∃u ≤ n)(∃q ≤ n)(∃v ≤ n)(Con(u,m,q) ∧ Con(q,v,n))
| 块 | 所说内容 |
|---|---|
| m = n | m 的字符串就是 n 的整个字符串 |
| (∃u ≤ n)Con(u,m,n) | n = u ∗ m:m 位于右端(S4) |
| (∃v ≤ n)Con(m,v,n) | n = m ∗ v:m 位于左端 |
| (∃u…)(∃q…)(∃v…)(Con(u,m,q) ∧ Con(q,v,n)) | n = (u ∗ m) ∗ v:m 位于内部;q 命名中间值 u ∗ m |
断言(a):对 m, n ≥ 1,Blk(m,n) ⟺ m P n。(四块枚举连续出现的四种可能位置——D5。) 断言(b): Blk(m,n) → m ≤ n,且每个存在见证都 ≤ n,所以显示的界限不遗漏任何东西。(S3的恒等式:u ∗ m = u·w + m ≥ m,且 m ∗ v = m·w′ + v ≥ m;内部情形组合使用。这个不等式为下面每个有界量词提供依据。)
S6——框的事实。 1ⱼ ∗ 1ₖ = 1_{j+k} (D9:写 j 个1,再写 k 个1);且 Blk(1ⱼ, n) ⟺ n 的某个最大框长度 ≥ j。(⟸:该框中 j 个连续位置就是 1ⱼ 的一次出现——S5(a)。⟹:j 个连续数位1的任何一次出现都扩展为一个长度 ≥ j 的最大框——D7。这就是数 1ⱼ 与字符串事实“j 个连续1”之间的双向桥梁。)
S7——字符串 OB 及其解析。 定义 OB(m) := m ≥ 1 ∧ Pw(12·m + 1)。
算术解析,其中 c = 数位十二:若 m = 1ⱼ,则 12·m 是 j 个 c 的字符串(每个数位1变成12;无进位,因为12 < 13),再加1则每一位都进位:c c…c + 1 = 1 0 0…0(j 个0)= 13^j。具体地,j = 3:12·(1 1 1) = (c c c);(c c c) + 1 = (1 0 0 0)。
断言: OB(m) ⟺ m 是框。(⟸:上面的计算 + S2。⟹:12m + 1 = 13^j,m ≥ 1 强制 m = (13^j − 1)/12 = 13^(j−1) + … + 13 + 1 = 1ⱼ。)
S8——编码布局。 给定非空 Q = {(a₁,b₁), …, (aₙ,bₙ)}:条目可能为0,而0没有字符串(D4),所以存储 a+1、b+1。令 m := 1 + max{ℓ(aᵢ+1), ℓ(bᵢ+1)}——严格长于每个存储字符串——并设
s := 2 ∗ 1ₘ ∗ 2 t := 2 ∗ 1₂ₘ ∗ 2
w := t ∗ (a₁+1) ∗ s ∗ (b₁+1) ∗ t ∗ … ∗ t ∗ (aₙ+1) ∗ s ∗ (bₙ+1) ∗ t
w 的一个单元的字符串图像:
2 [2m个1] 2 [aᵢ+1] 2 [m个1] 2 [bᵢ+1] 2 [2m个1] 2
(从这里开始偏离书本:书中的 s、t 是纯框 1ₘ、1₂ₘ;数位2的端点是本次研读所加。)
S9——w 中最大框的统计。 w 的每个最大框都完全位于一个条目字符串、一个 s 或一个 t 内,其长度分别为 < m、恰好 m、恰好 2m。(框占据连续的数位1,所以不能跨越任何带其他数位的位置[D6、D7];由S8,每个 s 和 t 都以数位2开头、结尾,所以分隔符的1不能与条目的1连在一起,反之亦然。长度直接由S8读出。这种限制就是数位2的全部任务。)
K(a,w,b) := (∃f ≤ w)[ OB(f) ∧ ¬Blk(f, a+1) ∧ ¬Blk(f, b+1)
∧ Blk(2∗f∗f∗2 ∗ (a+1) ∗ 2∗f∗2 ∗ (b+1) ∗ 2∗f∗f∗2, w)
∧ (∀h ≤ w)(OB(h) ∧ Blk(h,w) → h ≤ f∗f) ]
| 块 | 所说内容 |
|---|---|
| (∃f ≤ w) | 有某个不超过 w 的数……(界限合理:预期的 f 出现在 w 内,所以由S5(b),它 ≤ w) |
| OB(f) | ……一个框——把长度记为 k(S7) |
| ¬Blk(f, a+1) | a+1 的字符串中任何地方都没有 k 个连续1(S6) |
| ¬Blk(f, b+1) | b+1 同样如此 |
| 2∗f∗f∗2 | 字符串:2,然后2k个1,然后2——尺度 k 下的 t 形(S6:f∗f = 1₂ₖ) |
| 2∗f∗2 | 字符串:2,然后k个1,然后2——尺度 k 下的 s 形 |
| Blk(2∗f∗f∗2 ∗ (a+1) ∗ 2∗f∗2 ∗ (b+1) ∗ 2∗f∗f∗2, w) | 一个尺度为 k、条目槽中放 a+1 和 b+1 的完整单元,出现在 w 的某处(S5(a)、S8的图像) |
| (∀h ≤ w)(OB(h) ∧ Blk(h,w) → h ≤ f∗f) | w 中出现的每个框都 ≤ 1₂ₖ——即 w 没有长度大于2k的最大框(S6、S7、D6) |
(每个 ∗ 都通过 Con 展开[S4];每个中间连接本身都是 w 的部分,所以由S5(b),它 ≤ w——内部界限合理。因此 K 是 Σ₀。)
S11——每个存储的数对都被检测到:(a,b) ∈ Q ⇒ K(a,w,b)。 取见证 f := 1ₘ,于是 k = m。第2块:S7。第3–4块:条目内若有 m 框,就通过S6与S9的长度统计(< m)矛盾。第5块组:S8布局中数对 (a,b) 的单元,字面上就是尺度 m 下所需的字符串。第6块:w 的每个框长度都 ≤ 2m(S9),因此 ≤ 1₂ₘ = f∗f(S6、D6)。
S12——(仅存储者,第1步)任何见证 f 都有长度 m。 (第5块把2k个连续1放入 w,所以 w 的某个最大框长度 ≥ 2k[S6];统计给出上限:2k ≤ 2m[S9]。反过来,1₂ₘ 出现在 w 的任意 t 内[S8],所以第6块在 h := 1₂ₘ 处给出 1₂ₘ ≤ 1₂ₖ,即 2m ≤ 2k[D6]。所以 k = m,f = 1ₘ。)
S13——(第2步)w 中每次出现的“2、2m个1、2”都恰好位于一个 t。 (它的2m个1位于一个长度 ≥ 2m 的最大框内部;由S9,只有 t 的内部符合条件,而那里恰有2m个1——所以这次出现的1恰好填满 t 的内部,两侧的2就是该 t 自己的2。)
S14——(第3步)这次单元出现的两个 t 形端点,位于 w 中两个连续的 t。 (由S12+S13,它们位于 t。若不连续,就会有一个完整的额外 t 严格位于中间“(a+1) 2 [m个1] 2 (b+1)”内;它的2m个1既放不进 s 形[只有m个1],也放不进 a+1 或 b+1——否则该条目包含m个连续1,使 f = 1ₘ 成为其部分[S6],与第3–4块矛盾。)
S15——(第4步)中间匹配一个存储数对;因此 (a,b) ∈ Q。 (在两个连续 t 之间,w 恰读为 (aᵢ+1) 2 [m个1] 2 (bᵢ+1)[S8];第5块说同一段读为 (a+1) 2 [m个1] 2 (b+1)。定位这次出现的“2 [m个1] 2”:它的m个1需要该段中一个长度 ≥ m 的最大框;条目中的框 < m[S9],所以仅 s 的内部符合——长度恰为m——强制这些1及两侧的2与 s 重合。在这个共享地标左侧,同一数位段既是 a+1,又是 aᵢ+1——相同字符串,相同数[D4];右侧同理。所以 (a,b) = (aᵢ,bᵢ)。 S11–S15合起来:K(a,w,b) ⟺ (a,b) ∈ Q——G1(i) ✓。)*
S16——条目以编码为界:K(a,w,b) → a ≤ w ∧ b ≤ w。 (第5块:a+1 是单元的部分,而单元是 w 的部分;两次用S5(b),得 a+1 ≤ w,因此 a ≤ w;b 同理。——G1(ii) ✓。 任务:它将使有界遍历 (∀a ≤ w)(∀b ≤ w) 能穷尽所编码的集合。)
S17——重述:x^y = z ⟺ 存在 (x,y,z) 的证书。 (⟹:S := {(i, x^i) : i ≤ y} 在 i = y 时满足 (α),并通过 (0, x⁰) = (0,1) 及 (i+1, x^(i+1)) = (i+1, x^i·x) 满足 (β)[D8]。⟸:对 a 归纳——每个 (a,b) ∈ S 都有 b = x^a:在 a = 0 时,(β) 的第二选择不可能,强制 (0,1) = (0, x⁰);在 a > 0 时,(β) 给出 (a,b) = (c+1, d·x),且 (c,d) ∈ S,所以 c = a−1,由归纳假设 d = x^(a−1),b = x^a。诚实列表之外的额外数对也因此被强制正确——所以 (β) 无须提及次序或完备性。然后 (α) 给出 z = x^y。归纳由我们一次性针对所有证书实施;没有公式在实施归纳。——G2 ✓。)
M := K(y,w,z) ∧ (∀a ≤ w)(∀b ≤ w)[ K(a,w,b) →
(a=0 ∧ b=1) ∨ (∃c ≤ w)(∃d ≤ w)(K(c,w,d) ∧ a = c+1 ∧ b = d·x) ]
全文将“所编码的集合”读作 S_w := {(a,b) : K(a,w,b)}。
| 块 | 所说内容 |
|---|---|
| K(y,w,z) | (y,z) ∈ S_w——所编码集合满足D8的条款 (α) |
| (∀a ≤ w)(∀b ≤ w)[K(a,w,b) → …] | “S_w 的每个数对都满足……”有界遍历能这样读,仅仅因为S16:S_w 没有成员位于 w 以外,因此没有东西逃出界限 |
| a = 0 ∧ b = 1 | 该数对是种子 (0,1)——(β) 的第一选择 |
| (∃c ≤ w)(∃d ≤ w)(K(c,w,d) ∧ …) | S_w 包含某个数对 (c,d)……(再次由S16,界限合理:任何成员数对都在 w 以下) |
| a = c+1 ∧ b = d·x | ……(a,b) 是它的一步后继:第一坐标加1,第二坐标乘以 x——(β) 的第二选择 |
M 的整个字符串说:S_w 是 (x,y,z) 的证书(D8)。
S19——定理E。 x^y = z ⟺ ∃w M;且 ∃w M 是 Σ₁。
(⟹:由 x^y = z 得到证书 S[S17 ⟹];将其编码为 w[S8、S11–S15:精确地 S_w = S]。于是 (α) 作为 K(y,w,z) 成立;对每个成员,(β) 的选择都传递:前驱 (c,d) ∈ S 被检测到[S11],并由有界 ∃ 可达[S16]。⟸:给定使 M 为真的 w,S18的解析说 S_w 是 (x,y,z) 的证书;S_w 有限[S16:≤ (w+1)² 个候选]且非空[(y,z) ∈ S_w];应用S17 ⟸:z = x^y。
形状检查。T1:K 是 Σ₀[S10];M 仅添加有界量词、=、+、·——由D1为 Σ₀。T2:两个方向如上。T3:展开每个缩写,M → K → OB, Blk → Con → Pw → div——剩下的词汇:+、·、=、≤、常数13、联结词、有界量词;没有 E。由D2,∃w M 为 Σ₁。——G3 ✓,目标达成。 ∎)
第六部分——练习1:P.A. +
练习(第50页)。 G = H[h̄],在 P.A. 中为真但不可证(H(v₁) 表达 P̃*)。将 G 加为公理;P.A. + {G} 仍正确,因为 G 为真。它完备吗?
读者的回答及评价。 判断“不,不完备”——正确。“G 现在是公理,所以这只是补丁”——框架正确:证明从来不针对某一条缺失公理。“形式逻辑最终会反复产生同一后果”——需要两处修补:(1) 不是同一后果:G 自身现在一行可证(它是公理),所以 G 不再是见证;再次出现的是新语句 G′,由同一构造从新系统的可证性集构成。(2) 没有什么“最终”,重新运行也并非免费:不完备性论证是具有两个输入条件的模板,重新应用它要求对扩大的系统检查两者——一个由练习直接给出,另一个就是解答的全部数学内容。
链条。
E1(定理作为模板)。 第三/四章的论证接受任意满足以下条件的系统 S:(i) S 正确,(ii) P̃*_S 可由某个 H_S(v₁) 表达——其中 P*_S := {n : E_n 的对角化在 S 中可证}——并输出:G_S := H_S[h̄_S] 为真,但在 S 中不可证。(把已掌握的证明重读为 S 的函数:它没有在任何地方使用 P.A. 除 (i)、(ii) 以外的性质。)
E2(条件(i))。 P.A. + {G} 正确——给定(G 为真,P.A. 正确,真理的后果为真)。
E3(条件(ii)——关键检查)。 P.A. + {G} 的算术化可证性机制与 P.A. 恰好只差一条:原来的公理检查公式是 A(v₁),现在变成 A(v₁) ∨ v₁ = ḡ,其中 g 是 G 的哥德尔数——一个析取项,一个数码。形成序列、推理步骤、证明、对角化:都不动。所以 P̃*_{P.A.+{G}} 可由某个 H′ 表达。(一句话回答跳过的步骤;唯一需要验证而非引用之处。)
E4(重新应用)。 对 S := P.A. + {G} 使用E1,输入E2、E3:G′ := H′[h̄′] 为真,但在 P.A. + {G} 中不可证。不完备。∎
E5(G′ ≠ G)。 G 在新系统中可证;G′ 不可证。而且字符串也字面不同:H′ 带有额外析取项,所以 h′ ≠ h。
E6(直觉需要的边界)。 迭代——P.A. + {G, G′, G″, …}——只要E3式的可表达性存续,就永远不能填平缺口。极端补丁,即加入所有真语句,给出一个正确且完备的系统,并无矛盾:对它恰好失效的是条件 (ii)(若 P̃* 在那里可表达,对角论证就会制造一个真却不真的语句)。所以诚实的口号是:只要公理集仍可用算术表达,就没有补丁奏效——限定语正是定理所在,它区分“加入一个语句”(E3成立)与“加入一切”(E3失效)。
第七部分——今天真正新增了什么
把本章化约为思想,它带来了四项:
- 素数底给出了纯乘法的幂识别方法——“每个 ≠ 1 的因子都能被 p 整除”用一行 Σ₀ 识别 {p⁰, p¹, p², …}(S1–S2),然后用序关系测试钉定“大于 n 的最小幂”(S4)。通过整除与搜索识别指数,从不计算——解决了循环疑虑。
- 靠长度 + 最大性保留,替代保留符号——当内容使用整个字母表时,仍能以比每个偶然相似者更长、并在检测公式中断言最大性,保证分隔符是真的(S8–S15;奎因)。第三章的 δ 是内容中尚有闲置数位的退化情形。
- 无序证书集就足够——通过一次在元理论中同时覆盖所有证书的归纳,条件 (β) 强制证书的每个成员都是正确的 (a, x^a) 数对(S17);因此编码无须记录次序或完备性,只要记录成员关系。对比第三章的有序形成序列(≺_z):排序装置被删去了,而非重建。
- 不完备性证明是有两个指定类型输入的模板——正确性 + P̃* 的可表达性(E1)。练习1是一次函数应用,而所有真语句的系统标出模板定义域之外的输入。
此外,同一研读三次遇到带级数/不带级数的断崖:因子技巧识别幂的集合,却不能给 p^y = z 分级;数码解码就是带级数关系(所以条目原样存储);朴素的“z 是 x 的幂”重述又偷偷引回带级数关系。一个区分,避开三条死路。
第八部分——区分表(当天的混淆 → 一句话解答)
| 问题 | 解答 |
|---|---|
| 为什么去掉 E 重要——不完备性不向下传递吗? | 不传递:第三章的哥德尔语句甚至不在 L_A 中;而在 {+,·} 以下确有完备性(普雷斯伯格 +、斯科伦 ·)——门槛是真实的,定理E表明 {+,·} 跨过了它。 |
| 递归塔是统一的——为什么语言止于 ·? | 方程的统一性属于元理论;“迭代 y 次”不是公式。+ 和 · 足以编码有限记录,一次性模拟所有迭代——所以无须第三个原始符号。 |
| 连接使用 13^ℓ(y)——循环依赖 E? | 公式从不给指数分级:它识别幂(因子测试,S1–S2),并以序关系测试钉定“大于 n 的最小幂”(S4)。任何地方都无指数变量。 |
| “‘z 是 x 的幂’没有因子刻画”——是什么意思? | 不带级数与带级数:素数的幂集具有静态整除测试;关系 p^y = z(指数自由)则没有——分级要数迭代次数,而这正是无法形式化的东西。 |
| 为什么不把条目编码为数码(仅两个符号,空出数位作边界)? | 从数码编码解码回其值,就是带级数的指数关系。条目原样进入;原样要使用全部十三个数位。 |
| 为什么不复用 δ 作分隔符? | 第三章的内容是 K₁₁——由构造不含 δ。§4的内容是“任何自然数,无论什么数”(书的措辞):所有数位都出现,没有数位可保留。 |
| 框做什么——承担什么任务? | 它们是靠长度 + 最大性而非符号实施保留性的分隔符:比每个偶然连续1串都长,再在公式内断言没有更长者出现。 |
| “有界量词重要,因为我们想为归纳提供有限检查”? | 对了一半:有界 = 会终止的检查,是的——但公式从不做归纳。逐成员检查 (β);对证书的归纳由我们在元理论中一次性实施(S17)。 |
| “神秘表达”——涂抹、容忍废料、识别而非计算 | 每个都兑现或删除:“识别而非计算”= 有界搜索 + 整除/序关系测试(S1、S4);“容忍废料”= (β) 迫使连额外数对也正确(S17);其余作为压缩造成的残余删除。方法规则:把每个比喻展开成步骤,否则丢掉。 |
| 练习1:“加入 G 只是打补丁;同一后果重现” | 不是同一个:G 变得可证;出现的是新的 G′——且仅因为公理集仍可用算术表达(一个额外析取项,E3)。加入所有真语句的扩张是此项检查失效的补丁,它是完备的。 |
| 消去 E 只是还原主义吗——并不禁止把递归当原始项,只是“导出”更严谨?(研读后) | 对了一半:没有禁令——P.E. 就是以 E 为原始符号的系统(N₁₀–N₁₁ 是其递归方程),它同样严谨。所得不是纯洁性,而是 (1) 定理的强度——不完备性不向下传递,所以每个可去掉的原始符号都会扩大其范围,普雷斯伯格/斯科伦表明 {+,·} 是底层;(2) 一幅边界图:在 {+,·} 上 E 是缩写(可定义——定理E),在 {+} 上 · 是真正的能力(否则普雷斯伯格算术就能判定乘法)。还原定位缩写/能力的分界,而不是净化。而元理论中的递归(S17的归纳)从未被消去——消去的只是对象语言中的原始递归项。 |
| 在 M 中,为什么 (∀a ≤ w)(∀b ≤ w) 可以读作“所编码集合的每个成员”? | S16:K(a,w,b) → a,b ≤ w——成员不能超过其编码,所以有界遍历没有遗漏。引理K的性质 (ii) 恰为授权这种解读而存在。 |
第九部分——自测
不看材料完成;每题后附答案。
1. 陈述“w 是 p 的幂”的因子刻画,并给出十进制的精确反例。
答案
w 除1以外的每个因子都能被 p 整除——仅当 p 为素数时正确。十进制:w = 100 有因子4;4 ≠ 1,且10 ∤ 4,但100 = 10²。测试错误地拒绝了真正的幂(也只有素性保证它不接受其他东西)。
2. 解析 Con 的第三块 (∀v < w)(Pw(v) → v ≤ n)。它与 n < w 合起来钉定什么,消去了什么变量?
答案
“没有更小的13的幂大于 n”;与 n < w 合起来,使 w 成为大于 n 的最小13的幂,即13^ℓ(n)——通过 ≤ z 的数之间的序关系测试钉定,消去了指数 ℓ(n)(从未出现指数变量)。
3. 为什么条目存成 a+1、b+1,而非 a、b——为什么这个平移不损害界限?
答案
条目可能为0——证书的种子是 (0,1),而 x = 0 时会出现 b = 0——0没有十三进制字符串(首位 ≠ 0)。无害:a ≤ a+1 ≤ w 仍给出 a ≤ w(S16)。
4. 用一句话说明数位2的全部任务,并指出哪一步陈述它。
答案
它限制连续1串:框不能跨过非1数位,每个分隔符又都以2开头结尾,所以 w 的每个最大框都完全在一个条目、一个 s 或一个 t 内——这就是统计,S9。
5. 通过数位计算说明 OB(m) := m ≥ 1 ∧ Pw(12m + 1) 识别框。
答案
m = 1ⱼ:12·m 是 j 个数位十二(无进位,12 < 13);加1使每位进位,得到1后接j个0 = 13^j。反过来12m+1 = 13^j 强制 m = (13^j−1)/12 = 1ⱼ。例如 j = 3:12·(111)₁₃ = (ccc)₁₃,+1 = (1000)₁₃。
6. K 的 ¬Blk(f, a+1) ∧ ¬Blk(f, b+1) 两块防止什么假匹配,在哪一步使用?
答案
一种中间部分跨越多个真实单元的“宽”匹配——一个完整 t 藏在检测到的 a+1 或 b+1 内。用在S14:中间若有 t,就会把2m个连续1放入一个条目,使 f = 1ₘ 成为其部分,与这两块矛盾。
7. 为什么 M 的有界遍历 (∀a ≤ w)(∀b ≤ w) 有资格表示“S_w 的每个成员”?说出步骤。
答案
S16(引理K的性质(ii)):K(a,w,b) → a,b ≤ w,所以没有成员在界限之外。没有它,遍历可能漏掉成员,M 的解析(“S_w 是证书”)就会是假的。
8. S17的归纳发生在哪里——公式内部还是外部——公式代之做什么?
答案
外部:我们一次性针对所有证书证明,每个成员都是正确的 (a, x^a) 数对。公式只在有界量词下逐成员检查 (α)、(β)——每个成员的检查会终止,没有进行归纳。
9. 为什么 S_w 可以包含诚实历史 {(i, x^i)} 以外的数对而无害?
答案
(β) 适用于每个成员,所以S17的归纳迫使连额外者也满足 b = x^a。所以编码无须记录次序或完备性——成员关系加局部正确性就足够。
10. 练习1:P.A. + {G} 的算术化可证性机制中哪一条改变了,对什么扩张重新运行会失败?
答案
公理检查:A(v₁) 变成 A(v₁) ∨ v₁ = ḡ——一个析取项,一个数码;其他不动,所以 P̃ 仍可表达,并出现新的 G′。对 P.A. + 所有真语句,重新运行失败:它正确且完备,因为 P̃ 的可表达性——条件(ii)——恰好崩溃。
11. 俯瞰的一句话:给定普雷斯伯格和斯科伦的结果,为什么“P.A. 不完备”是这一现象所能有的最精确形式?
答案
因为单独 + 和单独 · 都完备且可判定——去掉任一符号,不完备性就消失。{+,·} 因而是展示这一现象的最小词汇,而定理E把第三章的机制降到了这个最小值。
第十部分——进度、应做项目、欠账
进度:第四章第40–50页。 §§1–5已深入完成——通过§5的证书证明,以链条形式(第五部分)完全掌握定理E;§6(P.A.的不完备性)作为它本来的推论读过。按读者选择有意推迟:说明(2)中经 β 函数的替代证明(哥德尔1931年的路线:通过由 K 构成的 β(w,i) 转写有序历史;历史上经中国剩余定理)——可留作未来研读的对比材料:有序历史与无序集合。书中接下来:“关于 Σ₁ 关系的更多内容”,第50页起。
读者应做——对书核验(今日新增): 1. 主要一项:书中纯1框的引理K如何处理分隔边界处连续1串的合并——以1结尾的条目紧贴框,会延长连续1串;第五部分的数位2保护使问题由构造消失(S9),所以书一定在最大框分析中做了别的事。找出它。(这是偏离带来的未完成义务。) 2. 两个30秒检查:(a) w = 1 时的因子刻画——书是否像S2一样把1算作幂(13⁰)?(b) §5如何表述 x = 0 情形(0⁰ = 1,0^y = 0——第五部分链条通过 +1 平移和 (β) 的 d·x = 0 处理它)。
持续未做(7月24–26日,未变):L₂(x)、L₃(x) 字符串;N₁₂的子关系(提示封存在7月26日文件第十一部分);L₃的情况检查;祖先解释的证伪;全域实例问题;7月26日两个30秒拼写检查。
欠账记录——今天偿还两项:消去E(自7月以来持续欠账:第五部分已全额偿还)和素数底13(S2是使用素性的地方;底数13现在有根据,不再靠运气)。剩余:性质1 ⇒ 性质2;机械 ⇒ 算术的(Arithmetic);1930年的恰切性;1931年的一般机器形式;运算一致;从 L₆ + L₇ 得到实例化。
方法记录——定型的链条格式。 今天的格式之争(第0部分)以如今被认为适合形式材料的确定格式结束:具有目标形状和义务的目标 → 可引用定义的术语表 → 标志性步骤,每步以任务开头,每个公式逐块解析语义,每个理由引用标签——而只要数是字符串,就在数位层面解析算术。过程中得到的否定规则:不让比喻承担关键任务(展开或删除);不设背景事实块(小学级事实在使用处直接用);没有声明目的地就没有严谨;作用先于公式。本文件第五部分是参考实例。
此前研读:7月15日(第一章)、17日(答案)、19–22日(第二章)、20及23日(练习)、24日及25日续篇(第三章§1)、26日(第三章§§2–4)。本文件:第四章。