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 / 篇目
- The punchline of the section
- How to use this document
- Part I — The meter: Σ₀ and Σ₁ are not "just arithmetic"
- Part II — The full ladder (the reader's follow-up)
- Part III — Proposition C: the closure algebra of Σ₁
- Part IV — Proposition C₁: scattered-∃ collapses to front-∃
- Part V — recursive = both it and its complement Σ₁
- Part VI — Theorem D: the same coding machine, rebuilt without E
- Part VII — What was actually new today
- Part VIII — Distinctions Ledger (confusions of the day → one-line resolutions)
- Part IX — Self-Test
- Part X — Position, owed items, debts
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
- 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.
- "different ⊊ disjoint." Σ₀ ⊊ Σ₁ (integers ⊊ rationals); C(a)'s vacuous quantifier is "decidable ⊆ r.e." in arithmetic dress.
- 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.
- 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.
- 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).
- 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.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月28日研读 · 斯穆里安《哥德尔不完备性定理》,第四章,书第50–55页(“关于Σ₁关系的更多内容”一节:命题C、命题C₁及两个推论,递归集/关系的定义;附录:定理D及练习1–8)· 与7月15–27日研读配套 · 性质:一次意义研读,而非形式化研读。7月27日争论证明的形状,今天则问对象意味着什么。读者带来一串困惑——“Σ₀/Σ₁感觉就只是算术”、跟不上证明、为什么递归定义为“自身及其补集都是Σ₁”、定理D究竟做什么用——每个困惑都化解为一个区分。没有建立新链条:读者已经独自做过定理D的证明,并拒绝练习集,要求改为从练习中提取其要点。贯穿线索,说一次便全天复用:Σ/Π的下标是一个复杂度计量器,本节每个结果都关乎如何读它、向上爬,或再降下来。
本节的关键结论
Σ/Π下标并不命名新的算术种类——它们按照定义需要多少无界搜索,给普通算术关系分级。 这一种读法驱动本节一切:
- Σ₀ = 只有有界量词 = 预先知道截止点的搜索 = 可判定。
- Σ₁ = Σ₀主体前一个无界∃ = 对是会停机,对否可能循环的搜索 = 递归可枚举(r.e.)/半可判定。
- 递归 = 关系及其补集都是Σ₁ = 可以确认是,也可以确认否 = 给可判定性一个名称。
四个结果是在这一计量器上的四种移动。命题C = 封闭代数:哪些操作使你留在Σ₁这一级(哪些操作——否定、无界∀——会把你推出去)。命题C₁ = 范式定理:散落在公式任何位置的存在量词都能拉到前面,所以“Σ公式”与“Σ₁关系”命名同一类。递归 = 两边均Σ₁ = 可判定的算术定义(无机器),即把波斯特定理当定义。定理D = 把句法谓词(项、公式、语句)从Σ₁向下撬回递归的工具——不用指数而重新得到可判定句法,这就是全章目的。
如何使用本文
第一部分确定计量器的意义(读者“只是算术”的反对)。第二部分是读者自己的追问——完整阶梯Σ₂、Σ₃……、“更不可判定?”以及真正的上限在哪里——保留下来,因为其余内容都位于这张地图上。第三至五部分按书中顺序走过三个命题,各以它解决的困惑开头。第六部分不逐题磨练,而从练习1–8提取定理D的要点,并记录读者所需的两项变量角色纠正。第七部分提炼今天真正新增的内容。第八部分为区分表(当天困惑 → 一句话解答);第九部分自测;第十部分进度与欠账。今天没有形式链条——读者已在7月27日掌握定理E的链条,并在本次之前私下做过定理D证明。
第一部分——计量器:Σ₀与Σ₁不是“只是算术”
读者反对意见的准确陈述:“Σ₀和Σ₁对我来说感觉就只是算术。”一半为真,假的那一半却是全部要点。
- 真的一半:每个Σ₀关系和每个Σ₁关系都是普通算术关系。下标没有召唤新对象。
- 假的一半——因此它没增加任何东西:它增加了一种测量。不是每个算术关系都属于Σ₀或Σ₁;算术关系可能需要交替无界量词组成的长塔。下标计量定义该关系的最简单公式中无界量词的结构——Σ₀ = 零个无界量词(全有界),Σ₁ = Σ₀主体前一个无界∃块。
最低两级在计算上意味着什么(使这种分级值得保留的回报):
| 层级 | 逻辑形式 | 搜索 | 判定 |
|---|---|---|---|
| Σ₀ | 所有量词有界 | 预先知道截止点 | 总会停机 → 可判定 |
| Σ₁ | ∃y(Σ₀主体) | y = 0, 1, 2, … 无界 | 对是停机,对否可能循环 → r.e. |
使之具体的对比(本次的锚点例子):
- “x是素数”——
x ≥ 2 ∧ (∀d ≤ x)(∀e ≤ x)[d·e = x ⊃ (d=1 ∨ e=1)]。每个量词以x为界;检查不超过x的因子,保证停机。Σ₀,可判定。 - “x可证”——
∃p [p编码x的一个证明]。内部检查有界(Σ₀);外部∃p无界——相对于x,证明可以任意长,所以不存在截止点。Σ₁,半可判定,一般不可判定。
素数与可证 = 有界且终止与只能确认的无界搜索 = Σ₀/Σ₁区分的全部意义。
为什么这本书如此倚重Σ。 (1) 哥德尔策略把证明算术化:“p证明x”是Σ₀,所以“x可证”是Σ₁——可证性的复杂度恰好是一个无界存在量词。(2) 斯穆里安在没有机器的情况下构造可计算性:Σ₁就是他对“r.e.”的替代物,递归将从它构成。所以“全都只是算术”的感觉正是设计成功——可计算性已被吸收进算术可定义性。
第二部分——完整阶梯(读者的追问)
读者问:Σ₂、Σ₃……是什么;它们是否“更不可判定”;有没有“彻底”不可判定的门槛?保留这些,因为它们是本节所处的地形。
构造(算术层级)。 连续同型量词可合并(∃x∃y通过配对合并),所以只数交替:
Σ₀ = Π₀ 没有无界量词
Σ₁ = ∃(Σ₀) Π₁ = ∀(Σ₀)
Σ₂ = ∃∀(Σ₀) Π₂ = ∀∃(Σ₀)
Σ₃ = ∃∀∃(Σ₀) …
下标 = 交替无界块数;Σ与Π = 最外块是∃还是∀。锚点:Σ₁ = “P在a上停机”;Π₁ = “P在a上永不停机”(一致性/哥德尔语句住在这里);Π₂ = “P在每个输入上停机”(全性);Σ₂ = “P只在有限多个输入上停机”。层级严格(哥德尔–克里尼):每次交替都换来确实新的可定义集。
“更不可判定?”——是,但不可判定性在第1级就已开启,而非更晚。 - 只有底层可判定:集合可判定,当且仅当它是Δ₁ = 同时是Σ₁和Π₁(这是第五部分定义的预告)。一旦有Σ₁但非Π₁——停机问题——第1级就已有不可判定性。 - 沿阶梯增长的是分级的不可判定性,由预言机(免费回答某个固定困难集合成员关系的装置)精确化:波斯特定理——Σ_{n+1} = 相对于最难Σ_n集的预言机为r.e.的集合。Σ₁ = 直接半可判定;Σ₂ = 给定停机问题预言机后半可判定;如此沿图灵跳跃0′、0″、0‴……上升。更高 = “如果可咨询前一级的不可解问题,就可通过搜索求解”。
门槛问题——区分“不可判定”的两个意义: - 意义A(一个集合):没有算法判定成员关系。由整个层级分级;没有有限顶点(对每个n,都有某个Σ_{n+1}集逃出Σ_n ∪ Π_n)——但在所有层级之上确有真正上限:由塔尔斯基真理不可定义性,真算术语句集对任何n都不是Σ_n——不仅不可判定,甚至不可用算术定义。这是最强意义的“彻底不可判定”。 - 意义B(一个理论中的语句):既不可证也不可反驳——独立,哥德尔的意义。这里门槛低而精确:在恰切系统中,每个真Σ₁语句都可证(Σ₁‑完备性——本章正构造的性质),所以Σ₁层没有真的独立语句;首批真却不可证的语句出现在Π₁(Con、哥德尔语句)。Σ₁ → Π₁的跳跃是哥德尔独立性诞生之处。
读者在这里掌握“最粗略的概念”便继续——关键收获仅是Σ₁是严格无限阶梯中的一级,以及可判定 = Δ₁ = 两个方向均Σ₁,第五部分需要这一点。
第三部分——命题C:Σ₁的封闭代数
它澄清的困惑(当天的核心):读者把“Σ₁不同于Σ₀”读成“不相交”,于是卡在C(a)——“每个Σ₀关系怎么同时还是Σ₁?”
解决——“不同”意味着“不相等”,关系是包含:
Σ₀ ⊊ Σ₁ (真子集)
恰如ℤ ⊊ ℚ:每个整数都是有理数(3 = 3/1),但两类仍不同,因为ℚ有非整数成员。每个Σ₀关系都是Σ₁;Σ₁仍有区别,因为它有非Σ₀成员(如“可证”)。没有矛盾——只是“不同”一词承担了过多含义。
C(a)——空量词。 Σ₁意味着∃y(Σ₀主体)。给定Σ₀关系R(x),加一个无所作为的量词:R(x) ⟺ ∃y R(x),y不出现在R中。任意y都可,所以它恰在R为真时真,而且现在有Σ₁形状。计算说明:判定程序本来就是确认程序——可判定 ⊆ r.e.。
完整命题——五个条款,每个证明一种操作使你留在Σ₁中:
| 条款 | 操作 | 机制 |
|---|---|---|
| (a) | Σ₀ ⟹ Σ₁ | 空∃ |
| (b) | 吸收一个无界∃ | 两个∃合并:∃y∃z S ⟺ ∃w (∃y≤w)(∃z≤w)S(取w为最大值),内部是Σ₀ |
| (c) | ∧和∨ | 给见证重命名,把∃推出,归于(b) |
| (d) | 有界∃及有界∀ | 有界∃直接;有界∀才是深的一项——见下 |
| (e) | R ⊃ S,其中R为Σ₀ | ¬R ∨ S;¬R是Σ₀(Σ₀在否定下封闭),故由(a)为Σ₁,再用(c) |
关键条款——有界全称,C(d)。 为什么(∀y≤z)R仍是Σ₁,无界(∀y)R却不是?展开R = ∃w S(S为Σ₀):
(∀y≤z) ∃w S(x,y,w) ⟺ ∃v (∀y≤z)(∃w≤v) S(x,y,w)
统一设界步骤(⟹):对每个y ≤ z选见证w_y;y只有有限多个(即z+1个),所以 v := max(w₀,…,w_z) 是一个单一上限,每个y都能在其下找到见证。内部全有界 → Σ₀;外部∃v → Σ₁。“有限多项要求,把见证收在同一上限之下”就是全部技巧——它也准确指出为什么无界∀失败:无限多个w_y,不保证有最大值,无法合并——于是逃到Π₂。从内部看到同一阶梯。
C作为整体的意义。 它是工具箱:原子部件一旦是Σ₀/Σ₁,就可用(a)–(e)自由组合,结果由构造为Σ₁,无须展开为原始形式。显眼缺席的——否定、无界∀——有意缺席:它们恰是爬升层级的操作。C仔细清点“保持r.e.时可做的一切”;其缺口与条目同样有意义。从计算上说,这是r.e.集的标准封闭性(∪、∩、投影、有界量化),以句法方式、无机器地证明。
第四部分——命题C₁:分散∃合并成前置∃
它为何不平凡(必须守住的区分):Σ公式(句法对象)由Σ₀公式通过∧、∨、有界∀、有界∃、无界∃构成——这些∃可在任何位置,深埋合取和有界量词内部。Σ₁(语义形状)要求一个整齐的∃块在最前面。所以
命题C₁:每个Σ关系都是Σ₁——存在量词无论散落得多深,该关系总能重写成Σ₀主体前单个∃。
一个范式定理。若不区分两类,C₁就读成“Σ₁是Σ₁”(空洞);一旦看到Σ公式允许埋藏∃,C₁就有真实内容,而归纳是覆盖每种埋藏模式的唯一办法。
归纳如何运行。 “度”= 形成步骤数(解析树高度)。对度作强归纳:假设每个更短的Σ公式都表达Σ₁关系,再按最外层操作分类。关键——每条形成规则都恰好匹配命题C的一个条款:
| Σ公式是…… | 由哪条款为Σ₁ |
|---|---|
| Σ₀公式(基础) | C(a) |
| G ∧ H / G ∨ H | C(c) |
| (∃x≤t)G / (∀x≤t)G | C(d) |
| ∃x G | C(b) |
| F₀ ⊃ G,F₀为Σ₀公式 | C(e) |
基础是Σ₁;每步保持Σ₁;归纳把结论扫遍整棵树。∎(书中“正规”的措辞仅是变量卫生——约束变量与自由变量分开——不是概念问题。)
C与C₁的关系(要带走的东西)。 C证明“一次操作保持Σ₁”;C₁的归纳把这些单步沿任意深公式连成链。C恰有五条,因为它们恰是Σ公式的五条形成规则——C是为使C₁归纳没有缺口而反向设计的。局部封闭性(C)→ 全局范式(C₁),以结构归纳为桥。
这换来什么许可。 三个名称,同一个类:Σ关系(易写)= Σ₁关系(易推理,一次搜索)= r.e.。现在要证明某物为Σ₁,只须展示它的任意Σ公式——存在量词爱落哪儿落哪儿——C₁免费给出清晰Σ₁形式。之后证明编码关系须证明为Σ₁时,这使斯穆里安免去记录整理;它也提供紧随其后的两个推论(A为Σ₁ ⟹ A*为Σ₁;集合P、R为Σ₁),读者认为由此前结果直接可得,没有停留。
第五部分——递归 = 自身及其补集均为Σ₁
定义。 集合/关系递归,当且仅当自身及其补集都是Σ₁。函数f递归,当且仅当其图f(x) = y递归。
为什么是这个定义(读者重构了论证;在此补上唯一缺口)。 读者自己的话——一个Σ₁搜索仅半可判定;若对面也是Σ₁,则“在对面搜索一个是的否定性搜索(确定的反驳)也会终止”,于是关系被钉定为完全可判定。正确。准确写出:
- A为Σ₁ → 搜索 P_A 恰在x ∈ A时停机并回答是(确认成员关系)。
- Ā为Σ₁ → 搜索 P_Ā 恰在x ∉ A时停机并回答是(这里的是 = 对x ∈ A的确定反驳)。
- 交错运行它们(交替步骤,使两者都不被饿死)。哪个停机,就给出判定。
读者略过的缺口——为什么保证有一个搜索停机? 单个Σ₁搜索本身没有任何东西强制终止。强制它的是搜索外部的事实:每个输入要么在A中,要么在Ā中,没有第三种选择,每种情况都有相应搜索会找到的见证。两个Σ₁定义把全部输入划分为各自的成功情况——没有漏网输入。所以任何单独的Σ₁都不够:只有P_A时,x ∉ A的输入会永远挂起,你无法区分“尚未”与“永不”。补集搜索把这种沉默转成确定的否。
给它名字。 这就是把波斯特定理(A可判定 ⟺ A与Ā都r.e.)当成可判定性的定义——用纯算术陈述,没有机器。不是“A是Σ₁”(仅半可判定),不是“A是Σ₀”(太窄——许多可判定集的定义需要无界搜索):“两边均Σ₁”精确落在可判定集上。
须防的滑动——“可判定”≠“可证或可反驳”。 读者最后把两者等同;它们相差一个要素: - 可判定 = 一个算法解决它(递归通过交错运行提供的结果); - 可证或可反驳 = 一个形式系统S导出“x ∈ A”或“x ∉ A”。
它们仅经S的Σ₁‑完备性才重合(S证明每个真Σ₁语句):若A递归,“x ∈ A”“x ∉ A”中一个是真Σ₁语句,所以Σ₁完备的S证明真的那个——算法判定作为证明反映进S内部。可判定性恰通过Σ₁‑完备性变成形式可证性——本章仍在建造的桥,下一章兑现(读者持续的猜想,得到重申)。
为什么费心命名“递归”——向前的钩子。 为了能指出什么不是递归的。后面的核心:“x是可证公式”是 Σ₁(搜索证明),但其补集不是Σ₁——可证性是r.e.,却不递归:半可判定,不可判定。这个唯一缺口——Σ₁没有Σ₁补集,所以无交错运行可救——就是不可判定性与不完备性所在。定义就是为清楚陈述这一失败而存在。
第六部分——定理D:同一编码机器,不用E重建
定理D是见证设界引理:对于条目均≤x的任何有限序列,它给出其编码的一个显式可计算上限π(x)。对照第三章自己的算术化关系编号表(命题3,第33–34页),目的最清楚,编号从(1)到(17)。关系 (1)–(15) 是全部句法与证明装置——下标串(Sb)、变量(Var)、数码(Num = Pow₁₃)、连接关系、形成序列及项/公式谓词(Seqt、tm、Seqf、fm)、原子公式、全称化(Gen)、公理(A)、肯定前件(M.P.)、可推导性(Der),最后是 Pf(x) = “x是证明”(15)——而 (16)–(17) 是可证性与可反驳性,P_E(x) = ∃y(Pf(y) ∧ x ∈ y) 与 R_E(x) = P_E(neg(x))。针对这张表,架构只有一句话:
定理D通过练习1–8兑现,证明(1)–(15)递归(可判定)——使(16)可证性与(17)可反驳性成为Σ₁。
(16)–(17)各自在递归证明关系(15)上加一个无界∃:清晰的Σ₁形状——可判定主体、单个存在量词——且由丘奇结果,不递归。整个递归/Σ₁分界恰落在 (15)/(16)边界:检查证明可判定,找到证明仅半可判定。
讲机制之前先作两项精确化。第一,定理D并不对十五项均匀用力。(1)–(15)中大多数已直接是Σ₀——Num、有界编码关系、M.P.、Der、公理检查——只有那些通过形成序列上的无界存在量词定义的关系需要定理D:经Seqt(5)定义的tm(6),经Seqf(10)定义的fm(11),以及建立其上的Pf(15)。这些是朴素地为Σ₁的关系;定理D给搜索设界,把它们降为递归,其余免费得到。练习6记录的集体结果——“(1)–(15)全部递归”——正是(16)–(17)的基础。第二,读者已做过证明定理D的十三进制长度论证,只要其意义;最清楚的方式不是磨完练习,而是看编码装置被构造两次——一次在第三章以指数E为原始符号,一次在这里不用它——因为定理D恰是去掉E时必须重新锻造的梁。
背后的单一步骤在关系(6)中可见。无界时,“x是项”读作tm(x) ⟺ ∃y[y编码项的形成序列 ∧ x出现在其中],无界∃y使它为Σ₁,却不保证可判定。定理D给见证封顶——x的形成序列条目≤x、长度有界,所以其编码≤π(x)——定义收紧为
tm(x) ⟺ (∃y ≤ π(x))[y编码形成序列 ∧ x出现在其中] (练习4)
搜索如今有界。练习1–3组装工具箱(图为Σ₁的函数递归;π自身递归;递归界限下的有界搜索仍递归),练习4–7以这种方式将每个朴素Σ₁关系向下推(项、公式、编码关系、语句),练习8则把结果跨过(15)/(16)门槛——可证公式集r.e.当且仅当可证语句集r.e.,递归当且仅当递归。
两次构造并排看
第三章构造与第四章构造相差一项特权。语言中有E时,可以把13^(v)写作一个项,指数v是变量;无E时则不行,每个倚赖这一特权的构造都获得一个不带级数的对应物。逐行横向读取,就是全部故事:
| 同一任务 | 第三章——有E | 第四章——无E(定理D) |
|---|---|---|
| 命名13的幂 | 写13^(v),v为变量——从指数计算 |
识别它(13的幂 = 每个≠1的因子均为13倍数的数;7月27日S1–S2),并以序关系测试定位所需者(大于n的最小者;S4) |
| 连接两个字符串 | x ∗ y = x·13^(ℓ(y)) + y——指数项 |
Con:“z = m·u + n,u是大于n的最小13的幂”——不带级数,Σ₀ |
| 给编码设界 | 编码 ≤ 13^(总长度)——一个项,一眼为真 |
证明编码 ≤ π(x)(定理D),并证明π递归(练习2) |
| 指数处在哪里 | 一个变量或表达式——带级数 | 固定目标,通过识别抵达——不带级数 |
沿右栏向下读,无指数方法是一条始终坚持的纪律:永不让变量站在指数位置。本章触及的每个13的幂都是特定的数,不是通过求值13^(某物)得到,而是先识别某个数为13的幂,再通过已在手的数之间的序关系钉定是哪一个。这是读者如今第四次遇到的带级数/不带级数区分,也就是“不用指数的算术”的全部意义。(经典编码以另一调式讲述同一故事:哥德尔1931年方案⟨a₁,…,aₖ⟩ = 2^(a₁+1)·3^(a₂+1)·⋯直接把条目放进指数,其上限pₙ^((n+1)·n)又是一个可以直接写下的项——有E便利的最纯形式。)
为什么有且只有一行成为定理
四项对应中有三项只是用一个公式换另一个。第三项在种类上不同。有E时,界限编码 ≤ 13^(总长度)由项的形状本身为真——没什么要证明。无E时,没有这样的项,所以必须论证界限;论证分两步,都留在+、·内部。首先数数位:连接编码最多占(最长条目长度)·(条目数)个十三进制位置——一个乘积,语言能形成。然后从数位计数跨到13的幂:L位的十三进制字符串小于具有L+1位的那个特定13的幂,而这个特定幂以不带级数的方式抵达。把计数与跨越接起来,就是定理D。因此它之为定理不是偶然——恰是在这一行中,去掉E使书写的项变成证明义务的代价;练习2(π递归)是同一重新锻造的后半,使得来不易的界限可用于+、·公式。
E曾代替什么——为什么π不是它的伪装
从这种对应看,E的全部贡献是允许以指数命名幂。它从来不是表达能力来源——定理E已说明每个指数事实都能在+、·中定义——只是便利来源:有E时那些事实处于Σ₀(有界、廉价),无E时至多能保证Σ₁。这化解了读者“π就是指数”的尖锐反对。禁令针对的是公式内部作为运算的指数——带级数的a^b = c,或指数为变量的13^(v)项——而非碰巧是幂的数;无论语言能说什么,13^k都在ℕ中。π的值是13的幂,但π以不带级数方式定义,且确实是递归函数(练习2),所以它恰引入E会提供的大小,而不引入任何被禁的运算。π只是右栏替代左栏。
哪里确实强制不用指数
对应关系可能令人以为这里一切都必须避开E,值得准确说明,因为并非如此。到附录时,E已可用——定理E已证——指数自身递归(具有Σ₁图的全函数递归,练习1)。所以用E构成的界限,比如B(x) = 13^(g(x))且g递归,自身也会递归,句法谓词同样会递归:这里没有什么禁止用E。真正的必要性在前一章、构造定理E的内部:证书编码需要编码界限时,E尚未定义——在那里用E会循环。定理D的内容——见证有一个关于x的可计算函数上限——无论如何都需要,因为E只改变已知界限的写法,不改变是否知道界限。所以诚实的地图有三项:定理D内容始终必需;定理E阶段必须无指数设界,否则循环;附录中无指数设界则是清晰的方法选择,而非必要。(事实上有两条无指数路线——斯穆里安十三进制连接,由定理D设界;以及哥德尔经中国剩余定理的β函数,即7月27日推迟的说明(2)证明;真正使用指数的是素数幂方法,而斯穆里安选了十三进制。)
正确读定理D
两项精确化避免误读引理——都来自读者自己的纠正。第一是逻辑方向。很容易把它改述为“找一个大于x的n,让编码放在π(x)之下”,但这把一切颠倒了;没有选什么比x更大的东西。必须区分三个量:
| 量 | 大小 | 角色 |
|---|---|---|
| 见证的条目aᵢ | 小,≤x | 由对象结构给定 |
| 长度k | 小,有界 | 给定 |
| 整个序列的编码 | 大,但≤π(x) | 定理D的结论 |
条目和长度因对象自身结构而小——条目界限就是x——定理效力单向运行:内容有界 ⟹ 编码有界。不能给任意序列编码封顶;只有内容已受控时才行。(读者的“π(x) > x”是错放槽位:π(x)给编码封顶,条目仍≤x。)第二项精确化涉及界限做什么用。它不是仅仅“因为有界”就给出可判定性——递归是“两边均Σ₁”,从不要求有界性本身。无界时,tm的补集∀y¬[…]是Π₁,不明显为Σ₁;界限的唯一任务是把该无界∀变成有界∀,后者为Σ₁,使两边同时Σ₁。为此,只需它确实给见证封顶(定理D),且是递归函数(练习2)。有界性是这里达成递归的方式,不是递归是什么。
为什么证明检查必须停机
这一切底下,是哥德尔为何需要这些东西,其关键正是本节不断构造的区分。Σ₁测试是半判定:搜索见证,若存在就找到并停机回答是,若不存在,搜索永远继续,确定的否从不到来。递归测试是完全判定:对每个输入——真正证明或一页废话——都会停机,回答是或否。“可能陷入循环的测试”是前一种,危险恰在否定情况显现:给它一个根本不是证明的畸形候选,只有Σ₁的检查器可能永远磨下去,从不返回证明检查应给的“否”。
所以确实——证明关系本身,即书中的 Pf(x) = “x是证明”(15),必须递归,而不能仅Σ₁。这就是练习1–8保障的:x是否编码公式序列,每行是否公理或经规则从先前行推出——每项都是有界、会终止的检查,所以Pf对每个输入停机,废料也包括在内。这不是吹毛求疵的细节。递归证明检查是有效公理化形式系统的算术面貌——公理可判定、规则可判定,因此证明可判定——哥德尔定理恰针对这一类。边界情形让必要性鲜明:去掉有效性,把所有真语句作为公理,就得到完备性,却失去可判定证明检查(由塔尔斯基,它甚至不再算术)。这是从递归一侧看7月27日的所有真语句扩张——可判定证明检查恰是不完备性需要的假设,放弃它恰是逃出定理的方式。
回报在 (15)/(16)边界两侧的不对称。检查证明可判定;找到证明则不然。Pf(15)递归,但在前面放一个无界∃,
P_E(x) ⟺ ∃y (Pf(y) ∧ x ∈ y) (关系16)
就落在Σ₁——半可判定,且由丘奇不递归:定理总能通过展示证明确认,却没有一般程序对每个非定理都停机回答否。(可反驳性R_E(17) = P_E(neg(x))随行,同样理由为Σ₁。)单个无界存在量词下的递归主体,恰是不完备性论证使用的形状——只有主体可判定,它才是如此清晰的形状。(一个诚实限定:即便Pf仅为Σ₁,“P_E是Σ₁”实际上仍成立,因为外部∃y会由C(b)吸收任何内部搜索。强制Pf递归的不是P_E的复杂度,而是“形式系统”的意义——证明检查必须终止——再加上Σ₁‑完备性,它需要系统真正判定其有界句法条件。定理D在+、·中不用E提供这一可判定性。)
第七部分——今天真正新增了什么
- Σ下标是搜索复杂度计量器,而非算术种类。 Σ₀ = 有界/可判定,Σ₁ = 一个无界∃/r.e.;上面的层级是按预言机强度分级的严格无限阶梯,只有塔尔斯基非算术的真理为其上限。素数与可证是计量器的校准例子。
- “不同 ⊊ 不相交。” Σ₀ ⊊ Σ₁(整数 ⊊ 有理数);C(a)的空量词是披着算术外衣的“可判定 ⊆ r.e.”。
- 命题C是封闭代数,其缺口有意为之。 有界∀通过统一设界保留(有限多见证,一个最大值);无界∀与¬省略,因为它们爬升阶梯。
- C₁是范式,其归纳解释C为何恰有五条——每条对应Σ公式一条形成规则。分散∃ = 前置∃;三个名称(Σ关系/Σ₁/r.e.)指同一类。
- 递归 = 两边均Σ₁ = 波斯特定理作定义——交错运行给出可判定,而可判定 → 可证或可反驳需要Σ₁‑完备性这个额外铰链(尚未安装)。
- 定理D是给见证设界的撬杆,不用指数便把句法从Σ₁向下拉到递归;练习是把它的一个思想逐集合应用。
第八部分——区分表(当天的混淆 → 一句话解答)
| 问题 | 解答 |
|---|---|
| Σ₀/Σ₁“感觉就只是算术” | 它们是算术关系;下标按无界搜索复杂度给它们分级(Σ₀可判定,Σ₁ r.e.)。不是每个算术关系都属于Σ₀/Σ₁——阶梯还有更高层。 |
| Σ₂、Σ₃……是什么?“更不可判定”吗? | 无界量词的交替数(算术层级)。不可判定性从Σ₁(停机问题)开始,而非更晚;更高级仅在预言机强度意义上“更不可判定”(波斯特/图灵跳跃)。 |
| 有没有彻底不可判定的门槛? | 对集合:无有限顶点,但所有层级之上有真正上限——算术真理对任何n都不是Σ_n(塔尔斯基)。对语句(独立性):Σ₁无(真Σ₁ ⇒ 可证),最早在Π₁(Con、哥德尔语句)。 |
| 若Σ₁不同于Σ₀,为什么每个Σ₀关系也为Σ₁(C a)? | “不同”=“不相等”,不是“不相交”:Σ₀ ⊊ Σ₁(如ℤ ⊊ ℚ)。空∃使任何Σ₀关系具有Σ₁形状。 |
| 跟不上命题C的证明 | 每条证明一种操作留在Σ₁:(b) 两个∃以最大值合并,(c) 把∃推出,(d) 有界量词——有界∀经统一设界,(e) ¬R∨S,其中¬R为Σ₀。 |
| 为什么有界∀保持Σ₁,无界∀却不? | 有限多个y ≤ z ⇒ 有限多见证 ⇒ 一个最大上限v;合并为∃v(∀y≤z)(∃w≤v)。无界∀不保证最大值——逃到Π₂。 |
| C₁(“每个Σ关系为Σ₁”)如何归纳? | Σ公式允许∃散落任何位置;C₁说它们可拉到前面。对公式度强归纳;每个形成规则 = C一个条款(基础=a,∧∨=c,有界=d,∃=b,⊃=e)。 |
| 为什么递归定义为“自身及补集均Σ₁”? | 交错运行两个Σ₁搜索:一个确认是,另一个确认否;排中律保证一个停机。= 可判定。把波斯特定理当定义,无机器。 |
| “……所以可判定,即可证或可反驳?” | 不相同:可判定 = 算法;可证或可反驳 = 在系统S内。仅经Σ₁‑完备性(真Σ₁ ⇒ 可证)才重合,这座桥下一章到来。 |
| 定理D做什么用? | 放在第三章清单(命题3)中:通过练习1–8,证明关系 (1)–(15)——项/公式/证明装置,顶点为 Pf(15)——递归,使 (16) P_E = ∃y(Pf(y)∧x∈y) 与 (17) R_E = P_E(neg(x)) 清晰地为 Σ₁。它只作用于朴素Σ₁的形成序列关系(tm/Seqt 6/5、fm/Seqf 11/10、Pf15),以π(x)给见证封顶;(1)–(15)其余已经Σ₀。递归/Σ₁分界 = (15)/(16)边界 = 检查证明与找到证明。 |
| 定理D = “找n大于x,让编码放在π(x)下”? | 颠倒了。条目由结构≤x(n := x,无须选择);定理效力是编码的上界(≤π(x))。单向蕴涵内容有界 ⟹ 编码有界。 |
| π(x)是13的幂——不就用了本章禁止的指数? | 不。禁令针对公式内部作为运算的指数(带级数a^b=c,或变量v的13^(v)),不针对是幂的数——13^k总在ℕ中。π是递归函数(练习2),其图通过不带级数的“大于……的最小13的幂”机制在+、·中可定义;值是指数的,图却简单。第四次跨越带级数/不带级数断崖。 |
| 此前(有E)的机器如何用指数,区别是什么? | 它允许指数为变量:第三章把13^(ℓ(y))写成项,以项13^(长度)给编码设界(素数幂编码也把条目放指数,免费得到上限pₙ^((n+1)·n))。无E时13^(v)写不了,所以界限必须计数(数位,经+、·),再跨越到识别的幂——计数加跨越就是定理D。分界 = 变量指数。 |
| β函数是使用指数的方法吗? | 不——β(哥德尔中国剩余定理编码)是另一条无指数路线(推迟的说明2)。使用指数 = 素数幂编码;无指数 = 十三进制/定理D 及 β。斯穆里安选十三进制。 |
| “有界∃”=可判定吗?Σ₁“界限”不就不是界限?(读者发现——纠正导师夸大) | 递归 = 两边均Σ₁;不要求有界或Σ₀。有界化只是把原本Π₁的补集(∀y¬…)变成有界∀(Σ₁)的机制。只需界限(a)确实给见证封顶(定理D),(b)是递归函数(练习2)——别无其他。 |
| 那不能用E设界,跳过无指数路线吗? | 附录中可以:exp 递归(Σ₁全函数 ⇒ 递归,练习1),所以由E构成的界限递归,给出递归谓词。只有此前构造定理E内部才强制无指数(E尚未定义 ⇒ 循环)。定理D的内容(见证≤π(x))无论如何需要;附录中不带级数的表达是经济选择,不是必要。 |
| “可能循环的测试”——是什么,“p是x的证明”必须递归吗? | 只有Σ₁的测试是半判定:对肯定情况停机回答是,对否定情况可能永远循环(如畸形p)。证明必须可验证,所以 Prf(p,x)必须递归(每个输入停机回答是/否)——“有效公理化”的算术面貌。不对称:检查证明(Prf)递归;找到证明(Provable = ∃p Prf)为Σ₁,且由丘奇不递归。(限定:单是Σ₁可证性即便Prf为Σ₁也由C(b)合并保持;强制Prf递归的是“形式系统”的意义 + Σ₁‑完备性。) |
第九部分——自测
不看材料完成;每题后附答案。
1. 用一句话说Σ下标测量什么,Σ₀、Σ₁的计算意义是什么?
答案
它计量最简单定义公式的无界量词(交替)结构:Σ₀ = 所有量词有界 = 可判定(已知截止点的搜索);Σ₁ = Σ₀主体前一个无界∃ = 递归可枚举(对是停机,对否可能循环)。
2. 给出本次用于校准Σ₀/Σ₁分界的两个例子,并说明各属哪类。
答案
“x是素数”——所有量词以x为界,保证停机 = Σ₀/可判定。“x可证”=∃p(p证明x),p无界,仅对是停机 = Σ₁/半可判定。
3. 解决:“Σ₁不同于Σ₀,所以没有东西能同时属于两者。”错误在哪?
答案
“不同”是“不相等”,不是“不相交”。Σ₀ ⊊ Σ₁(真子集,如ℤ ⊊ ℚ):所有Σ₀都是Σ₁(C a,经空∃),但Σ₁严格更大(如“可证”为Σ₁,非Σ₀)。
4. 为什么有界∀使关系保持Σ₁,无界∀却不?说出操作。
答案
统一设界:对(∀y≤z)∃w S,y只有z+1个值,所以其见证有单一最大值v;重写为∃v (∀y≤z)(∃w≤v)S,内部Σ₀,整体Σ₁。无界∀给出无限多见证,不保证最大值——无法合并,逃到Π₂。
5. 陈述命题C₁,说明为何不平凡,并用一行描述归纳。
答案
每个Σ关系都是Σ₁。不平凡,因为Σ公式允许无界∃散落任何位置,而Σ₁要求单个前置∃;C₁说它们总能拉到前面。对公式度归纳,每个形成规则由命题C匹配条款处理(基础=a,∧∨=c,有界=d,∃=b,⊃=e)。
6. 为什么命题C恰有五条?
答案
它们是Σ公式的五条形成规则;C反向设计,使C₁结构归纳没有缺口。局部封闭性(C)连成全局范式(C₁)。
7. 给出“A与Ā均Σ₁ ⟹ A可判定”的交错运行论证,并点名保证终止的事实。
答案
交错运行P_A(x∈A时停机回答是)与P_Ā(x∉A时停机回答是);哪个停机就给判定。成员关系的排中律保证终止——每个x在A或Ā中,两个搜索把全部输入划分成各自成功情况,所以总有一个停机。
8. 区分“可判定”与“可证或可反驳”,并说出它们之间的桥。
答案
可判定 = 算法解决(递归所给)。可证或可反驳 = 形式系统推出成员/非成员关系。桥 = Σ₁‑完备性:“x∈A”/“x∉A”中一个为真Σ₁语句,所以Σ₁完备系统证明它,把判定反映成证明。
9. 一句话说出定理D要点,以及它允许对“x是项”做何重写。
答案
当有限序列条目≤x时,它用显式π(x)给编码设界,把tm(x) ⟺ ∃y(y编码形成序列 ∧ x在其中)变成(∃y ≤ π(x))(…)——递归矩阵上的有界∃,因此递归,不仅是Σ₁。
10. 纠正错误陈述:“定理D让我们找一个大于x的n,使编码落在π(x)下。”
答案
没有选什么大于x的东西:条目由对象自身结构≤x(n := x)。定理内容是编码的上界(≤π(x))——单向蕴涵内容有界 ⟹ 编码有界。条目保持小(≤x);只有编码爬到π(x)。
11. 为什么定理D必须在本章证明而非引用,它重新得到什么?
答案
本章禁止指数,而在别处指数免费给序列编码设界(素数幂/β编码)。定理D是无指数替代,由十三进制长度论证得到;它重新得到句法装置(项、公式、语句、证明)的可判定性。
第十部分——进度、应做项目、欠账
进度:第四章第50–55页完成。 “关于Σ₁关系的更多内容”一节——命题C(五条全部理解,掌握有界∀的统一设界)、命题C₁(范式定理,掌握归纳↔条款对应)、推论1–2(作为此前结果的直接后果接受,未停留)、递归定义(掌握交错运行/波斯特定理读法,加上可判定与可证的区分)。附录:读者已私下做过定理D证明;这里从练习1–8提取其意义。书中接下来:附录之后的章节(第四章剩余各节/进入正式算术化)。
按读者选择推迟:练习1–8的完整解答——读者判断“我们确实需要做完所有练习才能充分探明这个思想”,但留待另一天。未来研读标记:练习1(Σ₁函数 ⇒ 递归)与练习3(有界搜索保持递归)是工具箱;练习4(经π(x)定义tm(x))是要重新导出的代表性应用;练习8(2)(可证公式r.e./递归当且仅当可证语句如此)是通向下一章的桥。
今日新增持续欠账:读者自己对“π(x)作为编码上界”的理解已接受但尚未操练——明确说过,真正熟练需要做练习。把三个量的表(条目≤x且小;长度小;编码大但≤π(x))带到那次研读。
持续未做(7月24–27日,未变):7月27日对书检查——纯1框引理K在分隔边界的连续串合并(数位2偏离的未完成义务)、w = 1时的因子刻画、§5对x = 0情形的措辞;以及更早7月24–26日项目——L₂(x)/L₃(x)字符串、N₁₂子关系、L₃情况检查、祖先解释证伪、全域实例问题、7月26日拼写检查。
欠账记录——与7月27日相同(消去E与素数底13当时已偿还):剩余性质1 ⇒ 性质2、机械 ⇒ 算术的(Arithmetic)、1930年的恰切性、1931年的一般机器形式、运算一致、从L₆ + L₇得到实例化。新预告(尚未到期):Σ₁‑完备性——从可判定到可证或可反驳的桥,预期下一章安装并兑现(读者持续猜想,今日重申)。
方法记录。 今天无链条——一次意义研读,以计量器(Σ复杂度)为唯一组织思想,用散文推进,模式是精确诊断错误(给每个困惑命名,分离其错误假设,一次性陈述纠正)。7月27日的链条格式仍是未来任何形式材料的标准。
此前研读:7月15日(第一章)、17日(答案)、19–22日(第二章)、20及23日(练习)、24日及25日续篇(第三章§1)、26日(第三章§§2–4)、27日(第四章第40–50页,定理E)。本文件:第四章第50–55页。