Gui Ruiyan

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

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 (in S): (∀n)[ S⊢H(n̄) ⟺ n∈A ]. Two‑directional, exact. (Ch. V: needed ω‑consistency to obtain for R*.)
  • enumerates A (by a 2‑place A(v₁,v₂)): n∈A ⟹ ∃m S⊢A(n̄,m̄) (clause 1) and n∉A ⟹ ∀m S⊢~A(n̄,m̄) (clause 2). One‑directional, cheap; from Σ₀‑completeness alone.
  • separates A from B (by F(v₁)): n∈A ⟹ S⊢F(n̄) (provable) and n∈B ⟹ S⊢~F(n̄) (refutable). No claim about n outside A∪B.
  • separates a relation R₁ from R₂ (by F(v₁,…,vₙ)): the n‑ary version, instance by instance.
  • witness. With A(x,y) enumerating P*: if A(x̄,ȳ) true then y is a witness that x is provable. Symmetrically B(x,y) enumerates R*; a B‑witness certifies x is refutable.
  • difference sets. R₁−R₂ = {x : R₁(x) ∧ ¬R₂(x)}. Note R₁−R₂ and R₂−R₁ are disjoint for any R₁,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 every n.
  • Ω₄ 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 on y≤n̄ vs n̄≤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 every B(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* from P* 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 (separate P* from R*).


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 of x is met by a refutation of x appearing 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̄)) and n∉P* (clause 2: every proof‑instance is refuted, S⊢~A(n̄,m̄) for all m).

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) ] separates R₁−R₂ from R₂−R₁ in S.

(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 separates R₁−R₂ from R₂−R₁. When A,B enumerate disjoint sets, A−B=A and B−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":

  1. It names the essential property. Theorem 4 shows P.A. is incomplete because R* separates from P*. 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."
  2. 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.
  3. 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.
  4. 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 S is (a) simply consistent, (b) proves Ω₄, Ω₅, and (c) has P*, R* enumerable in S, then S is 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 the W‑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?

answerLemma 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₂?

answerBecause 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?

answerUnrefutability. 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.

answerCorrect + 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.

answerP.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?

answerR 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.


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–the n‑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 "G is 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).