Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness Theorems — Session 2026‑08‑04
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 / 篇目
- Chapter VII: Shepherdson's Representation Theorems (pp. 86–96) — representability of every Σ₁ set from simple consistency alone
- Orientation — the problem, and Shepherdson's one trick
- Part 0 — the one‑sentence shift, and what carries over
- Part I — the two tracks: end state, payload, assembly
- Part II — Citable glossary
- Part III — the preparatory apparatus (four foundational questions)
- Part IV — the representation track, in full (verified against clean scans)
- Part V — the separation track: one formula, two teams, a race
- Part VI — §3 variants (Ex 4–10) and §4 the strengthenings
- Distinctions Ledger
- Self‑Test
- References & cross‑links
- What's ahead
Chapter VII: Shepherdson's Representation Theorems (pp. 86–96) — representability of every Σ₁ set from simple consistency alone
Orientation — the problem, and Shepherdson's one trick
Read this first; everything below is its unfolding.
The problem. To represent a Σ₁ set A is to build a formula F with F(n̄) provable ⟺ n∈A — a biconditional, so two obligations:
- (→) cover
A— members get proved. This is free: membership is a true, Σ₀‑witnessed fact, and the system proves true facts. - (←) dodge
~A— non‑members stay unproved. This is the whole difficulty, and it is a claim about the complement~A.
(←) is hard for one reason with two faces. A merely simply consistent system can prove false sentences (consistency forbids proving a sentence and its negation, not proving something false in ℕ) — so the natural "true‑on‑A" formula can leak provability onto non‑members (exactly the ω‑inconsistency pathology of Ex 9: ∃y R(n̄,y) provable with no real witness). And you can't route around this by policing the non‑members yourself, because ~A need not be Σ₁ (Post: only when A is recursive) — there's no enumeration of ~A to grab. You can neither trust the system to stay silent on ~A, nor force silence by enumerating it. Historically this (←) half was bought with ω‑consistency (the promise "no false witnessed ∃ is provable").
Shepherdson's trick — never confront ~A; make it lose a race. Build F as a self‑referential ≤‑race (Rosser's device, via the diagonal gadget Π): a sentence that pits the set's membership‑witnesses against the sentence's own proof/refutation‑witnesses, and asks which shows up first. Then:
- non‑membership never has to be enumerated or trusted — it surfaces only as the loser of a race between two things that genuinely are Σ₁ (the set
A, and the provability relation); - the only fact needed to adjudicate the race is simple consistency — a refutation cannot precede itself — no soundness, no ω‑consistency.
That single move — recast the impossible obligation about ~A as a winnable race between two Σ₁ objects, settled by simple consistency — is the whole chapter. The two tracks are just two settings of the same dial: feed the diagonal a weak separation and it represents one set (Track A); feed it a strong separation and it exactly separates a pair (Track B, which contains A).
New chapter, and it inverts the last one's polarity. Chapter VI used Rosser's ≤‑race to separate R* from P* — a one‑shot, aimed at undeciding a single sentence (incompleteness, a negative result). Chapter VII shows the same Rosser machinery, once packaged as the property "Rosser system," delivers the strongest positive result available: every Σ₁ set is representable — and still from nothing more than simple consistency.
Historically this was the surprise. At the time of Gödel's proof, the only known route to representing P* in P.A. ran through ω‑consistency. Ehrenfeucht–Feferman [1960] first showed all Σ₁ sets are representable in every simply consistent axiomatizable extension of (R) (combining a Rosser‑type argument with Myhill's recursion‑theoretic result). Shepherdson [1961] then found the direct, self‑contained route this chapter follows.
This session did two things: (i) cleared the preparatory apparatus — weak separation, the wrapper E[m̄,n̄] and its Gödel‑number function Π — through four foundational questions; then (ii) reconstructed and verified against clean scans the full representation chain Lemma 1* → Lemma 1 → Theorem S₁ → Theorem 1. The parallel separation chain is then made concrete through Shepherdson's actual formula φ (Part V) — Rosser's ρ with A and B on opposite sides of the race — with the three outcomes (provable on A, refutable on B, undecidable between) verified by that race; the §4 strengthenings are stated exactly.
Reading order follows the logical spine, not the book's page order.
Part 0 — the one‑sentence shift, and what carries over
Chapter VI's currency was separation; Chapter VII spends it to buy representation.
| Chapter VI (Rosser) | Chapter VII (Shepherdson) | |
|---|---|---|
| goal | undecide one sentence ⟹ incomplete (negative) | represent every Σ₁ set (positive) |
| tool | H separates R* from P* (one pair) |
S is a Rosser system: separates every disjoint Σ₁ pair |
| consistency used | simple | simple |
| headline | Theorem R — P.A. incomplete | Theorem S₁ — all Σ₁ sets representable |
The bridge between them is a single gadget introduced here: a diagonal self‑reference through provability, carried by a Gödel‑number function Π. Feed it a separating formula and it returns a representing one. Everything in the chapter is that gadget plus bookkeeping.
What we import unchanged from Ch. VI: the definition of a Rosser system, the ≤‑race formula, and the fact that every simply consistent axiomatizable extension of (R) is a Rosser system (the Ω₄, Ω₅ machinery, 08‑03 Lemma S / Thm 3). Chapter VII never re‑proves that; it consumes it (Theorem 1, Theorem 2).
Part I — the two tracks: end state, payload, assembly
GOAL of the chapter. Show that a simply consistent axiomatizable Rosser system represents every Σ₁ set — recovering, from simple consistency alone, what Gödel needed ω‑consistency for.
The one idea both tracks share. You can't represent a Σ₁ set A head‑on: representing A means controlling F(n̄) for n∉A too, and ~A need not be Σ₁ (Post: ~A is Σ₁ only when A is recursive). So instead —
build two Σ₁ relations out of
Aand a provability predicate, have the Rosser system separate them, and let a self‑referential diagonal convert that separation into representation.
The Rosser hypothesis supplies the separation; the diagonal ★ (via the wrapper Π) makes a sentence talk about its own provability; simple consistency does one small conversion. Both tracks run this method on the shared gadget wrapper E[m̄,n̄] → Π → Master Equivalence → diagonal ★. The tracks differ in one dial only: whether the separation fed to the diagonal is weak (one polarity) or strong (both polarities).
Track A — REPRESENTATION (weak separation → one polarity)
- End state. Every Σ₁ set
Ais representable: a formulaFwithn∈A ⟺ F(n̄)provable. — Theorem S₁; for extensions of (R), Theorem 1 (Ehrenfeucht–Feferman). - What it tells you. Provability tracks membership — one set, the provable/not‑provable polarity only. This is everything incompleteness and undecidability of the theory require.
- How assembled (3 rungs):
1.
Lemma 1*(engine) — from a weak separation of two relations, the diagonal gives one biconditionalF(n̄) provable ⟺ R(n,h). Spends nothing — pure fixed‑point logic. 2.Lemma 1— setR := "x∈A"; the engine yieldsF = E_h(v₁,h̄)representsA. 3.Theorem S₁— the Rosser hypothesis strongly separates the pairU,V; simple consistency (spent here, once) downgrades strong→weak; feedLemma 1.
Track B — SEPARATION (strong separation → both polarities)
- End state. Every disjoint pair of Σ₁ sets
A,Bis exactly separable: a formulaFwithn∈A ⟺provable,n∈B ⟺refutable, else undecidable. — Theorem S₂; for extensions of (R), Theorem 2 (Putnam–Smullyan). - What it tells you. Provability tracks
Aand refutability tracksB— two sets, both polarities. Strictly more than Track A: setB=∅and exact separation collapses to plain representation, so Track B contains Track A (S₂ ⟹ S₁). The extra — control of refutability — is what the inseparability and essential‑undecidability results need. - How assembled (3 rungs, the strong‑separation twin):
1.
Lemma 2*(engine) — from a strong separation, the diagonal run twice (once for provability, once for refutability) gives two biconditionalsprovable ⟺ R₁,refutable ⟺ R₂. Spends simple consistency — to stop the two outputs colliding. 2.Lemma 2— set the two "teams"R₁ = A∨Ref,R₂ = B∨Prov; the engine yieldsFexactly separatesAfromB. 3.Theorem S₂— the Rosser hypothesis supplies the strong separation directly (no downgrade); the two biconditionals are exact separation.
The one essential distinction
| Track A — representation | Track B — separation | |
|---|---|---|
| separation fed to the diagonal | weak | strong |
| polarities kept | provable only | provable and refutable |
| end state | represent one set | exactly separate a pair |
| logical strength | the headline | strictly stronger — implies A via B=∅ |
| powers downstream | incompleteness, undecidability | inseparability, essential undecidability |
They are not siblings. Track A is the clean headline (simplest proof, widest use); Track B is its strict upgrade. Same gadget, same three‑rung shape; the only structural difference is weak vs. strong separation into the engine — equivalently, discard vs. keep the refutable half.
Part II — Citable glossary
Carried: E_x = expression with Gödel number x; P = set of Gödel numbers of provable sentences; P*, R* from Ch. V/VI.
- represents
A(byF(v₁)):(∀n)[ S⊢F(n̄) ⟺ n∈A ]. Two‑directional; stated purely in provable / not‑provable — refutability never appears. - strongly separates
AfromB(= Ch. VI's "separates"):n∈A ⟹ S⊢F(n̄);n∈B ⟹ S⊢~F(n̄)(refutable). - weakly separates
AfromB— definition (the book's):Frepresents some supersetA'⊇AwithA'∩B=∅. Equivalent characterization:n∈A ⟹ S⊢F(n̄);n∈B ⟹ S⊬F(n̄)(not provable). The B‑clause softens "refutable" to "not provable." - exactly separates
AfromB(byF):n∈A ⟹provable;n∈B ⟹refutable;n∉A∪B ⟹undecidable. EquivalentlyFrepresentsAand~FrepresentsB— a double representation. - Rosser system for
n‑ary relations: for any Σ₁ relationsR₁,R₂, the differenceR₁−R₂is strongly separable fromR₂−R₁. for sets = then=1case. exact Rosser system for sets: every disjoint Σ₁ pair is exactly separable. - wrapper
E[m̄,n̄] := ∀v₁(v₁=m̄ ⊃ ∀v₂(v₂=n̄ ⊃ E)). A fixed syntactic frame around all ofE; never inspectsE's interior. Π(a,b,c)= Gödel number ofE_a[b̄,c̄]. A total concatenation function ofa,b,c; its graph is Σ₀.- (MEq) Master Equivalence:
(∀a,b,c)[ Π(a,b,c)∈P ⟺ E_a(b̄,c̄) provable ]. (IfE_aisn't a formula, both sides false.) Σ₁ in(a,b,c)sincePis Σ₁. Prov(x,y) := Π(y,x,y)∈P— the binary relation "E_y(x̄,ȳ)is provable." The slotysits in positions 1 and 3 (index and second argument); slot 2 holds the real inputx. Σ₁.- diagonal ★. Fix a formula
Ewith freev₁,v₂,h=⌜E⌝(soE=E_h); writeG_n := E_h(n̄,h̄). ThenProv(n,h) ⟺ G_n provable— the numberhdoing double duty is the entire self‑reference.
Part III — the preparatory apparatus (four foundational questions)
Before any theorem, four confusions had to be cleared. They are the reason the later proofs read cleanly.
III.1 Weak separation — definition vs. characterization (the order matters)
The definition is the superset one (def): F weakly separates A from B iff F represents some A'⊇A disjoint from B. The provable/not‑provable pair is a derived characterization, not the definition. Derivation, using representation's two clauses on A' = {n : S⊢F(n̄)}:
| # | claim | why |
|---|---|---|
| 1 | n∈A ⟹ S⊢F(n̄) |
A⊆A', and F represents A' (clause i: member ⟹ provable) |
| 2 | n∈B ⟹ S⊬F(n̄) |
A'∩B=∅ ⟹ n∉A', and F represents A' (clause ii: non‑member ⟹ not provable) |
So "not provable" is inherited verbatim from representation's negative clause (ii) — refutability is structurally absent from representation, hence cannot appear. Superset legitimately appears, but as A' (the set F actually represents), not as "A is its own superset."
Strong ⟹ weak (Ch. VI Lemma 1): from strong separation put A'={n:S⊢F(n̄)}; then A⊆A' (strong's provable half) and, for n∈B, S⊢~F(n̄) + simple consistency ⟹ S⊬F(n̄) ⟹ n∉A'. That lone step "refutable ⟹ not provable" is where the downgrade lives — the sole consistency cash, exactly as in Ch. VI.
Why A' is generally a proper superset. Split ℕ into three bands: A (forced provable), B (forced not‑provable), and the don't‑care region ∉A∪B (unconstrained). If F(n̄) happens to be provable on some don't‑care n, that n joins A'. So A' = A plus possibly harmless overshoot that avoids B. The superset has no special power; it is just the honest name for what F represents. And when B is the complement of A, the bands pinch — A⊆A'⊆(complement of B)=A — so A'=A and weak separation collapses to exact representation. Representation is the limiting case of weak separation against a full complement.
III.2 The wrapper E[m̄,n̄] and the function Π
Two statements the book makes back‑to‑back are not redundant:
- (1) if
Eis a formula whose only free variables arev₁,v₂, thenE[m̄,n̄]is a sentence equivalent toE(m̄,n̄); - (2) if
Eis any formula, thenE[m̄,n̄] ≡ E(m̄,n̄)is logically valid (⟹ provable inS⟹ provability transfers).
They differ on both axes. The single logical fact underneath is the double equality‑guard collapse ∀v(v=t ⊃ Φ) ≡ Φ(t) (valid by: instantiate v:=t with t=t; and substitution of equals), applied twice. From it: (2) is that fact; (1)'s "equivalent" is a semantic shadow of it — but (1)'s "is a sentence" is a separate, purely syntactic fact (the two ∀'s bind v₁,v₂; if those were the only frees, nothing dangles). So it is one logical fact + one independent syntactic fact, not two consequences of one cause. And both are needed: sentence‑hood (1) makes "provable" meaningful (only sentences lie in P); logical validity (2) makes provability transfer (mere semantic equivalence would not give S⊢E[m̄,n̄] ⟺ S⊢E(m̄,n̄) — you need the biconditional itself provable).
Why the wrapper at all? E[m̄,n̄] is a fixed frame prepended/appended around E — so ⌜E[m̄,n̄]⌝ = Π(⌜E⌝,m,n) is a trivial concatenation function, total on all x. Genuine substitution E(m̄,n̄) must hunt free occurrences and replace them — far messier to arithmetize. The wrapper buys the same provable‑equivalence with a clean Σ₀ coding function. This yields the Master Equivalence (MEq).
Junk filters itself out (why totality is harmless): if Π(x,y,z)∈P, then E_x[ȳ,z̄] is a provable sentence ⟹ well‑formed ⟹ the ⊃ has a formula on its right ⟹ E_x is automatically a formula. We never need a side hypothesis "x codes a formula" — membership in P forces it.
Part IV — the representation track, in full (verified against clean scans)
This is the spine, and every line below was checked against pp. 88–89.
Ch. VII Lemma 1* — the engine (spends nothing)
→ Role: convert a given weak separation into an exact biconditional. Consistency‑free; Rosser‑free. Pure diagonal logic.
The two relations (binary in x,y), with Prov = Π(y,x,y)∈P:
U(x,y) := R(x,y) ∧ Π(y,x,y)∉P("R holds, and the diagonal sentence is not provable")V(x,y) := Π(y,x,y)∈P ∧ ~R(x,y)("the diagonal sentence is provable, and R fails")
The ∉P / ∈P asymmetry is the whole engine — this was the crux we could not read until the clean scan, and the argument only closes with it (see the note after the proof).
Statement. For any relation R(x,y): if a formula E_h(v₁,v₂) (with h=⌜E_h⌝) weakly separates U from V, then (∀n)[ E_h(n̄,h̄) provable ⟺ R(n,h) ].
Proof. Weak separation at a generic tuple (n,m) (instance E_h(n̄,m̄)):
| clause | says |
|---|---|
| (1) | R(n,m) ∧ Π(m,n,m)∉P ⟹ S⊢E_h(n̄,m̄) |
| (2) | Π(m,n,m)∈P ∧ ~R(n,m) ⟹ S⊬E_h(n̄,m̄) |
Freeze m=h; write G = E_h(n̄,h̄). By ★, Π(h,n,h)∈P ⟺ G provable. The clauses become self‑refuting traps:
| says | |
|---|---|
| (1ₕ) | R(n,h) ∧ [G not provable] ⟹ G provable |
| (2ₕ) | [G provable] ∧ ~R(n,h) ⟹ G not provable |
| direction | argument |
|---|---|
R(n,h) ⟹ G provable |
Assume R(n,h). If G were not provable, (1ₕ)'s antecedent holds ⟹ G provable — a flat metalanguage contradiction. So G provable. |
G provable ⟹ R(n,h) |
Assume G provable. If ~R(n,h), (2ₕ)'s antecedent holds ⟹ G not provable — contradiction. So R(n,h). |
Hence G provable ⟺ R(n,h). ∎
Two things to mark.
1. No consistency, no Rosser. The contradictions are "this one fixed sentence G is both provable and not‑provable" in the metatheory — not a claim that S is consistent. The lemma is pure bookkeeping on the given separation.
2. The ∉P conjunct in U is load‑bearing. Had U carried Π∈P instead, (1ₕ) would read R(n,h) ∧ [G provable] ⟹ G provable — vacuous, and the forward direction collapses. The "not provable" conjunct is precisely what springs the trap. (This is the exact spot flagged two turns earlier as "will not fake"; the clean scan resolved it.)
Ch. VII Lemma 1 — Representation Lemma
Statement. For a set A: if [x∈A ∧ Π(y,x,y)∉P] is weakly separable from [Π(y,x,y)∈P ∧ x∉A], then A is representable; concretely, the separator E_h(v₁,v₂) gives E_h(v₁, h̄) represents A.
Proof. Lemma 1* with R(x,y):⟺ x∈A. Then R(n,h) ⟺ n∈A, so E_h(n̄,h̄) provable ⟺ n∈A, i.e. E_h(v₁,h̄) represents A. ∎ (The scan prints the first relation's connective as ∈P; it must read ∉P to match Lemma 1* and the Theorem S₁ proof — a typo we corrected against the argument.)
Ch. VII Theorem S₁ — Shepherdson's Representation Theorem
Statement. If S is a simply consistent axiomatizable Rosser system for binary relations, then every Σ₁ set A is representable in S.
Proof. Choose two Σ₁ relations:
| definition | Σ₁ because | |
|---|---|---|
R₁(x,y) |
x∈A |
A is Σ₁ |
R₂(x,y) |
Π(y,x,y)∈P (= Prov) |
S axiomatizable ⟹ P is Σ₁; Π's graph is Σ₀ |
Take their differences — the negations appear for free:
| # | claim | grounds |
|---|---|---|
| 1 | R₁−R₂ = (x∈A) ∧ Π(y,x,y)∉P = U and R₂−R₁ = Π(y,x,y)∈P ∧ ~(x∈A) = V |
set algebra |
| 2 | U strongly separable from V |
Rosser system (binary) on the Σ₁ pair R₁,R₂ |
| 3 | U weakly separable from V |
2 + simple consistency (strong ⟹ weak, III.1) |
| 4 | E_h(v₁,h̄) represents A |
3 + Lemma 1 ∎ |
The deep point — no complement need be Σ₁. The worry "~A isn't Σ₁, so how can we separate against it?" dissolves here: we hand the Rosser system two honestly Σ₁ relations R₁=A, R₂=Prov, and the difference operation manufactures both ~A and ~Prov at zero complexity cost. This is precisely Ch. VI's difference‑set trick (08‑03 Lemma S: "R₁−R₂, R₂−R₁ disjoint for any sets, disjointness manufactured"), now carrying representation, with the provability predicate Prov playing the role of R₂.
Consistency ledger. One dose of simple consistency, at line 3. Axiomatizability is spent choosing R₂ (makes Prov Σ₁). The Rosser property is spent at line 2. Lemma 1* itself (line 4's interior) spends nothing.
Ch. VII Theorem 1 — Ehrenfeucht–Feferman
Statement. All Σ₁ sets are representable in every simply consistent axiomatizable extension of (R).
Proof. Every such extension is a Rosser system for binary relations — the Ch. VI ≤‑machinery, which needs Ω₄, Ω₅ (proved in (R)) and Σ₀‑completeness (08‑03 Theorem 3, lifted to relations). Apply Theorem S₁. ∎
The concrete representing sentence (p. 90 Discussion)
For an extension of (R) you can write it down. With A(x,z) the Σ₀ generator (∃z A(n,z) ⟺ n∈A) and B(x,w) enumerating provability of the diagonal sentences, the fixed point is
H_n := ∀z( A(n̄,z) ⊃ (∃w≤z) B(n̄,w) )— "every witnesszthatn∈Ais matched by an≤‑earlier witnesswthat I am provable,"
with the dual ∃z( A(n̄,z) ∧ (∀w≤z)~B(n̄,w) ) also representing A. It is Rosser's ≤‑race redirected: instead of racing proofs against refutations to undecide (Ch. VI), it races the provability‑of‑H_n against the membership‑witness of A to represent. The w≤z race is what lets simple consistency do the job ω‑consistency did for Gödel's G. Theorem S₁'s abstract proof is exactly this sentence with the ≤‑race outsourced to the Rosser hypothesis.
Part V — the separation track: one formula, two teams, a race
The second half of the chapter upgrades representation (one set) to exact separation (two disjoint sets A,B at once): a single formula φ with
n∈A ⟹ φ(n̄)provable,n∈B ⟹ φ(n̄)refutable,n∉A∪B ⟹ φ(n̄)undecidable.
The clean scan (p. 91) hands us Shepherdson's actual φ, and it is the clearest object in the chapter — it is Rosser's ρ with A and B drafted onto opposite sides of the race. Everything abstract (Lemma 2, Lemma 2*) is bookkeeping around this one sentence.
V.1 The formula, read in plain words
The p. 91 paragraph says φ(n̄) expresses:
"For any
x: ifxis (a witness that I am provable) or (a witness thatn∈B), then there is somew ≤ xthat is (a witness that I am refutable) or (a witness thatn∈A)."
In symbols, with four Σ₀ witness‑predicates — Pf(n,x)="x codes a proof of φ(n̄)", Rf(n,x)="x codes a refutation of φ(n̄)", and A(n,x), B(n,x) the generators of the sets (∃x A(n,x) ⟺ n∈A, etc.):
φ(n̄) = ∀x[ (Pf(n,x) ∨ B(n,x)) ⊃ (∃w≤x)( Rf(n,w) ∨ A(n,w) ) ]
V.2 It is Rosser's ρ, plus one disjunct on each side
Recall Rosser's ρ (Ch. VI): ρ = ∀x[ Pf(x) ⊃ (∃w≤x) Rf(w) ] — "every proof of me is overtaken by an earlier refutation of me." Shepherdson adds exactly one disjunct to each side:
| side of the race | Rosser ρ |
Shepherdson φ |
effect of the new disjunct |
|---|---|---|---|
antecedent — the attack (fires ⟹ pushes φ toward refutable) |
proof of me | proof of me ∨ n∈B |
a B‑witness fires the attack |
consequent — the defense (holds ⟹ pushes φ toward provable) |
refutation of me | refutation of me ∨ n∈A |
an A‑witness mans the defense |
So the whole mechanism is a race between two teams, with A and B drafted onto opposite teams:
Ajoins the defense. A witness forn∈Amakes the consequent hold for free ⟹φ(n̄)provable.Bjoins the attack. A witness forn∈Bfires the antecedent with nothing to answer it ⟹φ(n̄)refutable.Pf‑of‑me vsRf‑of‑me is Rosser's original self‑referential race, still running underneath, keeping the sentence consistent (no proof ofφslips in without an earlier refutation, and vice versa). That underlying race is what makes simple consistency enough.
One slogan: A on the defending side ⟹ provable; B on the attacking side ⟹ refutable; nobody drafted ⟹ bare ρ ⟹ undecidable.
V.3 The three outcomes, by substituting into φ
Rather than re‑run the race each time, plug the case's facts straight into φ and watch it collapse to something you can read off. Recall φ(n̄) = ∀x[ (Pf(n,x) ∨ B(n,x)) ⊃ (∃w≤x)(Rf(n,w) ∨ A(n,w)) ].
Case n∈A (so n∉B; let a = least A‑witness). Put B(n,x) ↦ false and A(n,a) = true:
φ(n̄) = ∀x[ Pf(n,x) ⊃ (∃w≤x)(Rf(n,w) ∨ A(n,w)) ]
For every x ≥ a the consequent already holds: S ⊢ A(n̄,ā) (Σ₀‑completeness — a is a genuine A‑witness, A a fixed decidable predicate), so w=a satisfies (∃w≤x)(Rf∨A). Those x drop out; below a, A(n,w) is false. What's left:
φ(n̄) ⟺ ∀x < a [ Pf(n,x) ⊃ (∃w≤x) Rf(n,w) ]
"Any proof of me below the deadline a is outrun by an earlier refutation" — a claim about finitely many x. Either some x<a already proves φ (then φ provable outright), or none does — then each Pf(n,x̄) is false, S ⊢ ¬Pf(n,x̄) (Σ₀‑completeness), the antecedents die, and Ω₄ bundles the finite ∀x<a into S ⊢ φ(n̄). Provable, either way. ✓
Case n∈B (so n∉A; let b = least B‑witness). Put A(n,w) ↦ false, so the defence collapses to just Rf:
φ(n̄) = ∀x[ (Pf(n,x) ∨ B(n,x)) ⊃ (∃w≤x) Rf(n,w) ]
"φ(n̄) refutable" means S ⊢ ~φ(n̄), so the whole job is to prove ~φ(n̄). Negating a ∀[…⊃…] gives an ∃[… ∧ ¬…]:
~φ(n̄) = ∃x[ (Pf(n,x) ∨ B(n,x)) ∧ (∀w≤x) ¬Rf(n,w) ] — "some attacker x gets through with no refutation at or below it."
To prove an ∃x, we exhibit one x that works and prove its two conjuncts — x = b is the attacker, and both conjuncts fall to the same Σ₀‑completeness used in the n∈A case (S proves every true decidable fact):
- attacker present at
b:S ⊢ B(n̄,b̄). This is the easy, non‑self‑referential step —B(n,x)is just the fixed decidable predicate defining the setB, nothing to do withφ; andbis a genuine witness ofn∈B, soB(n,b)is a true Σ₀ fact andSproves it. (Exactly the moveS ⊢ A(n̄,ā)played in the previous case.) HenceS ⊢ (Pf∨B)(n̄,b̄). - no earlier refutation: if no number
≤ bcodes a refutation ofφ(n̄), then each¬Rf(n̄,w̄)(w≤b) is a true decidable fact, soS ⊢ ¬Rf(n̄,w̄), andΩ₄bundles the finitely many intoS ⊢ (∀w≤b̄) ¬Rf(n̄,w̄).
Conjoin the two: S ⊢ (Pf∨B)(n̄,b̄) ∧ (∀w≤b̄)¬Rf(n̄,w̄), which is exactly the x=b instance of ~φ(n̄). So S ⊢ ~φ(n̄). Refutable. (And if instead some refutation of φ did have code ≤ b, then φ is refutable outright — either way, refutable.) ✓
The mirror is exact: in n∈A, the A‑witness a was a defender past which no attack survives, so S proves φ; here the B‑witness b is an attacker with the field cleared of defenders (n∉A) and no refutation beating it, so S proves ~φ. Both use S ⊢ (witness) + Ω₄‑bundle‑the‑bounded‑part + Σ₀‑completeness; only the roles (defend vs. attack) swap.
Case n∉A∪B. Put A(n,w) ↦ false and B(n,x) ↦ false:
φ(n̄) = ∀x[ Pf(n,x) ⊃ (∃w≤x) Rf(n,w) ] — this is exactly Rosser's ρ.
No A, no B left. Undecidable under simple consistency (Ch. VI). ✓
The punchline is the third line: with nobody drafted onto either team, φ literally becomes ρ. A and B are the only things you can add to tip the race — A to the defense (⟹ provable), B to the attack (⟹ refutable). So φ exactly separates A from B on simple consistency alone.
V.4 The abstract packaging, proved (Lemma 2)
The abstract lemma drops the concrete witnesses and works with the two teams as Σ₁ relations, so the result holds for any Rosser system (not just extensions of (R)). Set up, at the diagonal φ(n̄):
p:= "φ(n̄)provable"r:= "φ(n̄)refutable"; consistency¬(p∧r);A,Bdisjoint¬(n∈A ∧ n∈B).- DEFENSE
D := (n∈A) ∨ r("inA, or I'm refutable" — the consequent side ofφ). - ATTACK
T := (n∈B) ∨ p("inB, or I'm provable" — the antecedent side ofφ).
These are the scan's R₁ = A∨Ref and R₂ = B∨Prov. A Rosser system strongly separates D−T from T−D — the formula φ of V.1 is that separator — which is two implications:
(I)
(n∈A ∨ r) ∧ ¬(n∈B) ∧ ¬p ⟹ p(II)(n∈B ∨ p) ∧ ¬(n∈A) ∧ ¬r ⟹ r
Goal: p ⟺ n∈A and r ⟺ n∈B (= exact separation). Each of the four directions is the same move — assume the claim, suppose its negation, one clause fires, contradiction:
| want | proof |
|---|---|
n∈A ⟹ p |
Assume n∈A, so ¬(n∈B). Suppose ¬p. Then (n∈A∨r), ¬(n∈B), ¬p hold ⟹ (I) ⟹ p. Contra. So p. |
p ⟹ n∈A |
Assume p, so ¬r (consistency). Suppose ¬(n∈A). Then (n∈B∨p), ¬(n∈A), ¬r hold ⟹ (II) ⟹ r. Contra ¬r. So n∈A. |
n∈B ⟹ r |
Assume n∈B, so ¬(n∈A). Suppose ¬r. Then (n∈B∨p), ¬(n∈A), ¬r hold ⟹ (II) ⟹ r. Contra. So r. |
r ⟹ n∈B |
Assume r, so ¬p (consistency). Suppose ¬(n∈B). Then (n∈A∨r), ¬(n∈B), ¬p hold ⟹ (I) ⟹ p. Contra ¬p. So n∈B. |
So p ⟺ n∈A, r ⟺ n∈B — exact separation. ∎ (Consistency is spent in the two reverse rows; disjointness in the two forward rows. The p, r glued into the teams are exactly what powers the two reverse rows — i.e. what upgrades strong separation to exact — as the table shows.)
Lemma 2* is this with sets
A,Breplaced by relationsR₁,R₂(D=R₁∨Ref,T=R₂∨Prov), yieldingR₁(n,h)⟺provable,R₂(n,h)⟺refutable. Theorem S₂: every consistent axiomatizable Rosser system for binary relations is an exact Rosser system for sets (the Rosser hypothesis supplies the strong separation ofD−TfromT−D). Theorem 2 (Putnam–Smullyan): every simply consistent axiomatizable extension of (R) is an exact Rosser system for sets (corollary via Thm 1's route — such extensions are Rosser systems). Smullyan proves clause (1) and leaves the symmetric (2) "to the reader" (p. 92); the table above does both.
Where representation and separation part ways. Representation needed only provability, so Theorem S₁ could downgrade strong → weak (throw away the refutable half, spend one dose of consistency). Exact separation needs both polarities, so Theorem S₂ keeps the whole strong separation and lets the refutable half do real work. That single difference — discard vs. keep the refutable side — is the entire distinction between the two tracks.
Part VI — §3 variants (Ex 4–10) and §4 the strengthenings
§3 — Theorem 3, its Corollary, and the exercises (pp. 94–95)
Theorem 3 and its Corollary re‑derive incompleteness by running the same engine on variant self‑referential sentences — the "some curious variants of Rosser's undecidable sentence." The two representing sentences from the Discussion are the templates:
∀z( A(x,z) ⊃ (∃w≤z) B(x,w) )and its dual∃z( A(x,z) ∧ (∀w≤z) ~B(x,w) ).
The Corollary reads off: if the relation Π(x,y,z)∈P is enumerable in S and S is a consistent extension of Ω₄, Ω₅, then S is incomplete — Rosser's result recovered through the representation apparatus rather than the bare separation of Ch. VI.
Exercises 4–10 (open threads, to work next):
- Ex 4 — using Ex 5 and Lemma 1*, show weak separability of Π(x,y,z)∉P from Π(x,y,z)∈P ∧ x∈A ⟹ (if consistent) S incomplete.
- Ex 5, Ex 6 — the enumeration steps that feed Ex 4 (extension of Ω₄, Ω₅, and Π(x,y) enumerable).
- Ex 7 — how Ex 6 yields another proof of Theorem 3.
- Ex 8 — if the set {x : Π(x,x,x)∈P} is representable, S is incomplete.
- Ex 9, Ex 10 — the dual‑formula versions (with Π(x,z,x)∈P shapes), giving yet another route to Ex 6.
These are the Chapter‑VII counterparts of Ch. VI's Ex 3–6; each is a short application of the engine, and they are the session's standing exercise debt.
§4 — Theorems S₁*, S₂*: naming the formula (p. 96)
Using the starred lemmas (1*, 2*) in place of the plain lemmas sharpens both theorems from "there exists a representing/separating formula" to "here is one, by its Gödel number":
Theorem S₁*. If
Sis a consistent axiomatizable Rosser system for binary relations andR(x,y)is Σ₁, there is a numberhsuch thatE_h(v₁,v₂)is a formula andE_h(v₁,h̄)representsR(x,h)— i.e.(∀n)[ n∈{x:R(x,h)} ⟺ E_h(n̄,h̄) provable ]. Theorem S₂*. Same hypotheses; for disjoint Σ₁ relationsR₁,R₂, there ishwithE_h(v₁,h̄)exactly separates{x:R₁(x,h)}from{x:R₂(x,h)}.
Exercise 11 asks for the proofs of S₁*, S₂* — direct, since Lemma 1*/2* already deliver the named h. Smullyan notes these sharper forms "have interesting applications in our sequel," and that the sequel compares Shepherdson's proof with the original, the two generalizing in incomparable directions (p. 86). This *‑upgrade is the exact analog of Ch. V's move from "incomplete" to "here is the undecidable sentence."
Distinctions Ledger
| Confusion | One‑line resolution |
|---|---|
| Is weak separation defined by provable/not‑provable? | No. Defined as "represents a superset A'⊇A disjoint from B." The provable/not‑provable pair is derived; "not provable" is inherited from representation's clause (ii). |
Does "superset" mean A is its own superset? |
No. The superset is A' = {n:S⊢F(n̄)}, the set F actually represents — generally a proper superset of A via the don't‑care band. |
| Strong ⟹ weak — mechanism? | Simple consistency on the B‑clause: refutable ⟹ not provable. Nothing else. |
E[m̄,n̄] ≡ E(m̄,n̄) valid and E[m̄,n̄] a sentence — redundant? |
No. Logical validity (any E) + sentence‑hood (only v₁,v₂ free) are different facts; the first makes provability transfer, the second makes "provable" meaningful. |
Why the wrapper [ , ] instead of substitution ( , )? |
⌜E[m̄,n̄]⌝ = Π(⌜E⌝,m,n) is a trivial Σ₀ concatenation, total on all x; substitution is messy to arithmetize. |
Π(x,y,z)∈P ⟹ E_x a formula — why automatic? |
Only sentences are provable; the wrapper is well‑formed only if E_x is a formula. P filters the junk. |
| Where is the self‑reference? | Diagonal ★: h=⌜E_h⌝ sits in Π's slots 1 and 3, so Π(h,n,h)∈P means "E_h(n̄,h̄) is provable." |
The ∉P / ∈P asymmetry in Lemma 1* — why essential? |
With ∈P in U, trap (1ₕ) is vacuous and R⟹provable fails. "Not provable" is what springs the trap. |
How is A representable when ~A isn't Σ₁? |
Never separate against ~A directly. Take Σ₁ R₁=A, R₂=Prov; the Rosser difference manufactures ~A, ~Prov for free. |
| Does Lemma 1* use consistency? | No. It is pure fixed‑point logic on a given weak separation. Simple consistency enters only at Theorem S₁ (strong ⟹ weak). |
| Representation vs exact separation? | Representation = one biconditional (provable ⟺ A). Exact separation = two (provable ⟺ A and refutable ⟺ B) = F reps A, ~F reps B. |
Self‑Test
Q1. The book states weak separation two ways. Which is the definition, and where does the derived "not provable" come from?
answer
Definition = "F represents a superset A'⊇A disjoint from B." The characterization n∈B ⟹ S⊬F(n̄) is derived: n∈B ⟹ n∉A' (disjoint) ⟹ (representation clause ii) F(n̄) not provable. Refutability is absent from representation, so it cannot appear.
Q2. In Prov(x,y)=Π(y,x,y)∈P, why must y occupy positions 1 and 3?
answer
By (MEq), Π(a,b,c)∈P ⟺ E_a(b̄,c̄) provable. To make a sentence talk about its own provability we set the index a and the second argument c to the same code h. So y (the slot frozen to h) must be both — positions 1 and 3. Position 2 holds the genuine input x. At y=h: Π(h,n,h)∈P ⟺ E_h(n̄,h̄) provable.
Q3. Write the two relations U, V of Lemma 1* and say which conjunct is load‑bearing.
answer
U = R(x,y) ∧ Π(y,x,y)∉P; V = Π(y,x,y)∈P ∧ ~R(x,y). The ∉P in U is load‑bearing: it makes trap (1ₕ) R(n,h) ∧ [G not provable] ⟹ G provable non‑vacuous. With ∈P there, the forward direction R⟹provable fails.
Q4. Lemma 1* proves a full biconditional yet uses no consistency. How is that possible?
answer
The two contradictions are metalinguistic — "this one fixed sentence G is both provable and not provable" — which is impossible regardless of whether S is consistent. Consistency (object‑level) would only be needed to compare provable against refutable; Lemma 1* only ever compares provable against not‑provable.
Q5. In Theorem S₁, ~A is not Σ₁. How does the proof separate against it anyway?
answer
It doesn't separate against ~A directly. It hands the Rosser system two Σ₁ relations R₁=A, R₂=Prov; the differences R₁−R₂=U and R₂−R₁=V manufacture ~A and ~Prov for free. Only Σ₁ inputs are ever required.
Q6. State exact separation as a pair of representation facts, and deduce the "undecidable off A∪B" clause.
answer
F exactly separates A from B iff F represents A (provable ⟺ n∈A) and ~F represents B (refutable ⟺ n∈B). Off A∪B: n∉A ⟹ not provable, n∉B ⟹ not refutable ⟹ undecidable.
Q7. Why is Theorem 1 (Ehrenfeucht–Feferman) a corollary of Theorem S₁ rather than a separate proof?
answer
Because every simply consistent axiomatizable extension of (R) is a Rosser system for binary relations (Ch. VI's Ω₄,Ω₅ ≤‑machinery). Theorem S₁'s hypothesis is met, so its conclusion — all Σ₁ sets representable — transfers directly.
References & cross‑links
| Imported result | Used in | Source |
|---|---|---|
Rosser system; ≤‑race; "extension of (R) ⟹ Rosser system"; Ω₄, Ω₅ |
Parts I, IV (Thm 1), V | 08‑03 Lemma S / Thm 3 |
represents vs separates; P*, R*; enumeration clauses |
Parts II, III | 07‑30, 08‑03 |
P is Σ₁ from axiomatizability; Σ₁ closure |
Part IV (Thm S₁) | 07‑29 prelude, 07‑28 Prop C |
| Σ₀‑completeness ("all true Σ₀ provable"), (R)=Ω₁–Ω₅ | Part IV (Thm 1) | 07‑31 Theorem B* |
| simple consistency = "refutable ⟹ not provable" | Parts III, IV | 07‑29 |
Book span this session: Smullyan, Gödel's Incompleteness Theorems, Ch. VII, pp. 86–96 — §1 (Thm S₁, Thm 1; weak separation; the function Π; Lemma 1, Lemma 1*, Discussion, Ex 1), §2 (Lemma 2, Lemma 2*, Thm S₂, Thm 2, Ex 2–3), §3 (Thm 3 + Cor, Ex 4–10), §4 (Thm S₁*, S₂*, Ex 11).
What's ahead
- Chapter VII drills still open: Exercises 4–10 (§3 variants, each a short engine application); Exercise 11 (proving the starred
S₁*, S₂*). (Both tracks are now fully proved — representation in Part IV, separation in Part V.3–V.4, the latter with the four‑row abstract proof that closes Smullyan's "left to the reader" clause (2).) These exercises are the direct continuation. - Still owed from Ch. V: §6 Ex 10–12 (the
P(X̄)provability predicate; Ex 11's full Σ₁ case deferred to Boolos) — the Σ₁‑completeness debt; and Chapter 9's Second Theorem (why "Gis true" is not P.A.‑formalizable). - The sequel's comparison (flagged on p. 86): Shepherdson's proof vs. the original Ehrenfeucht–Feferman route — "very different, generalizing in apparently incomparable directions." Worth revisiting once the separation track is fully drilled.
Prior session files: 07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 · 08‑03 · 08‑04 (this file).
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
第七章:谢泼德森的表示定理(第86–96页)——仅凭简单一致性得到每个 Σ₁ 集的可表示性
导读——问题,以及谢泼德森的一招
先读这一段;以下一切都是它的展开。
问题。表示一个 Σ₁ 集 A,就是构造公式 F,使 F(n̄) 可证 ⟺ n∈A——这是一个双条件,因此有两项义务:
- (→) 覆盖
A——成员都得到证明。这是免费的:成员关系是一个真的、由 Σ₀ 见证的事实,而系统会证明真事实。 - (←) 避开
~A——非成员保持不可证。这就是全部困难,而它是一个关于补集~A的断言。
(←) 困难的原因有一体两面。一个仅仅简单一致的系统可以证明假语句(一致性禁止同时证明一个语句及其否定,并不禁止证明在 ℕ 中为假的东西)——因此,自然的“在 A 上为真”公式可能把可证性泄漏到非成员上(正是练习9的 ω‑不一致病症:∃y R(n̄,y) 可证,却没有真实见证)。你也不能亲自管控非成员来绕过这个问题,因为 ~A 未必是 Σ₁(波斯特:只有当 A 递归时才是)——没有 ~A 的枚举可用。你既不能相信系统会对 ~A 保持沉默,也不能通过枚举它强迫系统沉默。历史上,这一 (←) 方向是用 ω‑一致性换来的(即承诺“不会有假的带见证 ∃ 可证”)。
谢泼德森的一招——永不正面对付 ~A;让它输掉竞赛。 把 F 构造成一个自指的 ≤ 竞赛(罗瑟的装置,通过对角化工具 Π):一个语句,让集合的成员见证与该语句自身的证明/反驳见证竞赛,询问谁先出现。于是:
- 无须枚举非成员关系,也无须相信它——它仅仅作为两个确实是 Σ₁ 的对象(集合
A和可证性关系)之间竞赛的败者出现; - 裁定竞赛所需的唯一事实是简单一致性——一个反驳不可能先于自身——不需要可靠性,也不需要 ω‑一致性。
这一步——把关于 ~A 的不可能义务,改写成两个 Σ₁ 对象之间可以获胜的竞赛,并以简单一致性裁定——就是整章。两条路线只是同一旋钮的两种设定:把弱分离送进对角化,就表示一个集合(路线A);把强分离送进去,就精确分离一对集合(路线B,包含A)。
新的一章,颠倒了上一章的极性。第六章用罗瑟的 ≤ 竞赛把 R* 与 P* 分离——一次性的操作,旨在让单个语句不可判定(不完备性,一个否定结果)。第七章表明,同样的罗瑟机制,一旦封装成“罗瑟系统”这一性质,就给出了所能得到的最强肯定结果:每个 Σ₁ 集都可表示——而依旧只凭简单一致性。
历史上,这是令人意外之处。在哥德尔证明的时代,已知在 P.A. 中表示 P* 的唯一途径要经过 ω‑一致性。埃伦福伊希特–费弗曼 [1960] 首先证明,所有 Σ₁ 集在 (R) 的每个简单一致、可公理化扩张中都可表示(把罗瑟型论证与迈希尔的递归论结果结合)。谢泼德森 [1961] 随后找到了本章采用的直接、自足路线。
本次研读做了两件事:(i) 通过四个基础问题理清了预备装置——弱分离、封装式 E[m̄,n̄] 及其哥德尔数函数 Π;然后 (ii) 重构完整的表示链 引理1* → 引理1 → 定理S₁ → 定理1,并对照清晰扫描件核验。随后,通过谢泼德森实际使用的公式 φ(第五部分),使平行的分离链变得具体——把 A 和 B 放在竞赛两边的罗瑟 ρ——通过这场竞赛核验三个结果(在 A 上可证、在 B 上可反驳、在两者之间不可判定);并准确陈述 §4的加强结果。
阅读顺序依照逻辑主线,而非书的页码顺序。
第0部分——一句话的转变,以及承接的内容
第六章使用的货币是分离;第七章用它换取表示。
| 第六章(罗瑟) | 第七章(谢泼德森) | |
|---|---|---|
| 目标 | 使一个语句不可判定 ⟹ 不完备(否定结果) | 表示每个 Σ₁ 集(肯定结果) |
| 工具 | H 将 R* 与 P* 分离(一对) |
S 是罗瑟系统:分离每一对不相交 Σ₁ 集 |
| 使用的一致性 | 简单一致性 | 简单一致性 |
| 核心结果 | 定理R——P.A. 不完备 | 定理S₁——所有 Σ₁ 集都可表示 |
两者之间的桥梁是这里引入的一个工具:通过哥德尔数函数 Π 承载的、经由可证性的对角自指。给它一个分离公式,它就返回一个表示公式。本章的一切,就是这个工具加上记录整理。
从第六章原样引入的内容:罗瑟系统的定义、≤ 竞赛公式,以及 (R) 的每个简单一致、可公理化扩张都是罗瑟系统这一事实(Ω₄, Ω₅ 机制,08‑03 引理S/定理3)。第七章不再证明这一点;它使用这个结果(定理1、定理2)。
第一部分——两条路线:终点、内容、组装
本章目标。 证明简单一致、可公理化的罗瑟系统表示每个 Σ₁ 集——仅凭简单一致性,重新得到哥德尔需要 ω‑一致性才得到的东西。
两条路线共享的一个思想。 不能正面表示 Σ₁ 集 A:表示 A 意味着还要控制 n∉A 时的 F(n̄),而 ~A 未必是 Σ₁(波斯特:仅当 A 递归时,~A 才是 Σ₁)。所以改为——
从
A和一个可证性谓词构造两个 Σ₁ 关系,让罗瑟系统分离它们,再让一个自指对角化把分离转化为表示。
罗瑟假设提供分离;对角化 ★(经由封装式 Π)使语句谈论自身的可证性;简单一致性完成一个小转换。两条路线都在共享工具 封装式 E[m̄,n̄] → Π → 总等价式 → 对角化 ★ 上运行这个方法。两条路线仅有一个旋钮不同:送入对角化的是弱分离(一种极性),还是强分离(两种极性)。
路线A——表示(弱分离 → 一种极性)
- 终点。 每个 Σ₁ 集
A都可表示:存在公式F,使n∈A ⟺ F(n̄)可证。——定理S₁;对于 (R) 的扩张,就是定理1(埃伦福伊希特–费弗曼)。 - 它告诉我们什么。可证性追踪成员关系——一个集合,只有可证/不可证这一极性。这已满足不完备性和理论的不可判定性所需的一切。
- 如何组装(三级):
1.
引理1*(引擎)——从两个关系的弱分离出发,对角化给出一个双条件F(n̄) 可证 ⟺ R(n,h)。不耗费任何条件——纯粹不动点逻辑。 2.引理1——令R := "x∈A";引擎给出F = E_h(v₁,h̄)表示A。 3.定理S₁——罗瑟假设强分离U,V这一对;简单一致性(在此使用,仅一次)将强→弱降级;送入引理1。
路线B——分离(强分离 → 两种极性)
- 终点。 每一对不相交的 Σ₁ 集
A,B都可精确分离:存在公式F,使n∈A ⟺可证,n∈B ⟺可反驳,否则不可判定。——定理S₂;对于 (R) 的扩张,就是定理2(普特南–斯穆里安)。 - 它告诉我们什么。可证性追踪
A,可反驳性追踪B——两个集合,两种极性。严格强于路线A:令B=∅,精确分离就退化为普通表示,因此路线B包含路线A(S₂ ⟹ S₁)。额外获得的——对可反驳性的控制——是不可分离性和本质不可判定性结果所需的。 - 如何组装(三级,强分离的对应版本):
1.
引理2*(引擎)——从强分离出发,对角化运行两次(一次针对可证性,一次针对可反驳性),给出两个双条件可证 ⟺ R₁、可反驳 ⟺ R₂。耗费简单一致性——防止两个输出冲突。 2.引理2——设置两支“队伍”R₁ = A∨Ref、R₂ = B∨Prov;引擎给出的F精确分离A与B。 3.定理S₂——罗瑟假设直接提供强分离(无须降级);两个双条件就是精确分离。
唯一关键区别
| 路线A——表示 | 路线B——分离 | |
|---|---|---|
| 送入对角化的分离 | 弱 | 强 |
| 保留的极性 | 仅可证 | 可证及可反驳 |
| 终点 | 表示一个集合 | 精确分离一对集合 |
| 逻辑强度 | 核心结果 | 严格更强——经 B=∅ 蕴涵A |
| 下游用途 | 不完备性、不可判定性 | 不可分离性、本质不可判定性 |
它们不是并列的同级结果。路线A是清晰的核心结果(证明最简单、用途最广);路线B是其严格加强版。同一个工具,同样的三级形状;唯一的结构差异是输入引擎的弱分离与强分离——等价地,舍弃还是保留可反驳的那一半。
第二部分——可引用的术语表
承接:E_x = 哥德尔数为 x 的表达式;P = 可证语句的哥德尔数集;P*、R* 沿用第五/六章。
- (由
F(v₁))表示A:(∀n)[ S⊢F(n̄) ⟺ n∈A ]。双向;纯粹以可证/不可证陈述——可反驳性从不出现。 - 将
A与B强分离(= 第六章的“分离”):n∈A ⟹ S⊢F(n̄);n∈B ⟹ S⊢~F(n̄)(可反驳)。 - 将
A与B弱分离——定义(书中的):F表示某个超集A'⊇A,且A'∩B=∅。等价刻画:n∈A ⟹ S⊢F(n̄);n∈B ⟹ S⊬F(n̄)(不可证)。关于B的条款把“可反驳”放宽成“不可证”。 - (由
F)将A与B精确分离:n∈A ⟹可证;n∈B ⟹可反驳;n∉A∪B ⟹不可判定。等价地,F表示A且~F表示B——一种双重表示。 - 关于
n元关系的罗瑟系统:对于任意 Σ₁ 关系R₁,R₂,差集R₁−R₂都可与R₂−R₁强分离。关于集合 =n=1的情形。关于集合的精确罗瑟系统:每一对不相交 Σ₁ 集都可精确分离。 - 封装式
E[m̄,n̄] := ∀v₁(v₁=m̄ ⊃ ∀v₂(v₂=n̄ ⊃ E))。包围整个E的固定句法框架;从不检查E的内部。 Π(a,b,c)=E_a[b̄,c̄]的哥德尔数。关于a,b,c的全连接函数;其图是 Σ₀ 的。- (MEq) 总等价式:
(∀a,b,c)[ Π(a,b,c)∈P ⟺ E_a(b̄,c̄) 可证 ]。(若E_a不是公式,两边都假。)因为P是 Σ₁,所以它关于(a,b,c)是 Σ₁。 Prov(x,y) := Π(y,x,y)∈P——二元关系“E_y(x̄,ȳ)可证”。槽位y位于第1和第3位置(指标及第二自变量);第2槽位放真正的输入x。Σ₁。- 对角化 ★。 固定一个自由变量为
v₁,v₂的公式E,h=⌜E⌝(所以E=E_h);记G_n := E_h(n̄,h̄)。则Prov(n,h) ⟺ G_n 可证——数字h身兼两职,就是全部自指。
第三部分——预备装置(四个基础问题)
在任何定理之前,必须消除四种混淆。正因如此,后面的证明才清晰。
III.1 弱分离——定义与刻画(顺序很重要)
定义是超集版本(定义):F 弱分离 A 与 B,当且仅当 F 表示某个与 B 不相交的 A'⊇A。可证/不可证这一对条件是导出的刻画,不是定义。对 A' = {n : S⊢F(n̄)} 使用表示的两个条款,推导如下:
| # | 断言 | 原因 |
|---|---|---|
| 1 | n∈A ⟹ S⊢F(n̄) |
A⊆A',且 F 表示 A'(条款i:成员 ⟹ 可证) |
| 2 | n∈B ⟹ S⊬F(n̄) |
A'∩B=∅ ⟹ n∉A',且 F 表示 A'(条款ii:非成员 ⟹ 不可证) |
所以“不可证”是从表示的否定条款 (ii) 原样继承而来——可反驳性在表示中结构性地缺席,因此不可能出现。超集的确合理出现,但它是 A'(F 实际表示的集合),不是“A 是自身的超集”。
强 ⟹ 弱(第六章引理1):由强分离令 A'={n:S⊢F(n̄)};则 A⊆A'(强分离的可证一半),而对 n∈B,S⊢~F(n̄) + 简单一致性 ⟹ S⊬F(n̄) ⟹ n∉A'。这唯一一步“可反驳 ⟹ 不可证”就是降级发生之处——唯一花费一致性的地方,与第六章完全一样。
为什么 A' 通常是真超集。 把 ℕ 分成三带:A(强制可证)、B(强制不可证),以及无关紧要的区域 ∉A∪B(不受约束)。如果在某个无关紧要的 n 上,F(n̄) 碰巧可证,这个 n 就加入 A'。所以 A' = A 加上可能存在的、避开 B 的无害溢出。超集没有特殊能力;它只是 F 所表示之物的诚实名称。而当 B 是 A 的补集时,三带收拢——A⊆A'⊆(B的补集)=A——于是 A'=A,弱分离退化为精确表示。表示就是针对完整补集进行弱分离的极限情形。
III.2 封装式 E[m̄,n̄] 和函数 Π
书中接连给出的两个陈述并不重复:
- (1) 若
E是仅有v₁,v₂为自由变量的公式,则E[m̄,n̄]是一个语句,并与E(m̄,n̄)等价; - (2) 若
E是任意公式,则E[m̄,n̄] ≡ E(m̄,n̄)逻辑有效(⟹ 在S中可证 ⟹ 可证性传递)。
它们在两个维度上都有区别。底层的单一逻辑事实是双重等式保护条件的消去 ∀v(v=t ⊃ Φ) ≡ Φ(t)(有效的原因:以 t=t 实例化 v:=t;以及等者代换),应用两次。由此:(2) 就是这个事实;(1) 的“等价”是它的语义投影——但 (1) 的“是一个语句”是一个独立的、纯句法事实(两个 ∀ 绑定 v₁,v₂;若它们是仅有的自由变量,就没有悬空变量)。所以这是一个逻辑事实 + 一个独立的句法事实,而非同一原因的两个后果。两者都需要:语句资格 (1) 使“可证”有意义(只有语句属于 P);逻辑有效性 (2) 使可证性传递(仅有语义等价不能给出 S⊢E[m̄,n̄] ⟺ S⊢E(m̄,n̄)——需要双条件本身可证)。
究竟为什么要封装式? E[m̄,n̄] 是在 E 前后添加的固定框架——所以 ⌜E[m̄,n̄]⌝ = Π(⌜E⌝,m,n) 是一个简单的连接函数,在所有 x 上都是全函数。真正的代入 E(m̄,n̄) 必须寻找自由出现并替换——其算术化复杂得多。封装式用一个清晰的 Σ₀ 编码函数换取相同的可证等价。由此得到总等价式 (MEq)。
废料会自行过滤(为什么全性无害):若 Π(x,y,z)∈P,则 E_x[ȳ,z̄] 是可证语句 ⟹ 合式 ⟹ ⊃ 右侧是公式 ⟹ E_x 自动是公式。从来不需要附加假设“x 编码一个公式”——属于 P 就强制了这一点。
第四部分——完整的表示路线(已对照清晰扫描件核验)
这是主线,以下每一行都对照第88–89页核验过。
第七章引理1*——引擎(不耗费条件)
→ 作用:把一个给定的弱分离转化为精确双条件。不需要一致性;不需要罗瑟条件。纯粹的对角逻辑。
两个关系(关于 x,y 的二元关系),其中 Prov = Π(y,x,y)∈P:
U(x,y) := R(x,y) ∧ Π(y,x,y)∉P(“R成立,且对角语句不可证”)V(x,y) := Π(y,x,y)∈P ∧ ~R(x,y)(“对角语句可证,且R不成立”)
∉P / ∈P 的不对称就是整个引擎——这是在拿到清晰扫描件前看不清的关键,只有它才能让论证闭合(见证明后的说明)。
陈述。 对任意关系 R(x,y):若公式 E_h(v₁,v₂)(其中 h=⌜E_h⌝)弱分离 U 与 V,则 (∀n)[ E_h(n̄,h̄) 可证 ⟺ R(n,h) ]。
证明。 对一般元组 (n,m) 应用弱分离(实例 E_h(n̄,m̄)):
| 条款 | 内容 |
|---|---|
| (1) | R(n,m) ∧ Π(m,n,m)∉P ⟹ S⊢E_h(n̄,m̄) |
| (2) | Π(m,n,m)∈P ∧ ~R(n,m) ⟹ S⊬E_h(n̄,m̄) |
固定 m=h;记 G = E_h(n̄,h̄)。由 ★,Π(h,n,h)∈P ⟺ G 可证。这些条款变成自我反驳的陷阱:
| 内容 | |
|---|---|
| (1ₕ) | R(n,h) ∧ [G 不可证] ⟹ G 可证 |
| (2ₕ) | [G 可证] ∧ ~R(n,h) ⟹ G 不可证 |
| 方向 | 论证 |
|---|---|
R(n,h) ⟹ G 可证 |
假设 R(n,h)。若 G 不可证,则 (1ₕ) 的前件成立 ⟹ G 可证——直接的元语言矛盾。所以 G 可证。 |
G 可证 ⟹ R(n,h) |
假设 G 可证。若 ~R(n,h),则 (2ₕ) 的前件成立 ⟹ G 不可证——矛盾。所以 R(n,h)。 |
故 G 可证 ⟺ R(n,h)。∎
两点值得标记。
1. 无一致性,无罗瑟。 矛盾是元理论中的“这个固定语句 G 既可证又不可证”——不是断言 S 一致。引理纯粹整理给定的分离。
2. U 中的 ∉P 合取项承受关键负荷。 如果 U 用的是 Π∈P,(1ₕ) 就会读作 R(n,h) ∧ [G 可证] ⟹ G 可证——空洞,正向证明随之崩溃。“不可证”合取项恰恰触发了陷阱。(这正是此前两轮标记为“不会假装”的地方;清晰扫描件解决了它。)
第七章引理1——表示引理
陈述。 对集合 A:若 [x∈A ∧ Π(y,x,y)∉P] 可与 [Π(y,x,y)∈P ∧ x∉A] 弱分离,则 A 可表示;具体而言,分离公式 E_h(v₁,v₂) 给出 E_h(v₁, h̄) 表示 A。
证明。 在引理1*中令 R(x,y):⟺ x∈A。则 R(n,h) ⟺ n∈A,所以 E_h(n̄,h̄) 可证 ⟺ n∈A,即 E_h(v₁,h̄) 表示 A。∎ (扫描件把第一个关系中的连接写成 ∈P;为与引理1* 和定理S₁的证明一致,必须读成 ∉P——我们依据论证更正了这个印误。)
第七章定理S₁——谢泼德森的表示定理
陈述。 若 S 是一个简单一致、可公理化、关于二元关系的罗瑟系统,则每个 Σ₁ 集 A 都在 S 中可表示。
证明。 选取两个 Σ₁ 关系:
| 定义 | 是 Σ₁ 的原因 | |
|---|---|---|
R₁(x,y) |
x∈A |
A 是 Σ₁ |
R₂(x,y) |
Π(y,x,y)∈P(= Prov) |
S 可公理化 ⟹ P 是 Σ₁;Π 的图是 Σ₀ |
取它们的差集——否定免费出现:
| # | 断言 | 依据 |
|---|---|---|
| 1 | R₁−R₂ = (x∈A) ∧ Π(y,x,y)∉P = U,且 R₂−R₁ = Π(y,x,y)∈P ∧ ~(x∈A) = V |
集合代数 |
| 2 | U 可与 V 强分离 |
对 Σ₁ 关系对 R₁,R₂ 使用(二元)罗瑟系统 |
| 3 | U 可与 V 弱分离 |
2 + 简单一致性(强 ⟹ 弱,III.1) |
| 4 | E_h(v₁,h̄) 表示 A |
3 + 引理1 ∎ |
深层要点——任何补集都无须是 Σ₁。 “~A 不是 Σ₁,怎么能对它做分离?”这一疑问在此化解:我们交给罗瑟系统的是两个确实为 Σ₁ 的关系 R₁=A、R₂=Prov,而差集操作以零复杂度成本制造出 ~A 和 ~Prov。这正是第六章的差集技巧(08‑03 引理S:“对任意集合,R₁−R₂、R₂−R₁ 都不相交,不相交性是制造出来的”),现在承载着表示,其中可证性谓词 Prov 扮演 R₂。
一致性账目。 一剂简单一致性,在第3行。可公理化性用在选取 R₂ 上(使 Prov 是 Σ₁)。罗瑟性质用在第2行。引理1* 本身(第4行内部)不耗费条件。
第七章定理1——埃伦福伊希特–费弗曼
陈述。 所有 Σ₁ 集都在 (R) 的每个简单一致、可公理化扩张中可表示。
证明。 每个这样的扩张都是关于二元关系的罗瑟系统——第六章的 ≤ 机制,需要 Ω₄, Ω₅(在 (R) 中可证)和 Σ₀‑完备性(08‑03 定理3,提升到关系)。应用定理S₁。∎
具体的表示语句(第90页讨论)
对 (R) 的扩张,可以把它写下来。以 A(x,z) 为 Σ₀ 生成式(∃z A(n,z) ⟺ n∈A),以 B(x,w) 枚举对角语句的可证性,不动点是
H_n := ∀z( A(n̄,z) ⊃ (∃w≤z) B(n̄,w) )——“每个证明n∈A的见证z,都配有一个在≤意义上更早的见证w,证明我可证”,
其对偶 ∃z( A(n̄,z) ∧ (∀w≤z)~B(n̄,w) ) 也表示 A。这是改向后的罗瑟 ≤ 竞赛:不再让证明与反驳竞赛来得到不可判定(第六章),而让 H_n 的可证性与 A 的成员见证竞赛来得到表示。w≤z 竞赛让简单一致性完成了 ω‑一致性对哥德尔 G 所做的工作。定理S₁的抽象证明正是这个语句,只不过把 ≤ 竞赛外包给了罗瑟假设。
第五部分——分离路线:一个公式、两支队伍、一场竞赛
本章后半把表示(一个集合)加强为精确分离(同时处理两个不相交集合 A,B):一个公式 φ 满足
n∈A ⟹ φ(n̄)可证,n∈B ⟹ φ(n̄)可反驳,n∉A∪B ⟹ φ(n̄)不可判定。
清晰扫描件(第91页)给出了谢泼德森实际使用的 φ,这是本章最清晰的对象——它就是把 A 和 B 编入竞赛两边的罗瑟 ρ。 一切抽象内容(引理2、引理2*)都是围绕这一个语句的记录整理。
V.1 用普通语言读这个公式
第91页的段落说,φ(n̄) 表达:
“对任意
x:若x是(我可证的见证)或(n∈B的见证),则存在某个w ≤ x,它是(我可反驳的见证)或(n∈A的见证)。”
以符号表示,使用四个 Σ₀ 见证谓词——Pf(n,x)=“x 编码 φ(n̄) 的一个证明”,Rf(n,x)=“x 编码 φ(n̄) 的一个反驳”,以及集合的生成式 A(n,x)、B(n,x)(∃x A(n,x) ⟺ n∈A,等等):
φ(n̄) = ∀x[ (Pf(n,x) ∨ B(n,x)) ⊃ (∃w≤x)( Rf(n,w) ∨ A(n,w) ) ]
V.2 它就是罗瑟的 ρ,两边各加一个析取项
回忆罗瑟的 ρ(第六章):ρ = ∀x[ Pf(x) ⊃ (∃w≤x) Rf(w) ]——“我的每个证明都被一个更早的反驳赶超。” 谢泼德森恰好在两边各加一个析取项:
| 竞赛的一边 | 罗瑟 ρ |
谢泼德森 φ |
新析取项的作用 |
|---|---|---|---|
前件——攻击(触发 ⟹ 推动 φ 变得可反驳) |
我的证明 | 我的证明 ∨ n∈B |
一个 B 见证发动攻击 |
后件——防御(成立 ⟹ 推动 φ 变得可证) |
我的反驳 | 我的反驳 ∨ n∈A |
一个 A 见证承担防御 |
所以整个机制是两支队伍的竞赛,A 和 B 分别编入对立两队:
A加入防御。n∈A的见证免费使后件成立 ⟹φ(n̄)可证。B加入攻击。n∈B的见证触发前件,却无物应对 ⟹φ(n̄)可反驳。- 关于我的
Pf与关于我的Rf是罗瑟原本的自指竞赛,仍在底层运行,使语句保持一致(没有φ的证明能在没有更早反驳的情况下溜进来,反之亦然)。正是这个底层竞赛使简单一致性足够。
一句口号:A 在防御方 ⟹ 可证;B 在攻击方 ⟹ 可反驳;两边都无人加入 ⟹ 裸的 ρ ⟹ 不可判定。
V.3 把三种情况代入 φ,得到三个结果
不必每次重新运行竞赛,直接把该情况的事实代入 φ,看它如何化简为一眼可读的形式。回忆 φ(n̄) = ∀x[ (Pf(n,x) ∨ B(n,x)) ⊃ (∃w≤x)(Rf(n,w) ∨ A(n,w)) ]。
情形 n∈A(所以 n∉B;令 a = 最小的 A 见证)。置 B(n,x) ↦ 假,且 A(n,a) = 真:
φ(n̄) = ∀x[ Pf(n,x) ⊃ (∃w≤x)(Rf(n,w) ∨ A(n,w)) ]
对每个 x ≥ a,后件已经成立:S ⊢ A(n̄,ā)(Σ₀‑完备性——a 是真正的 A 见证,A 是固定的可判定谓词),所以 w=a 满足 (∃w≤x)(Rf∨A)。这些 x 被消去;在 a 以下,A(n,w) 为假。剩下:
φ(n̄) ⟺ ∀x < a [ Pf(n,x) ⊃ (∃w≤x) Rf(n,w) ]
“我在截止点 a 以下的任何证明,都被更早的反驳赶超”——这是关于有限多个 x 的断言。要么某个 x<a 已经证明 φ(于是 φ 直接可证),要么没有——则每个 Pf(n,x̄) 为假,S ⊢ ¬Pf(n,x̄)(Σ₀‑完备性),前件消失,Ω₄ 把有限的 ∀x<a 汇总成 S ⊢ φ(n̄)。两种情况下都可证。 ✓
情形 n∈B(所以 n∉A;令 b = 最小的 B 见证)。置 A(n,w) ↦ 假,防御便化简为仅有 Rf:
φ(n̄) = ∀x[ (Pf(n,x) ∨ B(n,x)) ⊃ (∃w≤x) Rf(n,w) ]
“φ(n̄) 可反驳”意味着 S ⊢ ~φ(n̄),所以全部工作就是证明 ~φ(n̄)。对 ∀[…⊃…] 取否定,得到 ∃[… ∧ ¬…]:
~φ(n̄) = ∃x[ (Pf(n,x) ∨ B(n,x)) ∧ (∀w≤x) ¬Rf(n,w) ] —— “某个攻击者 x 突破了,而在它之前或同一位置没有反驳。”
要证明 ∃x,我们给出一个可用的 x 并证明其两个合取项——x = b 就是攻击者,而两个合取项都由 n∈A 情形使用的同一个 Σ₀‑完备性解决(S 证明每个真的可判定事实):
- 在
b处有攻击者:S ⊢ B(n̄,b̄)。这是简单、非自指的一步——B(n,x)只是定义集合B的固定可判定谓词,与φ无关;b是n∈B的真正见证,所以B(n,b)是真的 Σ₀ 事实,S证明它。(恰如上一情形中的S ⊢ A(n̄,ā)。) 因此S ⊢ (Pf∨B)(n̄,b̄)。 - 没有更早的反驳:若没有任何
≤ b的数编码φ(n̄)的反驳,则每个¬Rf(n̄,w̄)(w≤b)都是真的可判定事实,所以S ⊢ ¬Rf(n̄,w̄),Ω₄将有限多个实例汇总成S ⊢ (∀w≤b̄) ¬Rf(n̄,w̄)。
合取两者:S ⊢ (Pf∨B)(n̄,b̄) ∧ (∀w≤b̄)¬Rf(n̄,w̄),这恰是 ~φ(n̄) 的 x=b 实例。所以 S ⊢ ~φ(n̄)。可反驳。 (而如果 φ 的某个反驳确实有 ≤ b 的编码,那么 φ 直接可反驳——无论哪种情况,都可反驳。) ✓
镜像完全对应:在 n∈A 时,A 见证 a 是一个防御者,越过它就没有攻击能幸存,所以 S 证明 φ;这里 B 见证 b 是一个攻击者,战场上已清除防御者(n∉A),又没有反驳抢先,所以 S 证明 ~φ。两者都用 S ⊢ (见证) + Ω₄ 汇总有界部分 + Σ₀‑完备性;只是角色(防御/攻击)互换。
情形 n∉A∪B。 置 A(n,w) ↦ 假 且 B(n,x) ↦ 假:
φ(n̄) = ∀x[ Pf(n,x) ⊃ (∃w≤x) Rf(n,w) ] —— 这恰好就是罗瑟的 ρ。
不剩 A,也不剩 B。在简单一致性下不可判定(第六章)。✓
关键在第三行:两边都无人入队,φ 就字面上变成 ρ。A 和 B 是仅有的、可添加以改变竞赛倾向的东西——A 加入防御(⟹ 可证),B 加入攻击(⟹ 可反驳)。因此 φ 仅凭简单一致性就精确分离 A 与 B。
V.4 抽象封装及其证明(引理2)
抽象引理舍去具体见证,把两支队伍作为 Σ₁ 关系处理,所以结果适用于任何罗瑟系统(不限于 (R) 的扩张)。在对角语句 φ(n̄) 处设置:
p:= “φ(n̄)可证”,r:= “φ(n̄)可反驳”;一致性¬(p∧r);A,B不相交¬(n∈A ∧ n∈B)。- 防御
D := (n∈A) ∨ r(“属于A,或我可反驳”——φ的后件一边)。 - 攻击
T := (n∈B) ∨ p(“属于B,或我可证”——φ的前件一边)。
这就是扫描件中的 R₁ = A∨Ref 和 R₂ = B∨Prov。一个罗瑟系统强分离 D−T 与 T−D——V.1的公式 φ 就是那个分离公式——即两个蕴涵:
(I)
(n∈A ∨ r) ∧ ¬(n∈B) ∧ ¬p ⟹ p(II)(n∈B ∨ p) ∧ ¬(n∈A) ∧ ¬r ⟹ r
目标: p ⟺ n∈A 且 r ⟺ n∈B(= 精确分离)。四个方向中的每一个都用同一步——假设前件,假定结论的否定,触发一条款,得到矛盾:
| 所需 | 证明 |
|---|---|
n∈A ⟹ p |
假设 n∈A,于是 ¬(n∈B)。假定 ¬p。则 (n∈A∨r)、¬(n∈B)、¬p 成立 ⟹ (I) ⟹ p。矛盾。所以 p。 |
p ⟹ n∈A |
假设 p,于是 ¬r(一致性)。假定 ¬(n∈A)。则 (n∈B∨p)、¬(n∈A)、¬r 成立 ⟹ (II) ⟹ r。与 ¬r 矛盾。所以 n∈A。 |
n∈B ⟹ r |
假设 n∈B,于是 ¬(n∈A)。假定 ¬r。则 (n∈B∨p)、¬(n∈A)、¬r 成立 ⟹ (II) ⟹ r。矛盾。所以 r。 |
r ⟹ n∈B |
假设 r,于是 ¬p(一致性)。假定 ¬(n∈B)。则 (n∈A∨r)、¬(n∈B)、¬p 成立 ⟹ (I) ⟹ p。与 ¬p 矛盾。所以 n∈B。 |
因此 p ⟺ n∈A、r ⟺ n∈B——精确分离。∎(一致性用于两条反向行;不相交性用于两条正向行。黏入队伍的 p, r 恰好驱动两条反向行——即把强分离升级为精确分离的东西——如表所示。)
引理2* 就是把这里的集合
A,B换成关系R₁,R₂(D=R₁∨Ref、T=R₂∨Prov),得到R₁(n,h)⟺可证、R₂(n,h)⟺可反驳。定理S₂:每个一致、可公理化、关于二元关系的罗瑟系统都是关于集合的精确罗瑟系统(罗瑟假设提供D−T与T−D的强分离)。定理2(普特南–斯穆里安): (R) 的每个简单一致、可公理化扩张都是关于集合的精确罗瑟系统(经定理1的路线得到推论——这些扩张都是罗瑟系统)。斯穆里安证明条款 (1),把对称的 (2) “留给读者”(第92页);上表完成了两者。
表示与分离在哪里分道扬镳。 表示只需要可证性,所以定理S₁可以把强降级为弱(舍去可反驳的一半,耗费一剂一致性)。精确分离需要两种极性,所以定理S₂保留整个强分离,让可反驳的一半切实工作。这唯一差异——舍去还是保留可反驳的一边——就是两条路线的全部区别。
第六部分——§3的变体(练习4–10)及§4的加强结果
§3——定理3、其推论及练习(第94–95页)
定理3及其推论在变体自指语句上运行同一引擎,从而重新导出不完备性——即“罗瑟不可判定语句的一些奇妙变体”。讨论中的两个表示语句是模板:
∀z( A(x,z) ⊃ (∃w≤z) B(x,w) )及其对偶∃z( A(x,z) ∧ (∀w≤z) ~B(x,w) )。
推论直接给出:若关系 Π(x,y,z)∈P 在 S 中可枚举,且 S 是 Ω₄, Ω₅ 的一致扩张,则 S 不完备——通过表示装置,而不是第六章裸的分离,重新得到罗瑟的结果。
练习4–10(尚未完成,接下来处理):
- 练习4——使用练习5和引理1*,证明 Π(x,y,z)∉P 可与 Π(x,y,z)∈P ∧ x∈A 弱分离 ⟹(若一致)S 不完备。
- 练习5、练习6——为练习4提供输入的枚举步骤(Ω₄, Ω₅ 的扩张,以及 Π(x,y) 可枚举)。
- 练习7——练习6如何给出定理3的另一个证明。
- 练习8——若集合 {x : Π(x,x,x)∈P} 可表示,则 S 不完备。
- 练习9、练习10——对偶公式版本(具有 Π(x,z,x)∈P 的形状),给出通往练习6的又一条路线。
这些是第六章练习3–6在第七章的对应;每个都是引擎的简短应用,它们是本次研读尚欠的练习。
§4——定理S₁*、S₂*:命名公式(第96页)
用带星号的引理(1*、2*)取代普通引理,把两个定理从“存在一个表示/分离公式”加强为“这里就有一个,由它的哥德尔数给出”:
定理S₁*。 若
S是一个一致、可公理化、关于二元关系的罗瑟系统,且R(x,y)是 Σ₁,则存在数h,使E_h(v₁,v₂)是公式,且E_h(v₁,h̄)表示R(x,h)——即(∀n)[ n∈{x:R(x,h)} ⟺ E_h(n̄,h̄) 可证 ]。 定理S₂*。 相同假设下,对于不相交的 Σ₁ 关系R₁,R₂,存在h,使E_h(v₁,h̄)精确分离{x:R₁(x,h)}与{x:R₂(x,h)}。
练习11要求证明 S₁*, S₂*——直接可得,因为引理1*/2* 已经给出了命名的 h。斯穆里安指出,这些更精确形式“在我们的续篇中有有趣的应用”,而续篇会比较谢泼德森证明与原证明,两者朝不可比较的方向推广(第86页)。这个 * 加强恰好对应于第五章从“不完备”到“这里就是不可判定语句”的推进。
区分表
| 混淆 | 一句话解答 |
|---|---|
| 弱分离以可证/不可证为定义吗? | 不。 定义是“表示与 B 不相交的超集 A'⊇A”。可证/不可证条件对是导出的;“不可证”继承自表示的条款 (ii)。 |
“超集”是否意味着 A 是自己的超集? |
不。超集是 A' = {n:S⊢F(n̄)},即 F 实际表示的集合——一般通过无关紧要的区域成为 A 的真超集。 |
| 强 ⟹ 弱——机制是什么? | 对B条款使用简单一致性:可反驳 ⟹ 不可证。别无其他。 |
E[m̄,n̄] ≡ E(m̄,n̄) 有效且 E[m̄,n̄] 是语句——重复吗? |
不。逻辑有效性(任意 E)与语句资格(仅 v₁,v₂ 自由)是不同事实;前者使可证性传递,后者使“可证”有意义。 |
为什么用封装式 [ , ] 而非代入 ( , )? |
⌜E[m̄,n̄]⌝ = Π(⌜E⌝,m,n) 是简单的 Σ₀ 连接,在所有 x 上为全函数;代入的算术化很复杂。 |
Π(x,y,z)∈P ⟹ E_x 是公式——为何自动成立? |
只有语句可证;封装式仅当 E_x 是公式时才合式。P 过滤废料。 |
| 自指在哪里? | 对角化 ★:h=⌜E_h⌝ 位于 Π 的第1及第3槽位,所以 Π(h,n,h)∈P 意味着“E_h(n̄,h̄) 可证”。 |
引理1*中的 ∉P / ∈P 不对称——为何关键? |
若 U 中为 ∈P,陷阱 (1ₕ) 就空洞,R⟹可证 失效。“不可证”正是触发陷阱的条件。 |
~A 不是 Σ₁ 时,A 怎么可表示? |
从不直接针对 ~A 分离。取 Σ₁ 的 R₁=A、R₂=Prov;罗瑟差集免费制造 ~A、~Prov。 |
| 引理1* 使用一致性吗? | 不。 它是在给定弱分离上的纯粹不动点逻辑。简单一致性仅在定理S₁中进入(强 ⟹ 弱)。 |
| 表示与精确分离? | 表示 = 一个双条件(可证 ⟺ A)。精确分离 = 两个(可证 ⟺ A 且 可反驳 ⟺ B)= F 表示 A,~F 表示 B。 |
自测
问题1。 书以两种方式陈述弱分离。哪一种是定义,导出的“不可证”从何而来?
答案
定义 = “F 表示与 B 不相交的超集 A'⊇A。”刻画 n∈B ⟹ S⊬F(n̄) 是导出的:n∈B ⟹ n∉A'(不相交)⟹(表示条款ii)F(n̄) 不可证。表示中没有可反驳性,因此它不可能出现。
问题2。 在 Prov(x,y)=Π(y,x,y)∈P 中,为什么 y 必须占据第1及第3位置?
答案
由 (MEq),Π(a,b,c)∈P ⟺ E_a(b̄,c̄) 可证。为让语句谈论自身的可证性,我们将指标 a 与第二自变量 c 设为同一编码 h。所以 y(固定为 h 的槽位)必须同时占据两者——第1和第3位置。第2位置放真正的输入 x。在 y=h 时:Π(h,n,h)∈P ⟺ E_h(n̄,h̄) 可证。
问题3。 写出引理1*的两个关系 U、V,并指出哪个合取项承受关键负荷。
答案
U = R(x,y) ∧ Π(y,x,y)∉P;V = Π(y,x,y)∈P ∧ ~R(x,y)。U 中的 ∉P 承受关键负荷:它使陷阱 (1ₕ) R(n,h) ∧ [G 不可证] ⟹ G 可证 不为空洞。如果那里是 ∈P,正向 R⟹可证 就失效。
问题4。 引理1*证明完整双条件,却不使用一致性。这怎么可能?
答案
两个矛盾都是元语言层面的——“这个固定语句 G 既可证又不可证”——无论 S 是否一致,这都不可能。一致性(对象层面)只在比较可证与可反驳时才需要;引理1*始终只比较可证与不可证。
问题5。 在定理S₁中,~A 不是 Σ₁。证明如何仍然针对它分离?
答案
它不直接针对 ~A 分离。它交给罗瑟系统两个 Σ₁ 关系 R₁=A、R₂=Prov;差集 R₁−R₂=U 和 R₂−R₁=V 免费制造 ~A 与 ~Prov。所需的输入始终只有 Σ₁。
问题6。 把精确分离陈述为一对表示事实,并推出“在 A∪B 外不可判定”条款。
答案
F 精确分离 A 与 B,当且仅当 F 表示 A(可证 ⟺ n∈A),且 ~F 表示 B(可反驳 ⟺ n∈B)。在 A∪B 外:n∉A ⟹ 不可证,n∉B ⟹ 不可反驳 ⟹ 不可判定。
问题7。 为什么定理1(埃伦福伊希特–费弗曼)是定理S₁的推论,而非独立证明?
答案
因为 (R) 的每个简单一致、可公理化扩张都是关于二元关系的罗瑟系统(第六章的 Ω₄,Ω₅、≤ 机制)。定理S₁的假设满足,所以其结论——所有 Σ₁ 集可表示——直接传递。
参考与交叉链接
| 引入的结果 | 使用位置 | 来源 |
|---|---|---|
罗瑟系统;≤ 竞赛;“(R) 的扩张 ⟹ 罗瑟系统”;Ω₄, Ω₅ |
第一、四(定理1)、五部分 | 08‑03 引理S/定理3 |
表示与分离;P*, R*;枚举条款 |
第二、三部分 | 07‑30、08‑03 |
由可公理化性得 P 是 Σ₁;Σ₁ 闭包 |
第四部分(定理S₁) | 07‑29 导言、07‑28 命题C |
| Σ₀‑完备性(“所有真的 Σ₀ 都可证”),(R)=Ω₁–Ω₅ | 第四部分(定理1) | 07‑31 定理B* |
| 简单一致性 = “可反驳 ⟹ 不可证” | 第三、四部分 | 07‑29 |
本次书中范围:斯穆里安,《哥德尔不完备性定理》,第七章,第86–96页——§1(定理S₁、定理1;弱分离;函数 Π;引理1、引理1*、讨论、练习1),§2(引理2、引理2*、定理S₂、定理2、练习2–3),§3(定理3及推论、练习4–10),§4(定理S₁*、S₂*、练习11)。
接下来
- 第七章尚待完成的练习:练习4–10(§3的变体,每个都是引擎的简短应用);练习11(证明带星号的
S₁*, S₂*)。(两条路线现已完整证明——表示见第四部分,分离见V.3–V.4;后者的四行抽象证明补齐了斯穆里安“留给读者”的条款 (2)。) 这些练习就是直接的后续。 - 第五章仍欠:§6练习10–12(
P(X̄)可证性谓词;练习11的完整 Σ₁ 情形推迟到布洛斯)——Σ₁‑完备性欠账;以及第九章第二定理(为什么“G为真”不能在 P.A. 内形式化)。 - 续篇的比较(第86页预告):谢泼德森证明与最初埃伦福伊希特–费弗曼路线——“非常不同,朝看来不可比较的方向推广”。完整练熟分离路线之后,值得重访。
此前研读文件:07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 · 08‑03 · 08‑04(本文件)。