Gui Ruiyan

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:

  1. 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.
  2. 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.

  1. In Ex 1, why is diagonalizing H (the P*-expressor) at its own index useless, and whose index works?
  2. State in one line why "H(h) provable ⟺ H(h) refutable" plus consistency yields undecidability.
  3. Ex 3: from "X disjoint from P*", what implication do you get, and what converse do you NOT get?
  4. Is "P implies not-P" a contradiction? What does asserting it amount to?
  5. Did Exercise 3 use consistency? What did its work instead, and whose theorem does that foreshadow?
  6. Define d⁻¹(A) in one clause. Does n ∈ d⁻¹(A) require n to be a Gödel number?
  7. Exactly one step of Ex 6's membership chain isn't pure definition-unfolding. Which, and what property of d does it need?
  8. Compute the two Ex 7(a) addresses from scratch (start at 7; machines: n ↦ 3n complements, n ↦ 3n+1 stars).
  9. Why is Ex 7(c)'s answer (31) achievable without correctness, while (a) needs it?
  10. Smullyan defines "a diagonal function" as total with garbage values off the genuine addresses. Name the two payoffs.

Answers

  1. 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.
  2. The biconditional forces both-or-neither; consistency forbids both; so neither — undecidable.
  3. Get: h ∈ X ⟹ h ∉ P. Don't get: h ∉ P ⟹ h ∈ X (X may be a sliver of the complement).
  4. No — it's equivalent to not-P. Asserting it is asserting not-P (reductio shape).
  5. No. The disjointness of the separating set X from P* did the work — Rosser's theorem (Ch. 6).
  6. d⁻¹(A) = {n : d(n) ∈ A}. No — d accepts every number; the only test is where its output lands.
  7. 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."
  8. 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).
  9. (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.
  10. 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.