Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter II, §4–§5: Concatenation to the Base b, and Gödel Numbering
Reflections · Study sessions
AI-prepared recaps of study sessions; these are working notes, not verbatim transcripts. / AI 整理的学习记录,并非逐字实录。
Reading / 研读:Raymond Smullyan / 雷蒙德·斯穆里安 · Gödel’s Incompleteness Theorems 哥德尔不完备性定理
In this note / 篇目
- How to use this document
- Part I — The idea: the one operation that builds all syntax
- Part II — Three layers: scribe → shift-and-add → superlative
- Part III — The n = 0 patch: the missing competitor
- Part IV — Proposition 1 and its proof: Exercise 5 cashed in
- Part V — The 0-pathology and left association
- Part VI — Corollary 1: where the induction lives
- Part VII — Other bases in concreto
- Part VIII — §5: the numbering itself
- Part IX — The numeral payoff: why the accent gets 0
- Part X — The asymmetry: many-one forward, stipulated backward
- Part XI — What "base" means: Quine's 10, and the zeroless family
- Part XII — Base 1: two machines, three deaths
- Part XIII — The coding theorem (beyond the book): any base b ≥ 2 codes any finite alphabet
- Part XIV — Distinctions Ledger
- Part XV — Self-Test
- Part XVI — What's ahead in Smullyan, and the state of play
Study session of July 21, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter II §4 (Concatenation to the Base b: Proposition 1, Corollary 1) and §5 (Gödel Numbering), with the doorway into Part III (§6, Tarski's Theorem) · Companion to the sessions of July 15, 17, 19, and 20, 2026
How to use this document
This follows the order in which understanding was actually built — each part presupposes the ones before it. For review: read Parts I–XIII in order the first time; afterwards the Distinctions Ledger (Part XIV) alone is a full refresher, and the Self-Test (Part XV) tells you whether it took. The session's character was different from July 20's: not one recurring bug fought three rounds, but a chain of foundational probes — why n ≥ 1? why base 10 for nine symbols? what IS base 1? — each of which turned out to have a precise answer, and two of which ended with the reader independently reinventing a real piece of mathematics (zeroless numeration, Part XI; multi-digit binary coding, Part XIII). The three concrete encode/decode checks were deferred all session in favor of these probes; they are settled in the Self-Test, answers included — do them cold before peeking.
Part I — The idea: the one operation that builds all syntax
Expressions of L_E are strings of symbols, and the single operation that builds every string is juxtaposition — writing one expression after another. The program of the chapter needs syntactic notions (formula, sentence, truth) to become notions about numbers. Two steps:
- §5: turn symbols into digits, so strings become numbers.
- §4: show that juxtaposition-of-strings, viewed through that translation, is an Arithmetic operation on numbers.
§4 does the heavy lifting first. The operation, in base 10: m ∗₁₀ n = write m, write n immediately after, read as one number. 53 ∗₁₀ 792 = 53792. The problem: "write the digits of m, then the digits of n" is an instruction to a scribe, not a formula of L_E. L_E has no digits and no "after." §4's entire job is to de-syntactify the scribal operation — describe it using only +, ·, E, ≤, =.
This is also where July 20's Exercise 5 was secretly headed: "x is the smallest element of A greater than y" turned out to be, verbatim, Step 2 of the proof of Proposition 1, with A = the powers of b. The "for later" flagged in that session's recap was paid out today.
Part II — Three layers: scribe → shift-and-add → superlative
Layer 1 (scribal): juxtapose the notations. 53 next to 792.
Layer 2 (shift and add): what juxtaposition does to values. Writing 792 after 53 shifts 53 three decimal places left, then adds:
53792 = 53·10³ + 792
Three, because 792 is three digits long. With ℓ_b(n) = the number of base-b digits of n:
m ∗_b n = m·b^ℓ(n) + n
Almost arithmetic — but ℓ still says "count the digits." One syntactic residue left.
Layer 3 (superlative): you never need ℓ(n) itself, only the power b^ℓ(n) — and that power has a purely order-theoretic description:
b^ℓ(n) = the smallest power of b greater than n (for n ≥ 1)
The book's example: 10^ℓ(5368) = 10⁴ = 10000, the smallest power of 10 exceeding 5368. Why it works — the squeeze: a number n with k digits in base b satisfies
b^(k−1) ≤ n < b^k
(the smallest k-digit number is 1 followed by k−1 zeros, i.e. b^(k−1); the largest is b^k − 1). So b^k beats n and b^(k−1) already doesn't: b^k = b^ℓ(n) is the smallest power beyond n. No digits mentioned — only powers and order.
Why strictly "greater than," not "≥" — verified independently in session: take 45 ∗₁₀ 100. The smallest power ≥ 100 is 100 itself, giving 45·100 + 100 = 4600 — wrong; wanted 45100, needing the multiplier 1000. The two readings disagree exactly when n is itself a power of b (a power of b has k+1 digits, not k), and every power of b is a legitimate second argument, so strictness is mandatory.
Part III — The n = 0 patch: the missing competitor
The confusion raised: why restrict Layer 3 to n ≥ 1? Isn't 10 the smallest power of 10 greater than 0, giving 1 ∗₁₀ 0 = 10 correctly?
The diagnosis: a competitor was left off the roster. Administer the superlative's test at n = 0 by hand:
powers of 10: 1, 10, 100, 1000, …
which are > 0? all of them
smallest? 1
Because 1 = 10⁰ is a power of 10 — the book's own formula is the receipt: Pow_b(x) iff ∃y(x = b^y), and y = 0 witnesses x = 1. The superlative outputs 1, not 10; trusting it would give 1 ∗₁₀ 0 = 1·1 + 0 = 1, and "1" is not "1 followed by 0."
Which layer broke: Layer 2 is fine at n = 0 — with ℓ(0) = 1 (the numeral "0" is one digit), m·10^ℓ(0) + 0 = 10m, the appended zero, correct (53 ∗₁₀ 0 = 530). Layer 3 is what fails: the squeeze's left half collapses (10⁰ ≤ 0 says 1 ≤ 0, false). Root cause: 0 is the one number whose numeral doesn't earn its digit — every n ≥ 1 with k digits has a nonzero leading digit forcing n ≥ b^(k−1); the numeral "0" is a single digit that IS a leading zero, the only one in the system. Every 0-pathology in the section traces here.
The fix: split by cases. The superlative lies at exactly one input, so patch it with ∨:
(y = 0 ∧ x = b̄) ∨ (y ≠ 0 ∧ [x is the smallest power of b greater than y])
Session check, passed: unpatched, 53 ∗₁₀ 0 = 53 (the concatenation that ate the zero); patched, 530.
Part IV — Proposition 1 and its proof: Exercise 5 cashed in
Proposition 1. For each b ≥ 2, the relation x ∗_b y = z is Arithmetic.
By the takeaway principle of July 20: the condition mentions three names — x, y, z — so the formula owes exactly three free variables, and every helper gets its own ∃. Three steps, each a tool already owned:
Step 1 — Pow_b(x): ∃w(x = b̄ E w). One free slot (membership in a set), one invented name, one ∃. This is where the capital A in "Arithmetic" earns its keep — E is used. (Whether it survives without E is the debt register's standing third entry: Gödel's E-elimination, owed by a later chapter.)
Step 2 — the relation b^ℓ(x) = y (book's orientation: x the measured number, y the power). For x ≥ 1 this says: y is the smallest member of Pow_b greater than x — verbatim Exercise 5 with A := Pow_b:
Pow_b(y) ∧ x < y ∧ ∀z((Pow_b(z) ∧ x < z) ⊃ y ≤ z)
Everything transfers: the ⊃-guard (not ∧) so non-powers pass vacuously; and Pow_b is infinite (b, b², b³, …), so every x has such a y — the relation is the graph of a total function, which is exactly what Step 3 needs. (July 20's remark "infinitude makes R total, for later" — this was the later.) Plus the Part III patch for x = 0.
Step 3 — assembly. x ∗_b y = z unpacks as z = x·b^ℓ(y) + y: two intermediate values (the power, the product), so two temporaries, glued with ∧:
∃z₁∃z₂( b^ℓ(y) = z₁ ∧ x·z₁ = z₂ ∧ z₂ + y = z )
Free: x, y, z — the condition's own names. Bound: z₁, z₂ — scaffolding. Every conjunct Arithmetic (Step 2; two atomic equations); ∧ and ∃ preserve Arithmetic-ness. ∎
Two sharpenings from the session narration:
- "Given a z" — nothing gives z. It is one of the three free slots; the last conjunct ties the scaffolding back to it. The July 20 lesson lives or dies in that wording.
- Free variables are plug points. Step 2 was proved as a 2-place relation with slots (measured number, power); Step 3 plugs y and z₁ into those slots. A relation proved Arithmetic once gets reused with whatever names the new context needs — that is why the slots had to stay free, and it is the whole economy of the three-step structure. Note also which number's length is taken: y's, the second argument — the shift on x is dictated by how much room y needs.
What the proof never does: count digits or mention base-b notation. The scribe motivated the formula in the metatheory; the formula itself knows only plus, times, powers, order.
Part V — The 0-pathology and left association
For positive x, y, z concatenation is associative. But 0's numeral is the one numeral that can vanish — a leading zero is not part of standard notation. Quine's example:
(5 ∗₁₀ 0) ∗₁₀ 3 = 50 ∗₁₀ 3 = 503
5 ∗₁₀ (0 ∗₁₀ 3) = 5 ∗₁₀ 3 = 53 since 0 ∗₁₀ 3 = 0·10² + 3 = 3
Base-2 twin, computed in session: (5 ∗₂ 0) ∗₂ 3 = 10 ∗₂ 3 = 43, but 5 ∗₂ (0 ∗₂ 3) = 5 ∗₂ 3 = 23. Same disease, any base.
Convention: unparenthesized chains associate left — x ∗_b y ∗_b z means (x ∗_b y) ∗_b z — and the 3-fold relation is Arithmetic by one more temporary: ∃z₁(x ∗_b y = z₁ ∧ z₁ ∗_b z = w).
Part VI — Corollary 1: where the induction lives
Corollary 1. For each n ≥ 2 (and each b ≥ 2), the relation x₁ ∗_b … ∗_b xₙ = y, as an (n+1)-place relation, is Arithmetic.
Proof by induction on n — in the metatheory. Base: n = 2 is Proposition 1. Step: assume the n-fold relation is Arithmetic (this assumption is what "the earlier concatenation yields z" leans on — without it, nothing certifies that the length-n prefix is expressible), then
x₁ ∗_b … ∗_b xₙ₊₁ = y iff ∃z( x₁ ∗_b … ∗_b xₙ = z ∧ z ∗_b xₙ₊₁ = y )
Left association is quietly load-bearing: it is what licenses treating the prefix as a single number z at all. ∎
The precision point: the induction produces an infinite family of formulas — F₂, F₃, F₄, … — one per fixed n. No single formula could cover all n: the n-fold relation has n+1 free slots, and a formula has a fixed number of them. Why this is harmless: any particular syntactic operation glues a fixed number of pieces. "Negate X" is the 4-piece concatenation ~, (, X, ) — Corollary 1 at n = 4, one formula, done. Nobody ever needs "all n" inside one formula.
Part VII — Other bases in concreto
Base 2 (5 = 101, 6 = 110, 3 = 11):
5 ∗₂ 6: scribal 101⌢110 = 101110 = 46; formula: smallest power of 2 beyond 6 is 8, so 5·8 + 6 = 46 ✓
(1 ∗₂ 2) ∗₂ 5 = 6 ∗₂ 5 = 53 = 1 ∗₂ (2 ∗₂ 5) — associativity, all-positive ✓
Base 13 (digits 0–12; multi-valued digits written ⟨·⟩; 24 = ⟨1⟩⟨11⟩):
7 ∗₁₃ 24: smallest power of 13 beyond 24 is 169, so 7·169 + 24 = 1207
decode: 1207 = 7·169 + 1·13 + 11 = ⟨7⟩⟨1⟩⟨11⟩ — both originals intact, side by side (losslessness)
Same inputs, different bases:
5 ∗₂ 3 = 23 5 ∗₁₀ 3 = 53 5 ∗₁₃ 3 = 68
There is no base-independent concatenation of numbers — only of numerals, and numerals presuppose a base.
Where b lives in the proof: exactly twice — the numeral b̄ inside Pow_b, and in the y = 0 patch. Swap 1̄0̄ for 2̄ or 1̄3̄ and the entire proof re-runs verbatim. The generalization from 10 to b is the observation that the argument never used anything specific to 10.
Part VIII — §5: the numbering itself
Base 13 needs thirteen digit-shapes; for ten, eleven, twelve the book introduces η, ε, δ. The assignment:
symbol: 0 ′ ( ) f , v ~ ⊃ ∀ = ≤ ♯
digit: 1 0 2 3 4 5 6 7 8 9 η ε δ
Two deliberate choices, from which everything subtle flows: the symbol 0 gets digit 1, and the accent ′ gets digit 0.
The rule: replace each symbol by its digit; read the resulting string as a base-13 numeral. The book's example: digit string "362" — the string ) v ( — names 3·13² + 6·13 + 2 = 587. Two morals: (i) "362" is a digit string, and which number it names depends on the base it's read in — always 13 here; (ii) ) v ( is grammatical garbage and that's fine — every string gets a number; "being a formula" will later be a property of the numbers (an Arithmetic set, if the program works).
The bridge — where §4 pays out, one line:
g.n. of Eₓ E_y = x ∗₁₃ y
Concatenating expressions IS ∗₁₃ on their Gödel numbers — digits of x followed by digits of y, read base 13, which is the definition of ∗₁₃ verbatim. Proposition 1 (b = 13) says that operation is Arithmetic: the one operation that builds all syntax is now an Arithmetic relation on ℕ. From here the book writes x ∗ y for x ∗₁₃ y, permanently.
Part IX — The numeral payoff: why the accent gets 0
The numeral n̄ is the symbol 0 followed by n accents → digit 1 followed by n zeros → read base 13:
g.n. of n̄ = 13ⁿ (checks: 2̄ = 0′′ → 100₁₃ = 169 = 13²; even 0̄ = "0" → 1 = 13⁰)
The coding function n ↦ g.n.(n̄) must be Arithmetic, and 13ⁿ transparently is: its graph is expressed by m = 1̄3̄ E n — two free slots, per the takeaway principle.
Necessity vs. convenience, refined in session: accent → 0 is not what makes the function Arithmetic — it's what makes it transparently Arithmetic. Had the accent gotten digit 5, the numeral would code as 13ⁿ + 5·(13ⁿ − 1)/12 — messier, still buildable from E, ·, + and an ∃ for the division, still Arithmetic. The zero-accent purchases immediacy (one E-term, no cleanup), not possibility. The book's own words: the numbering was chosen to secure its two properties "as quickly as possible."
And the §4 pathology becomes a feature: x ∗ 0 = x·13^ℓ(0) + 0 = 13x — multiplying a code by 13 appends one 0-digit, i.e. appends one accent. The operation that broke associativity in §4 is now the successor-symbol applicator; g.n.(n̄) = 1 ∗ 0 ∗ 0 ∗ … ∗ 0 (left-grouped) = 13ⁿ is just this iterated.
Part X — The asymmetry: many-one forward, stipulated backward
The confusion raised: "any string of accents has Gödel number 0" — ′ ↦ 0, ′′′ ↦ 0, ′′′′′′′ ↦ 0 — yet E₀ is only ′. How is the asymmetry allowable?
Resolution: two maps, opposite directions, different natures.
- Forward (strings → numbers): total, many-one. All accent strings have digit string 00…0 = the number 0. Nor is 0 the only collision: ′0 has digits 01 = 1, colliding with "0" (digit 1). Every accent-initial string collides with its beheaded self. These collisions are permanent — the price, willingly paid, for accent → 0.
- Backward (numbers → strings): a chosen representative, not an inverse (a many-one map has none). For n > 0 the choice is automatic: n's base-13 numeral has no leading zero, so decoding yields the unique non-accent-initial string Eₙ. For n = 0 the fiber is {′, ′′, ′′′, …} and the book stipulates the spokesman: E₀ := ′.
Why the collisions are harmless: injectivity is needed only on strings that matter, and no grammatical syntax ever begins with an accent — accents always trail something. The orphaned strings are garbage, and garbage can share room numbers.
Why the single accent — the forcing, slowed to walking pace. The two sides of the bridge equation come from different sections and only one is negotiable:
- Frozen side: ∗ was defined in §4 by pure arithmetic, before numbering existed. x ∗ 0 = x·13^ℓ(0) + 0 = 13x, since the numeral "0" occupies one digit-slot. 6 ∗ 0 = 78, and nothing in §5 can change it.
-
Free side: which string is E₀ — our one open choice. The bridge equation, tested at y = 0, becomes a constraint on the choice. Candidate test with x = 6 (E₆ = v):
E₀ := ′ → v′ → digits 6 0 → 78 = 6 ∗ 0 survives E₀ := ′′ → v′′ → digits 6 0 0 → 1014 ≠ 78 dies
Appending a symbol is ×13 plus the symbol's digit; the accent's digit is 0, so one accent is exactly ×13 — one slot demanded by the frozen arithmetic, so the representative must be one symbol long. Forced.
Two nuances that fixed the in-session paraphrase:
- The direct calculus is never ambiguous — v′′ gets 1014 under any choice of E₀. "Two Gödel numbers for one expression" arises only from holding three commitments at once (direct rule + bridge equation + bad choice); the first two are non-negotiable, so the choice gives way. Same verdict, culprit properly indicted.
- The stipulation E₀ := ′ is not a patch that removes the collision — ′′ ↦ 0 stays true forever. It settles only the reverse lookup. Not "a bug fixed" but "an unavoidable many-one collapse, plus a forced choice of spokesman for 0."
The dissolving analogy: decimal already does this. Zero's spellings are 0, 00, 000, …; notation stipulates the canonical one — a single 0-digit. E₀ := ′ is that same convention wearing a Gödel code: the accent is the 0-digit, so zero's canonical spelling is one accent.
Part XI — What "base" means: Quine's 10, and the zeroless family
The confusion raised: Quine has 9 symbols — why base 10 and not base 9? Followed by: "if digits are 1–9, after 19 comes 21 — sounds like base 9 to me."
Resolution 1: the base is the carry law, not the count of digit-shapes used. Base b means: places worth 1, b, b², …, and a digit overflows at b (b units of one place = one unit of the next). Quine builds no new notation — he works in ordinary decimal, all ten digits existing, "53" meaning 5·10 + 3 as always. His ban is on the assignment table: no symbol gets code 0, so Gödel numbers are ordinary decimal numbers that happen to be zero-free. Numbers like 20 or 105 just aren't codes of anything — costless, since a numbering needs to be injective, not onto. In standard base 9 the digit "9" does not exist (digits stop at b−1 = 8), leaving eight nonzero digits for nine symbols: doesn't fit. The design space:
standard base b, ban 0: b−1 usable digits → 9 symbols need base 10 (Quine)
standard base b, harness 0: b usable digits → 13 symbols fit base 13 (Smullyan)
Resolution 2: "after 19 comes 21" is a real system — reinvented in session. Zeroless (bijective) base 9: digits 1–9, weight 9, no 0. Counting: …, "18" (=17), "19" (=18), "21" (=19). Every positive integer has a unique name — injectivity holds. Why nobody here uses it: §4's machinery was proved for standard notation, and the load-bearing squeeze b^(ℓ−1) ≤ n < b^ℓ fails in zeroless systems at the digit equal to the base. Concretely: y = 9 is a single digit ⟨9⟩ there, so 1 ∗ 9 = ⟨1⟩⟨9⟩ = 1·9 + 9 = 18, true shift 9; but "the smallest power of 9 greater than 9" is 81, and the superlative rule computes 1·81 + 9 = 90. Wrong number; Proposition 1 would need rebuilding from scratch. Both men stay standard because standard is what the theorem covers.
Part XII — Base 1: two machines, three deaths
The confusion raised: what IS base 1? Tally marks were the mental picture, yet "0, 00, 000 all worth zero" looked wrong.
Diagnosis: "base 1" is ambiguous between two machines, and the head was picturing them as one.
Machine A — standard base 1, the degenerate one. Feed b = 1 to the standard definition: digit set = {0, …, b−1} = {0}, one dead key; places worth 1⁰ = 1¹ = 1² = 1, no growth. Every typable string — 0, 00, 000 — is worth zero; the number 5 has no name. The weirdness felt was correct perception: this is not a notation with a strange flavor, it is the definition evaluated where it stops producing a notation. The overflow picture, run at b = 1: a digit overflows on reaching b = 1, so writing the number one puts a unit in the ones place, which instantly overflows to the next place, which instantly overflows… — the string inflates 0 → 00 → 000 while the value never moves off zero (each string still denotes zero, not nothing). The carry never rests because one unit of any place equals one unit of the next: 1 cannot be written; it is a permanent overflow rolling leftward. Growth without expression.
Machine B — tally (unary), from the other family. The b = 1 member of the zeroless family reinvented in Part XI: digit set {1}, the stroke. It works — |, ||, ||| name every positive quantity uniquely. But: no place values, no positions; in base 2 each digit answers a yes/no question ("is a 4 present?"), while a stroke answers a question with only one possible answer — a message with no alternatives carries no information. The quantity lives purely in length; the characters are the medium the length is made of. Position means nothing, length means everything — and "holding an emptiness that nonetheless expresses value" (the digit 0's job, isolated in session) is exactly the capability tally lacks. That capability IS positional notation.
The three deaths for §4 (any one suffices for b ≥ 2):
- Standard base 1 can't name numbers (one dead key, weights don't grow).
- The superlative finds no candidates: powers of 1 = {1}; "smallest power of 1 greater than 5" describes nothing; Step 2's total function evaporates.
- One digit shape can't distinguish thirteen symbols — coding needs position to carry information.
The unary Gödel-collision — constructed independently in session: assign ( ↦ 1 and ) ↦ 11; then () ↦ 111 and )( ↦ 111. Autopsy in §4 vocabulary: unary concatenation is addition, and addition commutes (1 + 11 = 11 + 1) — but concatenation of expressions must not commute. Any coding with commutative ∗ is dead on arrival; for b ≥ 2, the non-commutativity of ∗_b is the order-memory. The in-session binary repair — ( ↦ 1, ) ↦ 10, so () ↦ 110 ≠ 101 ↦ )( — is sound (every 0 closes a "10") and is exactly the multi-digit trick of Part XIII.
Part XIII — The coding theorem (beyond the book): any base b ≥ 2 codes any finite alphabet
The challenge raised: this claim was asserted, but Proposition 1 only proves ∗_b Arithmetic — where's the proof? Rightly demanded: Proposition 1 is a definability theorem; the coding claim is a combinatorial one. Different genre, and it isn't in the book. The missing theorem:
Claim. For b ≥ 2 and an alphabet of k symbols, there is an assignment of base-b digit strings to symbols such that (i) distinct symbol-strings get distinct Gödel numbers, and (ii) g.n.(XY) = x ∗_b y — whence, by Proposition 1, concatenation on codes is Arithmetic.
Proof — fixed-length codes (the dumbest thing that works). Give every symbol a codeword of the same length L, each beginning with a nonzero digit.
- Existence: such codewords number (b−1)·b^(L−1) — first digit b−1 ways, rest free — which grows without bound in L since b ≥ 2; pick L with (b−1)·b^(L−1) ≥ k. (At b = 1 the count is 0·1 = 0 at every L: the counting formula is the "one dead key" fact, killing b = 1 one last time.)
- Decodability: chop the digit string into L-blocks and look each up — fixed length makes unique readability free. No codeword starts with 0, so no leading zero evaporates.
- Bridge: digit-string(XY) = digit-string(X) ⌢ digit-string(Y) by construction; Y's digit string has no leading zero, so it IS the base-b numeral of y, and value(XY) = x·b^ℓ(y) + y = x ∗_b y. Proposition 1 finishes. ∎
The instance to remember: base 2, thirteen symbols → L = 5 (sixteen codewords 10000–11111, thirteen used). This is ASCII — fixed-width binary blocks, chop and look up — the scheme by which actual computers code all text as one long base-2 numeral. The Discussion's "base 13 is taste, not necessity" has been running in production for sixty years.
Footnotes: variable-length codes (the in-session {1, 10}; Smullyan's 1, 0, 2, …, 7, 89, 899, 8999, 89999, 899999 for base 10) are more economical but each needs its own unique-readability argument; fixed-length buys the proof free. Property 2 (numeral function) survives such schemes less prettily (append-accent = ×b^L + constant; closed form via E, ·, +, one ∃) — and Smullyan's promissory note that property 1 implies property 2 covers it wholesale, a couple of chapters hence.
The two IOUs the book itself signed: 13 is prime — technical advantages collected in a later chapter; and property 1 ⇒ property 2 — also later, resting on how numerals are built. Logged next to the standing E-elimination debt.
Part XIV — Distinctions Ledger
| Confusion raised | One-line resolution |
|---|---|
| Why n ≥ 1 in "b^ℓ(n) = smallest power of b > n"? Isn't 10 smallest at n = 0? | A competitor was left off the roster: 1 = 10⁰ is a power (witness y = 0 in Pow's own formula) and 1 > 0, so the superlative outputs 1, not 10 — wrong at exactly one input; hence the ∨-patch. |
| Which layer breaks at 0? | Layer 2 (shift-and-add) is fine — ℓ(0) = 1 gives m·10, the appended zero. Layer 3 (superlative) lies — the squeeze's left half, 10⁰ ≤ 0, is false. Root: "0" is the only numeral that is a leading zero. |
| Why strictly greater, not ≥? | They disagree exactly when n is itself a power of b (45 ∗₁₀ 100 → 4600 under ≥, wanted 45100) — and powers are legitimate arguments. |
| "Given a z" in Step 3 | Nothing gives z — it's one of the three free slots the condition itself mentions; the last conjunct ties scaffolding back to it. |
| Corollary = "just chaining"? | The chaining needs a license: the induction hypothesis is what certifies the length-n prefix expressible. Induction lives in the metatheory and yields infinitely many formulas F₂, F₃, … — necessarily (n+1 free slots each), and harmlessly (each syntactic operation glues a fixed number of pieces). |
| Quine has 9 symbols — why base 10, not 9? | Base = carry law / place weight, not the count of shapes used. Quine stays in ordinary decimal and merely assigns no symbol the digit 0; injective-not-onto is costless. Standard base 9 has only eight nonzero digits — nine symbols don't fit. |
| "After 19 comes 21 — sounds like base 9" | Reinvented zeroless (bijective) base 9 — a real system with unique names, but the squeeze fails at the digit equal to the base (1 ∗ 9: true 18, superlative computes 90), so §4's theorem doesn't cover it. |
| ′, ′′′, ′′′′′′′ all ↦ 0, yet E₀ = ′ only — asymmetry? | Forward map: total, many-one, collisions permanent. Backward map: not an inverse but a chosen representative; automatic for n > 0, stipulated at 0. |
| Why must E₀ be the single accent? | The bridge equation at y = 0: §4 froze x ∗ 0 = 13x (the numeral "0" is one digit), so appending E₀ must be ×13 exactly — one 0-digit, one accent. Candidate ′′ gives 1014 ≠ 78 = 6 ∗ 0 and dies. |
| "One expression, two Gödel numbers"? | Never within the calculus — v′′ gets 1014 under any choice. The clash is among three commitments (direct rule + bridge + bad choice); the choice is the negotiable one and gives way. |
| "A bug fixed by a patch"? | The collision ′′ ↦ 0 is permanent — willingly bought (numerals = 13ⁿ). The stipulation fixes only the reverse lookup: a spokesman for 0, like printing zero as "0" not "00". |
| Accent → 0 is necessary for Arithmetic numerals? | No — convenience: digit 5 would give 13ⁿ + 5(13ⁿ−1)/12, still Arithmetic but with a cleanup crew. Zero buys transparency ("as quickly as possible"). |
| What IS base 1? | Two machines. Standard: digit set {0}, weights all 1 — the number 1 is a permanent overflow rolling leftward; only 0 expressible. Tally: zeroless base 1 — position means nothing, length means everything; each stroke answers a question with one possible answer, zero information per character. |
| Why can't unary Gödel-number? | Unary concatenation is addition, which commutes — () and )( both ↦ 111 under ( ↦ 1, ) ↦ 11. Order-memory requires non-commutative ∗, which requires positions, which require b ≥ 2. |
| "Any base b ≥ 2 codes any alphabet" — proof? | Not Prop 1 (definability) but a combinatorial theorem: fixed-length codes, length L with (b−1)·b^(L−1) ≥ k, nonzero first digits; chop into blocks; bridge equation holds; Prop 1 finishes. Instance: ASCII (b = 2, L = 5 covers thirteen symbols). |
Part XV — Self-Test
Answer before peeking; the last three were assigned in session and are settled here for the first time.
- State the three layers that turn scribal concatenation into arithmetic, and prove the Layer-3 characterization via the squeeze.
- For which second arguments do "smallest power > n" and "smallest power ≥ n" disagree? Give the 45 ∗₁₀ 100 computation under each.
- Administer the superlative's test at n = 0 and show it outputs the wrong power. Which layer failed, and what is the root cause in terms of leading digits?
- Prove Proposition 1 in three steps. In Step 3, list free and bound variables and justify the count by the takeaway principle. Where exactly does the constant b enter the formulas?
- Quine's associativity failure: compute both groupings of 5 ∗₁₀ 0 ∗₁₀ 3, and state the convention that resolves the ambiguity.
- Corollary 1: give the induction, say where the induction lives, why it must produce infinitely many formulas, and why that's harmless for arithmetizing syntax.
- Write the thirteen-symbol/digit table from memory. Which two assignments are design decisions, and what does each buy?
- Encode ( 0 = 0 ): give the base-13 digit string and (optionally) the decimal value.
- Decode E₁₇₀: write 170 in base 13, then read the digits back into symbols.
- Explain g.n.(v′′) = g.n.(v)·13² using x ∗ 0, not digit-pictures.
- Why is E₀ the single accent and not ′′? Frozen side, free side, candidate test.
- Quine uses 9 symbols in base 10. Why not base 9? And what real system does "digits 1–9, after 19 comes 21" describe — and why doesn't §4 cover it?
- Base 1: name the two machines, show why the number 1 cannot be written in the standard one, and give the three independent deaths that justify b ≥ 2.
- State and prove the fixed-length coding theorem. What familiar real-world scheme is its (b = 2, L = 5)... (approximately L = 7/8) instance?
Answers
- Scribal (juxtapose numerals); shift-and-add (m ∗_b n = m·b^ℓ(n) + n — appending shifts m left ℓ(n) places); superlative (b^ℓ(n) = smallest power of b > n, for n ≥ 1). Squeeze: k-digit n satisfies b^(k−1) ≤ n < b^k (smallest k-digit number is b^(k−1), largest is b^k − 1), so b^k beats n and b^(k−1) doesn't — b^ℓ(n) is the smallest power beyond n, with no digit-counting in sight.
- Exactly at n = a power of b (a power has one more digit than its exponent's worth). Under ≥: 45·100 + 100 = 4600, wrong. Under >: smallest power beyond 100 is 1000, so 45·1000 + 100 = 45100, the true concatenation.
- Candidates: 1, 10, 100, … — all > 0, smallest is 1 = 10⁰ (witness y = 0 in ∃y(x = 10^y)). So the rule outputs 1, but ℓ(0) = 1 demands 10. Layer 3 failed (squeeze's left half: 1 ≤ 0 false); Layer 2 is fine (53 ∗ 0 = 530 by m·10¹). Root cause: 0 is the unique numeral that is a leading zero — every n ≥ 1 has a nonzero leading digit forcing b^(k−1) ≤ n.
- Step 1: Pow_b(x) iff ∃w(x = b̄ E w). Step 2: b^ℓ(x) = y iff (x = 0 ∧ y = b̄) ∨ (x ≠ 0 ∧ Pow_b(y) ∧ x < y ∧ ∀z((Pow_b(z) ∧ x < z) ⊃ y ≤ z)) — Exercise 5 with A = Pow_b; infinitude of Pow_b makes it total. Step 3: ∃z₁∃z₂(b^ℓ(y) = z₁ ∧ x·z₁ = z₂ ∧ z₂ + y = z). Free: x, y, z — the condition's own names; bound: z₁, z₂ — two invented intermediates, one ∃ each. b enters exactly twice: as b̄ in Pow_b and in the zero-patch — which is why the proof generalizes verbatim.
- (5 ∗ 0) ∗ 3 = 50 ∗ 3 = 503; 5 ∗ (0 ∗ 3) = 5 ∗ 3 = 53, since 0 ∗ 3 = 0·10² + 3 = 3 — the leading zero vanishes. Convention: associate left; x ∗ y ∗ z means (x ∗ y) ∗ z.
- F₂ is Prop 1; given Fₙ, the (n+1)-fold relation is ∃z(Fₙ(x₁,…,xₙ,z) ∧ z ∗ xₙ₊₁ = y) — the hypothesis licenses treating the prefix as expressible; left association licenses treating it as one number. The induction is metatheoretic, producing F₂, F₃, … — one formula per n, necessarily (n+1 free slots each). Harmless: each syntactic operation concatenates a fixed number of pieces (negation: ~, (, X, ) — n = 4).
- Symbols 0 ′ ( ) f , v ~ ⊃ ∀ = ≤ ♯ get digits 1 0 2 3 4 5 6 7 8 9 η ε δ. Decisions: accent → 0 (numerals code as 13ⁿ — transparency of the coding function) and 0 → 1 (numeral codes have leading digit 1, never a vanishing zero).
- ( 0 = 0 ) → digits 2 1 η 1 3 → 2·13⁴ + 1·13³ + 10·13² + 1·13 + 3 = 57122 + 2197 + 1690 + 13 + 3 = 61025.
- 170 = 1·169 + 0·13 + 1 → digits 1 0 1 → symbols 0 ′ 0: E₁₇₀ is the string 0′0 (ungrammatical — fine; every number names a string).
- Appending one accent is concatenating with E₀, and the frozen arithmetic says x ∗ 0 = x·13^ℓ(0) + 0 = 13x. So g.n.(v′′) = (6 ∗ 0) ∗ 0 = (6·13)·13 = 6·13² = g.n.(v)·13². One accent, one factor of 13; two accents, two.
- Frozen side: §4 defined ∗ before numbering existed — 6 ∗ 0 = 78, non-negotiable. Free side: the choice of E₀. Test with Eₓ = v: E₀ = ′ gives v′ = digits 60 = 78 = 6 ∗ 0, survives; E₀ = ′′ gives v′′ = digits 600 = 1014 ≠ 78, dies. The numeral "0" occupies one digit-slot, so the representative must occupy one symbol-slot; the accent is the only one-symbol string with g.n. 0.
- Base = carry law: places worth powers of ten, overflow at ten. Quine works in ordinary decimal and just assigns no symbol the code 0 — 9 symbols need 9 nonzero digits, and standard base 9 has only eight (digits stop at 8). "Digits 1–9, carry at nine" is zeroless (bijective) base 9 — unique names for all positive integers, but the squeeze fails at the digit equal to the base (1 ∗ 9 = 18 truly; superlative computes 90), so Prop 1's proof doesn't transfer.
- Standard base 1: digit set {0}, weights all 1 — writing 1 puts a unit in the ones place, which overflows at 1, sending a unit to an equally-weighted place, which overflows again: permanent leftward overflow, the string inflates 0 → 00 → 000 while denoting zero throughout. Tally: zeroless base 1, digit {1}; quantity = length; each character carries zero information. Deaths: (i) standard base 1 names only 0; (ii) powers of 1 = {1}, so "smallest power > y" describes nothing and Step 2 dies; (iii) one shape can't distinguish thirteen symbols — and unary ∗ is addition, which commutes, destroying order (( ↦ 1, ) ↦ 11 makes () and )( both 111).
- Fixed-length codes: choose L with (b−1)·b^(L−1) ≥ k; assign distinct length-L codewords with nonzero first digit. Decodability: chop into L-blocks (fixed length = unique readability free; no leading zeros evaporate). Bridge: digit-string(XY) = digits(X) ⌢ digits(Y), and Y's string is y's genuine numeral, so value = x·b^ℓ(y) + y = x ∗_b y; Prop 1 gives Arithmetic-ness. The b = 2 fixed-width instance is ASCII.
Part XVI — What's ahead in Smullyan, and the state of play
Position: Chapter II §4–§5 complete. Proposition 1 and Corollary 1 proved and narrated back; the thirteen-symbol numbering installed; x ∗ y now means x ∗₁₃ y permanently; the coding theorem proved as a supplement beyond the book.
Next: Part III of Chapter II — §6, Diagonalization and Gödel Sentences. The target is already on the page: T := the set of Gödel numbers of the true sentences of L_E — a perfectly definite set of natural numbers, thanks to this session's work. The chapter's question: is T Arithmetic? Tarski's theorem: no — truth is a set no formula can carve. The route: Gödel sentences (X is a Gödel sentence for A iff X is true ↔ g.n.(X) ∈ A — the machine-and-register pattern from Chapter I, now for real), and a diagonal construction due to Tarski that bypasses Gödel's heavy sub(x,y) substitution-arithmetic. The book promises the trick is "simple but clever"; the July 15 session's self-referential machine puzzle was the toy version.
Standing connections: Exercise 5 (July 20) was cashed in as Step 2 of Proposition 1 — the promised "for later" arrived one session later, with A = Pow_b and infinitude spent on totality. The free-variables-as-plug-points discipline carried the assembly step. The encode/decode losslessness standard (July 20's identity law) reappeared as: a Gödel numbering must be injective on the strings that matter, and E₀'s stipulation is choosing a canonical spelling — decimal's "print zero as 0," relocated.
The debt register, updated: (1) Gödel's E-elimination — x^y = z from + and · alone — still the hardest entry, owed by a later chapter. (2) New: why a prime base (13) has technical advantages — the book signs this IOU on p. 23. (3) New: property 1 (concatenation Arithmetic) implies property 2 (numeral function Arithmetic) — "not evident until a couple of chapters later."
The method, continued: this session's engine was the refusal to accept assertions at their altitude — why n ≥ 1? why base 10 for nine symbols? what is base 1 really? where is the proof that any base codes any alphabet? Twice the probing reinvented real mathematics (bijective numeration; uniquely decodable binary codes), and once it caught the tutor asserting past the book (the coding claim, which then had to be proved). The complementary lesson: when a paragraph feels mysterious ("the bridge equation forces it"), the cure is to run the test by hand with concrete numbers — 78 versus 1014 dissolved what prose couldn't. A formula defines through its ability to reject; so does an explanation.
End of session review · Smullyan, "Gödel's Incompleteness Theorems," Chapter II §4–§5 complete · Previous files: Godel-Incompleteness-Session-2026-07-15.md (Chapter 1 framework & machine puzzle), Godel-Incompleteness-Session-2026-07-17-Answer-Sheet.md (Chapter 1 exercises 1–7), Godel-Incompleteness-Session-2026-07-19.md (Chapter II §1–§2, language and truth), Godel-Incompleteness-Session-2026-07-20.md (Chapter II §3, Arithmetic sets/relations/functions, Exercises 2–5) · Next: Chapter II §6, Diagonalization and Gödel Sentences — Tarski's theorem.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
- 如何使用本文
- 第一部分——观念:构造全部句法的一个操作
- 第二部分——三个层次:抄写→移位相加→最小者
- 第三部分——n = 0的修补:漏掉的竞争者
- 第四部分——命题1及其证明:兑现习题5
- 第五部分——0的病症与左结合
- 第六部分——推论1:归纳位于哪里
- 第七部分——其他进制的具体例子
- 第八部分——§5:编号本身
- 第九部分——数码的收益:为什么撇号对应0
- 第十部分——不对称:正向多对一,反向靠规定
- 第十一部分——“底数”的意义:奎因的10,以及无零记数法家族
- 第十二部分——1进制:两台机器,三种死法
- 第十三部分——编码定理(书外补充):任何b ≥ 2都能编码任意有限字母表
- 第十四部分——区分清单
- 第十五部分——自测
- 第十六部分——斯穆里安后面的内容与当前进度
2026年7月21日学习记录 · 斯穆里安《哥德尔不完备性定理》,第二章§4(以b为底的拼接:命题1、推论1)与§5(哥德尔编号),并走到第三部分(§6,塔斯基定理)的门口 · 与2026年7月15、17、19、20日记录配套
如何使用本文
本文依照理解实际形成的顺序展开,每部分都预设前面的部分。复习时,第一次依序阅读第一至第十三部分;之后单看区分清单(第十四部分)就能完整回顾,自测(第十五部分)则检验是否真正掌握。本次与7月20日不同:不是围绕一个反复出现的错误交锋三轮,而是一串基础追问:为什么n ≥ 1?九个符号为什么用10进制?1进制究竟是什么?每个问题都有精确答案,其中两次追问以读者独立重新发明真正的数学而告终(无零记数法,第十一部分;多位二进制编码,第十三部分)。三个具体的编码/解码检查在整次学习中都为这些追问让路,现在在自测里解决并附上答案;先独立做,再看答案。
第一部分——观念:构造全部句法的一个操作
L_E的表达式是符号字符串,构造每个字符串的单一操作是并置,即把一个表达式写在另一个之后。本章的计划要求把句法概念(公式、语句、真)变成关于数的概念。分两步:
- §5:把符号变成数字,使字符串变成数。
- §4:证明字符串并置经由这种翻译,成为数上的算术操作。
§4先完成困难工作。以10为底的操作:m ∗₁₀ n=写下m,紧接着写n,读成一个数。53 ∗₁₀ 792 = 53792。问题在于,“先写m的数字,再写n的数字”是给抄写员的指令,不是L_E的公式。L_E没有数字,也没有“之后”。§4的全部任务就是让抄写操作脱去句法外衣,只用+、·、E、≤、=描述它。
这也是7月20日习题5暗中指向的地方:“x是A中大于y的最小元素”,原样成为命题1证明的步骤2,取A=b的幂。那次复习中标记的“以后有用”,今天兑现了。
第二部分——三个层次:抄写→移位相加→最小者
第一层(抄写):并置记号。把53放在792旁边。
第二层(移位相加):并置对数值做了什么。在53后面写792,使53向左移动三个十进制位,再相加:
53792 = 53·10³ + 792
移三位,因为792有三位数字。令ℓ_b(n)=n在b进制中的位数:
m ∗_b n = m·b^ℓ(n) + n
几乎已是算术,但ℓ还在说“数数字位数”,仍有一处句法残余。
第三层(最小者):其实不需要ℓ(n)本身,只需幂b^ℓ(n),而这个幂有纯粹的序论描述:
b^ℓ(n) = 大于n的最小b次幂 (n ≥ 1时)
书中的例子:10^ℓ(5368) = 10⁴ = 10000,是超过5368的最小10次幂。为什么有效:夹逼。b进制中有k位的数n满足:
b^(k−1) ≤ n < b^k
(最小k位数是1后接k−1个零,即b^(k−1);最大是b^k − 1。)所以b^k超过n,b^(k−1)已经不能超过:b^k = b^ℓ(n)就是大于n的最小幂。不再提数字,只提幂与顺序。
为什么严格“大于”,而非“≥”:本次已独立验证。取45 ∗₁₀ 100。≥100的最小幂是100自身,给出45·100 + 100 = 4600,错误;想要的是45100,需要乘数1000。两种读法恰好在n本身为b的幂时不一致(b的k次幂有k+1位,而非k位),而b的每个幂都是合法的第二自变量,因此必须严格大于。
第三部分——n = 0的修补:漏掉的竞争者
提出的困惑:为什么把第三层限制为n ≥ 1?10难道不是大于0的最小10次幂,从而正确给出1 ∗₁₀ 0 = 10吗?
诊断:名单漏掉了一个竞争者。在n = 0处亲手执行最小者检验:
10的幂: 1、10、100、1000、……
哪些大于0? 全部
最小? 1
因为1 = 10⁰也是10的幂。书中自己的公式就是凭据:Pow_b(x)当且仅当∃y(x = b^y),y = 0见证x = 1。最小者规则输出1,不是10;相信它就会得到1 ∗₁₀ 0 = 1·1 + 0 = 1,而“1”不是“1后接0”。
哪层坏了:第二层在n = 0处完全没问题。ℓ(0) = 1(数码“0”有一位),于是m·10^ℓ(0) + 0 = 10m,附加一个零,正确(53 ∗₁₀ 0 = 530)。失败的是第三层:夹逼的左半边崩溃(10⁰ ≤ 0就是1 ≤ 0,为假)。根因:0是唯一一个数码“配不上”自身位数的数;每个n ≥ 1若有k位,非零首位都会迫使n ≥ b^(k−1),而数码“0”是本身就为前导零的单个数字,是系统中唯一这种情况。本节所有0的病症都追溯到这里。
修补:分情况。最小者规则恰好只在一个输入处说谎,用∨修补它:
(y = 0 ∧ x = b̄) ∨ (y ≠ 0 ∧ [x是大于y的最小b次幂])
本次检验通过:未修补时,53 ∗₁₀ 0 = 53(吞掉零的拼接);修补后,530。
第四部分——命题1及其证明:兑现习题5
命题1。对每个b ≥ 2,关系x ∗_b y = z是算术的。
根据7月20日的核心原则:条件提及三个名称x、y、z,公式就必须恰有三个自由变量,每个辅助量各配一个∃。三步,每步都使用已有工具:
步骤1:Pow_b(x):∃w(x = b̄ E w)。一个自由空位(属于某集合),一个新引入的名称,一个∃。这正是“Arithmetic”中的大写A发挥作用之处,用到了E。(没有E是否还能成立,是欠账表中常驻的第三项:哥德尔的E消去,要由后面章节偿还。)
步骤2:关系b^ℓ(x) = y(书中的方向:x是被测数,y是幂)。当x ≥ 1时,它说:y是Pow_b中大于x的最小元素,原样就是习题5,取A := Pow_b:
Pow_b(y) ∧ x < y ∧ ∀z((Pow_b(z) ∧ x < z) ⊃ y ≤ z)
全部照搬:用⊃作条件(不用∧),让非幂的数空真地通过;Pow_b无限(b、b²、b³、……),所以每个x都有这样的y,关系是一个全函数的图,这正是步骤3需要的。(7月20日说“无限性使R成为全函数,以后有用”,所谓以后就是这里。)再加第三部分对x = 0的修补。
步骤3:组装。x ∗_b y = z展开为z = x·b^ℓ(y) + y。有两个中间值(幂、乘积),所以引入两个临时变量,用∧连接:
∃z₁∃z₂( b^ℓ(y) = z₁ ∧ x·z₁ = z₂ ∧ z₂ + y = z )
自由:x、y、z,条件自己的名称。约束:z₁、z₂,脚手架。每个合取项都算术(步骤2;两个原子等式);∧与∃保持算术性。∎
本次复述中两处更精确的说明:
- “给定一个z”:没有什么给出z。它就是三个自由空位之一;最后的合取项把脚手架接回它。这句话的说法,决定7月20日的教训是否真正保留。
- 自由变量就是代入点。步骤2证明了一个二元关系,空位为(被测数,幂);步骤3把y和z₁代入这些空位。一个关系被证明算术后,就能用新语境需要的任意名称重复使用;所以这些空位必须保持自由,这也是三步结构的全部节省之道。还要注意取哪个数的长度:y,即第二个自变量;x移多少位,由y需要多少空间决定。
证明从不做的事:数位数,或提及b进制记号。抄写员在元理论中为公式提供动机,公式自身只知道加、乘、幂与顺序。
第五部分——0的病症与左结合
对正数x、y、z,拼接满足结合律。但0的数码是唯一会消失的数码,因为前导零不属于标准记号。奎因的例子:
(5 ∗₁₀ 0) ∗₁₀ 3 = 50 ∗₁₀ 3 = 503
5 ∗₁₀ (0 ∗₁₀ 3) = 5 ∗₁₀ 3 = 53 因为0 ∗₁₀ 3 = 0·10² + 3 = 3
本次计算了二进制的孪生例子:(5 ∗₂ 0) ∗₂ 3 = 10 ∗₂ 3 = 43,但5 ∗₂ (0 ∗₂ 3) = 5 ∗₂ 3 = 23。任何底数,同一病症。
约定:没有括号的链按左结合,x ∗_b y ∗_b z意指(x ∗_b y) ∗_b z。三重关系多引入一个临时变量就算术:∃z₁(x ∗_b y = z₁ ∧ z₁ ∗_b z = w)。
第六部分——推论1:归纳位于哪里
推论1。对每个n ≥ 2(及每个b ≥ 2),关系x₁ ∗_b … ∗_b xₙ = y,作为(n+1)元关系,是算术的。
对n归纳,在元理论中进行。基础:n = 2就是命题1。步骤:假定n重关系算术(“前面的拼接得到z”所依赖的就是这一假设;没有它,就没有什么保证长度为n的前缀可表达),那么:
x₁ ∗_b … ∗_b xₙ₊₁ = y 当且仅当 ∃z( x₁ ∗_b … ∗_b xₙ = z ∧ z ∗_b xₙ₊₁ = y )
左结合在这里默默承担关键作用,正是它允许把前缀当作单个数z。∎
精确之处:归纳产生一个无穷的公式族F₂、F₃、F₄、……,每个固定n对应一个。单个公式不可能涵盖所有n:n重关系有n+1个自由空位,公式的自由空位数却固定。为什么无害:任何特定句法操作只拼接固定数量的部分。“否定X”是四块拼接:~、(、X、)。在n = 4时用推论1,一个公式就完成。没有人需要在一个公式内部包含“所有n”。
第七部分——其他进制的具体例子
二进制(5 = 101,6 = 110,3 = 11):
5 ∗₂ 6:抄写101⌢110 = 101110 = 46;公式:超过6的最小2次幂为8,所以5·8 + 6 = 46 ✓
(1 ∗₂ 2) ∗₂ 5 = 6 ∗₂ 5 = 53 = 1 ∗₂ (2 ∗₂ 5) ——全为正数时的结合律 ✓
13进制(数字0–12;用⟨·⟩表示较大数值的数字;24 = ⟨1⟩⟨11⟩):
7 ∗₁₃ 24:超过24的最小13次幂是169,所以7·169 + 24 = 1207
解码:1207 = 7·169 + 1·13 + 11 = ⟨7⟩⟨1⟩⟨11⟩ ——两个原项都完整保留,并排出现(无损性)
相同输入,不同底数:
5 ∗₂ 3 = 23 5 ∗₁₀ 3 = 53 5 ∗₁₃ 3 = 68
不存在独立于底数的数的拼接,只有数码的拼接,而数码预设底数。
b在证明中何处出现:恰好两次,Pow_b内部的数码b̄,以及y = 0的修补。把1̄0̄换成2̄或1̄3̄,整个证明原样重跑。从10推广到b,只是观察到论证没有使用10的任何特殊之处。
第八部分——§5:编号本身
13进制需要十三种数字形状;书中为十、十一、十二引入η、ε、δ。对应如下:
符号: 0 ′ ( ) f , v ~ ⊃ ∀ = ≤ ♯
数字: 1 0 2 3 4 5 6 7 8 9 η ε δ
两个有意的选择,所有微妙之处都由此而来:符号0对应数字1,撇号′对应数字0。
规则:把每个符号替换为对应数字,将所得字符串读作13进制数码。书中的例子:数字串“362”,即字符串) v (,命名3·13² + 6·13 + 2 = 587。两点教训:(i)“362”是数字串,命名哪个数取决于按什么底数读,这里总是13;(ii)) v (在语法上无意义,但没关系,每个字符串都获得一个数;“是公式”后来将成为数的性质(如果计划成功,就是算术集合)。
桥梁:§4在何处兑现,一行:
Eₓ E_y的哥德尔数 = x ∗₁₃ y
表达式拼接就是其哥德尔数上的∗₁₃:x的数字后接y的数字,以13进制读出,原样就是∗₁₃的定义。命题1(b = 13)说明该操作算术:构造全部句法的一个操作,现在成为ℕ上的算术关系。从这里起,书中永久用x ∗ y表示x ∗₁₃ y。
第九部分——数码的收益:为什么撇号对应0
数码n̄是符号0后接n个撇号→数字1后接n个零→按13进制读取:
n̄的哥德尔数 = 13ⁿ (检验:2̄ = 0′′ → 100₁₃ = 169 = 13²;甚至0̄ = “0” → 1 = 13⁰)
编码函数n ↦ g.n.(n̄)必须算术,而13ⁿ显然算术:其图由m = 1̄3̄ E n表达;按照核心原则,有两个自由空位。
必要性与便利性,本次进一步精确:撇号→0不是使函数算术,而是使它显然算术。如果撇号对应数字5,数码编码将为13ⁿ + 5·(13ⁿ − 1)/12,较复杂,但仍可由E、·、+及一个用于除法的∃构造,仍是算术的。零撇号买来的是直接性(一个E项,无需善后),不是可能性。书中自己的话是:选择此编号,是为“尽可能快地”确保它的两个性质。
而§4的病症成了功能:x ∗ 0 = x·13^ℓ(0) + 0 = 13x。编码乘13就是附加一个0数字,即附加一个撇号。在§4破坏结合律的操作,现在成了后继符号的施加器;g.n.(n̄) = 1 ∗ 0 ∗ 0 ∗ … ∗ 0(左结合)= 13ⁿ,不过是它的迭代。
第十部分——不对称:正向多对一,反向靠规定
提出的困惑:“任意撇号串的哥德尔数都是0”,′ ↦ 0、′′′ ↦ 0、′′′′′′′ ↦ 0,但E₀却只有′。这种不对称怎么能被允许?
解决:两个映射,方向相反,性质不同。
- 正向(字符串→数):全映射,多对一。所有撇号串的数字串都是00…0=数0。0也不是唯一碰撞:′0的数字为01=1,与“0”(数字1)碰撞。每个以撇号开头的串,都与去掉首部撇号后的自身碰撞。这些碰撞永久存在,是为撇号→0自愿付出的代价。
- 反向(数→字符串):选定代表,不是逆映射(多对一映射没有逆)。n > 0时,选择自动确定:n的13进制数码没有前导零,所以解码得到唯一不以撇号开头的串Eₙ。n = 0时,原像为{′、′′、′′′、……},书中规定代言者:E₀ := ′。
为什么碰撞无害:只有重要的字符串需要单射,而合乎语法的句法绝不以撇号开头,撇号总跟在某物之后。孤零零的那些串是无意义的,无意义的串可以共用房号。
为什么是单个撇号:把强制过程放慢。桥梁等式的两边来自不同小节,只有一边可以商量:
- 冻结的一边:∗在§4就由纯算术定义了,那时还没有编号。x ∗ 0 = x·13^ℓ(0) + 0 = 13x,因为数码“0”占一个数字位。6 ∗ 0 = 78,§5无论做什么都不能改变它。
-
可自由选择的一边:哪个串是E₀,这是唯一开放的选择。在y = 0处测试桥梁等式,就成为对选择的约束。取x = 6(E₆ = v)检查候选:
E₀ := ′ → v′ → 数字6 0 → 78 = 6 ∗ 0 通过 E₀ := ′′ → v′′ → 数字6 0 0 → 1014 ≠ 78 失败
附加一个符号就是×13再加该符号的数字;撇号的数字是0,所以一个撇号恰好是×13,冻结的算术要求一位,因此代表必须只有一个符号。这是被迫的。
修正本次转述的两个细节:
- 直接计算从不歧义:无论怎样选E₀,v′′都得到1014。“一个表达式有两个哥德尔数”只在同时坚持三个承诺时出现(直接规则+桥梁等式+错误选择);前两项不能让步,所以让步的是选择。结论相同,但责任归属准确了。
- 规定E₀ := ′不是消除碰撞的补丁,′′ ↦ 0永远仍为真。它只解决反向查找。不是“修复一个错误”,而是“不可避免的多对一塌缩,加上被迫为0选择代言者”。
化解困惑的类比:十进制本来就在做这件事。零的写法有0、00、000、……;记号规定其中规范的一个,即单个数字0。E₀ := ′就是同一约定披上哥德尔编码:撇号是数字0,所以零的规范写法是单个撇号。
第十一部分——“底数”的意义:奎因的10,以及无零记数法家族
提出的困惑:奎因有9个符号,为什么用10进制,不用9进制?接着又问:“如果数字是1–9,19之后是21,这听着就是9进制。”
解决1:底数是进位规则,不是所用数字形状的数量。底数b意指位值1、b、b²、……,数字达到b时进位(某位b个单位=下一位一个单位)。奎因没有建立新记数法,他用普通十进制,十个数字全都存在,“53”始终表示5·10 + 3。他的禁令只针对对应表:没有符号分配到编码0,所以哥德尔数是恰好不含零的普通十进制数。20或105这类数不是任何东西的编码,这没有代价,因为编号需要单射,不需要满射。标准9进制里没有数字“9”(到b−1 = 8为止),只有八个非零数字,却要容纳九个符号,不够。设计空间如下:
标准b进制,禁用0: b−1个可用数字 → 9个符号需要10进制 (奎因)
标准b进制,利用0: b个可用数字 → 13个符号可用13进制 (斯穆里安)
解决2:“19之后是21”是真正的系统,本次重新发明了它。无零(双射)9进制:数字1–9,位权9,没有0。计数:……“18”(=17)、“19”(=18)、“21”(=19)。每个正整数有唯一名称,单射成立。这里没人用它,是因为§4的机制针对标准记号证明,而关键的夹逼b^(ℓ−1) ≤ n < b^ℓ,在无零系统中遇到等于底数的数字就失效。具体说:y = 9在那里是单个数字⟨9⟩,所以1 ∗ 9 = ⟨1⟩⟨9⟩ = 1·9 + 9 = 18,真正的移位乘数是9;但“大于9的最小9次幂”是81,最小者规则计算出1·81 + 9 = 90。数错了,命题1需要从头重建。两位作者都留在标准记法中,因为定理涵盖的是标准记法。
第十二部分——1进制:两台机器,三种死法
提出的困惑:1进制究竟是什么?脑中的画面是刻痕计数,但“0、00、000全值为零”看起来不对。
诊断:“1进制”在两台机器之间歧义,脑中却把它们当成一台。
机器A:标准1进制,退化的那台。把b = 1代入标准定义:数字集={0, …, b−1}={0},只有一个无效键;位值1⁰ = 1¹ = 1² = 1,没有增长。每个可打出的串——0、00、000——都值零;数5没有名称。感到怪异是正确知觉:这不是一种风味奇特的记数法,而是定义在不再产生记数法之处求值的结果。在b = 1处运行进位图景:数字达到b = 1就进位,所以写数一,就是在个位放一个单位,它立即进到下一位,下一位又立即进位……字符串不断膨胀0 → 00 → 000,数值却从不离开零(每个字符串仍然指称零,不是不指称任何东西)。进位永不停止,因为任一位的一个单位都等于下一位的一个单位:1写不出来,它是不断向左滚动的永久进位。有增长,没有表达。
机器B:来自另一家族的刻痕计数(一元记数)。即第十一部分重新发明的无零家族中b = 1的成员:数字集{1},就是一笔。它有效,|、||、|||唯一命名每个正数量。但没有位值,没有位置;二进制中每个数字回答一个是/否问题(“有没有一个4?”),而一笔回答的是只有一个可能答案的问题,没有备选项的信息不携带信息。数量纯粹存在于长度,字符是长度所由构成的媒介。位置什么都不表示,长度表示一切;而“保留一个仍能表达数值的空位”(本次分离出的数字0的作用),恰好是一元计数欠缺的能力。那个能力就是位值记数法。
对§4的三种死法(任一种都足以要求b ≥ 2):
- 标准1进制不能命名数(只有一个无效键,位权不增长)。
- 最小者找不到候选:1的幂={1};“大于5的最小1次幂”不描述任何东西;步骤2的全函数消失。
- 一种数字形状无法区分十三个符号,编码需要位置携带信息。
一元哥德尔编码的碰撞,本次独立构造:指定( ↦ 1、) ↦ 11,那么() ↦ 111,)( ↦ 111。用§4词汇剖析:一元拼接就是加法,而加法可交换(1 + 11 = 11 + 1),但表达式拼接不能交换。∗可交换的编码从一开始就注定失败;b ≥ 2时,∗_b的非交换性就是顺序记忆。本次的二进制修补——( ↦ 1、) ↦ 10,因而() ↦ 110 ≠ 101 ↦ )(——是正确的(每个0结束一个“10”),恰好就是第十三部分的多位技巧。
第十三部分——编码定理(书外补充):任何b ≥ 2都能编码任意有限字母表
提出的质疑:这个主张被直接断言了,但命题1只证明∗_b算术,证明在哪里?这个要求完全正当:命题1是可定义性定理,编码主张则是组合定理,类型不同,而且不在书中。缺失的定理如下:
主张。对b ≥ 2及一个有k个符号的字母表,存在把b进制数字串分配给符号的方法,使(i)不同符号串获得不同哥德尔数;(ii)g.n.(XY) = x ∗_b y。因此由命题1,编码上的拼接是算术的。
证明:定长编码(能奏效的最笨办法)。给每个符号同样长度L的码字,每个都以非零数字开头。
- 存在性:这种码字有(b−1)·b^(L−1)个,首位有b−1种,其余任意;因b ≥ 2,数量随L无界增长。选L使(b−1)·b^(L−1) ≥ k。(b = 1时,每个L的计数都为0·1 = 0;这个计数公式正是“一个无效键”的事实,最后再杀死一次b = 1。)
- 可解码性:把数字串切成长度L的块,逐块查表;固定长度免费带来唯一可读性。没有码字以0开头,所以不会丢失前导零。
- 桥梁:按构造,digit-string(XY) = digit-string(X) ⌢ digit-string(Y)。Y的数字串没有前导零,所以它就是y的b进制数码,value(XY) = x·b^ℓ(y) + y = x ∗_b y。命题1完成证明。∎
值得记住的实例:二进制、十三个符号→L = 5(10000–11111共十六个码字,取十三个)。这就是ASCII:定宽二进制块,切块查表;现实计算机正是这样把全部文本编码成一个长二进制数码。讨论中“13进制是偏好,不是必要”的观点,已在实际系统中运行六十年。
注脚:变长编码(本次的{1, 10};斯穆里安为10进制给出的1、0、2、……、7、89、899、8999、89999、899999)更经济,但每种都需自己的唯一可读性论证;定长把证明免费买来。性质2(数码函数)在这种方案下仍成立,只是不那么漂亮(附加撇号=×b^L+常数;用E、·、+与一个∃给封闭形式)。斯穆里安承诺的“性质1蕴涵性质2”会在几章后整体覆盖它。
书本自己签下的两张欠条:13是素数,技术优势在后面章节兑现;性质1⇒性质2,也在后面,依赖数码的构造方式。与常驻的E消去欠账一起记录。
第十四部分——区分清单
| 提出的困惑 | 一行解决 |
|---|---|
| “b^ℓ(n)=大于n的最小b次幂”为什么要求n ≥ 1?n = 0时最小不是10吗? | 名单漏了一个竞争者:1 = 10⁰是幂(Pow自身公式中y = 0为见证),且1 > 0,所以最小者输出1而非10。恰好一个输入错误,因此用∨修补。 |
| 哪层在0处失败? | 第二层(移位相加)没问题,ℓ(0) = 1给出m·10,即附加零。第三层(最小者)说谎,夹逼左半边10⁰ ≤ 0为假。根因:“0”是唯一自己就是前导零的数码。 |
| 为什么严格大于,不是≥? | 恰好在n本身为b的幂时不同(45 ∗₁₀ 100在≥下给4600,想要45100),而幂是合法自变量。 |
| 步骤3的“给定一个z” | 没有东西给出z,它是条件自己提及的三个自由空位之一;最后的合取项把脚手架接回它。 |
| 推论就是“直接串起来”? | 串接需要许可:归纳假设保证长度n的前缀可表达。归纳位于元理论,给出无穷多个公式F₂、F₃、……;这是必要的(每个有n+1个自由空位),也是无害的(每个句法操作拼接固定数量的部分)。 |
| 奎因有9个符号,为何用10进制,不用9进制? | 底数=进位规则/位权,不是形状使用数。奎因保留普通十进制,只是不把数字0分给任何符号;单射而非满射不费代价。标准9进制只有八个非零数字,容不下九个符号。 |
| “19之后21,听着是9进制” | 重新发明了无零(双射)9进制,是真正的系统,有唯一名称;但夹逼在等于底数的数字处失败(1 ∗ 9实际为18,最小者算出90),所以§4的定理不涵盖它。 |
| ′、′′′、′′′′′′′都↦0,却只有E₀ = ′,不对称? | 正向映射:全、多对一,碰撞永久存在。反向映射:不是逆,而是选定代表;n > 0自动确定,0处靠规定。 |
| 为什么E₀必须是单个撇号? | y = 0时的桥梁等式:§4冻结了x ∗ 0 = 13x(数码“0”有一位),所以附加E₀必须恰好×13,一个0数字、一个撇号。候选′′给1014 ≠ 78 = 6 ∗ 0,失败。 |
| “一个表达式,两个哥德尔数”? | 计算本身从不如此,无论怎样选择,v′′都得1014。冲突发生在三个承诺间(直接规则+桥梁+坏选择);选择是可商量的,所以它让步。 |
| “用补丁修复错误”? | 碰撞′′ ↦ 0永久存在,是自愿购买的(数码=13ⁿ)。规定只修复反向查找:给0选代言者,就像零打印为“0”而不是“00”。 |
| 撇号→0是数码算术性的必要条件? | 不,是便利。数字5会给13ⁿ + 5(13ⁿ−1)/12,仍算术,但需善后。零买来清晰直接(“尽可能快”)。 |
| 1进制究竟是什么? | 两台机器。标准记法:数字集{0},位权全1;数1是不断向左滚动的永久进位,只能表达0。刻痕计数:无零1进制;位置不表示任何东西,长度表示一切;每笔回答只有一个可能答案的问题,每字符信息为零。 |
| 为什么一元记数不能作哥德尔编号? | 一元拼接是可交换的加法,在( ↦ 1、) ↦ 11下,()与)(都↦111。顺序记忆要求∗非交换,非交换需要位置,位置需要b ≥ 2。 |
| “任何b ≥ 2都能编码任何字母表”,证明呢? | 不是命题1(可定义性),而是组合定理:固定长度L,满足(b−1)·b^(L−1) ≥ k,首位非零;切块;桥梁等式成立;命题1完成。实例:ASCII(b = 2,L = 5足以覆盖十三个符号)。 |
第十五部分——自测
先回答,再看答案;最后三项在本次学习中布置,现在首次解决。
- 陈述把抄写拼接变成算术的三个层次,并用夹逼证明第三层刻画。
- 对哪些第二自变量,“大于n的最小幂”与“大于等于n的最小幂”不同?分别计算45 ∗₁₀ 100。
- 在n = 0处执行最小者检验,说明它输出错误的幂。哪层失败?从首位数字看,根因是什么?
- 分三步证明命题1。在步骤3列出自由与约束变量,依据核心原则说明数量。常数b究竟在公式哪里出现?
- 奎因的结合律失败:计算5 ∗₁₀ 0 ∗₁₀ 3的两种分组,陈述消除歧义的约定。
- 推论1:给出归纳,说明归纳位于哪里、为什么必须产生无穷多个公式,以及为什么这对句法算术化无害。
- 凭记忆写出十三个符号与数字的对应表。哪两项是设计决定,各换来什么?
- 编码( 0 = 0 ):给出13进制数字串,可选算出十进制数值。
- 解码E₁₇₀:把170写成13进制,再把数字读回符号。
- 用x ∗ 0解释g.n.(v′′) = g.n.(v)·13²,不要用数字图像。
- 为什么E₀是单个撇号而非′′?说明冻结的一边、自由的一边,并检验候选。
- 奎因在10进制中使用9个符号,为什么不用9进制?“数字1–9,19之后21”描述哪个真实系统,又为何§4不涵盖它?
- 1进制:说出两台机器,说明为什么标准版本写不出数1,再给出支持b ≥ 2的三种独立死法。
- 陈述并证明定长编码定理。哪种熟悉的现实方案是它的(b = 2, L = 5)……(大约L = 7/8)实例?
答案
- 抄写(并置数码);移位相加(m ∗_b n = m·b^ℓ(n) + n,附加使m左移ℓ(n)位);最小者(n ≥ 1时,b^ℓ(n)=大于n的最小b次幂)。夹逼:k位数n满足b^(k−1) ≤ n < b^k(最小k位数为b^(k−1),最大为b^k − 1),故b^k超过n而b^(k−1)不超过,b^ℓ(n)就是大于n的最小幂,不再需要数数字位数。
- 恰好在n为b的幂时(幂的位数比指数多一)。用≥:45·100 + 100 = 4600,错误。用>:超过100的最小幂为1000,所以45·1000 + 100 = 45100,真正的拼接。
- 候选:1、10、100、……全都>0,最小是1 = 10⁰(∃y(x = 10^y)中见证y = 0)。规则输出1,但ℓ(0) = 1要求10。第三层失败(夹逼左半边1 ≤ 0为假);第二层没问题(由m·10¹,53 ∗ 0 = 530)。根因:0是唯一自己就是前导零的数码;每个n ≥ 1都有非零首位,迫使b^(k−1) ≤ n。
- 步骤1:Pow_b(x)当且仅当∃w(x = b̄ E w)。步骤2:b^ℓ(x) = y当且仅当(x = 0 ∧ y = b̄) ∨ (x ≠ 0 ∧ Pow_b(y) ∧ x < y ∧ ∀z((Pow_b(z) ∧ x < z) ⊃ y ≤ z)),即习题5取A = Pow_b;Pow_b无限使它全定义。步骤3:∃z₁∃z₂(b^ℓ(y) = z₁ ∧ x·z₁ = z₂ ∧ z₂ + y = z)。自由:x、y、z,条件自身的名称;约束:z₁、z₂,两个新引入中间量,各有一个∃。b恰好出现两次:Pow_b中的b̄,以及零的修补中,所以证明能原样推广。
- (5 ∗ 0) ∗ 3 = 50 ∗ 3 = 503;5 ∗ (0 ∗ 3) = 5 ∗ 3 = 53,因为0 ∗ 3 = 0·10² + 3 = 3,前导零消失。约定:左结合;x ∗ y ∗ z意指(x ∗ y) ∗ z。
- F₂是命题1;已知Fₙ,(n+1)重关系是∃z(Fₙ(x₁,…,xₙ,z) ∧ z ∗ xₙ₊₁ = y)。假设许可把前缀当作可表达,左结合许可把它当作一个数。归纳在元理论中,产生F₂、F₃、……,每个n一个公式,这是必然的(每个n+1个自由空位)。无害:每个句法操作只拼接固定数量部分(否定:~、(、X、),n = 4)。
- 符号0 ′ ( ) f , v ~ ⊃ ∀ = ≤ ♯对应数字1 0 2 3 4 5 6 7 8 9 η ε δ。决定:撇号→0(数码编码为13ⁿ,编码函数清晰直接),0→1(数码编码首位为1,绝不会是消失的零)。
- ( 0 = 0 )→数字2 1 η 1 3→2·13⁴ + 1·13³ + 10·13² + 1·13 + 3 = 57122 + 2197 + 1690 + 13 + 3 = 61025。
- 170 = 1·169 + 0·13 + 1→数字1 0 1→符号0 ′ 0:E₁₇₀是字符串0′0(不合语法,没关系,每个数都命名一个字符串)。
- 附加一个撇号就是与E₀拼接,而冻结的算术说x ∗ 0 = x·13^ℓ(0) + 0 = 13x。所以g.n.(v′′) = (6 ∗ 0) ∗ 0 = (6·13)·13 = 6·13² = g.n.(v)·13²。一个撇号,一个13因子;两个撇号,两个因子。
- 冻结的一边:§4在编号出现前就定义∗,6 ∗ 0 = 78,不可更改。自由的一边:E₀的选择。用Eₓ = v测试:E₀ = ′给v′=数字60=78=6 ∗ 0,通过;E₀ = ′′给v′′=数字600=1014 ≠ 78,失败。数码“0”占一个数字位,所以代表必须占一个符号位;撇号是唯一哥德尔数为0的单符号字符串。
- 底数=进位规则:位值是十的幂,达到十进位。奎因在普通十进制中工作,只是不把编码0分给任何符号;9个符号需要9个非零数字,而标准9进制只有八个(到8为止)。“数字1–9,逢九进位”是无零(双射)9进制,所有正整数都有唯一名称,但夹逼在等于底数的数字处失败(1 ∗ 9实际为18,最小者算出90),所以命题1的证明不能转移。
- 标准1进制:数字集{0},位权全1。写1,就是在个位放一个单位,它达到1就进位,把单位送到同权重的下一位,那里再次进位;永久向左进位,字符串膨胀0 → 00 → 000,却始终指称零。刻痕计数:无零1进制,数字{1},数量=长度,每个字符携带零信息。死法:(i)标准1进制只命名0;(ii)1的幂={1},所以“大于y的最小幂”不描述任何东西,步骤2失败;(iii)一种形状不能区分十三个符号,而且一元∗是可交换的加法,破坏顺序(( ↦ 1、) ↦ 11使()与)(都成为111)。
- 定长编码:选L使(b−1)·b^(L−1) ≥ k;分配不同的长度L、首位非零的码字。可解码性:切成L块(定长免费保证唯一可读性,前导零不会消失)。桥梁:digit-string(XY) = digits(X) ⌢ digits(Y),而Y的字符串就是y真正的数码,所以值=x·b^ℓ(y) + y = x ∗_b y;命题1给出算术性。b = 2的定宽实例就是ASCII。
第十六部分——斯穆里安后面的内容与当前进度
位置:第二章§4–§5完成。命题1、推论1已证明且能复述;十三符号编号已建立;x ∗ y从此永久表示x ∗₁₃ y;编码定理作为书外补充得到证明。
下一步:第二章第三部分§6,对角化与哥德尔语句。目标已经在纸上:T := L_E真语句的哥德尔数集合。由于本次工作,它是完全确定的自然数集合。本章的问题:T算术吗?塔斯基定理:不。真是任何公式都无法划出的集合。路线:哥德尔语句(X是A的哥德尔语句,当且仅当X真↔g.n.(X) ∈ A;第一章机器与登记表的模式,现在来真的),以及塔斯基的一种对角构造,绕开哥德尔繁重的sub(x,y)代入算术。书中承诺技巧“简单而巧妙”,7月15日的自指机器谜题是它的玩具版本。
持续的联系:习题5(7月20日)在命题1的步骤2兑现,承诺的“以后有用”只隔了一次学习就到了:A = Pow_b,无限性用来保证全定义。自由变量作为代入点的纪律支撑了组装步骤。编码/解码的无损性标准(7月20日的同一律)重新表现为:哥德尔编号必须在重要的字符串上单射;E₀的规定是选规范写法,即十进制“把零打印为0”的迁移。
更新后的欠账表:(1)哥德尔的E消去,即只用+与·表达x^y = z,仍是最难的一项,由后面章节偿还。(2)新增:素数底(13)为什么有技术优势,书中第23页签下此欠条。(3)新增:性质1(拼接算术)蕴涵性质2(数码函数算术),“要再过几章才明显”。
继续沿用的方法:本次动力是拒绝在断言所处的高度直接接受它:为什么n ≥ 1?九符号为什么用10进制?1进制究竟是什么?任何底数都能编码任何字母表,证明在哪?两次追问重新发明了真正的数学(双射记数法、唯一可解码的二进制编码),一次抓住了讲解者超出书本作断言(编码主张,随后不得不证明)。互补的教训是:当一段话令人困惑(“桥梁等式迫使它如此”),补救就是用具体数字亲手测试;78与1014化解了文字无法化解的困惑。公式通过拒绝的能力来定义,解释亦然。
本次复习结束 · 斯穆里安《哥德尔不完备性定理》第二章§4–§5完成 · 前序文件:Godel-Incompleteness-Session-2026-07-15.md(第一章框架与机器谜题)、Godel-Incompleteness-Session-2026-07-17-Answer-Sheet.md(第一章习题1–7)、Godel-Incompleteness-Session-2026-07-19.md(第二章§1–§2,语言与真)、Godel-Incompleteness-Session-2026-07-20.md(第二章§3,算术集合/关系/函数,习题2–5)· 下一步:第二章§6,对角化与哥德尔语句,塔斯基定理。