Gui Ruiyan

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

Study journals ·

Gödel's Incompleteness — Chapter IV: More on Σ₁-Relations (Propositions C, C₁; recursive sets; Theorem D)

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 28, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter IV, book pp. 50–55 (§ "More on Σ₁-Relations": Proposition C, Proposition C₁ + its two corollaries, the definition of recursive set/relation; Appendix: Theorem D and Exercises 1–8) · Companion to the sessions of July 15–27 · Character: a significance session, not a formalization one. Where July 27 fought over the shape of a proof, today asked what the objects mean. The reader arrived with a stack of confusions — "Σ₀/Σ₁ feel like they just mean arithmetic," the proofs don't follow, why is recursive defined as "it and its complement are both Σ₁," and what is Theorem D actually for — and each dissolved into a single distinction. No new chain was built: the reader had already worked Theorem D's proof alone and declined the exercise set, asking instead that its point be extracted from the exercises. The through-line, stated once and reused all day: the Σ/Π subscript is a complexity meter, and every result in the section is about reading it, climbing it, or getting back down it.


The punchline of the section

The Σ/Π subscripts do not name new kinds of arithmetic — they grade ordinary arithmetic relations by how much unbounded search their definition needs. That single reading powers everything in the section:

  • Σ₀ = bounded quantifiers only = a search with a known-in-advance cutoff = decidable.
  • Σ₁ = one unbounded ∃ over a Σ₀ body = a search that halts on yes but may loop on no = recursively enumerable (r.e.) / semi-decidable.
  • recursive = the relation and its complement are both Σ₁ = you can confirm yes and confirm no = decidable, given a name.

The four results are four moves on that meter. Proposition C = the closure algebra: which operations keep you on rung Σ₁ (and which — negation, unbounded ∀ — would push you off it). Proposition C₁ = the normal-form theorem: existentials scattered anywhere in a formula can always be pulled to the front, so "Σ-formula" and "Σ₁-relation" name the same class. recursive = both-Σ₁ = the arithmetic (machine-free) definition of decidable, i.e. Post's theorem taken as a definition. Theorem D = the crowbar that drags the syntactic predicates (term, formula, sentence) down from Σ₁ to recursive — recovering decidable syntax without exponentiation, which is the whole point of the chapter.


How to use this document

