Gui Ruiyan

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 / 篇目

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:

  1. §5: turn symbols into digits, so strings become numbers.
  2. §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:

  1. 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.
  2. 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):

  1. Standard base 1 can't name numbers (one dead key, weights don't grow).
  2. The superlative finds no candidates: powers of 1 = {1}; "smallest power of 1 greater than 5" describes nothing; Step 2's total function evaporates.
  3. 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.

  1. State the three layers that turn scribal concatenation into arithmetic, and prove the Layer-3 characterization via the squeeze.
  2. For which second arguments do "smallest power > n" and "smallest power ≥ n" disagree? Give the 45 ∗₁₀ 100 computation under each.
  3. 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?
  4. 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?
  5. Quine's associativity failure: compute both groupings of 5 ∗₁₀ 0 ∗₁₀ 3, and state the convention that resolves the ambiguity.
  6. 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.
  7. Write the thirteen-symbol/digit table from memory. Which two assignments are design decisions, and what does each buy?
  8. Encode ( 0 = 0 ): give the base-13 digit string and (optionally) the decimal value.
  9. Decode E₁₇₀: write 170 in base 13, then read the digits back into symbols.
  10. Explain g.n.(v′′) = g.n.(v)·13² using x ∗ 0, not digit-pictures.
  11. Why is E₀ the single accent and not ′′? Frozen side, free side, candidate test.
  12. 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?
  13. 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.
  14. 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

  1. 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.
  2. 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.
  3. 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.
  4. 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. (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.
  6. 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).
  7. 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).
  8. ( 0 = 0 ) → digits 2 1 η 1 3 → 2·13⁴ + 1·13³ + 10·13² + 1·13 + 3 = 57122 + 2197 + 1690 + 13 + 3 = 61025.
  9. 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).
  10. 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.
  11. 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.
  12. 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.
  13. 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).
  14. 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.