Gui Ruiyan

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

Study journals ·

Gödel's Incompleteness Theorems — Session 2026‑08‑04

Reflections · Study sessions

AI-prepared recaps of study sessions; these are working notes, not verbatim transcripts. / AI 整理的学习记录,并非逐字实录。

Reading / 研读:Raymond Smullyan / 雷蒙德·斯穆里安 · Gödel’s Incompleteness Theorems 哥德尔不完备性定理

In this note / 篇目

Chapter VII: Shepherdson's Representation Theorems (pp. 86–96) — representability of every Σ₁ set from simple consistency alone

Orientation — the problem, and Shepherdson's one trick

Read this first; everything below is its unfolding.

The problem. To represent a Σ₁ set A is to build a formula F with F(n̄) provable ⟺ n∈A — a biconditional, so two obligations:

  • (→) cover A — members get proved. This is free: membership is a true, Σ₀‑witnessed fact, and the system proves true facts.
  • (←) dodge ~A — non‑members stay unproved. This is the whole difficulty, and it is a claim about the complement ~A.

(←) is hard for one reason with two faces. A merely simply consistent system can prove false sentences (consistency forbids proving a sentence and its negation, not proving something false in ℕ) — so the natural "true‑on‑A" formula can leak provability onto non‑members (exactly the ω‑inconsistency pathology of Ex 9: ∃y R(n̄,y) provable with no real witness). And you can't route around this by policing the non‑members yourself, because ~A need not be Σ₁ (Post: only when A is recursive) — there's no enumeration of ~A to grab. You can neither trust the system to stay silent on ~A, nor force silence by enumerating it. Historically this (←) half was bought with ω‑consistency (the promise "no false witnessed ∃ is provable").

Shepherdson's trick — never confront ~A; make it lose a race. Build F as a self‑referential ≤‑race (Rosser's device, via the diagonal gadget Π): a sentence that pits the set's membership‑witnesses against the sentence's own proof/refutation‑witnesses, and asks which shows up first. Then:

  • non‑membership never has to be enumerated or trusted — it surfaces only as the loser of a race between two things that genuinely are Σ₁ (the set A, and the provability relation);
  • the only fact needed to adjudicate the race is simple consistency — a refutation cannot precede itself — no soundness, no ω‑consistency.

That single move — recast the impossible obligation about ~A as a winnable race between two Σ₁ objects, settled by simple consistency — is the whole chapter. The two tracks are just two settings of the same dial: feed the diagonal a weak separation and it represents one set (Track A); feed it a strong separation and it exactly separates a pair (Track B, which contains A).


New chapter, and it inverts the last one's polarity. Chapter VI used Rosser's ≤‑race to separate R* from P* — a one‑shot, aimed at undeciding a single sentence (incompleteness, a negative result). Chapter VII shows the same Rosser machinery, once packaged as the property "Rosser system," delivers the strongest positive result available: every Σ₁ set is representable — and still from nothing more than simple consistency.

Historically this was the surprise. At the time of Gödel's proof, the only known route to representing P* in P.A. ran through ω‑consistency. Ehrenfeucht–Feferman [1960] first showed all Σ₁ sets are representable in every simply consistent axiomatizable extension of (R) (combining a Rosser‑type argument with Myhill's recursion‑theoretic result). Shepherdson [1961] then found the direct, self‑contained route this chapter follows.

This session did two things: (i) cleared the preparatory apparatus — weak separation, the wrapper E[m̄,n̄] and its Gödel‑number function Π — through four foundational questions; then (ii) reconstructed and verified against clean scans the full representation chain Lemma 1* → Lemma 1 → Theorem S₁ → Theorem 1. The parallel separation chain is then made concrete through Shepherdson's actual formula φ (Part V) — Rosser's ρ with A and B on opposite sides of the race — with the three outcomes (provable on A, refutable on B, undecidable between) verified by that race; the §4 strengthenings are stated exactly.

Reading order follows the logical spine, not the book's page order.


Part 0 — the one‑sentence shift, and what carries over

Chapter VI's currency was separation; Chapter VII spends it to buy representation.

Chapter VI (Rosser) Chapter VII (Shepherdson)
goal undecide one sentence ⟹ incomplete (negative) represent every Σ₁ set (positive)
tool H separates R* from P* (one pair) S is a Rosser system: separates every disjoint Σ₁ pair
consistency used simple simple
headline Theorem R — P.A. incomplete Theorem S₁ — all Σ₁ sets representable

The bridge between them is a single gadget introduced here: a diagonal self‑reference through provability, carried by a Gödel‑number function Π. Feed it a separating formula and it returns a representing one. Everything in the chapter is that gadget plus bookkeeping.

What we import unchanged from Ch. VI: the definition of a Rosser system, the ≤‑race formula, and the fact that every simply consistent axiomatizable extension of (R) is a Rosser system (the Ω₄, Ω₅ machinery, 08‑03 Lemma S / Thm 3). Chapter VII never re‑proves that; it consumes it (Theorem 1, Theorem 2).


Part I — the two tracks: end state, payload, assembly

GOAL of the chapter. Show that a simply consistent axiomatizable Rosser system represents every Σ₁ set — recovering, from simple consistency alone, what Gödel needed ω‑consistency for.

