Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter 1 Exercises 1–7, Answer Sheet & Synopsis
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 / 篇目
Study session of July 17, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter 1 exercises · Companion to the session review of July 15, 2026
How to use this document
Part I is the toolkit — the definitions every exercise runs on. Part II is the Master Move, the single trick all seven exercises are variations of. Part III has full statements and solutions, each followed by "Trap log" notes recording exactly where I got stuck and why. For a fast refresher, Part IV (Distinctions Ledger) alone covers every confusion of the session in one line each. Part V is the map of what each exercise means. Part VI is the self-test.
Part I — The toolkit
- The diagonalization: E_n(n) is the n-th expression applied to its own index; d(n) is its Gödel number. (In the chapter's setting every number indexes an expression, so d is total.)
- The star operation: n ∈ A ⟺ d(n) ∈ A. Concretely: n ∈ P ⟺ E_n(n) is provable; n ∈ R ⟺ E_n(n) is refutable. The star is preimage under d in disguise: A = d⁻¹(A).
- Three grades of "H captures A" — they differ only in which status of H(n) tracks membership:
- H expresses A: H(n) is true ⟺ n ∈ A (semantic)
- H represents A: H(n) is provable ⟺ n ∈ A (syntactic)
- H contrarepresents A: H(n) is refutable ⟺ n ∈ A (syntactic)
- Correct: provable ⟹ true, and refutable ⟹ false. (Two halves — use both.)
- Consistent: no sentence is both provable and refutable.
- Gödel sentence for A: a sentence X such that X is true ⟺ g(X) ∈ A (its truth tracks its own Gödel number's membership in A).
- Incomplete (working target throughout): there is a sentence that is neither provable nor refutable (undecidable). In a correct system, a true unprovable sentence is automatically such a sentence, since refutable sentences are false.
Part II — The Master Move
Every exercise is this, once:
Take a predicate K, let k be its index (K = E_k), and stare at the self-applied sentence K(k) — which is exactly E_k(k). Unwind what each hypothesis says about K(k) until the sentence is cornered.
Two refinements learned the hard way:
- Choose whose index to diagonalize. If the hypothesis speaks the same language as the star (provability for P, refutability for R), diagonalize the given predicate at its own index (Ex 2, 3, 4). If there's a mismatch (Ex 1: "expresses" is about truth, but the mirror condition is about refutability), diagonalize the auxiliary predicate's index and evaluate the original predicate there.
- The corner is almost never an outright contradiction. The sentence lands in a biconditional like "provable ⟺ refutable," and the hypotheses kill one branch (usually "both"), leaving the other ("neither"). If you derive an unconditional absurdity from satisfiable hypotheses, a step went wrong — check your arrows.
Part III — The exercises
Exercise 1
Given: L correct; (1) P is expressible; (2) for any predicate H there is a predicate H′ with: H′(n) provable ⟺ H(n) refutable. Show:* L is incomplete.
Solution. Let H express P* (that's what hypothesis 1 gives). Condition (2) is universally quantified — feed H itself into it — to get H′ with H′(n) provable ⟺ H(n) refutable, for every n. Let k be the index of H′, i.e. H′ = E_k. Chase:
- H(k) is true ⟺ k ∈ P (H expresses P)
- ⟺ E_k(k) is provable (definition of P*)
- ⟺ H′(k) is provable (E_k is H′)
- ⟺ H(k) is refutable (condition 2 at n = k)
So H(k) is true ⟺ H(k) is refutable. If H(k) were true, it would be refutable, hence false by correctness — contradiction. So H(k) is false; reading the biconditional back, it is not refutable. And it is not provable either, by the other half of correctness: provable ⟹ true, but H(k) is false. Neither provable nor refutable: L is incomplete. (The witness is a false undecidable sentence — contrast Ex 7's true ones.)
Trap log. - Diagonalizing H at its own index h is a dead end: it yields "H(h) true ⟺ H(h) provable," whose two cases (true & provable / false & unprovable) are both perfectly consistent. Nothing is cornered. The lesson: the mere existence of a self-referential sentence proves nothing; it must self-refer to the right property. - The negation of "provable" is "not provable" — never "refutable". Those are independent properties. - Quantifier reading: condition (2) doesn't give one fixed pair (H, H′); it is a machine accepting any predicate. The proof works by feeding it the specific predicate that expresses P*.
Exercise 2
Given: "H represents A" means H(n) provable ⟺ n ∈ A. R is representable; L is consistent. Show:* L is incomplete.
Solution. Let H represent R*, with index h. Then:
- H(h) is provable ⟺ h ∈ R* (representation at n = h)
- ⟺ E_h(h) is refutable (definition of R*)
- ⟺ H(h) is refutable (E_h is H)
So H(h) provable ⟺ H(h) refutable: both or neither. Consistency forbids "both." So neither — H(h) is undecidable. L is incomplete.
Trap log. - A biconditional is not itself a contradiction. "P ⟺ R" is satisfied fine when neither side holds. The hypothesis (consistency) eliminates the "both" branch; the conclusion is the surviving "neither" branch. Say it that way. - Direction of the theorem: consistency is the hypothesis, incompleteness the conclusion — "if L is consistent, then L is incomplete." Not the other way around. - Why this exercise matters (Smullyan's bracketed note): "represents" and "consistent" are syntactic — about which strings are derivable, checkable by finite symbol-manipulation, no notion of truth needed. Ex 1's "expresses"/"correct" are semantic. In 1931 (pre-Tarski) truth-talk was philosophically suspect and Hilbert's program demanded finitary metamathematics — a formalist skeptic must accept "consistent ⟹ incomplete" on their own terms. This is why Gödel's real proof is the Ex 2 version.
Exercise 3
Given: some set X with R ⊆ X, X ∩ P = ∅, and X representable by H (index h). Show: L is incomplete. (No consistency assumed!)
Solution. Case analysis on the one sentence H(h).
Suppose H(h) is provable. Two facts about h from two different hypotheses: - From representation (left-to-right): h ∈ X. - H(h) is literally E_h(h); it being provable means, by definition of P, h ∈ P.
So h ∈ X ∩ P = ∅ — impossible. Hence H(h) is not provable.*
Then, by representation read right-to-left: h ∉ X. Since R ⊆ X, being outside the big set forces being outside the small one: h ∉ R. By definition of R, E_h(h) = H(h) is not refutable. Neither provable nor refutable: L is incomplete.*
Trap log. (This exercise generated the most fog — all of it about arrows.) - Disjoint ≠ complement. "X disjoint from P" means X ⊆ ~[P] — possibly a tiny sliver of the complement. It licenses "h ∈ X ⟹ h ∉ P" only. The converse ("h ∉ P ⟹ h ∈ X") is exactly what disjointness does not give. - A chain is only as bidirectional as its weakest link. Gluing an iff to a one-way arrow yields a one-way arrow. My "H(h) provable ⟺ H(h) not provable" pseudo-contradiction came from silently upgrading an implication to an iff mid-chain. - "P implies not-P" is NOT a contradiction — it is a coherent statement equivalent to not-P. That's the reductio shape: suppose provable, derive not provable, conclude not provable. ("P iff not-P" would be a contradiction; that's how to tell you broke something.) - Gap elements are irrelevant. Numbers outside both X and P exist and do nothing — the argument was never about all numbers, only about the one specific h. - Where's consistency? Used nowhere. Disjointness of X from P did the job consistency did in Ex 2. That substitution — build a separating set instead of assuming consistency — is the germ of Rosser's trick (Chapter 6). - Subtle bonus: the hypothesis does imply R ∩ P = ∅ — a consistency-like fact — but only for diagonal sentences. It does NOT imply full consistency of L: a sentence both provable and refutable that is not of the form E_n(n) would be invisible to P and R. General habit: the diagonal map n ↦ E_n(n) hits only the diagonal sentences; P contains plenty of ordinary provable sentences that are nobody's diagonalization. Keep separate books on the image vs. the whole codomain.
Exercise 4
Given: "H contrarepresents A" means H(n) refutable ⟺ n ∈ A. P is contrarepresentable; L consistent. Show:* L is incomplete.
Solution. Let H contrarepresent P*, index h. Then:
- H(h) refutable ⟺ h ∈ P* ⟺ E_h(h) provable ⟺ H(h) provable.
Both or neither; consistency kills "both"; so H(h) is neither provable nor refutable — L is incomplete. Mirror image of Ex 2: there the diagonal sentence said "I am refutable" through its provability; here it says "I am provable" through its refutability.
Exercise 5
Given: a Gödel numbering g where not every number is a Gödel number. A function d(x) is a diagonal function if: for any e, IF e is the Gödel number of an expression E, THEN d(e) = g(E(e)). (On non-Gödel numbers, d outputs anything — garbage allowed, but it always outputs something: d is total.) Show: if d⁻¹(A) is expressible, there is a Gödel sentence for A.
Solution. d⁻¹(A) is the preimage: {n : d(n) ∈ A} — "the numbers d sends into A." Let H express it, and let h = g(H) (every expression has a Gödel number; non-surjectivity only means some numbers name nothing). Two pockets:
- Pocket 1 (expressibility, valid for all n): H(n) true ⟺ d(n) ∈ A. At n = h: H(h) true ⟺ d(h) ∈ A.
- Pocket 2 (diagonal property, fires only where its "if" clause holds): h IS the Gödel number of an expression — namely H — so d(h) = g(H(h)).
Substitute: H(h) is true ⟺ g(H(h)) ∈ A. That is precisely the definition of a Gödel sentence for A, with X = H(h). ∎
Trap log. - d⁻¹(A) is not an inverse function. d needn't be injective or surjective; nobody inverts anything. Preimage = push each n forward, test the output. (Example: d(n) = n², A = {4,5,6,9} ⟹ d⁻¹(A) = {2,3}; the unhit 5 and 6 are harmless.) - A is arbitrary. Nothing says A's elements are diagonal numbers. Stop trying to characterize A; the theorem quantifies over all A. - Membership in d⁻¹(A) has one clause: d(n) ∈ A. It does NOT require n to be a Gödel number — d accepts every number. - How can diagonalization "fail"? The recipe's first step — "find the expression this number is the address of" — presupposes the number IS an address. Under gappy numberings (e.g. prime-power codes 2^a·3^b·5^c…, where most numbers decode to no well-formed expression) that presupposition can be false. The failure is number→expression, never expression→number (a numbering by definition gives every expression an address). - No cardinality problem. Expressions are FINITE strings over a finite alphabet — countably many (list by length, then alphabetically). The uncountable thing (2^ℵ₀ — calling it ℵ₁ is the continuum hypothesis, careful) is the set of INFINITE strings; the monkey's eternal output is one infinite string, but every expression/sentence/proof is a finite chunk. A bijective numbering therefore exists — the chapter's E_0, E_1, … is one. The gappy numberings are chosen anyway for computational transparency: decoding = factoring, substitution = arithmetic on codes, provability becomes expressible inside arithmetic. Ex 5 is the insurance policy: the theorem survives any numbering, elegant or gappy. - Partial vs. total — where the fog was thickest. "Total vs. partial" is about where the function HAS VALUES, not where its values are PINNED DOWN. Smullyan's d has a value at every number (total); it is merely unconstrained off the genuine addresses. Employment-contract analogy: constrained 9-to-5, free otherwise — but you don't cease to exist at 6pm. A partial function is the person who blinks out of existence off-hours, and then questions like "is d(n) in A?" stop having answers. - Smullyan's strategy, one line: d eats every number and always outputs a number; the promise "d(e) = g(E(e))" is in force only when e actually addresses an expression E; off those addresses the output is whatever it is — and no proof ever asks. He says "a diagonal function (rather than the diagonal function)" because many total functions extend the one true partial diagonalization, and any of them will do. Payoffs: the proof is safe (it only evaluates d at h, a genuine address) and the algebra is safe (totality is what Exercise 6 runs on).
Exercise 6
Question: is (Ã) = (A)~ necessarily true? Answer: yes — but only because d is total.
Chase an arbitrary n:
- n ∈ (Ã) ⟺ d(n) ∈ Ã ⟺ d(n) ∉ A ⟺ n ∉ A ⟺ n ∈ (A*)~
Every step is definition-unfolding except "d(n) ∉ A ⟺ n ∉ A", which negates "n ∈ A ⟺ d(n) ∈ A" — valid only because d(n) exists for every n, so "fails to land in A" and "lands outside A" coincide.
Stress test (why it's not trivial): if d were partial, take n with d(n) undefined. Then n ∉ A and n ∉ (Ã) (nothing lands anywhere), yet n ∈ (A)~. The identity fails: (Ã) becomes a proper subset of (A*)~.
Trap log. - Two readings of "not landing in A": (1) positive — the value exists and sits in Ã; (2) negative — it's merely not the case that d(n) ∈ A (also satisfied by nonexistence). The star always demands the positive reading; the complement-of-star is the negative one. Totality glues them together. - Parking analogy: A = paid spots, d(n) = where person n parked. "Car in an unpaid spot" vs. "car not in a paid spot" — same crowd only if everyone owns a car. Carless people are in the second set, not the first. Junk numbers are the carless; the garbage-value trick issues everyone a junk car. - The alternative convention is coherent but costly: declaring "d(n) doesn't exist ⟹ d(n) ∈ A counts as false" preserves all the incompleteness proofs (they only evaluate d at the genuine address h) but flips Ex 6's answer to "no" — star stops commuting with complement, and every complement manipulation carries a junk-number footnote. Smullyan buys frictionless algebra for free. Design lesson: when a definition seems weirdly permissive, the permissiveness usually signals the theorem never looks there, and the definition was engineered so some algebraic identity holds without exceptions.
Exercise 7 — the constructive finale
Given: L correct, nice numbering, and three machine-conditions: (1) E₇ expresses P; (2) if E_n expresses B then E_3n expresses B̃; (3) if E_n expresses B then E_3n+1 expresses B. The machines act on addresses*: from index n compute 3n or 3n+1.
(a) Find a, b < 100 with E_a(b) true but not provable — two solutions.
Plan: manufacture a predicate expressing the complement of P (the chapter's main theorem then delivers a true-unprovable sentence by diagonalization). Two routes to the same set — same destination by Exercise 6* — but different addresses, since 3(3n)+1 ≠ 3(3n+1):
- Route 1, complement then star: E₇ (P) → E₂₁ (P̃) → E₆₄ expresses (P̃) = (P)~. a = b = 64.
- Route 2, star then complement: E₇ (P) → E₂₂ (P) → E₆₆ expresses (P)~. a = b = 66.
The diagonal argument (route 1; route 2 identical): E₆₄(64) true ⟺ 64 ∈ (P)~ ⟺ d(64) ∉ P ⟺ E₆₄(64) not provable. If provable then true (correctness) then not provable — contradiction; so not provable, hence true. True but unprovable.*
(b) Infinitely many pairs. Double complementation is a set-theoretic no-op that changes the address: if E_n expresses B, then E_9n (= 3·(3n)) expresses B again. So E with index 9^k·64 expresses (P*)~ for every k, and each pair (9^k·64, 9^k·64) is a true-unprovable sentence by the same argument. Distinct indices, infinitely many pairs. (The 66-family is a second supply.)
(c) Gödel sentence for the set A expressed by E₁₀. Condition (3): E₃₁ (= 3·10+1) expresses A. Diagonalize: E₃₁(31) true ⟺ 31 ∈ A ⟺ d(31) ∈ A ⟺ g(E₃₁(31)) ∈ A — a Gödel sentence for A. c = d = 31. Note: needed neither the complement machine nor correctness — the star condition alone builds Gödel sentences (that's Exercise 5 in concrete clothing). The extra machinery in (a) is what aims the Gödel sentence at the specific set (P)~ to make it true-but-unprovable*.
The point of Ex 7: Gödel's proof is constructive down to street addresses — you don't learn that an undecidable sentence exists somewhere; you compute 64, 66, 31 by arithmetic on indices.
Part IV — The Distinctions Ledger (every fog of this session, one line each)
| Confusion raised | Resolution |
|---|---|
| Diagonalized H (expressing P*) at its own index; got "true ⟺ provable"; stuck | Dead end by design — both cases are consistent. Diagonalize the mirror predicate's index and evaluate H there. Self-reference must target the right property. |
| Negation of "provable" | "Not provable." Never "refutable" — independent properties. |
| "Condition 2's H is any predicate — why would K (expressing P*) coincide with some H?" | It needn't. The condition is universally quantified: feed K itself into the machine and get K's own mirror. Names carry no magic. |
| "H(h) provable ⟺ H(h) refutable is a contradiction" | A biconditional means both-or-neither. Consistency kills "both," leaving "neither." The biconditional itself is satisfiable. |
| "L has to be incomplete if it is to be consistent" | Backwards. Consistency is the hypothesis, incompleteness the conclusion: consistent ⟹ incomplete. |
| "X disjoint from P, so X = ~[P]" | Disjoint = subset of the complement, possibly a sliver. Yields one implication, never the converse. |
| Chained an iff with a one-way arrow, kept the iff | A chain is only as bidirectional as its weakest link. Output: one-way arrow. |
| "H(h) provable ⟹ H(h) not provable — contradiction!" | Not a contradiction: "P ⟹ ¬P" just means ¬P (reductio). Only "P ⟺ ¬P" is absurd — and deriving it means you broke an arrow. |
| "What about numbers outside both X and P*?" | Real, and irrelevant. The argument is about one specific number h, not the general landscape. |
| Where did Ex 3 use consistency? | Nowhere. Disjointness replaced it — Rosser's trick in embryo (Ch. 6). |
| "The Ex 3 hypothesis implies P and R disjoint" | Only for diagonal sentences. Not every provable sentence is anyone's diagonalization; P* 's image doesn't cover P. Keep separate books: image vs. codomain. |
| Why consistency instead of correctness mattered to Gödel | Consistency/representability are syntactic (finite symbol-checking); correctness/expressibility are semantic (presuppose arithmetic truth, suspect in 1931). "Consistent ⟹ incomplete" binds the formalist skeptic. |
| "d⁻¹(A) — but de-diagonalization can fail!" | Preimage notation, not an inverse: d⁻¹(A) = {n : d(n) ∈ A}. Push forward and test; nothing is pulled back. |
| "A is the set of numbers of the form d(e)…" | A is arbitrary. No structure. Stop characterizing it. |
| "n ∈ d⁻¹(A) means n is a Gödel number such that…" | One clause only: d(n) ∈ A. d accepts every number. |
| "How can diagonalization fail? It's just a recipe" | The recipe's step 1 — "find the expression at this address" — fails on unassigned addresses. Gappy numberings (prime-power codes) leave most numbers naming nothing. |
| "Countably many strings vs. numbers — or is it ℵ₁?" | Finite strings: countable (list by length). Infinite strings: uncountable, 2^ℵ₀ (= ℵ₁ only if CH). Expressions are finite. A bijective numbering exists; gappy ones are chosen for computational transparency. |
| "Constraining only genuine addresses = partial, no?" | No: total/partial is about where the function has values; the constraint is about where values are pinned down. Smullyan's d has (possibly garbage) values everywhere — total, merely unconstrained off the genuine addresses. |
| "Just say the diagonalization doesn't exist, so it's not in A — logic preserved" | Coherent! Proofs survive (they only touch h). But Ex 6's identity fails: junk numbers land in (A)~ but not (Ã). Totality is bought purely for frictionless complement algebra. |
Part V — The map: what each exercise means
| Exercise | Role in the story |
|---|---|
| 1 | Gödel's theorem, semantic flavor: correctness + expressibility of P* + a refutability mirror ⟹ a (false) undecidable sentence. |
| 2 | Gödel's theorem, syntactic flavor — the historically real one: consistency + representability of R* suffice. No truth-talk. |
| 3 | Rosser's germ: a separating set (superset of R disjoint from P) replaces even the consistency assumption. Chapter 6 grows this into Rosser's theorem. |
| 4 | Mirror of Ex 2 through refutability (contrarepresentation); with Ex 2, will be expanded in Chapter 5. |
| 5 | Robustness: the diagonal machinery survives ugly (non-surjective) Gödel numberings; A* generalizes to d⁻¹(A). |
| 6 | The silent lemma: star commutes with complement ⟺ d is total. Explains the garbage-value design of Ex 5 and licenses both routes in Ex 7. |
| 7 | Constructivity: the undecidable sentences have computable street addresses — 64, 66 (true-unprovable), 31 (Gödel sentence for E₁₀'s set). |
Part VI — Self-Test
Answer before peeking; each was worked (or stumbled through) in the session.
- In Ex 1, why is diagonalizing H (the P*-expressor) at its own index useless, and whose index works?
- State in one line why "H(h) provable ⟺ H(h) refutable" plus consistency yields undecidability.
- Ex 3: from "X disjoint from P*", what implication do you get, and what converse do you NOT get?
- Is "P implies not-P" a contradiction? What does asserting it amount to?
- Did Exercise 3 use consistency? What did its work instead, and whose theorem does that foreshadow?
- Define d⁻¹(A) in one clause. Does n ∈ d⁻¹(A) require n to be a Gödel number?
- Exactly one step of Ex 6's membership chain isn't pure definition-unfolding. Which, and what property of d does it need?
- Compute the two Ex 7(a) addresses from scratch (start at 7; machines: n ↦ 3n complements, n ↦ 3n+1 stars).
- Why is Ex 7(c)'s answer (31) achievable without correctness, while (a) needs it?
- Smullyan defines "a diagonal function" as total with garbage values off the genuine addresses. Name the two payoffs.
Answers
- It yields "true ⟺ provable," whose branches (true & provable / false & unprovable) are both consistent — no corner. Use k = index of the mirror H′: then H(k) true ⟺ E_k(k) = H′(k) provable ⟺ H(k) refutable, which correctness corners.
- The biconditional forces both-or-neither; consistency forbids both; so neither — undecidable.
- Get: h ∈ X ⟹ h ∉ P. Don't get: h ∉ P ⟹ h ∈ X (X may be a sliver of the complement).
- No — it's equivalent to not-P. Asserting it is asserting not-P (reductio shape).
- No. The disjointness of the separating set X from P* did the work — Rosser's theorem (Ch. 6).
- d⁻¹(A) = {n : d(n) ∈ A}. No — d accepts every number; the only test is where its output lands.
- Negating "n ∈ A ⟺ d(n) ∈ A" into "n ∉ A ⟺ d(n) ∉ A" — needs d total, so that "fails to land in A" = "lands outside A."
- Route 1: 7 → 21 (complement: P̃) → 3·21+1 = 64 (star: (P̃) = (P)~). Route 2: 7 → 3·7+1 = 22 (star: P) → 3·22 = 66 (complement: (P)~). Sentences: E₆₄(64), E₆₆(66).
- (c) only builds a Gödel sentence for A (truth tracks own-number-in-A) — pure star condition, Ex 5's construction. (a) must additionally conclude the sentence is TRUE and UNPROVABLE, which needs the sentence aimed at (P*)~ and the provable ⟹ true half of correctness to spring the trap.
- Proof-safety (the proofs only evaluate d at the genuine address h, so garbage is never consulted) and algebra-safety (totality makes star commute with complement — Ex 6).
End of answer sheet · Smullyan Ch. 1 exercises 1–7 complete · Previous file: Godel-Incompleteness-Session-2026-07-15.md (framework & machine puzzle) · Next: Chapter 2.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月17日学习记录 · Smullyan《哥德尔不完备定理》第一章练习 · 与2026年7月15日学习回顾配套
如何使用本文
第一部分是工具箱,即每道练习所依赖的定义。第二部分是核心步骤,七道练习都是这一技巧的变式。第三部分给出完整题目与解答,每题之后附有“误区记录”,准确记录我卡在哪里、为什么卡住。如需快速复习,只看第四部分“区别清单”即可,其中用一行概括本次学习的每个困惑。第五部分说明每道练习的意义。第六部分是自测。
第一部分——工具箱
- 对角化:E_n(n)是第n个表达式应用于其自身的序号;d(n)是它的哥德尔数。在本章的设定中,每个数都对应一个表达式,所以d是全函数。
- 星号运算:n ∈ A ⟺ d(n) ∈ A。具体说,n ∈ P ⟺ E_n(n)可证;n ∈ R ⟺ E_n(n)可反驳。星号其实是对d取原像的另一种写法:A = d⁻¹(A)。
- “H刻画A”的三个层次——区别只在于H(n)的哪种状态追踪成员关系:
- H表达A:H(n)为真 ⟺ n ∈ A,语义层面。
- H表示A:H(n)可证 ⟺ n ∈ A,句法层面。
- H反表示A:H(n)可反驳 ⟺ n ∈ A,句法层面。
- 正确:可证 ⟹ 真,可反驳 ⟹ 假。两半都要用。
- 一致:没有语句既可证又可反驳。
- A的哥德尔句:语句X满足,X为真 ⟺ g(X) ∈ A,即其真值追踪自身哥德尔数是否属于A。
- 不完备,全文使用的目标:存在既不可证又不可反驳的语句,即不可判定句。在正确系统中,真而不可证的语句自动满足这一条件,因为可反驳的语句为假。
第二部分——核心步骤
每道练习都做一次这样的事:
取谓词K,令k为其序号,即K = E_k,然后盯住自应用语句K(k),它恰好就是E_k(k)。逐一展开每个假设对K(k)的规定,直到把这个语句逼入特定处境。
两个吃过苦头才学会的细化:
- 选择对谁的序号进行对角化。 如果假设与星号说的是同一种语言,P对应可证性,R对应可反驳性,就在给定谓词自身的序号上对角化,见练习2、3、4。如果两者不匹配,如练习1中“表达”关乎真,而镜像条件关乎可反驳性,就对辅助谓词的序号对角化,再在那里求原谓词的值。
- 最后得到的几乎从不是直接矛盾。 语句落入诸如“可证 ⟺ 可反驳”的双条件,而假设排除一支,通常是“两者都成立”,留下另一支“两者都不成立”。如果从可满足的假设推出无条件的荒谬,就有一步出了问题:检查箭头。
第三部分——练习
练习1
已知: L正确;(1) P可表达;(2) 对任意谓词H,都有谓词H′,满足H′(n)可证 ⟺ H(n)可反驳。证明:* L不完备。
解答。 令H表达P*,这是假设1给予的。条件(2)是全称量化的,把H本身输入其中,得到H′,对每个n都有H′(n)可证 ⟺ H(n)可反驳。令k为H′的序号,即H′ = E_k。依次展开:
- H(k)为真 ⟺ k ∈ P,因为H表达P。
- ⟺ E_k(k)可证,由P*的定义。
- ⟺ H′(k)可证,因为E_k就是H′。
- ⟺ H(k)可反驳,由条件2在n = k处的实例。
所以,H(k)为真 ⟺ H(k)可反驳。如果H(k)为真,它就可反驳,由正确性便为假,矛盾。因此H(k)为假;反向读取双条件,它不可反驳。由正确性的另一半,它也不可证:可证 ⟹ 真,但H(k)为假。既不可证又不可反驳:L不完备。见证是一个假的不可判定句,与练习7中的真句形成对照。
误区记录。 - 在H自身序号h上对角化是死路:它只得到“H(h)真 ⟺ H(h)可证”,而“真且可证”与“假且不可证”两种情形都完全一致,没有被逼出结论。教训是:自指语句的存在本身不能证明任何事;它必须自指于正确的性质。 - “可证”的否定是“不可证”,绝不是“可反驳”。 二者是独立性质。 - 量词的读法:条件(2)不是给出一对固定的(H, H′),而是一台接受任何谓词的机器。证明把表达P*的那个特定谓词输入其中。
练习2
已知: “H表示A”意味着H(n)可证 ⟺ n ∈ A。R可表示;L一致。证明:* L不完备。
解答。 令H表示R*,序号为h。那么:
- H(h)可证 ⟺ h ∈ R*,由表示关系在n = h处的实例。
- ⟺ E_h(h)可反驳,由R*的定义。
- ⟺ H(h)可反驳,因为E_h就是H。
所以,H(h)可证 ⟺ H(h)可反驳:两者都成立,或两者都不成立。一致性禁止“两者都成立”,因此两者都不成立,H(h)不可判定。L不完备。
误区记录。 - 双条件本身不是矛盾。 “P ⟺ R”在两边都不成立时完全可满足。假设,即一致性,排除了“两者都成立”这一支;结论就是留下的“两者都不成立”这一支。要这样表述。 - 定理的方向:一致性是假设,不完备性是结论,即“如果L一致,那么L不完备”,不是反过来。 - 为什么这道练习重要,Smullyan的括注:“表示”与“一致”都是句法性的,关乎哪些符号串可推导,可通过有限的符号操作检查,无须真理概念。练习1中的“表达”与“正确”则是语义性的。1931年,在塔斯基之前,关于真的谈论在哲学上受怀疑,而希尔伯特纲领要求有限主义的元数学;形式主义怀疑者也必须按自己的标准接受“一致 ⟹ 不完备”。因此,哥德尔真正的证明是练习2这个版本。
练习3
已知: 某集合X满足R ⊆ X、X ∩ P = ∅,且X可由H表示,H的序号为h。证明: L不完备。不假定一致性!
解答。 对单个语句H(h)分情况讨论。
假设H(h)可证。 从两个不同假设得到关于h的两个事实: - 由表示关系,从左至右:h ∈ X。 - H(h)字面上就是E_h(h);它可证,依P的定义意味着h ∈ P。
因此h ∈ X ∩ P = ∅,不可能。所以H(h)不可证。*
接着,反向运用表示关系:h ∉ X。由于R ⊆ X,在大集合之外,就必定在小集合之外,所以h ∉ R。由R的定义,E_h(h) = H(h)不可反驳。既不可证又不可反驳:L不完备。*
误区记录。 这道题产生了最多迷雾,全都与箭头有关。 - 不相交 ≠ 互补。 “X与P不相交”意味着X ⊆ ~[P],X可能只是补集的一小片。这只允许推出“h ∈ X ⟹ h ∉ P”;逆命题“h ∉ P ⟹ h ∈ X”,恰恰是由不相交无法得到的。 - 推理链的双向性,取决于其中最弱的一环。 把一个当且仅当与一个单向箭头连接,只会得到单向箭头。我得出的“H(h)可证 ⟺ H(h)不可证”这一伪矛盾,就是在链条中悄悄把蕴含升级为当且仅当造成的。 - “P蕴含非P”不是矛盾,而是一个与非P等价的一致陈述。这就是反证法的形状:假设可证,推出不可证,结论为不可证。“P当且仅当非P”才会是矛盾;看到它,就知道某一步被弄坏了。 - 间隙中的元素无关紧要。 同时在X与P之外的数确实存在,却不起作用;论证从来不关乎所有数,只关乎那个特定的h。 - 一致性在哪里? 完全没有用到。 X与P不相交,完成了练习2中一致性的工作。以构造分离集合替代假定一致性,这一替换就是罗瑟技巧的萌芽,见第六章。 - 一个微妙的补充:假设确实蕴含R ∩ P = ∅,这是类似一致性的事实,但只针对对角语句。它不蕴含L的完全一致性:若某句既可证又可反驳,却不是E_n(n)的形式,P与R就看不见它。一般习惯:对角映射n ↦ E_n(n)只命中对角语句;P中有许多普通可证句,并非任何表达式的对角化。像与整个陪域要分开记账。
练习4
已知: “H反表示A”意味着H(n)可反驳 ⟺ n ∈ A。P可反表示;L一致。证明:* L不完备。
解答。 令H反表示P*,序号为h。那么:
- H(h)可反驳 ⟺ h ∈ P* ⟺ E_h(h)可证 ⟺ H(h)可证。
两者都成立,或都不成立;一致性排除前者,因此H(h)既不可证又不可反驳,L不完备。这是练习2的镜像:那里,对角句通过其可证性说“我可反驳”;这里则通过其可反驳性说“我可证”。
练习5
已知: 哥德尔编号g中,并非每个数都是哥德尔数。函数d(x)是一个对角函数,如果:对任意e,若e是表达式E的哥德尔数,则d(e) = g(E(e))。在非哥德尔数上,d可以输出任意东西,允许垃圾值,但总会输出某个值:d是全函数。证明: 如果d⁻¹(A)可表达,就存在A的哥德尔句。
解答。 d⁻¹(A)是原像:{n : d(n) ∈ A},即“被d送入A的那些数”。令H表达它,令h = g(H)。每个表达式都有哥德尔数;不满射只意味着某些数不命名任何东西。分装在两个口袋里:
- 口袋1,可表达性,对所有n有效:H(n)真 ⟺ d(n) ∈ A。在n = h处,H(h)真 ⟺ d(h) ∈ A。
- 口袋2,对角性质,只在“如果”条件满足时触发:h确实是一个表达式的哥德尔数,即H的哥德尔数,所以d(h) = g(H(h))。
代入:H(h)真 ⟺ g(H(h)) ∈ A。 这恰好是A的哥德尔句的定义,取X = H(h)。∎
误区记录。 - d⁻¹(A)不是逆函数。 d不必单射或满射;这里没有求逆。原像就是把每个n正向送入,再检验输出。例如d(n) = n²,A = {4,5,6,9},则d⁻¹(A) = {2,3};未被命中的5与6无妨。 - A是任意的。 没有任何条件说A的元素是对角数。不要试图刻画A;定理量化遍及所有A。 - 属于d⁻¹(A)只有一个条件:d(n) ∈ A。它不要求n是哥德尔数,d接受每一个数。 - 对角化怎么会“失败”? 操作的第一步,“找到以这个数为地址的表达式”,预设该数确实是地址。在有空缺的编号中,例如素数幂编码2^a·3^b·5^c…,大多数数解码不出合式表达式,这一预设可能不成立。失败发生在数→表达式,而从不发生在表达式→数,因为编号按定义给每个表达式一个地址。 - 没有基数问题。 表达式是有限字母表上的有限符号串,只有可数多个,按长度再按字母序排列即可。不可数的是无限符号串的集合,其基数为2^ℵ₀;把它称作ℵ₁就是连续统假设,要小心。猴子永远打出的输出是一个无限串,但每个表达式、语句、证明都是有限片段。因此,双射编号存在,本章的E_0、E_1、…就是一个。之所以仍选择有空缺的编号,是为了计算上的透明性:解码就是因数分解,代入就是编码上的算术,可证性因此能够在算术内部被表达。练习5提供保险:无论编号整齐还是有空缺,定理都成立。 - 偏函数与全函数,这是迷雾最浓的地方。 “全或偏”关乎函数在哪里有值,而非其值在哪里被规定。Smullyan的d对每个数都有值,所以是全函数;它只是在真正地址之外不受约束。劳动合同的类比:朝九晚五受约束,其余时间自由,但你不会在下午六点停止存在。偏函数则像一个下班后就从存在中消失的人,此时“d(n)是否在A中”这样的问题就不再有答案。 - 用一句话概括Smullyan的策略:d吞下每个数,始终输出一个数;只有当e确实是表达式E的地址时,“d(e) = g(E(e))”这一承诺才生效;在其它地址之外,输出是什么就是什么,证明从不询问。他说的是“一个对角函数”,而非“那个对角函数”,因为许多全函数都能延拓那个真正的偏对角化函数,任何一个都够用。收益有二:证明安全,因为只在真正地址h处计算d;代数安全,因为练习6依赖全函数性。
练习6
问题: (Ã) = (A)~必然成立吗?答案:成立,但只是因为d是全函数。
追踪任意n:
- n ∈ (Ã) ⟺ d(n) ∈ Ã ⟺ d(n) ∉ A ⟺ n ∉ A ⟺ n ∈ (A*)~
每一步都是展开定义,唯独“d(n) ∉ A ⟺ n ∉ A”是在否定“n ∈ A ⟺ d(n) ∈ A”;只有因为每个n都有d(n)存在,这才有效,使“未落入A”与“落在A之外”重合。
压力测试,说明为何并非平凡: 若d是偏函数,取d(n)未定义的n。那么n ∉ A,也有n ∉ (Ã),因为没有东西落到任何地方;但n ∈ (A)~。等式失败:(Ã)成为(A)~的真子集*。
误区记录。 - “没有落入A”的两种读法:(1) 肯定性的,值存在且位于Ã;(2) 否定性的,只是d(n) ∈ A不成立,值不存在时也满足。星号总要求肯定性读法,星号之后的补集则是否定性读法。全函数性把二者接合。 - 停车类比:A是收费车位,d(n)是第n个人停车之处。“车在非收费车位”与“车不在收费车位”,只有人人有车时才指同一群体。无车者属于后一个集合,不属于前一个。垃圾数就像无车者;垃圾值技巧给每个人发一辆破车。 - 另一种约定是自洽的,但有代价:规定“d(n)不存在 ⟹ d(n) ∈ A算作假”,保留了全部不完备性证明,因为它们只在真正地址h上计算d,却让练习6的答案变成“不成立”。星号不再与补集交换,每次补集运算都得附一条关于垃圾数的脚注。Smullyan免费获得了顺畅的代数。定义设计的教训:当某个定义看起来宽容得奇怪时,这种宽容通常表明定理从不查看那些地方,而定义是为了使某个代数恒等式无例外成立而设计的。
练习7——构造性的压轴
已知: L正确,编号良好,且有三个机器条件:(1) E₇表达P;(2) 若E_n表达B,则E_3n表达B̃;(3) 若E_n表达B,则E_3n+1表达B。机器作用于地址*:由序号n计算3n或3n+1。
(a) 找出a, b < 100,使E_a(b)真而不可证,给出两组解。
计划:制造一个表达P之补集的谓词,本章主定理随后通过对角化给出真而不可证的语句。通往同一集合的两条路线,由练习6*保证终点相同,但地址不同,因为3(3n)+1 ≠ 3(3n+1):
- 路线1,先补集后星号: E₇ (P) → E₂₁ (P̃) → E₆₄表达(P̃) = (P)~。a = b = 64。
- 路线2,先星号后补集: E₇ (P) → E₂₂ (P) → E₆₆表达(P)~。a = b = 66。
对角论证,以路线1为例,路线2相同:E₆₄(64)真 ⟺ 64 ∈ (P)~ ⟺ d(64) ∉ P ⟺ E₆₄(64)不可证。若可证,由正确性便为真,因而不可证,矛盾;所以不可证,因而为真。真而不可证。*
(b) 无限多组数对。 双重取补在集合论上不改变集合,却改变地址:若E_n表达B,则E_9n,即3·(3n),再次表达B。因此,对每个k,序号为9^k·64的E都表达(P*)~;每个数对(9^k·64, 9^k·64)都由同一论证给出真而不可证的语句。序号不同,数对无限多。以66开头的族是另一批来源。
(c) 为E₁₀所表达的集合A构造哥德尔句。 由条件(3),E₃₁,即3·10+1,表达A。对角化:E₃₁(31)真 ⟺ 31 ∈ A ⟺ d(31) ∈ A ⟺ g(E₃₁(31)) ∈ A,因此是A的哥德尔句。c = d = 31。 注意:既不需要补集机器,也不需要正确性;星号条件本身就能构造哥德尔句,这是练习5的具体版本。(a)中的额外机制,把哥德尔句瞄准特定集合(P)~,才使其真而不可证*。
练习7的要点: 哥德尔证明的构造性具体到门牌号;你不仅知道某处存在不可判定句,还能通过序号算术算出64、66、31。
第四部分——区别清单:本次学习的每处迷雾,各用一行说明
| 提出的困惑 | 澄清 |
|---|---|
| 在表达P*的H自身序号上对角化,得到“真 ⟺ 可证”,然后卡住 | 这本来就是死路,两种情形都一致。对镜像谓词的序号对角化,再在那里计算H。自指必须瞄准正确性质。 |
| “可证”的否定 | “不可证”,绝不是“可反驳”;二者独立。 |
| “条件2的H是任意谓词,为什么表达P*的K会与某个H重合?” | 不必如此。条件是全称量化的,把K本身输入机器,就得到K自己的镜像。名称没有魔力。 |
| “H(h)可证 ⟺ H(h)可反驳是矛盾” | 双条件意味着两者都成立或都不成立。一致性排除前者,留下后者。双条件本身可满足。 |
| “L若要一致,就必须不完备” | 方向反了。一致性是假设,不完备性是结论:一致 ⟹ 不完备。 |
| “X与P不相交,所以X = ~[P]” | 不相交意味着是补集的子集,可能只是一小片。只给出一个方向的蕴含,不给逆命题。 |
| 把当且仅当接上单向箭头,却保留当且仅当 | 链条的双向性取决于最弱的一环。输出是单向箭头。 |
| “H(h)可证 ⟹ H(h)不可证,矛盾!” | 不是矛盾:“P ⟹ ¬P”只意味着¬P,即反证法。只有“P ⟺ ¬P”荒谬;若推出它,说明弄坏了某个箭头。 |
| “同时在X与P*之外的数怎么办?” | 确实存在,但无关紧要。论证针对一个特定数h,而非总体分布。 |
| 练习3在哪里使用一致性? | 完全没有。不相交取代了它,是罗瑟技巧的萌芽,见第六章。 |
| “练习3的假设蕴含P与R不相交” | 只对对角句如此。并非每个可证句都是谁的对角化;P*的像不覆盖P。像与陪域要分开记账。 |
| 为什么对哥德尔而言,一致性而非正确性很重要 | 一致性与可表示性是句法性的,可通过有限符号检查;正确性与可表达性是语义性的,预设算术真理,在1931年受到怀疑。“一致 ⟹ 不完备”让形式主义怀疑者也必须接受。 |
| “d⁻¹(A),但反对角化可能失败!” | 这是原像记号,不是逆函数:d⁻¹(A) = {n : d(n) ∈ A}。正向送入再检验,没有求逆。 |
| “A是形如d(e)的数的集合……” | A是任意的,没有结构要求。不要刻画它。 |
| “n ∈ d⁻¹(A)意味着n是满足某条件的哥德尔数……” | 只有一个条件:d(n) ∈ A。d接受每一个数。 |
| “对角化怎么会失败?它不就是操作步骤吗?” | 第一步“找到这个地址上的表达式”会在未分配地址上失败。有空缺的编号,如素数幂编码,让大多数数不命名任何东西。 |
| “可数多个符号串与数,还是ℵ₁?” | 有限串可数,按长度排列即可;无限串不可数,基数2^ℵ₀,只有连续统假设成立时才等于ℵ₁。表达式是有限的。双射编号存在;选择有空缺的编号,是为了计算透明。 |
| “只约束真正地址,不就是偏函数吗?” | 不是。全或偏关乎函数在哪里有值;约束关乎值在哪里被规定。Smullyan的d处处有值,可能是垃圾值,所以是全函数,只在真正地址之外不受约束。 |
| “只说对角化不存在,所以不在A中,逻辑仍保留” | 自洽!证明保留,因为只触及h。但练习6的等式失败:垃圾数落在(A)~中,却不在(Ã)中。全函数性纯粹是为了顺畅的补集代数。 |
第五部分——地图:每道练习的意义
| 练习 | 在整体中的作用 |
|---|---|
| 1 | 语义版哥德尔定理:正确性 + P*可表达 + 可反驳性的镜像 ⟹ 一个假的不可判定句。 |
| 2 | 句法版哥德尔定理,也是历史上真正的版本:一致性 + R*可表示就足够。不谈真理。 |
| 3 | 罗瑟的萌芽:一个分离集合,即包含R且与P不相交的集合,甚至替代了一致性假设。第六章将其发展为罗瑟定理。 |
| 4 | 通过可反驳性,即反表示,得到练习2的镜像;它与练习2将在第五章中展开。 |
| 5 | 稳健性:对角机制在不漂亮的非满射哥德尔编号下仍成立;A*推广为d⁻¹(A)。 |
| 6 | 隐含引理:星号与补集交换 ⟺ d是全函数。它解释了练习5的垃圾值设计,并允许练习7的两条路线。 |
| 7 | 构造性:不可判定句有可计算的门牌号,64、66给出真而不可证句,31给出E₁₀所表达集合的哥德尔句。 |
第六部分——自测
先回答,再看答案;每题都曾在本次学习中解决,或磕磕绊绊地走过。
- 练习1中,为什么在表达P*的H自身序号上对角化没有用?谁的序号有用?
- 用一句话说明,“H(h)可证 ⟺ H(h)可反驳”加上一致性,为什么推出不可判定性。
- 练习3:由“X与P*不相交”,能得到哪个蕴含,又不能得到哪个逆命题?
- “P蕴含非P”是矛盾吗?断言它等于断言什么?
- 练习3使用了一致性吗?什么替代了它,又预示谁的定理?
- 用一个条件定义d⁻¹(A)。n ∈ d⁻¹(A)要求n是哥德尔数吗?
- 练习6的成员关系链中,恰有一步不只是展开定义。是哪一步?需要d的什么性质?
- 从头计算练习7(a)中的两个地址:从7开始,n ↦ 3n取补,n ↦ 3n+1加星号。
- 为什么练习7(c)的答案31无须正确性就能得到,而(a)需要正确性?
- Smullyan把“一个对角函数”定义为真正地址之外取垃圾值的全函数。指出这样做的两项收益。
答案
- 它得到“真 ⟺ 可证”,而“真且可证”与“假且不可证”两支都一致,没有被逼出结论。使用镜像H′的序号k:H(k)真 ⟺ E_k(k) = H′(k)可证 ⟺ H(k)可反驳,正确性便能逼出结论。
- 双条件迫使两者都成立或都不成立;一致性禁止都成立,所以都不成立,即不可判定。
- 能得到h ∈ X ⟹ h ∉ P;不能得到h ∉ P ⟹ h ∈ X,因为X可能只是补集的一小片。
- 不是,它等价于非P。断言它,就是断言非P,是反证法的形状。
- 没有。分离集合X与P*不相交承担了这一工作,预示罗瑟定理,见第六章。
- d⁻¹(A) = {n : d(n) ∈ A}。不要求;d接受每个数,唯一检验的是输出落在哪里。
- 将“n ∈ A ⟺ d(n) ∈ A”否定为“n ∉ A ⟺ d(n) ∉ A”;需要d为全函数,使“未落入A”=“落在A之外”。
- 路线1:7 → 21,取补得到P̃,→ 3·21+1 = 64,加星号得到(P̃) = (P)~。路线2:7 → 3·7+1 = 22,加星号得到P,→ 3·22 = 66,取补得到(P)~。语句是E₆₄(64)、E₆₆(66)。
- (c)只构造A的哥德尔句,即真值追踪自身编号是否属于A,只需星号条件,是练习5的构造。(a)还必须得出语句为真且不可证,这要求它瞄准(P*)~,并使用正确性中“可证 ⟹ 真”的一半来触发论证。
- 证明安全:证明只在真正地址h上计算d,从不查看垃圾值;代数安全:全函数性使星号与补集交换,见练习6。
答案页结束 · Smullyan第一章练习1–7完成 · 前一文件:Godel-Incompleteness-Session-2026-07-15.md,框架与机器谜题 · 下一步:第二章。