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
- How to use this doc
- 0. The three shelves (fix this first — everything downstream needs it)
- 1. My "possible world" ⟶ valuation set V
- 2. My "reducible to A=A" ⟶ tautology
- 3. My "set of all true statements" ⟶ truth set T — derived twice
- Provability is syntactic — the same in every world
- Who the alien is (fix this before anything)
- First — the corrected recap (the direction that trips everyone)
- Two different things impostors do (opposite directions, different sentences)
- Where A and B MEET — at the Gödel sentence
- Scope — which sentences behave this way
- The circularity coda (where it all bottoms out)
- The property ladder (the hypotheses the theorems switch on/off), with plain glosses
- Abstract hypotheses ⟶ concrete premises on S (what each theorem really assumes)
- A. The verbs + the cardinal distinction
- B. The arithmetic hierarchy & completeness
- C. Consistency strengths (the axis Rosser moves)
- D. Self‑reference machinery
- E. Interpretations / survivors / impostors (the semantic layer)
- F. Rosser / representation machinery
- G. Provability predicates (Ch. IX / type 4)
- The whole book in one breath
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
- Forgot what a technical definition means? → Part I (my concepts → valuation set / tautology / truth set, full build).
- Forgot why the Gödel sentence is true‑but‑unprovable, or what an "alien / fake proof" is? → Part II (the semantic engine).
- Forgot a result? → Part IV (the Five Theorems: statement + concrete counterpart + where it's proved).
- Forgot a word? (represent vs. express, ω‑ vs. simple consistency, Σ₀, Rosser system…) → Part VI (glossary → session pointer).
- 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⊃fthen 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=Ais 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 spellsA=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. - "
Xis provable" is such an existential: "∃y : y codes a proof of X." So aliens strike exactly the provability‑sentencesBX. - To pick out the worlds not fooled by aliens about proving, demand the verdict rest on a genuine proof:
BXtrue ⟺Xreally 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 isBXtrue ⟹Xprovable = "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:
Gis true‑in‑ℕand unprovable ⟹Gisn't forced by the axioms ⟹ some impostor makesGfalse. 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 truthGprecisely 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 thatGliterally 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 numberpcodes a proof ofX." 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. IfXis unprovable, no number is a proof, soS⊢¬Prf(n̄,⌜X⌝)for everyn̄(Σ₀‑completeness). Then⊢BXwould 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 everyF, stability needs it only forF = Prf. That's why "roughly," not exactly, equal. Alien reading: a fake proof is a non‑standardpwitnessing∃p Prfwith 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⊢Xfollow. 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 sentenceBX⊃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 everyX= the system declaring itself stable.) - Löb = that self‑vouching goes through only forXit 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 atX=fgivesBf⊃f = ~Bf = consis, so⊢consis ⟹ ⊢f— the system can't vouch even for "I don't prove0=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): separatesRfrom 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‑Σ₀;Pis Σ₁. → 07‑30 - recursive =
RandR̄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 (
funprovable) — 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₁)hasXwithS⊢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 honestP. → 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 worldM*". → 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); derivedP₄(monotone),(★)/P₆(engine). → 08‑06 §1consis, 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
Bon a set with⊃and a falsehoodf. 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‑referentialG ≡ ~BGis undecidable (Gödel, T2) — and true if the world is correct (Tarski–Gödel, T1). It's unprovable because some impostor falsifies it — and, sinceGsays "I have no proof," that impostor falsifies it by an alien fake‑proof ofG; the real proof never exists. Trade correctness for a race (Rosser mapping = a Rosser system) → undecidability from bare consistency (Rosser, T3). Add the box‑lawsP₂,P₃(type 4) andBreasons 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 reflectionBX⊃XunlessXwas already provable (Löb, T5). The Second Theorem is just Löb pointed atf.
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).
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
从我自己的概念出发,抵达五个抽象定理(第十一章§II,第126–127页),以及它们压缩的整本书
这是整项学习的个人速查图。从我已有的概念(可能世界、A=A、“全部真陈述”)出发,推导技术定义,再说明语义机制(异类、冒牌者、哥德尔语句),之后列出五个定理、抽象↔具体词典,以及术语→学习记录的跳转索引。忘记什么时,先来这里。
如何使用本文
- 忘记某个技术定义的意义?→第一部分(我的概念→赋值集/重言式/真集,完整构建)。
- 忘记哥德尔语句为什么真而不可证明,或“异类/伪证明”是什么?→第二部分(语义机制)。
- 忘记某个结果?→第四部分(五个定理:陈述+具体对应+证明位置)。
- 忘记某个词?(表示与表达、ω一致与简单一致、Σ₀、罗瑟系统……)→第六部分(术语表→学习记录)。
- 忘记抽象↔实际的对应?→第五部分(词典)。只想知道“重读哪里”?→第七部分。
两套词汇,一个主题,请先读一遍。这项学习有两个命名层次,分清它们就是成功的一半: - 抽象名称(第十一章§II):
第一类(type 1)、正规(normal)、稳定(stable)、罗瑟映射、赋值集、真集。这是全书最后抽象章节的打包词汇,出现在本文第一、三、四、五部分,却不出现在按日期记录的学习笔记中。 - 具体名称(第二至第九章):学习记录实际使用的词:幸存者/解释、罗瑟系统、ω一致性、冒牌者、正确(=可靠)。每个抽象名称都有具体孪生者,它们在第五部分词典中对齐。本文使用抽象名称时,会链接回其孪生者的定义。尤其注意:赋值集↔解释、真集↔
ℕ的真语句、稳定↔ω一致性、罗瑟映射↔罗瑟系统、正确=学习记录中“可靠”的叫法。(本文用正确/正确性,与学习记录一致;早期少数记录用“可靠”,是同一回事。)
第一部分——底层:我的概念→技术定义
0. 三个层架(先固定这一点,后面全要用)
把三类东西放在不同层架。混淆它们,是一切混乱的来源:
| 层架 | 放什么 | 例子 |
|---|---|---|
| 对象(数) | 世界论域的元素 | 真正的数0,1,2,…;冒牌世界里的异类(假冒的数) |
| 语句 | 真或假的陈述 | “X可证明”、“0=1”、哥德尔语句 |
| 证明 | 有限的逐步推导,每个都被一个数编码 | 实际写出的0=0推导 |
- 可证明≠真。这是整本书所依赖的首要区分。“可证明”=存在真正的有限推导(证明层架+对象层架的事实)。“真”=在一个世界中成立(语句层架的事实)。混同两者,恰是塔斯基与哥德尔所摧毁的错误。
- 异类是对象,即假冒的数。伪证明=一个扮演证明编码的异类。(第二部分完整处理。)
1. 我的“可能世界”⟶赋值集V
- 我的概念:事物可能如此的一种方式,也许反事实,但逻辑仍成立,因此能在其中推理。
- 每个世界给每条陈述确定的真/假。把真的记录成清单
V,这就是“赋值集”,即一个可能世界的真清单。(只列真不损失什么:“下雨”是假,就会以“不下雨”为真出现。) - “逻辑成立”只需两条规则,两条就足以涵盖全部逻辑,因为其他逻辑词都是缩写:
或=“若非X,则Y”;且=“非(非X或非Y)”;当且仅当=“(若X则Y)且(若Y则X)”。把非与如果—那么弄对,所有联结词就免费正确(类似固定shift+字母,就有了大写)。 - 写出来:假不为真(
f ∉ V);“若X则Y”总真,除非X真而Y假(X⊃Y ∈ V ⟺ X∉V或Y∈V)。于是,否定~X := X⊃f就成为真正的否定(~X∈V ⟺ X∉V)。
赋值集=一个可能世界的真清单;两项条款就是“这里逻辑成立”。
学习记录中的孪生者:按日期的笔记把世界叫作解释,恰好让所有公理为真的解释叫作幸存者(“冒牌者”就是不是
ℕ副本的幸存者,见第二部分)。所以,可能世界→赋值集(抽象)→解释/幸存者(学习记录用语)。同一对象,三个名称。
2. 我的“可还原为A=A”⟶重言式
- 我的概念:装扮过的
A=A,必然、空洞地为真,不说世界的任何事情。 A=A在每个世界都真,无论雨天、晴天、反事实,都不查询任何事实。有这个特征的就是重言式;哪怕在一个世界为假,就确实说了些什么。- “每个世界都真”=“在每个世界的真清单上”=“属于每个赋值集”。
重言式=属于每个赋值集=无论如何都真=我的
A=A。(不是每个重言式都字面写成A=A,例如“下雨或不下雨”;但它们共享一个特征:不在任何世界为假。学习记录也把这叫作逻辑有效。)
3. 我的“全部真陈述的集合”⟶真集T,推导两次
3a. 从“真实世界”出发
每个世界都有自己的真清单,所以“全部真陈述”需要说明在哪里真。真集T是实际世界的真清单,即标准数ℕ。再加一项:这里有特殊算子B(“可证明”);要使T成为真正的真实世界,它必须如实报告这个词,BX真⟺X确实可证明。(这种如实盒条件,就是8月6日记录所称正确的可证明性谓词:P表达可证明性。)
3b. 从异类出发(更尖锐的推导,异类图景见第二部分)
- 冒牌世界与
ℕ的区别,只在于含有异类,即假冒的数。 - 异类只能通过存在句“
∃x…”破坏一个真,充当伪见证。 - “
X可证明”就是这样的存在句:“∃y:y编码X的一个证明”。因此异类恰好攻击可证明性语句BX。 - 要挑出在证明问题上不被异类欺骗的世界,就要求判断建立在真正证明上:
BX真⟺X确实可证明。与3a同一条款。
真集
T=“没有异类能让它误以为不可证明者可证明的世界”。ℕ完全没有异类,自动合格。非平凡的一半是BX真⟹X可证明,即“没有伪见证”。(尾声:把一个见证称作“异类”,已经使用前形式的有限概念,定义在这里触底,见第二部分。)
第二部分——语义机制:异类、冒牌者与哥德尔语句
可证明性是句法性的,在每个世界都相同
“X可证明”意指存在从公理出发的有限推导,通过展示证明、让检查员逐步验证来检验。没有世界或意义介入。因此,可证明性是在每个解释中都相同的事实。两个后果:
- 真正证明传到每个世界:如果X有真正证明,X就在公理的每个幸存者中为真。
- 逆否:X在某个世界为假⟹X没有真正证明⟹不可证明。
异类是谁(先解决这个)
冒牌者(impostor)=公理的某个幸存者,却不是ℕ的副本。其论域带有额外对象,即异类(aliens),位于可达阶梯0, 0′, 0″, …之外,从0出发有限步永远到不了(7月24日的“异类世界M*”;只有二阶归纳/戴德金范畴性能排除它们,一阶逻辑做不到)。(标准模型论术语称冒牌者为“非标准模型”;我的学习记录从不用这个词,而说冒牌者、幸存者、异类世界。)
- 异类是对象,是假冒的数。不是证明,不是真。
- 伪证明=被读作证明编码的异类→无穷长度的伪推导,一种永远无法实际产出的假冒品。
首先,纠正后的回顾(人人容易绊倒的方向)
自然的初始说法是“有冒牌者,就必然有其中的假”。要纠正的恰好就是这一环。仅仅是冒牌者,并不迫使任何假:真算术的非标准模型在每条语句上都与ℕ一致(有异类,零个假)。箭头走反方向:
G在ℕ中真且不可证明⟹公理不强制G⟹某个冒牌者使G假。不可证明性召出使它为假的冒牌者。假在先,召来世界;不是“有冒牌者”便产生假。
修复这一环,其余回顾完全正确:在那个冒牌者中,G只有在“断言自己可证明”时才可能为假,所以它错误地声称有证明:实际上不可证明,只在退化的伪见证意义上“可证明”。下面两框说明为什么。
冒牌者做的两件不同事情(方向相反,语句不同)
现象A:不可证明的真被投票判为假(独立性)。
G在ℕ中真,在某个冒牌者中假。为什么能不同意?因为公理不决定G,它的真值保持自由,不同幸存者投不同票。涉及普通语句(G)。方向:*ℕ中真→冒牌者中假。(陈述此事不需要伪证明,这只是独立性。)*
现象B:可证明性主张被异类弄成真(伪证明)。
语句“X可证明”,即BX,是存在句“∃y:y编码X的一个证明”。在冒牌者中,异类y能见证这个∃,使BX真,即便X没有真正证明。涉及可证明性语句(BX)。方向:ℕ中假→冒牌者中真。
所以,“不可证明的真”(A)与“异类伪证明”(B)一般不是同一回事,它们指向相反方向,触及不同语句。这一间隙通常是不安的来源。它们只在一个特殊地方重合↓。
A与B在哪里相遇:哥德尔语句
它们恰好在G处重合,因为G说:G ≡ ¬BG,“我不可证明”。看这份记账:
| 语句 | ℕ(真实世界) |
使它为假的冒牌者 |
|---|---|---|
G ≡ ¬BG |
G真、BG假,没有G的证明 |
G假、BG真,有G的异类伪证明 |
consis ≡ ¬Bf |
consis真、Bf假,没有0=1的证明 |
consis假、Bf真,有0=1的异类伪证明 |
读冒牌者那列。要使G假(现象A),冒牌者必须使¬BG假,即使BG真,即相信G可证明(现象B)。但G没有真正证明,唯一可用见证就是异类。
在
G处,现象A由现象B造成:冒牌者恰好通过容纳G的异类伪证明,使不可证明的真G为假。“不可推导的真”与“异类证明”是同一事件的两种描述,因为G字面说“我没有证明”,两者便焊在一起。使“我没有证明”为假=幻觉出一个证明=异类。不与不可证明性矛盾:真正证明从不在任何世界存在;冒牌者只是不正确(不可靠),依据无法产出的假冒品,相信某个假可证明。
范围:哪些语句这样运作
紧密的“假⟺自称可证明”联系,只适用于形式为¬P(σ)(“σ不可证明”)的语句:
| 语句 | 真而不可证明? | 哥德尔语句? | 在某个冒牌者中假? | 通过伪证明而为假? |
|---|---|---|---|---|
G=“我不可证明” |
是 | 是(自指¬P(⌜G⌝)) |
是 | 是(G的伪证明) |
consis=“0=1不可证明” |
是 | 否(但形式为¬P(σ)) |
是 | 是(0=1的伪证明) |
| 古德斯坦/帕里斯–哈林顿 | 是 | 否(无自指,无P) |
是 | 否,只是被投票判假 |
- “在某个冒牌者中假”是普遍的,每个不可证明语句都如此(反向运用完备性)。
- “通过伪证明而为假”是特殊的,只限于
¬P(σ)家族;哥德尔语句是自指原型(σ=自身)。一般的独立真(古德斯坦)只被投票判假,不涉及伪证明。 - 所以,不是每个真而不可证明的语句都是哥德尔语句;哥德尔语句只是更广泛类别中的一种自指种类。
循环性的尾声(一切触底之处)
把冒牌者的证明称为“伪”,我使用的是前形式的实际有限/实际可写概念,也就是标准自然数。一阶逻辑不能钉住ℕ(冒牌者总存在);二阶归纳能(戴德金:仅有的幸存者是ℕ的副本),但必须预设“所有子集”,这个承诺与“标准有限”同样强。所以,辨明真实世界始终是在一个系统自身不能认证的前形式总体上立足。不是恶性循环,而是地基。可以放心:所有定理都不需要先解决这个问题。可证明/不可证明是句法性的,稳固;“G真”只需某个正确诚实的世界,不必唯一钉住ℕ。→8月6日(异类/循环性讨论)、7月24日(戴德金、范畴性、异类世界)。
第三部分——抽象机器M(第十一章的五种材料与类型阶梯)
斯穆里安最后的动作:抽象可证明性系统M,任何地方都没有算术。
| # | 材料 | 是什么 | 具体意义(一阶S中) |
|---|---|---|---|
| 1 | S(集合) |
“语句”/“命题” | 理论的语句 |
| 2 | f |
“假” | 可反驳语句,0=1 |
| 3 | ⊃ |
二元运算X⊃Y |
实质蕴涵 |
| 4 | 可证明元素 | 指定子集 | 定理 |
| 5 | B |
映射X ↦ BX |
盒算子/可证明性谓词:BX = P(⌜X⌝)=“X可证明” |
在M内导出:~X := X⊃f;赋值集(第一部分1);重言式(第一部分2);真集T(第一部分3)。
性质阶梯(各定理开关的假设),附普通语言解释
| 性质 | 抽象定义 | 用我的话说 | 桥梁:为什么二者相同 | 支持 |
|---|---|---|---|---|
| 第一类 | 可证明集⊇重言式,对肯定前件封闭 | “懂基本逻辑” | 重言式=逻辑真(第一部分2:每个世界都真);“对MP封闭”=一条推理规则“有X与X⊃Y→得到Y”。所有逻辑真加上该规则,恰好就是“对逻辑封闭”。 |
T2、T3(T4、T5预设) |
| 正规 | X可证⟹BX可证 |
“证明某事时,也能证明它证明了某事”(P₁/D1,必然化) |
BX就意指“X可证明”(盒算子,第零部分)。所以条款逐字读作:“X是定理⟹‘X是定理’是定理。”这只是一个方向(必然化),不是“表示”的双条件。 |
T2、T4、T5 |
| 稳定 | ⊢BX ⟹ ⊢X(关于裸主张BX的元规则) |
“除非真可证,否则从不声称可证”(不虚张声势),是系统具有的性质 | 正规的逆方向:若它证明裸主张“X可证明”,则存在真正证明,即定理层面没有异类伪证明(第二部分现象B在S内部被排除)。这是ω一致性的抽象替身;为什么是同一禁令,见具体前提表T2行。别与勒布混淆(T5):稳定谈BX,勒布谈条件句BX⊃X,见勒布≠稳定。 |
T2第二部分 |
| 一致 | f不可证明 |
“绝不证明直接矛盾” | f=0=1=假;证明它=矛盾,由爆炸原理=证明一切。所以“f不可证明”=“不坍塌为证明所有东西”,即简单一致性。 |
T3、T4 |
罗瑟映射Q |
X可证⟹QX可证;~X可证⟹~QX可证 |
“≤竞赛机制”(具体说:罗瑟系统) |
两项条款是证明与反驳竞赛的两半(ρ):可证明性经Q传递,可反驳性经~Q传递,恰好使自指X≡QX能在简单一致性下躲开两者。 |
T3 |
| 第四类 | P₁+P₂(B(X⊃Y)⊃(BX⊃BY))+P₃(BX⊃BBX) |
“诚实地对自己的证明推理” | P₁=必然化(D1);P₂=“知道肯定前件对自己的证明成立”(D2);P₃=“能证明,凡自己证明的,自己都证明了”(D3,可证明的Σ₁完备性)。合起来=关于自身可证明性的完整、诚实的内部理论。 |
T4、T5 |
一行说出阶梯:每个定理都在问“能假设得多弱”。哥德尔(T2)=正规+第一类;罗瑟(T3)用罗瑟映射换掉稳定性,只靠单纯一致性运作;第二定理与勒布(T4、T5)需要完整的第四类盒算子规则。注意,稳定就是第二部分相同的“无异类伪证明”观念,现在作为系统的性质。
第四部分——五个定理(压缩整本书)
| # | 对应 | 抽象假设 | 结论 | 用我的话说 | 复习 |
|---|---|---|---|---|---|
| 1 | 塔斯基–哥德尔 | 真集T⊇可证明者;X ≡ ~BX属于T |
X、~X都不可证明,然而X真 |
“若只证明真,‘我不可证明’就真而不可及” | 第二章;8月5日§5 |
| 2 | 哥德尔 | 正规、第一类;G ≡ ~BG可证明 |
(1)G可证⟹不一致;(2)~G可证⟹不一致或不稳定 |
“除非对证明虚张声势,‘我不可证明’就既不能证明也不能反驳” | 7月30日、7月31日 |
| 3 | 罗瑟 | 第一类;罗瑟映射Q;X ≡ QX可证明;一致 |
X、~X都不可证明 |
“只从‘从不证明矛盾’便得到同样不可及的陈述” | 8月3日 |
| 4 | 哥德尔第二定理 | 第四类;G ≡ ~BG可证明;一致 |
consis(= ~Bf)不可证明 |
“若能对证明推理,就不能证明‘我从不证明假’” | 8月6日 |
| 5 | 勒布 | 第四类;BX ⊃ X可证明;Y ≡ (BY ⊃ X)可证明 |
X可证明 |
“只有X已是定理时,才能证明反思承诺BX⊃X(‘若我能证明X,则X’),所以不能认证自己不虚张声势”(≠稳定) |
8月6日 |
抽象假设⟶关于S的具体前提(每个定理真正假设什么)
每个抽象假设都来自阶梯中的某项性质;给机器输入真正系统S时,它变成以下算术前提。
| 定理 | 抽象假设 | 关于S的具体前提 |
|---|---|---|
| 1 | 存在真集T |
标准模型ℕ,P表达可证明性(P(⌜X⌝)真⟺X可证明),即正确的可证明性谓词(8月6日的意义) |
每个可证明元素∈T |
S正确(可靠),是ℕ的子系统,每个定理在ℕ中真 |
|
X ≡ ~BX属于T |
哥德尔语句G ≡ ¬P(⌜G⌝)存在(不动点引理),且在ℕ中真 |
|
| 2 | 第一类 | S对一阶逻辑封闭 |
| 正规 | D1/必然化:⊢X ⟹ ⊢P(⌜X⌝)(单向规则;成立因为P是Σ₁且S是Σ₁完备的) |
|
G ≡ ~BG可证明 |
不动点引理给出S ⊢ G ≡ ¬P(⌜G⌝) |
|
稳定,抽象地说⊢BX ⟹ ⊢X;仅第二部分需要(G不可反驳) |
Sω一致,稳定≈ω一致的理由在表下展开↓ |
|
| 3 | 第一类 | 一阶逻辑 |
罗瑟映射Q |
S是罗瑟系统,例如(R)的扩张,具有Ω₄,Ω₅且Σ₀完备,足以运行≤竞赛 |
|
X ≡ QX可证明 |
罗瑟语句ρ存在(≤竞赛的不动点) |
|
| 一致 | S简单一致 |
|
| 4 | 第四类 | P满足可推导性条件D1、D2、D3(P.A.的标准可证明性谓词) |
G ≡ ~BG可证明 |
哥德尔不动点(不动点引理) | |
| 一致 | 简单一致性;结论~Bf就是consis = Con(S) = ¬P(⌜0=1⌝) |
|
| 5 | 第四类 | P满足D1、D2、D3 |
BX ⊃ X可证明 |
反思语句P(⌜X⌝) ⊃ X是S的定理(X=目标语句) |
|
Y ≡ (BY ⊃ X)可证明 |
柯里/勒布辅助不动点存在(对角化) |
(阅读提示:左列是第十一章的抽象陈述,右列是对P.A.、(R)或(Q)的意义。第十一章的全部目的,就是抽象地证明一次,便同时完成全部具体情况。)
为什么
稳定≈ω一致性(看起来奇怪的一项)。语言不同,却是同一禁令,分三步: 1. 盒算子是存在句。BX = ∃p Prf(p,⌜X⌝),即“某个数p编码X的证明”。 2. 两侧各禁止什么。稳定=⊢BX ⟹ ⊢X(没有真正证明,不能证明“证明存在”)。ω一致性=绝不一面⊢∃x F(x),一面对每个数码都有⊢¬F(0),¬F(1),…(不能在反驳每个实例时断言存在)。 3. 它们合拢。若X不可证明,没有数是证明,所以对每个n̄,S⊢¬Prf(n̄,⌜X⌝)(Σ₀完备性)。此时⊢BX就恰好是被禁止的ω不一致形式。所以ω一致⟹(⊢BX ⟹ ⊢X)=稳定。所以,稳定只是针对单个谓词
Prf的ω一致性;ω对每个F禁止该模式,稳定只对F = Prf需要它。因此是“大致”而非精确相等。异类读法:伪证明就是一个非标准p,见证∃p Prf却没有真正证明;因此稳定=“没有异类伪证明”,ω=“任何∃都没有异类见证”。
定理1(塔斯基–哥德尔,语义)。X ≡ ~BX是放在世界中读的哥德尔语句。假设=正确性(每个可证明元素真)。若X可证明→真,却说不可证明(矛盾);若~X可证明→X真→不可判定而且真。也就是塔斯基的真不可定义性。→8月5日§5。
定理2(哥德尔,句法)。第(1)部分=由简单一致性得到不可证明(用正规)。第(2)部分=不可反驳需要稳定性(抽象的ω一致性;不稳定=证明BG却不证明G,即异类伪证明的病症)。记住分工:不可证明←一致性;不可反驳←稳定/ω。→7月30日、7月31日。
定理3(罗瑟)。去掉稳定性,要求罗瑟映射(抽象≤竞赛ρ = ∀y[A(x,y)⊃(∃z≤y)B(x,z)],具体为罗瑟系统),由简单一致性得到不可判定性。→8月3日。
定理4(第二定理)。consis = ~Bf=Con(S)。第四类让M证明consis ⊃ G(第一定理内部化);于是M⊢consis⟹M⊢G,与定理2矛盾。引擎:(★) ⊢X⊃(BX⊃Y) ⟹ ⊢BX⊃BY(斯穆里安的P₆=P₄+P₂+P₃)。不是怀疑的理由:不一致系统能自我认证,因为证明一切。→8月6日§2。
定理5(勒布)。记号:斯穆里安的X=目标(先前我们的Y);他的Y=柯里/勒布辅助者(我们的X)。对Bv⊃X对角化,经过(★)与P₁,X就出现。亨金H ≡ BH(“我可证明”)因此可证明;第二定理=X=f时的勒布(克赖塞尔)。化解柯里担忧(为什么勒布≠“证明任何东西”):路线A(证明目标)是唯一的门;路线B(“目标不可证明”)是伪装的第二定理,被爆炸原理封闭。→8月6日§3。
勒布≠稳定(它们看似相同的陷阱)。 两者都读起来像“可证明⟹真”,容易把勒布叫作“就是稳定性”。它们恰恰不同: - 一行证明不同:勒布(T5)只需要第四类;稳定(T2第二部分)需要ω一致性。推导的定理与假定的前提不可能是同一个东西。 - 逐符号分析两个表达式,数证明号。区别在这里不容错过: - 稳定=
⊢BX ⟹ ⊢X,读作“如果系统断言‘X可证明’,那么系统断言‘X’。”两个证明号、两条分离断言,二者之间的⟹是我们的(元理论),系统从未把它们接起来。我们从外观察,发现第一条断言每次成立,第二条也成立。 - 反思语句=⊢(BX⊃X),读作“系统把‘若X可证明则X’作为一个语句断言。”一个证明号;如果—那么⊃位于系统自身语句内部。系统自己把假设缝到结论上,凭自身权威为整个条件句担保。 - 因而,⟹是两个系统主张之间的我们的箭头;⊃是一个主张内部的系统自己的箭头。勒布的前提是⊢(BX⊃X) ⟹ ⊢X:系统说出那一个内部条件句,然后才在我们的记账中推出⊢X。同样是“若可证明则X”,一边是我们跨两个证明号观察的模式,另一边是系统自己写下的一个证明号。两条规则都不直接给出另一条。 - 真正关系:外部判定与内部自证(理解的关键): - 稳定性=我们在元理论中、站在外部评价系统所得的判定:“它不虚张声势”(≈ω一致性),是关于系统的事实。 - 反思语句BX⊃X=从内部说出的完全相同内容,系统凭自己的权威为自身担保:“如果我证明X,那么X。”(对每个X都证明它=系统宣称自己稳定。) - 勒布=这种自我担保只有对已经证明的X才能成功;对仍未定的东西,系统根本无法说自己不虚张声势。 - 所以性质可以真,系统却无法从内部说出或证明它。一旦看见为什么系统关于自己的话毫无价值,就不神秘:系统总可以对自己的说谎再说谎。一个确实虚张声势的系统会不一致,而不一致系统证明一切,包括“我不虚张声势”。所以“我从不虚张声势,签名:我”,携带零信息;诚实系统与说谎系统都这么说,话语无法区分它们。这一间隙就是哥德尔第二定理:勒布取X=f,得到Bf⊃f = ~Bf = consis,所以⊢consis ⟹ ⊢f,系统甚至不能为“我不证明0=1”担保。稳定=外部判断它具有;勒布=内部无法说自己具有。
第五部分——词典:抽象M⟷具体一阶S
抽象M(第十一章) |
具体S/学习记录用词 |
|---|---|
S(集合) |
S的语句 |
| 可证明元素 | 定理(⊢) |
f(假) |
可反驳语句,0=1 |
X ⊃ Y、~X = X⊃f |
实质蕴涵、否定 |
B、BX |
可证明性谓词P(v₁)、P(⌜X⌝) |
赋值集V |
布尔赋值/解释;使所有公理真者=幸存者 |
| 重言式 | 逻辑有效的语句 |
真集T |
真语句(标准模型ℕ),即在证明问题上不被异类欺骗的世界 |
| 第一类 | 对(一阶)逻辑封闭 |
正规(P₁) |
必然化/D1(⊢X ⟹ ⊢P(X̄),单向) |
P₂ |
S ⊢ P(⌜X⊃Y⌝)⊃(P(X̄)⊃P(Ȳ))/D2 |
P₃ |
S ⊢ P(X̄)⊃P(⌜P(X̄)⌝)/D3(可证明的Σ₁完备性) |
| 第四类 | 具有可证明性谓词(D1、D2、D3) |
| 稳定 | ω一致性(学习记录用语);=“没有异类伪证明”/P的反思正确性,稳定≈ω的理由见T2行 |
| 一致 | 简单一致性(简单一致) |
罗瑟映射Q |
罗瑟系统,≤竞赛构造(ρ) |
G ≡ ~BG |
哥德尔语句 |
H ≡ BH |
亨金语句 |
Y ≡ (BY⊃X) |
柯里/勒布辅助语句 |
consis = ~Bf |
consis = Con(S) = ¬P(⌜0=1⌝) |
| 异类 | 冒牌者中的假冒数,在0,0′,0″,…之外(模型论:非标准元素) |
| 伪证明 | 被读作证明编码的异类(非标准长度的伪推导) |
| 冒牌者 | 不是ℕ副本的公理幸存者(模型论:非标准模型) |
第六部分——概念术语表→去哪里复习
A. 动词与首要区分
- 表达
R:F(n̄)真⟺n∈R。(真/语义)→7月30日 - 表示
R:F(n̄)可证明⟺n∈R。(证明/句法)→7月30日 - 反表示(contrarepresents)
R:F(n̄)可反驳⟺n∈R。(表示在反驳一侧的孪生者,用于精确分离)→8月4日 - 枚举
R:单向,弱于表示;可借ω一致性升级。→7月30日 - 定义
R(第八章):将R与其补集分离;完全表示=精确分离=表示+反表示(双重表示)。→8月5日§1、8月4日 - 可证明≠真,首要区分;混同它们是本书所针对的核心错误。→8月6日
B. 算术层级与完备性
- Σ₀有界→可判定;Σ₀完备性。→7月31日
- Σ₁=Σ₀上加
∃;P是Σ₁。→7月30日 - 递归=
R与R̄都为Σ₁。→8月5日 - 三个层次(教训):真不可表达(塔斯基)/可证明性可表示,不可定义(丘奇)/递归集合可定义。→8月5日
C. 一致性的强度(罗瑟改变的轴线)
- 简单(
f不可证明),学习记录叫简单一致;ω(不允许∃vφ而全部φ(n̄)都被反驳);正确(只证明真,学习记录中“可靠”的叫法)。→8月3日、7月30日 - 层级:正确⟹ω⟹简单,每个都严格;ω的抽象替身=稳定。→8月3日第十部分
- 爆炸原理(ex falso):不一致⟹证明一切⟹“有一个语句不可证明⟹一致”。→8月6日§3
D. 自指机制
- 对角化/哥德尔编号;对角
d(x)。→7月24日、8月5日 - 不动点引理:每个
F(v₁)都有X使S⊢X≡F(X̄)。→8月5日定理4 - 强与弱可定义性:强=可证明的唯一性=把
≡放到证明号之下。→8月5日§2 P*(对角集合)与诚实的P。→8月5日第零部分
E. 解释/幸存者/冒牌者(语义层)
- 解释=世界;幸存者=使全部公理为真的解释;冒牌者=幸存者≠
ℕ;异类=其中的假冒数;伪证明=作为证明编码的异类。见上文第二部分;戴德金范畴性、二阶、“异类世界M*”。→7月24日、8月6日 - 正确性与“盒算子表达可证明性”,是真集的两条分离条款(全部定理真,与
BX真⟺可证明)。→8月6日
F. 罗瑟/表示机制
- 罗瑟系统(分离不相交Σ₁集合对→不完备性与可表示性)。→8月3日、8月4日
≤竞赛ρ,需要Ω₄,Ω₅。→8月3日- 精确分离=双重表示。→8月4日
- (R)、(Q)、(R₀)、(Q₀)、P.A.;(R)=
Ω₁–Ω₅;全部Σ₀完备,全部为罗瑟系统。→7月31日
G. 可证明性谓词(第九章/第四类)
P₁,P₂,P₃=D1、D2、D3(可推导性条件/盒算子规则);导出的P₄(单调)、(★)/P₆(引擎)。→8月6日§1consis、第二定理、“不是怀疑的理由”。→8月6日§2- 勒布、亨金、克赖塞尔、克里普克、模态逻辑GL;化解柯里。→8月6日§3
第七部分——“忘记什么,就重读哪里”(快速跳转索引)
| 若模糊的是…… | 重读 |
|---|---|
| 从我自己概念出发的赋值集/重言式/真集 | 本文第一部分 |
| 异类、伪证明、使哥德尔语句为假的冒牌者图景、循环性 | 本文第二部分;8月6日、7月24日 |
M、B、第一/第四类、罗瑟映射、为何稳定≈ω |
本文第三与第五部分(加T2行) |
| 可证明与真(首要错误) | 8月6日 |
| 表达/表示/反表示/枚举/定义 | 7月30日、8月4日、8月5日§1 |
| Σ₀/Σ₁/递归/Σ₀完备性 | 7月31日 |
| 简单与ω与正确;“越弱⟹越一般” | 8月3日第十部分 |
哥德尔G、定理A/A*;ω不完备性、P.A.+{~G} |
7月30日、7月31日 |
罗瑟ρ、≤竞赛、引理S |
8月3日 |
| Σ₁可表示(谢泼德森)、精确分离 | 8月4日 |
| 不动点引理、强可定义性、三个层次、塔斯基 | 8月5日 |
P₁P₂P₃、(★)、第二定理、勒布、化解柯里 |
8月6日 |
| 二阶逻辑、戴德金范畴性、“没有恰切的机器” | 7月24日 |
一口气说完整本书
从集合上的盒算子
B出发,集合带有⊃与假f。世界是相容的真清单(赋值集,具体为解释);真实世界ℕ不会被任何异类(假冒数)诱骗为相信伪证明。只假定逻辑(第一类)+必然化(正规),自指G ≡ ~BG就不可判定(哥德尔,T2);如果世界正确,它还真(塔斯基–哥德尔,T1)。它不可证明,因为某个冒牌者使它假;而G说“我没有证明”,所以冒牌者是通过G的异类伪证明使它假,真正证明从不存在。用竞赛(罗瑟映射=罗瑟系统)替换正确性,就从单纯一致性得到不可判定性(罗瑟,T3)。加上盒算子规则P₂,P₃(第四类),B开始对自身推理:它几乎在内部证明第一定理,已经足以使它不能证明自身一致性~Bf(哥德尔第二定理,T4),也不能证明任何反思BX⊃X,除非X已可证明(勒布,T5)。第二定理就是把勒布指向f。
系列:7月15日 · 7月17日 · 7月19日 · 7月20日 · 7月21日 · 7月22日 · 7月23日 · 7月24日 · 7月26日 · 7月27日 · 7月28日 · 7月29日 · 7月30日 · 7月31日 · 8月3日 · 8月4日 · 8月5日 · 8月6日 · 总参考(本文)。