Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness Theorems — Session 2026‑08‑03
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 VI: Rosser Systems (pp. 75–85) — incompleteness from simple consistency alone
- Part 0 — The one‑sentence shift, and why it costs something
- Part I — GOAL and the reduction chain
- Part II — Citable glossary
- Part III — §1 Abstract incompleteness after Rosser
- Part IV — §2 The general separation principle (the ≤‑trick)
- Part V — §3 Rosser's undecidable sentence (assembling Theorem R)
- Part VI — §4 The Gödel and Rosser sentences compared
- Part VII — §5 More on separation (the point‑set backbone, Ex 10 / Thm 5)
- Part X — The payoff: why ω‑consistency is a "metamathematically weaker" assumption
- Distinctions Ledger
- Self‑Test
- References & cross‑links
- What's ahead
Chapter VI: Rosser Systems (pp. 75–85) — incompleteness from simple consistency alone
New chapter. Chapter V gave Gödel's second proof: incompleteness from ω‑consistency (plus "all true Σ₀ provable"). Rosser [1936] pushes the hypothesis down one more notch to simple consistency, paying for it with an extra structural demand (the system must prove Ω₄, Ω₅) and a cleverer undecidable sentence built on the ≤‑ordering of proofs. This session reconstructs that arc end‑to‑end, and then answers the standing conceptual question: in exactly what sense is ω‑consistency a "metamathematically weaker" assumption? (See Part X — it is the payoff.)
Reading order follows the logical spine, not always the book's page order.
Part 0 — The one‑sentence shift, and why it costs something
Last chapter's headline (Theorem A): axiomatizable + all‑true‑Σ₀‑provable + ω‑consistent ⟹ incomplete. Rosser's headline:
Theorem R. Every simply consistent axiomatizable extension of Ω₄ and Ω₅ in which all Σ₁‑sets are enumerable is incomplete.
The trade, stated by Smullyan's Remark (p. 76), is not a strict improvement but a sideways one:
| Theorem A (Gödel, Ch. V) | Theorem R (Rosser, Ch. VI) | |
|---|---|---|
| consistency hypothesis | ω‑consistent | simply consistent ← weaker (win) |
| structural hypothesis | none beyond Σ₀‑completeness | must prove Ω₄, Ω₅ ← extra demand (cost) |
| verdict | incomparable strength — neither implies the other |
So "Rosser improved Gödel" is only half true. Rosser weakens the consistency assumption (the metamathematically interesting axis) but adds a structural assumption. A system that is ω‑consistent but does not prove Ω₄/Ω₅ is covered by A and not by R; a system that is merely simply consistent but does prove them is covered by R and not by A. Corollary 2 (below) is what Shoenfield [1967] calls the Gödel–Rosser Incompleteness Theorem.
Corollaries of Theorem R (each just checks the hypotheses for a concrete system):
| statement | why it follows | |
|---|---|---|
| Cor 1 | simply consistent axiomatizable extension of Ω₄,Ω₅ with all true Σ₀ provable is incomplete | "all true Σ₀ provable ⟹ all Σ₁ enumerable" (Ch. V), feeding Theorem R |
| Cor 2 | every simply consistent axiomatizable extension of (R) is incomplete | (R)=Ω₁–Ω₅ proves Ω₄,Ω₅ and is Σ₀‑complete (Theorem B*) |
| Cor 3 | P.A., if simply consistent, is incomplete | P.A. ⊇ (R) |
Part I — GOAL and the reduction chain
GOAL. Prove P.A. incomplete assuming only its simple consistency (no ω‑consistency).
The last chapter reduced incompleteness to representing R* (or P*). Representation is where ω‑consistency was spent (enumerable → representable). Rosser's insight: do not represent R*; instead separate R* from P*. Separation is cheaper — it never needs ω‑consistency, only Ω₄/Ω₅ and Σ₀‑completeness — and simple consistency finishes the job at the very last step.
Reduction pipeline (Ch. VI theorem numbers):
Thm 1: H represents a superset of R* disjoint from P* ⟹ H(h̄) undecidable [consistency FREE — it's derived]
Lemma 1: F separates R* from P* + S simply consistent ⟹ H represents such a superset
Thm 2: F separates R* from P* + S simply consistent ⟹ S incomplete [= Lemma 1 ∘ Thm 1]
↑ Theorem 2 = Lemma 1 then Thm 1 (see assembly map below)
Ex 3/4: the ≤-ordering trick — the two provable/refutable halves
Lemma S: Ω₄,Ω₅ provable ⟹ R₁−R₂ separable from R₂−R₁ for enumerable R₁,R₂ [consistency FREE]
Thm 3: extension of Ω₄,Ω₅ with all-true-Σ₀-provable ⟹ Rosser system for sets
Thm 4: simply consistent + P*,R* enumerable + Ω₄,Ω₅ provable ⟹ incomplete [= Thm R for P.A.]
The load‑bearing observation (memorize this): simple consistency is one hypothesis, cashed at just two points — the difference‑collapse and Lemma 1's "F(n̄) refutable ⟹ not provable." Everything upstream — the separating formula, Ex 3/4, Lemma S, the difference sets — is built with no consistency assumption at all. That is the structural reason Rosser gets away with simple consistency: he front‑loads all the real work into consistency‑free separation, and only cashes two minimal checks at the end.
How the pieces join — assembling Theorem 4
The list above is the parts bin; this is how they bolt together. Theorem 4 (= Theorem R) is the only end‑product — everything else is a feeder. Two chains converge on it:
FEEDER α — the SEPARATOR FEEDER β — the ENGINE ( = Theorem 2 )
Ex 3/4 (≤-race halves) Theorem 1 ─┐
│ ├─▶ Theorem 2
Lemma S ⟹ H separates Lemma 1 ──┘
R*−P* from P*−R* │
└───────────────┐ ┌──────────┘
▼ ▼
T H E O R E M 4 ⟹ Theorem R
(P.A. incomplete from SIMPLE consistency)
side-branch (general packaging, NOT on the path to Thm 4):
Lemma S + Σ₀-completeness ⟹ Theorem 3 ⟹ (R),(Q),P.A. are Rosser systems
Theorem 4's three hypotheses — H1 simply consistent, H2 P*,R* enumerable, H3 Ω₄,Ω₅ provable — are spent in three stages:
| stage | what you now have | built by | hypothesis spent |
|---|---|---|---|
| 1 · separator | H separates R*−P* from P*−R* |
Lemma S ← Ex 3/4 | H2 + H3 — no consistency |
| 2 · collapse | H separates R* from P* |
R*∩P*=∅ ⟹ R*−P*=R*, P*−R*=P* |
H1 (applied to stage 1) |
| 3 · engine | H(h̄) undecidable ⟹ incomplete |
Theorem 2 (applied to stage 2) | H1 again (inside Lemma 1) |
The one subtlety you flagged — Theorem 2 is not atomic. Stage 3 hides two earlier pieces:
Theorem 2 ( input: "H separates R* from P*" + H1 )
│
├─ Lemma 1 : separates ─▶ represents a superset A⊇R* disjoint from P* ← spends H1
│
└─ Theorem 1 : that representation ─▶ H(h̄) undecidable ← spends nothing (it DERIVES consistency)
So the complete descent from the headline down to bedrock is:
Theorem R ═ Theorem 4
├─ stage 1 → Lemma S → Ex 3/4 [Ω₄,Ω₅ + enumeration; NO consistency]
├─ stage 2 → difference-collapse [H1]
└─ stage 3 → Theorem 2 → { Lemma 1 [H1] , Theorem 1 [—] }
Consistency ledger (the whole account). H1 is one hypothesis cashed at two points — the stage‑2 collapse and Lemma 1's "refutable ⟹ not provable." H2, H3 are cashed once, both inside stage 1's Lemma S. Theorem 1 and the separating formula spend nothing. The entire ≤‑machine (Ex 3/4 → Lemma S) runs consistency‑free; consistency only does the two small closing jobs. (This is the same accounting as Theorem 4's proof table, lines 1 and 5, now shown as a descent.)
Role of each piece — one‑glance architecture. Every row answers the question you asked: what is this doing for Theorem 4?
| piece | one‑line job | on the Thm 4 path? |
|---|---|---|
| Ex 3/4 | the ≤‑race — the provable & refutable halves of H |
✓ raw material for Lemma S |
| Lemma S | builds the separator H; separates the difference sets — no consistency |
✓ stage 1 |
| Theorem 1 | undecidability core: "represents a superset ⊇R* disjoint from P*" ⟹ "H(h̄) undecidable" |
✓ (inside Thm 2) |
| Lemma 1 | upgrader + consistency‑spender: "separates R* from P*" (+ H1) ⟹ that representation |
✓ (inside Thm 2) |
| Theorem 2 | the engine = Lemma 1 then Theorem 1: a separator (+ H1) ⟹ incomplete | ✓ stage 3 |
| Theorem 4 | assembles stage 1 (Lemma S) + stage 2 (collapse, H1) + stage 3 (Thm 2) | ═ Theorem R |
| Theorem 3 | sibling, not feeder: same Lemma S on all disjoint Σ₁ pairs — the reusable engine of later chapters (undecidability, inseparability) | ✗ not this proof |
| Theorem 5 | point‑set backbone: refine any Σ₁ pair to disjoint Σ₁ supersets of the differences | ✗ off‑path |
On Theorem 3 specifically (the piece whose role felt vague): it is not a step inside Theorem 4. Theorem 4 runs Lemma S on the one pair R*,P*; Theorem 3 runs the same Lemma S on every disjoint Σ₁ pair. They are siblings sharing one parent (Lemma S), and neither is invoked by the other. Theorem 3's job is to name the general property ("Rosser system for sets") and certify that concrete systems have it (the corollaries) — not to drive incompleteness.
Part II — Citable glossary
Carried from prior sessions: E_n = formula with Gödel number n (one free variable v₁); E_n(n̄) its self‑application; P* = {n : E_n(n̄) provable}, R* = {n : E_n(n̄) refutable}.
- represents
A(inS):(∀n)[ S⊢H(n̄) ⟺ n∈A ]. Two‑directional, exact. (Ch. V: needed ω‑consistency to obtain forR*.) - enumerates
A(by a 2‑placeA(v₁,v₂)):n∈A ⟹ ∃m S⊢A(n̄,m̄)(clause 1) andn∉A ⟹ ∀m S⊢~A(n̄,m̄)(clause 2). One‑directional, cheap; from Σ₀‑completeness alone. - separates
AfromB(byF(v₁)):n∈A ⟹ S⊢F(n̄)(provable) andn∈B ⟹ S⊢~F(n̄)(refutable). No claim aboutnoutsideA∪B. - separates a relation
R₁fromR₂(byF(v₁,…,vₙ)): then‑ary version, instance by instance. - witness. With
A(x,y)enumeratingP*: ifA(x̄,ȳ)true thenyis a witness thatxis provable. SymmetricallyB(x,y)enumeratesR*; aB‑witness certifiesxis refutable. - difference sets.
R₁−R₂ = {x : R₁(x) ∧ ¬R₂(x)}. NoteR₁−R₂andR₂−R₁are disjoint for anyR₁,R₂— disjointness is built in, requiring no consistency. This is the hinge of the whole method. - Rosser system for sets — every pair of disjoint Σ₁ sets is separable in
S. Rosser system for n‑ary relations — same for disjoint Σ₁n‑ary relations. Rosser system — the latter for everyn. - Ω₄
v₁≤n̄ ≡ (v₁=0̄∨…∨v₁=n̄)Ω₅v₁≤n̄ ∨ n̄≤v₁(linearity). (From Ch. V; (R)=Ω₁–Ω₅, and (Q),P.A. prove both.) These two are exactly what lets a proof "reason by cases ony≤n̄vsn̄≤y" and "unpack a bounded quantifier into a finite disjunction" — the two moves the≤‑trick needs. - simply consistent — no sentence both provable and refutable. ω‑consistent — no
B(v)with∃vB(v)provable yet everyB(m̄)refutable. (Def‑chain analyzed in Part X.)
Part III — §1 Abstract incompleteness after Rosser
Ch. VI Theorem 1 — representing a superset of R* disjoint from P* suffices
→ Role for Theorem 4: the undecidability core. Input = "H represents a superset A⊇R* disjoint from P*"; output = "H(h̄) undecidable." It is the last act of Theorem 4 (inside Theorem 2, stage 3) and spends no consistency — it even derives it.
Load. Weaken Ch. V's "represent R*" to "represent any superset A ⊇ R* with A∩P*=∅," and still get an undecidable sentence — and get consistency for free.
Statement. If H(v₁) represents in S a set A with R*⊆A and P*∩A=∅, then H(h̄) is undecidable in S, where h = Gödel number of H(v₁).
Proof.
| # | Claim | Justification |
|---|---|---|
| 1 | S⊢H(h̄) ⟺ h∈A |
H represents A, instance n:=h |
| 2 | S⊢H(h̄) ⟺ h∈P* |
definition of P* (H(h̄)=E_h(h̄)) |
| 3 | h∈A ⟺ h∈P* |
1 ∧ 2 |
| 4 | h∉P* and h∉A |
3 + A∩P*=∅ (can't be in both ⟹ in neither) |
| 5 | H(h̄) not provable |
4 (h∉P*) via 2 |
| 6 | h∉R* |
4 (h∉A) + R*⊆A |
| 7 | H(h̄) not refutable |
6 + def of R* (H(h̄) refutable ⟺ h∈R*) |
| 8 | H(h̄) undecidable |
5 ∧ 7 ∎ |
Remark — consistency is derived, not assumed. The hypotheses R*⊆A and P*∩A=∅ force R*∩P*=∅. But R*∩P*≠∅ would mean some sentence is both provable and refutable. So the hypotheses entail simple consistency; no need to list it. (This already exceeds Ch. V's Theorem 1′, which had to assume consistency.)
Exercise 1 (dual). A superset of P* disjoint from R*, represented in S, likewise yields incompleteness — the mirror image, refuting instead of proving the diagonal sentence.
Ch. VI Lemma 1 — separation upgrades to representation‑of‑a‑superset (here consistency enters)
→ Role for Theorem 4: the upgrader, and one of the two consistency cashes. Input = "F separates R* from P*" + simple consistency; output = "F represents a superset A⊇R* disjoint from P*" — precisely Theorem 1's input. It is the first half of stage 3's Theorem 2.
Statement. If F(v₁) separates A from B in S and S is simply consistent, then F represents some superset A'⊇A disjoint from B.
Proof. Let A' = {n : S⊢F(n̄)} (the set F actually represents).
| # | Claim | Justification |
|---|---|---|
| 1 | A ⊆ A' |
n∈A ⟹ S⊢F(n̄) (separation, provable half) ⟹ n∈A' |
| 2 | B ∩ A' = ∅ |
n∈B ⟹ S⊢~F(n̄) (refutable half); simple consistency ⟹ S⊬F(n̄) ⟹ n∉A' |
A'⊇A, A'∩B=∅. ∎ This step 2 is the sole consumer of consistency in the entire chapter.
Ch. VI Theorem 2 — the reduction target
→ Role for Theorem 4: the whole engine = Lemma 1 then Theorem 1. Input = a separator of R* from P* (+ simple consistency); output = incompleteness. In Theorem 4 this is stage 3 — it consumes the separator that stages 1–2 produced.
Statement. If F separates R* from P* in S and S is simply consistent, then S is incomplete (the diagonal F(f̄) is undecidable).
Proof. Lemma 1 (A:=R*, B:=P*) ⟹ F represents a superset of R* disjoint from P* ⟹ Theorem 1 ⟹ undecidable. ∎
So the whole problem is now: separate
R*fromP*in P.A. — with no consistency needed for the separation itself. This is exactly what Rosser did (Smullyan, p. 78). Exercise 2 is the dual (separateP*fromR*).
Part IV — §2 The general separation principle (the ≤‑trick)
Rosser's separation of R* from P* is a special case of a general fact: any two disjoint Σ₁ sets are separable in a system proving Ω₄, Ω₅. The engine is a single formula that breaks ties by which witness shows up first.
The tie‑breaker, in miniature — Exercises 3 & 4
Let A(x,y) enumerate P* (provability witnesses) and B(x,y) enumerate R* (refutation witnesses). Rosser's separating formula for R* from P* is
H(x) := ∀y[ A(x,y) ⊃ (∃z≤y) B(x,z) ]— "every proof ofxis met by a refutation ofxappearing no later."
Exercise 3 (semantic warm‑up, truth). For σ := ∀y[F₂(y) ⊃ (∃z≤y)F₁(z)]: if F₁(n̄) is true and every F₂(m̄) (m≤n) is false, then σ is true (the antecedent fails below n, and at/above n the witness z=n works). This is the pure‑arithmetic skeleton, no provability yet.
Exercise 4 (the real lemma, provability, needs Ω₄,Ω₅). Same σ, with F₁,F₂ now matched to B,A:
Part 1 — the provable half. If S⊢F₁(n̄) and S⊢~F₂(m̄) for every m≤n, then S⊢σ.
case on y |
argument | uses |
|---|---|---|
n̄≤y |
F₁(n̄) provable and n̄≤y ⟹ (∃z≤y)F₁(z) (witness z=n̄) ⟹ consequent holds |
— |
y≤n̄ |
Ω₄: y=0̄∨…∨y=n̄; each S⊢~F₂(k̄) (k≤n) ⟹ S⊢~F₂(y) ⟹ antecedent fails ⟹ implication holds |
Ω₄ |
| bundle | Ω₅ (y≤n̄ ∨ n̄≤y) makes the two cases exhaustive; discharge ∀y |
Ω₅ |
Why n is a threshold, and where m≤n is born. The witness n (from S⊢F₁(n̄)) splits every y into two regimes, each leaning on a different premise:
- y ≥ n (at/above threshold): the F₁‑witness at n fills the consequent (∃z≤y)F₁(z) — because n≤y, z=n̄ works. The implication holds by its right side; nothing about F₂ is needed here.
- y ≤ n (below threshold): by Ω₄, y∈{0̄,…,n̄}, so we kill the antecedent F₂(y) using S⊢~F₂(y) — and that is needed only for these values, i.e. only m≤n.
So m≤n is not an assumption we impose; it is exactly the band of y that falls into the antecedent‑killing case. Above n, the single F₁‑witness carries every implication for free, so no F₂‑fact is required there. (In the R*−P* application, x∉P* hands us A(x̄,m̄) refutable for all m (Chain 2), so the m≤n demand is over‑met — the bound only bites in the general tie‑breaking case, where you control refutations only up to the first witness.)
Part 2 — the refutable half. If S⊢F₂(n̄) and S⊢~F₁(m̄) for every m≤n, then S⊢~σ.
| # | claim | justification |
|---|---|---|
| 1 | witness y=n̄: S⊢F₂(n̄) |
hypothesis |
| 2 | S⊢(∀z≤n̄)~F₁(z) |
Ω₄ unpacks z≤n̄ to z=0̄∨…∨z=n̄; each S⊢~F₁(k̄) |
| 3 | S⊢ F₂(n̄) ∧ (∀z≤n̄)~F₁(z) = S⊢∃y[F₂(y)∧(∀z≤y)~F₁(z)] = S⊢~σ |
1,2 |
Now match to R*/P* (with F₂=A, F₁=B, so σ = H(x)):
x is… |
premises we have (from membership) | what Ex 4 needs ( ⊆ what we have) | ⟹ | so H … |
|---|---|---|---|---|
x∈R*, x∉P* |
B(x̄,n̄) provable (from ∈R*, some n) + A(x̄,m̄) refutable for all m (from ∉P*) |
Part 1: B(x̄,n̄) provable + A(x̄,m̄) refutable for m≤n — the m≤n band is a subset of "all m", so ✓ |
S⊢H(x̄) |
proves on R* |
x∈P*, x∉R* |
A(x̄,n̄) provable (from ∈P*, some n) + B(x̄,m̄) refutable for all m (from ∉R*) |
Part 2: A(x̄,n̄) provable + B(x̄,m̄) refutable for m≤n — the m≤n band is a subset of "all m", so ✓ |
S⊢~H(x̄) |
refutes on P* |
The middle arrow is the step you named: "all m refutable" (what membership gives) ⟹ "m≤n refutable" (all Ex 4 consumes), because {m : m≤n} ⊆ {all m}. We have more than we need; the surplus is harmless.
Reading the table — the premise‑vs‑case‑split trap. The two items in each row are the two premises of Ex 4, holding simultaneously — not two branches of a choice. They arrive from two different memberships: B(x̄,n̄) provable comes from x∈R* (a refutation‑witness exists — enum clause 1); every A(x̄,m̄) refutable comes from x∉P* (no proof ⟹ every proof‑instance refuted — clause 2). Both feed Part 1 at once. The "n̄≤y ⟹ use B, y≤n̄ ⟹ use A" split is inside the proof of Part 1 (the case table just above): for each y the proof reaches for whichever premise fits, but it must hold both to cover all y. Premises coexist; the proof spends them case by case. (This two‑fact package — in R*, not in P* — is exactly why we work with the difference set R*−P*.)
So H separates R* from P* — provided they are disjoint. But H never assumed disjointness of the sets; it only used, for each individual x, that x sits in one difference and not the other. That is why the honest general statement is about differences:
Lemma S (Separation Lemma) — the consistency‑free core
→ Role for Theorem 4: the separator builder — stage 1. Input = Ω₄,Ω₅ (H3) + R*,P* enumerable (H2); output = "H separates the differences R*−P*, P*−R*," with no consistency. It manufactures the very H that stage 3's Theorem 2 consumes.
(i) The strategy, in the large
We need — from Theorem 2 — one formula H that is provable on R* and refutable on P*; that is all "separates R* from P*" means. The whole logic of Rosser's construction is this single top‑to‑bottom chain. Read it first; the tables afterward only fill in the arrows.
GOAL (Theorem 2): build H that SEPARATES R* from P*
i.e. n∈R* ⟹ S⊢H(n̄) and n∈P* ⟹ S⊢~H(n̄)
│
coherence check: what if some n ∈ R* ∩ P* ?
separation would demand S⊢H(n̄) AND S⊢~H(n̄)
= H(n̄) both provable and refutable = an INCONSISTENCY.
⟹ "separate R* from P*" is a coherent demand ONLY when
R* ∩ P* = ∅ … and that emptiness IS simple consistency.
(NB — this box is MOTIVATION, not a proof step: it does NOT
establish R*∩P*=∅. It only shows the separation demand must be
PAID FOR by consistency SOMEWHERE. That debt is deferred, and
finally cashed at Theorem 4's closure — stage 2: assume H1 ⟹
R*∩P*=∅ ⟹ the differences collapse to R*, P*.)
│
Rosser's move: don't bolt consistency on at the start. Prove instead the
consistency‑FREE statement about the DIFFERENCE sets:
│
LEMMA S gives: H separates R*−P* from P*−R*
├ (fact 1) R*−P* and P*−R* are disjoint for ANY sets — free.
├ (fact 2) "n ∈ R*−P*" is WORD‑FOR‑WORD the premise that
│ fires Ex 4's provable half ⟹ S⊢H(n̄)
└ (fact 3) "n ∈ P*−R*" is WORD‑FOR‑WORD Ex 4's refutable half
⟹ S⊢~H(n̄)
uses Ω₄, Ω₅ (inside Ex 4); uses NO consistency.
│
THEOREM 4 closes: NOW add simple consistency ⟹ R* ∩ P* = ∅
⟹ R*−P* = R* and P*−R* = P*
⟹ Lemma S now literally reads "H separates R* from P*"
⟹ feed Theorem 2 ⟹ S incomplete.
Three prose beats expanding that spine — this is the part that was vague:
(a) Yes — we genuinely want disjointness, and here is exactly why. "Separate A from B" asks F to be provable on A and refutable on B. If a single n lies in A∩B, the two clauses collide: they ask F(n̄) to be provable and refutable at once — which is an inconsistency. So separation is even a coherent request only for disjoint A,B; over an overlap it can be met only by an already‑inconsistent system. Two ways out: (i) assume R*,P* disjoint up front — but that is assuming simple consistency; (ii) only ever request separation where disjointness comes for free. Rosser takes (ii), which is why his construction needs no consistency of its own.
(b) Difference sets supply that free disjointness — and lose nothing. For any sets, R*−P* and P*−R* are disjoint (a member of the first is outside P*; a member of the second is inside P* — they cannot share an element). So separating them is always a coherent request. And nothing is sacrificed: the moment we do know S is simply consistent, R*∩P*=∅ makes R*−P* collapse back to R* exactly (Theorem 4, line 2). The differences are a scaffold that dissolves once consistency is available.
(c) The quiet miracle: the difference‑set condition is the trigger. Unfold membership against the two enumeration clauses (B enumerates R* = refutation‑witnesses, A enumerates P* = proof‑witnesses):
n∈R*−P*≡n∈R*(clause 1: a refutation‑witness exists,S⊢B(n̄,k̄)) andn∉P*(clause 2: every proof‑instance is refuted,S⊢~A(n̄,m̄)for allm).
Those two facts are, verbatim, the two premises of Exercise 4, Part 1. So n∈R*−P* ⟹ S⊢H(n̄) follows with nothing added. Membership in the difference set doesn't lead to the hypothesis — it is the hypothesis. (Symmetrically n∈P*−R* is Part 2's premise.) That equality is the entire reason the ≤‑race works without consistency: (∃z≤y) settles proof‑vs‑refutation ties by who is numerically first, doing syntactically the job ω‑consistency did semantically last chapter.
(ii) Statement and detailed proof
Statement. If all formulas of Ω₄, Ω₅ are provable in S, and R₁, R₂ are enumerable in S — say B(x,y) enumerates R₁ and A(x,y) enumerates R₂ — then
H(x) = ∀y[ A(x,y) ⊃ (∃z≤y) B(x,z) ]separatesR₁−R₂fromR₂−R₁inS.
(For the incompleteness application, R₁=R* and R₂=P*; R*, P*, and "enumerates" trace back to the 07‑29 prelude and 07‑30.)
Proof — the provable half (n ∈ R₁−R₂ ⟹ S⊢H(n̄)):
| # | Claim | Justification |
|---|---|---|
| 1 | n∈R₁ ⟹ S⊢B(n̄,k̄) for some k |
B enumerates R₁, clause 1 (a witness is provable) |
| 2 | n∉R₂ ⟹ S⊢~A(n̄,m̄) for every m (in particular all m≤k) |
A enumerates R₂, clause 2 (non‑member ⟹ every instance refutable) |
| 3 | S⊢H(n̄) |
Ex 4, Part 1 with F₁=B, F₂=A, index k: rows 1–2 are exactly its two premises (Ω₄,Ω₅ consumed there) |
Proof — the refutable half (n ∈ R₂−R₁ ⟹ S⊢~H(n̄)), mirror image:
| # | Claim | Justification |
|---|---|---|
| 1 | n∈R₂ ⟹ S⊢A(n̄,k̄) for some k |
A enumerates R₂, clause 1 |
| 2 | n∉R₁ ⟹ S⊢~B(n̄,m̄) for all m≤k |
B enumerates R₁, clause 2 |
| 3 | S⊢~H(n̄) |
Ex 4, Part 2 with F₁=B, F₂=A, index k |
No line cites consistency. The only non‑logical inputs are the four enumeration clauses and Ω₄/Ω₅ (buried in Ex 4). ∎
One‑line role recap. A marks proofs, B marks refutations; H says "every proof y of me is met by a refutation z≤y." On R₁−R₂ there is a refutation and no proof at all, so H holds trivially (provable); on R₂−R₁ there is a proof and no refutation, so H fails at that proof (refutable). The ≤ only matters in the overlap R₁∩R₂ — which the difference sets exclude, which is why we never needed to look there.
- Exercise 5. Derive Lemma S from Exercise 4 — it is precisely Parts 1–2 read off the difference sets (the proof tables above are this derivation).
- Exercise 6. Check that the dual formula
∃y[B(x,y) ∧ (∀z≤y)~A(x,z)]also separatesR₁−R₂fromR₂−R₁. WhenA,Benumerate disjoint sets,A−B=AandB−A=B, so it separates them directly.
Ch. VI Theorem 3 — Rosser systems exist
→ Role (sibling, not feeder — but far from idle): Theorem 3 is not a lemma inside Theorem 4's proof — delete it and P.A.'s incompleteness still stands (Theorem 4 runs Lemma S straight on R*,P*). What it adds is generality: the same Lemma S separates every disjoint Σ₁ pair, so incompleteness is exposed as one instance of a system‑wide separating power. That generality is what carries Corollary 2 (all extensions) and the undecidability/inseparability results of later chapters. See "Why prove the general version?" at the end of this section.
What must be shown. "S is a Rosser system for sets" means: every pair of disjoint Σ₁ sets A,B (not just R*,P*) is separable in S. So fix an arbitrary disjoint Σ₁ pair and produce a separator.
The gap Lemma S leaves — and where "all Σ₁ enumerable" plugs in. Lemma S separates A−B from B−A, but only if A,B are enumerable in S — that is its precondition. Being Σ₁ is a property of a set as a set; being enumerable in S is a property of what S can prove — two different things, not connected for free. The bridge that links them is Ch. V's: all true Σ₀ provable ⟹ every Σ₁ set is enumerable in S (the 07‑31 enumeration step 2a). That is the entire role of "all Σ₁ enumerable": it upgrades an arbitrary Σ₁ pair to a pair Lemma S will accept.
| # | step | why |
|---|---|---|
| 1 | fix arbitrary disjoint Σ₁ A,B |
this is what "Rosser system for sets" must cover |
| 2 | A,B are enumerable in S |
hypothesis all true Σ₀ provable ⟹ all Σ₁ enumerable (Ch. V bridge) — the factor in question |
| 3 | H separates A−B from B−A |
Lemma S: Ω₄,Ω₅ provable (hypothesis) + A,B enumerable (2) |
| 4 | A−B=A, B−A=B |
A,B disjoint (1) |
| 5 | H separates A from B |
3 + 4 |
| 6 | ∴ S is a Rosser system for sets |
1–5 held for an arbitrary disjoint Σ₁ pair ∎ |
Note the two hypotheses attach at different rungs: Ω₄,Ω₅ and enumerability both feed step 3 (via Lemma S), while disjointness does step 4. The original one‑liner collapsed 2→3→5 and hid step 2.
Theorem 3. Any extension of Ω₄, Ω₅ in which all true Σ₀‑sentences are provable is a Rosser system for sets. Corollary. (R), (Q), P.A. are all Rosser systems for sets.
Why the corollary holds — each system meets both hypotheses: they prove Ω₄, Ω₅ (axioms of (R); theorems of (Q), P.A. by Ch. V Prop 4/5) and they are Σ₀‑complete (Theorem B*). So Theorem 3 applies to all three.
Why prove the general Theorem 3 at all? — since Theorem 4 alone already incompletes P.A. Four reasons, none of them "the proof needs it," all of them "it is the right object":
- It names the essential property. Theorem 4 shows P.A. is incomplete because
R*separates fromP*. Theorem 3 shows this is no accident of those two sets: P.A. separates any disjoint Σ₁ pair. Incompleteness becomes a symptom of a general capability — it answers "why does Rosser's trick work?" (the system is a Rosser system), not merely "that it works." - It carries the "all extensions" corollary. Corollary 2 — every simply consistent axiomatizable extension of (R) is incomplete (the Gödel–Rosser theorem) — is cleanest as: extension of (R) ⟹ Σ₀‑complete ⟹ (Theorem 3) Rosser system ⟹ incomplete. Uniformity over all extensions is a statement about separating power (Theorem 3's content), not the single‑pair argument of Theorem 4.
- It is the reusable tool downstream. Exercise 7 is flagged "needed in the next chapter" and builds separation for relations. Separating disjoint Σ₁ sets/relations (= being a Rosser system) is the master tool behind what follows: undecidability of the theory (Church — no algorithm decides theoremhood), recursive and effective inseparability, essential undecidability/incompleteness. Incompleteness is just its first, simplest application.
- It is nearly free. The general version is proved by the same Lemma S as the special case — no extra work buys much more reach. Smullyan proves it once and harvests both the incompleteness instance (Theorem 4) and everything above.
So Theorem 3 is not a load‑bearing beam of this proof — it is the conceptual home of the method and the tool the rest of the theory stands on. Theorem 4 fires the machine at the one pair R*,P* that undecides a sentence; Theorem 3 is the machine. (This is also why Theorem 4 lists "P*,R* enumerable" as a hypothesis: they are enumerable because axiomatizability makes them Σ₁ and the Σ₀‑completeness bridge makes every Σ₁ set enumerable — the same bridge Theorem 3 uses wholesale.)
Part V — §3 Rosser's undecidable sentence (assembling Theorem R)
Ch. VI Theorem 4 — the abstract engine (Theorem R & Cors 1–3 specialize it)
Statement. Let S be simply consistent, with P* and R* enumerable and Ω₄, Ω₅ provable. Then S is incomplete.
Proof.
| # | Claim | grounds (which earlier piece) | what that piece is doing |
|---|---|---|---|
| 1 | P*∩R*=∅ |
hypothesis H1 (simple consistency) | first consistency cash — forces the two sets disjoint |
| 2 | R*−P*=R*, P*−R*=P* |
line 1 | stage 2: collapse the differences down to the sets |
| 3 | H separates R*−P* from P*−R* |
Lemma S + H2 (enumerable) + H3 (Ω₄,Ω₅) | stage 1: builds the separator H, consistency‑free |
| 4 | H separates R* from P* |
2 + 3 | feed the collapse into Lemma S's output |
| 5 | H(h̄) undecidable ⟹ incomplete |
Theorem 2 = Lemma 1 (H1) then Theorem 1 | stage 3: the engine — Lemma 1 turns "separates R* from P*" into "represents a superset ⊇R* disjoint from P*"; Theorem 1 turns that into "H(h̄) undecidable" ∎ |
Every hypothesis, placed. H2 (enumerable) and H3 (Ω₄,Ω₅) are spent once, both inside Lemma S (line 3). H1 (simple consistency) is one hypothesis cashed at two points — line 1's collapse and Lemma 1 inside line 5. ω‑consistency appears nowhere. See the staged assembly in Part I for this same descent drawn as a tree (Theorem 4 → Theorem 2 → Lemma 1 / Theorem 1).
How Theorem R and Corollaries 1–3 come out of Theorem 4 (the specialization ladder). Direction first: Theorem 4 is the general form; each result below is a specialization of it (narrower, more concrete), so the arrows run Theorem 4 ⟹ Theorem R ⟹ Cor 1 ⟹ Cor 2 ⟹ Cor 3. To make that legible, freeze Theorem 4's content as three requirements on a system S:
Theorem 4, spelled out. If
Sis (a) simply consistent, (b) proves Ω₄, Ω₅, and (c) hasP*, R*enumerable inS, thenSis incomplete.
Every rung below keeps (a) and (b) verbatim — they are already concrete — and specializes only (c), swapping "P*,R* enumerable" for a stronger but more checkable condition that implies it. So the table's three columns just are (a)/(b)/(c). A cell marked [carried] repeats a Theorem‑4 requirement unchanged; [specialized] is the one place that rung does work. The conclusion — S incomplete — never changes; only the route to (c) narrows.
| statement | (a) simply consistent | (b) proves Ω₄, Ω₅ | (c) P*,R* enumerable — how this rung gets it |
|---|---|---|---|
| Theorem 4 (core) | assumed | assumed | assumed directly |
| Theorem R | [carried] | [carried] (= "extension of Ω₄,Ω₅") | [specialized] axiomatizable ⟹ P*,R* are Σ₁ sets (07‑31 §2b–2c); + all Σ₁ enumerable ⟹ those two are enumerable |
| Corollary 1 | [carried] | [carried] | [specialized] axiomatizable ⟹ Σ₁; + all true Σ₀ provable ⟹ (Ch. V bridge) all Σ₁ enumerable |
| Corollary 2 | [carried] | [carried] — supplied by extending (R) | [specialized] axiomatizable + (R) is Σ₀‑complete (Theorem B*) ⟹ enumerable |
| Corollary 3 | [carried] (P.A.'s sole hypothesis) | [carried] — P.A. ⊇ (R) proves them | [specialized] P.A. axiomatizable + Σ₀‑complete ⟹ enumerable |
Scan the columns: (a) and (b) are a solid wall of [carried] — every rung inherits them untouched — while (c) is entirely [specialized], a different (stronger, more concrete) supply at each step. That column is the ladder.
Read top‑down, each rung trades one abstract hypothesis for a more familiar one: "P*,R* enumerable" ⤳ "all Σ₁ enumerable" ⤳ "all true Σ₀ provable" ⤳ "extends (R)" ⤳ "is P.A." That descent is the whole reason to state Theorem R and its corollaries at all: Theorem 4 is the engine; Theorem R and Cors 1–3 bolt it onto ever‑more‑concrete systems. (So the assembly diagrams' shorthand "Theorem 4 = Theorem R" means "same engine" — Theorem R is just the checkable packaging of it, one rung down the ladder.)
Rosser's sentence, concretely. With h = Gödel number of ∀y[A(v₁,y)⊃(∃z≤y)B(v₁,z)], the undecidable sentence is
ρ = ∀y[ A(h̄,y) ⊃ (∃z≤y) B(h̄,z) ]— "for every proof of me, there is a refutation of me no later than it."
Part VI — §4 The Gödel and Rosser sentences compared
Both are diagonal fixed points built from the same two enumerators A (provability, P*) and B (refutability, R*). They differ in what the fixed point asserts about its own proofs.
Gödel G |
Rosser ρ |
|
|---|---|---|
| formula | ∀y ~A(h̄,y) |
∀y[A(h̄,y) ⊃ (∃z≤y)B(h̄,z)] |
| self‑reading | "there is no witness that I am provable" = "I am unprovable" | "every witness that I am provable is overtaken by a witness that I am refutable" |
| unprovable needs | simple consistency | simple consistency |
| unrefutable needs | ω‑consistency | simple consistency |
| why the difference | G refutable would give ∃y A(h̄,y) provable while all ~A(h̄,m̄) provable — only ω‑consistency rules this out |
ρ refutable is blocked by the ≤‑race: a refutation witness would have to precede itself; simple consistency suffices |
Dual Rosser sentence (Exercise 6's formula, diagonalized at its own number b):
ρ' = ∃y[ B(b̄,y) ∧ (∀z≤y)~A(b̄,z) ]— "I have a refutation earlier than any proof of me." Also undecidable under simple consistency.
The moral: Gödel's G says "unprovable" and needs an external promise (ω‑consistency) that its instances don't lie about the ∃; Rosser's ρ internalizes that promise as a numerical race between proof‑ and refutation‑codes, so nothing beyond simple consistency is required. The ≤ is doing, inside the arithmetic, the work ω‑consistency did from outside.
Part VII — §5 More on separation (the point‑set backbone, Ex 10 / Thm 5)
→ Role: off the incompleteness path. Theorem 5 proves nothing about S or provability — it is the pure set‑theoretic skeleton beneath Lemma S, showing the difference‑refinement is a fact about Σ₁ sets as such. Its payoff (the corollary) is that "Rosser system for sets" (stated for disjoint pairs) and "separates all differences" are the same property — which is why Theorem 4 may freely phrase everything through difference sets.
Statement. For any two Σ₁ sets A,B there are disjoint Σ₁ sets A' ⊇ A−B and B' ⊇ B−A.
Construction. A,B Σ₁ ⟹ pick Σ₀ relations R₁,R₂ with A={x:∃y R₁(x,y)}, B={x:∃y R₂(x,y)} (Σ₁ normal form). Define
- A' = {x : ∃y[ R₁(x,y) ∧ (∀z≤y)~R₂(x,z) ]} — "an R₁‑witness with no R₂‑witness at or below it,"
- B' = {x : ∃y[ R₂(x,y) ∧ (∀z≤y)~R₁(x,z) ]} — the mirror image.
Three checks:
| claim | argument |
|---|---|
A−B ⊆ A' |
x∈A−B: x∈A gives an R₁‑witness y; x∉B gives ~R₂(x,z) for all z (so all z≤y). That same y witnesses x∈A'. (Symmetrically B−A ⊆ B'.) |
A'∩B'=∅ — the ≤‑race |
Suppose x∈A'∩B': an R₁‑witness y with (∀z≤y)~R₂, and an R₂‑witness y' with (∀z≤y')~R₁. WLOG y≤y'; then y is an R₁‑witness with y≤y', but B' demands ~R₁(x,y) — contradiction. (Whoever's witness is smaller wins; the other side's bounded ∀ forbids it.) |
A',B' Σ₁ |
matrix R₁(x,y) ∧ (∀z≤y)~R₂(x,z) is Σ₀ (bounded ∀); one leading ∃y ⟹ Σ₁. |
Model‑free shadow of Lemma S. The identical ∃y[ … ∧ (∀z≤y)~ … ] shape that separated provably in S now refines any two Σ₁ sets into disjoint Σ₁ supersets of their differences — no S, no proofs, pure sets. (Exercise 10 asks for exactly this.)
Corollary (Theorem 6). If every disjoint pair of Σ₁ sets is separable in S (i.e. S is a Rosser system for sets), then S separates A−B from B−A for any Σ₁ A,B (disjoint or not).
Proof. Given A,B, Theorem 5 gives disjoint Σ₁ A'⊇A−B, B'⊇B−A. By hypothesis some F separates A' from B'. Since A−B⊆A' and B−A⊆B', that same F separates A−B from B−A. ∎
So the two readings of "Rosser system for sets" — separates disjoint pairs vs separates all differences — coincide. n‑ary lift: all of this holds for Σ₁ relations of any arity n>1 (p. 85, "the reader can easily verify this").
Part X — The payoff: why ω‑consistency is a "metamathematically weaker" assumption
You had the right instinct but lacked the vocabulary. Here is the precise language, on three separate axes.
X.1 What "weaker assumption" means, formally
Hypothesis W is weaker than hypothesis Σ when Σ ⟹ W but W ⇏ Σ. The crucial consequence for theorems:
A theorem "
W⟹ incomplete" is logically stronger than "Σ⟹ incomplete", because it covers every systemΣcovers, plus more (all theW‑but‑not‑Σsystems). Weaker hypothesis ⇒ stronger, more general theorem.
"Metamathematically" is the qualifier that these are predicates about the system S, asserted in the metatheory — S is consistent / ω‑consistent / correct are all statements we make about S, none of them sentences of S. So "metamathematically weaker" = weaker as a metatheoretic condition on S.
X.2 The hierarchy, with the entailments spelled out
Three metamathematical conditions, strongest to weakest:
CORRECTNESS (soundness) every provable sentence is true in ℕ
⟹ (X.2a)
ω-CONSISTENCY no B(v): ∃vB(v) provable yet every B(m̄) refutable
⟹ (X.2b)
SIMPLE CONSISTENCY no sentence both provable and refutable
(X.2a) Correctness ⟹ ω‑consistency — straight from the definition. Suppose S is correct and, for contradiction, ω‑inconsistent via B(v): every B(m̄) refutable and ∃vB(v) provable. Refutable + correct ⟹ each B(m̄) false in ℕ ⟹ ∃v B(v) is false in ℕ ⟹ (correct) ∃vB(v) not provable — contradiction. So correct systems are automatically ω‑consistent.
(X.2b) ω‑consistency ⟹ simple consistency — even more immediately from the definition. If S were simply inconsistent it proves everything; then for any B(v), both ∃vB(v) and every ~B(m̄) are provable — i.e. S is ω‑inconsistent. Contrapositive: ω‑consistent ⟹ simply consistent. In other words ω‑consistency has simple consistency built into it as a special/degenerate case — this is the sense in which "by its very definition" it is the stronger of the two, sitting above simple consistency.
X.3 Why the implications are strict (the gaps are real, not formal)
- Simple ⇏ ω (the lower gap). Witness from last session's Exercise 9:
P.A.+{~G}is simply consistent yet ω‑inconsistent — it proves∃v₂A(h̄,v₂)(the axiom~G) while inheriting every~A(h̄,m̄). So simple consistency genuinely permits the pathology ω‑consistency forbids. This is precisely the extra thing ω‑consistency buys, and precisely what Rosser learned to do without. - ω ⇏ correctness (the upper gap). ω‑consistency only forbids one shape of falsehood (a witnessed
∃whose instances are all refutable); it says nothing about, e.g., a false sentence with no such witnessing pattern. So an ω‑consistent system can still prove some false sentence and thus fail correctness. ω‑consistency is the purely syntactic residue of soundness — the exact fragment of "tells no lies" that the unrefutability argument actually consumes — not the whole of it.
X.4 Tying in your own observation — the two axes are independent
You already noticed a different weakening: "all true Σ₀ provable" is far weaker than "all provable sentences true." That is correct and it is a separate axis from the consistency axis. A naïve incompleteness proof leans on correctness in two places; Smullyan/Rosser weaken each independently:
| where correctness was used | naïve hypothesis | weakened to | axis |
|---|---|---|---|
| get the sets enumerated/represented | "all provable are true" (full soundness) | all true Σ₀ provable (one direction, Σ₀ only) + then ω‑cons (Gödel) | expressibility axis |
| make the diagonal unrefutable | full soundness | ω‑consistency (Gödel) → simple consistency (Rosser) | consistency axis |
- The Σ₀ axis is weaker because it (i) restricts to the bottom class Σ₀, and (ii) asks only the provability‑of‑truths direction, not the truth‑of‑provables direction (the dangerous one).
- The consistency axis is the X.2 chain: full soundness ⟹ ω‑consistency ⟹ simple consistency, each strict.
Rosser's contribution is entirely on the consistency axis (ω → simple), purchased with the structural Ω₄/Ω₅ demand. The Σ₀ axis is untouched — Theorem R still assumes "all Σ₁ enumerable" (equivalently, via Cor 1, "all true Σ₀ provable").
One‑paragraph answer, if you want the compressed version: ω‑consistency is "metamathematically weaker" than correctness because it is entailed by correctness but does not entail it (X.2a, X.3‑upper): it is the thin syntactic slice of soundness that the unrefutability step actually needs, forbidding only the single configuration "∃vB provable while every B(m̄) refutable." It is stronger than simple consistency because simple inconsistency is a degenerate instance of ω‑inconsistency (X.2b), so ω‑consistency contains simple consistency plus a ban on the Exercise‑9 pathology. Rosser's ≤‑race re‑expresses that ban inside the arithmetic, so his sentence needs only the bottom of the chain — simple consistency.
Distinctions Ledger
| Confusion | One‑line resolution |
|---|---|
| Is Rosser strictly better than Gödel? | No — incomparable. Rosser weakens ω→simple consistency but adds "extension of Ω₄,Ω₅." Each covers systems the other misses. |
| Represent vs separate | Represent = exact two‑way (needed ω‑cons for R*). Separate = one‑way on each of A,B only; consistency‑free, and enough (Thm 2). |
| Where is consistency actually used? | Exactly once, Lemma 1 step 2 ("refutable ⟹ not provable"), plus once to collapse P*−R* to P*. Both simple. The separating formula and Lemma S use none. |
Why difference sets R₁−R₂, not R₁ itself? |
R₁−R₂ and R₂−R₁ are disjoint for any sets — disjointness is manufactured, so no consistency is needed to separate them. |
What does the ≤ in (∃z≤y) buy? |
It runs a numerical race between proof‑codes and refutation‑codes; whoever is first wins. This internalizes, syntactically, the promise ω‑consistency made externally. |
| What do Ω₄, Ω₅ contribute? | Ω₄ unpacks a bounded quantifier into a finite disjunction; Ω₅ gives the y≤n̄ ∨ n̄≤y case split. Together they let S prove the two halves of Exercise 4. |
Gödel G vs Rosser ρ unrefutability |
G unrefutable needs ω‑cons (blocks ∃yA(h̄,y) provable + all instances refutable). ρ unrefutable needs only simple cons — the race forbids a self‑preceding refutation. |
| "ω‑consistency weaker" — weaker than what? | Weaker than correctness (soundness): correctness ⟹ ω‑cons, not conversely. Stronger than simple consistency. It is the middle of the chain. |
| Why "metamathematically"? | Consistency/ω‑cons/correctness are predicates about S asserted in the metatheory, not sentences of S. |
| Two independent weakenings? | Yes: the Σ₀ axis ("all true Σ₀ provable" ≪ soundness) and the consistency axis (soundness ⟹ ω ⟹ simple). Rosser moves only the second. |
Self‑Test
Q1. Rosser reduces incompleteness to separating R* from P*. At which single point does any consistency assumption enter, and which flavor?
answer
Lemma 1, step 2: "F(n̄) refutable ⟹ F(n̄) not provable," which is simple consistency. (Also used once to note P*∩R*=∅.) The separating formula and Lemma S are consistency‑free.
Q2. Why is Lemma S stated for the differences R₁−R₂, R₂−R₁ rather than for R₁, R₂?
answer
Because R₁−R₂ and R₂−R₁ are disjoint for any sets — the construction manufactures disjointness, so no consistency is needed. Only when S is simply consistent do the differences collapse back to R*, P* (Theorem 4).
Q3. In Exercise 4 Part 1, exactly where are Ω₄ and Ω₅ used?
answer
Ω₅ gives the exhaustive case split y≤n̄ ∨ n̄≤y. Ω₄ unpacks y≤n̄ into y=0̄∨…∨y=n̄, so the finitely many refutations ~F₂(k̄) (k≤n) discharge the antecedent on the low side.
Q4. Both Gödel's G and Rosser's ρ are unprovable from simple consistency. Where do they diverge, and why?
answer
Unrefutability. G's needs ω‑consistency (to block ∃yA(h̄,y) provable while all ~A(h̄,m̄) provable). ρ's needs only simple consistency: the (∃z≤y) race makes a refutation of ρ require a refutation‑witness preceding every proof‑witness of itself, which simple consistency already forbids.
Q5. State precisely why "correctness ⟹ ω‑consistency" and "ω‑consistency ⟹ simple consistency," each from the definitions.
answer
Correct + every B(m̄) refutable ⟹ every B(m̄) false ⟹ ∃vB false ⟹ (correct) ∃vB unprovable — so ω‑inconsistency is impossible. And simple inconsistency proves everything, instantly giving the ω‑inconsistent pattern — so ω‑consistent ⟹ simply consistent.
Q6. Give the concrete witness that "simple consistency ⇏ ω‑consistency," and name where we built it.
answer
P.A.+{~G} (Exercise 9, 07‑31 session): simply consistent because P.A.⊬G, but ω‑inconsistent because it proves ∃v₂A(h̄,v₂) (=~G) while inheriting every ~A(h̄,m̄).
Q7. Why is Theorem R incomparable to (not stronger than) Ch. V's Theorem A?
answer
R weakens the consistency hypothesis (ω → simple) but adds a structural one (must prove Ω₄,Ω₅). A system ω‑consistent but not proving Ω₄/Ω₅ is covered by A not R; one simply consistent and proving them is covered by R not A. Neither hypothesis implies the other.
References & cross‑links
| Imported result | Used in | Source |
|---|---|---|
P*, R* definitions; E_n(n̄); represents vs enumerates; Def 1 (H(h̄) provable ⟺ h∈P*) |
Parts II, III | 07‑29, 07‑30 |
Theorem 1′ (represent R* + consistent ⟹ incomplete) — the thing Ch. VI Thm 1 strengthens |
Part III | 07‑30 |
| "all true Σ₀ provable ⟹ all Σ₁ sets enumerable" | Parts IV (Thm 3), V | 07‑31 Theorem B* |
| Ω₄, Ω₅ schemes (and (R)=Ω₁–Ω₅) | Parts II, IV, V | 07‑31 glossary/Prop 3–5 |
simple / ω‑consistency definitions; Exercise 9 (P.A.+{~G} simply cons but ω‑incons) |
Parts VI, X | 07‑29, 07‑31 Part IX |
Gödel G=∀v₂~A(h̄,v₂); two‑strength split (unprovable←simple, unrefutable←ω) |
Part VI, X.4 | 07‑30 Theorem 3 |
Book span this session: Smullyan, Gödel's Incompleteness Theorems, Ch. VI, pp. 75–85 (headline Theorem R + Cors 1–3; §1 Thm 1, Lemma 1, Thm 2, Ex 1–2; §2 Ex 3–6, Lemma S, Thm 3; §3 Thm 4 + Rosser's sentence; §4 Gödel vs Rosser; §5 Thm 5/6, Ex 10, the n‑ary lift).
What's ahead
- Chapter VI exercises still open as threads: Ex 7 (a relation‑enumerability result "needed in the next chapter"), Ex 8 (separation with an explicit
ψ), Proposition S′ (the general separation proposition, of which Ex 3/4/6 are the pieces), Ex 10–then‑ary Theorem 6/Corollary lift. - 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). - Next chapter builds on Ex 7 — the Rosser machinery (separation of disjoint Σ₁ relations) is the tool there.
Prior session files: 07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 · 08‑03 (this file).
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
第六章:罗瑟系统(第75–85页)——仅由简单一致性推出不完备性
新的一章。第五章给出了哥德尔的第二个证明:由ω一致性(加上“所有真Σ₀句子可证”)推出不完备性。罗瑟[1936]把假设进一步减弱为简单一致性,代价是增加一个结构要求(系统必须证明Ω₄、Ω₅),并利用证明的≤次序构造一个更巧妙的不可判定句子。本次记录从头到尾重构这条思路,然后回答一直悬而未决的概念问题:究竟在什么意义上,ω一致性是一个“在元数学上较弱”的假设?(见第十部分,那是本次的收获。)
阅读次序遵循逻辑主线,不总是遵循书中的页码次序。
第0部分——一句话概括的转变,以及为何有所代价
上一章的主要结论(定理A):可公理化+所有真Σ₀句子可证+ω一致 ⟹ 不完备。罗瑟的主要结论:
定理R。 Ω₄和Ω₅的每个简单一致的可公理化扩张,只要其中所有Σ₁集合都可枚举,就不完备。
斯穆里安在附注(第76页)中说明,这一交换并非严格的改进,而是一次横向变化:
| 定理A(哥德尔,第五章) | 定理R(罗瑟,第六章) | |
|---|---|---|
| 一致性假设 | ω一致 | 简单一致 ← 更弱(收益) |
| 结构假设 | 除Σ₀完备性外无额外要求 | 必须证明Ω₄、Ω₅ ← 额外要求(代价) |
| 判断 | 强度不可比较——彼此互不蕴涵 |
所以,“罗瑟改进了哥德尔”只说对了一半。罗瑟减弱了一致性假设(在元数学上有意思的那条轴),却增加了一个结构假设。一个ω一致但不证明Ω₄/Ω₅的系统适用A、不适用R;一个仅仅简单一致却能证明它们的系统适用R、不适用A。下面的推论2,就是绍恩菲尔德[1967]所称的哥德尔—罗瑟不完备定理。
定理R的推论(每条只是为具体系统核对假设):
| 陈述 | 推出理由 | |
|---|---|---|
| 推论1 | Ω₄、Ω₅的简单一致可公理化扩张,若所有真Σ₀句子可证,就不完备 | “所有真Σ₀句子可证 ⟹ 所有Σ₁集合可枚举”(第五章),代入定理R |
| 推论2 | (R)的每个简单一致可公理化扩张都不完备 | (R)=Ω₁–Ω₅,证明Ω₄、Ω₅,且Σ₀完备(定理B*) |
| 推论3 | P.A.若简单一致,就不完备 | P.A. ⊇ (R) |
第一部分——目标与归约链
目标。 只假设P.A.简单一致,证明其不完备(不使用ω一致性)。
上一章把不完备性归约为表示R*(或P*)。ω一致性用在表示这一步(可枚举→可表示)。罗瑟的洞见是:不去表示R*,而是把R*与P*分离。分离的代价更低——从不需要ω一致性,只需要Ω₄/Ω₅及Σ₀完备性——而简单一致性在最后一步完成证明。
归约流程(第六章的定理编号):
定理1: H表示一个包含R*、与P*不交的超集 ⟹ H(h̄)不可判定 [无需一致性——一致性可导出]
引理1: F把R*与P*分离 + S简单一致 ⟹ H表示这样的超集
定理2: F把R*与P*分离 + S简单一致 ⟹ S不完备 [= 引理1 ∘ 定理1]
↑ 定理2 = 先引理1、再定理1(见下方组装图)
习题3/4:≤次序技巧——可证与可反驳的两半
引理S: Ω₄、Ω₅可证 ⟹ 对可枚举R₁、R₂,R₁−R₂可与R₂−R₁分离 [无需一致性]
定理3: Ω₄、Ω₅的扩张,且所有真Σ₀句子可证 ⟹ 集合的罗瑟系统
定理4: 简单一致 + P*、R*可枚举 + Ω₄、Ω₅可证 ⟹ 不完备 [= 对P.A.的定理R]
承重的观察(请记住):简单一致性是一个假设,只在两个位置兑现——差集的化简,以及引理1中的“F(n̄)可反驳 ⟹ 不可证”。上游的一切——分离公式、习题3/4、引理S、差集——都在完全没有一致性假设的情况下构造。这就是罗瑟能只用简单一致性的结构原因:他预先把所有实质工作放进无需一致性的分离过程,最后才兑现两项最低限度的检查。
各部分如何衔接——组装定理4
上面的列表是零件箱;下面说明如何把它们装起来。定理4(=定理R)是唯一的成品——其余都为它提供输入。两条链在此汇合:
输入链α——分离器 输入链β——引擎(=定理2)
习题3/4(≤竞赛的两半) 定理1 ─┐
│ ├─▶ 定理2
引理S ⟹ H把 引理1 ─┘
R*−P*与P*−R*分离 │
└───────────────┐ ┌─────────┘
▼ ▼
定 理 4 ⟹ 定理R
(由简单一致性推出P.A.不完备)
支线(一般化表述,不在通向定理4的路径上):
引理S + Σ₀完备性 ⟹ 定理3 ⟹ (R)、(Q)、P.A.是罗瑟系统
定理4的三个假设——H1简单一致,H2 P*、R*可枚举,H3 Ω₄、Ω₅可证——在三个阶段中使用:
| 阶段 | 现在得到什么 | 由什么建立 | 用到的假设 |
|---|---|---|---|
| 1 · 分离器 | H把R*−P*与P*−R*分离 |
引理S ← 习题3/4 | H2+H3——无需一致性 |
| 2 · 化简 | H把R*与P*分离 |
R*∩P*=∅ ⟹ R*−P*=R*、P*−R*=P* |
H1(应用于阶段1) |
| 3 · 引擎 | H(h̄)不可判定 ⟹ 不完备 |
定理2(应用于阶段2) | 再次使用H1(在引理1内部) |
你指出的那个细节——定理2并非不可分解。阶段3藏着前面的两个部分:
定理2(输入:“H把R*与P*分离” + H1)
│
├─ 引理1:分离 ─▶ 表示一个与P*不交的超集A⊇R* ← 使用H1
│
└─ 定理1:该表示 ─▶ H(h̄)不可判定 ← 不使用假设(它导出一致性)
因此,从主要结论一路下探到基础的完整路径是:
定理R ═ 定理4
├─ 阶段1 → 引理S → 习题3/4 [Ω₄、Ω₅+枚举;无需一致性]
├─ 阶段2 → 差集化简 [H1]
└─ 阶段3 → 定理2 → {引理1[H1],定理1[—]}
一致性使用账本(完整记录)。H1是一个假设,在两处兑现——阶段2的化简,以及引理1中的“可反驳 ⟹ 不可证”。H2、H3各用一次,都在阶段1的引理S中。定理1和分离公式不使用任何一致性假设。整个≤机制(习题3/4→引理S)无需一致性即可运行;一致性只做两项收尾工作。(这与定理4证明表第1、5行的记账相同,现在改为逐层下探的展示。)
每个部分的作用——架构一览。每一行都回答你问的问题:它为定理4做了什么?
| 部分 | 一句话说明任务 | 是否位于通向定理4的路径上? |
|---|---|---|
| 习题3/4 | ≤竞赛——H可证与可反驳的两半 |
✓ 引理S的原料 |
| 引理S | 构造分离器H,分离差集——无需一致性 |
✓ 阶段1 |
| 定理1 | 不可判定性核心:“表示一个包含R*、与P*不交的超集” ⟹ “H(h̄)不可判定” |
✓(定理2内部) |
| 引理1 | 升级器+一致性使用者:“把R*与P*分离”(+H1) ⟹ 那种表示 |
✓(定理2内部) |
| 定理2 | 引擎 = 引理1之后接定理1:分离器(+H1) ⟹ 不完备 | ✓ 阶段3 |
| 定理4 | 组装阶段1(引理S)+阶段2(化简、H1)+阶段3(定理2) | ═ 定理R |
| 定理3 | 同级分支,而非输入项:把同一个引理S应用于所有不交的Σ₁集合对——后续章节(不可判定性、不可分离性)可复用的引擎 | ✗ 不属于本证明 |
| 定理5 | 点集层面的骨架:把任意Σ₁集合对细化成其差集的不交Σ₁超集 | ✗ 不在路径上 |
具体说说定理3(之前作用显得模糊的那一块):它不是定理4内部的一步。定理4对R*、P*这一对集合运行引理S;定理3对每一对不交Σ₁集合运行同一个引理S。它们是共享同一个来源(引理S)的同级分支,彼此都不调用对方。定理3的任务是命名一般性质(“集合的罗瑟系统”),并确认具体系统具备该性质(各推论),而不是推动不完备性证明。
第二部分——可引用的术语表
沿用此前记录:E_n = 哥德尔数为n的公式(有一个自由变量v₁);E_n(n̄)是其自应用;P* = {n : E_n(n̄) provable},即自应用可证的编号集合,R* = {n : E_n(n̄) refutable},即自应用可反驳的编号集合。
- (在
S中)表示A:(∀n)[ S⊢H(n̄) ⟺ n∈A ]。双向、精确。(第五章:要为R*获得它,需要ω一致性。) - (以二元公式
A(v₁,v₂))枚举A:n∈A ⟹ ∃m S⊢A(n̄,m̄)(条件1),且n∉A ⟹ ∀m S⊢~A(n̄,m̄)(条件2)。单向、代价低;仅由Σ₀完备性即可得到。 - (以
F(v₁))把A与B分离:n∈A ⟹ S⊢F(n̄)(可证),且n∈B ⟹ S⊢~F(n̄)(可反驳)。对A∪B外的n不作任何断言。 - (以
F(v₁,…,vₙ))把关系R₁与R₂分离:逐实例应用的n元版本。 - 见证。当
A(x,y)枚举P*时:如果A(x̄,ȳ)为真,则y是x可证的见证。对称地,B(x,y)枚举R*;一个B见证证实x可反驳。 - 差集。
R₁−R₂ = {x : R₁(x) ∧ ¬R₂(x)}。注意,对任意R₁、R₂,R₁−R₂与R₂−R₁都不交——不交性已经内置,无需一致性。这是整个方法的枢纽。 - 集合的罗瑟系统——每一对不交Σ₁集合在
S中都可分离。n元关系的罗瑟系统——对不交Σ₁n元关系作同样要求。罗瑟系统——对每个n都满足后一性质。 - Ω₄
v₁≤n̄ ≡ (v₁=0̄∨…∨v₁=n̄),Ω₅v₁≤n̄ ∨ n̄≤v₁(线性)。(沿自第五章;(R)=Ω₁–Ω₅,(Q)、P.A.都证明这两者。)正是这两者允许证明“按y≤n̄与n̄≤y分情况推理”,以及“把有界量词展开为有限析取”——≤技巧所需要的两个动作。 - 简单一致——没有句子既可证又可反驳。ω一致——不存在这样的
B(v):∃vB(v)可证,而每个B(m̄)都可反驳。(第十部分分析这条定义链。)
第三部分——§1 罗瑟之后的抽象不完备性
第六章定理1——只需表示一个包含R*且与P*不交的超集
→ 对定理4的作用:不可判定性核心。输入 = “H表示一个包含R*且与P*不交的超集A”;输出 = “H(h̄)不可判定”。它是定理4的最后一步(在阶段3的定理2内部),不使用一致性,甚至能导出一致性。
任务。把第五章的“表示R*”弱化为“表示任意满足A ⊇ R*且A∩P*=∅的超集”,仍可得到不可判定句子,并且免费得到一致性。
陈述。如果H(v₁)在S中表示集合A,且R*⊆A、P*∩A=∅,则H(h̄)在S中不可判定,其中h = H(v₁)的哥德尔数。
证明。
| # | 断言 | 理由 |
|---|---|---|
| 1 | S⊢H(h̄) ⟺ h∈A |
H表示A,取实例n:=h |
| 2 | S⊢H(h̄) ⟺ h∈P* |
P*的定义(H(h̄)=E_h(h̄)) |
| 3 | h∈A ⟺ h∈P* |
1 ∧ 2 |
| 4 | h∉P*且h∉A |
3+A∩P*=∅(不能同时属于两者 ⟹ 两者都不属于) |
| 5 | H(h̄)不可证 |
由2,把4(h∉P*)转换过来 |
| 6 | h∉R* |
4(h∉A)+R*⊆A |
| 7 | H(h̄)不可反驳 |
6+R*的定义(H(h̄)可反驳 ⟺ h∈R*) |
| 8 | H(h̄)不可判定 |
5 ∧ 7 ∎ |
附注——一致性是导出的,并非假设的。假设R*⊆A与P*∩A=∅强制得到R*∩P*=∅。但R*∩P*≠∅意味着某个句子既可证又可反驳。所以这些假设蕴涵简单一致性,无须另列。(这已经超过第五章定理1′,后者还必须假设一致性。)
习题1(对偶)。在S中表示一个包含P*且与R*不交的超集,同样得到不完备性——镜像证明,转而反驳而非证明对角句子。
第六章引理1——分离升级为表示一个超集(一致性在此进入)
→ 对定理4的作用:升级器,也是两次兑现一致性的其中一次。输入 = “F把R*与P*分离”+简单一致性;输出 = “F表示一个与P*不交的超集A⊇R*”——恰是定理1的输入。它是阶段3的定理2的前半段。
陈述。如果F(v₁)在S中把A与B分离,且S简单一致,那么F表示某个与B不交的超集A'⊇A。
证明。令A' = {n : S⊢F(n̄)}(F实际表示的集合)。
| # | 断言 | 理由 |
|---|---|---|
| 1 | A ⊆ A' |
n∈A ⟹ S⊢F(n̄)(分离的可证一半) ⟹ n∈A' |
| 2 | B ∩ A' = ∅ |
n∈B ⟹ S⊢~F(n̄)(可反驳一半);简单一致性 ⟹ S⊬F(n̄) ⟹ n∉A' |
A'⊇A,A'∩B=∅。∎ 这第2步是全章唯一使用一致性的地方。
第六章定理2——归约目标
→ 对定理4的作用:整个引擎 = 引理1之后接定理1。输入 = R*与P*的分离器(+简单一致性);输出 = 不完备性。在定理4中,这是阶段3,使用阶段1–2生成的分离器。
陈述。如果F在S中把R*与P*分离,且S简单一致,那么S不完备(对角句子F(f̄)不可判定)。
证明。引理1(A:=R*、B:=P*) ⟹ F表示一个包含R*、与P*不交的超集 ⟹ 定理1 ⟹ 不可判定。∎
所以,现在整个问题是:在P.A.中把
R*与P*分离——分离本身无需一致性。这正是罗瑟所做的(斯穆里安,第78页)。习题2是其对偶(把P*与R*分离)。
第四部分——§2 一般分离原则(≤技巧)
罗瑟把R*与P*分离,是一个一般事实的特例:在证明Ω₄、Ω₅的系统中,任意两个不交的Σ₁集合都可分离。其引擎是一个单独的公式,通过哪个见证先出现来决出胜负。
决胜机制的缩影——习题3与4
令A(x,y)枚举P*(可证性的见证),B(x,y)枚举R*(反驳的见证)。罗瑟把R*与P*分离的公式是:
H(x) := ∀y[ A(x,y) ⊃ (∃z≤y) B(x,z) ]——“x的每一个证明,都有一个不晚于它出现的x的反驳与之对应。”
习题3(语义热身,谈真)。对σ := ∀y[F₂(y) ⊃ (∃z≤y)F₁(z)]:如果F₁(n̄)为真,而每个F₂(m̄)(m≤n)都为假,那么σ为真(在n以下前件不成立,在n处及以上见证z=n起作用)。这是纯算术的骨架,尚未涉及可证性。
习题4(真正的引理,谈可证性,需要Ω₄、Ω₅)。同一个σ,现在把F₁、F₂分别对应为B、A:
第1部分——可证的一半。如果S⊢F₁(n̄),且对每个m≤n都有S⊢~F₂(m̄),则S⊢σ。
关于y的情况 |
论证 | 使用 |
|---|---|---|
n̄≤y |
F₁(n̄)可证,且n̄≤y ⟹ (∃z≤y)F₁(z)(见证z=n̄) ⟹ 后件成立 |
— |
y≤n̄ |
Ω₄:y=0̄∨…∨y=n̄;每个S⊢~F₂(k̄)(k≤n) ⟹ S⊢~F₂(y) ⟹ 前件不成立 ⟹ 蕴涵成立 |
Ω₄ |
| 合并 | Ω₅(y≤n̄ ∨ n̄≤y)保证两种情况穷尽;得到∀y |
Ω₅ |
为何n是一个阈值,以及m≤n从哪里来。见证n(来自S⊢F₁(n̄))把每个y划进两个区间,各自依靠不同前提:
- y ≥ n(阈值处及以上):位于n的F₁见证填入后件(∃z≤y)F₁(z)——因为n≤y,所以z=n̄可用。蕴涵凭其右边成立;这里不需要任何关于F₂的信息。
- y ≤ n(阈值以下):由Ω₄,y∈{0̄,…,n̄},所以用S⊢~F₂(y)消掉前件F₂(y)——而只对这些值才需要它,即仅需m≤n。
所以,m≤n不是我们额外施加的假设,而恰好是落入“消掉前件”这一情况的y的范围。在n以上,单个F₁见证已足以让每个蕴涵成立,无须任何F₂事实。(在R*−P*的应用中,x∉P*给出了对 所有 m,A(x̄,m̄)都可反驳(链2),所以它超额满足m≤n的要求——只有在一般的决胜情形中,你只能控制到第一个见证为止的反驳时,这个界才起限制作用。)
第2部分——可反驳的一半。如果S⊢F₂(n̄),且对每个m≤n都有S⊢~F₁(m̄),则S⊢~σ。
| # | 断言 | 理由 |
|---|---|---|
| 1 | 见证y=n̄:S⊢F₂(n̄) |
假设 |
| 2 | S⊢(∀z≤n̄)~F₁(z) |
Ω₄把z≤n̄展开为z=0̄∨…∨z=n̄;每个S⊢~F₁(k̄) |
| 3 | S⊢ F₂(n̄) ∧ (∀z≤n̄)~F₁(z) = S⊢∃y[F₂(y)∧(∀z≤y)~F₁(z)] = S⊢~σ |
1、2 |
现在与R*/P*对应(取F₂=A、F₁=B,于是σ = H(x)):
x满足…… |
从隶属关系得到、我们拥有的前提 | 习题4需要的前提(⊆我们拥有的) | ⟹ | 因而H…… |
|---|---|---|---|---|
x∈R*、x∉P* |
B(x̄,n̄)可证(由∈R*,对某个n)+对所有m,A(x̄,m̄)可反驳(由∉P*) |
第1部分:B(x̄,n̄)可证+对m≤n,A(x̄,m̄)可反驳——m≤n范围是“所有m”的子集,所以✓ |
S⊢H(x̄) |
在R*上可证 |
x∈P*、x∉R* |
A(x̄,n̄)可证(由∈P*,对某个n)+对所有m,B(x̄,m̄)可反驳(由∉R*) |
第2部分:A(x̄,n̄)可证+对m≤n,B(x̄,m̄)可反驳——m≤n范围是“所有m”的子集,所以✓ |
S⊢~H(x̄) |
在P*上可反驳 |
中间的箭头就是你点出的那一步:“对所有m可反驳”(隶属关系所给的)⟹“对m≤n可反驳”(习题4所用的全部),因为{m : m≤n} ⊆ {all m}。我们拥有的比需要的更多;多出来的无妨。
读表——把前提误作分类讨论的陷阱。每一行的两项是习题4的两个前提,同时成立,并非二选一的两个分支。它们来自两种不同的隶属关系:B(x̄,n̄)可证来自x∈R*(存在反驳见证——枚举条件1);每个A(x̄,m̄)可反驳来自x∉P*(没有证明 ⟹ 每个证明实例均被反驳——条件2)。它们同时输入第1部分。“n̄≤y ⟹ 用B,y≤n̄ ⟹ 用A”的分支发生在第1部分的证明内部(就在上面的分类表中):对每个y,证明选用适合的前提,但要覆盖所有y,必须同时拥有两者。前提共存;证明分情况使用它们。(这两项事实——在R*中、不在P*中——恰恰说明为何使用差集R*−P*。)
所以,只要R*与P*不交,H就把它们分离。但H从未假定这两个集合不交;它只针对每个单独的x,使用x位于某一差集而非另一差集的事实。这就是为何准确的一般陈述谈的是差集:
引理S(分离引理)——无需一致性的核心
→ 对定理4的作用:分离器的构造者——阶段1。输入 = Ω₄、Ω₅(H3)+R*、P*可枚举(H2);输出 = “H把差集R*−P*、P*−R*分离”,无需一致性。它制造的正是阶段3的定理2所使用的那个H。
(i) 整体策略
根据定理2,我们需要一个在R*上可证、在P*上可反驳的公式H;这就是“把R*与P*分离”的全部含义。罗瑟构造的全部逻辑就是下面这条从上到下的链。先读这条链;后面的表只是把箭头补全。
目标(定理2):构造把R*与P*分离的H
即 n∈R* ⟹ S⊢H(n̄),且 n∈P* ⟹ S⊢~H(n̄)
│
融贯性检查:如果某个n ∈ R* ∩ P*呢?
分离将同时要求 S⊢H(n̄) 和 S⊢~H(n̄)
= H(n̄)既可证又可反驳 = 不一致。
⟹ “把R*与P*分离”只有在R* ∩ P* = ∅时才是融贯的要求……
而这一空交集就是简单一致性。
(注意——这一格是动机,不是证明步骤:它没有建立R*∩P*=∅。
它只说明,分离要求必须在某处由一致性支付代价。
这笔债被推迟,最终在定理4收尾处的阶段2兑现:
假设H1 ⟹ R*∩P*=∅ ⟹ 差集化简为R*、P*。)
│
罗瑟的做法:不在开头加上一致性,改为证明关于差集、
无需一致性的陈述:
│
引理S给出:H把 R*−P* 与 P*−R* 分离
├(事实1)对任何集合,R*−P*与P*−R*都不交——免费。
├(事实2)“n ∈ R*−P*”逐字就是触发习题4
│ 可证一半的前提 ⟹ S⊢H(n̄)
└(事实3)“n ∈ P*−R*”逐字就是习题4可反驳一半的前提
⟹ S⊢~H(n̄)
使用Ω₄、Ω₅(在习题4内部);不使用一致性。
│
定理4收尾:现在加入简单一致性 ⟹ R* ∩ P* = ∅
⟹ R*−P* = R* 且 P*−R* = P*
⟹ 引理S现在字面上就是“H把R*与P*分离”
⟹ 输入定理2 ⟹ S不完备。
用三段文字展开这条主线——这正是之前不清楚的部分:
(a) 是的——我们确实想要不交性,理由恰是如此。“把A与B分离”要求F在A上可证、在B上可反驳。如果哪怕只有一个n在A∩B中,两条条件就发生冲突:它们要求F(n̄)同时可证且可反驳——这就是不一致。所以,分离甚至只有对不交的A、B才是一个融贯的要求;若有交叠,只有已经不一致的系统才能满足它。有两条出路:(i) 一开始就假设R*、P*不交——但这就是假设简单一致性;(ii) 只在不交性免费成立的地方提出分离要求。罗瑟选择(ii),所以他的构造本身无须一致性。
(b) 差集免费提供不交性——而且没有损失。对任意集合,R*−P*与P*−R*都不交(前者的成员在P*之外,后者的成员在P*之内,两者不可能共享元素)。所以,把它们分离永远是融贯要求。而且没有牺牲什么:一旦我们确实知道S简单一致,R*∩P*=∅就使R*−P*精确地化简回R*(定理4第2行)。差集是一副脚手架,一致性到位后就会消失。
(c) 不起眼的妙处:差集条件就是触发条件。对照两条枚举条件展开隶属关系(B枚举R* = 反驳见证,A枚举P* = 证明见证):
n∈R*−P*≡n∈R*(条件1:存在反驳见证,S⊢B(n̄,k̄))且n∉P*(条件2:每个证明实例均被反驳,对所有m有S⊢~A(n̄,m̄))。
这两项事实逐字就是习题4第1部分的两个前提。所以,无须额外添加什么,就得到n∈R*−P* ⟹ S⊢H(n̄)。属于差集并不是导致假设成立——它就是假设。(对称地,n∈P*−R*就是第2部分的前提。)这一等同就是≤竞赛能够不用一致性的全部原因:(∃z≤y)通过谁在数值上更早来裁定证明与反驳的胜负,在句法上完成上一章ω一致性在语义上完成的工作。
(ii) 陈述与详细证明
陈述。如果Ω₄、Ω₅的全部公式在S中可证,而且R₁、R₂在S中可枚举——设B(x,y)枚举R₁、A(x,y)枚举R₂——那么:
H(x) = ∀y[ A(x,y) ⊃ (∃z≤y) B(x,z) ]在S中把R₁−R₂与R₂−R₁分离。
(对于不完备性的应用,R₁=R*、R₂=P*;R*、P*以及“枚举”可追溯至07‑29序篇和07‑30。)
证明——可证的一半(n ∈ R₁−R₂ ⟹ S⊢H(n̄)):
| # | 断言 | 理由 |
|---|---|---|
| 1 | n∈R₁ ⟹ 对某个k有S⊢B(n̄,k̄) |
B枚举R₁,条件1(某个见证可证) |
| 2 | n∉R₂ ⟹ 对每个m有S⊢~A(n̄,m̄)(特别地,对所有m≤k) |
A枚举R₂,条件2(非成员 ⟹ 每个实例可反驳) |
| 3 | S⊢H(n̄) |
习题4第1部分,取F₁=B、F₂=A、指标k:第1–2行恰为其两个前提(Ω₄、Ω₅在那里使用) |
证明——可反驳的一半(n ∈ R₂−R₁ ⟹ S⊢~H(n̄)),镜像:
| # | 断言 | 理由 |
|---|---|---|
| 1 | n∈R₂ ⟹ 对某个k有S⊢A(n̄,k̄) |
A枚举R₂,条件1 |
| 2 | n∉R₁ ⟹ 对所有m≤k有S⊢~B(n̄,m̄) |
B枚举R₁,条件2 |
| 3 | S⊢~H(n̄) |
习题4第2部分,取F₁=B、F₂=A、指标k |
没有一行引用一致性。仅有的非逻辑输入是四条枚举条件和Ω₄/Ω₅(藏在习题4中)。∎
一句话回顾各自作用。A标记证明,B标记反驳;H说“我的每个证明y都有一个反驳z≤y与之对应”。在R₁−R₂上,有反驳而完全没有证明,所以H平凡地成立(可证);在R₂−R₁上,有证明而没有反驳,所以H在那个证明处不成立(可反驳)。≤只在交叠R₁∩R₂中才有影响——差集排除了那里,因此我们从不需要查看那里。
- 习题5。从习题4导出引理S——恰好是从差集读出第1–2部分(上面的证明表就是这一推导)。
- 习题6。检查对偶公式
∃y[B(x,y) ∧ (∀z≤y)~A(x,z)]也把R₁−R₂与R₂−R₁分离。当A、B枚举不交集合时,A−B=A、B−A=B,所以它直接把这两者分离。
第六章定理3——罗瑟系统存在
→ 作用(同级分支,而非输入项——但绝非无用):定理3不是定理4证明中的引理——删掉它,P.A.的不完备性仍然成立(定理4直接对R*、P*运行引理S)。它增加的是一般性:同一个引理S分离每一对不交Σ₁集合,于是不完备性显现为系统整体分离能力的一个实例。正是这种一般性支撑推论2(所有扩张),以及后续章节的不可判定性/不可分离性结果。见本节末尾的“为什么证明一般版本?”。
必须证明什么。“S是集合的罗瑟系统”意味着:每一对不交Σ₁集合A、B(不只是R*、P*)在S中都可分离。所以,固定任意一对不交Σ₁集合,构造一个分离器。
引理S留下的缺口——以及“所有Σ₁集合可枚举”填在哪里。引理S把A−B与B−A分离,但仅当A、B在S中可枚举——这是它的先决条件。是Σ₁是集合作为集合的性质;在S中可枚举是关于S能证明什么的性质——这是两回事,不会自动关联。连接它们的桥梁来自第五章:所有真Σ₀句子可证 ⟹ 每个Σ₁集合在S中可枚举(07‑31枚举步骤2a)。这就是“所有Σ₁集合可枚举”的全部作用:把任意Σ₁集合对升级成引理S能够接受的集合对。
| # | 步骤 | 理由 |
|---|---|---|
| 1 | 固定任意不交Σ₁集合A、B |
“集合的罗瑟系统”必须覆盖这些集合 |
| 2 | A、B在S中可枚举 |
假设所有真Σ₀句子可证 ⟹ 所有Σ₁集合可枚举(第五章的桥梁)——所问的因素 |
| 3 | H把A−B与B−A分离 |
引理S:Ω₄、Ω₅可证(假设)+A、B可枚举(2) |
| 4 | A−B=A、B−A=B |
A、B不交(1) |
| 5 | H把A与B分离 |
3+4 |
| 6 | ∴ S是集合的罗瑟系统 |
1–5对任意不交Σ₁集合对成立 ∎ |
注意,这两个假设接在不同层级:Ω₄、Ω₅和可枚举性都通过引理S输入第3步,而不交性在第4步起作用。原先一句话的版本把2→3→5压在一起,隐藏了第2步。
定理3。Ω₄、Ω₅的任何扩张,只要其中所有真Σ₀句子都可证,就是一个集合的罗瑟系统。 推论。(R)、(Q)、P.A.都是集合的罗瑟系统。
推论为何成立——每个系统都满足两个假设:它们证明Ω₄、Ω₅((R)的公理;根据第五章命题4/5,也是(Q)、P.A.的定理),而且它们Σ₀完备(定理B*)。所以定理3适用于这三个系统。
既然定理4本身已经证明P.A.不完备,为何还要证明一般的定理3?四个理由,没有一个是“这个证明需要它”,全都是“它是恰当的研究对象”:
- 它命名了本质性质。定理4表明,P.A.不完备是因为
R*与P*可分离。定理3表明,这并非这两个集合的偶然:P.A.能分离任意不交Σ₁集合对。不完备性成为一般能力的症候——它回答“罗瑟技巧为什么有效?”(因为该系统是一个罗瑟系统),而不只是说明它“确实有效”。 - 它支撑“所有扩张”的推论。推论2——(R)的每个简单一致可公理化扩张都不完备(哥德尔—罗瑟定理)——最简洁地表述为:(R)的扩张 ⟹ Σ₀完备 ⟹(定理3)罗瑟系统 ⟹ 不完备。对所有扩张的统一性,是关于分离能力的陈述(定理3的内容),而非定理4那种单一集合对的论证。
- 它是后续可复用的工具。习题7被标为“下一章需要”,并为关系建立分离。分离不交Σ₁集合/关系(=成为罗瑟系统),是后续结果背后的主要工具:理论的不可判定性(丘奇——没有算法判定定理性)、递归与有效不可分离性、本质不可判定性/不完备性。不完备性只是它第一个、最简单的应用。
- 它几乎免费。一般版本与特例用同一个引理S证明——不增加工作,就能覆盖更多。斯穆里安证明一次,收获不完备性实例(定理4)及上述一切。
所以,定理3不是这个证明的承重梁,而是这一方法的概念归宿以及其余理论赖以建立的工具。定理4把机制作用于R*、P*这一对集合,使一个句子不可判定;定理3就是这个机制。(这也解释了为何定理4把“P*、R*可枚举”列为假设:它们之所以可枚举,是因为可公理化性使它们成为Σ₁集合,而Σ₀完备性的桥梁使每个Σ₁集合都可枚举——与定理3全面使用的是同一座桥。)
第五部分——§3 罗瑟的不可判定句子(组装定理R)
第六章定理4——抽象引擎(定理R及推论1–3是它的特化)
陈述。设S简单一致,P*与R*可枚举,且Ω₄、Ω₅可证。则S不完备。
证明。
| # | 断言 | 根据(前面的哪个部分) | 该部分在做什么 |
|---|---|---|---|
| 1 | P*∩R*=∅ |
假设H1(简单一致性) | 第一次兑现一致性——使两集合不交 |
| 2 | R*−P*=R*、P*−R*=P* |
第1行 | 阶段2:把差集化简为原集合 |
| 3 | H把R*−P*与P*−R*分离 |
引理S+H2(可枚举)+H3(Ω₄、Ω₅) | 阶段1:无需一致性,构造分离器H |
| 4 | H把R*与P*分离 |
2+3 | 把化简输入引理S的输出 |
| 5 | H(h̄)不可判定 ⟹ 不完备 |
定理2 = 引理1(H1)之后接定理1 | 阶段3:引擎——引理1把“把R*与P*分离”变成“表示一个包含R*、与P*不交的超集”;定理1再把它变成“H(h̄)不可判定” ∎ |
每个假设的位置。H2(可枚举)与H3(Ω₄、Ω₅)各用一次,都在引理S内部(第3行)。H1(简单一致性)是一个假设,在两处兑现——第1行的化简,以及第5行内部的引理1。ω一致性从未出现。第一部分的分阶段组装图把同一路径画成树(定理4→定理2→引理1/定理1)。
定理R及推论1–3如何从定理4而来(特化阶梯)。先弄清方向:定理4是一般形式;下面每个结果都是它的特化(更窄、更具体),所以箭头方向为定理4 ⟹ 定理R ⟹ 推论1 ⟹ 推论2 ⟹ 推论3。为便于看清,把定理4的内容固定为对系统S的三个要求:
完整展开的定理4。如果
S(a)简单一致,(b)证明Ω₄、Ω₅,且(c)P*、R*在S中可枚举,那么S不完备。
下面每一级都原样保留(a)与(b)——它们已经很具体——并且只特化(c),把“P*、R*可枚举”换成更强、但更易于检查且蕴涵它的条件。所以表中的三列就是(a)/(b)/(c)。标为[沿用]的格子原样重复定理4的要求;[特化]是该级实际做工作的唯一位置。结论——S不完备——从不改变;只有到达(c)的路线变窄。
| 陈述 | (a)简单一致 | (b)证明Ω₄、Ω₅ | (c)P*、R*可枚举——本级如何获得它 |
|---|---|---|---|
| 定理4(核心) | 假设 | 假设 | 直接假设 |
| 定理R | [沿用] | [沿用](=“Ω₄、Ω₅的扩张”) | [特化]可公理化 ⟹ P*、R*是Σ₁集合(07‑31 §2b–2c);+所有Σ₁集合可枚举 ⟹ 这两个集合可枚举 |
| 推论1 | [沿用] | [沿用] | [特化]可公理化 ⟹ Σ₁;+所有真Σ₀句子可证 ⟹(第五章的桥梁)所有Σ₁集合可枚举 |
| 推论2 | [沿用] | [沿用]——由扩张 (R)提供 | [特化]可公理化+(R)是Σ₀完备的(定理B*) ⟹ 可枚举 |
| 推论3 | [沿用](P.A.唯一的假设) | [沿用]——P.A. ⊇ (R),证明它们 | [特化]P.A.可公理化+Σ₀完备 ⟹ 可枚举 |
纵览各列:(a)和(b)全是[沿用]——每一级都原封不动地继承它们——而(c)全是[特化],每一步都有一种不同的、更强、更具体的供给。那一列就是阶梯。
从上往下读,每一级都以一个更熟悉的假设交换一个抽象假设:“P*、R*可枚举” ⤳ “所有Σ₁集合可枚举” ⤳ “所有真Σ₀句子可证” ⤳ “扩张(R)” ⤳ “是P.A.”。这种逐层下降,就是陈述定理R及其推论的全部理由:定理4是引擎;定理R及推论1–3把它安装到越来越具体的系统上。(所以,组装图中“定理4=定理R”的简写意指“同一个引擎”——定理R只是在阶梯上下降一级,把它包装成可检查的形式。)
具体的罗瑟句子。令h = ∀y[A(v₁,y)⊃(∃z≤y)B(v₁,z)]的哥德尔数,则不可判定句子是:
ρ = ∀y[ A(h̄,y) ⊃ (∃z≤y) B(h̄,z) ]——“对于我的每个证明,都存在一个不晚于它的对我的反驳。”
第六部分——§4 哥德尔句子与罗瑟句子的比较
两者都是从同样的两个枚举器A(可证性,P*)和B(可反驳性,R*)构造的对角不动点。区别在于,不动点对自己的证明作了什么断言。
哥德尔G |
罗瑟ρ |
|
|---|---|---|
| 公式 | ∀y ~A(h̄,y) |
∀y[A(h̄,y) ⊃ (∃z≤y)B(h̄,z)] |
| 自指读法 | “没有我可证的见证”=“我不可证” | “我可证的每个见证,都被我可反驳的某个见证抢先” |
| 不可证需要 | 简单一致性 | 简单一致性 |
| 不可反驳需要 | ω一致性 | 简单一致性 |
| 差异原因 | 若G可反驳,则∃y A(h̄,y)可证,而所有~A(h̄,m̄)也可证——只有ω一致性排除它 |
ρ可反驳被≤竞赛阻止:反驳见证将必须早于自身;简单一致性就足够 |
对偶罗瑟句子(习题6的公式,在自身编号b处对角化):
ρ' = ∃y[ B(b̄,y) ∧ (∀z≤y)~A(b̄,z) ]——“我有一个反驳,早于我的任何证明。”在简单一致性下同样不可判定。
要点是:哥德尔的G说“不可证”,并需要一个外在保证(ω一致性),保证其实例不会在∃上撒谎;罗瑟的ρ把这个保证内化为证明编码与反驳编码之间的数值竞赛,所以除简单一致性之外别无所需。≤在算术内部完成了ω一致性原先从外部完成的工作。
第七部分——§5 关于分离的进一步讨论(点集骨架,习题10/定理5)
→ 作用:不在不完备性证明的路径上。定理5不证明任何关于S或可证性的事情——它是引理S之下纯粹集合论的骨架,表明差集细化是关于Σ₁集合本身的事实。它的收获(推论)是:“集合的罗瑟系统”(对不交集合对陈述)与“分离所有差集”是同一个性质——所以定理4可以自由地用差集表述一切。
陈述。对任意两个Σ₁集合A、B,存在不交的Σ₁集合A' ⊇ A−B与B' ⊇ B−A。
构造。A、B是Σ₁ ⟹ 选取Σ₀关系R₁、R₂,使A={x:∃y R₁(x,y)}、B={x:∃y R₂(x,y)}(Σ₁范式)。定义:
- A' = {x : ∃y[ R₁(x,y) ∧ (∀z≤y)~R₂(x,z) ]}——“存在一个R₁见证,而在它之处或以下没有R₂见证”;
- B' = {x : ∃y[ R₂(x,y) ∧ (∀z≤y)~R₁(x,z) ]}——镜像。
三项检查:
| 断言 | 论证 |
|---|---|
A−B ⊆ A' |
x∈A−B:x∈A给出一个R₁见证y;x∉B给出对所有z成立的~R₂(x,z)(因而也对所有z≤y成立)。同一个y见证x∈A'。(对称地,B−A ⊆ B'。) |
A'∩B'=∅——≤竞赛 |
假设x∈A'∩B':存在一个R₁见证y,满足(∀z≤y)~R₂,以及一个R₂见证y',满足(∀z≤y')~R₁。不失一般性,设y≤y';于是y是一个满足y≤y'的R₁见证,但B'要求~R₁(x,y)——矛盾。(谁的见证较小谁胜出;另一边的有界∀禁止它。) |
A'、B'是Σ₁ |
矩阵R₁(x,y) ∧ (∀z≤y)~R₂(x,z)是Σ₀(有界∀);前面加一个∃y ⟹ Σ₁。 |
引理S不依赖模型的影子。原先在S中可证地实现分离的同一∃y[ … ∧ (∀z≤y)~ … ]形式,现在把任意两个Σ₁集合细化为其差集的不交Σ₁超集——没有S,没有证明,只有纯粹集合。(习题10要求的正是这一点。)
推论(定理6)。如果每一对不交Σ₁集合在S中都可分离(即S是集合的罗瑟系统),那么对任意Σ₁集合A、B(不交或有交),S都能把A−B与B−A分离。
证明。给定A、B,定理5给出不交Σ₁集合A'⊇A−B、B'⊇B−A。由假设,某个F把A'与B'分离。由于A−B⊆A'、B−A⊆B',同一个F把A−B与B−A分离。∎
所以,“集合的罗瑟系统”的两种读法——分离不交集合对与分离所有差集——相同。n元推广:对任意元数n>1的Σ₁关系,上述一切都成立(第85页,“读者可以容易地验证这一点”)。
第十部分——收获:为何ω一致性是“在元数学上较弱”的假设
你的直觉是对的,只是缺少词汇。下面给出精确表述,分成三个不同方面。
X.1 “较弱假设”的形式含义
当Σ ⟹ W而W ⇏ Σ时,假设W比假设Σ弱。对于定理,关键后果是:
定理“
W⟹ 不完备”在逻辑上更强于“Σ⟹ 不完备”,因为它覆盖Σ覆盖的每个系统,还覆盖更多系统(所有满足W却不满足Σ的系统)。假设更弱 ⇒ 定理更强、更一般。
“在元数学上”这一限定表明,这些是关于系统S、在元理论中断言的谓词——S一致/ω一致/正确,都是我们对S作的陈述,没有一个是S的句子。所以,“在元数学上较弱”= 作为对S的元理论条件而言较弱。
X.2 层级,以及明确展开的蕴涵
三个元数学条件,从最强到最弱:
正确性(可靠性) 每个可证句子都在ℕ中为真
⟹(X.2a)
ω一致性 不存在B(v):∃vB(v)可证,而每个B(m̄)可反驳
⟹(X.2b)
简单一致性 没有句子既可证又可反驳
(X.2a) 正确性 ⟹ ω一致性——直接来自定义。设S正确,反设它通过B(v)而ω不一致:每个B(m̄)可反驳,而∃vB(v)可证。可反驳+正确 ⟹ 每个B(m̄)在ℕ中为假 ⟹ ∃v B(v)在ℕ中为假 ⟹(正确性)∃vB(v)不可证——矛盾。所以正确系统自动ω一致。
(X.2b) ω一致性 ⟹ 简单一致性——更加直接地来自定义。如果S简单不一致,它便证明一切;于是对任意B(v),∃vB(v)与每个~B(m̄)都可证——即S是ω不一致的。逆否:ω一致 ⟹ 简单一致。换言之,ω一致性把简单一致性作为特殊/退化情形内置于自身——这就是它“依其定义本身”成为两者中较强者、位于简单一致性之上的意义。
X.3 为何这些蕴涵是严格的(差距是真实的,而非形式上的)
- 简单一致 ⇏ ω一致(下层差距)。见证来自上次记录的习题9:
P.A.+{~G}简单一致,却ω不一致——它证明∃v₂A(h̄,v₂)(公理~G),同时继承每个~A(h̄,m̄)。所以简单一致性确实容许ω一致性禁止的病态。这正是ω一致性额外带来的东西,也是罗瑟学会不再依赖的东西。 - ω一致 ⇏ 正确(上层差距)。ω一致性只禁止一种形式的假性(其全部实例都可反驳、却得到断言的带见证
∃);对于例如没有这种见证模式的假句子,它什么也没说。所以,ω一致系统仍可能证明某个假句子,因而不正确。ω一致性是可靠性的纯句法残余——“不撒谎”中不可反驳性论证真正用到的精确片段,而非它的全部。
X.4 连接你自己的观察——两条轴是独立的
你已注意到另一种弱化:“所有真Σ₀句子可证”远弱于“所有可证句子为真”。这是对的,而且它是与一致性轴不同的另一条轴。朴素的不完备性证明在两处依赖正确性;斯穆里安/罗瑟分别独立地弱化了这两处:
| 正确性原先用在哪里 | 朴素假设 | 弱化为 | 轴 |
|---|---|---|---|
| 使集合被枚举/表示 | “所有可证者为真”(完全可靠性) | 所有真Σ₀句子可证(单向、只限Σ₀)+随后加ω一致性(哥德尔) | 可表达性轴 |
| 使对角句子不可反驳 | 完全可靠性 | ω一致性(哥德尔)→简单一致性(罗瑟) | 一致性轴 |
- Σ₀轴更弱,因为它(i)限制于最底层的Σ₀,且(ii)只要求真者可证这个方向,而不要求可证者为真这个方向(危险的方向)。
- 一致性轴是X.2的链:完全可靠性 ⟹ ω一致性 ⟹ 简单一致性,每一步都严格。
罗瑟的贡献完全发生在一致性轴上(ω→简单),以Ω₄/Ω₅的结构要求为代价。Σ₀轴未变——定理R仍假设“所有Σ₁集合可枚举”(等价地,通过推论1,“所有真Σ₀句子可证”)。
如果需要压缩版,一段话的回答是:ω一致性比正确性“在元数学上更弱”,因为它被正确性蕴涵,却不蕴涵正确性(X.2a、X.3上层):它是不可反驳性这一步实际需要的可靠性之薄薄句法片段,只禁止“∃vB可证,而每个B(m̄)可反驳”这一种配置。它又比简单一致性强,因为简单不一致是ω不一致的退化实例(X.2b),所以ω一致性包含简单一致性,再加上对习题9病态的禁止。罗瑟的≤竞赛在算术内部重新表达了这种禁止,所以他的句子只需要链条最底层——简单一致性。
区分记录
| 混淆 | 一句话澄清 |
|---|---|
| 罗瑟严格优于哥德尔吗? | 不——不可比较。罗瑟把ω一致性弱化为简单一致性,却增加了“Ω₄、Ω₅的扩张”。两者各自覆盖对方遗漏的系统。 |
| 表示与分离 | 表示 = 精确双向(为R*得到它需要ω一致性)。分离 = 只在A、B各自上单向;无需一致性,而且足够(定理2)。 |
| 一致性究竟用在哪里? | 恰好一次,引理1第2步(“可反驳 ⟹ 不可证”),再加一次把P*−R*化简为P*。两者都是简单一致性。分离公式和引理S完全不用。 |
为何用差集R₁−R₂,而非R₁自身? |
R₁−R₂与R₂−R₁对任意集合都不交——不交性是构造出来的,所以分离它们无需一致性。 |
(∃z≤y)中的≤带来了什么? |
它运行一场证明编码与反驳编码之间的数值竞赛;谁先到谁胜。它把ω一致性从外部作出的保证在句法上内化。 |
| Ω₄、Ω₅贡献什么? | Ω₄把有界量词展开为有限析取;Ω₅给出y≤n̄ ∨ n̄≤y的分类。两者共同让S证明习题4的两半。 |
哥德尔G与罗瑟ρ的不可反驳性 |
G不可反驳需要ω一致性(阻止∃yA(h̄,y)可证+所有实例可反驳)。ρ不可反驳只需要简单一致性——竞赛禁止先于自身的反驳。 |
| “ω一致性更弱”——比什么弱? | 比正确性(可靠性)弱:正确性 ⟹ ω一致性,反向不成立。比简单一致性强。它在链的中间。 |
| 为何说“在元数学上”? | 一致性/ω一致性/正确性是元理论中对S断言的谓词,而不是S的句子。 |
| 两个独立的弱化? | 是:Σ₀轴(“所有真Σ₀句子可证”≪可靠性),以及一致性轴(可靠性 ⟹ ω ⟹ 简单)。罗瑟只移动了第二条。 |
自测
问题1。罗瑟把不完备性归约为把R*与P*分离。任何一致性假设在唯一哪个位置进入?是哪一种一致性?
答案
引理1第2步:“F(n̄)可反驳 ⟹ F(n̄)不可证”,这就是简单一致性。(还用过一次,指出P*∩R*=∅。)分离公式与引理S无需一致性。
问题2。为何引理S针对差集R₁−R₂、R₂−R₁陈述,而非针对R₁、R₂?
答案
因为R₁−R₂与R₂−R₁对任意集合都不交——构造制造了不交性,所以无须一致性。只有当S简单一致时,差集才化简回R*、P*(定理4)。
问题3。在习题4第1部分中,Ω₄与Ω₅具体用在哪里?
答案
Ω₅给出穷尽的分类y≤n̄ ∨ n̄≤y。Ω₄把y≤n̄展开为y=0̄∨…∨y=n̄,于是有限多个反驳~F₂(k̄)(k≤n)在较低一侧消掉前件。
问题4。哥德尔G与罗瑟ρ都由简单一致性得到不可证性。两者在哪里分岔,为什么?
答案
不可反驳性。G需要ω一致性(阻止∃yA(h̄,y)可证而所有~A(h̄,m̄)可证)。ρ只需要简单一致性:(∃z≤y)竞赛使对ρ的反驳必须要求一个反驳见证先于它自身的每个证明见证,而简单一致性已经禁止这一点。
问题5。分别从定义精确说明为何“正确性 ⟹ ω一致性”以及“ω一致性 ⟹ 简单一致性”。
答案
正确+每个B(m̄)可反驳 ⟹ 每个B(m̄)为假 ⟹ ∃vB为假 ⟹(正确性)∃vB不可证——所以ω不一致不可能。而简单不一致会证明一切,立刻产生ω不一致的模式——所以ω一致 ⟹ 简单一致。
问题6。给出“简单一致性 ⇏ ω一致性”的具体见证,并指出我们在哪里构造过它。
答案
P.A.+{~G}(07‑31记录的习题9):由于P.A.⊬G,它简单一致;但它证明∃v₂A(h̄,v₂)(=~G),同时继承每个~A(h̄,m̄),所以ω不一致。
问题7。为何定理R与第五章定理A不可比较,而不是更强?
答案
R弱化一致性假设(ω→简单),但增加了结构假设(必须证明Ω₄、Ω₅)。ω一致而不证明Ω₄/Ω₅的系统适用A、不适用R;简单一致并证明它们的系统适用R、不适用A。两者的假设互不蕴涵。
参考与交叉链接
| 引入的结果 | 使用位置 | 来源 |
|---|---|---|
P*、R*定义;E_n(n̄);表示与枚举;定义1(H(h̄)可证 ⟺ h∈P*) |
第二、三部分 | 07‑29、07‑30 |
定理1′(表示R*+一致 ⟹ 不完备)——第六章定理1加强的结果 |
第三部分 | 07‑30 |
| “所有真Σ₀句子可证 ⟹ 所有Σ₁集合可枚举” | 第四部分(定理3)、第五部分 | 07‑31定理B* |
| Ω₄、Ω₅模式(以及(R)=Ω₁–Ω₅) | 第二、四、五部分 | 07‑31术语表/命题3–5 |
简单一致性/ω一致性定义;习题9(P.A.+{~G}简单一致却ω不一致) |
第六、十部分 | 07‑29、07‑31第九部分 |
哥德尔G=∀v₂~A(h̄,v₂);两种强度的分工(不可证←简单,不可反驳←ω) |
第六部分、X.4 | 07‑30定理3 |
本次阅读范围:斯穆里安,《哥德尔不完备定理》,第六章,第75–85页(主要定理R+推论1–3;§1定理1、引理1、定理2、习题1–2;§2习题3–6、引理S、定理3;§3定理4+罗瑟句子;§4哥德尔与罗瑟比较;§5定理5/6、习题10、n元推广)。
后续
- 第六章仍未完成的习题线索:习题7(一个关系可枚举性结果,“下一章需要”),习题8(带显式
ψ的分离),命题S′(一般分离命题,习题3/4/6是其组成部分),习题10——定理6/推论的n元推广。 - 第五章仍欠的部分:§6习题10–12(
P(X̄)可证性谓词;习题11完整的Σ₁情形留待布洛斯)——Σ₁完备性这笔未完成的账;以及第九章的第二定理(为何“G为真”无法在P.A.中形式化)。 - 下一章以习题7为基础——罗瑟机制(不交Σ₁关系的分离)在那里将作为工具。
先前记录:07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 · 08‑03(本文件)。