Gui Ruiyan

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

Study journals · Undated 未注日期

Gödel's Incompleteness Theorems — **Master Reference & Conceptual Roadmap**

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 / 篇目

Built from my own concepts up to the Five Abstract Theorems (Ch. XI §II, pp. 126–127) — and the whole book they compress

This is the personal quick‑access map for the whole study. It starts from concepts I already own (possible world, A=A, "all true statements"), derives the technical definitions from them, then explains the semantic engine (aliens, impostors, the Gödel sentence) before laying out the five theorems, the abstract↔concrete dictionary, and a glossary→session jump index. If I forget something, I come here first.


How to use this doc

  1. Forgot what a technical definition means? → Part I (my concepts → valuation set / tautology / truth set, full build).
  2. Forgot why the Gödel sentence is true‑but‑unprovable, or what an "alien / fake proof" is? → Part II (the semantic engine).
  3. Forgot a result? → Part IV (the Five Theorems: statement + concrete counterpart + where it's proved).
  4. Forgot a word? (represent vs. express, ω‑ vs. simple consistency, Σ₀, Rosser system…) → Part VI (glossary → session pointer).
  5. Forgot the abstract↔real map? → Part V (dictionary). Just want "reread ___"? → Part VII.

Two vocabularies, one subject — read this once. This study runs on two layers of naming, and keeping them straight is half the battle: - Abstract (Ch. XI §II) names — type 1, normal, stable, Rosser mapping, valuation set, truth set. These are the packaging vocabulary of the book's final abstract chapter. They appear in Parts I, III, IV, V of this doc but not in my dated session notes. - Concrete (Ch. II–IX) names — the words my session docs actually use: survivor / interpretation, Rosser system, ω‑consistency, impostor, correct (= sound).

Every abstract name has a concrete twin; the twins are lined up in the Part V dictionary. When this doc uses an abstract name it links back to where the twin is defined. In particular: valuation set ↔ interpretation, truth set ↔ the true sentences of ℕ, stable ↔ ω‑consistency, Rosser mapping ↔ Rosser system, correct = the session docs' word for "sound." (This doc uses correct/correctness, matching the session docs; a few early docs said "sound" — same thing.)


Part I — The ground floor: my concepts → the technical definitions

0. The three shelves (fix this first — everything downstream needs it)

Keep three kinds of thing on separate shelves. Confusing them is the source of every muddle:

shelf what lives there examples
objects (numbers) elements of a world's domain genuine numbers 0,1,2,…; in impostor worlds, aliens (counterfeit numbers)
sentences statements that are true or false "X is provable", "0=1", the Gödel sentence
proofs finite step‑by‑step derivations; each is coded by a number an actual written derivation of 0=0
  • provable ≠ true. This is the cardinal distinction the whole book rests on. "Provable" = a real finite derivation exists (a proof shelf + object shelf fact). "True" = holds in a world (a sentence shelf fact). Conflating them is the exact error Tarski + Gödel destroy.
  • An alien is an object — a counterfeit number. A fake proof = an alien playing the role of a proof‑code. (Full treatment in Part II.)

1. My "possible world" ⟶ valuation set V

  • My concept: a way things could be — maybe counterfactual — where logic still holds, so I can reason inside it.
  • Each world gives every statement a definite true/false. Record the true ones as a list V. That's a "valuation set" — the true‑list of one possible world. (Listing only truths loses nothing: a false "it rains" shows up as the true "it doesn't rain.")
  • "Logic holds" needs only two rules — and two suffice for all of logic, because the other logic‑words are abbreviations: or = "if not‑X then Y", and = "not(not‑X or not‑Y)", iff = "(if X then Y) and (if Y then X)". Get not and if‑then right and every connective is right for free (like: fix shift + letter and you've got capitals).
  • Written out: falsehood isn't true (f ∉ V) and "if X then Y" is true unless X true & Y false (X⊃Y ∈ V ⟺ X∉V or Y∈V). Negation ~X := X⊃f then comes out genuine (~X∈V ⟺ X∉V).

valuation set = the true‑list of one possible world; its two clauses just are "logic holds here."

Session‑doc twin: my dated notes call a world an interpretation, and one that happens to make all the axioms true a survivor (an "impostor" is then just a survivor that isn't a copy of ℕ — Part II). So possible world → valuation set (abstract) → interpretation / survivor (session‑doc word). Same object, three names.

2. My "reducible to A=A" ⟶ tautology

  • My concept: a dressed‑up A=A — necessarily, emptily true, saying nothing about the world.
  • A=A is true in every world — rain, shine, counterfactual — no fact ever consulted. Anything with that trait is a tautology; anything false in even one world genuinely says something.
  • "True in every world" = "on every world's true‑list" = "in every valuation set."

tautology = in every valuation set = true‑no‑matter‑what = my A=A. (Not every tautology literally spells A=A — e.g. "raining or not raining" — but each shares its one trait: false in no world. Session docs also say logically valid for this.)

3. My "set of all true statements" ⟶ truth set T — derived twice

3a. From "the real world"

Every world has its own true‑list, so "all true statements" needs a true where. The truth set T is the actual world's true‑list = the standard numbers ℕ. One added clause: the setting carries the special operator B ("is provable"); for T to be the genuine real world it must report that word truthfully — BX true ⟺ X really provable. (This truthful‑box condition is what the 08‑06 doc names a correct provability predicate: P expresses provability.)

3b. From the aliens (the sharper derivation — see Part II for the alien picture)

  • Impostor worlds differ from ℕ only by containing aliens (counterfeit numbers).
  • An alien can corrupt a truth only through an existential "∃x…" — by serving as a fake witness.
  • "X is provable" is such an existential: "∃y : y codes a proof of X." So aliens strike exactly the provability‑sentences BX.
  • To pick out the worlds not fooled by aliens about proving, demand the verdict rest on a genuine proof: BX true ⟺ X really provable. Same clause as 3a.

truth set T = "a world no alien can trick into thinking something is provable when it isn't." ℕ (no aliens at all) qualifies automatically. The nontrivial half is BX true ⟹ X provable = "no fake witnesses." (Coda: to call a witness "an alien" you already use the pre‑formal notion of finite — the definition bottoms out there; see Part II.)


Part II — The semantic engine: aliens, impostors, and the Gödel sentence

Provability is syntactic — the same in every world

"X is provable" means a finite derivation from the axioms exists — checked by exhibiting the proof and having a clerk verify each step. No world, no meaning enters. So provability is the same fact in every interpretation. Two consequences: - A real proof carries to every world: if X has a genuine proof, X is true in every survivor of the axioms. - Contrapositive: X false in some world ⟹ X has no real proof ⟹ unprovable.

Who the alien is (fix this before anything)

An impostor = a survivor of the axioms that is not a copy of ℕ: its domain carries extra objects — aliens — sitting past the reachable ladder 0, 0′, 0″, …, never reached from 0 in finitely many steps (the 07‑24 "alien world M*"; only second‑order induction / Dedekind categoricity rules them out, which first‑order logic cannot do). (In standard model‑theory jargon an impostor is a "non‑standard model"; my session docs never use that phrase — they say impostor, survivor, alien world.)

  • The alien is an object — a counterfeit number. Not a proof, not a truth.
  • A fake proof = an alien read as a proof‑code → a pseudo‑derivation of infinite length, a counterfeit that can never be produced.

First — the corrected recap (the direction that trips everyone)

The natural first phrasing is "having an impostor necessitates a falsehood in it." That's the one link to correct. Impostor‑hood alone forces no falsehood: non‑standard models of true arithmetic agree with ℕ on every sentence (aliens present, zero falsehoods). The arrow runs the other way:

G is true‑in‑ℕ and unprovable ⟹ G isn't forced by the axioms ⟹ some impostor makes G false. Unprovability conjures the falsifying impostor. The falsehood comes first and summons the world — it is not that "having an impostor" produces a falsehood.

With that one link fixed, the rest of the recap is exactly right: in that impostor G can be false only if it "asserts it is provable," so it falsely claims a proof — really unprovable, only "provable" in the degenerate, fake‑witness sense. The next two boxes are why.

Two different things impostors do (opposite directions, different sentences)

Phenomenon A — an unprovable truth is voted false (independence). G is true in ℕ, false in some impostor. Why can they disagree? Because the axioms don't decide G — its truth‑value is left free, so different survivors vote differently. Concerns an ordinary sentence (G). Direction: ℕ true → impostor false. (No fake proof needed to state this — it's pure independence.)

Phenomenon B — a provability‑claim is made true by an alien (fake proof). The sentence "X is provable" — BX — is the existential "∃y : y codes a proof of X." In an impostor an alien y can witness that ∃, making BX true even when X has no real proof. Concerns a provability‑sentence (BX). Direction: ℕ false → impostor true.

So "an unprovable truth" (A) and "an alien fake‑proof" (B) are not the same thing in general — they point in opposite directions and touch different sentences. That gap is the usual source of unease. They coincide only at one special place ↓.

Where A and B MEET — at the Gödel sentence

They coincide exactly at G, because of what G says: G ≡ ¬BG, "I am not provable." Watch the bookkeeping:

sentence ℕ (real world) the impostor that falsifies it
G ≡ ¬BG G true, BG false — no proof of G G false, BG true — an alien fake‑proof of G
consis ≡ ¬Bf consis true, Bf false — no proof of 0=1 consis false, Bf true — an alien fake‑proof of 0=1

Read the impostor column. To make G false (Phenomenon A), the impostor must make ¬BG false, i.e. make BG true — i.e. believe G is provable (Phenomenon B). But G has no real proof, so the only witness available is an alien.

At G, Phenomenon A is caused by Phenomenon B: the impostor falsifies the unprovable truth G precisely by hosting an alien fake‑proof of it. The "truth that isn't derivable" and the "alien proof" are two descriptions of one event — welded by the fact that G literally says "I have no proof." Falsifying "I have no proof" = hallucinating a proof = an alien. No contradiction with unprovability: the real proof never exists in any world; the impostor is simply incorrect (unsound), believing a falsehood provable on a counterfeit that cannot be produced.

Scope — which sentences behave this way

The tight "false ⟺ self‑asserts‑provable" linkage holds only for sentences of the form ¬P(σ) ("σ is not provable"):

sentence true‑but‑unprovable? a Gödel sentence? false in some impostor? falsified by a fake proof?
G = "I'm unprovable" yes yes (self‑ref ¬P(⌜G⌝)) yes yes (fake proof of G)
consis = "0=1 unprovable" yes no (but shape ¬P(σ)) yes yes (fake proof of 0=1)
Goodstein / Paris–Harrington yes no (no self‑ref, no P) yes no — just voted false
  • "false in some impostor" is universal — every unprovable sentence is (completeness run backwards).
  • "falsified by a fake proof" is special — only the ¬P(σ) family; the Gödel sentence is the self‑referential archetype (σ = itself). Generic independent truths (Goodstein) are simply voted false, no fake proof involved.
  • So: not every true‑but‑unprovable sentence is a Gödel sentence; Gödel sentences are one self‑referential species of a much wider class.

The circularity coda (where it all bottoms out)

To call an impostor's proof "fake," I use the pre‑formal notion of actually finite / actually writable — which is the standard naturals. First‑order logic cannot pin ℕ down (impostors always exist). Second‑order induction can (Dedekind: only survivors are copies of ℕ) — but only by presupposing "all subsets," a commitment as strong as "the standard finite." So singling out the real world is always an act of standing on a pre‑formal totality the system can't itself certify. Not a vicious circle — a floor. Reassurance: none of the theorems need this resolved. Provability/unprovability is syntactic and robust; "G is true" needs only some correct honest world, not a uniquely‑pinned ℕ. → 08‑06 (the aliens/circularity exchange), 07‑24 (Dedekind, categoricity, alien world).


Part III — The abstract machine M (Ch. XI's five ingredients + the type ladder)

Smullyan's final move: an abstract provability system M — nothing arithmetical anywhere.

# ingredient what it is concrete meaning (in a first‑order S)
1 S (a set) the "sentences"/"propositions" the sentences of the theory
2 f "falsehood" a refutable sentence, 0=1
3 ⊃ binary operation X⊃Y material implication
4 provable elements a distinguished subset the theorems
5 B map X ↦ BX the box / provability predicate: BX = P(⌜X⌝) = "X is provable"

Derived inside M: ~X := X⊃f; valuation set (Part I.1); tautology (Part I.2); truth set T (Part I.3).

The property ladder (the hypotheses the theorems switch on/off), with plain glosses

property abstract definition in my words bridge — why the two are the same powers
type 1 provable set ⊇ tautologies, closed under modus ponens "it knows basic logic" tautologies = the logic‑truths (Part I.2: true in every world); "closed under MP" = the one inference rule "have X and X⊃Y → get Y." All logic‑truths + that rule = exactly "closed under logic." T2, T3 (assumed by T4,T5)
normal X prov ⟹ BX prov "when it proves a thing, it can prove that it proved it" (P₁ / D1, necessitation) BX just means "X is provable" (the box, Part 0). So the clause reads word‑for‑word: "X is a theorem ⟹ 'X is a theorem' is a theorem." This is one direction only (necessitation) — not the biconditional "represents." T2, T4, T5
stable ⊢BX ⟹ ⊢X (a meta‑rule about the bare claim BX) "never claims provable unless it is" (no bluff) — a property the system has the converse of normal: if it proves the bare claim "X is provable," a real proof exists — i.e. no alien fake‑proof at the theorem level (Part II, Phenomenon B ruled out inside S). This is the abstract stand‑in for ω‑consistency — why they're the same ban is spelled out in the concrete‑premises table, T2 row. Don't confuse with Löb (T5): stable is about BX; Löb is about the conditional BX⊃X — see the Löb ≠ stability note. T2 (part 2)
consistent f not provable "never proves a flat contradiction" f = 0=1 = falsehood; proving it = a contradiction, and by explosion = proving everything. So "f unprovable" = "doesn't collapse into proving all." = simple consistency. T3, T4
Rosser mapping Q X prov ⟹ QX prov; ~X prov ⟹ ~QX prov "the ≤‑race machinery" (concretely: a Rosser system) the two clauses are the two halves of the proof‑vs‑refutation race (ρ): provability rides through Q, refutability through ~Q — exactly what lets a self‑referential X≡QX dodge both on simple consistency. T3
type 4 P₁ + P₂(B(X⊃Y)⊃(BX⊃BY)) + P₃(BX⊃BBX) "reasons about its own proving, honestly" P₁ = necessitation (D1); P₂ = "it knows modus ponens holds of its own proofs" (D2); P₃ = "it can prove that it proves whatever it proves" (D3, provable Σ₁‑completeness). Together = a complete, honest internal theory of its own provability. T4, T5

The ladder in one line: each theorem is "how little you can assume." Gödel (T2) = normal + type 1; Rosser (T3) trades stability for a Rosser mapping → runs on bare consistency; Second Theorem & Löb (T4, T5) need the full type 4 box‑laws. Notice stable = the same "no alien fake‑proof" idea from Part II, now as a property of the system.


Part IV — The Five Theorems (the compression of the entire book)

# after… abstract hypotheses conclusion in my words review
1 Tarski–Gödel truth set T ⊇ provable; X ≡ ~BX in T neither X nor ~X provable — yet X true "if it proves only truths, 'I'm unprovable' is true but out of reach" Ch. II; 08‑05 §5
2 Gödel normal, type 1; G ≡ ~BG provable (1) G prov ⟹ inconsistent; (2) ~G prov ⟹ inconsistent or unstable "unless it bluffs about proofs, 'I'm unprovable' can't be proved or disproved" 07‑30, 07‑31
3 Rosser type 1; Rosser mapping Q; X ≡ QX provable; consistent neither X nor ~X provable "same unreachable statement from only 'never proves a contradiction'" 08‑03
4 Gödel II type 4; G ≡ ~BG provable; consistent consis (= ~Bf) not provable "if it can reason about proving, it can't prove 'I never prove a falsehood'" 08‑06
5 Löb type 4; BX ⊃ X provable; Y ≡ (BY ⊃ X) provable X provable "it can prove the reflection promise BX⊃X ('if I could prove X, then X') only when X is already a theorem — so it can't certify its own non‑bluffing" (≠ stable) 08‑06

Abstract hypotheses ⟶ concrete premises on S (what each theorem really assumes)

Each abstract hypothesis is a property from the ladder; here is the arithmetic premise it becomes when you feed the machine a real system S.

thm abstract hypothesis concrete premise on S
1 a truth set T exists the standard model ℕ, with P expressing provability (P(⌜X⌝) true ⟺ X provable) — a correct provability predicate (08‑06 sense)
every provable element ∈ T S is correct (sound) — a subsystem of ℕ; every theorem is true in ℕ
X ≡ ~BX in T the Gödel sentence G ≡ ¬P(⌜G⌝) exists (fixed‑point lemma) and is true in ℕ
2 type 1 S is closed under first‑order logic
normal D1 / necessitation: ⊢X ⟹ ⊢P(⌜X⌝) (a one‑way rule; holds because P is Σ₁ and S is Σ₁‑complete)
G ≡ ~BG provable fixed‑point lemma gives S ⊢ G ≡ ¬P(⌜G⌝)
stable — abstractly ⊢BX ⟹ ⊢X; needed only for part 2 (unrefutability of G) S is ω‑consistent — why stable ≈ ω‑consistent is unpacked right below the table ↓
3 type 1 first‑order logic
Rosser mapping Q S is a Rosser system — e.g. an extension of (R): has Ω₄,Ω₅ and is Σ₀‑complete, enough to run the ≤‑race
X ≡ QX provable the Rosser sentence ρ exists (fixed point of the ≤‑race)
consistent S is simply consistent
4 type 4 P satisfies the derivability conditions D1, D2, D3 (P.A.'s standard provability predicate)
G ≡ ~BG provable the Gödel fixed point (fixed‑point lemma)
consistent simple consistency; the conclusion ~Bf is consis = Con(S) = ¬P(⌜0=1⌝)
5 type 4 P satisfies D1, D2, D3
BX ⊃ X provable the reflection sentence P(⌜X⌝) ⊃ X is a theorem of S (X = the target sentence)
Y ≡ (BY ⊃ X) provable the Curry/Löb helper fixed point exists (diagonalization)

(Reading tip: the left column is what Ch. XI states abstractly; the right column is what it means for P.A. or (R) or (Q). The whole point of Ch. XI is that proving the theorems once, abstractly, discharges every concrete case at once.)

Why stable ≈ ω‑consistency (the one that looks bizarre). They're stated in different languages but are the same ban, in three steps: 1. The box is an existential. BX = ∃p Prf(p,⌜X⌝) — "some number p codes a proof of X." 2. What each side forbids. stable = ⊢BX ⟹ ⊢X (can't prove "a proof exists" without a real proof). ω‑consistency = never ⊢∃x F(x) while ⊢¬F(0),¬F(1),… for every numeral (can't assert an existential while refuting each instance). 3. They collapse. If X is unprovable, no number is a proof, so S⊢¬Prf(n̄,⌜X⌝) for every n̄ (Σ₀‑completeness). Then ⊢BX would be exactly the forbidden ω‑inconsistent shape. So ω‑consistent ⟹ (⊢BX ⟹ ⊢X) = stable.

So stable is just ω‑consistency aimed at the single predicate Prf — ω bans the pattern for every F, stability needs it only for F = Prf. That's why "roughly," not exactly, equal. Alien reading: a fake proof is a non‑standard p witnessing ∃p Prf with no real proof, so stable = "no alien fake‑proof," ω = "no alien witness for any ∃."

Theorem 1 (Tarski–Gödel, semantic). X ≡ ~BX is the Gödel sentence read in a world. Hypothesis = correctness (every provable element true). If X provable → true yet says unprovable (contradiction); if ~X provable → X true → undecidable and true. Also = Tarski's undefinability of truth. → 08‑05 §5.

Theorem 2 (Gödel, syntactic). Part (1) = unprovable from simple consistency (uses normal). Part (2) = unrefutable needs stability (abstract ω‑consistency; unstable = proves BG without proving G = the alien‑fake‑proof pathology). Memorize the split: unprovable ← consistency; unrefutable ← stability/ω. → 07‑30, 07‑31.

Theorem 3 (Rosser). Drops stability, demands a Rosser mapping (abstract ≤‑race ρ = ∀y[A(x,y)⊃(∃z≤y)B(x,z)], concretely a Rosser system) → undecidability from simple consistency. → 08‑03.

Theorem 4 (Second Theorem). consis = ~Bf = Con(S). Type 4 lets M prove consis ⊃ G (First Theorem internalized); so M⊢consis ⟹ M⊢G, contradicting Thm 2. Engine: (★) ⊢X⊃(BX⊃Y) ⟹ ⊢BX⊃BY (Smullyan's P₆ = P₄+P₂+P₃). Not grounds for doubt: an inconsistent system can self‑certify (proves everything). → 08‑06 §2.

Theorem 5 (Löb). Notation: Smullyan's X = target (our earlier Y); his Y = the Curry/Löb helper (our X). Diagonalize Bv⊃X, push through (★) and P₁, out pops X. Henkin H ≡ BH ("I'm provable") is therefore provable; Second Theorem = Löb at X=f (Kreisel). Curry worry defused (why Löb ≠ "prove anything"): Route A (prove the target) is the only door; Route B ("target unprovable") is the Second Theorem in disguise, shut by explosion. → 08‑06 §3.

Löb ≠ stability (the trap they look identical). Both read "provable ⟹ true," so it's tempting to call Löb "just stability." They're the opposite of the same: - One-line proof they differ: Löb (T5) needs only type 4; stability (T2 part 2) needs ω‑consistency. A theorem you derive and a hypothesis you assume can't be one thing. - Parse the two expressions symbol‑by‑symbol — count the turnstiles. This is where the distinction becomes unmissable: - stability = ⊢BX ⟹ ⊢X — read: "IF the system asserts 'X is provable', THEN the system asserts 'X'." Two turnstiles, two separate assertions, and the link ⟹ between them is ours (metatheory) — the system never joins them. We watch from outside and notice: whenever the first assertion fires, so does the second. - the reflection sentence = ⊢(BX⊃X) — read: "the system asserts, as one sentence, 'if X is provable then X'." One turnstile; the if‑then ⊃ lives inside the system's own sentence. The system itself stitches hypothesis to conclusion and stands behind the whole conditional on its own authority. - So: ⟹ is our arrow between two of the system's claims; ⊃ is the system's own arrow inside one claim. Löb's premise is ⊢(BX⊃X) ⟹ ⊢X — the system utters that single internal conditional, and only then (in our bookkeeping) does ⊢X follow. Same words "if provable then X," but one is a pattern we observe across two turnstiles, the other is one turnstile the system writes itself. Neither rule gives the other. - The real relationship — outside verdict vs. inside self‑testimony (this is the click): - stability = our verdict, reached in the metatheory, standing outside and evaluating the system: "it doesn't bluff" (≈ ω‑consistency). A fact about the system. - the reflection sentence BX⊃X = the exact same content spoken from inside — the system vouching for itself, on its own authority: "if I prove X, then X." (Proving it for every X = the system declaring itself stable.) - Löb = that self‑vouching goes through only for X it has already proved; on anything still open, the system simply cannot say it doesn't bluff. - So the property can be true while the system cannot say or prove it — from inside. And that's no mystery once you see why a system's word about itself is worthless: a system can always lie about its own lying. A system that did bluff would be inconsistent, and an inconsistent system proves everything — including "I don't bluff." So "I never bluff, signed: me" carries zero information: the honest system and the lying one utter it alike, so the utterance can't distinguish them. That gap is Gödel II: Löb at X=f gives Bf⊃f = ~Bf = consis, so ⊢consis ⟹ ⊢f — the system can't vouch even for "I don't prove 0=1." Stability = the outside having it; Löb = the inside can't‑say‑you‑have‑it.


Part V — The dictionary: abstract M ⟷ concrete first‑order S

abstract M (Ch. XI) concrete S / session‑doc word
S (the set) sentences of S
provable elements theorems (⊢)
f (falsehood) a refutable sentence, 0=1
X ⊃ Y, ~X = X⊃f material implication, negation
B, BX provability predicate P(v₁), P(⌜X⌝)
valuation set V a Boolean valuation / an interpretation; one that makes all axioms true = a survivor
tautology logically valid sentence
truth set T the true sentences (the standard model ℕ) — the world no alien can fool about proving
type 1 closed under (first‑order) logic
normal (P₁) necessitation / D1 (⊢X ⟹ ⊢P(X̄), one‑way)
P₂ S ⊢ P(⌜X⊃Y⌝)⊃(P(X̄)⊃P(Ȳ)) / D2
P₃ S ⊢ P(X̄)⊃P(⌜P(X̄)⌝) / D3 (provable Σ₁‑completeness)
type 4 has a provability predicate (D1,D2,D3)
stable ω‑consistency (the session‑doc term); ="no alien fake‑proof" / reflection‑correctness of P — see T2 row for why stable ≈ ω
consistent simple consistency (simply consistent)
Rosser mapping Q a Rosser system — the ≤‑race construction (ρ)
G ≡ ~BG Gödel sentence
H ≡ BH Henkin sentence
Y ≡ (BY⊃X) Curry / Löb helper sentence
consis = ~Bf consis = Con(S) = ¬P(⌜0=1⌝)
alien a counterfeit number in an impostor, past 0,0′,0″,… (model‑theory: a non‑standard element)
fake proof an alien read as a proof‑code (a pseudo‑derivation of non‑standard length)
impostor a survivor of the axioms that isn't a copy of ℕ (model‑theory: a non‑standard model)

Part VI — Concept glossary → where to review

A. The verbs + the cardinal distinction

  • expresses R: F(n̄) true ⟺ n∈R. (truth / semantic) → 07‑30
  • represents R: F(n̄) provable ⟺ n∈R. (proof / syntactic) → 07‑30
  • contrarepresents R: F(n̄) refutable ⟺ n∈R. (the refutation‑side twin of represent; used in exact separation) → 08‑04
  • enumerates R: one‑way, weaker than represent; upgraded via ω‑consistency. → 07‑30
  • defines R (Ch. VIII): separates R from its complement; completely represents = exactly separates = represent + contrarepresent (double representation). → 08‑05 §1, 08‑04
  • provable ≠ true — the cardinal distinction; conflating them is the book's central error. → 08‑06

B. The arithmetic hierarchy & completeness

  • Σ₀ bounded → decidable; Σ₀‑completeness. → 07‑31
  • Σ₁ = ∃‑over‑Σ₀; P is Σ₁. → 07‑30
  • recursive = R and R̄ both Σ₁. → 08‑05
  • three tiers (moral): truth not expressible (Tarski) / provability representable, not definable (Church) / recursive sets definable. → 08‑05

C. Consistency strengths (the axis Rosser moves)

  • simple (f unprovable) — session‑doc term simply consistent; ω (no ∃vφ with all φ(n̄) refuted); correct (proves only truths — the session‑doc word for "sound"). → 08‑03, 07‑30
  • hierarchy correct ⟹ ω ⟹ simple, each strict; abstract stand‑in for ω = stable. → 08‑03 Part X
  • explosion (ex falso): inconsistent ⟹ proves everything ⟹ "one sentence unprovable ⟹ consistent." → 08‑06 §3

D. Self‑reference machinery

  • diagonalization / Gödel numbering; the diagonal d(x). → 07‑24, 08‑05
  • Fixed‑Point Lemma: every F(v₁) has X with S⊢X≡F(X̄). → 08‑05 Thm 4
  • strong vs weak definability: strong = provable uniqueness = puts ≡ under the turnstile. → 08‑05 §2
  • P* (diagonal set) vs honest P. → 08‑05 Part 0

E. Interpretations / survivors / impostors (the semantic layer)

  • interpretation = a world; survivor = an interpretation making all axioms true; impostor = a survivor ≠ ℕ; alien = a counterfeit number in one; fake proof = an alien as proof‑code — Part II above; Dedekind categoricity, second‑order, "alien world M*". → 07‑24, 08‑06
  • correctness vs "box expresses provability" — two separate clauses of a truth set (all‑theorems‑true vs BX‑true‑⟺‑provable). → 08‑06

F. Rosser / representation machinery

  • Rosser system (separates disjoint Σ₁ pairs → incompleteness and representability). → 08‑03, 08‑04
  • the ≤‑race ρ, needs Ω₄,Ω₅. → 08‑03
  • exact separation = double representation. → 08‑04
  • (R),(Q),(R₀),(Q₀),P.A.; (R)=Ω₁–Ω₅; all Σ₀‑complete, all Rosser systems. → 07‑31

G. Provability predicates (Ch. IX / type 4)

  • P₁,P₂,P₃ = D1,D2,D3 (the derivability conditions / box laws); derived P₄ (monotone), (★)/P₆ (engine). → 08‑06 §1
  • consis, Second Theorem, "not grounds for doubt". → 08‑06 §2
  • Löb, Henkin, Kreisel, Kripke, modal logic GL; Curry defused. → 08‑06 §3

Part VII — "If you forget , reread " (fast jump index)

If you're fuzzy on… reread
valuation set / tautology / truth set from my own concepts this doc, Part I
aliens, fake proofs, the Gödel‑falsifying‑impostor picture, the circularity this doc, Part II; 08‑06, 07‑24
M, B, type 1/4, Rosser mapping, why stable ≈ ω this doc, Parts III & V (+ T2 row)
provable vs. true (the cardinal sin) 08‑06
express / represent / contrarepresent / enumerate / define 07‑30, 08‑04, 08‑05 §1
Σ₀ / Σ₁ / recursive / Σ₀‑completeness 07‑31
simple vs ω vs correct; "weaker ⟹ more general" 08‑03 Part X
Gödel G, Theorem A/A*; ω‑incompleteness, P.A.+{~G} 07‑30, 07‑31
Rosser ρ, the ≤‑race, Lemma S 08‑03
Σ₁ representable (Shepherdson), exact separation 08‑04
Fixed‑Point Lemma, strong definability, three tiers, Tarski 08‑05
P₁P₂P₃, (★), Second Theorem, Löb, Curry defusing 08‑06
second‑order logic, Dedekind categoricity, "no adequate machine" 07‑24

The whole book in one breath

Start from a box B on a set with ⊃ and a falsehood f. A world is a coherent true‑list (a valuation set; concretely an interpretation); the real world ℕ is the one no alien (counterfeit number) can trick into a fake proof. Assume just logic (type 1) + necessitation (normal): the self‑referential G ≡ ~BG is undecidable (Gödel, T2) — and true if the world is correct (Tarski–Gödel, T1). It's unprovable because some impostor falsifies it — and, since G says "I have no proof," that impostor falsifies it by an alien fake‑proof of G; the real proof never exists. Trade correctness for a race (Rosser mapping = a Rosser system) → undecidability from bare consistency (Rosser, T3). Add the box‑laws P₂,P₃ (type 4) and B reasons about itself: it almost proves the First Theorem internally — close enough that it cannot prove its own consistency ~Bf (Gödel II, T4), nor any reflection BX⊃X unless X was already provable (Löb, T5). The Second Theorem is just Löb pointed at f.

Series: 07‑15 · 07‑17 · 07‑19 · 07‑20 · 07‑21 · 07‑22 · 07‑23 · 07‑24 · 07‑26 · 07‑27 · 07‑28 · 07‑29 · 07‑30 · 07‑31 · 08‑03 · 08‑04 · 08‑05 · 08‑06 · Master Reference (this file).