The one idea both tracks share. You can't represent a Σ₁ set A head‑on: representing A means controlling F(n̄) for n∉A too, and ~A need not be Σ₁ (Post: ~A is Σ₁ only when A is recursive). So instead —

build two Σ₁ relations out of A and a provability predicate, have the Rosser system separate them, and let a self‑referential diagonal convert that separation into representation.

The Rosser hypothesis supplies the separation; the diagonal ★ (via the wrapper Π) makes a sentence talk about its own provability; simple consistency does one small conversion. Both tracks run this method on the shared gadget wrapper E[m̄,n̄] → Π → Master Equivalence → diagonal ★. The tracks differ in one dial only: whether the separation fed to the diagonal is weak (one polarity) or strong (both polarities).

Track A — REPRESENTATION (weak separation → one polarity)

  • End state. Every Σ₁ set A is representable: a formula F with n∈A ⟺ F(n̄) provable. — Theorem S₁; for extensions of (R), Theorem 1 (Ehrenfeucht–Feferman).
  • What it tells you. Provability tracks membership — one set, the provable/not‑provable polarity only. This is everything incompleteness and undecidability of the theory require.
  • How assembled (3 rungs): 1. Lemma 1* (engine) — from a weak separation of two relations, the diagonal gives one biconditional F(n̄) provable ⟺ R(n,h). Spends nothing — pure fixed‑point logic. 2. Lemma 1 — set R := "x∈A"; the engine yields F = E_h(v₁,h̄) represents A. 3. Theorem S₁ — the Rosser hypothesis strongly separates the pair U,V; simple consistency (spent here, once) downgrades strong→weak; feed Lemma 1.

Track B — SEPARATION (strong separation → both polarities)

  • End state. Every disjoint pair of Σ₁ sets A,B is exactly separable: a formula F with n∈A ⟺ provable, n∈B ⟺ refutable, else undecidable. — Theorem S₂; for extensions of (R), Theorem 2 (Putnam–Smullyan).
  • What it tells you. Provability tracks A and refutability tracks B — two sets, both polarities. Strictly more than Track A: set B=∅ and exact separation collapses to plain representation, so Track B contains Track A (S₂ ⟹ S₁). The extra — control of refutability — is what the inseparability and essential‑undecidability results need.
  • How assembled (3 rungs, the strong‑separation twin): 1. Lemma 2* (engine) — from a strong separation, the diagonal run twice (once for provability, once for refutability) gives two biconditionals provable ⟺ R₁, refutable ⟺ R₂. Spends simple consistency — to stop the two outputs colliding. 2. Lemma 2 — set the two "teams" R₁ = A∨Ref, R₂ = B∨Prov; the engine yields F exactly separates A from B. 3. Theorem S₂ — the Rosser hypothesis supplies the strong separation directly (no downgrade); the two biconditionals are exact separation.

The one essential distinction

Track A — representation Track B — separation
separation fed to the diagonal weak strong
polarities kept provable only provable and refutable
end state represent one set exactly separate a pair
logical strength the headline strictly stronger — implies A via B=∅
powers downstream incompleteness, undecidability inseparability, essential undecidability

They are not siblings. Track A is the clean headline (simplest proof, widest use); Track B is its strict upgrade. Same gadget, same three‑rung shape; the only structural difference is weak vs. strong separation into the engine — equivalently, discard vs. keep the refutable half.


Part II — Citable glossary

