Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter II, §6: Diagonalization and Gödel Sentences — Tarski's Theorem
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 / 篇目
- How to use this document
- Part I — The opening question: Chapter I made concrete
- Part II — The new objects: wrapper, r, Proposition 2, d, A*, Lemma 1
- Part III — Why direct self-reference is impossible
- Part IV — Two plugging operations, their equivalence, and Gödel's price tag
- Part V — Theorem 1: the bare chain
- Part VI — Anatomy: why each step is what it is
- Part VII — Theorem 2: Tarski's Theorem
- Part VIII — The three statuses: a nameability audit
- Part IX — Quantifiers and mechanicality: when infinite search collapses
- Part X — Distinctions Ledger
- Part XI — Self-Test
- Part XII — What's ahead, state of play, and the method
Study session of July 22, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter II Part III, §6 (Proposition 2, Lemma 1, Theorem 1, Theorem 2 — Tarski's Theorem; book pp. 24–27) · Companion to the sessions of July 15, 17, 19, 20, and 21, 2026 · Exercises 6–8 deferred to next session
How to use this document
This follows the order in which understanding was actually built. The session's character was again different: not foundational probes (July 21) or one recurring bug (July 20), but one proof — Theorem 1 — fought for across many rounds, through a chain of misconceptions each of which had to be located precisely before the next could surface. The version that finally settled it is the bare numbered chain in Part V; everything before it is the material the chain compresses, and everything after it is the anatomy of why each step is what it is. For review: Parts I–IX in order the first time; afterwards Part V (the chain) plus the Distinctions Ledger (Part X) are a full refresher. The Self-Test (Part XI) tells you whether it took. A hard-won lesson about how to explain is recorded at the end of Part XII: when an explanation stalls, the cure is the bare chain — every step citing exactly one definition or theorem, no invented vocabulary.
Part I — The opening question: Chapter I made concrete
The session opened with: each proposition, lemma, and theorem here is an actualization of the structural proof from Chapter I — how exactly do they correspond?
The two-level pattern (July 15, Part IX) pays out. Chapter I stipulated properties of an abstract language — expressions are numbered, diagonalization is nameable, and then the Gödel-sentence theorem and Tarski's theorem follow by short arguments. Chapter II proves those stipulated properties hold for the concrete language L_E. So the chapter splits into two components:
- Component B — the arithmetization labor (the genuinely new math): the base-13 numbering (§5), Proposition 1 (∗ is Arithmetic, §4), Proposition 2 (r is Arithmetic), Lemma 1 (A Arithmetic ⇒ A Arithmetic). This is the work of earning* what Chapter I assumed.
- Component A — the diagonal argument itself (unchanged from Chapter I): the proofs of Theorem 1 and Theorem 2, which replay the abstract argument word for word once Lemma 1 is in hand.
The pipeline:
§5 numbering ──► Prop 1 (∗ Arithmetic) ──► Prop 2 (r Arithmetic) ──► Lemma 1 (A* Arithmetic) ──► Theorem 1 (Gödel sentences) ──► Theorem 2 (Tarski)
└────────────────── Component B: new math ──────────────────────┘ └───────── Component A: Chapter I replayed ─────────┘
The correspondence table, with the July 15 machine puzzle as third column:
| Chapter I (stipulated) | Chapter II (proved for L_E) | Machine puzzle (toy) |
|---|---|---|
| expressions enumerated E₁, E₂, … | base-13 Gödel numbering; Eₙ = the expression whose digits spell n | strings over P N ~ ( ) |
| a diagonalization operation on expressions, with a code function d | the wrapper E_x[ȳ] and r(x, y); d(x) = r(x, x) | the norm of an expression |
| "nameability is preserved by diagonalization": A nameable ⇒ A* nameable | Lemma 1 — the single genuinely new theorem, paid for by Proposition 2 | the letter N |
| every nameable set has a Gödel sentence | Theorem 1 | G = ~PN(~PN) |
| the set of truths is not nameable | Theorem 2 (Tarski) | no machine prints exactly the true sentences |
The moral the table carries: {wrapper, r, D} is the letter N. In the puzzle, N was handed to us as a primitive of the machine language; here it must be built, and Proposition 2 is the receipt. Everything downstream of Lemma 1 is July 15 again.
Part II — The new objects: wrapper, r, Proposition 2, d, A*, Lemma 1
The wrapper. For any expression E_x and number y, define
E_x[ȳ] := ∀v₁(v₁ = ȳ ⊃ E_x)
— read: "for every v₁, if v₁ equals ȳ, then E_x." When E_x is a formula with free variable v₁, this sentence has the same truth value as the literal substitution E_x(ȳ) (proved in Part IV) — but its string leaves E_x intact as an unopened block, and that is the entire trick.
The code function r. r(x, y) := g.n.(E_x[ȳ]). Read the Gödel number straight off the string ∀ v ′ ( v ′ = ȳ ⊃ E_x ): prefix "∀v₁(v₁ =" is a fixed string with a fixed code k = digits 9 6 0 2 6 0 η; then the numeral ȳ (code 13ʸ, by §5); then ⊃ (digit 8); then E_x (code x); then ) (digit 3):
r(x, y) = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3
Proposition 2. r(x, y) is Arithmetic. Proof: the displayed equation is a 5-fold concatenation of Arithmetic ingredients — constants, the numeral-coding function y ↦ 13ʸ (Arithmetic, July 21 Part IX), and the free slot x — so Corollary 1 finishes it in one line. ∎ Note what x does in this formula: it is never opened. The output code depends on x only as a whole block. Compare Gödel's counterpart in Part IV.
The diagonal and the star. d(x) := r(x, x) = the code of E_x diagonalized on its own index. For any number set A:
A* := {n : d(n) ∈ A}
Lemma 1. If A is Arithmetic, so is A.* Proof: d is an Arithmetic function (Proposition 2 with x = y, one more ∃ to identify the slots), so let D(v₁, v₂) express its graph; let F(v₁) express A. Then
H(v₁) := ∃v₂( D(v₁, v₂) ∧ F(v₂) )
expresses A: H(n̄) is true ⟺ some m has D(n̄, m̄) and F(m̄) true ⟺ m = d(n) and d(n) ∈ A ⟺ n ∈ A. ∎
Where Proposition 2 is spent — and its only appearance in the whole chapter: inside this proof, supplying D. The sentence H must internally say "the diagonal of my input lands in A," and D is the sub-machine that says "the diagonal of." (This settles the session question "what is r's Arithmetic-ness for?" — see Ledger, and Part VI.)
Part III — Why direct self-reference is impossible
Before the real construction, the plan that every newcomer (and this session's reconstruction attempt) reaches for first, and why it is dead on arrival.
The naive plan. F expresses A, so F(n̄) is true ⟺ n ∈ A, for every n. If the plugged number could be the finished sentence's own code — S = F(s̄) with s = g.n.(S) — the Gödel-sentence biconditional would hold immediately. Required: a number s with
s = g.n.(F(s̄))
The refutation, one line. The string F(s̄) contains the numeral s̄, whose code alone is 13ˢ (July 21, Part IX). So g.n.(F(s̄)) ≥ 13ˢ > s, for every s. No solutions — not "hard to find": provably zero hits, so no search of any length can succeed. A sentence's code strictly exceeds every number plugged into it: plugging always undershoots the sentence's own address. (July 15's "poster containing a full-size copy of itself," reincarnated in code arithmetic.)
The moral that dictates the whole construction: since the sentence cannot contain its own address, it must instead contain a small seed plus a stretching instruction, arranged so that the stretch of the seed equals the address. The stretch is d; the seed is h; the arrangement is Theorem 1.
Part IV — Two plugging operations, their equivalence, and Gödel's price tag
The two operations. For a formula F (free variable v₁) and number n:
Φ_lit(F, n) = F(n̄) — literal substitution: open F, replace each free v₁ by n̄ (Gödel)
Φ_wrap(F, n) = ∀v₁(v₁ = n̄ ⊃ F) — the wrapper: staple n̄ on the front, F intact (Smullyan)
The equivalence. For every F and n, Φ_lit(F, n) and Φ_wrap(F, n) have the same truth value. Proof: the wrapped sentence is true ⟺ every number m satisfies "if m = n then F holds of m." For m ≠ n the condition holds vacuously (the ⊃-guard passes them free); the only case that bears weight is m = n, where it says: F holds of n. And F(n̄) is true ⟺ F holds of n. Same condition, same truth value. ∎ — Concrete instance carried through the session: "6 is even" versus "every number that equals 6 is even."
Three layers — the distinction that unlocked Gödel's side. For both men there are three separate objects, and conflating them was a recurring session bug:
- The string operation — what you do to the sentence on paper (substitute / wrap).
- The code function ℕ × ℕ → ℕ — sub(x, y) or r(x, y), tracking what layer 1 does to Gödel numbers. Lives in the metatheory; perfectly computable and easy to describe in English for both men. Having this machine costs nothing.
- The naming formula D of L_E — true of (x, y, z) exactly when the layer-2 function sends (x, y) to z. "Arithmetic" is the claim that layer 3 exists. All the cost difference between Gödel and Smullyan lives here.
Gödel's counterpart to Proposition 2 is: sub(x, y) is Arithmetic, where sub(x, y) = g.n. of the literal substitution. His route: show sub is mechanical — buildable by a ladder of ~31 explicit definitions — then invoke a general bridge theorem, every mechanical function is Arithmetic (the status 1 ⇒ status 2 bridge; on the debt register, owed by a later chapter of Smullyan too). Why the ladder is long: sub's output code depends on the interior digits of x —
- find the occurrences of v₁ (digit pattern 60 — and 60 sits inside 600, the code of v₂: occurrence-finding must not misfire);
- determine which occurrences are free (requires parsing parenthesis scope);
- replace each occurrence, one at a time (formulas can't loop: iteration must be simulated by coding whole sequences of intermediate results into single numbers);
- reassemble without leading-zero accidents.
Smullyan's r treats x as an unopened parcel — output code = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3 — so layer 3 is one line. The correct slogan (replacing a wrong analogy raised in session — see Ledger): the wrapper does not shorten the sentence (it lengthens it); it shortens the formula that computes the sentence's address as a function of the input addresses.
Part V — Theorem 1: the bare chain
Theorem 1. Every Arithmetic set A has a Gödel sentence — a sentence X with: X is true ⟺ g.n.(X) ∈ A.
Ingredients used, and nothing else: the definition of expresses, the definition of r and d, Proposition 2, Lemma 1, the equivalence, the definition of A*, the definition of Gödel sentence.
Given: A is Arithmetic.
Step 1. By Lemma 1, A = {n : d(n) ∈ A} is Arithmetic. So there is a formula H, free variable v₁, such that for every n: H(n̄) is true ⟺ n ∈ A. (Justification: definition of "expresses." H(n̄) means literal substitution — that is how "expresses" is defined. Proposition 2 is consumed inside Lemma 1's proof, supplying D. This is Proposition 2's only appearance.)
Step 2. Let h = the Gödel number of H.
Step 3. Let X = ∀v₁(v₁ = h̄ ⊃ H). (This string is what H[h̄] abbreviates. Nothing is claimed yet; X is merely written down.)
Step 4. g.n.(X) = r(h, h) = d(h). (Justification: r(x, y) is defined as the Gödel number of ∀v₁(v₁ = ȳ ⊃ E_x); apply with x = y = h. No theorem needed — this is reading the numbering rules off the string in Step 3.)
Step 5. X is true ⟺ H(h̄) is true. (Justification: the equivalence. Its only appearance.)
Step 6. H(h̄) is true ⟺ h ∈ A. (Justification: Step 1 with n = h.)*
Step 7. h ∈ A ⟺ d(h) ∈ A. (Justification: definition of A.)
Step 8. Chaining 5, 6, 7: X is true ⟺ d(h) ∈ A. By Step 4, d(h) = g.n.(X). Therefore: X is true ⟺ g.n.(X) ∈ A.
Step 9. By the definition of Gödel sentence, X is a Gödel sentence for A. ∎
Each ingredient is spent exactly once: Proposition 2 at Step 1 (inside Lemma 1), the definition of r at Step 4, the equivalence at Step 5, expressibility at Step 6, the definition of A* at Step 7.
Part VI — Anatomy: why each step is what it is
(a) The definition of Gödel sentence mentions no substitution. It is a condition on a finished sentence — its truth versus its own address — and says nothing about how the sentence was manufactured or what shape it has. Diagonalization is the construction method that finds such a sentence; folding the method into the definition was a session error that generated several others.
(b) Two sentences, one Gödel sentence. At the end of Step 2, two candidate sentences exist, both true ⟺ d(h) ∈ A:
| sentence | its own address | truth condition | verdict |
|---|---|---|---|
| X = ∀v₁(v₁ = h̄ ⊃ H) | r(h, h) = d(h) | d(h) ∈ A | truth condition names its own address: Gödel sentence ✓ |
| H(h̄) | sub(h, h) — a different number, which nothing in this proof names | d(h) ∈ A | truth condition names the other sentence's address: a cross-reference, not a Gödel sentence ✗ |
Both say the same thing about the same number; that number is the home address of only one of them. H(h̄) is not "also a Gödel sentence pending some verification" — it fails the definition outright. And finiteness is a red herring: both strings are trivially finitely constructible; constructibility was never anyone's problem.
(c) Why equivalence cannot transfer Gödel-sentence-hood. Equivalence transfers truth conditions stated in absolute terms ("true ⟺ d(h) ∈ A" — both sentences share it). But Gödel-sentence-hood is "true ⟺ my own code ∈ A," and "my own" re-points at each sentence. Equivalent sentences are different strings with different addresses, so a self-referential title does not ride along. Equivalence preserves what sentences say; being a Gödel sentence is about whether what you say is about you.
(d) Where the equivalence is cashed — the fused line. The book's proof writes "H[h̄] is true ⟺ h ∈ A." That line is two steps fused: Steps 5 and 6 of the chain. Expressibility, by its definition, licenses only statements about the literal instances H(n̄); the silent half-step from the wrapped X to the literal H(h̄) is the equivalence. That half-step is its entire appearance in the chapter. And downstream (Theorem 2 and beyond) consumes Theorem 1 only through its finished statement — truth and code, nothing finer — so the joint never reopens. (Forward note: when "true" becomes "provable in a system," instance-by-instance truth-agreement would not suffice by itself — but ∀v₁(v₁ = h̄ ⊃ H) ⟺ H(h̄) is a logical* equivalence, provable from pure logic, so the swap survives into the incompleteness chapters.)
(e) The two knobs. The plugging operation appears twice in the proof, and the two appearances are independent choices:
- Knob A — which diagonal is named inside H (which D is embedded). Fixed when H is written; determines what everything built from H says.
- Knob B — which plugging manufactures X from H and h. Determines X's address: literal → sub(h, h); wrapped → r(h, h).
A Gödel sentence needs truth condition and address to name the same number, so the knobs must match:
| inside H | manufacture | X says | X's address | verdict |
|---|---|---|---|---|
| d (wrapped) | wrap | d(h) ∈ A | d(h) | match — Smullyan |
| d (wrapped) | literal | d(h) ∈ A | sub(h, h) | mismatch |
| d_lit = sub(x, x) | literal | d_lit(h) ∈ A | d_lit(h) | match — Gödel (price: sub Arithmetic, the ladder) |
| d_lit | wrap | d_lit(h) ∈ A | r(h, h) | mismatch |
Each man plays a matched pair. In Smullyan's row, expressibility (defined via literal probes) doesn't apply to the wrapped X directly — hence the one borrowed line of Step 5. In Gödel's row, no equivalence is needed anywhere — but the D inside H costs the ladder. The equivalence line is, precisely, the bill for the wrapper: one line of semantic glue at the end, in exchange for a chapter of digit-surgery in the middle. What H says is fixed by its text, not by how you later plug — a plugging method chooses the address of the resulting sentence and cannot retroactively change which function H names. (Session counterexample: H = "v₁ + 3 is even," plug in 5 by either method — both results are about 8; no delivery method turns +3 into +7.)
(f) Three ranks of notation. The session's last knot, and its dissolution:
- Rank 1 — open formula: H, written H(v₁) only to display which variable is free. No substitution happened — or, equally, the degenerate substitution of v₁ for itself, which returns H. Never true or false; it carves a set (the numbers satisfying it).
- Rank 2 — sentences: H(n̄) and H[n̄], both. Each is a truth-valued instance answering "does n satisfy H?" — two thermometers for the same temperature, which is exactly what the equivalence certifies.
"H(v₁) expresses A" is a rank-1 assertion (the set satisfying H is A), cashed at rank 2 through the literal instances. Misreading H(v₁) as rank 2 — as if v₁ were a plugged-in thing — was the root of the "why not H[v₁]?" confusion.
(g) Where literal substitution actually lives in the proof. In the definition of expresses — the infinitely many instances H(n̄) through which truth conditions are known — and nowhere else. The proof's exhibit is manufactured by wrapping (Step 3); no line of Theorem 1 manufactures H(h̄); its truth value is consulted (Steps 5–6) and the string discarded. And "the machine we have" is the wrapping machine (r, D) — sub was never built; refusing to build it is Smullyan's whole economy.
Part VII — Theorem 2: Tarski's Theorem
T := the set of Gödel numbers of the true sentences of L_E — a perfectly definite set (status 0; Part VIII), courtesy of §5.
Theorem 2. T is not Arithmetic.
Proof. Suppose it were, via a formula F. Then ~F expresses the complement T̃ (Arithmetic sets are closed under complement), so by Theorem 1, T̃ has a Gödel sentence X:
X is true ⟺ g.n.(X) ∈ T̃ ⟺ g.n.(X) ∉ T ⟺ X is not true
— the last step by the definition of T itself (a sentence's code is in T exactly when the sentence is true). Contradiction. ∎
Note the shape: Theorem 1 is a machine — feed it any Arithmetic set, receive a Gödel sentence. Tarski's theorem feeds it a set that cannot afford one (a Gödel sentence for T̃ is a sentence true iff not true), concluding the set was never Arithmetic. T's forced failure of nameability is not an inconvenience the proof works around; it is the theorem.
Part VIII — The three statuses: a nameability audit
A recurring session theme, finally systematized. For a set of numbers, three independent gradations:
- Status 0 — definite: a well-defined set in the metatheory. Costs nothing; every set discussed has it, including T. (Naming a set "T" in our own discourse requires nothing of L_E.)
- Status 1 — mechanical: some finite procedure decides membership, both verdicts.
- Status 2 — Arithmetic (internally nameable): some formula of L_E expresses it.
The inclusion runs one way: status 1 ⇒ status 2 (the bridge theorem, proved later in the book; Gödel's route to sub uses it). Not conversely: P̃ — the complement of the provable sentences' codes — is Arithmetic (in the systems studied later) yet not even listable. And "truth is not mechanical" is a corollary of Tarski (status 1 ⇒ status 2, and T lacks status 2), not a premise available before it.
The selection rule — which sets need status 2: exactly those the Gödel sentence's own text must mention. Audit:
| set / function | needs status 2? | why |
|---|---|---|
| A (the target set) | yes | F sits inside H |
| d (the diagonal) | yes | D sits inside H |
| grammar ("is a formula") | no | the proof never writes a sentence about grammaticality; garbage strings get numbers and are harmlessly ignored |
| T | its failure is the theorem | Tarski = the audit coming back negative |
Part IX — Quantifiers and mechanicality: when infinite search collapses
The session's parallel thread, resolved cleanly at the end.
The naive reading of ∃. For the set defined by ∃v₂ φ(n, v₂) (φ directly checkable), the obvious procedure — try v₂ = 0, 1, 2, … — has a built-in asymmetry: if n is in the set, a witness sits at a finite position and YES arrives after finitely many steps; if n is not, no finite failure justifies NO. YES-half mechanical, NO-half missing — such a set is called listable (P, provability, is the standard example: grind out all proofs; every provable sentence eventually appears; absence proves nothing).
The collapse criterion. The set is fully mechanical exactly when the search can be legitimately cut off: a provable, computable bound B(n) such that if any witness exists, one exists below B(n). Then checking v₂ ≤ B(n) decides both ways — the quantifier's range is infinite, but all-but-finitely-much of it is provably irrelevant. Example: "n is even" = ∃v₂(n = v₂ + v₂); any witness satisfies v₂ ≤ n.
Presburger arithmetic (+ without ·) is the collapse made total: every quantifier in every formula can be eliminated in favor of finitely checkable facts about remainders and order (∃v₂(n = v₂ + v₂) becomes "n leaves remainder 0 mod 2"); truth there is fully mechanical despite unbounded quantifiers throughout.
When it provably never collapses. For full arithmetic (+ and ·), no procedure decides truth — not by inspection of any formula, but by Tarski run backwards: mechanical ⇒ Arithmetic, and T is not Arithmetic. What · adds is the power to code finite sequences into single numbers (this chapter's own trick), i.e., to talk about arbitrary computation histories — a language whose truth, were it decidable, would decide too much. Addition alone cannot code sequences; that poverty is Presburger's tameness.
Guardrails. (i) Failure of the naive search proves nothing — a different procedure might exist; undecidability claims are theorems, never shrugs. (ii) One ∃ already suffices to lose the NO-half (P is undecidable); the ladder of quantifier alternations is a ladder of definitional complexity (the arithmetical hierarchy), not of cardinality — everything in sight is countable. The session's "multiple quantifiers → higher alephs" guess pointed at the wrong ladder.
Part X — Distinctions Ledger
| Confusion raised | One-line resolution |
|---|---|
| How does each §6 item actualize Chapter I? | Two-level pattern: Ch. I stipulated, Ch. II proves. Component B (numbering, Prop 1, Prop 2, Lemma 1) is the only new math — it builds the machine puzzle's letter N as {wrapper, r, D}; Theorems 1–2 are Chapter I replayed verbatim. |
| What is "internal nameability" (talkaboutability)? | Status 2: some formula of L_E expresses the set. Distinct from status 0 (definite in the metatheory — free for everything, including T) and status 1 (mechanically decidable). A set needs status 2 iff the Gödel sentence's text must mention it. |
| "F is Arithmetic, so F(n̄) is Arithmetic too — isn't that enough?" | Category error: Arithmetic is a predicate of sets/relations/functions; F(n̄) is a sentence — just true or false. The thing whose Arithmetic-ness the proof needs is the code function r. |
| "T is not mechanical, hence not Arithmetic"? | Inclusion runs the other way (mechanical ⇒ Arithmetic). P̃ is Arithmetic yet not even listable. "Truth not mechanical" is a corollary of Tarski, not its premise. |
| "Multiple quantifiers → aleph-n → non-mechanical"? | Everything is countable; stacking quantifiers climbs definitional complexity (arithmetical hierarchy), not cardinality — and one ∃ already breaks decidability (P). |
| "Doesn't the wrapper circle back — don't we still need the literal-substitution relation to be Arithmetic?" | No: the wrapper redefines the plugging operation itself. The hard literal relation is abandoned, never expressed; downstream consumes only truth values and codes, which the wrapper supplies identically. |
| "∀ condenses infinite ANDs — is that the wrapper's efficiency?" | Wrong layer: the wrapped sentence is longer than F(n̄). The saving is that E_x rides unopened, so the output's code depends on x as one block — the wrapper shortens the formula computing the sentence's address, not the sentence. |
| "The machine is a finite concatenation of strings / a rule in the symbols" | Three layers: string operation → code function (metatheory; cheap for both men) → naming formula D of L_E. "Arithmetic" is a claim about layer 3; all cost differences live there. |
| "r Arithmetic = we have a finite way to crank out codes" | Cranking needs no theorem — we compute r(h, h) in the margin. Arithmetic means L_E can name r's graph via D — needed because D sits inside H as a building block. |
| "Where do we get H[h̄]'s truth? Why not just use H(h̄), since H expresses A*?" | Expressibility speaks only of literal instances; the book's "H[h̄] true ⟺ h ∈ A*" fuses equivalence (Step 5) + expressibility (Step 6). And H(h̄) can't be the exhibit: its own address is sub(h, h), which nothing in the proof names. |
| "Two diagonalizations d1, d2, two star sets, chains through both" | Only one A exists: what H says is fixed by the D baked into its text, not by how you later plug. Plugging picks the resulting sentence's address; it cannot change what the formula says* (the +3/+7 example). |
| "H(v₁) — why not H[v₁]? Isn't H(v₁) like F(n̄)?" | Three ranks: H(v₁) is the open formula with its free variable displayed (identity substitution returns H itself); H(n̄) and H[n̄] are rank-2 sentence instances. "Expresses" is a rank-1 property, tested through rank-2 literal instances. |
| "A Gödel sentence is by definition a formula with its own number substituted in" | The definition is shape-free: X true ⟺ g.n.(X) ∈ A. Diagonalization is the construction method, not the definition. (And X need not be true — the evens' Gödel sentence is false.) |
| "H(h̄) is a Gödel sentence by definition; H[h̄] is one by equivalence" | Backwards: H[h̄]'s truth condition names its own address (Gödel sentence); H(h̄)'s names its sibling's (a cross-reference). Equivalence transfers absolute truth conditions, never a self-referential title — the two strings have different addresses. |
| "We pick H[h̄] only because H(h̄)'s finite construction isn't shown" | Red herring: both strings are trivially finitely constructible. H(h̄) fails the definition, full stop. |
| "The proof substitutes h literally into H to arrive at the Gödel sentence" | Literal substitution lives only in the definition of expresses (the testing side). The exhibit is manufactured by wrapping: Step 3 says "let X = ∀v₁(v₁ = h̄ ⊃ H)"; no line manufactures H(h̄); the only machine built this chapter is r/D — sub was never constructed. |
| "Find s by plugging all numbers into F and checking" | The search provably has zero hits: s = g.n.(F(s̄)) is impossible since g.n.(F(s̄)) ≥ 13ˢ > s. The real construction computes (write H, read off h, wrap); it never searches. |
Part XI — Self-Test
Answer before peeking.
- Define "Gödel sentence for A." Must a Gödel sentence be true? Give a counterexample.
- Define the wrapper E_x[ȳ], derive the closed form of r(x, y), and prove Proposition 2. What does x never undergo in this formula, and why is that the whole trick?
- State and prove Lemma 1. Where exactly — and only where — is Proposition 2 consumed in this chapter?
- Reproduce the nine-step chain of Theorem 1, citing for each step exactly one definition or theorem.
- Prove the equivalence of Φ_lit and Φ_wrap. Which case of the ∀ bears the weight, and how do the other cases pass?
- Show that H(h̄) is not a Gödel sentence for A, even though its truth value equals X's. Why can't the equivalence transfer the title?
- Prove there is no s with s = g.n.(F(s̄)), and state the moral that dictates the seed-plus-stretch design.
- What is Gödel's counterpart to Proposition 2? Name his route (two moves) and the four hazards that make his ladder long. State the three layers and say in which layer all the cost lives.
- The two knobs: name them, produce the four-row table, and say which single line each man's matched pair costs him extra.
- The three ranks: what is H(v₁), and in what sense is writing it "a substitution that changes nothing"?
- Unfold the book's fused line "H[h̄] is true ⟺ h ∈ A*" into its two steps with justifications.
- Prove Tarski's theorem from Theorem 1. What does the proof feed the Theorem-1 machine, and why can't that set afford the output?
- Give the three statuses, the direction of the inclusion between statuses 1 and 2, the in-house counterexample to the converse, and the selection rule for which sets need status 2.
- When does an ∃-definition remain mechanically decidable? State the collapse criterion, give one collapsing example, name the theory where collapse is total, and say why full arithmetic provably never collapses (which theorem, run which way).
Answers
- X is a Gödel sentence for A iff (X is true ⟺ g.n.(X) ∈ A). Shape-free — no substitution mentioned. It need not be true: for A = the even numbers, the constructed sentence turns out false with code odd — biconditional satisfied on the false side (Exercise 6, next session).
- E_x[ȳ] := ∀v₁(v₁ = ȳ ⊃ E_x). Reading the numbering off the string: prefix "∀v₁(v₁ =" = fixed code k, then 13ʸ (the numeral), 8 (⊃), x, 3 ( ")" ): r(x, y) = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3. Arithmetic by Corollary 1 (5-fold concatenation of Arithmetic pieces). x is never opened — the output code depends on x only as a block, which is what makes the naming formula one line.
- Lemma 1: A Arithmetic ⇒ A = {n : d(n) ∈ A} Arithmetic. Proof: d(x) = r(x, x) is Arithmetic (Prop 2), let D express its graph, F express A; H(v₁) = ∃v₂(D(v₁, v₂) ∧ F(v₂)) expresses A. Proposition 2 is consumed here and only here — supplying the D that sits inside H.
- See Part V. Justifications: Step 1 Lemma 1 + definition of expresses; Step 4 definition of r; Step 5 the equivalence; Step 6 Step 1 at n = h; Step 7 definition of A*; Step 9 definition of Gödel sentence.
- Wrapped true ⟺ every m: (m = n ⊃ F holds of m). For m ≠ n the ⊃-guard passes them vacuously; m = n bears the weight, saying F holds of n — which is F(n̄)'s truth condition exactly.
- H(h̄)'s own address is sub(h, h); its truth condition names d(h) — the other sentence's address. The definition compares truth with the sentence's own code, and equivalence preserves what is said (absolute conditions), while addresses differ between the two strings; "my own code ∈ A" re-points with each sentence, so the title doesn't transfer.
- F(s̄) contains the numeral s̄ of code 13ˢ, so g.n.(F(s̄)) ≥ 13ˢ > s: no fixed point. Moral: plugging always undershoots the sentence's own address, so the sentence must carry a small seed h plus a stretching instruction (D naming d) with d(h) = its own address.
- "sub(x, y) is Arithmetic." Route: (i) sub is mechanical — a ladder of ~31 explicit definitions; (ii) the bridge theorem, mechanical ⇒ Arithmetic. Hazards: occurrence-finding (60 inside 600), freeness (parenthesis scope), replace-all (iteration simulated by coding sequences), leading-zero reassembly. Layers: string operation → code function → naming formula; all cost lives in layer 3.
- Knob A: which diagonal is named inside H (fixed at writing). Knob B: which plugging manufactures X (fixes the address). Table in Part VI(e). Smullyan's extra line: Step 5 (equivalence — expressibility only speaks in literal probes). Gödel's extra bill: sub Arithmetic (the ladder), paid inside Lemma 1's counterpart.
- H(v₁) is the open formula with its free variable displayed — rank 1, never true or false, carves a set. Substituting v₁ for v₁ returns H itself, so the display-notation and the substitution-notation are one notation, met at the degenerate case.
- H[h̄] true ⟺ H(h̄) true (the equivalence) ⟺ h ∈ A* (definition of expresses, instance n = h). The book fuses them because the equivalence was noted once when brackets were introduced.
- If T were Arithmetic, so is T̃ (complement closure: ~F). Theorem 1 on T̃ yields X: X true ⟺ g.n.(X) ∈ T̃ ⟺ g.n.(X) ∉ T ⟺ X not true — contradiction. The machine is fed the one set whose Gödel sentence would have to be true-iff-not-true; the set therefore was never Arithmetic.
- Status 0 definite (metatheory; free for all sets, including T); status 1 mechanical; status 2 Arithmetic. Status 1 ⇒ status 2 (bridge theorem, later chapter); converse fails — P̃ is Arithmetic but not even listable. Selection rule: a set needs status 2 iff the Gödel sentence's text must mention it (A and d: yes; grammar: no; T: its failure is Tarski).
- Decidable iff the search can be cut off: a provable computable bound B(n) with "witness exists ⇒ witness ≤ B(n)." Example: evens, witness ≤ n. Total collapse: Presburger arithmetic (quantifier elimination). Full arithmetic never collapses: mechanical ⇒ Arithmetic plus Tarski (T not Arithmetic) — the theorem run backwards; · is what lets arithmetic code sequences, hence computation histories.
Part XII — What's ahead, state of play, and the method
Position: Chapter II complete through §6: Proposition 2, Lemma 1, Theorem 1, and Theorem 2 (Tarski) proved and — after a long battle — narrated back correctly. The Chapter I ↔ Chapter II correspondence is settled (Part I): Lemma 1 was the only new mathematics; the rest was July 15 wearing base-13 clothing.
Next session: Exercises 6, 7, 8 (book p. 27), deliberately left fresh:
- Exercise 6 — the alternative base-10 numbering (codes 1, 0, 2, 3, 4, 5, 6, 7, 89, 899, 8999, 89999, 899999): is the Gödel sentence for the set of even numbers true or false? For the odd numbers? Hint: what digit does the constructed sentence always end in, and what does the last digit tell you in base 10 that it wouldn't in base 13?
- Exercise 7 — a function f such that for every n, f(n) is the Gödel number of a Gödel sentence for A whenever... (build a Gödelizer). Hint: make the code of Hₙ a concatenation with n riding as an unopened block — the wrapper trick, one level up.
- Exercise 8 — the cross-reference pair: sentences X and Y with X true ⟺ g.n.(Y) ∈ A and Y true ⟺ g.n.(X) ∈ B. Hint: a two-variable wrapper ∀v₁(v₁ = x̄ ⊃ ∀v₂(v₂ = ȳ ⊃ E)) gives an r₂(e, x, y); diagonalize it two ways. Note: the session's diagnosis of H(h̄) as "a sentence about its sibling" is Exercise 8's phenomenon appearing uninvited.
After the exercises: Chapter III — from truth to provability, where "true" is replaced by "provable in a system" and the forward notes of Part VI(d) (the equivalence is provable, not merely true) and Part VIII (the bridge theorem; P̃) come due.
The debt register, updated: (1) Gödel's E-elimination — still the hardest entry. (2) Why prime base 13 — still owed. (3) Property 1 ⇒ property 2 — still owed. (4) Restated with new urgency: mechanical ⇒ Arithmetic (status 1 ⇒ status 2) — this session leaned on it twice (Gödel's route to sub; "truth not mechanical" as Tarski's corollary); the book proves it in the provability chapters.
The method, continued — a lesson about explanations themselves. This session's hardest stretch was not mathematical but expository, and it produced an explicit standard, twice demanded and finally met: no unexplained coinages, no invented metaphor-vocabulary doing load-bearing work, no smuggled baggage. What broke the deadlock each time was the same move: strip the account to a bare numbered chain in which each step cites exactly one definition or theorem already owned (Part V), or run a concrete instance by hand ("6 is even" vs "every number that equals 6 is even"; the +3/+7 example). Terminology invented mid-explanation — however vivid — is a cost, not a gift, unless it is immediately glossed in words already paid for. The complementary reader's-side lesson: three of the session's errors (the two-diagonalizations chain, the definition-with-substitution, the literal-manufacture claim) were each a plausible narrative that collapsed the distinction between what a formula says (fixed by its text) and what is done with it (chosen later) — when a story feels right but won't survive being written as a numbered chain with justifications, the chain is the arbiter.
End of session review · Smullyan, "Gödel's Incompleteness Theorems," Chapter II §6 complete — Tarski's Theorem · Previous files: Godel-Incompleteness-Session-2026-07-15.md (Chapter 1 framework & machine puzzle), Godel-Incompleteness-Session-2026-07-17-Answer-Sheet.md (Chapter 1 exercises 1–7), Godel-Incompleteness-Session-2026-07-19.md (Chapter II §1–§2, language and truth), Godel-Incompleteness-Session-2026-07-20.md (Chapter II §3, Arithmetic sets/relations/functions, Exercises 2–5), Godel-Incompleteness-Session-2026-07-21.md (Chapter II §4–§5, concatenation and Gödel numbering) · Next: Exercises 6–8, then Chapter III.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月22日学习记录 · 斯穆里安《哥德尔不完备性定理》,第二章第三部分§6(命题2、引理1、定理1、定理2即塔斯基定理;书中第24–27页)· 与2026年7月15、17、19、20、21日记录配套 · 习题6–8留至下次
如何使用本文
本文依照理解实际形成的顺序展开。本次的特点又不相同:既不是基础性的追问(7月21日),也不是反复出现的一个错误(7月20日),而是围绕一个证明——定理1——经过多轮交锋,穿过一连串误解;必须精确定位每一个,下一个才会浮现。最终解决问题的版本是第五部分简明的编号推导链;之前的一切都是这条链压缩的材料,之后的一切则剖析每步为什么如此。复习时,第一次按顺序阅读第一至第九部分;之后只需第五部分(推导链)加上区分清单(第十部分),就能完整回顾。自测(第十一部分)检验是否掌握。第十二部分末尾记录了一条来之不易的、关于如何解释的教训:解释停滞时,补救就是简明推导链,每步恰好引用一个定义或定理,不使用自造词汇。
第一部分——开场问题:第一章的具体化
本次从这个问题开始:这里的每个命题、引理、定理都是第一章结构性证明的现实化,它们究竟怎样对应?
两层模式(7月15日第九部分)兑现了。第一章规定了抽象语言的性质:表达式有编号,对角化可以命名,然后哥德尔语句定理与塔斯基定理由简短论证得出。第二章证明这些规定的性质对具体语言L_E成立。所以本章分成两个组件:
- 组件B:算术化劳动(真正新的数学):13进制编号(§5)、命题1(∗是算术的,§4)、命题2(r是算术的)、引理1(A是算术的⇒A是算术的)。这是逐步挣得*第一章所假设内容的工作。
- 组件A:对角论证本身(与第一章完全相同):定理1与定理2的证明,有了引理1以后,就逐字重演抽象论证。
流程:
§5编号 ──► 命题1(∗算术)──► 命题2(r算术)──► 引理1(A*算术)──► 定理1(哥德尔语句)──► 定理2(塔斯基)
└────────────────── 组件B:新的数学 ──────────────────┘ └──────── 组件A:重演第一章 ────────┘
对应表,第三列加入7月15日的机器谜题:
| 第一章(规定) | 第二章(对L_E证明) | 机器谜题(玩具模型) |
|---|---|---|
| 表达式被枚举为E₁、E₂、…… | 13进制哥德尔编号;Eₙ=其数字拼成n的表达式 | 由P N ~ ( )构成的字符串 |
| 表达式上的对角化操作,带编码函数d | 封装式E_x[ȳ]与r(x, y);d(x) = r(x, x) | 表达式的范式(norm) |
| “对角化保留可命名性”:A可命名⇒A*可命名 | 引理1,唯一真正新的定理,由命题2支付代价 | 字母N |
| 每个可命名集合都有哥德尔语句 | 定理1 | G = ~PN(~PN) |
| 真之集合不可命名 | 定理2(塔斯基) | 没有机器恰好打印所有真语句 |
此表的教训:{封装式,r,D}就是字母N。在谜题中,N作为机器语言的原始成分交给我们;这里却必须构造它,命题2就是凭据。引理1之后的一切,都是7月15日的重演。
第二部分——新对象:封装式、r、命题2、d、A*、引理1
封装式。对任意表达式E_x与数y,定义:
E_x[ȳ] := ∀v₁(v₁ = ȳ ⊃ E_x)
读作:“对每个v₁,如果v₁等于ȳ,那么E_x。”当E_x是自由变量为v₁的公式时,这个语句与字面代入E_x(ȳ)真值相同(第四部分证明),但它的字符串把E_x作为未拆封的块完整保留,这就是全部技巧。
编码函数r。r(x, y) := g.n.(E_x[ȳ])。直接从字符串∀ v ′ ( v ′ = ȳ ⊃ E_x )读出哥德尔数:前缀“∀v₁(v₁ =”是固定字符串,其固定编码k的数字为9 6 0 2 6 0 η;然后是数码ȳ(由§5,编码为13ʸ);然后是⊃(数字8);然后是E_x(编码x);最后是)(数字3):
r(x, y) = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3
命题2。r(x, y)是算术的。证明:所列等式是算术成分的五重拼接,包括常数、数码编码函数y ↦ 13ʸ(是算术的,7月21日第九部分)、自由空位x,因此推论1一行就完成证明。∎ 注意x在公式中做了什么:它从未被打开。输出编码只把x当作整体的块来依赖。可与第四部分哥德尔的对应做法比较。
对角与星号。d(x) := r(x, x),即E_x以自身序号对角化后的编码。对任意数集A:
A* := {n : d(n) ∈ A}
引理1。如果A是算术的,A也是。*证明:d是算术函数(命题2中令x = y,再加一个∃来认同两个空位),故令D(v₁, v₂)表达其图;令F(v₁)表达A。那么:
H(v₁) := ∃v₂( D(v₁, v₂) ∧ F(v₂) )
表达A:H(n̄)真⟺某个m使D(n̄, m̄)与F(m̄)真⟺m = d(n)且d(n) ∈ A⟺n ∈ A。∎
命题2在何处被使用,也是它在整章中唯一的出现:在此证明内提供D。语句H必须在内部说出“我的输入的对角落在A中”,而D是说“……的对角”的子机制。(这解决了本次“r是算术的到底有什么用”的问题,见清单与第六部分。)
第三部分——为什么直接自指不可能
在真正构造之前,先看每个初学者(也包括本次重建尝试)最先想到的方案,以及它为什么从一开始就行不通。
天真方案。F表达A,所以对每个n,F(n̄)真⟺n ∈ A。如果代入的数能够是完成后语句自己的编码,即S = F(s̄),其中s = g.n.(S),哥德尔语句的双条件便立刻成立。这要求有一个数s满足:
s = g.n.(F(s̄))
一行反驳。字符串F(s̄)包含数码s̄,单这个数码的编码就是13ˢ(7月21日第九部分)。所以对每个s,g.n.(F(s̄)) ≥ 13ˢ > s。无解,不是“难找”,而是可证明命中次数为零,再长的搜索都不可能成功。语句的编码严格大于代入其中的每个数:代入的数总比语句自己的地址小。(7月15日“包含自身原尺寸副本的海报”,在编码算术中重生。)
决定整个构造的教训:语句既然不能包含自己的地址,就必须改为包含一个小种子加一条拉伸指令,并安排种子的拉伸结果恰好等于地址。拉伸是d,种子是h,安排则是定理1。
第四部分——两种代入操作、它们的等价,以及哥德尔付出的代价
两种操作。对公式F(自由变量v₁)与数n:
Φ_lit(F, n) = F(n̄) ——字面代入:打开F,把每个自由v₁替换为n̄ (哥德尔)
Φ_wrap(F, n) = ∀v₁(v₁ = n̄ ⊃ F) ——封装:把n̄订在前面,F保持完整 (斯穆里安)
等价性。对每个F与n,Φ_lit(F, n)与Φ_wrap(F, n)真值相同。证明:封装后的语句真⟺每个数m满足“若m = n,则F对m成立”。m ≠ n时条件空真(⊃条件让它们直接通过);唯一有实质作用的是m = n的情况,它说F对n成立。而F(n̄)真⟺F对n成立。同一条件,同一真值。∎ 本次反复使用的具体例子:“6是偶数”与“每个等于6的数都是偶数”。
三个层次:打开哥德尔一侧的关键区分。对两位作者,均有三个分离的对象,混同它们是本次反复出现的错误:
- 字符串操作:在纸上对语句做什么(代入/封装)。
- 编码函数ℕ × ℕ → ℕ,即sub(x, y)或r(x, y),追踪第一层操作对哥德尔数做了什么。它位于元理论中,对两位作者都完全可计算,也容易用普通语言描述。拥有这台机器不费什么代价。
- L_E的命名公式D:对(x, y, z)为真,当且仅当第二层函数将(x, y)送到z。“是算术的”主张的就是第三层存在。哥德尔与斯穆里安之间的全部成本差异都在这里。
哥德尔对应于命题2的陈述是:sub(x, y)是算术的,其中sub(x, y)=字面代入后的哥德尔数。他的路线:证明sub是机械的,可由约31个明确的定义逐级构造,再调用一般的桥梁定理:每个机械函数都是算术的(状态1⇒状态2的桥梁;列于欠账表中,斯穆里安后面的章节也要偿还)。阶梯漫长,因为sub的输出编码依赖x的内部数字:
- 找到v₁的各次出现(数字模式60;而60也在600内部,600是v₂的编码,所以寻找出现不能误触);
- 判定哪些出现是自由的(需要分析括号辖域);
- 逐个替换每次出现(公式不能循环,必须把中间结果的整个序列编码成单个数来模拟迭代);
- 重新组装,避免前导零造成意外。
斯穆里安的r把x当作未拆封的包裹:输出编码=k ∗ 13ʸ ∗ 8 ∗ x ∗ 3,所以第三层只需一行。正确的概括是(取代本次提出的一个错误比喻,见清单):封装并不缩短语句,反而加长它;它缩短的是根据输入地址计算语句地址的公式。
第五部分——定理1:简明推导链
定理1。每个算术集合A都有哥德尔语句,即某语句X满足:X真⟺g.n.(X) ∈ A。
使用的材料,仅此而已:表达的定义、r与d的定义、命题2、引理1、等价性、A*的定义、哥德尔语句的定义。
已知:A是算术的。
步骤1。由引理1,A = {n : d(n) ∈ A}是算术的。因此存在自由变量为v₁的公式H,使对每个n:H(n̄)真⟺n ∈ A。 (理由:“表达”的定义。H(n̄)意指字面代入,“表达”就是这样定义的。命题2在引理1的证明内部被使用,用来提供D。这是命题2唯一的出现。)
步骤2。令h=H的哥德尔数。
步骤3。令X = ∀v₁(v₁ = h̄ ⊃ H)。 (这个字符串就是H[h̄]的缩写所指。目前还没提出任何主张,只是把X写下来。)
步骤4。g.n.(X) = r(h, h) = d(h)。 (理由:r(x, y)被定义为∀v₁(v₁ = ȳ ⊃ E_x)的哥德尔数;取x = y = h。不需要定理,只是从步骤3的字符串读出编号规则。)
步骤5。X真⟺H(h̄)真。 (理由:等价性。它唯一的出现。)
步骤6。H(h̄)真⟺h ∈ A。 (理由:步骤1中取n = h。)*
步骤7。h ∈ A⟺d(h) ∈ A。 (理由:A的定义。)
步骤8。串联5、6、7:X真⟺d(h) ∈ A。由步骤4,d(h) = g.n.(X)。因此X真⟺g.n.(X) ∈ A。
步骤9。根据哥德尔语句的定义,X是A的哥德尔语句。∎
每种材料恰好使用一次:命题2在步骤1(引理1内部),r的定义在步骤4,等价性在步骤5,可表达性在步骤6,A*的定义在步骤7。
第六部分——剖析:每步为什么如此
(a)哥德尔语句的定义没有提及代入。它是对完成后语句的条件:语句的真与自身地址之间的关系,并不说明语句如何制造或有什么形状。对角化是找到这种语句的构造方法;把方法揉进定义,是本次一个错误,而且引出了若干其他错误。
(b)两个语句,一个哥德尔语句。步骤2结束时,有两个候选语句,两者都满足真⟺d(h) ∈ A:
| 语句 | 自身地址 | 真条件 | 判断 |
|---|---|---|---|
| X = ∀v₁(v₁ = h̄ ⊃ H) | r(h, h) = d(h) | d(h) ∈ A | 真条件命名自身地址:哥德尔语句✓ |
| H(h̄) | sub(h, h),另一个数,本证明没有命名它 | d(h) ∈ A | 真条件命名另一个语句的地址:交叉指涉,不是哥德尔语句✗ |
两者对同一个数说同样的事,但这个数只属于其中一个的地址。H(h̄)不是“等进一步验证后也会是哥德尔语句”,而是直接不满足定义。而且有限性是无关因素:两个字符串显然都能有限构造;可构造性从来不是任何人的问题。
(c)为什么等价性不能转移哥德尔语句的身份。等价性传递以绝对方式陈述的真条件(“真⟺d(h) ∈ A”,两者共享)。但哥德尔语句身份要求“真⟺我自己的编码∈A”,而“我自己的”在每个语句那里都会重新指向。等价语句是不同字符串,地址不同,因此自指的称号不会跟着转移。等价性保留语句说什么;是不是哥德尔语句,则关乎所说的是否关于你自己。
(d)等价性在哪里兑现:合并的一行。书中证明写“H[h̄]真⟺h ∈ A”。这一行合并了两步,即推导链的步骤5与6。可表达性的定义只允许谈论字面实例H(n̄);从封装后的X到字面的H(h̄),那个无声的半步就是等价性。这半步就是它在本章的全部出现。之后(定理2及更后)只通过定理1完成后的陈述使用它:真与编码,没有更细的东西,所以接缝不再打开。(前瞻:当“真”变成“系统中可证明”时,逐实例真值相同本身并不足够;但∀v₁(v₁ = h̄ ⊃ H) ⟺ H(h̄)是逻辑*等价,可以由纯逻辑证明,因此这种替换能延续到不完备性章节。)
(e)两个旋钮。代入操作在证明中出现两次,两次是独立的选择:
- 旋钮A:H内部命名哪一种对角(嵌入哪个D)。在写下H时固定,决定由H构成的一切说什么。
- 旋钮B:用哪种代入方式从H与h制造X。决定X的地址:字面代入→sub(h, h);封装→r(h, h)。
哥德尔语句要求真条件和地址命名同一个数,所以两个旋钮必须匹配:
| H内部 | 制造方式 | X说什么 | X的地址 | 判断 |
|---|---|---|---|---|
| d(封装) | 封装 | d(h) ∈ A | d(h) | 匹配:斯穆里安 |
| d(封装) | 字面代入 | d(h) ∈ A | sub(h, h) | 不匹配 |
| d_lit = sub(x, x) | 字面代入 | d_lit(h) ∈ A | d_lit(h) | 匹配:哥德尔(代价:sub是算术的,那条阶梯) |
| d_lit | 封装 | d_lit(h) ∈ A | r(h, h) | 不匹配 |
两位作者各自使用匹配的一对。在斯穆里安那行,可表达性(通过字面探测定义)不能直接适用于封装后的X,所以借用步骤5的一行。在哥德尔那行,任何地方都不需要等价性,但H内部的D需要那条阶梯。等价性那一行,恰恰是封装的账单:最后付一行语义粘合,换掉中间一整章的数字手术。H说什么由其文本决定,不由后来的代入方式决定;代入方法选择结果语句的地址,不能回溯改变H命名哪个函数。(本次反例:H=“v₁ + 3是偶数”,用任一方法代入5,两种结果都在谈8;任何递送方式都不能把+3变成+7。)
(f)记号的三个层级。本次最后一个结,以及它的解开:
- 第一层:开放公式。H写成H(v₁),只是展示哪个变量自由。没有发生代入;或等价地说,把v₁代入自身,是返回H的退化代入。它从来没有真或假,而是划出一个集合(满足它的数)。
- 第二层:语句。H(n̄)与H[n̄]都属于这一层。各自是有真值的实例,回答“n满足H吗?”;它们像测量同一温度的两支温度计,等价性确证的正是这一点。
“H(v₁)表达A”是第一层的主张(满足H的集合为A),通过字面实例在第二层兑现。把H(v₁)误读成第二层,仿佛v₁是代进去的某个东西,就是“为什么不是H[v₁]?”这一困惑的根源。
(g)字面代入实际处在证明的哪里。在表达的定义中,即借以知道真条件的无穷多个实例H(n̄),除此之外没有别处。证明展示的对象由封装制造(步骤3);定理1没有哪行制造H(h̄),只是查询它的真值(步骤5–6),然后丢开字符串。而“我们拥有的机器”是封装机器(r、D);sub从未构造,不去构造它就是斯穆里安全部的节省之道。
第七部分——定理2:塔斯基定理
T := L_E真语句的哥德尔数集合。借助§5,它是一个完全确定的集合(状态0,见第八部分)。
定理2。T不是算术的。
证明。假定它通过某个公式F是算术的。那么~F表达补集T̃(算术集合对取补封闭),故由定理1,T̃有哥德尔语句X:
X真 ⟺ g.n.(X) ∈ T̃ ⟺ g.n.(X) ∉ T ⟺ X不真
最后一步来自T本身的定义(语句编码属于T,当且仅当语句真)。矛盾。∎
注意其形状:定理1是一台机器,输入任意算术集合,输出哥德尔语句。塔斯基定理输入一个承受不起这种语句的集合(T̃的哥德尔语句会真当且仅当不真),从而得出该集合原本就不是算术的。T被迫失去可命名性,并非证明绕开的不便;它就是定理。
第八部分——三个状态:可命名性审查
这是本次反复出现的主题,现在终于系统化。对一个数集,有三个独立层次:
- 状态0:确定。元理论中良好定义的集合。不费代价;所讨论的每个集合都有,包括T。(在我们自己的论述中把集合叫作“T”,对L_E没有任何要求。)
- 状态1:机械。某个有限程序能判定成员身份,给出两种判断。
- 状态2:算术的(内部可命名)。L_E的某个公式表达它。
包含关系是单向的:状态1⇒状态2(桥梁定理,书中稍后证明;哥德尔对sub的路线使用它)。反方向不成立:P̃,即可证明语句编码的补集,是算术的(在后来研究的系统里),却甚至不可列举。而“真不是机械的”是塔斯基的推论(状态1⇒状态2,而T没有状态2),不是在塔斯基之前就能使用的前提。
选择规则:哪些集合需要状态2。恰好是哥德尔语句自身文本必须提及的那些。审查如下:
| 集合/函数 | 需要状态2? | 原因 |
|---|---|---|
| A(目标集合) | 是 | F在H内部 |
| d(对角) | 是 | D在H内部 |
| 语法(“是公式”) | 否 | 证明从不写出关于语法合格性的语句;无意义字符串获得编号,被无害地忽略 |
| T | 它的失败就是定理 | 塔斯基=审查得出否定结果 |
第九部分——量词与机械性:无穷搜索何时能收缩
本次的平行线索,最后得到清晰解决。
对∃的天真读法。对由∃v₂ φ(n, v₂)定义的集合(φ可直接检查),显然的程序——依次试v₂ = 0, 1, 2, …——有内在不对称:如果n属于集合,见证就在某个有限位置,有限步后会得到“是”;如果n不属于集合,任何有限次失败都不足以支持“否”。“是”这一半机械,“否”这一半缺失,这种集合称为可列举(可证明性P是标准例子:逐个产出全部证明;每个可证明语句最终出现,但未出现不能证明任何事)。
收缩判准。集合完全机械,当且仅当搜索能够正当地截断:存在一个可证明、可计算的界B(n),使得如果有任何见证,就有一个见证在B(n)以下。那么检查v₂ ≤ B(n)即可作出两种判断:量词范围无限,却可证明除了有限部分,其余全不相关。例如“n是偶数”=∃v₂(n = v₂ + v₂);任何见证都满足v₂ ≤ n。
普雷斯堡算术(有+,无·)使这种收缩成为普遍情况:每个公式的每个量词,都可消去为关于余数与顺序的有限可检查事实(∃v₂(n = v₂ + v₂)变成“n除以2余0”)。尽管到处有无界量词,其中的真仍完全机械。
何时能证明它绝不会收缩。对完整算术(+与·),没有程序能判定真。这不是观察某个公式得来的,而是反向运用塔斯基:机械⇒算术的,而T不是算术的。·增加了把有限序列编码成单个数的能力(本章自己的技巧),即谈论任意计算历史的能力;如果这种语言的真可判定,就会判定过多的东西。只有加法不能编码序列,这种贫乏使普雷斯堡算术温顺。
边界提醒。(i)天真搜索失败不能证明什么,可能存在另一种程序;不可判定性主张是定理,不是耸肩。(ii)一个∃就已足以失去“否”的那一半(P不可判定);量词交替的阶梯是定义复杂性的阶梯(算术层级),不是基数的阶梯,这里的所有东西都可数。本次“多个量词→更高阿列夫”的猜想指向了错误的阶梯。
第十部分——区分清单
| 提出的困惑 | 一行解决 |
|---|---|
| §6每项如何现实化第一章? | 两层模式:第一章规定,第二章证明。组件B(编号、命题1、命题2、引理1)是唯一新的数学,把机器谜题的字母N构造成{封装式,r,D};定理1–2逐字重演第一章。 |
| 什么是“内部可命名性”(可谈论性)? | 状态2:L_E某个公式表达集合。区别于状态0(元理论中确定,包括T在内一切都免费具有)与状态1(机械可判定)。集合需要状态2,当且仅当哥德尔语句文本必须提及它。 |
| “F是算术的,F(n̄)也是算术的,这还不够吗?” | 范畴错误:“算术的”是集合/关系/函数的谓词;F(n̄)是语句,只有真或假。证明需要其为算术的东西是编码函数r。 |
| “T不机械,因而不是算术的”? | 包含关系反过来(机械⇒算术的)。P̃是算术的,却甚至不可列举。“真不机械”是塔斯基的推论,不是前提。 |
| “多个量词→阿列夫n→非机械”? | 一切都可数;叠加量词提高定义复杂性(算术层级),不提高基数;一个∃已经能破坏可判定性(P)。 |
| “封装不又绕回去了吗,还不是需要字面代入关系为算术的?” | 不,封装重新定义了代入操作本身。困难的字面关系被放弃,从未被表达;下游只使用真值与编码,封装同样提供这些。 |
| “∀压缩无穷合取,这是封装效率的来源吗?” | 层次错了:封装语句比F(n̄)更长。节省在于E_x未拆封地进入,使输出编码只依赖x这整个块;封装缩短的是计算语句地址的公式,不是语句。 |
| “机器就是字符串的有限拼接/符号中的规则” | 三层:字符串操作→编码函数(元理论,两位作者都便宜)→L_E的命名公式D。“算术的”是关于第三层的主张;全部成本差异都在那里。 |
| “r是算术的=有有限方法算出编码” | 算出编码不需要定理,我们在旁边就能计算r(h, h)。算术性意指L_E能通过D命名r的图;需要它,是因为D作为构件处在H内部。 |
| “H[h̄]的真从哪里来?既然H表达A*,为何不直接用H(h̄)?” | 可表达性只谈字面实例;书中“H[h̄]真⟺h ∈ A*”合并了等价性(步骤5)与可表达性(步骤6)。H(h̄)不能成为展示对象:其自身地址是sub(h, h),本证明没有命名它。 |
| “两种对角化d1、d2,两个星集合,链条经过两者” | 只有一个A:H说什么由嵌入文本的D固定,不由后来怎样代入决定。代入选择结果语句的地址,不能改变公式说什么*(+3/+7例子)。 |
| “H(v₁),为何不是H[v₁]?H(v₁)不是像F(n̄)吗?” | 三层:H(v₁)是展示自由变量的开放公式(恒等代入返回H本身);H(n̄)与H[n̄]是第二层的语句实例。“表达”是第一层性质,通过第二层字面实例检验。 |
| “哥德尔语句按定义就是代入自身编号的公式” | 定义不限定形状:X真⟺g.n.(X) ∈ A。对角化是构造方法,不是定义。(而且X未必真,偶数集合的哥德尔语句是假。) |
| “H(h̄)按定义是哥德尔语句,H[h̄]由等价性也是” | 反了:H[h̄]的真条件命名自身地址(哥德尔语句);H(h̄)的真条件命名兄弟语句的地址(交叉指涉)。等价性传递绝对真条件,不传递自指称号;两个字符串地址不同。 |
| “选择H[h̄]只是因为尚未展示H(h̄)的有限构造” | 无关:两个字符串显然都能有限构造。H(h̄)不满足定义,仅此而已。 |
| “证明把h字面代入H,从而得到哥德尔语句” | 字面代入只在表达的定义中(检验一侧)。展示对象靠封装制造:步骤3说“令X = ∀v₁(v₁ = h̄ ⊃ H)”;没有哪行制造H(h̄);本章只构造r/D机器,sub从未构造。 |
| “把所有数代入F并检查,以找到s” | 可证明搜索零命中:s = g.n.(F(s̄))不可能,因为g.n.(F(s̄)) ≥ 13ˢ > s。真正的构造是计算(写H、读出h、封装),从不搜索。 |
第十一部分——自测
先回答,再看答案。
- 定义“A的哥德尔语句”。哥德尔语句必须真吗?给出反例。
- 定义封装式E_x[ȳ],导出r(x, y)的封闭形式,并证明命题2。x在公式中从不经历什么,为什么这就是全部技巧?
- 陈述并证明引理1。本章究竟在何处、且只在何处使用命题2?
- 重现定理1的九步推导链,每步恰好引用一个定义或定理。
- 证明Φ_lit与Φ_wrap等价。∀的哪个情况承担实质作用,其他情况如何通过?
- 说明即使H(h̄)与X真值相同,它也不是A的哥德尔语句。为什么等价性不能转移称号?
- 证明不存在s使s = g.n.(F(s̄)),说出决定“种子+拉伸”设计的教训。
- 哥德尔对应于命题2的陈述是什么?说出他的路线(两个动作),以及使阶梯漫长的四种难题。陈述三个层次,指出全部成本在哪层。
- 两个旋钮:说出它们,列出四行表,并说明两位作者匹配的一对各需额外支付哪一行。
- 三个层级:H(v₁)是什么?在什么意义上,写出它是“不改变任何东西的代入”?
- 把书中合并的一行“H[h̄]真⟺h ∈ A*”拆成两步,各给理由。
- 从定理1证明塔斯基定理。证明给定理1的机器输入什么,为什么该集合承受不起输出?
- 给出三个状态、状态1与2之间包含的方向、现有材料中反方向的反例,以及哪些集合需要状态2的选择规则。
- ∃定义何时仍可机械判定?陈述收缩判准,给一个能收缩的例子,说出收缩普遍成立的理论,并解释为什么完整算术可证明地绝不会收缩(哪条定理,向哪个方向使用)。
答案
- X是A的哥德尔语句,当且仅当(X真⟺g.n.(X) ∈ A)。不限定形状,没有提及代入。它未必真:取A为偶数集合,构造出的语句是假,编码是奇数,双条件在假的一侧满足(习题6,下次)。
- E_x[ȳ] := ∀v₁(v₁ = ȳ ⊃ E_x)。从字符串读编号:前缀“∀v₁(v₁ =”=固定编码k,然后13ʸ(数码)、8(⊃)、x、3(“)”):r(x, y) = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3。由推论1是算术的(算术成分的五重拼接)。x从未被打开,输出编码只把x当作块来依赖,所以命名公式只需一行。
- 引理1:A算术⇒A = {n : d(n) ∈ A}算术。证明:d(x) = r(x, x)是算术的(命题2),令D表达其图,F表达A;H(v₁) = ∃v₂(D(v₁, v₂) ∧ F(v₂))表达A。命题2在这里且只在这里被使用,提供H内部的D。
- 见第五部分。理由:步骤1,引理1+表达的定义;步骤4,r的定义;步骤5,等价性;步骤6,步骤1取n = h;步骤7,A*的定义;步骤9,哥德尔语句的定义。
- 封装语句真⟺对每个m:(m = n ⊃ F对m成立)。m ≠ n时,⊃条件使它们空真地通过;m = n承担实质作用,要求F对n成立,恰好就是F(n̄)的真条件。
- H(h̄)自身地址为sub(h, h),真条件却命名d(h),即另一个语句的地址。定义比较真与语句自身编码;等价性保留所说的内容(绝对条件),但两个字符串地址不同。“我自己的编码∈A”在每个语句那里重新指向,因此称号不转移。
- F(s̄)包含编码为13ˢ的数码s̄,所以g.n.(F(s̄)) ≥ 13ˢ > s,没有不动点。教训:代入总达不到语句自身地址,因此语句必须携带小种子h与拉伸指令(命名d的D),使d(h)=自身地址。
- “sub(x, y)是算术的。”路线:(i)sub机械,由约31个明确的定义构成阶梯;(ii)桥梁定理,机械⇒算术的。难题:寻找出现(60嵌在600中)、自由性(括号辖域)、全部替换(通过编码序列模拟迭代)、带前导零的重组。层次:字符串操作→编码函数→命名公式;全部成本在第三层。
- 旋钮A:H内部命名哪种对角(写下时固定)。旋钮B:哪种代入制造X(固定地址)。表见第六部分(e)。斯穆里安多的一行:步骤5(等价性,因为可表达性只谈字面探测)。哥德尔多的账单:sub是算术的(那条阶梯),在对应于引理1的内部支付。
- H(v₁)是展示自由变量的开放公式,第一层,从无真或假,划出集合。把v₁代入v₁返回H本身,因此展示记号与代入记号是同一种记号,在退化情况下相遇。
- H[h̄]真⟺H(h̄)真(等价性)⟺h ∈ A*(表达的定义,实例n = h)。书中合并两步,因为引入方括号时已说明过等价性。
- 若T算术,则T̃也算术(取补封闭:~F)。定理1作用于T̃给出X:X真⟺g.n.(X) ∈ T̃⟺g.n.(X) ∉ T⟺X不真,矛盾。机器得到的那个集合,其哥德尔语句将不得不“真当且仅当不真”,所以集合原本就不是算术的。
- 状态0确定(元理论,包括T在内所有集合免费拥有);状态1机械;状态2算术的。状态1⇒状态2(桥梁定理,后面章节);反方向失败:P̃算术,却甚至不可列举。选择规则:集合需要状态2,当且仅当哥德尔语句文本必须提及它(A、d:是;语法:否;T:其失败就是塔斯基)。
- 可判定当且仅当搜索可截断:可证明、可计算的界B(n),满足“见证存在⇒存在见证≤B(n)”。例:偶数,见证≤n。普遍收缩:普雷斯堡算术(量词消去)。完整算术绝不收缩:机械⇒算术的,加上塔斯基(T不算术),即反向使用定理;·使算术能够编码序列,因而编码计算历史。
第十二部分——接下来、当前进度与方法
位置:第二章已完成至§6:命题2、引理1、定理1、定理2(塔斯基)均已证明,而且经过漫长交锋,终于能正确复述。第一章↔第二章的对应已解决(第一部分):引理1是唯一新的数学,其余就是披着13进制外衣的7月15日。
下次:习题6、7、8(书中第27页),特意留待新鲜尝试:
- 习题6:另一种10进制编号(编码1、0、2、3、4、5、6、7、89、899、8999、89999、899999):偶数集合的哥德尔语句真还是假?奇数集合呢?提示:构造的语句总以哪个数字结尾?最后一位在10进制中告诉你什么,而在13进制中不能?
- 习题7:函数f,使对每个n,f(n)在……时是A的某个哥德尔语句的哥德尔数(构造哥德尔句生成器)。提示:把Hₙ的编码做成拼接,让n作为未拆封块进入,即封装技巧再升一层。
- 习题8:交叉指涉的一对:语句X、Y满足X真⟺g.n.(Y) ∈ A,且Y真⟺g.n.(X) ∈ B。提示:双变量封装式∀v₁(v₁ = x̄ ⊃ ∀v₂(v₂ = ȳ ⊃ E))给出r₂(e, x, y);用两种方式对角化它。注意:本次将H(h̄)诊断为“谈论兄弟语句的语句”,正是习题8的现象不请自来。
习题后:第三章,从真走向可证明性,“真”将换成“系统中可证明”;第六部分(d)的前瞻(等价性可证明,不只为真)与第八部分的前瞻(桥梁定理、P̃)将到期。
更新后的欠账表:(1)哥德尔的E消去,仍是最困难的一项。(2)为什么选素数底13,仍欠。(3)性质1⇒性质2,仍欠。(4)现在更迫切地重申:机械⇒算术的(状态1⇒状态2),本次两次依靠它(哥德尔通往sub的路线;“真不机械”作为塔斯基推论);书中会在可证明性章节证明。
继续沿用的方法:关于解释本身的一课。本次最困难的一段不是数学,而是阐述,由此形成一个明确标准,两次提出要求,最终满足:没有未解释的新造词,没有让自创比喻词汇承担关键推理,没有偷带的包袱。每次打破僵局的都是同一个动作:把说明剥成简明编号链,每步恰好引用一个已掌握的定义或定理(第五部分);或者亲手运行一个具体实例(“6是偶数”与“每个等于6的数都是偶数”;+3/+7的例子)。解释中途发明的术语,无论多生动,都是成本,而非赠礼,除非立刻用已经掌握的词语解释。读者一侧互补的教训是:本次三个错误(双对角化链、带代入的定义、字面制造主张)各自都是看似合理的叙述,却把公式说什么(由文本固定)与拿公式做什么(后来选择)混为一谈。当故事听着对,却经不起写成带理由的编号推导链时,推导链才是裁判。
本次复习结束 · 斯穆里安《哥德尔不完备性定理》第二章§6完成,塔斯基定理 · 前序文件:Godel-Incompleteness-Session-2026-07-15.md(第一章框架与机器谜题)、Godel-Incompleteness-Session-2026-07-17-Answer-Sheet.md(第一章习题1–7)、Godel-Incompleteness-Session-2026-07-19.md(第二章§1–§2,语言与真)、Godel-Incompleteness-Session-2026-07-20.md(第二章§3,算术集合/关系/函数,习题2–5)、Godel-Incompleteness-Session-2026-07-21.md(第二章§4–§5,拼接与哥德尔编号)· 下一步:习题6–8,然后第三章。