Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter II, Exercises 6–8: Base-10 Gödel Sentences, the Gödelizer, Cross-Reference
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 — Exercise 6: the base-10 numbering and the false Gödel sentence
- Part II — Exercise 7: the Gödelizer, book architecture
- Part III — Exercise 7: the session's alternative architecture, and the knob repair
- Part IV — Exercise 8: cross-reference — given, goal, chain
- Part V — Exercise 8 anatomy: the accounting principle and its consequences
- Part VI — Concrete instance: A = evens, B = odds, base 10
- Part VII — Distinctions Ledger
- Part VIII — Self-Test
- Part IX — Position, what's ahead, and the method
Study session of July 23, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter II Exercises 6, 7, 8 (book p. 27) · Companion to the sessions of July 15, 17, 19, 20, 21, and 22, 2026 · Chapter II now complete in full
How to use this document
Exercise session: the machinery of July 22 — the wrapper, r, d, Lemma 1, the nine-step chain — run on three concrete assignments. No new theorems were learned; three new constructions were built out of owned parts, and each exercise contributed one idea worth keeping: Exercise 6 — a Gödel sentence can be false, and a well-chosen numbering lets a one-symbol glance at a string settle a property of an uncomputable number; Exercise 7 — the wrapper works with a variable in the slot, not just a numeral (and the session produced an original second architecture, debugged via the knobs table); Exercise 8 — cross-reference is manufactured from a pair of seeds wrapped identically into two formulas, and the whole design is governed by one accounting principle about how a specific number can reach a formula's text. For review: Part I's last-digit argument and the chains of Parts II, III, and IV are the content; the Ledger (Part VII) and Self-Test (Part VIII) are the refresher. A two-sided lesson about explanations — the second failure mode — is recorded in Part IX.
Scorecard, for honesty: Exercise 6 the user solved outright (the last-digit argument was his). Exercise 7 the user solved with an architecture different from the book's — initially buggy, repaired by him after the bug was located in his own July 22 knobs table. Exercise 8 was presented after burnout set in; the user's contribution was auditing the chain, which caught a genuinely missing justification (Part IV, Step 7).
Part I — Exercise 6: the base-10 numbering and the false Gödel sentence
The alternative numbering. Same 13 symbols, base 10 codes:
0 ' ( ) f , v ¬ ⊃ ∀ = ≤ #
1 0 2 3 4 5 6 7 89 899 8999 89999 899999
The numeral ȳ (= 0 followed by y accents) now has code 1 followed by y zeros: 10ʸ (was 13ʸ). Concatenation ∗ is now base-10 gluing: x ∗ y = x·10^(number of digits of y) + y.
The construction, unchanged. A = the even numbers, Arithmetic via ∃v₂(v₁ = v₂ + v₂). Theorem 1's chain runs verbatim in the new numbering and hands us X = ∀v₁(v₁ = h̄ ⊃ H) with
g.n.(X) = r(h, h) = 899602608999 ∗ 10ʰ ∗ 89 ∗ h ∗ 3
(prefix "∀v₁(v₁ =" = digits 899 6 0 2 6 0 8999; then the numeral, ⊃, the block h, and ")").
The question and the lever. Theorem 1 guarantees the biconditional — X is true ⟺ g.n.(X) is even — but not which side holds. Nobody can compute g.n.(X): h is astronomical. But one feature of the string is visible without knowing h: X ends in the symbol ), so g.n.(X) ends in the digit 3. In base 10, the last digit fixes parity. So g.n.(X) is odd, hence not in A, hence — by the biconditional — X is false.
No contradiction, and the payoff of the whole exercise: a false Gödel sentence. The definition is a biconditional; false-X-with-code-outside-A satisfies it on the false side. This is the concrete answer to July 22's Self-Test question 1: a Gödel sentence need not be true.
Part 2, the odd numbers: same string shape, same last digit 3, same odd code — but now the guarantee reads "X true ⟺ g.n.(X) odd," so this X is true. Symmetry worth keeping: the evens' Gödel sentence is a false sentence asserting "my code is even"; the odds' is a true sentence asserting "my code is odd." Both correct about themselves in the only sense the definition demands.
What base 10 bought (and base 13 wouldn't). In base 13, N = Σ dᵢ·13ⁱ and 13 ≡ 1 (mod 2), so every term ≡ dᵢ (mod 2): parity of N = parity of the digit sum — the last digit alone says nothing; you would need all of h. In base 10, parity = last digit alone. Smullyan set the exercise in base 10 precisely so that a one-symbol glance at the string settles a property of a number nobody can write down.
Session repairs en route (all recurrences of known bugs): (i) the stars in the code formula are concatenation, not multiplication — multiplying by 3 doesn't make a number end in 3; (ii) "the Gödel number is ∀v₁(...)" — layer slip; the string is X, the number is the concatenation; (iii) the plugged-in object is the numeral h̄, not the number h.
Part II — Exercise 7: the Gödelizer, book architecture
The task. Find an Arithmetic f such that: if n is the Gödel number of a formula F(v₁), then f(n) is the Gödel number of a Gödel sentence for the set F(v₁) expresses. (On other n, f may output garbage.) Theorem 1 industrialized: not one Gödel sentence for one A, but one machine, uniform in n.
Notation, fixed at the door: Eₙ is the expression whose Gödel number is n (the §5 numbering names an expression for every number). The exercise's hypothesis on n says exactly that this expression is a formula with sole free variable v₁ — so Eₙ = F(v₁): two names for one string. "Eₙ" emphasizes how the proof reaches it (from the number n, as an unopened block); "F(v₁)" emphasizes its shape and job (expressing A). Every Eₙ below may be read as F(v₁).
Entry error, diagnosed first: F(v₁) was momentarily taken for a function with pairs (x, y). No — a formula with one free variable expresses a set of single numbers. The function-shaped thing is f itself, ℕ → ℕ, living in the metatheory like r and d; "f is Arithmetic" means some two-variable formula expresses its graph — and it gets certified by closure (built from Arithmetic pieces), never written by hand.
The reduction. Theorem 1's output address was d(h), h = g.n.(H). So the candidate is f(n) = d(h(n)), where h(n) = g.n. of the formula Hₙ that Lemma 1's recipe builds from Eₙ. d is Arithmetic and compositions of Arithmetic functions are Arithmetic, so the entire exercise reduces to: is n ↦ h(n) Arithmetic?
The trap (two illegal moves attempted in session):
- "F(v₂), whose Gödel number is n" — no: n codes F(v₁). F(v₂) is a different string; producing its code from n requires interior digit-surgery (find occurrences of 60, check freeness, replace by 600, reassemble) — the sub ladder. If Hₙ contains the literal string F(v₂), the exercise re-buys Gödel's ladder.
- "F(d(v₁))" — two crimes: d is not a symbol of L_E (a formula talks about the diagonal only through the graph formula D — the entire reason Proposition 2 exists), and F(anything) is literal substitution — opening the parcel.
The one new idea of the exercise: the wrapper takes a variable. Lemma 1's recipe calls for
∃v₂( D(v₁, v₂) ∧ F(v₂) ) ← defective: the conjunct F(v₂)
The defect: building the string F(v₂) from n means surgery inside Eₙ — dig out the v₁'s, insert v₂'s — the sub ladder. The repair is a drop-in replacement for that one conjunct, nothing more. Put the variable v₂ in the wrapper's slot:
Wₙ := ∀v₁(v₁ = v₂ ⊃ Eₙ) ← the replacement part — not, by itself, the answer to anything
Wₙ's free variable is v₂ (the ∀v₁ binds every v₁, including Eₙ's, exactly as the numeral wrapper Eₙ[m̄] always has; the only novelty is a variable in the guard). Plugging m̄ into v₂ gives Eₙ[m̄], true ⟺ m ∈ A — so Wₙ says "F holds of v₂," exactly what F(v₂) said, but its string is a fixed prefix followed by Eₙ untouched: same meaning, no surgery. Now swap Wₙ into the defective slot, and this is the exercise's actual formula:
Hₙ := ∃v₂( D(v₁, v₂) ∧ Wₙ ) = ∃v₂( D(v₁, v₂) ∧ ∀v₁(v₁ = v₂ ⊃ Eₙ) )
from which the chain below reads off h(n) = p ∗ n ∗ s and f(n) = d(h(n)). (That Wₙ alone cannot be the answer is visible at a glance: its free variable is v₂ and it expresses A itself — merely a restatement of F. Only inside Hₙ, with D pinning v₂ to the diagonal of v₁, does it earn its keep.)
The chain.
Given: n = the Gödel number of a formula F(v₁); A = the set F(v₁) expresses (so for all m: F(m̄) true ⟺ m ∈ A).
Step 1. Eₙ = F(v₁). (Justification: definition of the numbering — Eₙ is the expression whose Gödel number is n — plus the hypothesis on n, which says that expression is F(v₁). This identification is where n enters the construction, and it is the same move as Exercise 8's Step 7 run in the other direction: there a formula in hand was recognized as E_{h₁} because h₁ = g.n.(H₁); here the expression reached from n is recognized as the given formula.)
Step 2. Wₙ := ∀v₁(v₁ = v₂ ⊃ Eₙ). Free variable: v₂ — the ∀ captures every v₁ in its scope, wherever it sits (Step 1 guarantees Eₙ contains free v₁'s; none is ever located). For every m, plugging m̄ into v₂ yields literally ∀v₁(v₁ = m̄ ⊃ Eₙ) = Eₙ[m̄], and: Eₙ[m̄] true ⟺ F(m̄) true ⟺ m ∈ A. (Justification: grammar read off the string; then the equivalence; then Step 1 + the definition of expresses. Wₙ says "F holds of v₂" with Eₙ riding as one unopened block — F(v₂)'s job without F(v₂)'s string.)
Step 3. Hₙ := ∃v₂( D(v₁, v₂) ∧ Wₙ ). Free variable: v₁ — the v₁'s inside Wₙ are bound locally by Wₙ's own ∀; the same variable can be free in one part of a formula and bound in another. For every m: Hₙ(m̄) true ⟺ some value equals d(m) and satisfies Wₙ ⟺ d(m) ∈ A ⟺ m ∈ A. Hₙ expresses A. (Justification: Lemma 1's proof, with Step 2 supplying for Wₙ exactly what expressibility supplied for F(v₂) there. Uniform in n: no step so far opened Eₙ.)
Step 4. h(n) := g.n.(Hₙ) = p ∗ n ∗ s, where p and s are the fixed codes of the prefix "∃v₂( D(v₁, v₂) ∧ ∀v₁(v₁ = v₂ ⊃" and the suffix "))". h is Arithmetic. (Justification: the middle block's code is n — that is Step 1 again, read as numbers — and the string around it is constant; Corollary 1. Proposition 2's proof re-run with n in the parcel position that x occupied.)
Step 5. f(n) := d(h(n)) = r(h(n), h(n)). f is Arithmetic. (Justification: Proposition 2 (d Arithmetic) + Step 4 + closure of Arithmetic functions under composition.)
Step 6 — verification that f does the job. Let X := Hₙ[num(h(n))]. Then g.n.(X) = r(h(n), h(n)) = d(h(n)) = f(n) (definition of r at x = y = h(n), the wrapped expression being E_{h(n)} = Hₙ by Step 4 — the double-role identification once more). And: X true ⟺ Hₙ(num(h(n))) true (the equivalence) ⟺ h(n) ∈ A (Step 3 at m = h(n)) ⟺ d(h(n)) ∈ A (definition of A) ⟺ g.n.(X) ∈ A. So X is a Gödel sentence for A, and f(n) is its Gödel number. ∎ (This is Theorem 1's Steps 2–9 verbatim, with H := Hₙ, h := h(n).)
Part III — Exercise 7: the session's alternative architecture, and the knob repair
The user's proposal: instead of converting Eₙ to speak of v₂, bind Eₙ's native variable directly:
Hₙ := ∃v₁( D(v₂, v₁) ∧ Eₙ )
Eₙ's free v₁ is captured by the ∃v₁ and pinned to the diagonal of v₂ by the first conjunct. Eₙ unopened, no nested wrapper, h(n) = p ∗ n ∗ s as before. Semantically sound: Hₙ holds of m ⟺ (diagonal of m) ∈ A.
The bug, found by running the chain: Hₙ's free variable is now v₂, and the whole downstream kit is calibrated to v₁-formulas.
- Step 3 jams (writing h for h(n)): X = ∀v₁(v₁ = h̄ ⊃ Hₙ) has no free v₁ to pin, and Hₙ's free v₂ sails through — X is not a sentence.
- Obvious fix — wrap on v₂ instead: X = ∀v₂(v₂ = h̄ ⊃ Hₙ). Now X is a sentence, true ⟺ d(h) ∈ A. But its address is d′(h), where r′(x, y) := g.n.(∀v₂(v₂ = ȳ ⊃ Eₓ)) and d′(x) := r′(x, x) — a different diagonal. Truth condition names d(h), address is d′(h): the mismatch row of the July 22 knobs table. A cross-reference, not a Gödel sentence.
The repair (user's): make both knobs point at the same diagonal — put D′ inside, where D′ expresses d′. Entitlement is free: r′(x, y) = k′ ∗ 13ʸ ∗ 8 ∗ x ∗ 3 with k′ = code of "∀v₂(v₂ =" (digits 9 600 2 600 η) — Proposition 2's one-liner with a different constant.
The repaired chain: Hₙ := ∃v₁(D′(v₂, v₁) ∧ Eₙ); h(n) = p ∗ n ∗ s; X := ∀v₂(v₂ = num(h(n)) ⊃ Hₙ); g.n.(X) = r′(h(n), h(n)) = d′(h(n)); X true ⟺ Hₙ holds of h(n) (equivalence, v₂-version — same proof) ⟺ d′(h(n)) ∈ A, i.e. g.n.(X) ∈ A; f(n) = d′(h(n)). ∎
Verdict: two correct architectures, same price. The book's: one diagonal d, wrapper nested inside H. The session's: flat H, the whole kit (r′, d′, D′, equivalence) rebuilt on v₂. What the bug taught, again: what a formula says and what address a manufacturing method assigns are independent choices, and a Gödel sentence exists only where they match.
Part IV — Exercise 8: cross-reference — given, goal, chain
Given: A and B Arithmetic; F expresses A, G expresses B.
Goal: sentences X, Y with (i) X true ⟺ g.n.(Y) ∈ A, and (ii) Y true ⟺ g.n.(X) ∈ B.
Step 1. For expression Eₑ and numbers x, y define Eₑ[x̄, ȳ] := ∀v₁(v₁ = x̄ ⊃ ∀v₂(v₂ = ȳ ⊃ Eₑ)) and r₂(e, x, y) := its Gödel number. Off the string: r₂(e, x, y) = k ∗ 13ˣ ∗ 8 ∗ k′ ∗ 13ʸ ∗ 8 ∗ e ∗ 33. r₂ is Arithmetic. (Corollary 1 — Proposition 2's proof with more blocks.)
Step 2. t(x, y) := r₂(y, x, y) and s(x, y) := r₂(x, x, y) are Arithmetic. (Step 1 + repeating/rearranging argument slots — the move that made d(x) = r(x, x) Arithmetic from r.)
Step 3. Let T(v₁, v₂, v₃) express t's graph; H₁ := ∃v₃( T(v₁, v₂, v₃) ∧ F(v₃) ). For all x, y: H₁(x̄, ȳ) true ⟺ t(x, y) ∈ A. (Lemma 1's proof with t in place of d, pairs in place of single numbers. F is one fixed formula here — unlike Exercise 7, writing F(v₃) by hand once costs nothing; no uniformity in F is needed.)
Step 4. Likewise S expressing s's graph; H₂ := ∃v₃( S(v₁, v₂, v₃) ∧ G(v₃) ): for all x, y, H₂(x̄, ȳ) true ⟺ s(x, y) ∈ B.
Step 5. h₁ := g.n.(H₁), h₂ := g.n.(H₂). (Exist now: H₁, H₂ are finished strings built only from T, S, F, G — their texts mention no h.)
Step 6. X := H₁[h̄₁, h̄₂], Y := H₂[h̄₁, h̄₂]. (Merely written down; sentences, since the two ∀'s bind both variables.)
Step 7. g.n.(X) = r₂(h₁, h₁, h₂) = s(h₁, h₂); g.n.(Y) = r₂(h₂, h₁, h₂) = t(h₁, h₂). (Justification, fully unpacked — the session's audit found the compressed version missing a link: Step 1's definition applies to the string X only once X is recognized as Eₑ[x̄, ȳ] for particular e, x, y. The wrapped numerals are h̄₁, h̄₂ — read off Step 6's string. And the wrapped expression is H₁ = E_{h₁} precisely because Step 5 set h₁ = g.n.(H₁): "the expression whose Gödel number is h₁" is H₁ itself. Hence e = h₁ — and this identification, Step 5 feeding Step 7, is where h₁ acquires its double role: which-formula and wrapped-in value at once. This collision is what s(x, y) = r₂(x, x, y) encodes — the exercise's copy of d(h) = r(h, h).)
Step 8. X true ⟺ H₁(h̄₁, h̄₂) true. (The equivalence, applied twice — outer wrapper, then inner.)
Step 9. H₁(h̄₁, h̄₂) true ⟺ t(h₁, h₂) ∈ A. (Step 3 at (x, y) = (h₁, h₂).)
Step 10. t(h₁, h₂) = g.n.(Y). (Step 7.)
Step 11. Chaining 8–10: X true ⟺ g.n.(Y) ∈ A. Goal (i). ✓
Step 12. Y true ⟺ H₂(h̄₁, h̄₂) true (equivalence, twice) ⟺ s(h₁, h₂) ∈ B (Step 4 at (h₁, h₂)) ⟺ g.n.(X) ∈ B (Step 7). Goal (ii). ✓ ∎
Side-by-side with Theorem 1: Steps 1–2 play Proposition 2's role, Steps 3–4 Lemma 1's, Steps 5–6 are "let h = g.n.(H), let X = H[h̄]," Steps 7–12 are its Steps 4–8 run twice. The only structural novelty is Step 2: two functions read off one r₂ — t computes the other sentence's address (planted inside H₁), s computes this sentence's own (planted inside H₂). The crossing is installed in the formulas' texts, before any sentence exists.
Part V — Exercise 8 anatomy: the accounting principle and its consequences
How a specific number reaches a formula's text — two ways, one extension. (1) As a numeral written in — possible only if the number exists when the formula is written. (2) Through a free variable, delivered at wrapping time. Extension of both: once a formula has hold of n by either way, it can speak of f(n) for any Arithmetic f via f's graph formula — how H spoke of d(h) in Theorem 1 while only receiving h.
Two obstructions force the design. Spec (i) demands H₁ speak of g.n.(Y); a wrapped sentence's code is determined by which formula + which numbers wrapped in (that's all r₂'s closed form contains), so H₁ must receive h₂ and everything wrapped into Y. Could the h's be written-in numerals? (a) Mutual constants circle: h̄₂ inside H₁ requires H₂ finished first, and symmetrically — both, impossible. (b) Own code is barred outright: any string containing the numeral h̄₁ has code ≥ 13^(h₁) > h₁, so it cannot be H₁ — July 22 Part III's undershoot argument, reappearing. So the h's must arrive through free variables, at wrapping time — which is after both formulas are complete strings; that is what breaks the circle.
Bookkeeping → the symmetric design. L₁, L₂ = the numbers wrapped into X, Y. H₁ receives L₁ and needs h₂ and all of L₂; H₂ receives L₂ and needs h₁ and all of L₁. Simplest solution of both containments: L₁ = L₂ = (h₁, h₂) — the same pair into both. Two numbers to receive ⇒ two free variables ⇒ the two-variable wrapper.
Not the unique design. An asymmetric variant exists: write H₂ first, Theorem-1 style with no constants (∃v₂(D(v₁,v₂) ∧ G(v₂))); h₂ then exists, so hardcode h̄₂ into H₁ (which says "r(h₂, v₁) ∈ A"); wrap both sentences with the single number h₁: X = H₁[h̄₁], Y = H₂[h̄₁]. Works with one-variable machinery. The invariant across all solutions is the accounting principle, not the symmetric shape.
Theorem 1 as degenerate case. Set h₁ = h₂ and A = B and the construction collapses into Theorem 1: one seed, one diagonal (s and t coincide — the two-variable analogue of d), and the "other sentence" becomes the sentence itself.
Cross-reference is cheap. Recall July 22's diagnosis of H(h̄): a sentence about its sibling's address — Exercise 8's phenomenon appearing uninvited as a bug. Here it is engineered, symmetric, on purpose. What was ever impossible was not sentences pointing at each other, but self-reference applied to truth itself — Tarski.
Part VI — Concrete instance: A = evens, B = odds, base 10
X says "g.n.(Y) is even"; Y says "g.n.(X) is odd." Both strings end in ), so both codes end in digit 3: both odd. Therefore X asserts of an odd number that it is even — X false; Y asserts of an odd number that it is odd — Y true. Check the spec: X false and g.n.(Y) ∉ A ✓; Y true and g.n.(X) ∈ B ✓. Two sentences, each speaking only of the other, one wrong and one right, no paradox anywhere.
Part VII — Distinctions Ledger
| Confusion raised | One-line resolution |
|---|---|
| ∗ read as multiplication | ∗ is concatenation: x ∗ y = x·10^(digits of y) + y. Multiplying by 3 makes nothing end in 3; concatenating 3 does. |
| "The Gödel number is ∀v₁(v₁ = h̄ ⊃ H)" | Layer slip: that string is X; its number is the concatenation; what X says (d(h) ∈ A) is a third thing. |
| "X is obviously false" (and stop) | The owed sentence: check against Theorem 1 — X false with g.n.(X) ∉ A satisfies the biconditional. A Gödel sentence need not be true. |
| Would last-digit-3 settle parity in base 13? | No: 13 ≡ 1 (mod 2), so parity = parity of digit sum — you'd need all of h. Base 10 makes parity a last-digit property; that is what the exercise's numbering bought. |
| F(v₁) taken for a function with pairs | One free variable ⇒ expresses a set of single numbers. The function in Exercise 7 is f itself (metatheory, like r and d); its Arithmetic-ness comes by closure, never by hand. |
| "F(v₂), whose Gödel number is n" | n codes F(v₁). F(v₂) is a different string; deriving its code from n is interior digit-surgery — the sub ladder. The variable wrapper ∀v₁(v₁ = v₂ ⊃ Eₙ) does F(v₂)'s job with Eₙ unopened. |
| "F(d(v₁))" | Two crimes: d is not a symbol of L_E (graph formula D is how formulas mention the diagonal — Proposition 2's whole point), and F(...) opens F. |
| "Avoid the capture: define E_m := F(v₂) with its own code m, and build Hₙ from E_m" | Legitimate string, fatal cost: h(n) = p ∗ m(n) ∗ s, and n ↦ m(n) — code of F(v₁) in, code of F(v₂) out — is the sub ladder. That's Gödel's route, price included. The wrapper's capture is deliberate and precedented (Eₙ[m̄] binds Eₙ's free v₁ the same way, since Theorem 1); it buys the same meaning with m(n) never needed. |
| "f(n) = X"; "H[h̄] is Arithmetic" | f(n) is a number (= g.n.(X)); Arithmetic is a predicate of sets/relations/functions, and H[h̄] is a sentence. Both are July 22 ledger entries, recurring. |
| Flat Hₙ = ∃v₁(D(v₂,v₁) ∧ Eₙ) "just works" | Its free variable is v₂; the v₁-calibrated wrapper leaves v₂ dangling (X not a sentence), and wrapping on v₂ instead mismatches the knobs (says d, lives at d′) — cross-reference. Repair: D′ expressing d′ = r′(x,x). Then a valid second architecture. |
| "Each sentence must contain the other's Gödel number" | Neither can (mutual constants circle; own code barred by the 13^h undershoot). Each contains the pair of seeds (h₁, h₂), which exist before either sentence, plus a graph formula computing the other's address from the pair. |
| Why the same pair wrapped into both? | Bookkeeping: H₁ needs h₂ and all of L₂; H₂ needs h₁ and all of L₁; L₁ = L₂ = (h₁, h₂) is the simplest solution. Two deliveries ⇒ two free variables ⇒ r₂. |
| Step 7 "read off the string" hides a link | (User's catch.) e = h₁ needs Step 5: H₁ = E_{h₁} because h₁ = g.n.(H₁). That identification is the double role — the exercise's d(h) = r(h, h). |
| Why is H₁ built around t (the other's address function)? | Spec (i) verbatim: X's truth condition must be "g.n.(Y) ∈ A" and g.n.(Y) = t(h₁, h₂). Swap in s and Step 9 becomes "⟺ s(h₁, h₂) ∈ A," which chained with Step 7 delivers "X true ⟺ g.n.(X) ∈ A" — a Gödel sentence for A, not cross-reference. |
| Doesn't mutual reference risk paradox? | Run it concrete (evens/odds, base 10): X false, Y true, spec satisfied, no contradiction. Cross-reference is cheap; Tarski is self-reference on truth. |
Part VIII — Self-Test
Answer before peeking.
- Exercise 6, full chain: why is the evens' Gödel sentence false, and why is that not a counterexample to Theorem 1?
- What exactly did the base-10 numbering buy that base 13 wouldn't? Prove the base-13 half.
- The variable wrapper ∀v₁(v₁ = v₂ ⊃ Eₙ): free variable, meaning, and the two illegal moves it replaces.
- State both Exercise 7 architectures. Where does the flat one jam if run against the v₁-calibrated kit, and what is the repair?
- Why is n ↦ h(n) Arithmetic in either architecture — and which July 22 proof is that argument a re-run of?
- Exercise 8: reproduce the twelve-step chain, citing for each step its justification.
- Unpack Step 7 completely. Where does e = h₁ come from, and what double role does that identification encode?
- The accounting principle: the two ways a specific number reaches a formula's text, the extension, and the two obstructions that bar the h's from being written-in numerals.
- Why the same pair (h₁, h₂) into both sentences? Derive it from the bookkeeping.
- Why does H₁ carry T (the graph of t) rather than S? What would you get instead if you swapped?
- Sketch the asymmetric variant. What does its existence tell you about which part of the construction is essential?
- In what precise sense is Theorem 1 the degenerate case of Exercise 8?
- Run A = evens, B = odds in base 10: truth values of X and Y, with the check against the spec.
Answers
- X = ∀v₁(v₁ = h̄ ⊃ H) ends in ), so g.n.(X) ends in digit 3, hence is odd, hence ∉ evens; by "X true ⟺ g.n.(X) even," X is false. No counterexample: the biconditional is satisfied on the false side — the definition never required truth.
- In base 10, parity = last digit (10 ≡ 0 mod 2). In base 13, N = Σ dᵢ·13ⁱ ≡ Σ dᵢ (mod 2) since 13 ≡ 1 (mod 2): parity = digit-sum parity, needing every digit of the astronomical code. Base 10 makes one visible symbol settle a property of an uncomputable number.
- Free variable v₂ (the ∀ captures every v₁ in its scope — the hypothesis Eₙ = F(v₁) guarantees free v₁'s exist without locating them); plugging m̄ into v₂ gives F(v₁)[m̄], so it says "F holds of v₂" while the code computation uses Eₙ only as an unopened block. Replaces: literal F(v₂) (whose code is not n; deriving it = sub ladder) and F(d(v₁)) (d is not a symbol of L_E; and F(...) opens F).
- Book: Hₙ = ∃v₂(D(v₁,v₂) ∧ ∀v₁(v₁ = v₂ ⊃ Eₙ)), free v₁, f(n) = d(h(n)). Flat: Hₙ = ∃v₁(D′(v₂,v₁) ∧ Eₙ), free v₂. Jam: ∀v₁-wrapper leaves v₂ free (not a sentence); wrapping on v₂ with plain D inside mismatches knobs (says d, lives at d′) — cross-reference. Repair: D′ expressing d′(x) = r′(x,x), r′(x,y) = k′ ∗ 13ʸ ∗ 8 ∗ x ∗ 3; then f(n) = d′(h(n)).
- In both, Hₙ = fixed prefix + Eₙ + fixed suffix as strings, so h(n) = p ∗ n ∗ s — concatenation of constants and the unopened block n: Corollary 1. A re-run of Proposition 2's proof with n in the parcel position x occupied.
- Part IV. Justifications: 1 Corollary 1; 2 slot rearrangement; 3–4 Lemma 1's method; 5 definition of g.n.; 6 written down; 7 definition of r₂ via Steps 5–6, then of s, t; 8 equivalence twice; 9 Step 3 at (h₁,h₂); 10 Step 7; 11 chaining 8–10; 12 mirror.
- r₂'s definition applies to X only once X is recognized as Eₑ[x̄,ȳ]: wrapped numerals (h̄₁, h̄₂) read off Step 6; wrapped expression is H₁ = E_{h₁} because Step 5 set h₁ = g.n.(H₁) — hence e = h₁. The identification gives h₁ two roles at once — which-formula and wrapped-in value — encoded by s(x,y) = r₂(x,x,y); the exercise's copy of d(h) = r(h,h).
- Ways: written-in numeral (number must pre-exist) or free variable (delivered at wrapping); extension: with n in hand, any Arithmetic f(n) is speakable via f's graph formula. Obstructions: mutual constants need each formula finished before the other; own code as numeral is impossible since a string containing h̄ has code ≥ 13ʰ > h. Hence the h's arrive by wrapping, after both formulas exist.
- H₁ receives L₁, needs h₂ ∪ L₂; H₂ receives L₂, needs h₁ ∪ L₁. L₁ = L₂ = (h₁, h₂) solves both containments minimally; two deliveries per formula ⇒ two free variables ⇒ the two-variable wrapper.
- Because spec (i) is "X true ⟺ g.n.(Y) ∈ A" and g.n.(Y) = t(h₁,h₂). With S instead, Step 9 becomes "⟺ s(h₁,h₂) ∈ A," and s(h₁,h₂) = g.n.(X) by Step 7 — so the chain yields "X true ⟺ g.n.(X) ∈ A": a Gödel sentence for A — self-reference where cross-reference was ordered.
- H₂ first, Theorem-1 style (no constants); h₂ exists, so hardcode h̄₂ into H₁ ("r(h₂, v₁) ∈ A"); wrap both with h₁ alone: X = H₁[h̄₁], Y = H₂[h̄₁]. Essential part: the accounting principle — enough must reach each formula to compute the other's address; the symmetric two-variable shape is just its cleanest solution.
- Set h₁ = h₂, A = B: the pair collapses to one seed, s and t coincide (playing d's role — a two-variable analogue, not literally r(x, x)), both sentences into one, and the chain becomes Theorem 1's nine steps.
- Both strings end in ) ⇒ both codes odd. X ("g.n.(Y) even") false; Y ("g.n.(X) odd") true. Spec: X false, g.n.(Y) ∉ A ✓; Y true, g.n.(X) ∈ B ✓. No paradox — cross-reference is cheap.
Part IX — Position, what's ahead, and the method
Position: Chapter II complete in full — text (§1–§6) and exercises (2–5 on July 20; 6–8 today). Every promise of Chapter I has been paid for the concrete language L_E, and today's exercises confirmed the machinery is usable, not just followable: run in a new numbering (Ex. 6), industrialized into a function (Ex. 7, two architectures), and re-plumbed into mutual reference (Ex. 8).
Next session: Chapter III — from truth to provability. "True" becomes "provable in a system," and two forward notes come due: the equivalence is provable, not merely true (July 22, Part VI(d)) — needed for the swap to survive; and the bridge theorem mechanical ⇒ Arithmetic (with P̃ still standing as the counterexample to its converse).
The debt register, unchanged: (1) Gödel's E-elimination. (2) Why prime base 13. (3) Property 1 ⇒ property 2. (4) Mechanical ⇒ Arithmetic — the provability chapters should start paying these down.
The method — the second failure mode of explanations. July 22 established that vivid coinages doing load-bearing work stall an explanation. Today found the failure on both sides of the July 22 fix and located the narrow channel between them. Exercise 8 was first presented as a compressed chain — too dense: "the steps don't connect, grammatically and semantically." The rewrite swung to natural-language paraphrase with fresh coinages ("preloading," "semi-diagonals," analogies) — rejected outright: "you don't need to replace symbolism with natural language — that's the last thing I want." What worked, on the third pass, was neither: symbols retained in full, the derivation of the design separated from the official proof, and every step of the official chain carrying its justification by explicit reference to a numbered step or an owned definition — the Theorem 1 Part V format, which the user requested by name. The channel is narrow: below it, links go invisible; beside it, invented vocabulary smuggles in unpaid debts. And the complementary reader's-side lesson: auditing justifications is not ceremony — the user's Step 7 audit ("this has one more justification: e = h₁, because of Step 5") caught the exact link where the diagonal trick lives. The step that "needs no theorem" is often the step carrying the construction's entire weight, and checking it is how you find that out.
End of session review · Smullyan, "Gödel's Incompleteness Theorems," Chapter II complete (text and Exercises 6–8) · 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), Godel-Incompleteness-Session-2026-07-20.md (Chapter II §3, Exercises 2–5), Godel-Incompleteness-Session-2026-07-21.md (Chapter II §4–§5), Godel-Incompleteness-Session-2026-07-22.md (Chapter II §6, Theorem 1 & Tarski) · Next: Chapter III — provability.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月23日学习记录 · Smullyan《哥德尔不完备定理》第二章练习6、7、8,书第27页 · 2026年7月15、17、19、20、21、22日学习记录的续篇 · 第二章现已全部完成
如何使用本文
练习课:把7月22日的机器,即封装式、r、d、引理1、九步链条,运行在三个具体任务上。没有学习新定理;用已经掌握的部件搭建了三种新的构造,每道练习贡献了一个值得保留的想法:练习6,哥德尔句可以为假,而精心选择的编号使得只看字符串的一个符号,就能确定一个无法算出的数的性质;练习7,封装式的槽位既可放数码,也可放变量,而本次学习产生了原创的第二种架构,通过旋钮表排除了错误;练习8,交叉指称从一对种子制造出来,将它们相同地封装进两个公式,而整个设计受一条记账原则支配,即具体的数如何进入公式文本。复习时:第一部分的末位数字论证,以及第二、三、四部分的链条是内容;第七部分的清单与第八部分的自测用于温习。关于解释的双面教训,即第二种失败模式,记录在第九部分。
如实记分: 练习6由用户直接解决,末位数字论证是他提出的。练习7由用户以不同于书中的架构解决,最初有错,在他自己的7月22日旋钮表中定位错误后,由他修复。练习8在精疲力竭之后才被展示;用户的贡献是审查链条,发现一处确实缺失的理由,第四部分步骤7。
第一部分——练习6:十进制编号与为假的哥德尔句
替代编号。 相同的13个符号,十进制编码:
0 ' ( ) f , v ¬ ⊃ ∀ = ≤ #
1 0 2 3 4 5 6 7 89 899 8999 89999 899999
数码ȳ,即0后接y个撇号,现在的编码为1后接y个零:10ʸ,此前是13ʸ。连接∗现在是十进制拼接:x ∗ y = x·10^(y的位数)+y。
构造不变。 A=偶数集合,可由∃v₂(v₁ = v₂ + v₂)得知是算术的。定理1的链条在新编号下逐字运行,交给我们X=∀v₁(v₁ = h̄ ⊃ H),其中
g.n.(X) = r(h, h) = 899602608999 ∗ 10ʰ ∗ 89 ∗ h ∗ 3
前缀“∀v₁(v₁ =”=数位899 6 0 2 6 0 8999;随后是数码、⊃、块h与“)”。
问题与着力点。 定理1保证双条件关系,X为真⟺g.n.(X)为偶数,却不保证哪一侧成立。没人能算出g.n.(X),h是天文数字。但无需知道h,就能看见字符串的一个特点:X以符号)结尾,所以g.n.(X)以数字3结尾。 十进制中,末位数字确定奇偶性。所以g.n.(X)是奇数,不属于A,因此由双条件关系,X为假。
没有矛盾,而整道练习的收获就是: 一个为假的哥德尔句。定义是双条件式;X为假且编码在A之外,在为假的一侧满足定义。这是对7月22日自测问题1的具体回答:哥德尔句不必为真。
第二小题,奇数集合: 同样的字符串形状,同样的末位数字3,同样的奇数编码,但现在的保证是“X真⟺g.n.(X)为奇数”,因此这个X是真的。值得保留的对称性:偶数集合的哥德尔句是假句,断言“我的编码是偶数”;奇数集合的哥德尔句是真句,断言“我的编码是奇数”。在定义要求的唯一意义上,两者对自身都正确。
十进制带来了什么,十三进制为何做不到。 十三进制中,N=Σ dᵢ·13ⁱ,且13≡1(mod 2),因此每一项≡dᵢ(mod 2):N的奇偶性=各位数字之和的奇偶性,单看末位无从得知;你需要整个h。十进制中,奇偶性只取决于末位数字。Smullyan恰恰为此把练习设置为十进制,让人只瞥一眼字符串的一个符号,就确定一个没人能写下的数的性质。
途中的修复,都是已知错误的复发:(i)编码公式中的星号是连接,不是乘法,乘以3不会让数以3结尾;(ii)“哥德尔数是∀v₁(...)”,层次滑移;字符串是X,数是连接结果;(iii)代入的对象是数码h̄,不是数h。
第二部分——练习7:哥德尔句生成器,书中的架构
任务。 找一个算术函数f,使得:若n是公式F(v₁)的哥德尔数,则f(n)是F(v₁)所表达集合的一个哥德尔句的哥德尔数。对其他n,f可以输出无用内容。把定理1工业化:不只是一个A的一个哥德尔句,而是一台对n统一运行的机器。
先固定记号: Eₙ是哥德尔数为n的表达式,§5的编号为每个数命名一个表达式。练习对n的假设恰好说,这个表达式是仅以v₁为自由变量的公式,因此Eₙ=F(v₁),同一个字符串的两个名字。 “Eₙ”强调证明如何抵达它,从数n抵达一个未拆封的块;“F(v₁)”强调其形状与工作,表达A。下面每个Eₙ都可读作F(v₁)。
先诊断入门错误: 曾一度把F(v₁)当成带有(x,y)对的函数。不是;一个带有一个自由变量的公式表达的是由单个数构成的集合。具有函数形状的是f自身,ℕ→ℕ,与r、d一样存在于元理论中;“f是算术的”意味着某个二变量公式表达其图,而它通过封闭性,由算术部件构造,获得认证,从不亲手写出。
归约。 定理1的输出地址是d(h),其中h=g.n.(H)。因此候选为f(n)=d(h(n)),其中h(n)=引理1的配方从Eₙ构建的公式Hₙ的哥德尔数。d是算术的,算术函数复合仍是算术的,所以整道练习归约为:n↦h(n)是算术的吗?
陷阱,本次尝试过的两个非法动作:
- “F(v₂),其哥德尔数是n”,不对:n编码F(v₁)。F(v₂)是不同的字符串;从n产生它的编码,需要对内部数位动手术,找出60的出现位置,检查自由性,替换为600,再组装,这就是sub阶梯。若Hₙ包含字面字符串F(v₂),练习就重新购买了哥德尔的阶梯。
- “F(d(v₁))”,两项罪过:d不是L_E的符号,公式只能通过图公式D谈论对角函数,这正是命题2存在的全部理由;而F(任何东西)是字面代入,即拆开包裹。
本题唯一的新想法:封装式接受变量。 引理1的配方要求
∃v₂( D(v₁, v₂) ∧ F(v₂) ) ← 缺陷在于合取项F(v₂)
缺陷:从n构造字符串F(v₂),意味着对Eₙ内部动手术,挖出v₁,插入v₂,即sub阶梯。修复只是对那一个合取项作直接替换,仅此而已。把变量v₂放进封装式的槽位:
Wₙ := ∀v₁(v₁ = v₂ ⊃ Eₙ) ← 替换部件,本身并非任何问题的答案
Wₙ的自由变量是v₂,∀v₁约束每个v₁,包括Eₙ中的v₁,与数码封装式Eₙ[m̄]一直所做的一样;唯一新意是在限定条件中放入变量。把m̄代入v₂得到Eₙ[m̄],真⟺m∈A,因此Wₙ说“F对v₂成立”,恰好是F(v₂)说的内容,但其字符串只是固定前缀后接未经触动的Eₙ:含义相同,无需手术。现在把Wₙ放进有缺陷的槽位,这才是本题实际的公式:
Hₙ := ∃v₂( D(v₁, v₂) ∧ Wₙ ) = ∃v₂( D(v₁, v₂) ∧ ∀v₁(v₁ = v₂ ⊃ Eₙ) )
由此,下面的链条读出h(n)=p∗n∗s及f(n)=d(h(n))。Wₙ单独不能成为答案,一眼就看得出:它的自由变量是v₂,表达A自身,只是重述F。只有放在Hₙ内部,由D把v₂固定为v₁的对角值,它才发挥作用。
链条。
已知: n=公式F(v₁)的哥德尔数;A=F(v₁)所表达的集合,因此对所有m:F(m̄)真⟺m∈A。
步骤1。 Eₙ=F(v₁)。 理由:编号的定义,Eₙ是哥德尔数为n的表达式,加上对n的假设,即该表达式就是F(v₁)。这一认定是n进入构造的位置,也是练习8步骤7反方向运行的同一动作:那里,因为h₁=g.n.(H₁),手中的公式被认作E_{h₁};这里,从n抵达的表达式被认作已给公式。
步骤2。 Wₙ := ∀v₁(v₁ = v₂ ⊃ Eₙ)。自由变量:v₂,∀捕获其辖域中的每个v₁,无论位于何处;步骤1保证Eₙ包含自由v₁,但从未定位任何一个。对每个m,把m̄代入v₂,逐字得到∀v₁(v₁ = m̄ ⊃ Eₙ)=Eₙ[m̄],并且:Eₙ[m̄]真⟺F(m̄)真⟺m∈A。 理由:从字符串读出语法;然后用等价关系;再用步骤1与表达的定义。Wₙ说“F对v₂成立”,Eₙ作为一个未拆封块随行;完成F(v₂)的工作,却不使用F(v₂)的字符串。
步骤3。 Hₙ := ∃v₂( D(v₁, v₂) ∧ Wₙ )。自由变量:v₁,Wₙ内部的v₁由Wₙ自身的∀局部约束;同一变量可以在公式的一部分自由,在另一部分被约束。对每个m:Hₙ(m̄)真⟺某个值等于d(m)且满足Wₙ⟺d(m)∈A⟺m∈A。Hₙ表达A。 理由:引理1的证明,步骤2为Wₙ提供的内容,恰好就是那里可表达性为F(v₂)提供的内容。对n统一:迄今没有一步拆开Eₙ。
步骤4。 h(n) := g.n.(Hₙ)=p∗n∗s,其中p、s是前缀“∃v₂( D(v₁, v₂) ∧ ∀v₁(v₁ = v₂ ⊃”与后缀“))”的固定编码。h是算术的。 理由:中间块的编码是n,这是步骤1再次被读作数;周围字符串为常量;用推论1。在命题2证明中原本由x占据的包裹位置放入n,重新运行证明。
步骤5。 f(n) := d(h(n))=r(h(n), h(n))。f是算术的。 理由:命题2,d是算术的,加步骤4,加算术函数对复合的封闭性。
步骤6,验证f完成任务。 令X := Hₙ[num(h(n))]。则g.n.(X)=r(h(n), h(n))=d(h(n))=f(n),r的定义取x=y=h(n),被封装表达式由步骤4为E_{h(n)}=Hₙ,再次出现双重角色认定。并且:X真⟺Hₙ(num(h(n)))真,等价关系,⟺h(n)∈A,步骤3取m=h(n),⟺d(h(n))∈A,A的定义,⟺g.n.(X)∈A。因此X是A的哥德尔句,f(n)是它的哥德尔数。∎ 这就是定理1的步骤2–9,逐字照搬,取H := Hₙ、h := h(n)。
第三部分——练习7:本次提出的替代架构,以及旋钮修复
用户的方案: 不把Eₙ改造成谈论v₂,而直接约束Eₙ原有的变量:
Hₙ := ∃v₁( D(v₂, v₁) ∧ Eₙ )
Eₙ的自由v₁被∃v₁捕获,由第一个合取项固定为v₂的对角值。Eₙ未拆封,没有嵌套封装式,h(n)=p∗n∗s如前。语义上成立:Hₙ对m成立⟺m的对角值∈A。
运行链条发现的错误: Hₙ的自由变量现在是v₂,而整套后续工具按v₁公式校准。
- 步骤3卡住,把h(n)写作h:X=∀v₁(v₁ = h̄ ⊃ Hₙ)没有自由v₁可固定,而Hₙ的自由v₂畅通无阻,X不是句子。
- 显然的修复,改在v₂上封装:X=∀v₂(v₂ = h̄ ⊃ Hₙ)。现在X是句子,真⟺d(h)∈A。但其地址是d′(h),其中r′(x,y) := g.n.(∀v₂(v₂ = ȳ ⊃ Eₓ)),d′(x) := r′(x,x),这是不同的对角函数。真值条件命名d(h),地址却是d′(h):7月22日旋钮表中的失配行。 是交叉指称,而非哥德尔句。
修复,用户提出: 让两个旋钮都指向同一个对角函数,在内部放入D′,D′表达d′。使用许可免费获得:r′(x,y)=k′∗13ʸ∗8∗x∗3,其中k′=“∀v₂(v₂ =”的编码,数位9 600 2 600 η;这是命题2的一行证明,只换了常量。
修复后的链条: Hₙ := ∃v₁(D′(v₂, v₁) ∧ Eₙ);h(n)=p∗n∗s;X := ∀v₂(v₂ = num(h(n)) ⊃ Hₙ);g.n.(X)=r′(h(n), h(n))=d′(h(n));X真⟺Hₙ对h(n)成立,等价关系的v₂版本,证明相同,⟺d′(h(n))∈A,即g.n.(X)∈A;f(n)=d′(h(n))。∎
判定: 两种正确架构,价格相同。书中架构:一个对角函数d,封装式嵌在H中。本次架构:平坦的H,整套工具r′、d′、D′、等价关系在v₂上重建。错误再次教会我们:公式说什么,与制造方法给它分配什么地址,是独立选择;只有两者匹配,才有哥德尔句。
第四部分——练习8:交叉指称,已知、目标、链条
已知: A、B是算术的;F表达A,G表达B。
目标: 句子X、Y满足(i)X真⟺g.n.(Y)∈A,(ii)Y真⟺g.n.(X)∈B。
步骤1。 对表达式Eₑ与数x、y,定义Eₑ[x̄, ȳ] := ∀v₁(v₁ = x̄ ⊃ ∀v₂(v₂ = ȳ ⊃ Eₑ)),令r₂(e,x,y)为其哥德尔数。从字符串读出:r₂(e,x,y)=k∗13ˣ∗8∗k′∗13ʸ∗8∗e∗33。r₂是算术的。 推论1,命题2的证明,只是增加了块。
步骤2。 t(x,y) := r₂(y,x,y),s(x,y) := r₂(x,x,y),两者均算术。步骤1加重复/重排自变量槽位;正是从r得到d(x)=r(x,x)为算术函数的动作。
步骤3。 令T(v₁,v₂,v₃)表达t的图;H₁ := ∃v₃( T(v₁,v₂,v₃) ∧ F(v₃) )。对所有x、y:H₁(x̄,ȳ)真⟺t(x,y)∈A。 引理1的证明,以t替换d,以数对替换单个数。此处F是一个固定公式,与练习7不同,手写一次F(v₃)无需代价,不需要对F统一。
步骤4。 类似地,S表达s的图;H₂ := ∃v₃( S(v₁,v₂,v₃) ∧ G(v₃) ):对所有x、y,H₂(x̄,ȳ)真⟺s(x,y)∈B。
步骤5。 h₁ := g.n.(H₁),h₂ := g.n.(H₂)。现在才存在:H₁、H₂是已经完成的字符串,只由T、S、F、G构成,其文本没有提及任何h。
步骤6。 X := H₁[h̄₁,h̄₂],Y := H₂[h̄₁,h̄₂]。仅仅写下来;它们是句子,因为两个∀约束两个变量。
步骤7。 g.n.(X)=r₂(h₁,h₁,h₂)=s(h₁,h₂);g.n.(Y)=r₂(h₂,h₁,h₂)=t(h₁,h₂)。 完整展开理由,本次审查发现压缩版缺少一环:只有先把X认作某些具体e、x、y对应的Eₑ[x̄,ȳ],步骤1的定义才能适用于字符串X。封装的数码为h̄₁、h̄₂,从步骤6的字符串读出。被封装的表达式是H₁=E_{h₁},恰恰因为步骤5设定h₁=g.n.(H₁):“哥德尔数为h₁的表达式”就是H₁自身。因此e=h₁;这一认定,即步骤5输入步骤7,正是h₁获得双重角色的位置:同时是哪个公式,以及封装进去的值。这一碰撞就是s(x,y)=r₂(x,x,y)所编码的,本题对d(h)=r(h,h)的复本。
步骤8。 X真⟺H₁(h̄₁,h̄₂)真。两次应用等价关系,先外层封装式,再内层。
步骤9。 H₁(h̄₁,h̄₂)真⟺t(h₁,h₂)∈A。步骤3取(x,y)=(h₁,h₂)。
步骤10。 t(h₁,h₂)=g.n.(Y)。步骤7。
步骤11。 连接8–10:X真⟺g.n.(Y)∈A。 目标(i)。✓
步骤12。 Y真⟺H₂(h̄₁,h̄₂)真,两次等价关系,⟺s(h₁,h₂)∈B,步骤4取(h₁,h₂),⟺g.n.(X)∈B,步骤7。目标(ii)。✓∎
与定理1并列比较:步骤1–2担任命题2的角色,步骤3–4担任引理1的角色,步骤5–6是“令h=g.n.(H),令X=H[h̄]”,步骤7–12是把其步骤4–8运行两遍。唯一的结构新意是步骤2:从一个r₂读出两个函数,t计算另一个句子的地址,植入H₁内部;s计算这个句子自己的地址,植入H₂内部。交叉在任何句子存在之前,就安装在公式文本中了。
第五部分——剖析练习8:记账原则及其后果
具体的数如何进入公式文本:两种方式,一个扩展。 (1)以数码写入,只有写公式时该数已经存在才可能。(2)通过自由变量,在封装时送达。两种方式共同的扩展:公式一旦通过任一方式获得n,就能通过f的图公式,谈论任意算术函数f的f(n);定理1中,H只收到h,却谈论d(h),就是如此。
两项障碍迫使我们这样设计。 规格(i)要求H₁谈论g.n.(Y);封装后句子的编码取决于哪个公式+封装了哪些数,r₂的闭式中只有这些,因此H₁必须收到h₂以及封装进Y的一切。能把这些h作为数码写入吗?(a)相互常量的循环: H₁内部的h̄₂要求先完成H₂,反向也一样,两者同时要求,不可能。(b)自身编码被直接禁止: 任何包含数码h̄₁的字符串,其编码≥13^(h₁)>h₁,所以它不可能是H₁;这是7月22日第三部分的不足以达到自身编码的论证再次出现。因此这些h必须通过自由变量,在封装时抵达,也就是在两个公式都已是完整字符串之后;这才打破循环。
记账→对称设计。 L₁、L₂=分别封装进X、Y的数。H₁收到L₁,需要h₂与整个L₂;H₂收到L₂,需要h₁与整个L₁。满足两项包含要求的最简单解:L₁=L₂=(h₁,h₂),把同一数对送入两者。要接收两个数⇒两个自由变量⇒二变量封装式。
并非唯一设计。 存在不对称变体:先写H₂,采用定理1风格,不含常量,∃v₂(D(v₁,v₂) ∧ G(v₂));此时h₂已经存在,因此把h̄₂硬写进H₁,它说“r(h₂,v₁)∈A”;用单个数h₁封装两个句子:X=H₁[h̄₁],Y=H₂[h̄₁]。使用单变量机器也能工作。所有解的不变量是记账原则,而非对称形状。
定理1是退化情形。 令h₁=h₂、A=B,构造便坍缩为定理1:一个种子,一个对角函数,s与t重合,是d的二变量类似物,而“另一个句子”变为句子自身。
交叉指称成本很低。 回忆7月22日对H(h̄)的诊断:一个关于其同胞句子地址的句子,练习8的现象作为错误不请自来。这里则是有意、对称地设计它。从来不可能的并不是句子互相指向,而是将自指用于真理本身,即塔斯基。
第六部分——具体实例:A=偶数,B=奇数,十进制
X说“g.n.(Y)是偶数”;Y说“g.n.(X)是奇数”。两个字符串都以)结尾,所以两个编码都以数字3结尾,都是奇数。因此X断言一个奇数是偶数,X假;Y断言一个奇数是奇数,Y真。检查规格:X假且g.n.(Y)∉A✓;Y真且g.n.(X)∈B✓。两个句子,每个只谈论对方,一个错一个对,处处没有悖论。
第七部分——区分清单
| 提出的困惑 | 一行解答 |
|---|---|
| 把∗读成乘法 | ∗是连接:x∗y=x·10^(y的位数)+y。乘以3不会让什么东西以3结尾;连接3才会。 |
| “哥德尔数是∀v₁(v₁ = h̄ ⊃ H)” | 层次滑移:那个字符串是X;它的数是连接结果;X说的内容,d(h)∈A,是第三件事。 |
| “X显然为假”,然后停下 | 还欠一句:对照定理1检查,X假且g.n.(X)∉A满足双条件式。哥德尔句不必为真。 |
| 在十三进制中,末位为3能确定奇偶性吗? | 不能:13≡1(mod 2),所以奇偶性=各位数字之和的奇偶性,需要整个h。十进制让奇偶性成为末位性质,这正是本题编号买到的东西。 |
| 把F(v₁)当成带数对的函数 | 一个自由变量⇒表达单个数组成的集合。练习7的函数是f自身,元理论中,与r、d相同;其算术性来自封闭性,从不靠手写。 |
| “F(v₂),其哥德尔数是n” | n编码F(v₁)。F(v₂)是不同字符串;从n推导其编码是对内部数位动手术,即sub阶梯。变量封装式∀v₁(v₁ = v₂ ⊃ Eₙ)在不拆开Eₙ的情况下完成F(v₂)的工作。 |
| “F(d(v₁))” | 两项罪过:d不是L_E的符号,公式通过图公式D提及对角函数,这就是命题2的全部要点;而F(...)拆开F。 |
| “避免捕获:定义E_m := F(v₂),具有自己的编码m,再从E_m构建Hₙ” | 字符串合法,成本致命:h(n)=p∗m(n)∗s,而n↦m(n),输入F(v₁)的编码、输出F(v₂)的编码,就是sub阶梯。这是哥德尔路线,价格包含在内。封装式的捕获是有意且有先例的,自定理1起,Eₙ[m̄]就以同样方式约束Eₙ的自由v₁;它买到相同含义,却从不需要m(n)。 |
| “f(n)=X”;“H[h̄]是算术的” | f(n)是数,等于g.n.(X);算术性是集合/关系/函数的谓词,而H[h̄]是句子。两者都是7月22日清单中的复发项目。 |
| 平坦的Hₙ=∃v₁(D(v₂,v₁) ∧ Eₙ)“直接就行” | 其自由变量是v₂;按v₁校准的封装式让v₂悬空,X不是句子;改在v₂上封装则使旋钮失配,说d,住在d′,即交叉指称。修复:让D′表达d′=r′(x,x)。这样就是有效的第二种架构。 |
| “每个句子都必须包含另一个的哥德尔数” | 两者都不能,相互常量造成循环,自身编码被13^h的不足论证禁止。每个句子包含一对种子(h₁,h₂),它们在两个句子之前已经存在,再加一个由数对计算对方地址的图公式。 |
| 为什么把同一个数对封装进两者? | 记账:H₁需要h₂与整个L₂;H₂需要h₁与整个L₁;L₁=L₂=(h₁,h₂)是最简单的解。两项递送⇒两个自由变量⇒r₂。 |
| 步骤7“从字符串读出”隐藏了一环 | 用户发现。e=h₁需要步骤5:H₁=E_{h₁},因为h₁=g.n.(H₁)。这一认定就是双重角色,本题的d(h)=r(h,h)。 |
| 为什么H₁围绕t,即对方地址函数构建? | 逐字依规格(i):X的真值条件必须是“g.n.(Y)∈A”,而g.n.(Y)=t(h₁,h₂)。换入s,步骤9就成为“⟺s(h₁,h₂)∈A”,与步骤7相连,得到“X真⟺g.n.(X)∈A”,即A的哥德尔句,而非交叉指称。 |
| 相互指称难道不会冒悖论风险吗? | 具体运行,偶数/奇数,十进制:X假、Y真,规格满足,无矛盾。交叉指称成本很低;塔斯基针对真理上的自指。 |
第八部分——自测
先回答,再看答案。
- 练习6的完整链条:为什么偶数集合的哥德尔句为假,而这为什么不是定理1的反例?
- 十进制编号到底买到了什么十三进制买不到的东西?证明十三进制的一半。
- 变量封装式∀v₁(v₁ = v₂ ⊃ Eₙ):自由变量、含义,以及它替代的两个非法动作。
- 陈述练习7的两种架构。平坦架构在按v₁校准的工具中运行时哪里卡住,如何修复?
- 为什么两种架构中的n↦h(n)都是算术的,这个论证重新运行了7月22日的哪个证明?
- 练习8:重现十二步链条,为每步引用理由。
- 完整展开步骤7。e=h₁来自哪里,这一认定编码了哪种双重角色?
- 记账原则:具体的数进入公式文本的两种方式、扩展,以及阻止把h作为数码写入的两项障碍。
- 为什么把同一个数对(h₁,h₂)送入两个句子?从记账要求推导。
- 为什么H₁携带T,即t的图,而不是S?若交换,会得到什么?
- 勾画不对称变体。其存在说明构造的哪部分是本质的?
- 定理1在哪个准确意义上是练习8的退化情形?
- 在十进制中运行A=偶数、B=奇数:给出X、Y的真值,并对照规格检查。
答案
- X=∀v₁(v₁ = h̄ ⊃ H)以)结尾,因此g.n.(X)以数字3结尾,所以为奇数,不属于偶数集合;由“X真⟺g.n.(X)为偶数”,X为假。不是反例:双条件关系在为假的一侧被满足,定义从未要求真。
- 十进制中,奇偶性=末位数字的奇偶性,10≡0 mod 2。十三进制中,N=Σ dᵢ·13ⁱ≡Σ dᵢ(mod 2),因为13≡1(mod 2):奇偶性=数位和的奇偶性,需要天文数字编码的每一位。十进制让一个可见符号确定一个无法算出的数的性质。
- 自由变量v₂,∀捕获其辖域中的每个v₁;假设Eₙ=F(v₁)保证自由v₁存在,而无需定位;把m̄代入v₂得到F(v₁)[m̄],因此它说“F对v₂成立”,而编码计算只把Eₙ用作未拆封块。替代:字面的F(v₂),其编码不是n,推导它=sub阶梯;以及F(d(v₁)),d不是L_E的符号,而且F(...)拆开F。
- 书中:Hₙ=∃v₂(D(v₁,v₂) ∧ ∀v₁(v₁ = v₂ ⊃ Eₙ)),自由变量v₁,f(n)=d(h(n))。平坦架构:Hₙ=∃v₁(D′(v₂,v₁) ∧ Eₙ),自由变量v₂。卡点:∀v₁封装式留下自由v₂,不是句子;在v₂上封装而内部用普通D,则旋钮失配,说d、住在d′,即交叉指称。修复:D′表达d′(x)=r′(x,x),r′(x,y)=k′∗13ʸ∗8∗x∗3;于是f(n)=d′(h(n))。
- 两者中,作为字符串Hₙ=固定前缀+Eₙ+固定后缀,因此h(n)=p∗n∗s,常量与未拆封块n的连接,由推论1。重新运行命题2的证明,把n放在原先x占据的包裹位置。
- 见第四部分。理由:1,推论1;2,槽位重排;3–4,引理1的方法;5,g.n.定义;6,写下来;7,通过步骤5–6使用r₂定义,再用s、t定义;8,两次等价关系;9,步骤3取(h₁,h₂);10,步骤7;11,连接8–10;12,镜像。
- 只有把X认作Eₑ[x̄,ȳ],r₂的定义才能适用:封装的数码(h̄₁,h̄₂)从步骤6读出;被封装表达式是H₁=E_{h₁},因为步骤5设定h₁=g.n.(H₁),所以e=h₁。这一认定让h₁同时有两种角色,哪个公式以及封装的值,由s(x,y)=r₂(x,x,y)编码;这是本题对d(h)=r(h,h)的复本。
- 方式:写入数码,数必须预先存在;或者自由变量,在封装时递送。扩展:拿到n后,任意算术f(n)都能通过f的图公式来谈论。障碍:相互常量要求每个公式都比另一个先完成;自身编码作为数码不可能,因为包含h̄的串编码≥13ʰ>h。因此h通过封装抵达,在两个公式都存在之后。
- H₁收到L₁,需要h₂∪L₂;H₂收到L₂,需要h₁∪L₁。L₁=L₂=(h₁,h₂)最小地满足两项包含要求;每个公式递送两项⇒两个自由变量⇒二变量封装式。
- 因为规格(i)是“X真⟺g.n.(Y)∈A”,而g.n.(Y)=t(h₁,h₂)。若改用S,步骤9变为“⟺s(h₁,h₂)∈A”,而步骤7给出s(h₁,h₂)=g.n.(X),因此链条得到“X真⟺g.n.(X)∈A”:A的哥德尔句,在要求交叉指称的位置得到自指。
- 先写H₂,定理1风格,无常量;h₂存在,于是把h̄₂硬写进H₁,“r(h₂,v₁)∈A”;两者只用h₁封装:X=H₁[h̄₁],Y=H₂[h̄₁]。本质部分:记账原则,每个公式必须收到足够信息以计算对方地址;对称的二变量形状只是其最清楚的解。
- 令h₁=h₂、A=B:数对坍缩为一个种子,s与t重合,担任d的角色,是二变量类似物,并非字面上的r(x,x);两个句子合为一个,链条成为定理1的九步。
- 两个字符串都以)结尾⇒两个编码都是奇数。X,“g.n.(Y)为偶数”,假;Y,“g.n.(X)为奇数”,真。规格:X假,g.n.(Y)∉A✓;Y真,g.n.(X)∈B✓。无悖论,交叉指称成本很低。
第九部分——进度、后续与方法
进度:第二章全部完成,正文§1–§6与练习,2–5在7月20日,6–8在今天。第一章的每个承诺都已在具体语言L_E上兑现,今天的练习确认机器是可用的,而不只是能跟着看懂:在新编号中运行,练习6;工业化为函数,练习7,两种架构;重新布线为相互指称,练习8。
下次学习:第三章,从真理到可证性。“真”变为“在一个系统中可证”,两个前瞻事项到期:等价关系是可证的,而不只是为真,7月22日第六部分(d),这是替换后仍然成立所需的;以及机械性⇒算术性的桥梁定理,其中P̃仍作为反向的反例。
未清事项登记,不变: (1)哥德尔的E消去。(2)为什么用素数底数13。(3)性质1⇒性质2。(4)机械性⇒算术性,可证性章节应该开始偿还这些事项。
方法:解释的第二种失败模式。 7月22日确定了,让生动的新造词承担实质作用会使解释停滞。今天在7月22日修复方案的两侧都发现失败,并找到了它们之间的狭窄通道。练习8起初以压缩链条呈现,太密集:“步骤在语法和语义上接不上。”重写又摆到自然语言转述,加上新造词,“预加载”“半对角线”与类比,被直接拒绝:“你不需要用自然语言取代符号,这是我最不想要的。” 第三次真正奏效的方式两者都不是:完整保留符号,把设计的推导与正式证明分开,并让正式链条的每一步通过明确引用某个编号步骤或已掌握定义来携带其理由,也就是用户点名要求的定理1第五部分格式。通道很窄:低于它,联系隐而不见;偏离它,发明的词汇偷带进尚未支付的负担。读者一侧互补的教训是:审查理由不是仪式,用户对步骤7的审查,“这还有一个理由:e=h₁,因为步骤5”,恰好抓住了对角技巧所在的环节。“不需要定理”的步骤,常常就是承担构造全部重量的步骤,而检查它才能发现这一点。
本次学习回顾结束 · Smullyan《哥德尔不完备定理》第二章完成,正文与练习6–8 · 之前文件: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;Godel-Incompleteness-Session-2026-07-22.md,第二章§6、定理1与塔斯基 · 下一步:第三章,可证性。