Carried: E_x = expression with Gödel number x; P = set of Gödel numbers of provable sentences; P*, R* from Ch. V/VI.

  • represents A (by F(v₁)): (∀n)[ S⊢F(n̄) ⟺ n∈A ]. Two‑directional; stated purely in provable / not‑provable — refutability never appears.
  • strongly separates A from B (= Ch. VI's "separates"): n∈A ⟹ S⊢F(n̄); n∈B ⟹ S⊢~F(n̄) (refutable).
  • weakly separates A from B — definition (the book's): F represents some superset A'⊇A with A'∩B=∅. Equivalent characterization: n∈A ⟹ S⊢F(n̄); n∈B ⟹ S⊬F(n̄) (not provable). The B‑clause softens "refutable" to "not provable."
  • exactly separates A from B (by F): n∈A ⟹ provable; n∈B ⟹ refutable; n∉A∪B ⟹ undecidable. Equivalently F represents A and ~F represents B — a double representation.
  • Rosser system for n‑ary relations: for any Σ₁ relations R₁,R₂, the difference R₁−R₂ is strongly separable from R₂−R₁. for sets = the n=1 case. exact Rosser system for sets: every disjoint Σ₁ pair is exactly separable.
  • wrapper E[m̄,n̄] := ∀v₁(v₁=m̄ ⊃ ∀v₂(v₂=n̄ ⊃ E)). A fixed syntactic frame around all of E; never inspects E's interior.
  • Π(a,b,c) = Gödel number of E_a[b̄,c̄]. A total concatenation function of a,b,c; its graph is Σ₀.
  • (MEq) Master Equivalence: (∀a,b,c)[ Π(a,b,c)∈P ⟺ E_a(b̄,c̄) provable ]. (If E_a isn't a formula, both sides false.) Σ₁ in (a,b,c) since P is Σ₁.
  • Prov(x,y) := Π(y,x,y)∈P — the binary relation "E_y(x̄,ȳ) is provable." The slot y sits in positions 1 and 3 (index and second argument); slot 2 holds the real input x. Σ₁.
  • diagonal ★. Fix a formula E with free v₁,v₂, h=⌜E⌝ (so E=E_h); write G_n := E_h(n̄,h̄). Then Prov(n,h) ⟺ G_n provable — the number h doing double duty is the entire self‑reference.

Part III — the preparatory apparatus (four foundational questions)

Before any theorem, four confusions had to be cleared. They are the reason the later proofs read cleanly.

III.1 Weak separation — definition vs. characterization (the order matters)

The definition is the superset one (def): F weakly separates A from B iff F represents some A'⊇A disjoint from B. The provable/not‑provable pair is a derived characterization, not the definition. Derivation, using representation's two clauses on A' = {n : S⊢F(n̄)}:

# claim why
1 n∈A ⟹ S⊢F(n̄) A⊆A', and F represents A' (clause i: member ⟹ provable)
2 n∈B ⟹ S⊬F(n̄) A'∩B=∅ ⟹ n∉A', and F represents A' (clause ii: non‑member ⟹ not provable)

So "not provable" is inherited verbatim from representation's negative clause (ii) — refutability is structurally absent from representation, hence cannot appear. Superset legitimately appears, but as A' (the set F actually represents), not as "A is its own superset."

Strong ⟹ weak (Ch. VI Lemma 1): from strong separation put A'={n:S⊢F(n̄)}; then A⊆A' (strong's provable half) and, for n∈B, S⊢~F(n̄) + simple consistency ⟹ S⊬F(n̄) ⟹ n∉A'. That lone step "refutable ⟹ not provable" is where the downgrade lives — the sole consistency cash, exactly as in Ch. VI.

Why A' is generally a proper superset. Split ℕ into three bands: A (forced provable), B (forced not‑provable), and the don't‑care region ∉A∪B (unconstrained). If F(n̄) happens to be provable on some don't‑care n, that n joins A'. So A' = A plus possibly harmless overshoot that avoids B. The superset has no special power; it is just the honest name for what F represents. And when B is the complement of A, the bands pinch — A⊆A'⊆(complement of B)=A — so A'=A and weak separation collapses to exact representation. Representation is the limiting case of weak separation against a full complement.

III.2 The wrapper E[m̄,n̄] and the function Π

Two statements the book makes back‑to‑back are not redundant:

  • (1) if E is a formula whose only free variables are v₁,v₂, then E[m̄,n̄] is a sentence equivalent to E(m̄,n̄);
  • (2) if E is any formula, then E[m̄,n̄] ≡ E(m̄,n̄) is logically valid (⟹ provable in S ⟹ provability transfers).

They differ on both axes. The single logical fact underneath is the double equality‑guard collapse ∀v(v=t ⊃ Φ) ≡ Φ(t) (valid by: instantiate v:=t with t=t; and substitution of equals), applied twice. From it: (2) is that fact; (1)'s "equivalent" is a semantic shadow of it — but (1)'s "is a sentence" is a separate, purely syntactic fact (the two ∀'s bind v₁,v₂; if those were the only frees, nothing dangles). So it is one logical fact + one independent syntactic fact, not two consequences of one cause. And both are needed: sentence‑hood (1) makes "provable" meaningful (only sentences lie in P); logical validity (2) makes provability transfer (mere semantic equivalence would not give S⊢E[m̄,n̄] ⟺ S⊢E(m̄,n̄) — you need the biconditional itself provable).

Why the wrapper at all? E[m̄,n̄] is a fixed frame prepended/appended around E — so ⌜E[m̄,n̄]⌝ = Π(⌜E⌝,m,n) is a trivial concatenation function, total on all x. Genuine substitution E(m̄,n̄) must hunt free occurrences and replace them — far messier to arithmetize. The wrapper buys the same provable‑equivalence with a clean Σ₀ coding function. This yields the Master Equivalence (MEq).

Junk filters itself out (why totality is harmless): if Π(x,y,z)∈P, then E_x[ȳ,z̄] is a provable sentence ⟹ well‑formed ⟹ the ⊃ has a formula on its right ⟹ E_x is automatically a formula. We never need a side hypothesis "x codes a formula" — membership in P forces it.


Part IV — the representation track, in full (verified against clean scans)

This is the spine, and every line below was checked against pp. 88–89.

Ch. VII Lemma 1* — the engine (spends nothing)

→ Role: convert a given weak separation into an exact biconditional. Consistency‑free; Rosser‑free. Pure diagonal logic.

The two relations (binary in x,y), with Prov = Π(y,x,y)∈P:

U(x,y) := R(x,y) ∧ Π(y,x,y)∉P ("R holds, and the diagonal sentence is not provable") V(x,y) := Π(y,x,y)∈P ∧ ~R(x,y) ("the diagonal sentence is provable, and R fails")

The ∉P / ∈P asymmetry is the whole engine — this was the crux we could not read until the clean scan, and the argument only closes with it (see the note after the proof).

Statement. For any relation R(x,y): if a formula E_h(v₁,v₂) (with h=⌜E_h⌝) weakly separates U from V, then (∀n)[ E_h(n̄,h̄) provable ⟺ R(n,h) ].

Proof. Weak separation at a generic tuple (n,m) (instance E_h(n̄,m̄)):

clause says
(1) R(n,m) ∧ Π(m,n,m)∉P ⟹ S⊢E_h(n̄,m̄)
(2) Π(m,n,m)∈P ∧ ~R(n,m) ⟹ S⊬E_h(n̄,m̄)

Freeze m=h; write G = E_h(n̄,h̄). By ★, Π(h,n,h)∈P ⟺ G provable. The clauses become self‑refuting traps:

says
(1ₕ) R(n,h) ∧ [G not provable] ⟹ G provable
(2ₕ) [G provable] ∧ ~R(n,h) ⟹ G not provable
direction argument
R(n,h) ⟹ G provable Assume R(n,h). If G were not provable, (1ₕ)'s antecedent holds ⟹ G provable — a flat metalanguage contradiction. So G provable.
G provable ⟹ R(n,h) Assume G provable. If ~R(n,h), (2ₕ)'s antecedent holds ⟹ G not provable — contradiction. So R(n,h).

Hence G provable ⟺ R(n,h). ∎

Two things to mark. 1. No consistency, no Rosser. The contradictions are "this one fixed sentence G is both provable and not‑provable" in the metatheory — not a claim that S is consistent. The lemma is pure bookkeeping on the given separation. 2. The ∉P conjunct in U is load‑bearing. Had U carried Π∈P instead, (1ₕ) would read R(n,h) ∧ [G provable] ⟹ G provable — vacuous, and the forward direction collapses. The "not provable" conjunct is precisely what springs the trap. (This is the exact spot flagged two turns earlier as "will not fake"; the clean scan resolved it.)

Ch. VII Lemma 1 — Representation Lemma

Statement. For a set A: if [x∈A ∧ Π(y,x,y)∉P] is weakly separable from [Π(y,x,y)∈P ∧ x∉A], then A is representable; concretely, the separator E_h(v₁,v₂) gives E_h(v₁, h̄) represents A.

Proof. Lemma 1* with R(x,y):⟺ x∈A. Then R(n,h) ⟺ n∈A, so E_h(n̄,h̄) provable ⟺ n∈A, i.e. E_h(v₁,h̄) represents A. ∎ (The scan prints the first relation's connective as ∈P; it must read ∉P to match Lemma 1* and the Theorem S₁ proof — a typo we corrected against the argument.)

Ch. VII Theorem S₁ — Shepherdson's Representation Theorem

Statement. If S is a simply consistent axiomatizable Rosser system for binary relations, then every Σ₁ set A is representable in S.

Proof. Choose two Σ₁ relations:

definition Σ₁ because
R₁(x,y) x∈A A is Σ₁
R₂(x,y) Π(y,x,y)∈P (= Prov) S axiomatizable ⟹ P is Σ₁; Π's graph is Σ₀

Take their differences — the negations appear for free:

# claim grounds
1 R₁−R₂ = (x∈A) ∧ Π(y,x,y)∉P = U and R₂−R₁ = Π(y,x,y)∈P ∧ ~(x∈A) = V set algebra
2 U strongly separable from V Rosser system (binary) on the Σ₁ pair R₁,R₂
3 U weakly separable from V 2 + simple consistency (strong ⟹ weak, III.1)
4 E_h(v₁,h̄) represents A 3 + Lemma 1 ∎

The deep point — no complement need be Σ₁. The worry "~A isn't Σ₁, so how can we separate against it?" dissolves here: we hand the Rosser system two honestly Σ₁ relations R₁=A, R₂=Prov, and the difference operation manufactures both ~A and ~Prov at zero complexity cost. This is precisely Ch. VI's difference‑set trick (08‑03 Lemma S: "R₁−R₂, R₂−R₁ disjoint for any sets, disjointness manufactured"), now carrying representation, with the provability predicate Prov playing the role of R₂.

Consistency ledger. One dose of simple consistency, at line 3. Axiomatizability is spent choosing R₂ (makes Prov Σ₁). The Rosser property is spent at line 2. Lemma 1* itself (line 4's interior) spends nothing.

Ch. VII Theorem 1 — Ehrenfeucht–Feferman

Statement. All Σ₁ sets are representable in every simply consistent axiomatizable extension of (R).

Proof. Every such extension is a Rosser system for binary relations — the Ch. VI ≤‑machinery, which needs Ω₄, Ω₅ (proved in (R)) and Σ₀‑completeness (08‑03 Theorem 3, lifted to relations). Apply Theorem S₁. ∎

The concrete representing sentence (p. 90 Discussion)

For an extension of (R) you can write it down. With A(x,z) the Σ₀ generator (∃z A(n,z) ⟺ n∈A) and B(x,w) enumerating provability of the diagonal sentences, the fixed point is

H_n := ∀z( A(n̄,z) ⊃ (∃w≤z) B(n̄,w) ) — "every witness z that n∈A is matched by an ≤‑earlier witness w that I am provable,"

with the dual ∃z( A(n̄,z) ∧ (∀w≤z)~B(n̄,w) ) also representing A. It is Rosser's ≤‑race redirected: instead of racing proofs against refutations to undecide (Ch. VI), it races the provability‑of‑H_n against the membership‑witness of A to represent. The w≤z race is what lets simple consistency do the job ω‑consistency did for Gödel's G. Theorem S₁'s abstract proof is exactly this sentence with the ≤‑race outsourced to the Rosser hypothesis.


Part V — the separation track: one formula, two teams, a race

The second half of the chapter upgrades representation (one set) to exact separation (two disjoint sets A,B at once): a single formula φ with

n∈A ⟹ φ(n̄) provable, n∈B ⟹ φ(n̄) refutable, n∉A∪B ⟹ φ(n̄) undecidable.

The clean scan (p. 91) hands us Shepherdson's actual φ, and it is the clearest object in the chapter — it is Rosser's ρ with A and B drafted onto opposite sides of the race. Everything abstract (Lemma 2, Lemma 2*) is bookkeeping around this one sentence.

V.1 The formula, read in plain words

The p. 91 paragraph says φ(n̄) expresses:

"For any x: if x is (a witness that I am provable) or (a witness that n∈B), then there is some w ≤ x that is (a witness that I am refutable) or (a witness that n∈A)."

In symbols, with four Σ₀ witness‑predicates — Pf(n,x)="x codes a proof of φ(n̄)", Rf(n,x)="x codes a refutation of φ(n̄)", and A(n,x), B(n,x) the generators of the sets (∃x A(n,x) ⟺ n∈A, etc.):

φ(n̄) = ∀x[ (Pf(n,x) ∨ B(n,x)) ⊃ (∃w≤x)( Rf(n,w) ∨ A(n,w) ) ]

V.2 It is Rosser's ρ, plus one disjunct on each side

Recall Rosser's ρ (Ch. VI): ρ = ∀x[ Pf(x) ⊃ (∃w≤x) Rf(w) ] — "every proof of me is overtaken by an earlier refutation of me." Shepherdson adds exactly one disjunct to each side:

side of the race Rosser ρ Shepherdson φ effect of the new disjunct
antecedent — the attack (fires ⟹ pushes φ toward refutable) proof of me proof of me ∨ n∈B a B‑witness fires the attack
consequent — the defense (holds ⟹ pushes φ toward provable) refutation of me refutation of me ∨ n∈A an A‑witness mans the defense

So the whole mechanism is a race between two teams, with A and B drafted onto opposite teams:

  • A joins the defense. A witness for n∈A makes the consequent hold for free ⟹ φ(n̄) provable.
  • B joins the attack. A witness for n∈B fires the antecedent with nothing to answer it ⟹ φ(n̄) refutable.
  • Pf‑of‑me vs Rf‑of‑me is Rosser's original self‑referential race, still running underneath, keeping the sentence consistent (no proof of φ slips in without an earlier refutation, and vice versa). That underlying race is what makes simple consistency enough.

One slogan: A on the defending side ⟹ provable; B on the attacking side ⟹ refutable; nobody drafted ⟹ bare ρ ⟹ undecidable.

V.3 The three outcomes, by substituting into φ

Rather than re‑run the race each time, plug the case's facts straight into φ and watch it collapse to something you can read off. Recall φ(n̄) = ∀x[ (Pf(n,x) ∨ B(n,x)) ⊃ (∃w≤x)(Rf(n,w) ∨ A(n,w)) ].

Case n∈A (so n∉B; let a = least A‑witness). Put B(n,x) ↦ false and A(n,a) = true:

φ(n̄) = ∀x[ Pf(n,x) ⊃ (∃w≤x)(Rf(n,w) ∨ A(n,w)) ]

For every x ≥ a the consequent already holds: S ⊢ A(n̄,ā) (Σ₀‑completeness — a is a genuine A‑witness, A a fixed decidable predicate), so w=a satisfies (∃w≤x)(Rf∨A). Those x drop out; below a, A(n,w) is false. What's left:

φ(n̄)  ⟺  ∀x < a [ Pf(n,x) ⊃ (∃w≤x) Rf(n,w) ]

"Any proof of me below the deadline a is outrun by an earlier refutation" — a claim about finitely many x. Either some x<a already proves φ (then φ provable outright), or none does — then each Pf(n,x̄) is false, S ⊢ ¬Pf(n,x̄) (Σ₀‑completeness), the antecedents die, and Ω₄ bundles the finite ∀x<a into S ⊢ φ(n̄). Provable, either way. ✓

Case n∈B (so n∉A; let b = least B‑witness). Put A(n,w) ↦ false, so the defence collapses to just Rf:

φ(n̄) = ∀x[ (Pf(n,x) ∨ B(n,x)) ⊃ (∃w≤x) Rf(n,w) ]

"φ(n̄) refutable" means S ⊢ ~φ(n̄), so the whole job is to prove ~φ(n̄). Negating a ∀[…⊃…] gives an ∃[… ∧ ¬…]:

~φ(n̄)  =  ∃x[ (Pf(n,x) ∨ B(n,x)) ∧ (∀w≤x) ¬Rf(n,w) ]   —  "some attacker x gets through with no refutation at or below it."

To prove an ∃x, we exhibit one x that works and prove its two conjuncts — x = b is the attacker, and both conjuncts fall to the same Σ₀‑completeness used in the n∈A case (S proves every true decidable fact):

  • attacker present at b: S ⊢ B(n̄,b̄). This is the easy, non‑self‑referential step — B(n,x) is just the fixed decidable predicate defining the set B, nothing to do with φ; and b is a genuine witness of n∈B, so B(n,b) is a true Σ₀ fact and S proves it. (Exactly the move S ⊢ A(n̄,ā) played in the previous case.) Hence S ⊢ (Pf∨B)(n̄,b̄).
  • no earlier refutation: if no number ≤ b codes a refutation of φ(n̄), then each ¬Rf(n̄,w̄) (w≤b) is a true decidable fact, so S ⊢ ¬Rf(n̄,w̄), and Ω₄ bundles the finitely many into S ⊢ (∀w≤b̄) ¬Rf(n̄,w̄).

Conjoin the two: S ⊢ (Pf∨B)(n̄,b̄) ∧ (∀w≤b̄)¬Rf(n̄,w̄), which is exactly the x=b instance of ~φ(n̄). So S ⊢ ~φ(n̄). Refutable. (And if instead some refutation of φ did have code ≤ b, then φ is refutable outright — either way, refutable.) ✓

The mirror is exact: in n∈A, the A‑witness a was a defender past which no attack survives, so S proves φ; here the B‑witness b is an attacker with the field cleared of defenders (n∉A) and no refutation beating it, so S proves ~φ. Both use S ⊢ (witness) + Ω₄‑bundle‑the‑bounded‑part + Σ₀‑completeness; only the roles (defend vs. attack) swap.

Case n∉A∪B. Put A(n,w) ↦ false and B(n,x) ↦ false:

φ(n̄)  =  ∀x[ Pf(n,x) ⊃ (∃w≤x) Rf(n,w) ]   —   this is exactly Rosser's ρ.

No A, no B left. Undecidable under simple consistency (Ch. VI). ✓

The punchline is the third line: with nobody drafted onto either team, φ literally becomes ρ. A and B are the only things you can add to tip the race — A to the defense (⟹ provable), B to the attack (⟹ refutable). So φ exactly separates A from B on simple consistency alone.

V.4 The abstract packaging, proved (Lemma 2)

The abstract lemma drops the concrete witnesses and works with the two teams as Σ₁ relations, so the result holds for any Rosser system (not just extensions of (R)). Set up, at the diagonal φ(n̄):

  • p := "φ(n̄) provable" r := "φ(n̄) refutable"; consistency ¬(p∧r); A,B disjoint ¬(n∈A ∧ n∈B).
  • DEFENSE D := (n∈A) ∨ r ("in A, or I'm refutable" — the consequent side of φ).
  • ATTACK T := (n∈B) ∨ p ("in B, or I'm provable" — the antecedent side of φ).

These are the scan's R₁ = A∨Ref and R₂ = B∨Prov. A Rosser system strongly separates D−T from T−D — the formula φ of V.1 is that separator — which is two implications:

(I) (n∈A ∨ r) ∧ ¬(n∈B) ∧ ¬p ⟹ p (II) (n∈B ∨ p) ∧ ¬(n∈A) ∧ ¬r ⟹ r

Goal: p ⟺ n∈A and r ⟺ n∈B (= exact separation). Each of the four directions is the same move — assume the claim, suppose its negation, one clause fires, contradiction:

want proof
n∈A ⟹ p Assume n∈A, so ¬(n∈B). Suppose ¬p. Then (n∈A∨r), ¬(n∈B), ¬p hold ⟹ (I) ⟹ p. Contra. So p.
p ⟹ n∈A Assume p, so ¬r (consistency). Suppose ¬(n∈A). Then (n∈B∨p), ¬(n∈A), ¬r hold ⟹ (II) ⟹ r. Contra ¬r. So n∈A.
n∈B ⟹ r Assume n∈B, so ¬(n∈A). Suppose ¬r. Then (n∈B∨p), ¬(n∈A), ¬r hold ⟹ (II) ⟹ r. Contra. So r.
r ⟹ n∈B Assume r, so ¬p (consistency). Suppose ¬(n∈B). Then (n∈A∨r), ¬(n∈B), ¬p hold ⟹ (I) ⟹ p. Contra ¬p. So n∈B.

So p ⟺ n∈A, r ⟺ n∈B — exact separation. ∎ (Consistency is spent in the two reverse rows; disjointness in the two forward rows. The p, r glued into the teams are exactly what powers the two reverse rows — i.e. what upgrades strong separation to exact — as the table shows.)

Lemma 2* is this with sets A,B replaced by relations R₁,R₂ (D=R₁∨Ref, T=R₂∨Prov), yielding R₁(n,h)⟺provable, R₂(n,h)⟺refutable. Theorem S₂: every consistent axiomatizable Rosser system for binary relations is an exact Rosser system for sets (the Rosser hypothesis supplies the strong separation of D−T from T−D). Theorem 2 (Putnam–Smullyan): every simply consistent axiomatizable extension of (R) is an exact Rosser system for sets (corollary via Thm 1's route — such extensions are Rosser systems). Smullyan proves clause (1) and leaves the symmetric (2) "to the reader" (p. 92); the table above does both.

Where representation and separation part ways. Representation needed only provability, so Theorem S₁ could downgrade strong → weak (throw away the refutable half, spend one dose of consistency). Exact separation needs both polarities, so Theorem S₂ keeps the whole strong separation and lets the refutable half do real work. That single difference — discard vs. keep the refutable side — is the entire distinction between the two tracks.


Part VI — §3 variants (Ex 4–10) and §4 the strengthenings

§3 — Theorem 3, its Corollary, and the exercises (pp. 94–95)

Theorem 3 and its Corollary re‑derive incompleteness by running the same engine on variant self‑referential sentences — the "some curious variants of Rosser's undecidable sentence." The two representing sentences from the Discussion are the templates:

∀z( A(x,z) ⊃ (∃w≤z) B(x,w) ) and its dual ∃z( A(x,z) ∧ (∀w≤z) ~B(x,w) ).

The Corollary reads off: if the relation Π(x,y,z)∈P is enumerable in S and S is a consistent extension of Ω₄, Ω₅, then S is incomplete — Rosser's result recovered through the representation apparatus rather than the bare separation of Ch. VI.

Exercises 4–10 (open threads, to work next): - Ex 4 — using Ex 5 and Lemma 1*, show weak separability of Π(x,y,z)∉P from Π(x,y,z)∈P ∧ x∈A ⟹ (if consistent) S incomplete. - Ex 5, Ex 6 — the enumeration steps that feed Ex 4 (extension of Ω₄, Ω₅, and Π(x,y) enumerable). - Ex 7 — how Ex 6 yields another proof of Theorem 3. - Ex 8 — if the set {x : Π(x,x,x)∈P} is representable, S is incomplete. - Ex 9, Ex 10 — the dual‑formula versions (with Π(x,z,x)∈P shapes), giving yet another route to Ex 6.

These are the Chapter‑VII counterparts of Ch. VI's Ex 3–6; each is a short application of the engine, and they are the session's standing exercise debt.

§4 — Theorems S₁*, S₂*: naming the formula (p. 96)

Using the starred lemmas (1*, 2*) in place of the plain lemmas sharpens both theorems from "there exists a representing/separating formula" to "here is one, by its Gödel number":

Theorem S₁*. If S is a consistent axiomatizable Rosser system for binary relations and R(x,y) is Σ₁, there is a number h such that E_h(v₁,v₂) is a formula and E_h(v₁,h̄) represents R(x,h) — i.e. (∀n)[ n∈{x:R(x,h)} ⟺ E_h(n̄,h̄) provable ]. Theorem S₂*. Same hypotheses; for disjoint Σ₁ relations R₁,R₂, there is h with E_h(v₁,h̄) exactly separates {x:R₁(x,h)} from {x:R₂(x,h)}.

Exercise 11 asks for the proofs of S₁*, S₂* — direct, since Lemma 1*/2* already deliver the named h. Smullyan notes these sharper forms "have interesting applications in our sequel," and that the sequel compares Shepherdson's proof with the original, the two generalizing in incomparable directions (p. 86). This *‑upgrade is the exact analog of Ch. V's move from "incomplete" to "here is the undecidable sentence."


Distinctions Ledger

Confusion One‑line resolution
Is weak separation defined by provable/not‑provable? No. Defined as "represents a superset A'⊇A disjoint from B." The provable/not‑provable pair is derived; "not provable" is inherited from representation's clause (ii).
Does "superset" mean A is its own superset? No. The superset is A' = {n:S⊢F(n̄)}, the set F actually represents — generally a proper superset of A via the don't‑care band.
Strong ⟹ weak — mechanism? Simple consistency on the B‑clause: refutable ⟹ not provable. Nothing else.
E[m̄,n̄] ≡ E(m̄,n̄) valid and E[m̄,n̄] a sentence — redundant? No. Logical validity (any E) + sentence‑hood (only v₁,v₂ free) are different facts; the first makes provability transfer, the second makes "provable" meaningful.
Why the wrapper [ , ] instead of substitution ( , )? ⌜E[m̄,n̄]⌝ = Π(⌜E⌝,m,n) is a trivial Σ₀ concatenation, total on all x; substitution is messy to arithmetize.
Π(x,y,z)∈P ⟹ E_x a formula — why automatic? Only sentences are provable; the wrapper is well‑formed only if E_x is a formula. P filters the junk.
Where is the self‑reference? Diagonal ★: h=⌜E_h⌝ sits in Π's slots 1 and 3, so Π(h,n,h)∈P means "E_h(n̄,h̄) is provable."
The ∉P / ∈P asymmetry in Lemma 1* — why essential? With ∈P in U, trap (1ₕ) is vacuous and R⟹provable fails. "Not provable" is what springs the trap.
How is A representable when ~A isn't Σ₁? Never separate against ~A directly. Take Σ₁ R₁=A, R₂=Prov; the Rosser difference manufactures ~A, ~Prov for free.
Does Lemma 1* use consistency? No. It is pure fixed‑point logic on a given weak separation. Simple consistency enters only at Theorem S₁ (strong ⟹ weak).
Representation vs exact separation? Representation = one biconditional (provable ⟺ A). Exact separation = two (provable ⟺ A and refutable ⟺ B) = F reps A, ~F reps B.

Self‑Test

Q1. The book states weak separation two ways. Which is the definition, and where does the derived "not provable" come from?

answerDefinition = "F represents a superset A'⊇A disjoint from B." The characterization n∈B ⟹ S⊬F(n̄) is derived: n∈B ⟹ n∉A' (disjoint) ⟹ (representation clause ii) F(n̄) not provable. Refutability is absent from representation, so it cannot appear.

Q2. In Prov(x,y)=Π(y,x,y)∈P, why must y occupy positions 1 and 3?

answerBy (MEq), Π(a,b,c)∈P ⟺ E_a(b̄,c̄) provable. To make a sentence talk about its own provability we set the index a and the second argument c to the same code h. So y (the slot frozen to h) must be both — positions 1 and 3. Position 2 holds the genuine input x. At y=h: Π(h,n,h)∈P ⟺ E_h(n̄,h̄) provable.

Q3. Write the two relations U, V of Lemma 1* and say which conjunct is load‑bearing.

answerU = R(x,y) ∧ Π(y,x,y)∉P; V = Π(y,x,y)∈P ∧ ~R(x,y). The ∉P in U is load‑bearing: it makes trap (1ₕ) R(n,h) ∧ [G not provable] ⟹ G provable non‑vacuous. With ∈P there, the forward direction R⟹provable fails.

Q4. Lemma 1* proves a full biconditional yet uses no consistency. How is that possible?

answerThe two contradictions are metalinguistic — "this one fixed sentence G is both provable and not provable" — which is impossible regardless of whether S is consistent. Consistency (object‑level) would only be needed to compare provable against refutable; Lemma 1* only ever compares provable against not‑provable.

Q5. In Theorem S₁, ~A is not Σ₁. How does the proof separate against it anyway?

answerIt doesn't separate against ~A directly. It hands the Rosser system two Σ₁ relations R₁=A, R₂=Prov; the differences R₁−R₂=U and R₂−R₁=V manufacture ~A and ~Prov for free. Only Σ₁ inputs are ever required.

Q6. State exact separation as a pair of representation facts, and deduce the "undecidable off A∪B" clause.

answerF exactly separates A from B iff F represents A (provable ⟺ n∈A) and ~F represents B (refutable ⟺ n∈B). Off A∪B: n∉A ⟹ not provable, n∉B ⟹ not refutable ⟹ undecidable.

Q7. Why is Theorem 1 (Ehrenfeucht–Feferman) a corollary of Theorem S₁ rather than a separate proof?

answerBecause every simply consistent axiomatizable extension of (R) is a Rosser system for binary relations (Ch. VI's Ω₄,Ω₅ ≤‑machinery). Theorem S₁'s hypothesis is met, so its conclusion — all Σ₁ sets representable — transfers directly.


Imported result Used in Source
Rosser system; ≤‑race; "extension of (R) ⟹ Rosser system"; Ω₄, Ω₅ Parts I, IV (Thm 1), V 08‑03 Lemma S / Thm 3
represents vs separates; P*, R*; enumeration clauses Parts II, III 07‑30, 08‑03
P is Σ₁ from axiomatizability; Σ₁ closure Part IV (Thm S₁) 07‑29 prelude, 07‑28 Prop C
Σ₀‑completeness ("all true Σ₀ provable"), (R)=Ω₁–Ω₅ Part IV (Thm 1) 07‑31 Theorem B*
simple consistency = "refutable ⟹ not provable" Parts III, IV 07‑29

Book span this session: Smullyan, Gödel's Incompleteness Theorems, Ch. VII, pp. 86–96 — §1 (Thm S₁, Thm 1; weak separation; the function Π; Lemma 1, Lemma 1*, Discussion, Ex 1), §2 (Lemma 2, Lemma 2*, Thm S₂, Thm 2, Ex 2–3), §3 (Thm 3 + Cor, Ex 4–10), §4 (Thm S₁*, S₂*, Ex 11).


What's ahead

  • Chapter VII drills still open: Exercises 4–10 (§3 variants, each a short engine application); Exercise 11 (proving the starred S₁*, S₂*). (Both tracks are now fully proved — representation in Part IV, separation in Part V.3–V.4, the latter with the four‑row abstract proof that closes Smullyan's "left to the reader" clause (2).) These exercises are the direct continuation.
  • Still owed from Ch. V: §6 Ex 10–12 (the P(X̄) provability predicate; Ex 11's full Σ₁ case deferred to Boolos) — the Σ₁‑completeness debt; and Chapter 9's Second Theorem (why "G is true" is not P.A.‑formalizable).
  • The sequel's comparison (flagged on p. 86): Shepherdson's proof vs. the original Ehrenfeucht–Feferman route — "very different, generalizing in apparently incomparable directions." Worth revisiting once the separation track is fully drilled.

Prior session files: 07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 · 08‑03 · 08‑04 (this file).