Gui Ruiyan

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

Study journals ·

Gödel's Incompleteness — Chapter III §§2–4: Arithmetization of the Axiom System, and Theorem 1

Reflections · Study sessions

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

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

In this note / 篇目

Study session of July 26, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter III, section II (§2 Preliminaries, §3 Arithmetization of the Syntax of P.E.) and §4 (Gödel's Incompleteness Theorem for P.E.), book pp. 30–36 · Companion to the sessions of July 15, 17, 19, 20, 21, 22, 23, and 24/25 · Character: a close reading, not an exercise session — the reader read the pages himself and asked for two things: (1) each condition's defining string together with its semantic value, with the equivalence argued rather than asserted — the flagged uncertainty being "the equivalence between Seq x and its string"; (2) organized summary notes. Part IV is the answer to (1) at its deepest point; the Ledger (Part IX) is the answer to (2) in compressed form.


The punchline of the chapter

Provability is Arithmetic; truth is not; therefore they cannot coincide. This session proved that P_E — the set of Gödel numbers of the provable sentences of P.E. — is Arithmetic (Prop. 3, the summit of the seventeen-condition tower below). Chapter II's Tarski theorem (July 24) proved that T — the set of Gödel numbers of the true sentences — is not Arithmetic. An Arithmetic set cannot equal a non-Arithmetic one, so P_E ≠ T: what is provable and what is true are different sets. And the mismatch has a forced direction — given one hypothesis: that P.E. is correct (provable ⊆ true). Under it, the sentence witnessing P_E ≠ T must lie in T \ P_E — a true sentence that is not provable. Correctness is an assumption about the system, not something proved here (a justified one for P.E., whose axioms are true and whose rules preserve truth); historically much weaker hypotheses suffice — Gödel worked from ω-consistency, and Rosser's later refinement from consistency alone — but those belong to later chapters. That is incompleteness, before any Gödel sentence is even written down; §4's Theorem 1 (Part VII) then exhibits the witness concretely as H[h̄]. Everything else in this file — B/E/P, sequence numbers, the seventeen conditions — is the engineering that makes the first half of this contrast ("provability is Arithmetic") true. The closing paragraph of Part VII restates this from the book's architecture.


How to use this document

The pages under study do one thing seventeen times: display a condition on numbers (a set or relation), give its defining string built from already-certified Arithmetic material, and move on — usually without arguing that the string and the condition are equivalent. This file supplies the missing arguments. Each condition below gets three entries: the string (transcribed exactly from the page), the semantic value (what property of what objects it defines), and why they coincide (both directions, wherever that is not immediate).

Two transcription warnings, both caught during this session, are flagged where they occur: a letterform trap in the xPy line (Part II), and two official spellings the book uses without redisplaying (Part V, marked "to confirm"). Nothing else in this file is reconstruction; every displayed string was verified against the page at magnification.

Read Parts I–VIII in order the first time. Afterwards the Ledger (Part IX) alone is the refresher, and the Self-Test (Part X) tells you whether it took. Owed items are collected in Part XI.


Part I — Why sequence numbers exist: the certificate trick

The chapter's goal, restated. Let P_E = the set of Gödel numbers of the provable formulas of P.E., and R_E = the set of Gödel numbers of the refutable ones. If these two sets are Arithmetic, the entire July 22 machinery (express the set → complement → star → diagonalize → Gödel sentence) fires with A := P̃_E, and incompleteness falls out in ten lines. §4 does exactly that (Part VIII). So the whole of §§2–3 is one long verification: P_E and R_E are Arithmetic.

The obstacle. Three definitions in the book so far are inductive: term (variables and numerals, closed under four building steps), formula (atomics, closed under three), provable (axioms, closed under two rules). An inductive definition says "reachable in finitely many steps" — and an Arithmetic condition is a formula of L_E, which has +, ·, E, ≤, =, connectives and number quantifiers, but no "finitely many steps."

The move — replace induction by a certificate. X is a term iff there exists a finite sequence of expressions, each of which is a starter or is built from earlier members, with X among the members (the book's formation sequence, p. 33). The inductive definition is traded for a single ∃ over finite sequences: every step of a construction, laid out in a row, IS the required sequence; conversely each member of such a sequence is a term by induction along it. The same trade works for formulas, and — this is the destination — for provability: a proof in a Hilbert-style system already is a finite sequence, each member an axiom or derived from earlier members. Nothing new is needed for Pf that wasn't already needed for tm.

What the trade costs. "∃ a finite sequence" quantifies over sequences, and L_E quantifies only over numbers. So finite sequences of numbers must be coded as single numbers, with three conditions Arithmetic: x codes a sequence (Seq x), n is a member of the sequence coded by y (x ∈ y), and x comes before y in the sequence coded by z (x ≺_z y). That is Proposition 2, the technical heart of the section — and §2's substring machinery (B, E, P) exists solely to prove it.

The tower, bottom to top (each floor Arithmetic because the floor below is):

∗ (concatenation, July 21)                        Ch. II §4, Prop. 1
  → B, E, P (begins / ends / part-of)             §2, Prop. 1
    → Seq, ∈, ≺  (sequence numbers)               §2, Prop. 2
      → Sb, Var, Num, R₁ (syntax atoms)           §3, conditions 1–4
        → Seqt, tm (terms)                        conditions 5–6
          → f₀, Gen, R₂, Seqf, fm (formulas)      conditions 7–11
            → A (axiomhood)                       condition 12 + Note
              → M.P., Der, Pf (proofs)            conditions 13–15
                → P_E, R_E                        conditions 16–17, Prop. 3
                  → Theorem 1 (incompleteness)    §4, via July 22's engine

Part II — §2 Preliminaries: begins, ends, part-of

The definitions, with the book's examples (base 10 for reading comfort; everything is stated for arbitrary base b ≥ 2).

  • xB_b y — "x begins y": x's base-b numeral is an initial segment of y's. 593 begins 59348; also 593 begins 593.
  • xE_b y — "x ends y": x's numeral is a final segment of y's. 348 ends 59348; also 48 ends 59348; 0 ends 570, as does 70, as does 570 itself.
  • xP_b y — "x is part of y": x ends some number that begins y — i.e., x's digit string occurs somewhere inside y's. 93, 934, 34 are parts of 59348; 0 is part of 5076 but not of 576.

The three strings (p. 31, transcribed exactly):

xB_b y  ↔  x = y ∨ (x ≠ 0 ∧ (∃z ≤ y)(∃w ≤ y)(Pow_b(w) ∧ (x·w) ∗_b z = y))
xE_b y  ↔  x = y ∨ (∃z ≤ y)(z ∗_b x = y)
xP_b y  ↔  (∃z ≤ y)(zB_b y ∧ xE_b z)

Semantic account, E first (the easy one). z ∗_b x glues z's digits before x's. So "some z with z ∗ x = y" says: y's digits = (z's digits)(x's digits) — x is a final segment. Why is E immune to the leading-zero disease that will plague B? Because the piece that must stand alone as a number is the head z, and heads of canonical numerals never start with 0. The tail x is planted verbatim, zeros and all: 0 ends 570 via z = 57 (57 ∗ 0 = 57·10 + 0 = 570 — the July 21 identity x ∗ 0 = 10x doing honest work).

B — the hard one, and why. Naively x begins y iff y = x ∗ z for some z. But ∗ appends z's canonical digits, and the piece of y after x may begin with zeros — "5 begins 5007," yet no number has digit string "007." The repair is July 21's 0-pathology patch reused: split the tail into its leading zeros and the rest. x·w (w a power of b, say bʲ) plants x followed by j zeros; ∗ z then appends the zero-free remainder. 5 begins 5007: w = 100, z = 7 — (5·100) ∗ 7 = 500·10 + 7 = 5007. When the tail has no leading zeros, w = 1 = b⁰ serves: 5 begins 57 via w = 1, z = 7. The conjunct x ≠ 0 enforces the book's convention that 0 begins nothing (a "0" prefix would be a leading zero); the disjunct x = y handles the degenerate case where there is no tail at all.

P — occurrence = final-segment-of-an-initial-segment. An occurrence of x's digits inside y's can be located by cutting y right after the occurrence: the left piece z is an initial segment of y (so zB_b y — and z, being a prefix of a canonical numeral, is itself canonical), and x is a final segment of z (so xE_b z). Conversely any such z exhibits an occurrence. The cut is chosen this way round — prefix first, then x at its end — precisely so that both standalone pieces (z, and the head inside E) are prefixes of y, hence never zero-led. This is what makes "0 is part of 5076" come out true: z = 50 begins 5076, and 0 ends 50.

Reading checkpoint (caught this session). At this print size the italic B and E in the P-line are nearly identical, and the line is dangerously readable as (∃z ≤ y)(zEy ∧ xBz) — "x begins a number that ends y." For x ≠ 0 the two readings are provably equivalent (both say "x's string occurs in y's"). They split exactly at x = 0: under the wrong reading, 0Pz requires a suffix of y starting with digit 0, which no number is, so "0 is part of 5076" would be false — contradicting the book's own bracketed example and its prose definition ("x ends some number that begins y"). The example is the checksum; the correct reading is the one displayed above.

The remark the book italicizes for later. Every ∃ in these strings is written bounded — (∃z ≤ y) — though plain ∃z would prove Arithmetic-ness just as well (the witnesses z, w never exceed y, in fact are < y). The extra care is an investment: the next chapter needs these relations in the narrower class of constructive arithmetic relations, where bounds matter. Same spirit as July 19's flag: all-quantifiers-bounded = mechanically checkable.

Proposition 1. For any b ≥ 2 and n ≥ 2, the relations xB_b y, xE_b y, xP_b y, and x₁ ∗_b … ∗_b xₙ P_b y are Arithmetic. (The last via (∃z ≤ y)(x₁ ∗ … ∗ xₙ = z ∧ zP_b y).)

Notation freeze (p. 32), in force for the rest of the book: b = 13; subscripts dropped (xBy, xEy, xPy); juxtaposition means concatenation — xy is x ∗₁₃ y (no clash with multiplication, always written x·y); xP̄y means ~xPy; x₁x₂…xₙPy means x₁ ∗ … ∗ xₙ P y. From here on, a string like δ0y names the number δ ∗ 0 ∗ y — read it as digits: δ, then 0, then y's digits.


Part III — Finite sequences: ♯'s job, K₁₁, and what a sequence number is

The thirteenth symbol finally earns its keep. The alphabet's ♯ (digit δ = twelve; July 21 table) has never been used. Its job: for expressions X₁, …, Xₙ, the expression

♯X₁♯X₂♯…♯Xₙ♯

serves as the formal counterpart of the n-tuple (X₁, …, Xₙ). The elegance: a sequence of expressions is again an expression, so the one Gödel numbering already covers sequences — no second coding apparatus. The Gödel number of ♯E_{x₁}♯…♯E_{xₙ}♯ is, digit by digit,

δ x₁ δ x₂ δ … δ xₙ δ        (concatenation, base 13)

and this number is called the sequence number of (x₁, …, xₙ).

K₁₁ — who may ride. K₁₁ = the numbers in whose base-13 representation the digit δ does not occur — equivalently, all digits are among the twelve digits 0–11 (hence the name). δ is the separator; a member containing δ would be indistinguishable from two members and a wall. No loss: every ♯-free expression — all numerals, variables, terms, formulas, the "meaningful" expressions — has its Gödel number in K₁₁.

The three conditions to arithmetize (p. 32):

  • Seq(x) — x is the sequence number of some finite sequence of members of K₁₁.
  • x ∈ y — y is a sequence number and x is a member of the coded sequence. (Not set membership — sequences have order and repetition; ∈ just ignores them.)
  • x ≺_z y — z is a sequence number, x and y are members, and the first occurrence of x precedes the first occurrence of y. (The book prints z beneath the symbol; we write it as a subscript.)

Concrete anchors, since these are honest numbers:

  • Sequence (0): δ0δ = digits (12, 0, 12) = 12·169 + 0 + 12 = 2040.
  • Sequence (2, 3): δ2δ3δ = 12·13⁴ + 2·13³ + 12·13² + 3·13 + 12 = 349205.
  • g.n.(v₁) = digits (2,6,5,3) = 5476 (Part V for why), so the one-term sequence (v₁) — the certificate below for "v₁ is a term" — is δ(2653)δ = digits (12,2,6,5,3,12) = 4,526,716. Astronomical growth for trivial content: normal, and harmless — these numbers are quantified over, never written down.

Part IV — Proposition 2: the three strings, equivalence proved (the flagged item)

Proposition 2. Each of Seq(y), x ∈ y, x ≺_z y is Arithmetic. The proof is three displayed strings (p. 32):

1.  Seq x   ↔  δBx ∧ δEx ∧ δ ≠ x ∧ δδP̄x ∧ (∀y ≤ x)(δ0yPx ⊃ δBy)
2.  x ∈ y   ↔  Seq y ∧ δxδPy ∧ δP̄x
3.  x ≺_z y ↔  x ∈ z ∧ y ∈ z ∧ (∃w ≤ z)(wBz ∧ x ∈ w ∧ ~ y ∈ w)

1. Seq x — five conjuncts, five jobs

Target semantic value: x's base-13 digit string is δ a₁ δ a₂ δ … δ aₙ δ, where n ≥ 1 and each aᵢ is the canonical digit string of a number in K₁₁.

conjunct literal content job
δBx first digit of x is δ opening wall present
δEx last digit of x is δ closing wall present
δ ≠ x x isn't the single digit δ kills the degenerate "one wall, no rooms"
δδP̄x "δδ" occurs nowhere in x no empty rooms: every two walls have digits between them (also kills x = δδ, the empty sequence — Seq requires n ≥ 1)
(∀y ≤ x)(δ0yPx ⊃ δBy) whatever follows an occurrence of "δ0" starts with δ no leading zeros: a room may start with digit 0 only by being exactly the one-digit room "0"

Direction 1: a genuine sequence number satisfies the string. Let x = δa₁δ…δaₙδ, each aᵢ ∈ K₁₁ in canonical spelling. The first four conjuncts are immediate (walls at both ends; n ≥ 1 rooms; rooms nonempty since a canonical numeral has at least one digit). The fifth: suppose δ0y P x, i.e., the string "δ 0 (digits of y)" occurs in x. Rooms are δ-free, so that δ is a wall, and the 0 after it is the first digit of some room aᵢ. Canonical spellings start with 0 only when the number is 0 itself, so aᵢ = 0 and the digit after that 0 is the next wall, δ. Hence y's digits, which begin right after the 0, begin with δ — δBy. ✓

Direction 2: anything satisfying the string is a genuine sequence number. Conjuncts 1–4 force the shape: reading x's digits, δ's occur, the first digit is one, the last is one, no two are adjacent, and x has more digits than just δ — so x = δs₁δ…δsₙδ with n ≥ 1 and each sᵢ a nonempty δ-free digit string. Each sᵢ is automatically δ-free (rooms are maximal runs between walls), hence, if canonical, spells a number in K₁₁. Only canonicity — "no leading zeros unless the room is exactly 0" — is in doubt, and conjunct 5 settles it. Suppose some room is 0t with t nonempty (the illegal shape). Two cases, both caught: - t starts with a digit d ≠ 0: take y = d. Then δ0d occurs in x (wall, the bad 0, then d), so δ0yPx; but δBy fails (d is a single non-δ digit). Conjunct 5 is violated. ✓ - t starts with 0 too: take y = 0. Then δ00 occurs, i.e., δ0y with y = 0; but δB0 fails (0's string is "0"). Violated again. ✓

Conversely, when all rooms are legal, no violation is possible (Direction 1). Note the finesse in the two cases: one cannot simply take "y = the rest of the room," because if the rest itself starts with 0 it is not the canonical string of any number — the case split takes y to be a single digit, which is always a legitimate number.

Edge check, the smallest citizen. x = δ0δ = 2040 (the sequence (0)): δB, δE ✓; x ≠ δ ✓; no δδ ✓; conjunct 5: the only y with δ0y P δ0δ is y = δ itself, and δBδ holds via the x = y clause of B. Seq(2040) ✓ — the room "0" is legal, exactly as designed.

2. x ∈ y — membership, and why the third conjunct is there

Semantic value: y codes a sequence and x is one of its members. String: Seq y ∧ δxδPy ∧ δP̄x.

Forward. If x = aᵢ, then the string δaᵢδ — x flanked by its two walls — occurs in y: δxδPy. And aᵢ ∈ K₁₁ gives δP̄x. ✓

Backward — the alignment argument. Suppose δxδPy with x δ-free. The two flanking δ's of the occurrence must coincide with walls of y (all δ's in y are walls). Between two consecutive walls sits exactly one room; x's string, being δ-free, cannot stretch across a wall, so the two flanking walls are consecutive and x's string is the whole room between them — not a proper piece of a room, because the occurrence is bounded by δ on both sides while a room's interior contains none. Hence x = aᵢ for some i. ✓

Why δP̄x is not decorative. Drop it and take y = δ1δ2δ (the sequence (1,2)) and x = the number with digits 1,δ,2 (= 169 + 156 + 2 = 327). Then δxδ = δ1δ2δ = y, which certainly occurs in y — yet 327 is not a member; its "occurrence" straddles a wall. The conjunct δP̄x is precisely the no-straddling guarantee that makes the alignment argument go.

3. x ≺_z y — order via a prefix witness

Semantic value: x and y are members of z's sequence and x's first occurrence is strictly earlier than y's. String: x ∈ z ∧ y ∈ z ∧ (∃w ≤ z)(wBz ∧ x ∈ w ∧ ~y ∈ w).

The picture. A prefix of z that is itself a sequence number is exactly "the first j rooms, walls included": w = δa₁δ…δaⱼδ. The string asks for such a w containing x but not y.

Forward. Let x first occur as room i, y first occur as room k, i < k. Take w = δa₁δ…δaᵢδ. Then w's digit string is an initial segment of z's, so wBz (and w < z, so the bound ∃w ≤ z is honest); x ∈ w by construction; y ∉ w since y appears among rooms 1…i only if its first occurrence were ≤ i < k. ✓

Backward. Given such a w: x ∈ w forces Seq w (it is the first conjunct of ∈), so w is a sequence number in its own right, AND wBz makes its digits an initial segment of z's. Initial segments match digit-for-digit, so every wall of w sits on a wall of z, and w's final δ sits on some wall of z — hence w's rooms are precisely z's rooms 1…j for some j. (A prefix like δa₁δ2 that cuts mid-room fails Seq; a cut mid-room at a wall position can't happen — the digit there is δ in one string and non-δ in the other, contradicting matching.) Now x ∈ w places x's first occurrence at some room ≤ j, and y ∉ w with y ∈ z places y's first occurrence at some room > j. Strictly earlier. ✓

Strictness for free: x ≺_z x is false — any w containing x contains x.

Why "first occurrence"? Sequences may repeat members. The relation the certificate conditions actually need is "there exist members available strictly before y is required" — and first occurrences are what a prefix witness can see. The match with the informal "earlier members" definitions is argued at condition 5.


Part V — §3, conditions 1–11: arithmetizing syntax

Standing conventions of §3. E_x = the expression whose Gödel number is x (July 21). For x₁, …, xₙ ∈ K₁₁, the Gödel number of the sequence (E_{x₁}, …, E_{xₙ}) is the sequence number of (x₁, …, xₙ) — i.e., the g.n. of ♯E_{x₁}♯…♯E_{xₙ}♯. Two abbreviations (p. 33):

(∀x ∈ y)(…)      for   ∀x(x ∈ y ⊃ …)
(∃x,y ≺_w z)(…)  for   ∃x∃y(x ≺_w z ∧ y ≺_w z ∧ …)

(The first looks like an unbounded ∀ — but members never exceed their sequence number (a member's string is a proper part of the sequence's string), so it is a bounded universal in disguise: ∀x(x ∈ y ⊃ …) ⟺ (∀x ≤ y)(x ∈ y ⊃ …). One-line check, worth doing once — the book's promise "only bounded universal quantifiers" survives.)

The eight concatenation functions (p. 34). For the g.n.'s of (E_x ⊃ E_y), ~E_x, (E_x + E_y), (E_x · E_y), (E_x E E_y), E_x′, E_x = E_y, E_x ≤ E_y the book writes x imp y, neg(x), x pl y, x tim y, x exp y, s(x), x id y, x le y. All are fixed concatenation templates, hence Arithmetic. The two the book displays, against the July 21 digit table (0→1, ′→0, (→2, )→3, f→4, subscript→5, v→6, ~→7, ⊃→8, ∀→9, =→η, ≤→ε, ♯→δ):

x imp y = 2x8y3      "(", x, "⊃", y, ")"
neg(x)  = 7x         "~", x  — no parentheses; and beware: this is 7 ∗ x,
                      prepend-a-digit, NOT multiplication by 7 (the book itself
                      adds "(i.e. 7 ∗ x)")

Two gems hiding in the others: s(x) = x ∗ 0 = 13·x — appending the accent is multiplication by 13, July 21's "successor-symbol applicator," now an official function. And since atomic formulas carry no parentheses (witness the book's unabbreviated L₆ below: ~∀vᵢ~vᵢ = t), x id y = xηy and x le y = xεy (inferred — the book doesn't redisplay these; 30-second check against Ch. II §1's official grammar owed, Part XI); likewise pl, tim, exp presumably wrap f′, f′′, f′′′ infix in parentheses, e.g. x pl y = 2x(40)y3 (same check).

The conditions, string / semantic value / equivalence:

1. Sb(x) — E_x is a (nonempty) string of subscripts: (∀y ≤ x)(yPx ⊃ 5Py). Why it works: every part of x contains the digit 5 ⟺ every digit of x is 5 — because single digits are parts, so any non-5 digit d would be a part with 5P̄d. (And x = 0 fails via y = 0: 5P̄0.) A lovely example of saying "all my digits are 5" without being able to say "digit." Delta against July 19: the alphabet's comma-like symbol (digit 5), jobless since its introduction, is revealed as the subscript-former for variables.

2. Var(x) — E_x is a variable: (∃y ≤ x)(Sb(y) ∧ x = 26y3). Semantic value: the official spelling of the i-th variable is ( v followed by i subscript-marks ) — digits 2, 6, 5…5, 3. So g.n.(v₁) = 2653₁₃ = 5476; g.n.(v₂) = 26553₁₃. The parentheses are part of the variable — that is how v₁v₂ stays parseable. The bound y ≤ x is honest: y's string is a part of x's.

3. Num(x) — E_x is a numeral: Pow₁₃(x). The July 21 payoff in one line: n̄ = 0 followed by n accents → digit 1 followed by n zeros → 13ⁿ. So "x codes a numeral" IS "x is a power of 13." (That Pow₁₃ is Arithmetic: standing debt "prime base 13," unchanged.)

4. R₁(x, y, z) — the formation relation for terms holds of (E_x, E_y, E_z): z = x pl y ∨ z = x tim y ∨ z = x exp y ∨ z = s(x). Semantic value: E_z is buildable in one step from E_x, E_y — it is (E_x + E_y), (E_x · E_y), (E_x E E_y), or E_x′. Pure template-matching on codes; the fourth disjunct is literally z = 13x.

5. Seqt(x) — x codes a formation sequence for terms:

Seq(x) ∧ (∀y ∈ x)(Var(y) ∨ Num(y) ∨ (∃z, w ≺_x y)R₁(z, w, y))

Semantic value (book's definition, p. 33): a finite sequence of expressions each of which is a variable, a numeral, or R_t-built from two earlier members. This is the certificate shape — memorize it once, it recurs verbatim twice more:

Seq(x) ∧ (∀y ∈ x)( seed(y) ∨ (∃z, w ≺_x y) rule(z, w, y) )

The index-vs-first-occurrence subtlety (the one real gap between string and informal definition). The informal definition speaks of positions: entry i is justified by entries j, k < i. The string speaks of values and first occurrences: every member-value y must be a seed or R₁-built from values first-occurring strictly before y's first occurrence. Equivalence: (⇒) in a position-justified sequence, look at any value y at its first occurrence i; its justifiers sit at positions < i, so their first occurrences are < i too — the string's demand is met. (⇐) from a string-satisfying x, the sequence read left to right is position-justified at each first occurrence, and repeats are justified by pointing left to the first occurrence. Same certificates, two bookkeepings. Note also: only Seq's members enter — and Seq confined members to K₁₁, which is why ♯-free syntax needed codes in K₁₁ in the first place.

6. tm(x) — E_x is a term: ∃y(Seqt(y) ∧ x ∈ y). The certificate cashed: term = member of some formation sequence for terms. The ∃y is unbounded — necessarily so at this price point (certificates dwarf their conclusions: y = 4,526,716 certifies x = 5476 above), and harmlessly so — Arithmetic-ness never required bounded ∃. Only the ∀'s had to stay bounded.

7. f₀(x) — E_x is an atomic formula: (∃y ≤ x)(∃z ≤ x)(tm(y) ∧ tm(z) ∧ (x = y id z ∨ x = y le z)). Atomic = t₁ = t₂ or t₁ ≤ t₂, t₁ and t₂ terms. Bounds honest (parts again).

8. Gen(x, y) — E_y = ∀vᵢ E_x for some variable vᵢ: (∃z ≤ y)(Var(z) ∧ y = 9zx). Digit 9 = ∀, then the variable, then the body — note there are no added parentheses, and the variable brings its own.

9. R₂(x, y, z) — the formation relation for formulas holds: z = x imp y ∨ z = neg(x) ∨ Gen(x, z). E_z is (E_x ⊃ E_y), ~E_x, or ∀vᵢE_x. (y idles in the second and third disjuncts — see condition 14 for the same idiom.)

10. Seqf(x) — x codes a formation sequence for formulas:

Seq(x) ∧ (∀y ∈ x)(f₀(y) ∨ (∃z, w ≺_x y)R₂(z, w, y))

The certificate shape, second instantiation — seeds are now atomic formulas, the rule is R₂.

11. fm(x) — E_x is a formula: ∃y(Seqf(y) ∧ x ∈ y).


Part VI — Conditions 12–17: axioms, derivations, proofs, provability

12. A(x) — E_x is an axiom of P.E.: the disjunction of nineteen conditions L₁(x), …, L₇(x), N₁(x), …, N₁₂(x), one per scheme of the July 24 catalogue. The book's Note on the Axioms gives sample cases:

  • Group I sample, L₁(x). E_x is an instance of (F ⊃ (G ⊃ F)) iff

    (∃y ≤ x)(∃z ≤ x)(fm(y) ∧ fm(z) ∧ x = y imp (z imp y))

Why the bounds are enough: the instance's F and G are subexpressions of E_x, and a part's code never exceeds the whole's (shorter or equal digit string). Scheme-hood has become template-matching with two formula-typed holes — this is what July 24 called "recognizable by shape alone," now literal. L₂(x), L₃(x): same idea, left to the reader (owed, Part XI).

  • Group II sample, L₄(x). Let φ(y, z, w) = the g.n. of ∀E_y(E_z ⊃ E_w) ⊃ (∀E_y E_z ⊃ ∀E_y E_w) — a fixed concatenation template in imp and 9-prefixing, hence Arithmetic. Then

    L₄(x) ⟺ (∃y ≤ x)(∃z ≤ x)(∃w ≤ x)(Var(y) ∧ fm(z) ∧ fm(w) ∧ x = φ(y, z, w))

Note which July 24/25 fact is being spent: the Kalish–Montague schemes have occurrence-scan side conditions, not freeness side conditions — L₅'s "vᵢ does not occur in F" is the substring check yP̄(code of F)-shaped, one P away from Arithmetic. Freeness would have needed scope-parsing; the axioms were engineered so §3 never parses a scope. (The book: L₆ was displayed with ∃ as an abbreviation; unabbreviated it is the scheme ~∀vᵢ~vᵢ = t.)

  • Group III (N₁–N₁₁). Each scheme has exactly one axiom, so Nᵢ(x) is simply x = gᵢ, gᵢ the g.n. of that one formula — equality with a constant, the most Arithmetic condition there is.

  • Group IV (N₁₂, induction). The book: one first verifies that the relation "E_x is a formula and E_y is one of the formulas E_x[v₁′]" is Arithmetic in (x, y) — left to the reader (owed, with a hint, Part XI) — after which N₁₂(x) is obvious. Delta against July 25's Part XI: E_x[v₁′] is the double wrapper ∀vᵢ(vᵢ = v₁′ ⊃ ∀v₁(v₁ = vᵢ ⊃ E_x)), and the plural "one of the formulas" is the fresh-variable freedom — one bracket-string per admissible vᵢ, so the arithmetized version is a relation, not a function. The wrapper was chosen over surgical substitution precisely for this moment: its code is a concatenation template around x with x riding as an unopened block (July 22's r(x, y) was the same shape), while genuine substitution would demand interior digit-surgery.

13. M.P.(x, y, z) — E_z is derivable from E_x and E_y by Rule 1 (modus ponens): y = x imp z. One equation. Semantic value: the major premise E_y is the string (E_x ⊃ E_z) — derivability-in-one-step is a shape fact about y, nothing more. (From F and (F ⊃ G), get G: x plays F, z plays G.)

14. Der(x, y, z) — E_z is derivable from E_x, E_y by Rule 1, or from E_x by Rule 2: M.P.(x, y, z) ∨ Gen(x, z). In the Gen disjunct y idles — Rule 2 (generalization: from F get ∀vᵢF) has one premise. The two-premise signature is kept uniform so condition 15 can demand a single pair (z, w) every time; a Rule-2 line just lets the second citation be anything earlier (z itself will do).

15. Pf(x) — x codes a proof in P.E.:

Seq(x) ∧ (∀y ∈ x)(A(y) ∨ (∃z, w ≺_x y)Der(z, w, y))

The certificate shape, third and final instantiation — seeds: axioms; rule: Der. Semantic value: a finite sequence of formulas, each an axiom or derivable from earlier members — the textbook definition of a Hilbert-style proof, verbatim. This is the line the whole section existed to write; note that after conditions 1–14, it cost nothing new. Two glosses: - Formulas only, though nobody checks fm: by induction along the sequence — axioms are formulas (each of the 19 disjuncts builds fm in or names a formula); if E_w = (E_z ⊃ E_y) and E_z, E_w are formulas, unique readability makes E_y one; ∀vᵢE_z likewise. The string needn't police what the rules can't produce. - First-occurrence bookkeeping: exactly as at condition 5 — every standard proof qualifies as written, and every qualifying x reads off as a standard proof.

16. P_E(x) — E_x is provable in P.E.: ∃y(Pf(y) ∧ x ∈ y). Provable = member of some proof — no "last line" clause, and none is needed: the prefix of a proof up through any member's first occurrence is itself a proof (all its members' justifiers first-occur inside it), so membership and being-the-last-line certify the same set. Unbounded ∃, same license as condition 6.

17. R_E(x) — E_x is refutable in P.E.: P_E(neg(x)). Refutable = negation provable (the Ch. I definition). One composition — July 20's "inverse image of an Arithmetic set under an Arithmetic function is Arithmetic," with f = neg. And once more: neg(x) = 7x is prepend the digit 7, i.e. 7·13^ℓ(x) + x — misread it as multiplication and nothing downstream survives.

Proposition 3. All the conditions (1)–(17) are Arithmetic. — "This completes our arithmetization of the syntax of P.E."


## Part VII — §4: the harvest — Theorem 1

The book's proof, as a citation chain into owned material (July 22 names in brackets):

  1. P_E and R_E are Arithmetic (Prop. 3) — so take formulas P(v₁) and R(v₁) expressing them in L_E.
  2. ~P(v₁) expresses the complement P̃_E [complement closure — trivial direction of July 20's toolkit].
  3. By the Lemma to Theorem 1 of the last chapter [Lemma 1, July 22: A Arithmetic ⇒ A* Arithmetic, via the wrapper r], there is H(v₁) expressing (P̃_E)*.
  4. Its diagonalization H[h̄] is a Gödel sentence for P̃_E [July 22, Theorem 1's proof]: H[h̄] is true ⟺ g.n.(H[h̄]) ∈ P̃_E ⟺ H[h̄] is not provable in P.E.
  5. P.E. is a correct system (provable ⇒ true; the July 24 sense). If H[h̄] were provable it would be true, hence unprovable — contradiction. So H[h̄] is unprovable; by the biconditional, true.
  6. Then ~H[h̄] is false, hence (correctness again) unprovable — so H[h̄] is not refutable either. A sentence neither provable nor refutable: P.E. is incomplete. (Theorem 1.)

The dual route, same engine: R_E Arithmetic ⇒ R_E* Arithmetic ⇒ K(v₁) expressing it ⇒ K[k̄] a Gödel sentence for R_E: true ⟺ refutable. Were it true it would be refutable, so ~K[k̄] provable, so ~K[k̄] true, so K[k̄] false — contradiction. So K[k̄] is false, hence not refutable, and (false + correctness) not provable. Same undecided sentence phenomenon from the refutability side. Note the July 23 symmetry reborn: H[h̄] is a true sentence asserting its own unprovability; K[k̄] a false one asserting its own refutability.

Aerial one-liner (not the book's words, but the book's architecture). Chapter II proved the set of true sentences is not expressible (Tarski). This chapter proved the set of provable ones is. Whatever is expressible differs somewhere from whatever isn't — and under correctness (provable ⊆ true) the difference can only be a true, unprovable sentence. The arithmetization had to succeed for provability exactly where it had to fail for truth; incompleteness is the daylight between.


Part VIII — What was actually new today

Strip the seventeen conditions to their ideas and the section bought exactly three:

  1. Substring relations are Arithmetic (B, E, P) — bought with July 21's ∗ plus one leading-zeros patch.
  2. Finite sequences of numbers are single numbers, Arithmetic-ly (Seq, ∈, ≺) — bought with a reserved separator digit and (1).
  3. Inductive definitions convert to ∃-certificate definitions — bought with (2), then spent three times (terms, formulas, proofs) on one reusable shape:

    Seq(x) ∧ (∀y ∈ x)( seed(y) ∨ (∃z, w ≺_x y) rule(z, w, y) )

Everything else is template bookkeeping. And the design debts of earlier sessions all fall due here, on schedule: the comma symbol (July 19) exists for Var; accent→0 (July 21) makes Num one Pow; x ∗ 0 = 13x (July 21's pathology) is s(x); occurrence-not-freeness side conditions (July 25) keep A(x) at concatenation-level; the wrapper (July 22/25) makes N₁₂'s brackets a template instead of surgery; and the ♯ symbol, jobless for a week, was the sequence machinery all along.


Part IX — The Ledger (string ↔ semantic value, complete)

Notation: juxtaposition = ∗₁₃ concatenation; digits per the July 21 table; P̄ = not-part-of; ≺_x = earlier-first-occurrence-in-x.

# condition defining string semantic value
— xBy x = y ∨ (x ≠ 0 ∧ (∃z,w ≤ y)(Pow₁₃(w) ∧ (x·w) ∗ z = y)) x's digits start y's (w = shift past the tail's leading zeros)
— xEy x = y ∨ (∃z ≤ y)(z ∗ x = y) x's digits end y's
— xPy (∃z ≤ y)(zBy ∧ xEz) x's digits occur in y's (x ends a beginner of y)
— Seq x δBx ∧ δEx ∧ δ ≠ x ∧ δδP̄x ∧ (∀y ≤ x)(δ0yPx ⊃ δBy) x = δa₁δ…δaₙδ, n ≥ 1, aᵢ ∈ K₁₁ canonical
— x ∈ y Seq y ∧ δxδPy ∧ δP̄x x is a member of y's sequence
— x ≺_z y x ∈ z ∧ y ∈ z ∧ (∃w ≤ z)(wBz ∧ x ∈ w ∧ ~y ∈ w) x's first occurrence precedes y's (w = prefix through x)
1 Sb(x) (∀y ≤ x)(yPx ⊃ 5Py) E_x is a string of subscripts (all digits 5)
2 Var(x) (∃y ≤ x)(Sb(y) ∧ x = 26y3) E_x is a variable ( v subscripts )
3 Num(x) Pow₁₃(x) E_x is a numeral (g.n.(n̄) = 13ⁿ)
4 R₁(x,y,z) z = x pl y ∨ z = x tim y ∨ z = x exp y ∨ z = s(x) E_z one-step buildable from E_x, E_y (term rules)
5 Seqt(x) Seq(x) ∧ (∀y ∈ x)(Var(y) ∨ Num(y) ∨ (∃z,w ≺_x y)R₁(z,w,y)) x codes a formation sequence for terms
6 tm(x) ∃y(Seqt(y) ∧ x ∈ y) E_x is a term
7 f₀(x) (∃y,z ≤ x)(tm(y) ∧ tm(z) ∧ (x = y id z ∨ x = y le z)) E_x is an atomic formula
8 Gen(x,y) (∃z ≤ y)(Var(z) ∧ y = 9zx) E_y = ∀vᵢE_x
9 R₂(x,y,z) z = x imp y ∨ z = neg(x) ∨ Gen(x,z) E_z one-step buildable (formula rules)
10 Seqf(x) Seq(x) ∧ (∀y ∈ x)(f₀(y) ∨ (∃z,w ≺_x y)R₂(z,w,y)) x codes a formation sequence for formulas
11 fm(x) ∃y(Seqf(y) ∧ x ∈ y) E_x is a formula
12 A(x) L₁(x) ∨ … ∨ L₇(x) ∨ N₁(x) ∨ … ∨ N₁₂(x) E_x is an axiom (19 templates; L₁ shown, Group III: x = gᵢ)
13 M.P.(x,y,z) y = x imp z E_z follows from E_x, E_y by modus ponens
14 Der(x,y,z) M.P.(x,y,z) ∨ Gen(x,z) E_z follows from E_x (and maybe E_y) by Rule 1 or 2
15 Pf(x) Seq(x) ∧ (∀y ∈ x)(A(y) ∨ (∃z,w ≺_x y)Der(z,w,y)) x codes a proof
16 P_E(x) ∃y(Pf(y) ∧ x ∈ y) E_x is provable
17 R_E(x) P_E(neg(x)) E_x is refutable

Distinctions Ledger (confusions of the day → one-line resolutions):

raised resolution
"Equivalence between Seq x and its string?" Five conjuncts = walls at both ends + at least one nonempty room + no leading zeros; both directions in Part IV, the only finesse being single-digit witnesses in the leading-zero cases.
δ0y, δxδ, 26y3, 7x look like arithmetic They are concatenations: juxtaposition = ∗₁₃ from p. 32 on. neg(x) = 7x is prepend-7, not ×7.
Why δP̄x inside x ∈ y? Without it, δxδPy can straddle walls: x = (1δ2) "occurs" in δ1δ2δ without being a member.
xPy: begins-an-ender or ends-a-beginner? Ends-a-beginner: (∃z ≤ y)(zBy ∧ xEz). The italic B/E transpose easily; checksum: 0 is part of 5076 — true only on this reading.
≺ uses first occurrences, definitions use positions Same certificates: justify each value at its first occurrence; repeats point left.
(∀y ∈ x) looks unbounded Members ≤ their sequence number, so it's (∀y ≤ x)(y ∈ x ⊃ …) in disguise; the bounded-∀ promise holds.
Why is ∃y in tm, fm, P_E allowed unbounded? Arithmetic-ness never restricted ∃; only ∀ must stay bounded (for the next chapter's constructive class). Certificates outgrow conclusions, so no cheap bound exists anyway.
"One of the formulas E_x[v₁′]" — why plural? One bracket-string per choice of fresh vᵢ; arithmetized as a relation. The wrapper keeps x an unopened block — that's why brackets, not substitution, were the axiom's notation.

Part X — Self-Test

Do these cold; answers follow each.

1. Why does Seq x need δδP̄x — what two illegal x's does it kill?

Answer Empty rooms: without it δa₁δδa₂δ would code a "sequence" with a memberless slot (no number has an empty digit string), and x = δδ would code the empty sequence, which Seq excludes (n ≥ 1).

2. Parse the fifth conjunct of Seq and show how it kills x = δ05δ (room "05").

Answer (∀y ≤ x)(δ0yPx ⊃ δBy): anything following an occurrence of "δ0" must start with δ. Take y = 5: δ05 occurs in x, so δ0yPx holds; but δB5 is false. Conjunct violated, Seq x false. (For room "00…": take y = 0; δB0 false.)

3. Compute the sequence number of the one-term sequence (0), and verify each Seq conjunct on it.

Answer δ0δ = 12·169 + 0·13 + 12 = 2040. δB ✓, δE ✓, ≠ δ ✓, no δδ (the 0 separates) ✓, fifth conjunct: only y = δ has δ0y P x, and δBδ holds via B's x = y clause ✓.

4. Give y and x with δxδPy true, x not a member of y's sequence — and name the conjunct that saves ∈.

Answer y = δ1δ2δ (sequence (1,2)), x = digits (1, δ, 2) = 327: δxδ is y itself. Saved by δP̄x — members must be δ-free, so straddling occurrences are barred.

5. In x ≺_z y, why must the witness w be a sequence number, and where does the string demand it?

Answer Demanded implicitly by x ∈ w (whose first conjunct is Seq w). It forces w to be a wall-aligned prefix — whole rooms only — so "x ∈ w ∧ y ∉ w" means "x among the first j members, y not," i.e., first-occurrence order.

6. A Rule-2 (generalization) line in a proof has one premise. How does it satisfy Pf's demand for two earlier members z, w?

Answer Der(z, w, y) = M.P.(z,w,y) ∨ Gen(z,y); in the Gen disjunct w idles, and the abbreviation (∃z,w ≺_x y) only requires w to be some earlier member — take w = z.

7. Why does P_E need no "last line of the proof" clause?

Answer Every member of a proof is provable: truncate at its first occurrence — the prefix is itself a proof (all justifiers first-occur within it). Membership and last-line-hood certify the same set.

8. What number is s(x), and which July 21 fact is it?

Answer s(x) = x ∗ 0 = 13x — appending the accent (digit 0) is one digit-slot, i.e. ×13: the pathology-turned-successor-applicator.

9. State the certificate shape once, and its three instantiations.

Answer Seq(x) ∧ (∀y ∈ x)(seed(y) ∨ (∃z,w ≺_x y)rule(z,w,y)). Seeds/rule = Var-or-Num/R₁ (Seqt); f₀/R₂ (Seqf); A/Der (Pf).

10. The aerial one-liner: derive incompleteness from "truth is not Arithmetic" + "P_E is Arithmetic" + correctness.

Answer P_E is expressible, the truth set isn't, so they differ on some sentence-code. Correctness rules out provable-but-false, so the difference is a true, unprovable sentence — incompleteness. (The book's §4 route instead builds the witness explicitly: H[h̄] via the Gödel-sentence machinery.)


## Part XI — Position, owed items, debts

Position: Chapter III pp. 30–36 read. Section II (arithmetization) and §4 (Theorem 1) — the chapter's first incompleteness proof is complete. The book continues (ω-consistency/Rosser-style refinements and the abstract forms, per the table of contents) from p. 37.

Owed by the reader — new today (all "left to the reader" by the book, p. 35–36): 1. L₂(x) and L₃(x): write the strings on the L₁ model. (Two-minute template drills.) 2. N₁₂'s sub-relation: show "fm(x) and E_y is one of the formulas E_x[v₁′]" is Arithmetic in (x, y). Hint kept sealed until attempted: the bracket is a concatenation template around the block x; freshness of vᵢ is a substring condition (zP̄x-shaped); g.n.(v₁) = 5476, g.n.(v₁′) = s(5476) = 71188; imp, id, 9-prefixing assemble the rest. 3. Two 30-second book checks: (a) Ch. II §1's official spelling of + · E in terms — confirms the inferred pl/tim/exp and id/le templates of Part V; (b) the one-liner that (∀x ∈ y) is a bounded universal in disguise.

Owed, standing (July 24/25): L₃ case-check; the ancestor-interpretation falsification of (v₁ ≤ v₂ ∨ v₂ ≤ v₁); the whole-domain instance question.

Debt register, unchanged plus none retired: E-elimination; prime base 13 (now load-bearing under Num); property 1 ⇒ property 2; mechanical ⇒ Arithmetic; adequacy 1930; general machine form of 1931; operation-agreement; instantiation from L₆ + L₇.

Method note. Today's format — string / semantic value / both-directions argument, with the reader's flagged item (Seq) taken deepest — fit a reading-session request well; the two OCR-level traps (the P-line letterforms, neg's 7x) confirm the July 25 lesson that holding the recap against the page's exact characters is where errors get caught, in both directions.

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