Gui Ruiyan

Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理

Study journals ·

Gödel's Incompleteness — Chapter IV: Arithmetic Without the Exponential (Theorem E, and Exercise 1)

Reflections · Study sessions

AI-prepared recaps of study sessions; these are working notes, not verbatim transcripts. / AI 整理的学习记录,并非逐字实录。

Reading / 研读:Raymond Smullyan / 雷蒙德·斯穆里安 · Gödel’s Incompleteness Theorems 哥德尔不完备性定理

In this note / 篇目

Study session of July 27, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter IV, book pp. 40–50 (§1 The Incompleteness of P.A., §2 Σ₀/Σ₁/Σ, §3 Concatenation to a Prime Base, §4 The Finite Set Lemma, §5 Proof of Theorem E, §6 sighted) · Companion to the sessions of July 15, 17, 19–24 (with 25 continuations), and 26 · Character: a strategy session that turned into a formalization session. The reader asked why the chapter exists at all, then for the central strategy of the proof of Theorem E, then — through four successive format rejections — forced the chain into a shape now judged the best of the sequence: GOAL + citable glossary + hallmark steps, each step opening with the load it bears, every formula parsed block-by-block into its semantic content, every justification citing labeled grounds. Part V prints that chain in full; Part 0 records the format war, which is itself a result.


The punchline of the chapter

{+, ·} is the exact threshold of incompleteness. Chapter III proved P.E. incomplete, but its Gödel sentence contains the symbol E — the proof says nothing about the weaker system P.A. (P.E. minus E, minus the two E-axioms N₁₀–N₁₁). And the question is genuinely open on both sides, because below the threshold completeness actually happens: arithmetic with + alone (Presburger) and with · alone (Skolem) are each complete and decidable. So "drop E" is not a formality — it is the last step down before incompleteness disappears. Theorem E closes the question from above: x^y = z is Σ₁ — definable from + and · alone — so everything Chapter III built out of E can be rebuilt inside P.A., and P.A. is incomplete (§6). The deeper moral: E was never a source of expressive power, only a convenience; the true source is that + and · together can code finite sequences, and that is where the whole recursion tower (succession → addition → multiplication → exponentiation → …) collapses into definability.


How to use this document

Parts I–IV rebuild, in the order the session built it, why the proof has the shape it has — threshold, obstruction, circularity scare, delimiter problem. Part V is the deliverable: the complete proof of Theorem E as a justified chain in the final format. Part VI is Exercise 1, graded and then done properly. The Ledger (Part VIII) is the refresher; the Self-Test (Part IX) tells you whether it took. One standing flag: Part V's coding deviates from the book's (digit-2 guards instead of pure 1-frames) — the deviation is announced where it starts (S8) and cashed where it pays (S9, S12–S15); the interface to the rest of the proof is identical to the book's Lemma K. The book-check it generates is registered in Part X.


Part 0 — The format war (method result)

Four versions of the same proof were rejected before one stuck; each rejection isolated a rule. The failures, in order:

  1. Metaphor terms doing load-bearing work — "smearing," "junk-tolerance," "recognized never computed," "the single cut severing E." The reader: "you are to explain things, not to explain terms by other unexplained terms." July 24's third failure mode (metaphor stacking), relapsed and re-caught. Every such phrase either got a definition and a label, or got expanded into the steps it was compressing and deleted.
  2. A background-facts block (B1–B3) stating positional notation, primes, recursion equations as numbered assumptions. Rejected as clutter: facts of that grade are used inline with a one-line reason at the point of use, not enthroned up front. Only load-bearing, citable items deserve labels.
  3. Goal-free rigor. The clean version dropped the GOAL/obligations scaffolding, and was rejected for exactly that: rigor without a stated destination is unreadable in a different way.
  4. Function stated late. Hallmark propositions must open with what load they bear — what the step is for, cited forward — before the formula, not as an afterthought.