Part I fixes the meaning of the meter (the reader's "it's just arithmetic" objection). Part II is the reader's own follow-up — the full ladder Σ₂, Σ₃, …, "more undecidable?", and where a genuine ceiling sits — kept because it is the map the rest lives on. Parts III–V walk the three propositions in book order, each led by the confusion it resolves. Part VI extracts Theorem D's point from Exercises 1–8 without grinding them, and records the two variable-role corrections the reader needed. Part VII isolates what was actually new. Part VIII is the Distinctions Ledger (the day's confusions → one-line resolutions); Part IX the Self-Test; Part X the Position and debts. No formal chain today — the reader owned Theorem E's chain on July 27 and worked Theorem D's proof privately before this session.


Part I — The meter: Σ₀ and Σ₁ are not "just arithmetic"

The reader's objection, stated precisely: "Σ₀ and Σ₁ feel like they just mean arithmetic to me." Half true, and the false half is the whole point.

  • True half: every Σ₀ relation and every Σ₁ relation is an ordinary arithmetic relation. The subscript conjures no new object.
  • False half — that it therefore adds nothing: it adds a measurement. Not every arithmetic relation is Σ₀ or Σ₁; arithmetic relations can need long towers of alternating unbounded quantifiers. The subscript counts the unbounded-quantifier structure of the simplest formula defining the relation — Σ₀ = zero unbounded quantifiers (all bounded), Σ₁ = one unbounded ∃ block over a Σ₀ body.

What the two lowest rungs mean — computationally (the payoff that makes the grading worth having):

rung logical form search verdict
Σ₀ all quantifiers bounded cutoff known in advance always halts → decidable
Σ₁ ∃y (Σ₀ body) y = 0, 1, 2, … unbounded halts on yes, may loop on no → r.e.

The contrast that makes it concrete (the session's anchor example):

  • "x is prime" — x ≥ 2 ∧ (∀d ≤ x)(∀e ≤ x)[d·e = x ⊃ (d=1 ∨ e=1)]. Every quantifier bounded by x; you inspect factors up to x, guaranteed halt. Σ₀, decidable.
  • "x is provable" — ∃p [p codes a proof of x]. The inner check is bounded (Σ₀); the outer ∃p is unbounded — a proof can be arbitrarily long relative to x, so no cutoff exists. Σ₁, semi-decidable, not decidable in general.

prime vs. provable = bounded-and-terminating vs. unbounded-search-that-only-confirms = the entire significance of the Σ₀/Σ₁ split.

Why this book leans on Σ so hard. (1) Gödel's strategy arithmetizes proof: "p proves x" is Σ₀, so "x is provable" is Σ₁ — provability's complexity is exactly one unbounded existential. (2) Smullyan builds computability with no machines: Σ₁ is his surrogate for "r.e.," and recursive will be built from it. So the feeling "it's all just arithmetic" is the design succeeding — computability has been absorbed into arithmetic definability.


Part II — The full ladder (the reader's follow-up)

The reader asked: what are Σ₂, Σ₃, …; are they "more undecidable"; is there a threshold of "utter" undecidability? Kept because it is the terrain the section sits in.

Construction (the arithmetical hierarchy). Consecutive same-type quantifiers collapse (∃x∃y merges by pairing), so only alternations count:

Σ₀ = Π₀   no unbounded quantifiers
Σ₁ = ∃(Σ₀)      Π₁ = ∀(Σ₀)
Σ₂ = ∃∀(Σ₀)     Π₂ = ∀∃(Σ₀)
Σ₃ = ∃∀∃(Σ₀)    …

Subscript = number of alternating unbounded blocks; Σ vs Π = whether the outermost block is ∃ or ∀. Anchors: Σ₁ = "P halts on a"; Π₁ = "P never halts on a" (consistency / the Gödel sentence live here); Π₂ = "P halts on every input" (totality); Σ₂ = "P halts on only finitely many inputs." The hierarchy is strict (Gödel–Kleene): each alternation buys genuinely new definable sets.

"More undecidable?" — yes, but undecidability switched on at rung 1, not later. - Only the bottom is decidable: a set is decidable iff it is Δ₁ = both Σ₁ and Π₁ (this is Part V's definition, previewed). The moment you have Σ₁-but-not-Π₁ — the halting problem — you have undecidability, at level 1. - What grows up the ladder is a graded undecidability, made precise by oracles (a free device answering membership for one fixed hard set): Post's theorem — Σ_{n+1} = the sets r.e. relative to an oracle for the hardest Σ_n set. Σ₁ = semi-decidable outright; Σ₂ = semi-decidable given a halting-problem oracle; and so on up the Turing jump 0′, 0″, 0‴, …. Higher = "solvable by search if you can consult the previous rung's unsolvable problem."

The threshold question — two senses of "undecidable," kept apart: - Meaning A (a set): no algorithm decides membership. Graded by the whole hierarchy; there is no finite top (for every n, some Σ_{n+1} set escapes Σ_n ∪ Π_n) — but there is a genuine ceiling above all of it: by Tarski's undefinability of truth, the set of true arithmetic sentences is not Σ_n for any n — not merely undecidable but not even arithmetically definable. That is "utterly undecidable" in the strongest sense. - Meaning B (a sentence in a theory): neither provable nor refutable — independent, the Gödel sense. Here the threshold is low and sharp: every true Σ₁ sentence is provable in an adequate system (Σ₁-completeness — the very property this chapter engineers), so nothing true is independent at Σ₁; the first true-but-unprovable sentences appear at Π₁ (Con, the Gödel sentence). The jump Σ₁ → Π₁ is where Gödel-independence is born.

The reader took "the roughest idea" here and moved on — the load-bearing takeaway is only that Σ₁ is one rung of a strict infinite ladder, and that decidable = Δ₁ = both directions Σ₁, which Part V needs.


Part III — Proposition C: the closure algebra of Σ₁

The confusion it clears (the headline of the day): the reader read "Σ₁ is different from Σ₀" as "disjoint," then choked on C(a) — "how can every Σ₀ relation also be Σ₁?"

Resolution — "different" means "not equal," and the relation is containment:

Σ₀  ⊊  Σ₁      (proper subset)

Exactly ℤ ⊊ ℚ: every integer is a rational (3 = 3/1), yet the classes differ because ℚ has non-integers. Every Σ₀ relation is Σ₁; Σ₁ still differs because it has non-Σ₀ members (like "provable"). No contradiction — only the word "different" carrying more than it should.

C(a) — the vacuous quantifier. Σ₁ means ∃y(Σ₀ body). Given Σ₀ relation R(x), bolt on a do-nothing quantifier: R(x) ⟺ ∃y R(x) with y not occurring in R. Any y works, so it is true exactly when R is, and it now has Σ₁ shape. Computational gloss: a decision procedure is already a confirmation procedure — decidable ⊆ r.e.

The proposition in full — five clauses, each certifying one operation keeps you in Σ₁:

clause operation mechanism
(a) Σ₀ ⟹ Σ₁ vacuous ∃
(b) absorb an unbounded ∃ two ∃'s collapse: ∃y∃z S ⟺ ∃w (∃y≤w)(∃z≤w)S (take w = max), inner is Σ₀
(c) ∧ and ∨ rename witnesses, push ∃'s out, reduce to (b)
(d) bounded ∃ and bounded ∀ bounded-∃ trivial; bounded-∀ is the deep one — see below
(e) R ⊃ S with R Σ₀ ¬R ∨ S; ¬R is Σ₀ (Σ₀ closed under negation), so Σ₁ by (a), then (c)

The load-bearing clause — bounded universal, C(d). Why does (∀y≤z)R stay Σ₁ when unbounded (∀y)R does not? Unfold R = ∃w S (S Σ₀):

(∀y≤z) ∃w S(x,y,w)   ⟺   ∃v (∀y≤z)(∃w≤v) S(x,y,w)

Uniform-bounding step (⟹): for each y ≤ z pick a witness w_y; there are only finitely many y (namely z+1), so v := max(w₀,…,w_z) is a single ceiling under which every y finds its witness. Inner part all bounded → Σ₀; outer ∃v → Σ₁. This "finitely many demands, collect their witnesses under one ceiling" is the whole trick — and it pinpoints why unbounded ∀ fails: infinitely many w_y, no guaranteed max, no collapse — you escape to Π₂. Same ladder, seen from inside.

Significance of C as a whole. It is the toolkit: once the atomic pieces are Σ₀/Σ₁, you may freely combine them by (a)–(e) and the result is Σ₁ by construction, never unwinding to raw form. What is conspicuously absent — negation, unbounded ∀ — is absent on purpose: those are exactly the operations that climb the hierarchy. C is the careful inventory of "everything you may do while staying r.e."; its gaps are as meaningful as its entries. Computationally it is the standard closure of r.e. sets (∪, ∩, projection, bounded quantification) proved syntactically, machine-free.


Part IV — Proposition C₁: scattered-∃ collapses to front-∃

What makes it non-trivial (the distinction to hold): a Σ-formula (syntactic object) is built from Σ₀-formulas by ∧, ∨, bounded ∀, bounded ∃, and unbounded ∃ — with those ∃'s allowed anywhere, buried deep inside conjunctions and bounded quantifiers. Σ₁ (semantic shape) demands one clean ∃ block out front. So

Proposition C₁: every Σ-relation is Σ₁ — however deeply the existentials are scattered, the relation can always be rewritten with a single leading ∃ over a Σ₀ body.

A normal-form theorem. If you don't separate the two classes, C₁ reads "Σ₁ is Σ₁" (empty); once you see Σ-formulas permit buried ∃'s, C₁ has real content, and induction is the only way to reach every burial pattern.

How the induction runs. "Degree" = number of formation steps (height of the parse tree). Strong induction on degree: assume every shorter Σ-formula expresses a Σ₁-relation, then classify by the outermost operation. The punchline — each formation rule is matched by exactly one clause of Prop C:

the Σ-formula is… Σ₁ by clause
a Σ₀-formula (base) C(a)
G ∧ H / G ∨ H C(c)
(∃x≤t)G / (∀x≤t)G C(d)
∃x G C(b)
F₀ ⊃ G, F₀ a Σ₀-formula C(e)

Base is Σ₁; every step preserves Σ₁; induction sweeps the conclusion up the whole tree. ∎ ("regular" in the book's phrasing is only variable-hygiene — bound vars kept distinct from free — not conceptual.)

The relationship between C and C₁ (the thing to carry). C proves "one operation preserves Σ₁"; C₁'s induction chains those single steps across an arbitrarily deep formula. C had exactly five clauses because they are exactly the five formation rules of a Σ-formula — C was reverse-engineered to make C₁'s induction gapless. Local closure (C) → global normal form (C₁), bridged by structural induction.

The license this buys. Three names, one class: Σ-relation (easy to write) = Σ₁-relation (easy to reason about, one search) = r.e. To certify something is Σ₁, you now exhibit any Σ-formula for it — existentials wherever they fall — and C₁ hands you the clean Σ₁ form free. This is what later spares Smullyan the bookkeeping when the proof-coding relations must be shown Σ₁, and it feeds the two corollaries stated right after (A Σ₁ ⟹ A* Σ₁; the sets P and R are Σ₁), which the reader judged immediate from earlier results and did not dwell on.


Part V — recursive = both it and its complement Σ₁

The definition. A set/relation is recursive iff it and its complement are both Σ₁. A function f is recursive iff its graph f(x) = y is recursive.

Why this definition (the reader reconstructed the argument; recorded with the one gap filled). The reader's own words — one Σ₁ search is only semi-decidable; if the opposite side is also Σ₁, then "the negative search for a yes on the opposite side (a definitive refutation) also terminates," so the relation is pinned down as fully decidable. Correct. Made exact:

  • A Σ₁ → search P_A halts-yes exactly when x ∈ A (confirms membership).
  • Ā Σ₁ → search P_Ā halts-yes exactly when x ∉ A (a yes here = definitive refutation of x ∈ A).
  • Dovetail them (interleave steps so neither starves). Whichever halts gives the verdict.

The gap the reader glided over — why is one search guaranteed to halt? Nothing about a lone Σ₁ search forces termination. What forces it is a fact outside the searches: every input is in A or in Ā, no third option, and each case has a witness the corresponding search will find. The two Σ₁ definitions partition all inputs into their success-cases — no input uncovered. That is why neither Σ₁ alone suffices: with only P_A, an input with x ∉ A hangs forever and you cannot tell "not yet" from "never." The complement's search converts that silence into a definite no.

What it is, named. This is Post's theorem (A decidable ⟺ A and Ā both r.e.) taken as the definition of decidable — stated in pure arithmetic, no machine. Not "A is Σ₁" (only semi-decidable), not "A is Σ₀" (too narrow — many decidable sets need unbounded search to define): "both Σ₁" lands exactly on the decidable sets.

The slide to watch — "decidable" ≠ "provable or refutable." The reader closed by equating them; they part company by one ingredient: - decidable = an algorithm settles it (what recursive delivers, via dovetailing); - provable-or-refutable = a formal system S derives "x ∈ A" or "x ∉ A."

They coincide only via Σ₁-completeness of S (S proves every true Σ₁ sentence): if A is recursive, one of "x ∈ A", "x ∉ A" is a true Σ₁ sentence, so a Σ₁-complete S proves the true one — the algorithmic decision is reflected inside S as a proof. Decidability becomes formal provability precisely through Σ₁-completeness — the bridge this chapter is still building, cashed next chapter (the reader's standing conjecture, reaffirmed).

Why bother naming "recursive" — the forward hook. So you can point at what fails to be recursive. The headline coming later: "x is a provable formula" is Σ₁ (search for a proof) but its complement is not Σ₁ — provability is r.e. but not recursive: semi-decidable, not decidable. That single gap — Σ₁ without a Σ₁ complement, so no dovetailing rescue — is where undecidability and incompleteness live. The definition exists to state that failure crisply.


Part VI — Theorem D: the same coding machine, rebuilt without E

Theorem D is a witness-bounding lemma: it gives an explicit, computable ceiling π(x) on the code of any finite sequence whose entries are all ≤ x. Its purpose reads cleanest against Chapter III's own numbered list of arithmetized relations (Prop. 3, pp. 33–34), which runs (1)–(17). Relations (1)–(15) are the whole syntactic-and-proof apparatus — subscript-string (Sb), variable (Var), numeral (Num = Pow₁₃), the concatenation relations, the formation-sequence and term/formula predicates (Seqt, tm, Seqf, fm), atomic formula, generalization (Gen), axiom (A), modus ponens (M.P.), derivability (Der), and finally Pf(x) = "x is a proof" (15) — while (16)–(17) are provability and refutability, P_E(x) = ∃y(Pf(y) ∧ x ∈ y) and R_E(x) = P_E(neg(x)). Stated against that list, the architecture is a single sentence:

Theorem D, discharged through Exercises 1–8, certifies that (1)–(15) are recursive (decidable) — so that (16) provability and (17) refutability come out Σ₁.

Each of (16)–(17) is one unbounded ∃ over the recursive proof relation (15): the clean Σ₁ shape — decidable body, single existential — and, by Church, not recursive. The whole recursive/Σ₁ split lands exactly at the (15)/(16) boundary: checking a proof is decidable, finding one is only semi-decidable.

Two precisions before the mechanics. First, Theorem D does not bite on all fifteen equally. Most of (1)–(15) are already Σ₀ outright — Num, the bounded coding relations, M.P., Der, the axiom check — and Theorem D is needed only for the ones defined by an unbounded existential over a formation sequence: tm (6) via Seqt (5), fm (11) via Seqf (10), and hence Pf (15), which is built on them. Those are the naively-Σ₁ relations; Theorem D bounds their search and drops them to recursive, while the rest come for free. The collective result Exercise 6 records — "(1)–(15) all recursive" — is what (16)–(17) rest on. Second, the reader had already worked the base-13 length argument that proves Theorem D and wanted only this significance; the clearest way to see it is not to grind the exercises but to watch the coding apparatus built twice — once in Chapter III with the exponential E as a primitive, once here without it — because Theorem D is precisely the girder that must be re-forged when E is removed.

The single move behind the whole thing is visible in relation (6). Unbounded, "x is a term" reads tm(x) ⟺ ∃y[y codes a formation sequence for terms ∧ x occurs in it], and that unbounded ∃y makes it Σ₁ with no guarantee of decidability. Theorem D caps the witness — a formation sequence for x has entries ≤ x and bounded length, so its code is ≤ π(x) — and the definition tightens to

tm(x)  ⟺  (∃y ≤ π(x))[y codes a formation sequence ∧ x occurs in it]      (Exercise 4)

with the search now bounded. Exercises 1–3 assemble the toolkit (a function with a Σ₁ graph is recursive; π is itself recursive; a bounded search below a recursive bound stays recursive), Exercises 4–7 push each naively-Σ₁ relation down this way (terms, formulas, the coding relations, sentences), and Exercise 8 carries the result across the (15)/(16) threshold — provable-formulas is r.e. iff provable-sentences is, recursive iff recursive.

The two builds, side by side

What separates the Chapter III build from the Chapter IV build is a single privilege. With E in the language you may write 13^(v) as a term whose exponent v is a variable; without E you may not, and every construction that leaned on that privilege acquires an ungraded counterpart. Reading the correspondence across, row by row, is the whole story:

the same task Chapter III — with E Chapter IV — without E (Theorem D)
name a power of 13 write 13^(v), v a variable — computed from its exponent recognize it (a power of 13 = a number whose every divisor ≠ 1 is a multiple of 13; July-27 S1–S2) and locate the one wanted by order tests (the least above n; S4)
concatenate two strings x ∗ y = x·13^(ℓ(y)) + y — an exponential term Con: "z = m·u + n with u the least power of 13 exceeding n" — ungraded, Σ₀
bound a code code ≤ 13^(total length) — a term, true on sight prove code ≤ π(x) (Theorem D) and prove π recursive (Exercise 2)
where the exponent sits a variable or expression — graded a fixed target, reached by recognition — ungraded

Read down the right-hand column and the exp-free method is one discipline held consistently: never let a variable stand in an exponent. Every power of 13 the chapter touches is a specific number, reached not by evaluating 13^(something) but by recognizing that a number is a power of 13 and then pinning down which one by order among the numbers already in hand. This is the graded/ungraded distinction the reader has now met four times, and it is the entire meaning of "arithmetic without the exponential." (The classical coding tells the same story in another key: Gödel's 1931 scheme ⟨a₁,…,aₖ⟩ = 2^(a₁+1)·3^(a₂+1)·⋯ puts the entries directly into the exponents, and its ceiling pₙ^((n+1)·n) is again a term one simply writes — the with-E convenience in its purest form.)

Why one row, and only one, becomes a theorem

Three of those four correspondences merely trade one formula for another. The third is different in kind. With E, the bound code ≤ 13^(total length) is true by the very shape of the term — there is nothing to prove. Without E there is no such term, so the bound must be argued, and the argument runs in two steps that both stay inside +,·. First, count the digits: the concatenated code occupies at most (max entry length)·(number of entries) base-13 positions — a product, which the language can form. Then cross from that digit-count to a power of 13: a string of L base-13 digits sits below the specific power of 13 that has L+1 digits, and that specific power is reached ungraded. Stitching the count to the crossing is Theorem D. So the theorem-hood is not incidental — it is exactly the price of the one row in which removing E turns a written term into a proof obligation, and Exercise 2 (π recursive) is the second half of that same re-forging, making the earned bound usable inside +,· formulas.

What E stood in for — and why π is not it in disguise

Seen through the correspondence, E's whole contribution was the license to name a power by its exponent. It was never a source of expressive power — Theorem E already showed every exponential fact is definable in +,· — only of convenience: with E those facts sit at Σ₀ (bounded, cheap), and without E the most one can secure is Σ₁. This is what dissolves the reader's sharp objection that π "is an exponential." The prohibition is on exponentiation as an operation inside formulas — a graded a^b = c, or a 13^(v) term with a variable exponent — not on numbers that happen to be powers; 13^k lives in ℕ whatever the language can say. π's values are powers of 13, but π is defined ungraded and is a genuinely recursive function (Exercise 2), so it imports exactly the size E would have supplied while importing none of the forbidden operation. π is simply the right-hand column standing in for the left.

Where the exp-free route is actually forced

The correspondence can make it look as though everything here must avoid E, and it is worth being exact, because it need not. By the Appendix, E is already available — Theorem E is proved — and exponentiation is itself recursive (a total function with a Σ₁ graph is recursive, Exercise 1). A bound built from E, say B(x) = 13^(g(x)) with g recursive, would therefore itself be recursive, and the syntactic predicates would come out recursive just the same: nothing here blocks using E. The genuine necessity lies one chapter earlier, inside building Theorem E, where the certificate coding needs a code-bound at a moment when E is not yet defined — and using it there would be circular. Theorem D's content — that the witness is capped by a computable function of x — is needed either way, since E would change only how an already-known bound is written, not whether it is known. So the honest map is threefold: Theorem D's content is mandatory always; exp-free bounding is mandatory at the Theorem-E stage, on pain of circularity; and exp-free bounding in the Appendix is a clean methodological choice, not a necessity. (There are, in fact, two exp-free routes — Smullyan's base-13 concatenation, bounded by Theorem D, and Gödel's β-function via the Chinese Remainder Theorem, the Remark (2) proof deferred July 27; the genuinely exp-using method is the prime-power one, and Smullyan took base-13.)

Reading Theorem D correctly

Two precisions keep the lemma from being misread — both of them the reader's own corrections. The first is its logical direction. It is tempting to paraphrase it as "find an n larger than x so the code fits under π(x)," but that inverts everything; nothing is chosen larger than x. Three magnitudes have to be held apart:

quantity size role
entries aᵢ of the witness small, ≤ x given by the object's structure
length k small, bounded given
code of the whole sequence big, but ≤ π(x) Theorem D's conclusion

The entries and length are small by the object's own structure — the entry-bound simply is x — and the theorem's force runs one way, bounded contents ⟹ bounded code. You cannot cap the code of an arbitrary sequence; you can cap it only once its contents are already controlled. (The reader's "π(x) > x" was a mis-slotting: π(x) ceilings the code, while the entries stay ≤ x.) The second precision concerns what the bound is for. It does not deliver decidability merely "by being bounded" — recursiveness is "both sides Σ₁," and never requires boundedness as such. Unbounded, tm's complement ∀y¬[…] is Π₁, not visibly Σ₁; the bound's one job is to turn that unbounded ∀ into a bounded ∀, which is Σ₁, so that both sides are Σ₁ at once. For that it needs only to genuinely cap the witness (Theorem D) and to be a recursive function (Exercise 2). Boundedness is how recursiveness is achieved here, not what it is.

Why proof-checking must halt

Underneath all of it is the reason Gödel needs any of this, and it turns on the very distinction the section has been building. A Σ₁ test is a semi-decision: you search for a witness, and if one exists you find it and halt with yes, but if none exists the search runs on forever and no definite no ever arrives. A recursive test is a full decision: on every input — a genuine proof or a page of garbage — it halts, with yes or with no. "A test that merely might loop" is the first kind, and its danger shows exactly on the negative cases: handed a malformed candidate that is not a proof at all, a merely-Σ₁ checker could grind forever, never returning the "no" that proof-checking owes.

So yes — the proof relation itself, the book's Pf(x) = "x is a proof" (15), must be recursive, not merely Σ₁. That is what Exercises 1–8 secure: whether x codes a sequence of formulas, whether each line is an axiom or follows from earlier ones by a rule — each is a bounded, terminating check, so Pf halts on every input, garbage included. And this is no fussy detail. Recursive proof-checking is the arithmetic face of what an effectively axiomatized formal system is — decidable axioms, decidable rules, hence decidable proofs — and Gödel's theorem is a claim about precisely that class. The boundary case makes the necessity vivid: drop effectiveness and take all true sentences as axioms, and you gain completeness but lose decidable proof-checking (it is no longer even arithmetical, by Tarski). That is the July-27 all-truths extension viewed from the recursion side — decidable proof-checking is exactly the hypothesis incompleteness requires, and surrendering it is exactly how one slips the theorem.

The payoff is the asymmetry across the (15)/(16) boundary. Checking a proof is decidable; finding one is not. Pf (15) is recursive, but placing one unbounded ∃ in front of it,

P_E(x)  ⟺  ∃y (Pf(y) ∧ x ∈ y)      (relation 16)

lands at Σ₁ — semi-decidable, and by Church not recursive: a theorem can always be confirmed by exhibiting a proof, yet no general procedure halts with no on every non-theorem. (Refutability R_E (17) = P_E(neg(x)) rides along, Σ₁ for the same reason.) A recursive body beneath a single unbounded existential is exactly the shape the incompleteness argument consumes — and it is that clean shape only because the body is decidable. (One honest qualification: "P_E is Σ₁" would in fact survive even a merely-Σ₁ Pf, since the outer ∃y absorbs any inner search by C(b). What forces Pf recursive is not the complexity of P_E but the meaning of "formal system" — proof-checking must terminate — together with Σ₁-completeness, which needs the system to actually decide its bounded syntactic conditions. Theorem D is what supplies that decidability in +,· without E.)


Part VII — What was actually new today

  1. The Σ-subscript is a search-complexity meter, not a species of arithmetic. Σ₀ = bounded/decidable, Σ₁ = one unbounded ∃/r.e.; the hierarchy above is a strict infinite ladder graded by oracle strength, capped only by Tarski's non-arithmetical truth. prime vs. provable is the meter's calibration example.
  2. "different ⊊ disjoint." Σ₀ ⊊ Σ₁ (integers ⊊ rationals); C(a)'s vacuous quantifier is "decidable ⊆ r.e." in arithmetic dress.
  3. Prop C is a closure algebra whose gaps are deliberate. Bounded-∀ survives by uniform-bounding (finitely many witnesses, one max); unbounded-∀ and ¬ are omitted because they climb the ladder.
  4. C₁ is a normal form, and its induction is why C has exactly five clauses — one per Σ-formula formation rule. Scattered-∃ = front-∃; three names (Σ-relation / Σ₁ / r.e.) for one class.
  5. recursive = both-Σ₁ = Post's theorem as a definition — dovetailing gives decidable, and decidable → provable-or-refutable needs the extra hinge of Σ₁-completeness (not yet installed).
  6. Theorem D is a witness-bounding crowbar that drags syntax from Σ₁ down to recursive without exponentiation; the exercises are its one idea applied set-by-set.

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

raised resolution
Σ₀/Σ₁ "feel like they just mean arithmetic" They are arithmetic relations; the subscript grades them by unbounded-search complexity (Σ₀ decidable, Σ₁ r.e.). Not every arithmetic relation is Σ₀/Σ₁ — the ladder has more rungs.
What are Σ₂, Σ₃, …? Are they "more undecidable"? Alternation count of unbounded quantifiers (arithmetical hierarchy). Undecidability starts at Σ₁ (halting problem), not later; higher rungs are "more undecidable" only via oracle strength (Post / Turing jump).
Is there a threshold of utter undecidability? For sets: no finite top, but a real ceiling above all rungs — arithmetic truth is not Σ_n for any n (Tarski). For sentences (independence): none at Σ₁ (true Σ₁ ⇒ provable), first ones at Π₁ (Con, Gödel sentence).
If Σ₁ differs from Σ₀, how is every Σ₀ relation also Σ₁ (C a)? "Different" = "not equal," not "disjoint": Σ₀ ⊊ Σ₁ (as ℤ ⊊ ℚ). A vacuous ∃ gives any Σ₀ relation Σ₁ shape.
The proofs of Prop C don't follow Each clause certifies one operation stays in Σ₁: (b) two-∃-collapse by max, (c) push ∃'s out, (d) bounded quantifiers — bounded-∀ by uniform-bounding, (e) ¬R∨S with ¬R Σ₀.
Why does bounded-∀ stay Σ₁ but unbounded-∀ not? Finitely many y ≤ z ⇒ finitely many witnesses ⇒ a single max ceiling v; collapse to ∃v(∀y≤z)(∃w≤v). Unbounded ∀ has no guaranteed max — escapes to Π₂.
How does C₁ ("every Σ-relation is Σ₁") go by induction? Σ-formula allows ∃'s scattered anywhere; C₁ says they pull to the front. Strong induction on formula degree; each formation rule = one clause of C (base=a, ∧∨=c, bounded=d, ∃=b, ⊃=e).
Why is recursive defined as "it and its complement both Σ₁"? Dovetail the two Σ₁ searches: one confirms yes, the other confirms no; excluded middle guarantees one halts. = decidable. Post's theorem as a definition, machine-free.
"…so decidable, i.e. provable or refutable?" Not identical: decidable = algorithm; provable-or-refutable = in a system S. They coincide only via Σ₁-completeness (true Σ₁ ⇒ provable), the bridge coming next chapter.
What is Theorem D for? Framed on Ch. III's list (Prop. 3): via Exercises 1–8 it certifies relations (1)–(15) — the term/formula/proof apparatus, culminating in Pf (15) — are recursive, so (16) P_E = ∃y(Pf(y)∧x∈y) and (17) R_E = P_E(neg(x)) are cleanly Σ₁. It bites only on the naively-Σ₁ formation-sequence relations (tm/Seqt 6/5, fm/Seqf 11/10, Pf 15), capping their witness by π(x); the rest of (1)–(15) are already Σ₀. The recursive/Σ₁ line = the (15)/(16) boundary = checking-a-proof vs finding-one.
Theorem D = "find n larger than x so the code fits under π(x)"? Inverted. Entries are ≤ x by structure (n := x, chosen by nothing); the theorem's force is the upper bound on the code (≤ π(x)). Implication bounded-contents ⟹ bounded-code, one-way.
π(x) is a power of 13 — doesn't that use the exponential the chapter forbids? No. The ban is on exponentiation as an operation inside formulas (graded a^b=c, or 13^(v) with variable v), NOT on numbers that are powers — 13^k ∈ ℕ regardless. π is a recursive function (Exercise 2) whose graph is +,·-definable via the ungraded "least power of 13 exceeding …" machinery; values exponential, graph simple. Fourth crossing of the graded/ungraded cliff.
How did the earlier (with-E) machine use exponentials, and what's the contrast? It let the exponent be a variable: Ch. III wrote 13^(ℓ(y)) as a term and bounded codes by 13^(length) as a term (prime-power coding likewise puts entries in exponents, ceiling pₙ^((n+1)·n) free). Without E, 13^(v) is unwritable, so the bound must be counted (digits, via +,·) and crossed to a recognized power — that counting-plus-crossing IS Theorem D. Dividing line = variable exponents.
Is the β-function an exp-using method? No — β (Gödel's CRT coding) is the rival exp-free route (the deferred Remark 2). Exp-using = prime-power coding; exp-free = base-13/Theorem D and β. Smullyan took base-13.
Does "bounded ∃" = decidability? Isn't a Σ₁ "bound" no bound? (reader's catch — corrects a tutor overstatement) Recursiveness = both sides Σ₁; it does NOT require boundedness or Σ₀-ness. Bounding is only the mechanism that turns the otherwise-Π₁ complement (∀y¬…) into a bounded ∀ (Σ₁). It needs a bound that (a) genuinely caps the witness (Theorem D) and (b) is a recursive function (Exercise 2) — nothing more.
Then couldn't we bound with E and skip the exp-free route? In the Appendix, yes: exp is recursive (Σ₁ total ⇒ recursive, Ex 1), so a bound built from E is recursive and gives recursive predicates. Exp-free is forced only earlier, inside building Theorem E (E not yet defined ⇒ circular). Theorem D's content (witness ≤ π(x)) is needed regardless; the ungraded expression in the Appendix is economy, not necessity.
"A test that merely might loop" — what is it, and must "p is a proof of x" be recursive? A merely-Σ₁ test is a semi-decision: halts yes on positives, may loop forever on negatives (e.g. malformed p). Proof must be verifiable, so Prf(p,x) must be recursive (halts yes/no on every input) — the arithmetic face of "effectively axiomatized." Asymmetry: checking a proof (Prf) is recursive; finding one (Provable = ∃p Prf) is Σ₁ and, by Church, not recursive. (Caveat: Σ₁-provability alone would survive a Σ₁ Prf via C(b)-collapse; what forces recursive Prf is the meaning of "formal system" + Σ₁-completeness.)

Part IX — Self-Test

Do these cold; answers follow each.

1. In one sentence, what does the Σ-subscript measure, and what are the computational meanings of Σ₀ and Σ₁?

Answer It counts the unbounded-quantifier (alternation) structure of the simplest defining formula: Σ₀ = all quantifiers bounded = decidable (search with a known cutoff); Σ₁ = one unbounded ∃ over a Σ₀ body = recursively enumerable (halts on yes, may loop on no).

2. Give the session's two-example calibration of the Σ₀/Σ₁ line and say which is which.

Answer "x is prime" — all quantifiers bounded by x, guaranteed halt = Σ₀ / decidable. "x is provable" = ∃p(p proves x), p unbounded, halts only on yes = Σ₁ / semi-decidable.

3. Resolve: "Σ₁ is different from Σ₀, so nothing can be both." Where is the error?

Answer "Different" means "not equal," not "disjoint." Σ₀ ⊊ Σ₁ (proper subset, like ℤ ⊊ ℚ): everything Σ₀ is Σ₁ (C a, via a vacuous ∃), yet Σ₁ is strictly bigger (e.g. "provable" is Σ₁, not Σ₀).

4. Why does bounded ∀ keep a relation Σ₁ while unbounded ∀ does not? Name the maneuver.

Answer Uniform-bounding: for (∀y≤z)∃w S, only z+1 values of y, so their witnesses have a single max v; rewrite as ∃v (∀y≤z)(∃w≤v)S, inner Σ₀, whole Σ₁. Unbounded ∀ gives infinitely many witnesses with no guaranteed max — no collapse, escapes to Π₂.

5. State Proposition C₁, say why it is not trivial, and describe the induction in one line.

Answer Every Σ-relation is Σ₁. Non-trivial because a Σ-formula permits unbounded ∃'s scattered anywhere, while Σ₁ demands one leading ∃; C₁ says they always pull to the front. Induction on formula degree, each formation rule handled by the matching clause of Prop C (base=a, ∧∨=c, bounded=d, ∃=b, ⊃=e).

6. Why exactly five clauses in Prop C?

Answer They are the five formation rules of a Σ-formula; C is reverse-engineered so C₁'s structural induction has no gap. Local closure (C) chained into global normal form (C₁).

7. Give the dovetailing argument that "A and Ā both Σ₁ ⟹ A decidable," and name the fact that guarantees termination.

Answer Run P_A (halts-yes on x∈A) and P_Ā (halts-yes on x∉A) interleaved; whichever halts gives the verdict. Termination is guaranteed by excluded middle on membership — every x is in A or Ā, and the two searches partition all inputs into their success-cases, so one always halts.

8. Distinguish "decidable" from "provable or refutable," and name the bridge between them.

Answer Decidable = an algorithm settles it (what recursive gives). Provable-or-refutable = a formal system derives membership/non-membership. Bridge = Σ₁-completeness: since one of "x∈A"/"x∉A" is a true Σ₁ sentence, a Σ₁-complete system proves it, reflecting the decision as a proof.

9. State Theorem D's point in one sentence and the rewrite it licenses for "x is a term."

Answer It bounds a finite sequence's code by an explicit π(x) when its entries are ≤ x, turning tm(x) ⟺ ∃y(y codes a formation sequence ∧ x in it) into (∃y ≤ π(x))(…) — a bounded ∃ over a recursive matrix, hence recursive, not merely Σ₁.

10. Correct the misstatement: "Theorem D lets us find an n larger than x so the code sits under π(x)."

Answer Nothing is chosen larger than x: the entries are ≤ x by the object's own structure (n := x). The theorem's content is the upper bound on the code (≤ π(x)) — an implication bounded-contents ⟹ bounded-code, one-directional. Entries stay small (≤ x); only the code climbs to π(x).

11. Why must Theorem D be proved in this chapter rather than quoted, and what does it recover?

Answer The chapter forbids exponentiation, which elsewhere bounds sequence-codes for free (prime-power/β-coding). Theorem D is the exp-free substitute, earned by a base-13 length argument; it recovers decidability of the syntactic apparatus (terms, formulas, sentences, proofs).


Part X — Position, owed items, debts

Position: Chapter IV pp. 50–55 done. § "More on Σ₁-Relations" — Proposition C (all five clauses understood, bounded-∀'s uniform-bounding owned), Proposition C₁ (normal-form theorem, induction↔clause correspondence owned), Corollaries 1–2 (accepted as immediate from earlier results, not dwelt on), the definition of recursive (dovetailing / Post's-theorem reading owned, plus the decidable-vs-provable distinction). Appendix: Theorem D proof already worked privately by the reader; its significance extracted here from Exercises 1–8. Next in the book: the section following the Appendix (Chapter IV's remaining §§ / into the arithmetization proper).

Deferred by the reader's choice: the full worked solutions to Exercises 1–8 — the reader judged "we do need to do all the exercises to fully sound the idea" but set them aside for another day. Flag for a future session: Ex 1 (Σ₁-function ⇒ recursive) and Ex 3 (bounded search preserves recursive) are the toolkit; Ex 4 (tm(x) via π(x)) is the flagship application to re-derive; Ex 8(2) (provable formulas r.e./recursive iff provable sentences are) is the bridge to the next chapter.

New standing debt today: the reader's own reading of "π(x) as an upper bound on the code" is accepted but not yet drilled — genuine fluency was explicitly said to require working the exercises. Carry the three-magnitudes table (entries ≤ x small; length small; code big but ≤ π(x)) into that session.

Owed, standing (July 24–27, unchanged): the July-27 book-checks — pure-1-frame Lemma K run-merging at separator boundaries (the digit-2 deviation's outstanding obligation), the divisor characterization at w = 1, the §5 wording of the x = 0 case; and the older July-24–26 items — L₂(x)/L₃(x) strings, N₁₂'s sub-relation, L₃ case-check, ancestor-interpretation falsification, whole-domain instance question, the July-26 spellings checks.

Debt register — unchanged from July 27 (E-elimination and prime-base-13 were paid then): remaining are property 1 ⇒ property 2, mechanical ⇒ Arithmetic, adequacy 1930, general machine form of 1931, operation-agreement, instantiation from L₆ + L₇. Newly previewed (not yet due): Σ₁-completeness — the bridge from decidable to provable-or-refutable, expected to be installed and cashed in the next chapter (the reader's standing conjecture, reaffirmed today).

Method note. No chain today — a significance session, run in prose with the meter (Σ-complexity) as the single organizing idea and precise error-diagnosis as the mode (each confusion named, its false assumption isolated, the correction stated once). The July-27 chain format remains the standard for any future formal material.

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