Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter III §§2–4: Arithmetization of the Axiom System, and Theorem 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 I — Why sequence numbers exist: the certificate trick
- Part II — §2 Preliminaries: begins, ends, part-of
- Part III — Finite sequences: ♯'s job, K₁₁, and what a sequence number is
- Part IV — Proposition 2: the three strings, equivalence proved (the flagged item)
- Part V — §3, conditions 1–11: arithmetizing syntax
- Part VI — Conditions 12–17: axioms, derivations, proofs, provability
- Part VIII — What was actually new today
- Part IX — The Ledger (string ↔ semantic value, complete)
- Part X — Self-Test
Study session of July 26, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter III, section II (§2 Preliminaries, §3 Arithmetization of the Syntax of P.E.) and §4 (Gödel's Incompleteness Theorem for P.E.), book pp. 30–36 · Companion to the sessions of July 15, 17, 19, 20, 21, 22, 23, and 24/25 · Character: a close reading, not an exercise session — the reader read the pages himself and asked for two things: (1) each condition's defining string together with its semantic value, with the equivalence argued rather than asserted — the flagged uncertainty being "the equivalence between Seq x and its string"; (2) organized summary notes. Part IV is the answer to (1) at its deepest point; the Ledger (Part IX) is the answer to (2) in compressed form.
The punchline of the chapter
Provability is Arithmetic; truth is not; therefore they cannot coincide. This session proved that P_E — the set of Gödel numbers of the provable sentences of P.E. — is Arithmetic (Prop. 3, the summit of the seventeen-condition tower below). Chapter II's Tarski theorem (July 24) proved that T — the set of Gödel numbers of the true sentences — is not Arithmetic. An Arithmetic set cannot equal a non-Arithmetic one, so P_E ≠ T: what is provable and what is true are different sets. And the mismatch has a forced direction — given one hypothesis: that P.E. is correct (provable ⊆ true). Under it, the sentence witnessing P_E ≠ T must lie in T \ P_E — a true sentence that is not provable. Correctness is an assumption about the system, not something proved here (a justified one for P.E., whose axioms are true and whose rules preserve truth); historically much weaker hypotheses suffice — Gödel worked from ω-consistency, and Rosser's later refinement from consistency alone — but those belong to later chapters. That is incompleteness, before any Gödel sentence is even written down; §4's Theorem 1 (Part VII) then exhibits the witness concretely as H[h̄]. Everything else in this file — B/E/P, sequence numbers, the seventeen conditions — is the engineering that makes the first half of this contrast ("provability is Arithmetic") true. The closing paragraph of Part VII restates this from the book's architecture.
How to use this document
The pages under study do one thing seventeen times: display a condition on numbers (a set or relation), give its defining string built from already-certified Arithmetic material, and move on — usually without arguing that the string and the condition are equivalent. This file supplies the missing arguments. Each condition below gets three entries: the string (transcribed exactly from the page), the semantic value (what property of what objects it defines), and why they coincide (both directions, wherever that is not immediate).
Two transcription warnings, both caught during this session, are flagged where they occur: a letterform trap in the xPy line (Part II), and two official spellings the book uses without redisplaying (Part V, marked "to confirm"). Nothing else in this file is reconstruction; every displayed string was verified against the page at magnification.
Read Parts I–VIII in order the first time. Afterwards the Ledger (Part IX) alone is the refresher, and the Self-Test (Part X) tells you whether it took. Owed items are collected in Part XI.
Part I — Why sequence numbers exist: the certificate trick
The chapter's goal, restated. Let P_E = the set of Gödel numbers of the provable formulas of P.E., and R_E = the set of Gödel numbers of the refutable ones. If these two sets are Arithmetic, the entire July 22 machinery (express the set → complement → star → diagonalize → Gödel sentence) fires with A := P̃_E, and incompleteness falls out in ten lines. §4 does exactly that (Part VIII). So the whole of §§2–3 is one long verification: P_E and R_E are Arithmetic.
The obstacle. Three definitions in the book so far are inductive: term (variables and numerals, closed under four building steps), formula (atomics, closed under three), provable (axioms, closed under two rules). An inductive definition says "reachable in finitely many steps" — and an Arithmetic condition is a formula of L_E, which has +, ·, E, ≤, =, connectives and number quantifiers, but no "finitely many steps."
The move — replace induction by a certificate. X is a term iff there exists a finite sequence of expressions, each of which is a starter or is built from earlier members, with X among the members (the book's formation sequence, p. 33). The inductive definition is traded for a single ∃ over finite sequences: every step of a construction, laid out in a row, IS the required sequence; conversely each member of such a sequence is a term by induction along it. The same trade works for formulas, and — this is the destination — for provability: a proof in a Hilbert-style system already is a finite sequence, each member an axiom or derived from earlier members. Nothing new is needed for Pf that wasn't already needed for tm.
What the trade costs. "∃ a finite sequence" quantifies over sequences, and L_E quantifies only over numbers. So finite sequences of numbers must be coded as single numbers, with three conditions Arithmetic: x codes a sequence (Seq x), n is a member of the sequence coded by y (x ∈ y), and x comes before y in the sequence coded by z (x ≺_z y). That is Proposition 2, the technical heart of the section — and §2's substring machinery (B, E, P) exists solely to prove it.
The tower, bottom to top (each floor Arithmetic because the floor below is):
∗ (concatenation, July 21) Ch. II §4, Prop. 1
→ B, E, P (begins / ends / part-of) §2, Prop. 1
→ Seq, ∈, ≺ (sequence numbers) §2, Prop. 2
→ Sb, Var, Num, R₁ (syntax atoms) §3, conditions 1–4
→ Seqt, tm (terms) conditions 5–6
→ f₀, Gen, R₂, Seqf, fm (formulas) conditions 7–11
→ A (axiomhood) condition 12 + Note
→ M.P., Der, Pf (proofs) conditions 13–15
→ P_E, R_E conditions 16–17, Prop. 3
→ Theorem 1 (incompleteness) §4, via July 22's engine
Part II — §2 Preliminaries: begins, ends, part-of
The definitions, with the book's examples (base 10 for reading comfort; everything is stated for arbitrary base b ≥ 2).
- xB_b y — "x begins y": x's base-b numeral is an initial segment of y's. 593 begins 59348; also 593 begins 593.
- xE_b y — "x ends y": x's numeral is a final segment of y's. 348 ends 59348; also 48 ends 59348; 0 ends 570, as does 70, as does 570 itself.
- xP_b y — "x is part of y": x ends some number that begins y — i.e., x's digit string occurs somewhere inside y's. 93, 934, 34 are parts of 59348; 0 is part of 5076 but not of 576.
The three strings (p. 31, transcribed exactly):
xB_b y ↔ x = y ∨ (x ≠ 0 ∧ (∃z ≤ y)(∃w ≤ y)(Pow_b(w) ∧ (x·w) ∗_b z = y))
xE_b y ↔ x = y ∨ (∃z ≤ y)(z ∗_b x = y)
xP_b y ↔ (∃z ≤ y)(zB_b y ∧ xE_b z)
Semantic account, E first (the easy one). z ∗_b x glues z's digits before x's. So "some z with z ∗ x = y" says: y's digits = (z's digits)(x's digits) — x is a final segment. Why is E immune to the leading-zero disease that will plague B? Because the piece that must stand alone as a number is the head z, and heads of canonical numerals never start with 0. The tail x is planted verbatim, zeros and all: 0 ends 570 via z = 57 (57 ∗ 0 = 57·10 + 0 = 570 — the July 21 identity x ∗ 0 = 10x doing honest work).
B — the hard one, and why. Naively x begins y iff y = x ∗ z for some z. But ∗ appends z's canonical digits, and the piece of y after x may begin with zeros — "5 begins 5007," yet no number has digit string "007." The repair is July 21's 0-pathology patch reused: split the tail into its leading zeros and the rest. x·w (w a power of b, say bʲ) plants x followed by j zeros; ∗ z then appends the zero-free remainder. 5 begins 5007: w = 100, z = 7 — (5·100) ∗ 7 = 500·10 + 7 = 5007. When the tail has no leading zeros, w = 1 = b⁰ serves: 5 begins 57 via w = 1, z = 7. The conjunct x ≠ 0 enforces the book's convention that 0 begins nothing (a "0" prefix would be a leading zero); the disjunct x = y handles the degenerate case where there is no tail at all.
P — occurrence = final-segment-of-an-initial-segment. An occurrence of x's digits inside y's can be located by cutting y right after the occurrence: the left piece z is an initial segment of y (so zB_b y — and z, being a prefix of a canonical numeral, is itself canonical), and x is a final segment of z (so xE_b z). Conversely any such z exhibits an occurrence. The cut is chosen this way round — prefix first, then x at its end — precisely so that both standalone pieces (z, and the head inside E) are prefixes of y, hence never zero-led. This is what makes "0 is part of 5076" come out true: z = 50 begins 5076, and 0 ends 50.
Reading checkpoint (caught this session). At this print size the italic B and E in the P-line are nearly identical, and the line is dangerously readable as (∃z ≤ y)(zEy ∧ xBz) — "x begins a number that ends y." For x ≠ 0 the two readings are provably equivalent (both say "x's string occurs in y's"). They split exactly at x = 0: under the wrong reading, 0Pz requires a suffix of y starting with digit 0, which no number is, so "0 is part of 5076" would be false — contradicting the book's own bracketed example and its prose definition ("x ends some number that begins y"). The example is the checksum; the correct reading is the one displayed above.
The remark the book italicizes for later. Every ∃ in these strings is written bounded — (∃z ≤ y) — though plain ∃z would prove Arithmetic-ness just as well (the witnesses z, w never exceed y, in fact are < y). The extra care is an investment: the next chapter needs these relations in the narrower class of constructive arithmetic relations, where bounds matter. Same spirit as July 19's flag: all-quantifiers-bounded = mechanically checkable.
Proposition 1. For any b ≥ 2 and n ≥ 2, the relations xB_b y, xE_b y, xP_b y, and x₁ ∗_b … ∗_b xₙ P_b y are Arithmetic. (The last via (∃z ≤ y)(x₁ ∗ … ∗ xₙ = z ∧ zP_b y).)
Notation freeze (p. 32), in force for the rest of the book: b = 13; subscripts dropped (xBy, xEy, xPy); juxtaposition means concatenation — xy is x ∗₁₃ y (no clash with multiplication, always written x·y); xP̄y means ~xPy; x₁x₂…xₙPy means x₁ ∗ … ∗ xₙ P y. From here on, a string like δ0y names the number δ ∗ 0 ∗ y — read it as digits: δ, then 0, then y's digits.
Part III — Finite sequences: ♯'s job, K₁₁, and what a sequence number is
The thirteenth symbol finally earns its keep. The alphabet's ♯ (digit δ = twelve; July 21 table) has never been used. Its job: for expressions X₁, …, Xₙ, the expression
♯X₁♯X₂♯…♯Xₙ♯
serves as the formal counterpart of the n-tuple (X₁, …, Xₙ). The elegance: a sequence of expressions is again an expression, so the one Gödel numbering already covers sequences — no second coding apparatus. The Gödel number of ♯E_{x₁}♯…♯E_{xₙ}♯ is, digit by digit,
δ x₁ δ x₂ δ … δ xₙ δ (concatenation, base 13)
and this number is called the sequence number of (x₁, …, xₙ).
K₁₁ — who may ride. K₁₁ = the numbers in whose base-13 representation the digit δ does not occur — equivalently, all digits are among the twelve digits 0–11 (hence the name). δ is the separator; a member containing δ would be indistinguishable from two members and a wall. No loss: every ♯-free expression — all numerals, variables, terms, formulas, the "meaningful" expressions — has its Gödel number in K₁₁.
The three conditions to arithmetize (p. 32):
- Seq(x) — x is the sequence number of some finite sequence of members of K₁₁.
- x ∈ y — y is a sequence number and x is a member of the coded sequence. (Not set membership — sequences have order and repetition; ∈ just ignores them.)
- x ≺_z y — z is a sequence number, x and y are members, and the first occurrence of x precedes the first occurrence of y. (The book prints z beneath the symbol; we write it as a subscript.)
Concrete anchors, since these are honest numbers:
- Sequence (0): δ0δ = digits (12, 0, 12) = 12·169 + 0 + 12 = 2040.
- Sequence (2, 3): δ2δ3δ = 12·13⁴ + 2·13³ + 12·13² + 3·13 + 12 = 349205.
- g.n.(v₁) = digits (2,6,5,3) = 5476 (Part V for why), so the one-term sequence (v₁) — the certificate below for "v₁ is a term" — is δ(2653)δ = digits (12,2,6,5,3,12) = 4,526,716. Astronomical growth for trivial content: normal, and harmless — these numbers are quantified over, never written down.
Part IV — Proposition 2: the three strings, equivalence proved (the flagged item)
Proposition 2. Each of Seq(y), x ∈ y, x ≺_z y is Arithmetic. The proof is three displayed strings (p. 32):
1. Seq x ↔ δBx ∧ δEx ∧ δ ≠ x ∧ δδP̄x ∧ (∀y ≤ x)(δ0yPx ⊃ δBy)
2. x ∈ y ↔ Seq y ∧ δxδPy ∧ δP̄x
3. x ≺_z y ↔ x ∈ z ∧ y ∈ z ∧ (∃w ≤ z)(wBz ∧ x ∈ w ∧ ~ y ∈ w)
1. Seq x — five conjuncts, five jobs
Target semantic value: x's base-13 digit string is δ a₁ δ a₂ δ … δ aₙ δ, where n ≥ 1 and each aᵢ is the canonical digit string of a number in K₁₁.
| conjunct | literal content | job |
|---|---|---|
| δBx | first digit of x is δ | opening wall present |
| δEx | last digit of x is δ | closing wall present |
| δ ≠ x | x isn't the single digit δ | kills the degenerate "one wall, no rooms" |
| δδP̄x | "δδ" occurs nowhere in x | no empty rooms: every two walls have digits between them (also kills x = δδ, the empty sequence — Seq requires n ≥ 1) |
| (∀y ≤ x)(δ0yPx ⊃ δBy) | whatever follows an occurrence of "δ0" starts with δ | no leading zeros: a room may start with digit 0 only by being exactly the one-digit room "0" |
Direction 1: a genuine sequence number satisfies the string. Let x = δa₁δ…δaₙδ, each aᵢ ∈ K₁₁ in canonical spelling. The first four conjuncts are immediate (walls at both ends; n ≥ 1 rooms; rooms nonempty since a canonical numeral has at least one digit). The fifth: suppose δ0y P x, i.e., the string "δ 0 (digits of y)" occurs in x. Rooms are δ-free, so that δ is a wall, and the 0 after it is the first digit of some room aᵢ. Canonical spellings start with 0 only when the number is 0 itself, so aᵢ = 0 and the digit after that 0 is the next wall, δ. Hence y's digits, which begin right after the 0, begin with δ — δBy. ✓
Direction 2: anything satisfying the string is a genuine sequence number. Conjuncts 1–4 force the shape: reading x's digits, δ's occur, the first digit is one, the last is one, no two are adjacent, and x has more digits than just δ — so x = δs₁δ…δsₙδ with n ≥ 1 and each sᵢ a nonempty δ-free digit string. Each sᵢ is automatically δ-free (rooms are maximal runs between walls), hence, if canonical, spells a number in K₁₁. Only canonicity — "no leading zeros unless the room is exactly 0" — is in doubt, and conjunct 5 settles it. Suppose some room is 0t with t nonempty (the illegal shape). Two cases, both caught: - t starts with a digit d ≠ 0: take y = d. Then δ0d occurs in x (wall, the bad 0, then d), so δ0yPx; but δBy fails (d is a single non-δ digit). Conjunct 5 is violated. ✓ - t starts with 0 too: take y = 0. Then δ00 occurs, i.e., δ0y with y = 0; but δB0 fails (0's string is "0"). Violated again. ✓
Conversely, when all rooms are legal, no violation is possible (Direction 1). Note the finesse in the two cases: one cannot simply take "y = the rest of the room," because if the rest itself starts with 0 it is not the canonical string of any number — the case split takes y to be a single digit, which is always a legitimate number.
Edge check, the smallest citizen. x = δ0δ = 2040 (the sequence (0)): δB, δE ✓; x ≠ δ ✓; no δδ ✓; conjunct 5: the only y with δ0y P δ0δ is y = δ itself, and δBδ holds via the x = y clause of B. Seq(2040) ✓ — the room "0" is legal, exactly as designed.
2. x ∈ y — membership, and why the third conjunct is there
Semantic value: y codes a sequence and x is one of its members. String: Seq y ∧ δxδPy ∧ δP̄x.
Forward. If x = aᵢ, then the string δaᵢδ — x flanked by its two walls — occurs in y: δxδPy. And aᵢ ∈ K₁₁ gives δP̄x. ✓
Backward — the alignment argument. Suppose δxδPy with x δ-free. The two flanking δ's of the occurrence must coincide with walls of y (all δ's in y are walls). Between two consecutive walls sits exactly one room; x's string, being δ-free, cannot stretch across a wall, so the two flanking walls are consecutive and x's string is the whole room between them — not a proper piece of a room, because the occurrence is bounded by δ on both sides while a room's interior contains none. Hence x = aᵢ for some i. ✓
Why δP̄x is not decorative. Drop it and take y = δ1δ2δ (the sequence (1,2)) and x = the number with digits 1,δ,2 (= 169 + 156 + 2 = 327). Then δxδ = δ1δ2δ = y, which certainly occurs in y — yet 327 is not a member; its "occurrence" straddles a wall. The conjunct δP̄x is precisely the no-straddling guarantee that makes the alignment argument go.
3. x ≺_z y — order via a prefix witness
Semantic value: x and y are members of z's sequence and x's first occurrence is strictly earlier than y's. String: x ∈ z ∧ y ∈ z ∧ (∃w ≤ z)(wBz ∧ x ∈ w ∧ ~y ∈ w).
The picture. A prefix of z that is itself a sequence number is exactly "the first j rooms, walls included": w = δa₁δ…δaⱼδ. The string asks for such a w containing x but not y.
Forward. Let x first occur as room i, y first occur as room k, i < k. Take w = δa₁δ…δaᵢδ. Then w's digit string is an initial segment of z's, so wBz (and w < z, so the bound ∃w ≤ z is honest); x ∈ w by construction; y ∉ w since y appears among rooms 1…i only if its first occurrence were ≤ i < k. ✓
Backward. Given such a w: x ∈ w forces Seq w (it is the first conjunct of ∈), so w is a sequence number in its own right, AND wBz makes its digits an initial segment of z's. Initial segments match digit-for-digit, so every wall of w sits on a wall of z, and w's final δ sits on some wall of z — hence w's rooms are precisely z's rooms 1…j for some j. (A prefix like δa₁δ2 that cuts mid-room fails Seq; a cut mid-room at a wall position can't happen — the digit there is δ in one string and non-δ in the other, contradicting matching.) Now x ∈ w places x's first occurrence at some room ≤ j, and y ∉ w with y ∈ z places y's first occurrence at some room > j. Strictly earlier. ✓
Strictness for free: x ≺_z x is false — any w containing x contains x.
Why "first occurrence"? Sequences may repeat members. The relation the certificate conditions actually need is "there exist members available strictly before y is required" — and first occurrences are what a prefix witness can see. The match with the informal "earlier members" definitions is argued at condition 5.
Part V — §3, conditions 1–11: arithmetizing syntax
Standing conventions of §3. E_x = the expression whose Gödel number is x (July 21). For x₁, …, xₙ ∈ K₁₁, the Gödel number of the sequence (E_{x₁}, …, E_{xₙ}) is the sequence number of (x₁, …, xₙ) — i.e., the g.n. of ♯E_{x₁}♯…♯E_{xₙ}♯. Two abbreviations (p. 33):
(∀x ∈ y)(…) for ∀x(x ∈ y ⊃ …)
(∃x,y ≺_w z)(…) for ∃x∃y(x ≺_w z ∧ y ≺_w z ∧ …)
(The first looks like an unbounded ∀ — but members never exceed their sequence number (a member's string is a proper part of the sequence's string), so it is a bounded universal in disguise: ∀x(x ∈ y ⊃ …) ⟺ (∀x ≤ y)(x ∈ y ⊃ …). One-line check, worth doing once — the book's promise "only bounded universal quantifiers" survives.)
The eight concatenation functions (p. 34). For the g.n.'s of (E_x ⊃ E_y), ~E_x, (E_x + E_y), (E_x · E_y), (E_x E E_y), E_x′, E_x = E_y, E_x ≤ E_y the book writes x imp y, neg(x), x pl y, x tim y, x exp y, s(x), x id y, x le y. All are fixed concatenation templates, hence Arithmetic. The two the book displays, against the July 21 digit table (0→1, ′→0, (→2, )→3, f→4, subscript→5, v→6, ~→7, ⊃→8, ∀→9, =→η, ≤→ε, ♯→δ):
x imp y = 2x8y3 "(", x, "⊃", y, ")"
neg(x) = 7x "~", x — no parentheses; and beware: this is 7 ∗ x,
prepend-a-digit, NOT multiplication by 7 (the book itself
adds "(i.e. 7 ∗ x)")
Two gems hiding in the others: s(x) = x ∗ 0 = 13·x — appending the accent is multiplication by 13, July 21's "successor-symbol applicator," now an official function. And since atomic formulas carry no parentheses (witness the book's unabbreviated L₆ below: ~∀vᵢ~vᵢ = t), x id y = xηy and x le y = xεy (inferred — the book doesn't redisplay these; 30-second check against Ch. II §1's official grammar owed, Part XI); likewise pl, tim, exp presumably wrap f′, f′′, f′′′ infix in parentheses, e.g. x pl y = 2x(40)y3 (same check).
The conditions, string / semantic value / equivalence:
1. Sb(x) — E_x is a (nonempty) string of subscripts: (∀y ≤ x)(yPx ⊃ 5Py). Why it works: every part of x contains the digit 5 ⟺ every digit of x is 5 — because single digits are parts, so any non-5 digit d would be a part with 5P̄d. (And x = 0 fails via y = 0: 5P̄0.) A lovely example of saying "all my digits are 5" without being able to say "digit." Delta against July 19: the alphabet's comma-like symbol (digit 5), jobless since its introduction, is revealed as the subscript-former for variables.
2. Var(x) — E_x is a variable: (∃y ≤ x)(Sb(y) ∧ x = 26y3). Semantic value: the official spelling of the i-th variable is ( v followed by i subscript-marks ) — digits 2, 6, 5…5, 3. So g.n.(v₁) = 2653₁₃ = 5476; g.n.(v₂) = 26553₁₃. The parentheses are part of the variable — that is how v₁v₂ stays parseable. The bound y ≤ x is honest: y's string is a part of x's.
3. Num(x) — E_x is a numeral: Pow₁₃(x). The July 21 payoff in one line: n̄ = 0 followed by n accents → digit 1 followed by n zeros → 13ⁿ. So "x codes a numeral" IS "x is a power of 13." (That Pow₁₃ is Arithmetic: standing debt "prime base 13," unchanged.)
4. R₁(x, y, z) — the formation relation for terms holds of (E_x, E_y, E_z): z = x pl y ∨ z = x tim y ∨ z = x exp y ∨ z = s(x). Semantic value: E_z is buildable in one step from E_x, E_y — it is (E_x + E_y), (E_x · E_y), (E_x E E_y), or E_x′. Pure template-matching on codes; the fourth disjunct is literally z = 13x.
5. Seqt(x) — x codes a formation sequence for terms:
Seq(x) ∧ (∀y ∈ x)(Var(y) ∨ Num(y) ∨ (∃z, w ≺_x y)R₁(z, w, y))
Semantic value (book's definition, p. 33): a finite sequence of expressions each of which is a variable, a numeral, or R_t-built from two earlier members. This is the certificate shape — memorize it once, it recurs verbatim twice more:
Seq(x) ∧ (∀y ∈ x)( seed(y) ∨ (∃z, w ≺_x y) rule(z, w, y) )
The index-vs-first-occurrence subtlety (the one real gap between string and informal definition). The informal definition speaks of positions: entry i is justified by entries j, k < i. The string speaks of values and first occurrences: every member-value y must be a seed or R₁-built from values first-occurring strictly before y's first occurrence. Equivalence: (⇒) in a position-justified sequence, look at any value y at its first occurrence i; its justifiers sit at positions < i, so their first occurrences are < i too — the string's demand is met. (⇐) from a string-satisfying x, the sequence read left to right is position-justified at each first occurrence, and repeats are justified by pointing left to the first occurrence. Same certificates, two bookkeepings. Note also: only Seq's members enter — and Seq confined members to K₁₁, which is why ♯-free syntax needed codes in K₁₁ in the first place.
6. tm(x) — E_x is a term: ∃y(Seqt(y) ∧ x ∈ y). The certificate cashed: term = member of some formation sequence for terms. The ∃y is unbounded — necessarily so at this price point (certificates dwarf their conclusions: y = 4,526,716 certifies x = 5476 above), and harmlessly so — Arithmetic-ness never required bounded ∃. Only the ∀'s had to stay bounded.
7. f₀(x) — E_x is an atomic formula: (∃y ≤ x)(∃z ≤ x)(tm(y) ∧ tm(z) ∧ (x = y id z ∨ x = y le z)). Atomic = t₁ = t₂ or t₁ ≤ t₂, t₁ and t₂ terms. Bounds honest (parts again).
8. Gen(x, y) — E_y = ∀vᵢ E_x for some variable vᵢ: (∃z ≤ y)(Var(z) ∧ y = 9zx). Digit 9 = ∀, then the variable, then the body — note there are no added parentheses, and the variable brings its own.
9. R₂(x, y, z) — the formation relation for formulas holds: z = x imp y ∨ z = neg(x) ∨ Gen(x, z). E_z is (E_x ⊃ E_y), ~E_x, or ∀vᵢE_x. (y idles in the second and third disjuncts — see condition 14 for the same idiom.)
10. Seqf(x) — x codes a formation sequence for formulas:
Seq(x) ∧ (∀y ∈ x)(f₀(y) ∨ (∃z, w ≺_x y)R₂(z, w, y))
The certificate shape, second instantiation — seeds are now atomic formulas, the rule is R₂.
11. fm(x) — E_x is a formula: ∃y(Seqf(y) ∧ x ∈ y).
Part VI — Conditions 12–17: axioms, derivations, proofs, provability
12. A(x) — E_x is an axiom of P.E.: the disjunction of nineteen conditions L₁(x), …, L₇(x), N₁(x), …, N₁₂(x), one per scheme of the July 24 catalogue. The book's Note on the Axioms gives sample cases:
-
Group I sample, L₁(x). E_x is an instance of (F ⊃ (G ⊃ F)) iff
(∃y ≤ x)(∃z ≤ x)(fm(y) ∧ fm(z) ∧ x = y imp (z imp y))
Why the bounds are enough: the instance's F and G are subexpressions of E_x, and a part's code never exceeds the whole's (shorter or equal digit string). Scheme-hood has become template-matching with two formula-typed holes — this is what July 24 called "recognizable by shape alone," now literal. L₂(x), L₃(x): same idea, left to the reader (owed, Part XI).
-
Group II sample, L₄(x). Let φ(y, z, w) = the g.n. of ∀E_y(E_z ⊃ E_w) ⊃ (∀E_y E_z ⊃ ∀E_y E_w) — a fixed concatenation template in imp and 9-prefixing, hence Arithmetic. Then
L₄(x) ⟺ (∃y ≤ x)(∃z ≤ x)(∃w ≤ x)(Var(y) ∧ fm(z) ∧ fm(w) ∧ x = φ(y, z, w))
Note which July 24/25 fact is being spent: the Kalish–Montague schemes have occurrence-scan side conditions, not freeness side conditions — L₅'s "vᵢ does not occur in F" is the substring check yP̄(code of F)-shaped, one P away from Arithmetic. Freeness would have needed scope-parsing; the axioms were engineered so §3 never parses a scope. (The book: L₆ was displayed with ∃ as an abbreviation; unabbreviated it is the scheme ~∀vᵢ~vᵢ = t.)
-
Group III (N₁–N₁₁). Each scheme has exactly one axiom, so Nᵢ(x) is simply x = gᵢ, gᵢ the g.n. of that one formula — equality with a constant, the most Arithmetic condition there is.
-
Group IV (N₁₂, induction). The book: one first verifies that the relation "E_x is a formula and E_y is one of the formulas E_x[v₁′]" is Arithmetic in (x, y) — left to the reader (owed, with a hint, Part XI) — after which N₁₂(x) is obvious. Delta against July 25's Part XI: E_x[v₁′] is the double wrapper ∀vᵢ(vᵢ = v₁′ ⊃ ∀v₁(v₁ = vᵢ ⊃ E_x)), and the plural "one of the formulas" is the fresh-variable freedom — one bracket-string per admissible vᵢ, so the arithmetized version is a relation, not a function. The wrapper was chosen over surgical substitution precisely for this moment: its code is a concatenation template around x with x riding as an unopened block (July 22's r(x, y) was the same shape), while genuine substitution would demand interior digit-surgery.
13. M.P.(x, y, z) — E_z is derivable from E_x and E_y by Rule 1 (modus ponens): y = x imp z. One equation. Semantic value: the major premise E_y is the string (E_x ⊃ E_z) — derivability-in-one-step is a shape fact about y, nothing more. (From F and (F ⊃ G), get G: x plays F, z plays G.)
14. Der(x, y, z) — E_z is derivable from E_x, E_y by Rule 1, or from E_x by Rule 2: M.P.(x, y, z) ∨ Gen(x, z). In the Gen disjunct y idles — Rule 2 (generalization: from F get ∀vᵢF) has one premise. The two-premise signature is kept uniform so condition 15 can demand a single pair (z, w) every time; a Rule-2 line just lets the second citation be anything earlier (z itself will do).
15. Pf(x) — x codes a proof in P.E.:
Seq(x) ∧ (∀y ∈ x)(A(y) ∨ (∃z, w ≺_x y)Der(z, w, y))
The certificate shape, third and final instantiation — seeds: axioms; rule: Der. Semantic value: a finite sequence of formulas, each an axiom or derivable from earlier members — the textbook definition of a Hilbert-style proof, verbatim. This is the line the whole section existed to write; note that after conditions 1–14, it cost nothing new. Two glosses: - Formulas only, though nobody checks fm: by induction along the sequence — axioms are formulas (each of the 19 disjuncts builds fm in or names a formula); if E_w = (E_z ⊃ E_y) and E_z, E_w are formulas, unique readability makes E_y one; ∀vᵢE_z likewise. The string needn't police what the rules can't produce. - First-occurrence bookkeeping: exactly as at condition 5 — every standard proof qualifies as written, and every qualifying x reads off as a standard proof.
16. P_E(x) — E_x is provable in P.E.: ∃y(Pf(y) ∧ x ∈ y). Provable = member of some proof — no "last line" clause, and none is needed: the prefix of a proof up through any member's first occurrence is itself a proof (all its members' justifiers first-occur inside it), so membership and being-the-last-line certify the same set. Unbounded ∃, same license as condition 6.
17. R_E(x) — E_x is refutable in P.E.: P_E(neg(x)). Refutable = negation provable (the Ch. I definition). One composition — July 20's "inverse image of an Arithmetic set under an Arithmetic function is Arithmetic," with f = neg. And once more: neg(x) = 7x is prepend the digit 7, i.e. 7·13^ℓ(x) + x — misread it as multiplication and nothing downstream survives.
Proposition 3. All the conditions (1)–(17) are Arithmetic. — "This completes our arithmetization of the syntax of P.E."
## Part VII — §4: the harvest — Theorem 1
The book's proof, as a citation chain into owned material (July 22 names in brackets):
- P_E and R_E are Arithmetic (Prop. 3) — so take formulas P(v₁) and R(v₁) expressing them in L_E.
- ~P(v₁) expresses the complement P̃_E [complement closure — trivial direction of July 20's toolkit].
- By the Lemma to Theorem 1 of the last chapter [Lemma 1, July 22: A Arithmetic ⇒ A* Arithmetic, via the wrapper r], there is H(v₁) expressing (P̃_E)*.
- Its diagonalization H[h̄] is a Gödel sentence for P̃_E [July 22, Theorem 1's proof]: H[h̄] is true ⟺ g.n.(H[h̄]) ∈ P̃_E ⟺ H[h̄] is not provable in P.E.
- P.E. is a correct system (provable ⇒ true; the July 24 sense). If H[h̄] were provable it would be true, hence unprovable — contradiction. So H[h̄] is unprovable; by the biconditional, true.
- Then ~H[h̄] is false, hence (correctness again) unprovable — so H[h̄] is not refutable either. A sentence neither provable nor refutable: P.E. is incomplete. (Theorem 1.)
The dual route, same engine: R_E Arithmetic ⇒ R_E* Arithmetic ⇒ K(v₁) expressing it ⇒ K[k̄] a Gödel sentence for R_E: true ⟺ refutable. Were it true it would be refutable, so ~K[k̄] provable, so ~K[k̄] true, so K[k̄] false — contradiction. So K[k̄] is false, hence not refutable, and (false + correctness) not provable. Same undecided sentence phenomenon from the refutability side. Note the July 23 symmetry reborn: H[h̄] is a true sentence asserting its own unprovability; K[k̄] a false one asserting its own refutability.
Aerial one-liner (not the book's words, but the book's architecture). Chapter II proved the set of true sentences is not expressible (Tarski). This chapter proved the set of provable ones is. Whatever is expressible differs somewhere from whatever isn't — and under correctness (provable ⊆ true) the difference can only be a true, unprovable sentence. The arithmetization had to succeed for provability exactly where it had to fail for truth; incompleteness is the daylight between.
Part VIII — What was actually new today
Strip the seventeen conditions to their ideas and the section bought exactly three:
- Substring relations are Arithmetic (B, E, P) — bought with July 21's ∗ plus one leading-zeros patch.
- Finite sequences of numbers are single numbers, Arithmetic-ly (Seq, ∈, ≺) — bought with a reserved separator digit and (1).
-
Inductive definitions convert to ∃-certificate definitions — bought with (2), then spent three times (terms, formulas, proofs) on one reusable shape:
Seq(x) ∧ (∀y ∈ x)( seed(y) ∨ (∃z, w ≺_x y) rule(z, w, y) )
Everything else is template bookkeeping. And the design debts of earlier sessions all fall due here, on schedule: the comma symbol (July 19) exists for Var; accent→0 (July 21) makes Num one Pow; x ∗ 0 = 13x (July 21's pathology) is s(x); occurrence-not-freeness side conditions (July 25) keep A(x) at concatenation-level; the wrapper (July 22/25) makes N₁₂'s brackets a template instead of surgery; and the ♯ symbol, jobless for a week, was the sequence machinery all along.
Part IX — The Ledger (string ↔ semantic value, complete)
Notation: juxtaposition = ∗₁₃ concatenation; digits per the July 21 table; P̄ = not-part-of; ≺_x = earlier-first-occurrence-in-x.
| # | condition | defining string | semantic value |
|---|---|---|---|
| — | xBy | x = y ∨ (x ≠ 0 ∧ (∃z,w ≤ y)(Pow₁₃(w) ∧ (x·w) ∗ z = y)) | x's digits start y's (w = shift past the tail's leading zeros) |
| — | xEy | x = y ∨ (∃z ≤ y)(z ∗ x = y) | x's digits end y's |
| — | xPy | (∃z ≤ y)(zBy ∧ xEz) | x's digits occur in y's (x ends a beginner of y) |
| — | Seq x | δBx ∧ δEx ∧ δ ≠ x ∧ δδP̄x ∧ (∀y ≤ x)(δ0yPx ⊃ δBy) | x = δa₁δ…δaₙδ, n ≥ 1, aᵢ ∈ K₁₁ canonical |
| — | x ∈ y | Seq y ∧ δxδPy ∧ δP̄x | x is a member of y's sequence |
| — | x ≺_z y | x ∈ z ∧ y ∈ z ∧ (∃w ≤ z)(wBz ∧ x ∈ w ∧ ~y ∈ w) | x's first occurrence precedes y's (w = prefix through x) |
| 1 | Sb(x) | (∀y ≤ x)(yPx ⊃ 5Py) | E_x is a string of subscripts (all digits 5) |
| 2 | Var(x) | (∃y ≤ x)(Sb(y) ∧ x = 26y3) | E_x is a variable ( v subscripts ) |
| 3 | Num(x) | Pow₁₃(x) | E_x is a numeral (g.n.(n̄) = 13ⁿ) |
| 4 | R₁(x,y,z) | z = x pl y ∨ z = x tim y ∨ z = x exp y ∨ z = s(x) | E_z one-step buildable from E_x, E_y (term rules) |
| 5 | Seqt(x) | Seq(x) ∧ (∀y ∈ x)(Var(y) ∨ Num(y) ∨ (∃z,w ≺_x y)R₁(z,w,y)) | x codes a formation sequence for terms |
| 6 | tm(x) | ∃y(Seqt(y) ∧ x ∈ y) | E_x is a term |
| 7 | f₀(x) | (∃y,z ≤ x)(tm(y) ∧ tm(z) ∧ (x = y id z ∨ x = y le z)) | E_x is an atomic formula |
| 8 | Gen(x,y) | (∃z ≤ y)(Var(z) ∧ y = 9zx) | E_y = ∀vᵢE_x |
| 9 | R₂(x,y,z) | z = x imp y ∨ z = neg(x) ∨ Gen(x,z) | E_z one-step buildable (formula rules) |
| 10 | Seqf(x) | Seq(x) ∧ (∀y ∈ x)(f₀(y) ∨ (∃z,w ≺_x y)R₂(z,w,y)) | x codes a formation sequence for formulas |
| 11 | fm(x) | ∃y(Seqf(y) ∧ x ∈ y) | E_x is a formula |
| 12 | A(x) | L₁(x) ∨ … ∨ L₇(x) ∨ N₁(x) ∨ … ∨ N₁₂(x) | E_x is an axiom (19 templates; L₁ shown, Group III: x = gᵢ) |
| 13 | M.P.(x,y,z) | y = x imp z | E_z follows from E_x, E_y by modus ponens |
| 14 | Der(x,y,z) | M.P.(x,y,z) ∨ Gen(x,z) | E_z follows from E_x (and maybe E_y) by Rule 1 or 2 |
| 15 | Pf(x) | Seq(x) ∧ (∀y ∈ x)(A(y) ∨ (∃z,w ≺_x y)Der(z,w,y)) | x codes a proof |
| 16 | P_E(x) | ∃y(Pf(y) ∧ x ∈ y) | E_x is provable |
| 17 | R_E(x) | P_E(neg(x)) | E_x is refutable |
Distinctions Ledger (confusions of the day → one-line resolutions):
| raised | resolution |
|---|---|
| "Equivalence between Seq x and its string?" | Five conjuncts = walls at both ends + at least one nonempty room + no leading zeros; both directions in Part IV, the only finesse being single-digit witnesses in the leading-zero cases. |
| δ0y, δxδ, 26y3, 7x look like arithmetic | They are concatenations: juxtaposition = ∗₁₃ from p. 32 on. neg(x) = 7x is prepend-7, not ×7. |
| Why δP̄x inside x ∈ y? | Without it, δxδPy can straddle walls: x = (1δ2) "occurs" in δ1δ2δ without being a member. |
| xPy: begins-an-ender or ends-a-beginner? | Ends-a-beginner: (∃z ≤ y)(zBy ∧ xEz). The italic B/E transpose easily; checksum: 0 is part of 5076 — true only on this reading. |
| ≺ uses first occurrences, definitions use positions | Same certificates: justify each value at its first occurrence; repeats point left. |
| (∀y ∈ x) looks unbounded | Members ≤ their sequence number, so it's (∀y ≤ x)(y ∈ x ⊃ …) in disguise; the bounded-∀ promise holds. |
| Why is ∃y in tm, fm, P_E allowed unbounded? | Arithmetic-ness never restricted ∃; only ∀ must stay bounded (for the next chapter's constructive class). Certificates outgrow conclusions, so no cheap bound exists anyway. |
| "One of the formulas E_x[v₁′]" — why plural? | One bracket-string per choice of fresh vᵢ; arithmetized as a relation. The wrapper keeps x an unopened block — that's why brackets, not substitution, were the axiom's notation. |
Part X — Self-Test
Do these cold; answers follow each.
1. Why does Seq x need δδP̄x — what two illegal x's does it kill?
Answer
Empty rooms: without it δa₁δδa₂δ would code a "sequence" with a memberless slot (no number has an empty digit string), and x = δδ would code the empty sequence, which Seq excludes (n ≥ 1).
2. Parse the fifth conjunct of Seq and show how it kills x = δ05δ (room "05").
Answer
(∀y ≤ x)(δ0yPx ⊃ δBy): anything following an occurrence of "δ0" must start with δ. Take y = 5: δ05 occurs in x, so δ0yPx holds; but δB5 is false. Conjunct violated, Seq x false. (For room "00…": take y = 0; δB0 false.)
3. Compute the sequence number of the one-term sequence (0), and verify each Seq conjunct on it.
Answer
δ0δ = 12·169 + 0·13 + 12 = 2040. δB ✓, δE ✓, ≠ δ ✓, no δδ (the 0 separates) ✓, fifth conjunct: only y = δ has δ0y P x, and δBδ holds via B's x = y clause ✓.
4. Give y and x with δxδPy true, x not a member of y's sequence — and name the conjunct that saves ∈.
Answer
y = δ1δ2δ (sequence (1,2)), x = digits (1, δ, 2) = 327: δxδ is y itself. Saved by δP̄x — members must be δ-free, so straddling occurrences are barred.
5. In x ≺_z y, why must the witness w be a sequence number, and where does the string demand it?
Answer
Demanded implicitly by x ∈ w (whose first conjunct is Seq w). It forces w to be a wall-aligned prefix — whole rooms only — so "x ∈ w ∧ y ∉ w" means "x among the first j members, y not," i.e., first-occurrence order.
6. A Rule-2 (generalization) line in a proof has one premise. How does it satisfy Pf's demand for two earlier members z, w?
Answer
Der(z, w, y) = M.P.(z,w,y) ∨ Gen(z,y); in the Gen disjunct w idles, and the abbreviation (∃z,w ≺_x y) only requires w to be some earlier member — take w = z.
7. Why does P_E need no "last line of the proof" clause?
Answer
Every member of a proof is provable: truncate at its first occurrence — the prefix is itself a proof (all justifiers first-occur within it). Membership and last-line-hood certify the same set.
8. What number is s(x), and which July 21 fact is it?
Answer
s(x) = x ∗ 0 = 13x — appending the accent (digit 0) is one digit-slot, i.e. ×13: the pathology-turned-successor-applicator.
9. State the certificate shape once, and its three instantiations.
Answer
Seq(x) ∧ (∀y ∈ x)(seed(y) ∨ (∃z,w ≺_x y)rule(z,w,y)). Seeds/rule = Var-or-Num/R₁ (Seqt); f₀/R₂ (Seqf); A/Der (Pf).
10. The aerial one-liner: derive incompleteness from "truth is not Arithmetic" + "P_E is Arithmetic" + correctness.
Answer
P_E is expressible, the truth set isn't, so they differ on some sentence-code. Correctness rules out provable-but-false, so the difference is a true, unprovable sentence — incompleteness. (The book's §4 route instead builds the witness explicitly: H[h̄] via the Gödel-sentence machinery.)
## Part XI — Position, owed items, debts
Position: Chapter III pp. 30–36 read. Section II (arithmetization) and §4 (Theorem 1) — the chapter's first incompleteness proof is complete. The book continues (ω-consistency/Rosser-style refinements and the abstract forms, per the table of contents) from p. 37.
Owed by the reader — new today (all "left to the reader" by the book, p. 35–36): 1. L₂(x) and L₃(x): write the strings on the L₁ model. (Two-minute template drills.) 2. N₁₂'s sub-relation: show "fm(x) and E_y is one of the formulas E_x[v₁′]" is Arithmetic in (x, y). Hint kept sealed until attempted: the bracket is a concatenation template around the block x; freshness of vᵢ is a substring condition (zP̄x-shaped); g.n.(v₁) = 5476, g.n.(v₁′) = s(5476) = 71188; imp, id, 9-prefixing assemble the rest. 3. Two 30-second book checks: (a) Ch. II §1's official spelling of + · E in terms — confirms the inferred pl/tim/exp and id/le templates of Part V; (b) the one-liner that (∀x ∈ y) is a bounded universal in disguise.
Owed, standing (July 24/25): L₃ case-check; the ancestor-interpretation falsification of (v₁ ≤ v₂ ∨ v₂ ≤ v₁); the whole-domain instance question.
Debt register, unchanged plus none retired: E-elimination; prime base 13 (now load-bearing under Num); property 1 ⇒ property 2; mechanical ⇒ Arithmetic; adequacy 1930; general machine form of 1931; operation-agreement; instantiation from L₆ + L₇.
Method note. Today's format — string / semantic value / both-directions argument, with the reader's flagged item (Seq) taken deepest — fit a reading-session request well; the two OCR-level traps (the P-line letterforms, neg's 7x) confirm the July 25 lesson that holding the recap against the page's exact characters is where errors get caught, in both directions.
Previous sessions: July 15 (Ch. 1), 17 (answers), 19–22 (Ch. II), 20 & 23 (exercises), 24 with continuations of 25 (Ch. III §1). This file: Ch. III §§2–4.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月26日研读 · 斯穆里安《哥德尔不完备性定理》,第三章第二部分(§2预备知识、§3 P.E.句法的算术化)及§4(P.E.的哥德尔不完备性定理),书第30–36页 · 与7月15、17、19、20、21、22、23及24/25日研读配套 · 性质:细读,而非练习课——读者亲自读了这些页面,要求两件事:(1) 每个条件的定义字符串及其语义值,要论证等价而非只作断言——标记的不确定之处是“Seq x 与其字符串之间的等价”;(2) 有组织的总结笔记。第四部分在最深处回应(1);区分表(第九部分)以压缩形式回应(2)。
本章的关键结论
可证性是算术的(Arithmetic);真理不是;因此两者不能重合。 本次研读证明,P_E——P.E.可证语句的哥德尔数集——是算术的(命题3,下方十七条件塔的顶峰)。第二章的塔尔斯基定理(7月24日)证明,T——真语句的哥德尔数集——不是算术的。一个算术集不能等于一个非算术集,所以 P_E ≠ T:可证者与真者是不同集合。 而不匹配的方向是被强制的——给定一个假设:P.E. 正确(可证 ⊆ 真)。在此假设下,见证 P_E ≠ T 的语句必须位于 T \ P_E——一个真却不可证的语句。正确性是关于系统的假设,不是在这里证明的东西(对 P.E. 是有理由的,因为其公理为真,规则保持真);历史上弱得多的假设就足够——哥德尔从 ω‑一致性出发,罗瑟后来的改进仅需一致性——但那些属于后面章节。还没写下任何哥德尔语句,不完备性就已出现;§4的定理1(第七部分)随后具体给出见证 H[h̄]。本文件其他一切——B/E/P、序列数、十七个条件——都是使这一对照的前半(“可证性是算术的”)成立的工程。第七部分末段从书的架构重新陈述这一点。
如何使用本文
所读页面把同一件事做了十七遍:展示一个关于数的条件(集合或关系),给出用已确认为算术的材料构成的定义字符串,然后继续——通常不论证字符串与条件等价。本文件补上缺失的论证。下面每个条件都有三项:字符串(从页面精确转录)、语义值(它定义什么对象的什么性质),以及两者为何重合(凡非直接显然处,都说明两个方向)。
两项转录警告,均在本次发现,已在相应处标记:xPy 一行的字形陷阱(第二部分),以及书中使用却不重新展示的两种正式拼写(第五部分,标记“待确认”)。本文件其他内容都不是重构;每个展示的字符串都在放大后对照页面核验。
第一次按顺序读第一至八部分。之后单看区分表(第九部分)即可复习,自测(第十部分)检验是否掌握。待做事项集中在第十一部分。
第一部分——为什么需要序列数:证书技巧
重述本章目标。 令 P_E = P.E.中可证公式的哥德尔数集,R_E = 可反驳公式的哥德尔数集。若这两个集合是算术的,7月22日的整套机制(表达集合 → 取补 → 加星 → 对角化 → 哥德尔语句)就以 A := P̃_E 启动,不完备性十行内得出。§4恰好这样做(第八部分)。因此整个§§2–3就是一个漫长验证:P_E 与 R_E 是算术的。
障碍。 书中到目前为止的三个定义都是归纳的:项(变量和数码,在四种构造步骤下封闭)、公式(原子式,在三种构造下封闭)、可证(公理,在两条规则下封闭)。归纳定义说“在有限步内可达”——而算术条件是 L_E 的公式,含有 +、·、E、≤、=、联结词和数的量词,却没有“有限步”。
这一步——用证书替代归纳。 X 是项,当且仅当存在一个表达式有限序列,其中每个表达式是起始项或由先前成员构成,且 X 在成员中(书中的形成序列,第33页)。归纳定义被换成一个对有限序列的 ∃:把构造每一步排成一列,就是所需序列;反过来,沿这种序列归纳,每个成员都是项。同样的交换适用于公式,以及——这才是目的地——可证性:希尔伯特式系统中的证明本来就是有限序列,每个成员是公理或从先前成员推出。Pf 不需要任何 tm 尚未需要的新东西。
交换的代价。 “∃一个有限序列”量化的是序列,L_E 却只量化数。所以数的有限序列必须编码为单个数,并使三个条件成为算术的:x 编码一个序列(Seq x)、n 是 y 编码的序列的成员(x ∈ y),以及在 z 编码的序列中,x 位于 y 之前(x ≺_z y)。这就是命题2,本节技术核心——§2的子串机制(B、E、P)只为证明它而存在。
自底向上的塔(每层是算术的,因为下一层是):
∗(连接,7月21日) 第二章§4,命题1
→ B、E、P(开头/结尾/部分) §2,命题1
→ Seq、∈、≺(序列数) §2,命题2
→ Sb、Var、Num、R₁(句法原子) §3,条件1–4
→ Seqt、tm(项) 条件5–6
→ f₀、Gen、R₂、Seqf、fm(公式) 条件7–11
→ A(公理资格) 条件12 + 注
→ M.P.、Der、Pf(证明) 条件13–15
→ P_E、R_E 条件16–17,命题3
→ 定理1(不完备性) §4,经7月22日的引擎
第二部分——§2预备知识:开头、结尾、部分
定义及书中例子(用十进制方便阅读;一切陈述适用于任意底 b ≥ 2)。
- xB_b y——“x 是 y 的开头”:x 的 b 进制数码是 y 的初始段。593 是59348的开头;593也是593的开头。
- xE_b y——“x 是 y 的结尾”:x 的数码是 y 的末尾段。348 是59348的结尾;48也是59348的结尾;0是570的结尾,70也是,570自身也是。
- xP_b y——“x 是 y 的部分”:x 是某个作为 y 开头的数的结尾——即 x 的数位字符串出现在 y 内部某处。93、934、34是59348的部分;0是5076的部分,却不是576的部分。
三个字符串(第31页,精确转录):
xB_b y ↔ x = y ∨ (x ≠ 0 ∧ (∃z ≤ y)(∃w ≤ y)(Pow_b(w) ∧ (x·w) ∗_b z = y))
xE_b y ↔ x = y ∨ (∃z ≤ y)(z ∗_b x = y)
xP_b y ↔ (∃z ≤ y)(zB_b y ∧ xE_b z)
语义说明,先讲较简单的 E。 z ∗_b x 将 z 的数位粘在 x 前面。所以“存在 z 使 z ∗ x = y”说:y 的数位 = (z的数位)(x的数位)——x 是末尾段。为什么 E 不受将困扰 B 的前导零病症影响?因为必须独立作为数的部分是头部 z,而规范数码的头部从不以0开头。尾部 x 原样植入,包括其中的零:0是570的结尾,取 z = 57(57 ∗ 0 = 57·10 + 0 = 570——7月21日的恒等式 x ∗ 0 = 10x 在切实工作)。
B——困难者,及其原因。 朴素地说,x 是 y 的开头,当且仅当存在 z 使 y = x ∗ z。但 ∗ 添加的是 z 的规范数位,而 y 中 x 后面的部分可能以零开头——“5是5007的开头”,却没有哪个数的数位字符串是“007”。修补就是复用7月21日的0病症补丁:把尾部拆成前导零与剩余部分。x·w(w 为 b 的幂,比如 bʲ)植入 x 后接 j 个零;∗ z 再添上无前导零的余部。5是5007的开头:w = 100、z = 7——(5·100) ∗ 7 = 500·10 + 7 = 5007。尾部没有前导零时,w = 1 = b⁰ 可用:5是57的开头,取 w = 1、z = 7。合取项 x ≠ 0 实施书的约定:0不是任何东西的开头(“0”前缀会成为前导零);析取项 x = y 处理根本没有尾部的退化情形。
P——出现 = 初始段的末尾段。 x 的数位在 y 内的一次出现,可以通过在它刚结束处切开 y 来定位:左边部分 z 是 y 的初始段(所以 zB_b y——z 作为规范数码的前缀,自身也规范),而 x 是 z 的末尾段(所以 xE_b z)。反过来,任何这样的 z 都展示一次出现。之所以如此选择切法——先取前缀,再取其末尾的 x——恰为使两个独立部分(z,以及 E 内的头部)都是 y 的前缀,从不以零开头。这使“0是5076的部分”为真:z = 50是5076的开头,0是50的结尾。
阅读检查点(本次发现)。 这种印刷大小下,P行中的斜体 B 与 E 几乎相同,很容易危险地读成 (∃z ≤ y)(zEy ∧ xBz)——“x 是某个作为 y 结尾的数的开头”。对 x ≠ 0,两种读法可证明等价(都说“x 的字符串出现在 y 内”)。它们恰在 x = 0 处分开:错误读法下,0Pz 要求 y 有一个以数位0开头的后缀,而没有数是这样的,所以“0是5076的部分”会为假——与书自己的括号例子及文字定义(“x 是某个作为 y 开头的数的结尾”)矛盾。例子是校验和;正确读法就是上面展示的。
书为后文以斜体强调的说明。 这些字符串中的每个 ∃ 都写成有界的——(∃z ≤ y)——尽管普通 ∃z 同样可以证明算术性(见证 z、w 从不超过 y,实际上 < y)。额外的谨慎是一项投资:下一章需要这些关系属于更窄的构造性算术关系类,界限在那里很重要。与7月19日的标记同一精神:所有量词有界 = 可机械检查。
命题1。 对任意 b ≥ 2 和 n ≥ 2,关系 xB_b y、xE_b y、xP_b y 和 x₁ ∗_b … ∗_b xₙ P_b y 都是算术的。(最后一个经 (∃z ≤ y)(x₁ ∗ … ∗ xₙ = z ∧ zP_b y) 得到。)
符号固定(第32页),此后全书生效: b = 13;省略下标(xBy、xEy、xPy);并置表示连接——xy 是 x ∗₁₃ y(不与乘法冲突,乘法始终写作 x·y);xP̄y 表示 ~xPy;x₁x₂…xₙPy 表示 x₁ ∗ … ∗ xₙ P y。从此像 δ0y 的字符串命名的是数 δ ∗ 0 ∗ y——把它读作数位:δ,然后0,再接 y 的数位。
第三部分——有限序列:♯的任务、K₁₁,以及什么是序列数
第十三个符号终于发挥价值。 字母表中的 ♯(数位 δ = 十二;7月21日表)一直没用过。它的任务:对表达式 X₁, …, Xₙ,表达式
♯X₁♯X₂♯…♯Xₙ♯
充当n元组 (X₁, …, Xₙ) 的形式对应物。巧妙之处:表达式序列又是一个表达式,所以已有的同一个哥德尔编码已经覆盖序列——不需要第二套编码装置。♯E_{x₁}♯…♯E_{xₙ}♯ 的哥德尔数逐位是
δ x₁ δ x₂ δ … δ xₙ δ (连接,十三进制)
这个数称为 (x₁, …, xₙ) 的序列数。
K₁₁——谁能搭乘。 K₁₁ = 十三进制表示中不出现数位 δ 的数——等价地,所有数位都属于0–11这十二个数位(名称由此来)。δ 是分隔符;含 δ 的成员会与两个成员加一道墙混淆。没有损失:每个不含 ♯ 的表达式——所有数码、变量、项、公式、“有意义”的表达式——其哥德尔数都在 K₁₁ 中。
要算术化的三个条件(第32页):
- Seq(x)——x 是某个 K₁₁ 成员的有限序列的序列数。
- x ∈ y——y 是序列数,且 x 是所编码序列的一个成员。(不是集合成员关系——序列有顺序和重复;∈ 只是忽略它们。)
- x ≺_z y——z 是序列数,x、y 是成员,且 x 的首次出现先于 y 的首次出现。(书把 z 印在符号下;我们写作下标。)
具体锚点,因为它们确实是数:
- 序列 (0):δ0δ = 数位 (12, 0, 12) = 12·169 + 0 + 12 = 2040。
- 序列 (2, 3):δ2δ3δ = 12·13⁴ + 2·13³ + 12·13² + 3·13 + 12 = 349205。
- g.n.(v₁) = 数位 (2,6,5,3) = 5476(原因见第五部分),所以单项序列 (v₁)——下面“v₁是项”的证书——是 δ(2653)δ = 数位 (12,2,6,5,3,12) = 4,526,716。微不足道的内容带来天文式增长:正常且无害——这些数被量化,从不写出来。
第四部分——命题2:三个字符串,证明等价(标记事项)
命题2。 Seq(y)、x ∈ y、x ≺_z y 都是算术的。证明是三个展示的字符串(第32页):
1. Seq x ↔ δBx ∧ δEx ∧ δ ≠ x ∧ δδP̄x ∧ (∀y ≤ x)(δ0yPx ⊃ δBy)
2. x ∈ y ↔ Seq y ∧ δxδPy ∧ δP̄x
3. x ≺_z y ↔ x ∈ z ∧ y ∈ z ∧ (∃w ≤ z)(wBz ∧ x ∈ w ∧ ~ y ∈ w)
1. Seq x——五个合取项,五项任务
目标语义值:x 的十三进制数位字符串是 δ a₁ δ a₂ δ … δ aₙ δ,其中 n ≥ 1,每个 aᵢ 都是 K₁₁ 中一个数的规范数位字符串。
| 合取项 | 字面内容 | 任务 |
|---|---|---|
| δBx | x 首位是 δ | 有开头的墙 |
| δEx | x 末位是 δ | 有末尾的墙 |
| δ ≠ x | x 不是单个数位 δ | 排除“一堵墙,没有房间”的退化情形 |
| δδP̄x | “δδ”在 x 中任何地方都不出现 | 没有空房间:任意两堵墙间都有数位(也排除 x = δδ,即空序列——Seq 要求 n ≥ 1) |
| (∀y ≤ x)(δ0yPx ⊃ δBy) | “δ0”一次出现之后的东西都以 δ 开头 | 无前导零:房间只有恰为单数位房间“0”时才可以以0开头 |
方向1:真正的序列数满足字符串。 令 x = δa₁δ…δaₙδ,每个 aᵢ ∈ K₁₁,采用规范拼写。前四个合取项直接成立(两端有墙;n ≥ 1 个房间;规范数码至少一位,所以房间非空)。第五个:假设 δ0y P x,即字符串“δ 0 (y的数位)”出现在 x 中。房间不含 δ,所以那个 δ 是墙,其后的0是某个房间 aᵢ 的首位。规范拼写只有数本身是0时才以0开头,所以 aᵢ = 0,那个0后面的一位就是下一堵墙 δ。因此 y 的数位紧接0之后开始,故以 δ 开头——δBy。✓
方向2:满足字符串的任何东西都是真正的序列数。 合取项1–4强制了形状:读取 x 的数位,δ出现,首位是它,末位也是它,没有两个相邻,且 x 不仅仅一个 δ——所以 x = δs₁δ…δsₙδ,其中 n ≥ 1,每个 sᵢ 是非空且不含 δ 的数位字符串。每个 sᵢ 自动不含 δ(房间是墙间的最大连续段),因此,若规范,就拼出 K₁₁ 中的数。唯一疑问是规范性——“没有前导零,除非房间恰为0”——合取项5解决它。假设某个房间为 0t,t 非空(非法形状)。分两种情况,都能捕获: - t 以数位 d ≠ 0 开头:取 y = d。则 δ0d 出现在 x 中(墙、坏的0、再接d),所以 δ0yPx;但 δBy 失败(d 是单个非δ数位)。违反合取项5。✓ - t 也以0开头:取 y = 0。则出现 δ00,即 y = 0 时的 δ0y;但 δB0 失败(0的字符串是“0”)。再次违反。✓
反过来,所有房间合法时,不可能违反(方向1)。注意两种情况的精巧处:不能直接取“y = 房间剩余部分”,因为若剩余部分也以0开头,它就不是任何数的规范字符串——分类取 y 为单个数位,它始终是合法的数。
边界检查,最小公民。 x = δ0δ = 2040(序列 (0)):δB、δE ✓;x ≠ δ ✓;无 δδ ✓;合取项5:使 δ0y P δ0δ 成立的唯一 y 就是 δ 本身,而 δBδ 经 B 的 x = y 条款成立。Seq(2040) ✓——房间“0”合法,恰如设计。
2. x ∈ y——成员关系,以及第三个合取项为何存在
语义值:y 编码一个序列,且 x 是其成员之一。字符串:Seq y ∧ δxδPy ∧ δP̄x。
正向。 若 x = aᵢ,则字符串 δaᵢδ——x 两侧夹着两堵墙——出现在 y 中:δxδPy。aᵢ ∈ K₁₁ 又给出 δP̄x。✓
反向——对齐论证。 假设 δxδPy,且 x 不含 δ。这次出现两侧的 δ 必须与 y 的墙重合(y 中所有 δ 都是墙)。两个连续墙之间恰有一个房间;x 的字符串不含 δ,不能跨墙,所以两侧的墙连续,x 的字符串就是中间的整个房间——不是房间的真部分,因为这次出现两侧以 δ 为界,而房间内部没有 δ。因此对某个 i,x = aᵢ。✓
为什么 δP̄x 不是装饰。 去掉它,取 y = δ1δ2δ(序列 (1,2)),x 为数位1、δ、2组成的数(= 169 + 156 + 2 = 327)。则 δxδ = δ1δ2δ = y,当然出现在 y 中——但327不是成员;它的“出现”跨过了墙。合取项 δP̄x 恰好是不跨墙的保证,使对齐论证成立。
3. x ≺_z y——通过前缀见证表达顺序
语义值:x、y 是 z 所编码序列的成员,且 x 的首次出现严格早于 y。字符串:x ∈ z ∧ y ∈ z ∧ (∃w ≤ z)(wBz ∧ x ∈ w ∧ ~y ∈ w)。
图像。 z 的一个自身也是序列数的前缀,恰好是“前 j 个房间,含墙”:w = δa₁δ…δaⱼδ。字符串要求存在这样的 w,含 x 却不含 y。
正向。 设 x 首次出现在房间 i,y 首次出现在房间 k,i < k。取 w = δa₁δ…δaᵢδ。则 w 的数位字符串是 z 的初始段,所以 wBz(且 w < z,故界限 ∃w ≤ z 合理);由构造 x ∈ w;y ∉ w,因为若 y 出现在房间1…i中,其首次出现就会 ≤ i < k。✓
反向。 给定这样的 w:x ∈ w 强制 Seq w(它是 ∈ 的第一合取项),所以 w 自身是序列数,且 wBz 使其数位成为 z 的初始段。初始段逐位匹配,所以 w 的每堵墙都位于 z 的墙上,w 末尾 δ 位于 z 的某堵墙——因此 w 的房间恰是 z 的房间1…j,对某个 j。(像 δa₁δ2 这样在房间中间截断的前缀不满足 Seq;在房间中间却恰好位于墙位置的切法不可能——该位置在一个字符串里是 δ,在另一个里是非δ,违反匹配。)现在 x ∈ w 使 x 首次出现位于某个 ≤ j 的房间,y ∉ w 且 y ∈ z 则使 y 首次出现位于某个 > j 的房间。严格更早。✓
免费得到严格性: x ≺_z x 为假——任何含 x 的 w 都含 x。
为什么是“首次出现”? 序列可能重复成员。证书条件实际需要的关系是“在需要 y 之前严格更早处,有成员可用”——前缀见证能看到的就是首次出现。它与非正式定义“先前成员”的匹配在条件5论证。
第五部分——§3,条件1–11:句法算术化
§3的固定约定。 E_x = 哥德尔数为 x 的表达式(7月21日)。对 x₁, …, xₙ ∈ K₁₁,序列 (E_{x₁}, …, E_{xₙ}) 的哥德尔数是 (x₁, …, xₙ) 的序列数——即 ♯E_{x₁}♯…♯E_{xₙ}♯ 的哥德尔数。两个缩写(第33页):
(∀x ∈ y)(…) 代表 ∀x(x ∈ y ⊃ …)
(∃x,y ≺_w z)(…) 代表 ∃x∃y(x ≺_w z ∧ y ≺_w z ∧ …)
(第一个看似无界 ∀——但成员从不超过其序列数[成员字符串是序列字符串的真部分],所以它是伪装的有界全称:∀x(x ∈ y ⊃ …) ⟺ (∀x ≤ y)(x ∈ y ⊃ …)。一行检查,值得做一次——书承诺的“只有有界全称量词”仍成立。)
八个连接函数(第34页)。 对 (E_x ⊃ E_y)、~E_x、(E_x + E_y)、(E_x · E_y)、(E_x E E_y)、E_x′、E_x = E_y、E_x ≤ E_y 的哥德尔数,书写作 x imp y、neg(x)、x pl y、x tim y、x exp y、s(x)、x id y、x le y。它们都是固定连接模板,因此是算术的。书展示的两个,对照7月21日数位表(0→1、′→0、(→2、)→3、f→4、下标→5、v→6、~→7、⊃→8、∀→9、=→η、≤→ε、♯→δ):
x imp y = 2x8y3 “(”、x、“⊃”、y、“)”
neg(x) = 7x “~”、x——无括号;注意:这是7 ∗ x,
在前面加一个数位,不是乘以7(书自己
添加了“即7 ∗ x”)
其他函数中藏着两颗宝石:s(x) = x ∗ 0 = 13·x——末尾加撇号就是乘以13,7月21日的“后继符号施加器”现在成为正式函数。而因为原子公式不带括号(看下面书中未缩写的 L₆:~∀vᵢ~vᵢ = t),x id y = xηy,x le y = xεy (推断——书没有重新展示;欠一次对照第二章§1正式语法的30秒检查,第十一部分);同样,pl、tim、exp 想必把中缀 f′、f′′、f′′′ 包在括号里,例如 x pl y = 2x(40)y3 (同样待查)。
各条件,字符串/语义值/等价:
1. Sb(x)——E_x 是一个(非空)下标串: (∀y ≤ x)(yPx ⊃ 5Py)。 为何成立:x 的每个部分都含数位5 ⟺ x 的每个数位都是5——因为单个数位也是部分,所以任何非5数位 d 都会成为一个满足5P̄d 的部分。(x = 0 也通过 y = 0 失败:5P̄0。)漂亮地在无法说“数位”的情况下说出“我的所有数位都是5”。 相对于7月19日的变化:字母表中类似逗号的符号(数位5),从引入以来一直没有工作,如今显露为变量的下标构成符。
2. Var(x)——E_x 是变量: (∃y ≤ x)(Sb(y) ∧ x = 26y3)。 语义值:第 i 个变量的正式拼写是 ( v 后接 i 个下标标记 )——数位2、6、5…5、3。所以 g.n.(v₁) = 2653₁₃ = 5476;g.n.(v₂) = 26553₁₃。括号是变量的一部分——这使 v₁v₂ 仍可解析。界限 y ≤ x 合理:y 的字符串是 x 的部分。
3. Num(x)——E_x 是数码: Pow₁₃(x)。 7月21日的回报浓缩一行: n̄ = 0后接n个撇号 → 数位1后接n个0 → 13ⁿ。所以“x 编码数码”就是“x 是13的幂”。(Pow₁₃ 是算术的:持续欠账“素数底13”,未变。)
4. R₁(x, y, z)——项的形成关系对 (E_x, E_y, E_z) 成立: z = x pl y ∨ z = x tim y ∨ z = x exp y ∨ z = s(x)。 语义值: E_z 可从 E_x、E_y 一步构成——它是 (E_x + E_y)、(E_x · E_y)、(E_x E E_y) 或 E_x′。纯粹在编码上做模板匹配;第四个析取项字面就是 z = 13x。
Seq(x) ∧ (∀y ∈ x)(Var(y) ∨ Num(y) ∨ (∃z, w ≺_x y)R₁(z, w, y))
语义值(书的定义,第33页):一个有限表达式序列,其中每个表达式是变量、数码,或由两个先前成员经 R_t 构成。 这就是证书的形状——记住一次,随后还会原样重现两次:
Seq(x) ∧ (∀y ∈ x)( seed(y) ∨ (∃z, w ≺_x y) rule(z, w, y) )
指标与首次出现的细微差异(字符串与非正式定义之间唯一真正的缺口)。 非正式定义谈位置:条目 i 由条目 j、k < i 证明其资格。字符串谈值和首次出现:每个成员值 y 必须是种子,或由首次出现严格早于 y 首次出现的值经 R₁ 构成。等价:(⇒) 在按位置说明资格的序列中,考察任意值 y 的首次出现 i;其依据位于 < i 的位置,所以依据的首次出现也 < i——满足字符串要求。(⇐) 从满足字符串的 x 出发,序列从左到右每个首次出现都有位置上的依据,重复项则指向左边的首次出现来取得依据。同样的证书,两种记录方式。 还要注意:只有 Seq 的成员进入——Seq 把成员限制在 K₁₁,这也是不含 ♯ 的句法起初就需要其编码位于 K₁₁ 的原因。
6. tm(x)——E_x 是项: ∃y(Seqt(y) ∧ x ∈ y)。 兑现证书:项 = 某个项的形成序列的成员。∃y 无界——在这个代价下必然如此(证书远大于其结论:上面的 y = 4,526,716 证明 x = 5476 的资格),且无害——算术性从未要求 ∃ 有界。只有 ∀ 必须保持有界。
7. f₀(x)——E_x 是原子公式: (∃y ≤ x)(∃z ≤ x)(tm(y) ∧ tm(z) ∧ (x = y id z ∨ x = y le z))。 原子式 = t₁ = t₂ 或 t₁ ≤ t₂,t₁、t₂ 为项。界限合理(又是部分关系)。
8. Gen(x, y)——对某个变量 vᵢ,E_y = ∀vᵢ E_x: (∃z ≤ y)(Var(z) ∧ y = 9zx)。 数位9 = ∀,然后变量,再是主体——注意没有额外括号,变量自带括号。
9. R₂(x, y, z)——公式的形成关系成立: z = x imp y ∨ z = neg(x) ∨ Gen(x, z)。 E_z 是 (E_x ⊃ E_y)、~E_x 或 ∀vᵢE_x。(在第二、第三析取项中 y 闲置——条件14中也有同样用法。)
10. Seqf(x)——x 编码公式的形成序列:
Seq(x) ∧ (∀y ∈ x)(f₀(y) ∨ (∃z, w ≺_x y)R₂(z, w, y))
证书形状的第二次实例化——种子现在是原子公式,规则是 R₂。
11. fm(x)——E_x 是公式: ∃y(Seqf(y) ∧ x ∈ y)。
第六部分——条件12–17:公理、推导、证明、可证性
12. A(x)——E_x 是 P.E. 的公理:十九个条件的析取 L₁(x), …, L₇(x), N₁(x), …, N₁₂(x),对应7月24日目录中的每个模式。书的公理说明给出样例:
-
第一组样例,L₁(x)。 E_x 是 (F ⊃ (G ⊃ F)) 的实例,当且仅当
(∃y ≤ x)(∃z ≤ x)(fm(y) ∧ fm(z) ∧ x = y imp (z imp y))
为何界限足够:实例中的 F、G 是 E_x 的子表达式,而部分编码从不超过整体编码(更短或等长的数位字符串)。属于某模式已变成具有两个公式类型空位的模板匹配——这就是7月24日所谓“仅凭形状即可识别”,如今已字面化。L₂(x)、L₃(x):同一思想,留给读者(待做,第十一部分)。
-
第二组样例,L₄(x)。 令 φ(y, z, w) = ∀E_y(E_z ⊃ E_w) ⊃ (∀E_y E_z ⊃ ∀E_y E_w) 的哥德尔数——以 imp 和9前缀构成的固定连接模板,因此是算术的。则
L₄(x) ⟺ (∃y ≤ x)(∃z ≤ x)(∃w ≤ x)(Var(y) ∧ fm(z) ∧ fm(w) ∧ x = φ(y, z, w))
注意使用了7月24/25日的哪个事实:卡利什–蒙塔古模式有出现扫描的附带条件,而非自由性的附带条件——L₅的“vᵢ 不出现在 F 中”是形如 yP̄(F的编码) 的子串检查,只差一个 P 就成为算术的。自由性则需要解析作用域;公理被如此设计,使§3从不解析作用域。(书说:L₆展示时以 ∃ 为缩写;不缩写就是模式 ~∀vᵢ~vᵢ = t。)
-
第三组(N₁–N₁₁)。 每个模式恰有一个公理,所以 Nᵢ(x) 就是 x = gᵢ,gᵢ 是那个公式的哥德尔数——与常数相等,最算术的条件。
-
第四组(N₁₂,归纳)。 书说:先验证关系“E_x 是公式,且 E_y 是诸公式 E_x[v₁′] 之一”关于 (x, y) 是算术的——留给读者(待做,附提示,第十一部分)——之后 N₁₂(x) 显然。相对于7月25日第十一部分的变化:E_x[v₁′] 是双重封装式 ∀vᵢ(vᵢ = v₁′ ⊃ ∀v₁(v₁ = vᵢ ⊃ E_x)),复数说法“诸公式之一”来自新鲜变量的自由——每个可用的 vᵢ 对应一个括号字符串,所以算术化版本是关系而非函数。舍弃手术式代入而选封装式,恰为这一刻:它的编码是围绕 x 的连接模板,x 作为未拆封块搭乘其中(7月22日的 r(x, y) 同样形状),而真正代入需要内部数位手术。
13. M.P.(x, y, z)——E_z 可由 E_x、E_y 经规则1(肯定前件)推出:y = x imp z。 一个等式。语义值:大前提 E_y 就是字符串 (E_x ⊃ E_z)——一步可推导性是关于 y 的形状事实,仅此而已。(从 F 和 (F ⊃ G) 得 G:x 扮演 F,z 扮演 G。)
14. Der(x, y, z)——E_z 可由 E_x、E_y 经规则1,或由 E_x 经规则2推出: M.P.(x, y, z) ∨ Gen(x, z)。 Gen 析取项中 y 闲置——规则2(全称化:从 F 得 ∀vᵢF)只有一个前提。保留统一的双前提形式,使条件15每次都能要求单个数对 (z, w);规则2的行只需让第二个引用是任意先前成员(z 自身即可)。
15. Pf(x)——x 编码 P.E. 中的一个证明:
Seq(x) ∧ (∀y ∈ x)(A(y) ∨ (∃z, w ≺_x y)Der(z, w, y))
证书形状的第三次、也是最后一次实例化——种子:公理;规则:Der。语义值:一个公式有限序列,每个公式是公理或可由先前成员推出——希尔伯特式证明的教科书定义,原样如此。整个章节就是为写出这一行而存在;注意条件1–14之后,它没有任何新成本。两项说明: - 只有公式,尽管没人检查 fm:沿序列归纳——公理是公式(十九个析取项各自内置 fm 或命名一个公式);若 E_w = (E_z ⊃ E_y),且 E_z、E_w 是公式,唯一可读性使 E_y 也是;∀vᵢE_z 同理。字符串无须管控规则不可能产生的东西。 - 首次出现的记录方式:与条件5完全一样——每个标准证明按原样都符合,每个符合的 x 都能读成标准证明。
16. P_E(x)——E_x 在 P.E. 中可证: ∃y(Pf(y) ∧ x ∈ y)。 可证 = 某个证明的成员——没有“最后一行”条款,也不需要:证明截至任意成员首次出现的前缀,本身就是证明(所有成员的依据都在此前缀内首次出现),所以成员资格与最后一行资格证明同一个集合。无界 ∃,与条件6得到同样许可。
17. R_E(x)——E_x 在 P.E. 中可反驳: P_E(neg(x))。 可反驳 = 否定可证(第一章定义)。一次复合——7月20日“算术集在算术函数下的逆像是算术的”,取 f = neg。再说一次:neg(x) = 7x 是在前面加数位7,即7·13^ℓ(x) + x——误读成乘法,后面一切都站不住。
命题3。 所有条件 (1)–(17) 都是算术的。——“这完成了我们对 P.E. 句法的算术化。”
书的证明,写成引用已掌握材料的链条(方括号中是7月22日的名称):
- P_E、R_E 是算术的(命题3)——所以取公式 P(v₁)、R(v₁),在 L_E 中表达它们。
- ~P(v₁) 表达补集 P̃_E[取补封闭——7月20日工具箱的直接方向]。
- 由上一章定理1的引理[引理1,7月22日:A 是算术的 ⇒ A* 是算术的,经封装式 r],存在表达 (P̃_E)* 的 H(v₁)。
- 其对角化 H[h̄] 是 P̃_E 的哥德尔语句[7月22日,定理1的证明]:H[h̄] 为真 ⟺ g.n.(H[h̄]) ∈ P̃_E ⟺ H[h̄] 在 P.E. 中不可证。
- P.E. 是正确系统(可证 ⇒ 真;7月24日的意义)。若 H[h̄] 可证,就为真,因此不可证——矛盾。所以 H[h̄] 不可证;由双条件,为真。
- 则 ~H[h̄] 为假,因此(再次用正确性)不可证——所以 H[h̄] 也不可反驳。一个既不可证也不可反驳的语句:P.E. 不完备。(定理1。)
对偶路线,同一个引擎: R_E 是算术的 ⇒ R_E* 是算术的 ⇒ K(v₁) 表达它 ⇒ K[k̄] 是 R_E 的哥德尔语句:真 ⟺ 可反驳。若它为真,就可反驳,于是 ~K[k̄] 可证,于是 ~K[k̄] 为真,于是 K[k̄] 为假——矛盾。所以 K[k̄] 为假,因此不可反驳,而且(假 + 正确性)不可证。从可反驳性一侧得到同样的不可判定语句现象。注意7月23日的对称重现:H[h̄] 是断言自身不可证的真语句;K[k̄] 是断言自身可反驳的假语句。
俯瞰的一句话(不是书的措辞,却是书的架构)。 第二章证明真语句集不可表达(塔尔斯基)。本章证明可证语句集可以。可表达者与不可表达者必定在某处不同——在正确性(可证 ⊆ 真)下,差别只能是一个真却不可证的语句。算术化在可证性上必须成功,恰与它在真理上必须失败相对;不完备性就是中间透出的光。
第八部分——今天真正新增了什么
把十七个条件化约为思想,本节恰好带来三项:
- 子串关系是算术的(B、E、P)——由7月21日的 ∗ 加一个前导零补丁换得。
- 数的有限序列以算术方式成为单个数(Seq、∈、≺)——由保留的分隔数位及 (1) 换得。
-
归纳定义转为 ∃ 证书定义——由 (2) 换得,再以同一可复用形状使用三次(项、公式、证明):
Seq(x) ∧ (∀y ∈ x)( seed(y) ∨ (∃z, w ≺_x y) rule(z, w, y) )
其他一切都是模板记录整理。此前研读的设计欠账都按时在这里到期:逗号符号(7月19日)为 Var 存在;撇号→0(7月21日)使 Num 只是一个 Pow;x ∗ 0 = 13x(7月21日的病症)就是 s(x);出现而非自由性的附带条件(7月25日)使 A(x) 保持在连接层面;封装式(7月22/25日)使 N₁₂ 的括号成为模板而非手术;一周来无所事事的 ♯ 符号,原来一直就是序列机制。
第九部分——汇总表(字符串 ↔ 语义值,完整)
符号:并置 = ∗₁₃ 连接;数位依7月21日表;P̄ = 不是部分;≺_x = 在x中首次出现更早。
| # | 条件 | 定义字符串 | 语义值 |
|---|---|---|---|
| — | xBy | x = y ∨ (x ≠ 0 ∧ (∃z,w ≤ y)(Pow₁₃(w) ∧ (x·w) ∗ z = y)) | x的数位是y的开头(w = 移过尾部前导零的位移量) |
| — | xEy | x = y ∨ (∃z ≤ y)(z ∗ x = y) | x的数位是y的结尾 |
| — | xPy | (∃z ≤ y)(zBy ∧ xEz) | x的数位出现在y中(x是y某个开头的结尾) |
| — | Seq x | δBx ∧ δEx ∧ δ ≠ x ∧ δδP̄x ∧ (∀y ≤ x)(δ0yPx ⊃ δBy) | x = δa₁δ…δaₙδ,n ≥ 1,aᵢ ∈ K₁₁且规范 |
| — | x ∈ y | Seq y ∧ δxδPy ∧ δP̄x | x是y的序列成员 |
| — | x ≺_z y | x ∈ z ∧ y ∈ z ∧ (∃w ≤ z)(wBz ∧ x ∈ w ∧ ~y ∈ w) | x的首次出现先于y(w = 截至x的前缀) |
| 1 | Sb(x) | (∀y ≤ x)(yPx ⊃ 5Py) | E_x是下标串(所有数位均为5) |
| 2 | Var(x) | (∃y ≤ x)(Sb(y) ∧ x = 26y3) | E_x是变量 ( v 下标 ) |
| 3 | Num(x) | Pow₁₃(x) | E_x是数码(g.n.(n̄) = 13ⁿ) |
| 4 | R₁(x,y,z) | z = x pl y ∨ z = x tim y ∨ z = x exp y ∨ z = s(x) | E_z可由E_x、E_y一步构成(项规则) |
| 5 | Seqt(x) | Seq(x) ∧ (∀y ∈ x)(Var(y) ∨ Num(y) ∨ (∃z,w ≺_x y)R₁(z,w,y)) | x编码项的形成序列 |
| 6 | tm(x) | ∃y(Seqt(y) ∧ x ∈ y) | E_x是项 |
| 7 | f₀(x) | (∃y,z ≤ x)(tm(y) ∧ tm(z) ∧ (x = y id z ∨ x = y le z)) | E_x是原子公式 |
| 8 | Gen(x,y) | (∃z ≤ y)(Var(z) ∧ y = 9zx) | E_y = ∀vᵢE_x |
| 9 | R₂(x,y,z) | z = x imp y ∨ z = neg(x) ∨ Gen(x,z) | E_z可一步构成(公式规则) |
| 10 | Seqf(x) | Seq(x) ∧ (∀y ∈ x)(f₀(y) ∨ (∃z,w ≺_x y)R₂(z,w,y)) | x编码公式的形成序列 |
| 11 | fm(x) | ∃y(Seqf(y) ∧ x ∈ y) | E_x是公式 |
| 12 | A(x) | L₁(x) ∨ … ∨ L₇(x) ∨ N₁(x) ∨ … ∨ N₁₂(x) | E_x是公理(19个模板;展示了L₁,第三组:x = gᵢ) |
| 13 | M.P.(x,y,z) | y = x imp z | E_z由E_x、E_y经肯定前件推出 |
| 14 | Der(x,y,z) | M.P.(x,y,z) ∨ Gen(x,z) | E_z由E_x(也可能有E_y)经规则1或2推出 |
| 15 | Pf(x) | Seq(x) ∧ (∀y ∈ x)(A(y) ∨ (∃z,w ≺_x y)Der(z,w,y)) | x编码证明 |
| 16 | P_E(x) | ∃y(Pf(y) ∧ x ∈ y) | E_x可证 |
| 17 | R_E(x) | P_E(neg(x)) | E_x可反驳 |
区分表(当天的混淆 → 一句话解答):
| 问题 | 解答 |
|---|---|
| “Seq x 与其字符串等价?” | 五个合取项 = 两端有墙 + 至少一个非空房间 + 无前导零;第四部分证明两个方向,唯一精巧处是前导零情况中的单数位见证。 |
| δ0y、δxδ、26y3、7x 看起来像算术 | 它们是连接:第32页起,并置 = ∗₁₃。neg(x) = 7x 是前加7,不是 ×7。 |
| 为什么 x ∈ y 内部要有 δP̄x? | 没有它,δxδPy 会跨墙:x = (1δ2) “出现”于 δ1δ2δ,却不是成员。 |
| xPy:结尾的开头,还是开头的结尾? | 开头的结尾:(∃z ≤ y)(zBy ∧ xEz)。斜体B/E容易换位;校验和:0是5076的部分——仅此读法为真。 |
| ≺使用首次出现,定义使用位置 | 同样的证书:每个值在首次出现处说明依据;重复项向左指。 |
| (∀y ∈ x) 看起来无界 | 成员 ≤ 其序列数,所以它是伪装的 (∀y ≤ x)(y ∈ x ⊃ …);有界∀的承诺仍成立。 |
| 为什么 tm、fm、P_E 中的 ∃y 允许无界? | 算术性从未限制∃;只有∀必须保持有界(为下一章的构造性类)。证书大于结论,反正也没有廉价界限。 |
| “诸公式 E_x[v₁′] 之一”——为什么复数? | 每种新鲜vᵢ选择对应一个括号串;算术化为关系。封装式使x保持未拆封块——所以公理记号用括号而非代入。 |
第十部分——自测
不看材料完成;每题后附答案。
1. 为什么 Seq x 需要 δδP̄x——它排除哪两种非法 x?
答案
空房间:没有它,δa₁δδa₂δ 会编码一个带无成员槽位的“序列”(没有数有空的数位字符串),而 x = δδ 会编码空序列,Seq 排除它(n ≥ 1)。
2. 解析 Seq 的第五合取项,说明它如何排除 x = δ05δ(房间“05”)。
答案
(∀y ≤ x)(δ0yPx ⊃ δBy):“δ0”一次出现之后的东西必须以δ开头。取 y = 5:δ05 出现在x中,所以δ0yPx成立;但δB5为假。违反合取项,Seq x为假。(房间“00…”:取y = 0;δB0为假。)
3. 计算单项序列 (0) 的序列数,并逐个验证 Seq 的合取项。
答案
δ0δ = 12·169 + 0·13 + 12 = 2040。δB ✓,δE ✓,≠ δ ✓,无δδ(0隔开)✓,第五合取项:只有y = δ满足δ0y P x,而δBδ经B的x = y条款成立 ✓。
4. 给出使 δxδPy 为真、但 x 不是 y 序列成员的 y、x,并指出挽救 ∈ 的合取项。
答案
y = δ1δ2δ(序列 (1,2)),x = 数位 (1, δ, 2) = 327:δxδ就是y自身。由δP̄x挽救——成员必须不含δ,所以禁止跨墙出现。
5. 在 x ≺_z y 中,为什么见证 w 必须是序列数,字符串在哪里要求它?
答案
x ∈ w 隐含要求它(第一合取项是Seq w)。这迫使w成为与墙对齐的前缀——只含完整房间——所以“x ∈ w ∧ y ∉ w”意味着“x在前j个成员中,y不在”,即首次出现的顺序。
6. 证明中规则2(全称化)的一行只有一个前提。它如何满足 Pf 对两个先前成员 z、w 的要求?
答案
Der(z, w, y) = M.P.(z,w,y) ∨ Gen(z,y);Gen析取项中w闲置,而缩写 (∃z,w ≺_x y) 只要求w是某个先前成员——取w = z。
7. 为什么 P_E 不需要“证明的最后一行”条款?
答案
证明的每个成员都可证:在它首次出现处截断——前缀自身就是证明(所有依据都在其中首次出现)。成员资格与最后一行资格证明同一个集合。
8. s(x) 是什么数,它是7月21日的哪个事实?
答案
s(x) = x ∗ 0 = 13x——末尾添撇号(数位0)占一个数位槽,即 ×13:病症变成了后继施加器。
9. 写出一次证书形状,并列出其三次实例化。
答案
Seq(x) ∧ (∀y ∈ x)(seed(y) ∨ (∃z,w ≺_x y)rule(z,w,y))。种子/规则 = Var或Num/R₁(Seqt);f₀/R₂(Seqf);A/Der(Pf)。
10. 俯瞰的一句话:从“真理不是算术的” + “P_E 是算术的” + 正确性,推出不完备性。
答案
P_E可表达,真集不可表达,所以它们在某个语句编码上不同。正确性排除可证却假的情况,所以差别是一个真却不可证的语句——不完备性。(书中§4路线则通过哥德尔语句机制显式构造见证:H[h̄]。)
进度:第三章第30–36页已读。 第二部分(算术化)及§4(定理1)——本章第一个不完备性证明完成。书从第37页继续(依目录,是ω‑一致性/罗瑟式改进及抽象形式)。
读者应做——今日新增(书第35–36页都“留给读者”): 1. L₂(x)、L₃(x):按L₁模型写出字符串。(两分钟模板练习。) 2. N₁₂的子关系:证明“fm(x),且E_y是诸公式E_x[v₁′]之一”关于(x, y)是算术的。尝试之前封存提示:括号是围绕块x的连接模板;vᵢ的新鲜性是子串条件(形如zP̄x);g.n.(v₁) = 5476,g.n.(v₁′) = s(5476) = 71188;imp、id、9前缀组装其余部分。 3. 两个30秒对书检查:(a) 第二章§1中项的 +、·、E 正式拼写——确认第五部分推断的pl/tim/exp与id/le模板;(b) 说明(∀x ∈ y)是伪装的有界全称量词的一行论证。
持续未做(7月24/25日):L₃情况检查;用祖先解释证伪(v₁ ≤ v₂ ∨ v₂ ≤ v₁);全域实例问题。
欠账记录,未变且无偿还:消去E;素数底13(现在在Num底下承担关键任务);性质1 ⇒ 性质2;机械 ⇒ 算术的(Arithmetic);1930年的恰切性;1931年的一般机器形式;运算一致;从L₆ + L₇得到实例化。
方法记录。 今日的格式——字符串/语义值/双向论证,对读者标记的项目(Seq)处理最深——很适合阅读研讨请求;两个OCR层面的陷阱(P行字形、neg的7x)印证7月25日的教训:把总结与页面的精确字符对照,正是双向捕捉错误之处。
此前研读:7月15日(第一章)、17日(答案)、19–22日(第二章)、20及23日(练习)、24日及25日续篇(第三章§1)。本文件:第三章§§2–4。