The settled shape (the reader: "far superior to earlier shapes and much more intelligible"):

  • GOAL first: the theorem, a target shape (what "done" looks like, as checkable conditions T1, T2, …), and a decomposition into obligations G1, G2, … with each chain step tagged by the obligation it serves.
  • Glossary of citable definitions before any argument (July 24's tool, kept).
  • Hallmark steps S1, S2, … — each opens with its load, then the formula, then a block-by-block parse table: every syntactic chunk of the string on the left, what it says semantically on the right, with the grounds cited. Then the claim and proof, every justification naming earlier labels.
  • Arithmetic parsed as strings: expressions like m·w + n, 12·m + 1, 2∗f∗f∗2 are read off at the digit level (what string does this arithmetic build?), since in this chapter numbers are their base-13 strings.

Part I — Why "without the exponential" is worth a chapter

Incompleteness does not transfer downward. A weaker language proves less — but it also says less, so there is less to fail to prove. Chapter III's undecidable sentence H[h̄] is a sentence of L_E; it is not even a sentence of P.A.'s language L_A. To show P.A. incomplete you need a Gödel sentence written without E, which means redoing the arithmetization — the seventeen conditions of July 26 — using + and · only.

The threshold facts that make it interesting (stated by the book's opening, proofs elsewhere): arithmetic with + but not · is complete and decidable (Presburger, 1929); with · but not + likewise (Skolem). So each of +, · alone is too weak to be incomplete. The pair {+, ·} is where the phenomenon switches on — and Theorem E is the proof that it switches on there, with nothing further needed.

Why E was in P.E. at all, and why it can go. E entered as a primitive because Chapter III's coding leaned on it (Num(x) was one Pow₁₃; concatenation's definition used 13^ℓ(y)). It leaves because it is derivable: Theorem E shows the relation x^y = z is Σ₁ in +, · — so E was redundancy, not power. The exclusion is a theorem, not a taste.


Part II — The obstruction: recursion is not definability

The reader's challenge: the tower is uniform — addition is iterated succession, multiplication is iterated addition, exponentiation is iterated multiplication — so why would the language stop at ·? Where does uniformity break?

Answer: "iterate y times" is not a first-order sentence. The recursion equations

x + 0 = x         x + (y+1) = (x + y) + 1
x · 0 = 0         x · (y+1) = x·y + x
x ^ 0 = 1         x ^ (y+1) = x^y · x

each define the next floor by an induction whose length is the variable y. A formula of L_A is one fixed finite string; it cannot contain y nested copies of anything. So having + and · as primitives does not automatically yield a formula for x^y = z — the uniformity of the equations lives in the metatheory, not in the language. What Gödel found (and §§3–5 reconstruct with Quine's method) is that + and · suffice to code a finite sequence and check it locally — "there exists a record of the computation, every line of which is correct" — and once sequences are codable, every floor of the tower (and far more) becomes definable at once. That is why the tower of primitives can stop at ·: not because iteration stops mattering, but because two floors are enough to express "finite record," and finite records simulate all iteration.

The vocabulary for "how definable" (D1–D2 of the chain): Σ₀ = bounded quantifiers over +, · only, so truth of a Σ₀ sentence is a terminating finite check; Σ₁ = one unbounded ∃ in front of a Σ₀ formula — "there exists a witness, checkable in bounded time." Theorem E lands x^y = z exactly there.


Part III — The circularity scare, and the divisor trick

The scare. The plan needs record-coding; record-coding needs concatenation; but July 21's concatenation was x ∗ y = x·13^ℓ(y) + y — there is an exponential in it. Are we defining E from E?

The resolution: recognize, don't compute. The formula never needs the graded relation 13^ℓ = w (exponent as a variable). It needs only (a) the set of powers of 13 — recognizable by a divisibility test — and (b) "the least power of 13 exceeding y" — pinned by order tests among numbers ≤ z. Both are Σ₀. The divisibility test is the chapter's one appeal to primality:

w is a power of 13  ⟺  every divisor of w other than 1 is divisible by 13

— true because 13 is prime (a divisor of 13^k has only 13's in its factorization), and false in base 10: 4 divides 100 and 10 does not divide 4. This is why the base must be prime and why Chapter III's base 13 was a lucky necessity, now earned.

The graded/ungraded distinction (the session's recurring cliff). "z belongs to the set of powers of p" (ungraded) has the divisor characterization above — one Σ₀ line. "p^y = z" with y a free variable (graded) has no such static characterization: the exponent counts iterations, and counting iterations is the very thing formulas cannot do (Part II). The whole architecture of the chapter is arranged so that only the ungraded fact is ever needed inside formulas; the graded relation x^y = z is delivered at the very end, by the certificate method, as the theorem itself. The same cliff explains two dead ends below: numeral-coding (Part IV) and the naive "z is a power of x" idea — both secretly demand the graded relation.


Part IV — Delimiters: from ♯ to frames

Chapter III's separator and why it dies here. July 26's sequence numbers were δx₁δx₂δ…δxₙδ — workable because the payload was K₁₁, the δ-free numbers, which covered all Gödel numbers of meaningful expressions. δ was a reserved symbol: banned from members, so walls were unmistakable. But §4's Finite Set Lemma must code sequences of pairs of arbitrary natural numbers — that is the meaning of the book's "any natural numbers whatsoever" — and arbitrary numbers use all thirteen digits. No digit can be reserved; any candidate wall-string might occur inside a member.

The numeral dead end (the reader's proposal, killed by the cliff). Why not code entries as numerals, which use only two symbols, freeing eleven digits for walls? Because the numeral of a is the string 0…0 (a accents), whose Gödel number is g·13^a-shaped: decoding a numeral-code back to a is the graded exponential relation — the thing being defined. Entries must be stored verbatim (positional notation, zero decoding cost), and verbatim entries use every digit.

Quine's repair: reservedness by length, not by symbol. A frame is a number whose string is all 1's (D6). Frames of a fixed length j can occur inside members — that cannot be banned — but it can be out-lengthed: choose the separator scale longer than any 1-run inside any member, and add a maximality clause to the detecting formula ("no frame in the whole code exceeds the separator scale") so that a detected separator is guaranteed genuine. Reservedness becomes a property enforced per-code by an inequality, not globally by an alphabet. (Kripke's alternative, the book's Remark: enlarge the base per table so every entry is a single digit — reservedness by base-choice instead. Not pursued.)

This session's variant (deviation, flagged). The chain below guards each frame with the digit 2 on both ends (separators 2 1…1 2), which confines 1-runs by construction and makes the census argument (S9) one line; the book's pure-1 frames must handle entry-boundary run-merging inside the maximal-frame analysis instead. Interface identical; book-check registered in Part X.


Part V — Theorem E: the chain (final format)

GOAL

Theorem E. The relation x^y = z is Σ₁.

Target shape: exhibit ∃w[M(x,y,z,w)] with

  • T1. M Σ₀ — bounded quantifiers over +, · only;
  • T2. x^y = z ⟺ ∃w M, both directions proved;
  • T3. no E anywhere in the construction.

Obligations: G1 (the tool: Σ₀-detectable coding of finite sets of pairs, entries bounded by their code) — S1–S16. G2 (the reformulation: x^y = z as existence of a certificate) — S17. G3 (the assembly) — S18–S19.

Glossary (citable, before any argument)

  • D1. Σ₀-formula: built from +, ·, =, ≤, connectives, and bounded quantifiers (∀v ≤ t), (∃v ≤ t) only.
  • D2. Σ₁-relation: expressible as ∃w F, F Σ₀.
  • D3. x div y ⟺ (∃v ≤ y)(x·v = y).
  • D4. Standing identification: each positive number is its base-13 digit string (unique, leading digit ≠ 0); ℓ(n) = its length. Two digit facts used throughout: multiplying by 13 appends a 0; the strings of length ℓ are exactly the numbers in [13^(ℓ−1), 13^ℓ).
  • D5. x P y: x's string occurs as a consecutive block inside y's string.
  • D6. Frame: a number whose string is all 1's; 1ⱼ = the frame of j ones. So ℓ(1ⱼ) = j and 1ⱼ ≤ 1ₖ ⟺ j ≤ k.
  • D7. Maximal frame of y: a frame that is part of y and not part of any longer frame that is part of y.
  • D8. Certificate for (x,y,z): a finite set S of pairs with (α) (y,z) ∈ S; (β) every (a,b) ∈ S is (0,1) or equals (c+1, d·x) for some (c,d) ∈ S.
  • D9. m ∗ n (m, n ≥ 1): the number whose string is m's string followed by n's string.

The chain

S1 — the string Pw and its parse. Define

Pw(w) := w ≥ 1 ∧ (∀v ≤ w)[ (v div w ∧ v ≠ 1) → 13 div v ]
block says
w ≥ 1 w has a string (D4)
(∀v ≤ w)[…] every v up to w passes the bracketed test — bounded, so a finite check (D1)
v div w ∧ v ≠ 1 v is a divisor of w other than 1 (D3)
13 div v v is a multiple of 13 — as a string: v ends in the digit 0 (D4: appending 0 = multiplying by 13)

Whole string says: every divisor of w except 1 ends in the digit 0.

S2. Pw(w) is true ⟺ w ∈ {1, 13, 13², …}. (⟸: 13 is prime, so a divisor of 13^k has only 13 in its factorization — every divisor ≠ 1 is a multiple of 13; w = 1 passes vacuously. ⟹, contraposed: w not a power of 13 gives w = 13^k·m, 13 ∤ m, m > 1; then v := m is a divisor ≠ 1 not ending in 0. The only step in the chain that uses primality; base 10 fails it: 4 div 100, 10 ∤ 4.)

S3. For m, n ≥ 1: m ∗ n = m·u + n, where u is the least power of 13 exceeding n. (D4, D9. Parse of the arithmetic: u = 13^ℓ(n) — by D4's second fact, that is exactly the least power above n; m·u = m's string followed by ℓ(n) zeros — D4's first fact, ℓ(n) times; + n writes n's ℓ(n) digits into those zero positions, no carrying. Result: m's string then n's string, i.e. m ∗ n. Base-10 picture of the mechanism: 95·100 + 25 = 9525.)

S4 — the string Con and its parse. Define

Con(m,n,z) := (∃w ≤ z)[ Pw(w) ∧ n < w ∧ (∀v < w)(Pw(v) → v ≤ n) ∧ z = m·w + n ]
block says
(∃w ≤ z) some number up to z… (bound sound: if z = m·w + n, m ≥ 1, then w ≤ z — the true witness is inside the search range)
Pw(w) …which is a power of 13 (S2)
n < w …exceeding n
(∀v < w)(Pw(v) → v ≤ n) …while every smaller power of 13 does not exceed n. With the previous block: w is the least power of 13 exceeding n — pinned by order tests alone, no exponent variable (S2)
z = m·w + n z is m's string followed by n's string (S3, since w is now the u of S3)

Claim: for m, n ≥ 1: Con(m,n,z) ⟺ m ∗ n = z. (⟸: w := 13^ℓ(n) verifies every block, by S2 and S3. ⟹: powers of 13 are totally ordered, so blocks 2–4 force w = 13^ℓ(n); block 5 and S3 finish. From here on, ∗ inside any formula abbreviates Con.)

S5 — the string Blk and its parse. Define

Blk(m,n) := m = n ∨ (∃u ≤ n)Con(u,m,n) ∨ (∃v ≤ n)Con(m,v,n)
                  ∨ (∃u ≤ n)(∃q ≤ n)(∃v ≤ n)(Con(u,m,q) ∧ Con(q,v,n))
block says
m = n m's string is the whole of n's string
(∃u ≤ n)Con(u,m,n) n = u ∗ m: m sits at the right end (S4)
(∃v ≤ n)Con(m,v,n) n = m ∗ v: m sits at the left end
(∃u…)(∃q…)(∃v…)(Con(u,m,q) ∧ Con(q,v,n)) n = (u ∗ m) ∗ v: m sits in the interior; q names the intermediate value u ∗ m

Claim (a): for m, n ≥ 1, Blk(m,n) ⟺ m P n. (The four blocks enumerate the four possible positions of a consecutive occurrence — D5.) Claim (b): Blk(m,n) → m ≤ n, and each existential witness is ≤ n, so the displayed bounds lose nothing. (S3's identity: u ∗ m = u·w + m ≥ m and m ∗ v = m·w′ + v ≥ m; compose for the interior case. This inequality funds every bounded quantifier below.)

S6 — frame facts. 1ⱼ ∗ 1ₖ = 1_{j+k} (D9: write j ones, then k ones); and Blk(1ⱼ, n) ⟺ some maximal frame of n has length ≥ j. (⟸: j consecutive positions inside that frame are an occurrence of 1ⱼ — S5(a). ⟹: any occurrence of j consecutive 1-digits extends to a maximal frame of length ≥ j — D7. This is the two-way bridge between the number 1ⱼ and the string fact "j consecutive ones.")

S7 — the string OB and its parse. Define OB(m) := m ≥ 1 ∧ Pw(12·m + 1).

Parse of the arithmetic, with c = the digit twelve: if m = 1ⱼ, then 12·m is the string of j c's (each digit 1 becomes 12; no carrying, since 12 < 13), and adding 1 carries through every position: c c…c + 1 = 1 0 0…0 (j zeros) = 13^j. Concretely, j = 3: 12·(1 1 1) = (c c c); (c c c) + 1 = (1 0 0 0).

Claim: OB(m) ⟺ m is a frame. (⟸: computation above + S2. ⟹: 12m + 1 = 13^j, m ≥ 1 forces m = (13^j − 1)/12 = 13^(j−1) + … + 13 + 1 = 1ⱼ.)

S8 — the code layout. Given nonempty Q = {(a₁,b₁), …, (aₙ,bₙ)}: entries may be 0 and 0 has no string (D4), so store a+1, b+1. Let m := 1 + max{ℓ(aᵢ+1), ℓ(bᵢ+1)} — strictly longer than every stored string — and set

s := 2 ∗ 1ₘ ∗ 2      t := 2 ∗ 1₂ₘ ∗ 2
w := t ∗ (a₁+1) ∗ s ∗ (b₁+1) ∗ t ∗ … ∗ t ∗ (aₙ+1) ∗ s ∗ (bₙ+1) ∗ t

String picture of one cell of w:

2 [2m ones] 2 [aᵢ+1] 2 [m ones] 2 [bᵢ+1] 2 [2m ones] 2

(Deviation from the book starts here: the book's s, t are pure frames 1ₘ, 1₂ₘ; the digit-2 endpoints are this session's addition.)

S9 — census of the maximal frames of w. Every maximal frame of w lies wholly inside one entry-string, one s, or one t, with length respectively < m, exactly m, exactly 2m. (A frame occupies consecutive 1-digits, so it cannot cross any position carrying another digit [D6, D7]; by S8 every s and t begins and ends with the digit 2, so separator-ones cannot join entry-ones and conversely. Lengths read off S8. This confinement is the digit 2's entire job.)

S10 — the string K and its parse. Define

K(a,w,b) := (∃f ≤ w)[ OB(f) ∧ ¬Blk(f, a+1) ∧ ¬Blk(f, b+1)
             ∧ Blk(2∗f∗f∗2 ∗ (a+1) ∗ 2∗f∗2 ∗ (b+1) ∗ 2∗f∗f∗2, w)
             ∧ (∀h ≤ w)(OB(h) ∧ Blk(h,w) → h ≤ f∗f) ]
block says
(∃f ≤ w) some number up to w… (bound sound: the intended f occurs inside w, hence ≤ w by S5(b))
OB(f) …a frame — call its length k (S7)
¬Blk(f, a+1) a+1's string nowhere contains k consecutive ones (S6)
¬Blk(f, b+1) likewise b+1
2∗f∗f∗2 the string: 2, then 2k ones, then 2 — a t-shape at scale k (S6: f∗f = 1₂ₖ)
2∗f∗2 the string: 2, then k ones, then 2 — an s-shape at scale k
Blk(2∗f∗f∗2 ∗ (a+1) ∗ 2∗f∗2 ∗ (b+1) ∗ 2∗f∗f∗2, w) one full cell at scale k, with a+1 and b+1 in the entry slots, occurs somewhere in w (S5(a), S8's picture)
(∀h ≤ w)(OB(h) ∧ Blk(h,w) → h ≤ f∗f) every frame occurring in w is ≤ 1₂ₖ — i.e. no maximal frame of w is longer than 2k (S6, S7, D6)

(Every ∗ expands through Con [S4]; each intermediate concatenation is itself part of w, hence ≤ w by S5(b) — the internal bounds are sound. So K is Σ₀.)

S11 — every stored pair is detected: (a,b) ∈ Q ⇒ K(a,w,b). Witness f := 1ₘ, so k = m. Block 2: S7. Blocks 3–4: an m-frame inside an entry would contradict S9's length census (< m), via S6. Block 5-group: the cell of the pair (a,b) in S8's layout is literally the required string at scale m. Block 6: every frame in w has length ≤ 2m (S9), hence is ≤ 1₂ₘ = f∗f (S6, D6).

S12 — (only-stored, step 1) any witness f has length m. (Block 5 puts 2k consecutive ones into w, so some maximal frame of w has length ≥ 2k [S6]; census caps it: 2k ≤ 2m [S9]. Conversely 1₂ₘ occurs inside any t of w [S8], so block 6 at h := 1₂ₘ gives 1₂ₘ ≤ 1₂ₖ, i.e. 2m ≤ 2k [D6]. So k = m, f = 1ₘ.)

S13 — (step 2) every occurrence in w of "2, 2m ones, 2" sits exactly at a t. (Its 2m ones lie inside a single maximal frame of length ≥ 2m; by S9 only t-interiors qualify, and those hold exactly 2m ones — so the occurrence's ones fill a t-interior exactly and its flanking 2's are that t's own 2's.)

S14 — (step 3) the cell-occurrence's two t-shaped ends sit at two consecutive t's of w. (They sit at t's by S12+S13. If not consecutive, an entire further t lies strictly inside the middle "(a+1) 2 [m ones] 2 (b+1)"; its 2m ones fit neither in the s-shape [only m ones] nor in a+1 or b+1 — for then that entry contains m consecutive ones, making f = 1ₘ part of it [S6], contradicting blocks 3–4.)

S15 — (step 4) the middle matches one stored pair; hence (a,b) ∈ Q. (Between two consecutive t's, w reads exactly (aᵢ+1) 2 [m ones] 2 (bᵢ+1) [S8]; block 5 says the same stretch reads (a+1) 2 [m ones] 2 (b+1). Locate the occurrence's "2 [m ones] 2": its m ones need a maximal frame of length ≥ m in the stretch; entry-frames are < m [S9], so only s's interior qualifies — length exactly m — forcing coincidence of the ones and of the flanking 2's with s. Left of this shared landmark, the same digit segment is both a+1 and aᵢ+1 — same string, same number [D4]; right likewise. So (a,b) = (aᵢ,bᵢ). S11–S15 together: K(a,w,b) ⟺ (a,b) ∈ Q — G1(i) ✓.)*

S16 — entries bounded by the code: K(a,w,b) → a ≤ w ∧ b ≤ w. (Block 5: a+1 is part of the cell, which is part of w; S5(b) twice gives a+1 ≤ w, so a ≤ w; likewise b. — G1(ii) ✓. Load: this is what will make a bounded sweep (∀a ≤ w)(∀b ≤ w) exhaustive over the coded set.)

S17 — the reformulation: x^y = z ⟺ a certificate for (x,y,z) exists. (⟹: S := {(i, x^i) : i ≤ y} satisfies (α) at i = y and (β) via (0, x⁰) = (0,1) and (i+1, x^(i+1)) = (i+1, x^i·x) [D8]. ⟸: induction on a — every (a,b) ∈ S has b = x^a: at a = 0, (β)'s second alternative is impossible, forcing (0,1) = (0, x⁰); at a > 0, (β) yields (a,b) = (c+1, d·x) with (c,d) ∈ S, so c = a−1, d = x^(a−1) by induction hypothesis, b = x^a. Extra pairs beyond the honest list are thereby forced correct too — why (β) needn't mention order or completeness. Then (α) gives z = x^y. The induction is performed by us, once, about all certificates; no formula performs it. — G2 ✓.)

S18 — the string M and its parse. Define

M := K(y,w,z) ∧ (∀a ≤ w)(∀b ≤ w)[ K(a,w,b) →
       (a=0 ∧ b=1) ∨ (∃c ≤ w)(∃d ≤ w)(K(c,w,d) ∧ a = c+1 ∧ b = d·x) ]

Throughout, read "the coded set" as S_w := {(a,b) : K(a,w,b)}.

block says
K(y,w,z) (y,z) ∈ S_w — clause (α) of D8 for the coded set
(∀a ≤ w)(∀b ≤ w)[K(a,w,b) → …] "every pair of S_w satisfies …". The bounded sweep is entitled to this reading only because of S16: no member of S_w lies beyond w, so nothing escapes the bounds
a = 0 ∧ b = 1 the pair is the seed (0,1) — (β)'s first alternative
(∃c ≤ w)(∃d ≤ w)(K(c,w,d) ∧ …) S_w contains some pair (c,d)… (bounds sound by S16 again: any member pair sits below w)
a = c+1 ∧ b = d·x …of which (a,b) is the one-step successor: first coordinate up by 1, second multiplied by x — (β)'s second alternative

Whole string of M says: S_w is a certificate for (x,y,z) (D8).

S19 — Theorem E. x^y = z ⟺ ∃w M; and ∃w M is Σ₁.

(⟹: from x^y = z get a certificate S [S17 ⟹]; code it as w [S8, S11–S15: S_w = S exactly]. Then (α) holds as K(y,w,z), and for each member, (β)'s alternatives transfer: the predecessor (c,d) ∈ S is detected [S11] and reachable by the bounded ∃'s [S16]. ⟸: given w with M true, S18's parse says S_w is a certificate for (x,y,z); S_w is finite [S16: ≤ (w+1)² candidates] and nonempty [(y,z) ∈ S_w]; apply S17 ⟸: z = x^y.

Shape check. T1: K is Σ₀ [S10]; M adds only bounded quantifiers, =, +, · — Σ₀ by D1. T2: both directions above. T3: expand every abbreviation, M → K → OB, Blk → Con → Pw → div — surviving vocabulary: +, ·, =, ≤, the constant 13, connectives, bounded quantifiers; no E. ∃w M is Σ₁ by D2. — G3 ✓, GOAL met. ∎)


Part VI — Exercise 1: P.A. +

The exercise (p. 50). G = H[h̄], true but not provable in P.A. (H(v₁) expresses P̃*). Add G as an axiom; P.A. + {G} is still correct, since G is true. Is it complete?

The reader's answer, graded. Verdict "no, incomplete" — correct. "G is now an axiom, so this is just a patch" — the right frame: the proof was never about one missing axiom. "The formal logic will eventually produce the same consequence all over again" — two repairs: (1) not the same consequence: G itself is now provable in one line (it is an axiom), so G is no longer a witness; what reappears is a new sentence G′, built by the same construction from the new system's provability set. (2) nothing "eventually," and the re-run is not free: the incompleteness argument is a template with two input conditions, and re-applying it requires checking both for the enlarged system — one is handed over by the exercise, the other is the entire mathematical content of the solution.

The chain.

E1 (the theorem as a template). The Ch. III/IV argument takes any system S with (i) S correct, (ii) P̃*_S expressible by some H_S(v₁) — where P*_S := {n : the diagonalization of E_n is provable in S} — and outputs: G_S := H_S[h̄_S] is true but not provable in S. (The owned proof, reread as a function of S: nowhere did it use anything about P.A. beyond (i) and (ii).)

E2 (condition (i)). P.A. + {G} is correct — given (G true, P.A. correct, consequences of truths true).

E3 (condition (ii) — the load-bearing check). The arithmetized provability machinery of P.A. + {G} differs from P.A.'s in exactly one clause: where the axiom-check formula was A(v₁), it becomes A(v₁) ∨ v₁ = ḡ, with g the Gödel number of G — one disjunct, one numeral. Formation sequences, inference steps, proofs, diagonalization: untouched. So P̃*_{P.A.+{G}} is expressible, by some H′. (The step the one-sentence answer skipped; the only thing to verify rather than quote.)

E4 (re-application). E1 at S := P.A. + {G}, inputs E2, E3: G′ := H′[h̄′] is true, not provable in P.A. + {G}. Incomplete. ∎

E5 (G′ ≠ G). G is provable in the new system; G′ is not. Also literally distinct strings: H′ carries the extra disjunct, so h′ ≠ h.

E6 (the boundary the intuition needs). Iterating — P.A. + {G, G′, G″, …} — never closes the gap while E3-style expressibility survives. The extreme patch, adding all true sentences, gives a correct and complete system with no contradiction: condition (ii) is exactly what fails for it (were P̃* expressible there, the diagonal argument would manufacture a true-but-not-true sentence). So the honest slogan: no patch works while the axiom set remains arithmetically expressible — the qualifier is where the theorem lives, and it separates "add one sentence" (E3 goes through) from "add everything" (E3 breaks).


Part VII — What was actually new today

Strip the chapter to its ideas and it bought four:

  1. A prime base gives a purely multiplicative handle on powers — "every divisor ≠ 1 is divisible by p" recognizes {p⁰, p¹, p², …} in one Σ₀ line (S1–S2), and "least power exceeding n" is then pinned by order tests (S4). Exponentials recognized by divisibility-and-search, never computed — the resolution of the circularity scare.
  2. Reservedness by length + maximality replaces a reserved symbol — when the payload uses the whole alphabet, a separator can still be guaranteed genuine by out-lengthing every accidental lookalike and asserting maximality inside the detecting formula (S8–S15; Quine). Chapter III's δ was the degenerate case where the payload had a spare digit.
  3. Unordered certificate sets suffice — condition (β) forces every member of a certificate to be a correct (a, x^a) pair, by one metatheoretic induction over all certificates at once (S17); so the code needn't record order or completeness, only membership. Contrast Ch. III's ordered formation sequences (≺_z): the ordering apparatus was dropped, not rebuilt.
  4. The incompleteness proof is a template with two typed inputs — correctness + expressibility of P̃* (E1). Exercise 1 is one function-application, and the all-truths system marks the input outside the template's domain.

And the graded/ungraded cliff, met three times in one session: the divisor trick recognizes the set of powers but cannot grade p^y = z; numeral-decoding is the graded relation (why entries are stored verbatim); the naive "z is a power of x" restatement smuggles the graded relation back in. One distinction, three dead ends avoided.


Part VIII — Distinctions Ledger (confusions of the day → one-line resolutions)

raised resolution
Why does dropping E matter — doesn't incompleteness carry down? It doesn't: Ch. III's Gödel sentence isn't even in L_A; and below {+,·} completeness actually happens (Presburger +, Skolem ·) — the threshold is real and Theorem E shows {+,·} crosses it.
The recursion tower is uniform — why does the language stop at ·? The equations' uniformity is metatheoretic; "iterate y times" is not a formula. + and · suffice to code finite records, which simulates all iteration at once — so no third primitive is needed.
Concatenation uses 13^ℓ(y) — circular dependence on E? The formula never grades an exponential: it recognizes powers (divisor test, S1–S2) and pins "least power exceeding n" by order tests (S4). No exponent variable anywhere.
"'z is a power of x' has no divisor characterization" — meaning? Ungraded vs graded: the set of powers of a prime has a static divisibility test; the relation p^y = z (exponent free) does not — grading counts iterations, the unformalizable thing.
Why not code entries as numerals (only two symbols, digits freed for walls)? Decoding a numeral-code back to its value is the graded exponential relation. Entries go in verbatim; verbatim uses all thirteen digits.
Why not reuse δ as the separator? Ch. III's payload was K₁₁ — δ-free by construction. §4's payload is "any natural numbers whatsoever" (the book's phrase): all digits occur, no digit is reservable.
What do frames do — what load? They are the separator with reservedness enforced by length + maximality instead of by symbol: out-length every accidental 1-run, then assert in-formula that nothing longer occurs.
"Bounded quantifiers matter because we want finite checks for the induction"? Half right: bounded = terminating check, yes — but the formula never performs the induction. (β) is checked member-by-member; the induction over certificates is ours, in the metatheory, once (S17).
"Mystical expressions" — smearing, junk-tolerance, recognized-not-computed Each cashed or deleted: "recognized not computed" = bounded search + divisibility/order tests (S1, S4); "junk-tolerance" = (β) forces even extra pairs correct (S17); the rest deleted as compression artifacts. Method rule: expand every metaphor into steps or drop it.
Exercise 1: "adding G just patches; the same consequence recurs" Not the same: G becomes provable; a new G′ arises — and only because the axiom-set stays arithmetically expressible (one extra disjunct, E3). The all-truths extension is the patch for which that check fails, and it is complete.
Is eliminating E just reductionism — recursion not forbidden as a primitive, but "derived" being more rigorous? (post-session) Half right: nothing forbidden — P.E. is the system with E primitive (N₁₀–N₁₁ are its recursion equations), and it is exactly as rigorous. What's gained isn't purity but (1) theorem strength — incompleteness doesn't transfer downward, so every discardable primitive widens its scope, and Presburger/Skolem show {+,·} is the floor; (2) a boundary map: E over {+,·} is an abbreviation (definable — Theorem E), · over {+} is genuine power (else Presburger would decide multiplication). Reduction locates the abbreviation/power line; it doesn't purify. And metatheoretic recursion (S17's induction) is never eliminated — only recursion as an object-language primitive.
In M, why may (∀a ≤ w)(∀b ≤ w) be read as "every member of the coded set"? S16: K(a,w,b) → a,b ≤ w — members cannot outrun their code, so the bounded sweep misses nothing. Property (ii) of Lemma K exists precisely to license this reading.

Part IX — Self-Test

Do these cold; answers follow each.

1. State the divisor characterization of "w is a power of p," and give the exact counterexample for base 10.

Answer Every divisor of w other than 1 is divisible by p — correct iff p is prime. Base 10: w = 100 has divisor 4; 4 ≠ 1 and 10 ∤ 4, yet 100 = 10². The test wrongly rejects genuine powers (and only primality guarantees it accepts nothing else).

2. Parse Con's third block, (∀v < w)(Pw(v) → v ≤ n). What does it pin, together with n < w, and what variable does it eliminate?

Answer "No smaller power of 13 exceeds n"; with n < w it makes w the least power of 13 exceeding n, i.e. 13^ℓ(n) — pinned by order tests among numbers ≤ z, eliminating the exponent ℓ(n) (no exponent variable ever appears).

3. Why are entries stored as a+1, b+1 rather than a, b — and why is the shift harmless for the bounds?

Answer Entries can be 0 — the certificate's seed is (0,1), and b = 0 occurs when x = 0 — and 0 has no base-13 string (leading digit ≠ 0). Harmless: a ≤ a+1 ≤ w still gives a ≤ w (S16).

4. What is the digit 2's entire job, in one sentence, and which step states it?

Answer It confines 1-runs: a frame cannot cross a non-1 digit, and every separator begins and ends with 2, so each maximal frame of w lies wholly inside one entry, one s, or one t — the census, S9.

5. Show by digit computation that OB(m) := m ≥ 1 ∧ Pw(12m + 1) recognizes frames.

Answer m = 1ⱼ: 12·m is j copies of the digit twelve (no carrying, 12 < 13); adding 1 carries through every position, giving 1 followed by j zeros = 13^j. Conversely 12m+1 = 13^j forces m = (13^j−1)/12 = 1ⱼ. E.g. j = 3: 12·(111)₁₃ = (ccc)₁₃, +1 = (1000)₁₃.

6. What false match do K's blocks ¬Blk(f, a+1) ∧ ¬Blk(f, b+1) prevent, and at which step are they spent?

Answer A "wide" match whose middle straddles several genuine cells — a whole t hiding inside the detected a+1 or b+1. Spent at S14: a t inside the middle would put 2m consecutive ones into an entry, making f = 1ₘ part of it, contradicting the blocks.

7. Why is M's bounded sweep (∀a ≤ w)(∀b ≤ w) entitled to mean "every member of S_w"? Name the step.

Answer S16 (Lemma K property (ii)): K(a,w,b) → a,b ≤ w, so no member lies beyond the bound. Without it the sweep could miss members and M's parse ("S_w is a certificate") would be false.

8. Where does S17's induction happen — inside the formula or outside — and what does the formula do instead?

Answer Outside: we prove once, about all certificates, that every member is a correct (a, x^a) pair. The formula only checks (α) and (β) member-by-member under bounded quantifiers — a terminating check per member, no induction performed.

9. Why may S_w contain pairs beyond the honest history {(i, x^i)} without harm?

Answer (β) applies to every member, so S17's induction forces even the extras to satisfy b = x^a. That is why the code needn't record order or completeness — membership plus local correctness suffices.

10. Exercise 1: what single clause changes in the arithmetized provability machinery of P.A. + {G}, and for which extension does the re-run fail?

Answer The axiom-check: A(v₁) becomes A(v₁) ∨ v₁ = ḡ — one disjunct, one numeral; all else untouched, so P̃ stays expressible and a new G′ arises. The re-run fails for P.A. + all true sentences: correct and complete, because expressibility of P̃ — condition (ii) — is exactly what breaks.

11. The aerial one-liner: why is "P.A. is incomplete" the sharpest possible form of the phenomenon, given Presburger and Skolem?

Answer Because + alone and · alone are each complete and decidable — remove either symbol and incompleteness vanishes. {+,·} is thus the minimal vocabulary exhibiting it, and Theorem E is what brings the Ch. III machinery down to that minimum.


Part X — Position, owed items, debts

Position: Chapter IV pp. 40–50. §§1–5 done in depth — Theorem E fully owned in chain form (Part V), via §5's certificate proof; §6 (incompleteness of P.A.) read as the corollary it is. Deliberately deferred by the reader's choice: Remark (2)'s alternative proof via β-functions (Gödel's 1931 route: ordered history transcribed by a β(w,i) built from K; historically via the Chinese Remainder Theorem) — available for a future session as a contrast piece: ordered-history vs unordered-set. Next in the book: "More on Σ₁-Relations," p. 50 onward.

Owed by the reader — book checks (new today): 1. The main one: how the book's pure-1-frame Lemma K handles run-merging at separator boundaries — an entry ending in 1's sits flush against a frame, extending the 1-run; Part V's digit-2 guards make the problem vanish by construction (S9), so the book must be doing something else inside the maximal-frame analysis. Find it. (This is the deviation's outstanding obligation.) 2. Two 30-second checks: (a) the divisor characterization at w = 1 — does the book count 1 as a power (13⁰) as S2 does? (b) how §5 words the x = 0 case (0⁰ = 1, 0^y = 0 — Part V's chain handles it via the +1 shift and (β)'s d·x = 0).

Owed, standing (July 24–26, unchanged): L₂(x), L₃(x) strings; N₁₂'s sub-relation (hint sealed in the July 26 file, Part XI); L₃ case-check; the ancestor-interpretation falsification; the whole-domain instance question; July 26's two 30-second spellings checks.

Debt register — two PAID today: E-elimination (the standing debt since July: Part V is the payment in full) and prime base 13 (S2 is where primality is spent; base 13 now earned, not lucky). Remaining: property 1 ⇒ property 2; mechanical ⇒ Arithmetic; adequacy 1930; general machine form of 1931; operation-agreement; instantiation from L₆ + L₇.

Method note — the settled chain format. Today's format war (Part 0) ended in the shape now considered definitive for formal material: GOAL with target shape and obligations → glossary of citable definitions → hallmark steps, each opening with its load, each formula parsed block-by-block into semantic content, each justification citing labels — and arithmetic parsed at the digit level wherever numbers are strings. The negative rules earned along the way: no metaphor doing load-bearing work (expand or delete); no background-facts block (grade-school facts are used inline at the point of use); no rigor without a stated destination; function before formula. This file's Part V is the reference instance.

Previous sessions: July 15 (Ch. 1), 17 (answers), 19–22 (Ch. II), 20 & 23 (exercises), 24 with continuations of 25 (Ch. III §1), 26 (Ch. III §§2–4). This file: Ch. IV.