Gui Ruiyan

Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理

Study journals ·

Gödel's Incompleteness — Chapter II, §6: Diagonalization and Gödel Sentences — Tarski's Theorem

Reflections · Study sessions

AI-prepared recaps of study sessions; these are working notes, not verbatim transcripts. / AI 整理的学习记录,并非逐字实录。

Reading / 研读:Raymond Smullyan / 雷蒙德·斯穆里安 · Gödel’s Incompleteness Theorems 哥德尔不完备性定理

In this note / 篇目

Study session of July 22, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter II Part III, §6 (Proposition 2, Lemma 1, Theorem 1, Theorem 2 — Tarski's Theorem; book pp. 24–27) · Companion to the sessions of July 15, 17, 19, 20, and 21, 2026 · Exercises 6–8 deferred to next session


How to use this document

This follows the order in which understanding was actually built. The session's character was again different: not foundational probes (July 21) or one recurring bug (July 20), but one proof — Theorem 1 — fought for across many rounds, through a chain of misconceptions each of which had to be located precisely before the next could surface. The version that finally settled it is the bare numbered chain in Part V; everything before it is the material the chain compresses, and everything after it is the anatomy of why each step is what it is. For review: Parts I–IX in order the first time; afterwards Part V (the chain) plus the Distinctions Ledger (Part X) are a full refresher. The Self-Test (Part XI) tells you whether it took. A hard-won lesson about how to explain is recorded at the end of Part XII: when an explanation stalls, the cure is the bare chain — every step citing exactly one definition or theorem, no invented vocabulary.


Part I — The opening question: Chapter I made concrete

The session opened with: each proposition, lemma, and theorem here is an actualization of the structural proof from Chapter I — how exactly do they correspond?

The two-level pattern (July 15, Part IX) pays out. Chapter I stipulated properties of an abstract language — expressions are numbered, diagonalization is nameable, and then the Gödel-sentence theorem and Tarski's theorem follow by short arguments. Chapter II proves those stipulated properties hold for the concrete language L_E. So the chapter splits into two components:

  • Component B — the arithmetization labor (the genuinely new math): the base-13 numbering (§5), Proposition 1 (∗ is Arithmetic, §4), Proposition 2 (r is Arithmetic), Lemma 1 (A Arithmetic ⇒ A Arithmetic). This is the work of earning* what Chapter I assumed.
  • Component A — the diagonal argument itself (unchanged from Chapter I): the proofs of Theorem 1 and Theorem 2, which replay the abstract argument word for word once Lemma 1 is in hand.

The pipeline:

§5 numbering ──► Prop 1 (∗ Arithmetic) ──► Prop 2 (r Arithmetic) ──► Lemma 1 (A* Arithmetic) ──► Theorem 1 (Gödel sentences) ──► Theorem 2 (Tarski)
└────────────────── Component B: new math ──────────────────────┘   └───────── Component A: Chapter I replayed ─────────┘

The correspondence table, with the July 15 machine puzzle as third column:

Chapter I (stipulated) Chapter II (proved for L_E) Machine puzzle (toy)
expressions enumerated E₁, E₂, … base-13 Gödel numbering; Eₙ = the expression whose digits spell n strings over P N ~ ( )
a diagonalization operation on expressions, with a code function d the wrapper E_x[ȳ] and r(x, y); d(x) = r(x, x) the norm of an expression
"nameability is preserved by diagonalization": A nameable ⇒ A* nameable Lemma 1 — the single genuinely new theorem, paid for by Proposition 2 the letter N
every nameable set has a Gödel sentence Theorem 1 G = ~PN(~PN)
the set of truths is not nameable Theorem 2 (Tarski) no machine prints exactly the true sentences

The moral the table carries: {wrapper, r, D} is the letter N. In the puzzle, N was handed to us as a primitive of the machine language; here it must be built, and Proposition 2 is the receipt. Everything downstream of Lemma 1 is July 15 again.


Part II — The new objects: wrapper, r, Proposition 2, d, A*, Lemma 1

The wrapper. For any expression E_x and number y, define

E_x[ȳ]  :=  ∀v₁(v₁ = ȳ ⊃ E_x)

— read: "for every v₁, if v₁ equals ȳ, then E_x." When E_x is a formula with free variable v₁, this sentence has the same truth value as the literal substitution E_x(ȳ) (proved in Part IV) — but its string leaves E_x intact as an unopened block, and that is the entire trick.

The code function r. r(x, y) := g.n.(E_x[ȳ]). Read the Gödel number straight off the string ∀ v ′ ( v ′ = ȳ ⊃ E_x ): prefix "∀v₁(v₁ =" is a fixed string with a fixed code k = digits 9 6 0 2 6 0 η; then the numeral ȳ (code 13ʸ, by §5); then ⊃ (digit 8); then E_x (code x); then ) (digit 3):

r(x, y) = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3

Proposition 2. r(x, y) is Arithmetic. Proof: the displayed equation is a 5-fold concatenation of Arithmetic ingredients — constants, the numeral-coding function y ↦ 13ʸ (Arithmetic, July 21 Part IX), and the free slot x — so Corollary 1 finishes it in one line. ∎ Note what x does in this formula: it is never opened. The output code depends on x only as a whole block. Compare Gödel's counterpart in Part IV.

The diagonal and the star. d(x) := r(x, x) = the code of E_x diagonalized on its own index. For any number set A:

A* := {n : d(n) ∈ A}

Lemma 1. If A is Arithmetic, so is A.* Proof: d is an Arithmetic function (Proposition 2 with x = y, one more ∃ to identify the slots), so let D(v₁, v₂) express its graph; let F(v₁) express A. Then

H(v₁) := ∃v₂( D(v₁, v₂) ∧ F(v₂) )

expresses A: H(n̄) is true ⟺ some m has D(n̄, m̄) and F(m̄) true ⟺ m = d(n) and d(n) ∈ A ⟺ n ∈ A. ∎

Where Proposition 2 is spent — and its only appearance in the whole chapter: inside this proof, supplying D. The sentence H must internally say "the diagonal of my input lands in A," and D is the sub-machine that says "the diagonal of." (This settles the session question "what is r's Arithmetic-ness for?" — see Ledger, and Part VI.)


Part III — Why direct self-reference is impossible

Before the real construction, the plan that every newcomer (and this session's reconstruction attempt) reaches for first, and why it is dead on arrival.

The naive plan. F expresses A, so F(n̄) is true ⟺ n ∈ A, for every n. If the plugged number could be the finished sentence's own code — S = F(s̄) with s = g.n.(S) — the Gödel-sentence biconditional would hold immediately. Required: a number s with

s = g.n.(F(s̄))

The refutation, one line. The string F(s̄) contains the numeral s̄, whose code alone is 13ˢ (July 21, Part IX). So g.n.(F(s̄)) ≥ 13ˢ > s, for every s. No solutions — not "hard to find": provably zero hits, so no search of any length can succeed. A sentence's code strictly exceeds every number plugged into it: plugging always undershoots the sentence's own address. (July 15's "poster containing a full-size copy of itself," reincarnated in code arithmetic.)

The moral that dictates the whole construction: since the sentence cannot contain its own address, it must instead contain a small seed plus a stretching instruction, arranged so that the stretch of the seed equals the address. The stretch is d; the seed is h; the arrangement is Theorem 1.


Part IV — Two plugging operations, their equivalence, and Gödel's price tag

The two operations. For a formula F (free variable v₁) and number n:

Φ_lit(F, n)  = F(n̄)                    — literal substitution: open F, replace each free v₁ by n̄   (Gödel)
Φ_wrap(F, n) = ∀v₁(v₁ = n̄ ⊃ F)         — the wrapper: staple n̄ on the front, F intact              (Smullyan)

The equivalence. For every F and n, Φ_lit(F, n) and Φ_wrap(F, n) have the same truth value. Proof: the wrapped sentence is true ⟺ every number m satisfies "if m = n then F holds of m." For m ≠ n the condition holds vacuously (the ⊃-guard passes them free); the only case that bears weight is m = n, where it says: F holds of n. And F(n̄) is true ⟺ F holds of n. Same condition, same truth value. ∎ — Concrete instance carried through the session: "6 is even" versus "every number that equals 6 is even."

Three layers — the distinction that unlocked Gödel's side. For both men there are three separate objects, and conflating them was a recurring session bug:

  1. The string operation — what you do to the sentence on paper (substitute / wrap).
  2. The code function ℕ × ℕ → ℕ — sub(x, y) or r(x, y), tracking what layer 1 does to Gödel numbers. Lives in the metatheory; perfectly computable and easy to describe in English for both men. Having this machine costs nothing.
  3. The naming formula D of L_E — true of (x, y, z) exactly when the layer-2 function sends (x, y) to z. "Arithmetic" is the claim that layer 3 exists. All the cost difference between Gödel and Smullyan lives here.

Gödel's counterpart to Proposition 2 is: sub(x, y) is Arithmetic, where sub(x, y) = g.n. of the literal substitution. His route: show sub is mechanical — buildable by a ladder of ~31 explicit definitions — then invoke a general bridge theorem, every mechanical function is Arithmetic (the status 1 ⇒ status 2 bridge; on the debt register, owed by a later chapter of Smullyan too). Why the ladder is long: sub's output code depends on the interior digits of x —

  • find the occurrences of v₁ (digit pattern 60 — and 60 sits inside 600, the code of v₂: occurrence-finding must not misfire);
  • determine which occurrences are free (requires parsing parenthesis scope);
  • replace each occurrence, one at a time (formulas can't loop: iteration must be simulated by coding whole sequences of intermediate results into single numbers);
  • reassemble without leading-zero accidents.

Smullyan's r treats x as an unopened parcel — output code = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3 — so layer 3 is one line. The correct slogan (replacing a wrong analogy raised in session — see Ledger): the wrapper does not shorten the sentence (it lengthens it); it shortens the formula that computes the sentence's address as a function of the input addresses.


Part V — Theorem 1: the bare chain

Theorem 1. Every Arithmetic set A has a Gödel sentence — a sentence X with: X is true ⟺ g.n.(X) ∈ A.

Ingredients used, and nothing else: the definition of expresses, the definition of r and d, Proposition 2, Lemma 1, the equivalence, the definition of A*, the definition of Gödel sentence.

Given: A is Arithmetic.

Step 1. By Lemma 1, A = {n : d(n) ∈ A} is Arithmetic. So there is a formula H, free variable v₁, such that for every n: H(n̄) is true ⟺ n ∈ A. (Justification: definition of "expresses." H(n̄) means literal substitution — that is how "expresses" is defined. Proposition 2 is consumed inside Lemma 1's proof, supplying D. This is Proposition 2's only appearance.)

Step 2. Let h = the Gödel number of H.

Step 3. Let X = ∀v₁(v₁ = h̄ ⊃ H). (This string is what H[h̄] abbreviates. Nothing is claimed yet; X is merely written down.)

Step 4. g.n.(X) = r(h, h) = d(h). (Justification: r(x, y) is defined as the Gödel number of ∀v₁(v₁ = ȳ ⊃ E_x); apply with x = y = h. No theorem needed — this is reading the numbering rules off the string in Step 3.)

Step 5. X is true ⟺ H(h̄) is true. (Justification: the equivalence. Its only appearance.)

Step 6. H(h̄) is true ⟺ h ∈ A. (Justification: Step 1 with n = h.)*

Step 7. h ∈ A ⟺ d(h) ∈ A. (Justification: definition of A.)

Step 8. Chaining 5, 6, 7: X is true ⟺ d(h) ∈ A. By Step 4, d(h) = g.n.(X). Therefore: X is true ⟺ g.n.(X) ∈ A.

Step 9. By the definition of Gödel sentence, X is a Gödel sentence for A. ∎

Each ingredient is spent exactly once: Proposition 2 at Step 1 (inside Lemma 1), the definition of r at Step 4, the equivalence at Step 5, expressibility at Step 6, the definition of A* at Step 7.


Part VI — Anatomy: why each step is what it is

(a) The definition of Gödel sentence mentions no substitution. It is a condition on a finished sentence — its truth versus its own address — and says nothing about how the sentence was manufactured or what shape it has. Diagonalization is the construction method that finds such a sentence; folding the method into the definition was a session error that generated several others.

(b) Two sentences, one Gödel sentence. At the end of Step 2, two candidate sentences exist, both true ⟺ d(h) ∈ A:

sentence its own address truth condition verdict
X = ∀v₁(v₁ = h̄ ⊃ H) r(h, h) = d(h) d(h) ∈ A truth condition names its own address: Gödel sentence ✓
H(h̄) sub(h, h) — a different number, which nothing in this proof names d(h) ∈ A truth condition names the other sentence's address: a cross-reference, not a Gödel sentence ✗

Both say the same thing about the same number; that number is the home address of only one of them. H(h̄) is not "also a Gödel sentence pending some verification" — it fails the definition outright. And finiteness is a red herring: both strings are trivially finitely constructible; constructibility was never anyone's problem.

(c) Why equivalence cannot transfer Gödel-sentence-hood. Equivalence transfers truth conditions stated in absolute terms ("true ⟺ d(h) ∈ A" — both sentences share it). But Gödel-sentence-hood is "true ⟺ my own code ∈ A," and "my own" re-points at each sentence. Equivalent sentences are different strings with different addresses, so a self-referential title does not ride along. Equivalence preserves what sentences say; being a Gödel sentence is about whether what you say is about you.

(d) Where the equivalence is cashed — the fused line. The book's proof writes "H[h̄] is true ⟺ h ∈ A." That line is two steps fused: Steps 5 and 6 of the chain. Expressibility, by its definition, licenses only statements about the literal instances H(n̄); the silent half-step from the wrapped X to the literal H(h̄) is the equivalence. That half-step is its entire appearance in the chapter. And downstream (Theorem 2 and beyond) consumes Theorem 1 only through its finished statement — truth and code, nothing finer — so the joint never reopens. (Forward note: when "true" becomes "provable in a system," instance-by-instance truth-agreement would not suffice by itself — but ∀v₁(v₁ = h̄ ⊃ H) ⟺ H(h̄) is a logical* equivalence, provable from pure logic, so the swap survives into the incompleteness chapters.)

(e) The two knobs. The plugging operation appears twice in the proof, and the two appearances are independent choices:

  • Knob A — which diagonal is named inside H (which D is embedded). Fixed when H is written; determines what everything built from H says.
  • Knob B — which plugging manufactures X from H and h. Determines X's address: literal → sub(h, h); wrapped → r(h, h).

A Gödel sentence needs truth condition and address to name the same number, so the knobs must match:

inside H manufacture X says X's address verdict
d (wrapped) wrap d(h) ∈ A d(h) match — Smullyan
d (wrapped) literal d(h) ∈ A sub(h, h) mismatch
d_lit = sub(x, x) literal d_lit(h) ∈ A d_lit(h) match — Gödel (price: sub Arithmetic, the ladder)
d_lit wrap d_lit(h) ∈ A r(h, h) mismatch

Each man plays a matched pair. In Smullyan's row, expressibility (defined via literal probes) doesn't apply to the wrapped X directly — hence the one borrowed line of Step 5. In Gödel's row, no equivalence is needed anywhere — but the D inside H costs the ladder. The equivalence line is, precisely, the bill for the wrapper: one line of semantic glue at the end, in exchange for a chapter of digit-surgery in the middle. What H says is fixed by its text, not by how you later plug — a plugging method chooses the address of the resulting sentence and cannot retroactively change which function H names. (Session counterexample: H = "v₁ + 3 is even," plug in 5 by either method — both results are about 8; no delivery method turns +3 into +7.)

(f) Three ranks of notation. The session's last knot, and its dissolution:

  • Rank 1 — open formula: H, written H(v₁) only to display which variable is free. No substitution happened — or, equally, the degenerate substitution of v₁ for itself, which returns H. Never true or false; it carves a set (the numbers satisfying it).
  • Rank 2 — sentences: H(n̄) and H[n̄], both. Each is a truth-valued instance answering "does n satisfy H?" — two thermometers for the same temperature, which is exactly what the equivalence certifies.

"H(v₁) expresses A" is a rank-1 assertion (the set satisfying H is A), cashed at rank 2 through the literal instances. Misreading H(v₁) as rank 2 — as if v₁ were a plugged-in thing — was the root of the "why not H[v₁]?" confusion.

(g) Where literal substitution actually lives in the proof. In the definition of expresses — the infinitely many instances H(n̄) through which truth conditions are known — and nowhere else. The proof's exhibit is manufactured by wrapping (Step 3); no line of Theorem 1 manufactures H(h̄); its truth value is consulted (Steps 5–6) and the string discarded. And "the machine we have" is the wrapping machine (r, D) — sub was never built; refusing to build it is Smullyan's whole economy.


Part VII — Theorem 2: Tarski's Theorem

T := the set of Gödel numbers of the true sentences of L_E — a perfectly definite set (status 0; Part VIII), courtesy of §5.

Theorem 2. T is not Arithmetic.

Proof. Suppose it were, via a formula F. Then ~F expresses the complement T̃ (Arithmetic sets are closed under complement), so by Theorem 1, T̃ has a Gödel sentence X:

X is true ⟺ g.n.(X) ∈ T̃ ⟺ g.n.(X) ∉ T ⟺ X is not true

— the last step by the definition of T itself (a sentence's code is in T exactly when the sentence is true). Contradiction. ∎

Note the shape: Theorem 1 is a machine — feed it any Arithmetic set, receive a Gödel sentence. Tarski's theorem feeds it a set that cannot afford one (a Gödel sentence for T̃ is a sentence true iff not true), concluding the set was never Arithmetic. T's forced failure of nameability is not an inconvenience the proof works around; it is the theorem.


Part VIII — The three statuses: a nameability audit

A recurring session theme, finally systematized. For a set of numbers, three independent gradations:

  • Status 0 — definite: a well-defined set in the metatheory. Costs nothing; every set discussed has it, including T. (Naming a set "T" in our own discourse requires nothing of L_E.)
  • Status 1 — mechanical: some finite procedure decides membership, both verdicts.
  • Status 2 — Arithmetic (internally nameable): some formula of L_E expresses it.

The inclusion runs one way: status 1 ⇒ status 2 (the bridge theorem, proved later in the book; Gödel's route to sub uses it). Not conversely: P̃ — the complement of the provable sentences' codes — is Arithmetic (in the systems studied later) yet not even listable. And "truth is not mechanical" is a corollary of Tarski (status 1 ⇒ status 2, and T lacks status 2), not a premise available before it.

The selection rule — which sets need status 2: exactly those the Gödel sentence's own text must mention. Audit:

set / function needs status 2? why
A (the target set) yes F sits inside H
d (the diagonal) yes D sits inside H
grammar ("is a formula") no the proof never writes a sentence about grammaticality; garbage strings get numbers and are harmlessly ignored
T its failure is the theorem Tarski = the audit coming back negative

Part IX — Quantifiers and mechanicality: when infinite search collapses

The session's parallel thread, resolved cleanly at the end.

The naive reading of ∃. For the set defined by ∃v₂ φ(n, v₂) (φ directly checkable), the obvious procedure — try v₂ = 0, 1, 2, … — has a built-in asymmetry: if n is in the set, a witness sits at a finite position and YES arrives after finitely many steps; if n is not, no finite failure justifies NO. YES-half mechanical, NO-half missing — such a set is called listable (P, provability, is the standard example: grind out all proofs; every provable sentence eventually appears; absence proves nothing).

The collapse criterion. The set is fully mechanical exactly when the search can be legitimately cut off: a provable, computable bound B(n) such that if any witness exists, one exists below B(n). Then checking v₂ ≤ B(n) decides both ways — the quantifier's range is infinite, but all-but-finitely-much of it is provably irrelevant. Example: "n is even" = ∃v₂(n = v₂ + v₂); any witness satisfies v₂ ≤ n.

Presburger arithmetic (+ without ·) is the collapse made total: every quantifier in every formula can be eliminated in favor of finitely checkable facts about remainders and order (∃v₂(n = v₂ + v₂) becomes "n leaves remainder 0 mod 2"); truth there is fully mechanical despite unbounded quantifiers throughout.

When it provably never collapses. For full arithmetic (+ and ·), no procedure decides truth — not by inspection of any formula, but by Tarski run backwards: mechanical ⇒ Arithmetic, and T is not Arithmetic. What · adds is the power to code finite sequences into single numbers (this chapter's own trick), i.e., to talk about arbitrary computation histories — a language whose truth, were it decidable, would decide too much. Addition alone cannot code sequences; that poverty is Presburger's tameness.

Guardrails. (i) Failure of the naive search proves nothing — a different procedure might exist; undecidability claims are theorems, never shrugs. (ii) One ∃ already suffices to lose the NO-half (P is undecidable); the ladder of quantifier alternations is a ladder of definitional complexity (the arithmetical hierarchy), not of cardinality — everything in sight is countable. The session's "multiple quantifiers → higher alephs" guess pointed at the wrong ladder.


Part X — Distinctions Ledger

Confusion raised One-line resolution
How does each §6 item actualize Chapter I? Two-level pattern: Ch. I stipulated, Ch. II proves. Component B (numbering, Prop 1, Prop 2, Lemma 1) is the only new math — it builds the machine puzzle's letter N as {wrapper, r, D}; Theorems 1–2 are Chapter I replayed verbatim.
What is "internal nameability" (talkaboutability)? Status 2: some formula of L_E expresses the set. Distinct from status 0 (definite in the metatheory — free for everything, including T) and status 1 (mechanically decidable). A set needs status 2 iff the Gödel sentence's text must mention it.
"F is Arithmetic, so F(n̄) is Arithmetic too — isn't that enough?" Category error: Arithmetic is a predicate of sets/relations/functions; F(n̄) is a sentence — just true or false. The thing whose Arithmetic-ness the proof needs is the code function r.
"T is not mechanical, hence not Arithmetic"? Inclusion runs the other way (mechanical ⇒ Arithmetic). P̃ is Arithmetic yet not even listable. "Truth not mechanical" is a corollary of Tarski, not its premise.
"Multiple quantifiers → aleph-n → non-mechanical"? Everything is countable; stacking quantifiers climbs definitional complexity (arithmetical hierarchy), not cardinality — and one ∃ already breaks decidability (P).
"Doesn't the wrapper circle back — don't we still need the literal-substitution relation to be Arithmetic?" No: the wrapper redefines the plugging operation itself. The hard literal relation is abandoned, never expressed; downstream consumes only truth values and codes, which the wrapper supplies identically.
"∀ condenses infinite ANDs — is that the wrapper's efficiency?" Wrong layer: the wrapped sentence is longer than F(n̄). The saving is that E_x rides unopened, so the output's code depends on x as one block — the wrapper shortens the formula computing the sentence's address, not the sentence.
"The machine is a finite concatenation of strings / a rule in the symbols" Three layers: string operation → code function (metatheory; cheap for both men) → naming formula D of L_E. "Arithmetic" is a claim about layer 3; all cost differences live there.
"r Arithmetic = we have a finite way to crank out codes" Cranking needs no theorem — we compute r(h, h) in the margin. Arithmetic means L_E can name r's graph via D — needed because D sits inside H as a building block.
"Where do we get H[h̄]'s truth? Why not just use H(h̄), since H expresses A*?" Expressibility speaks only of literal instances; the book's "H[h̄] true ⟺ h ∈ A*" fuses equivalence (Step 5) + expressibility (Step 6). And H(h̄) can't be the exhibit: its own address is sub(h, h), which nothing in the proof names.
"Two diagonalizations d1, d2, two star sets, chains through both" Only one A exists: what H says is fixed by the D baked into its text, not by how you later plug. Plugging picks the resulting sentence's address; it cannot change what the formula says* (the +3/+7 example).
"H(v₁) — why not H[v₁]? Isn't H(v₁) like F(n̄)?" Three ranks: H(v₁) is the open formula with its free variable displayed (identity substitution returns H itself); H(n̄) and H[n̄] are rank-2 sentence instances. "Expresses" is a rank-1 property, tested through rank-2 literal instances.
"A Gödel sentence is by definition a formula with its own number substituted in" The definition is shape-free: X true ⟺ g.n.(X) ∈ A. Diagonalization is the construction method, not the definition. (And X need not be true — the evens' Gödel sentence is false.)
"H(h̄) is a Gödel sentence by definition; H[h̄] is one by equivalence" Backwards: H[h̄]'s truth condition names its own address (Gödel sentence); H(h̄)'s names its sibling's (a cross-reference). Equivalence transfers absolute truth conditions, never a self-referential title — the two strings have different addresses.
"We pick H[h̄] only because H(h̄)'s finite construction isn't shown" Red herring: both strings are trivially finitely constructible. H(h̄) fails the definition, full stop.
"The proof substitutes h literally into H to arrive at the Gödel sentence" Literal substitution lives only in the definition of expresses (the testing side). The exhibit is manufactured by wrapping: Step 3 says "let X = ∀v₁(v₁ = h̄ ⊃ H)"; no line manufactures H(h̄); the only machine built this chapter is r/D — sub was never constructed.
"Find s by plugging all numbers into F and checking" The search provably has zero hits: s = g.n.(F(s̄)) is impossible since g.n.(F(s̄)) ≥ 13ˢ > s. The real construction computes (write H, read off h, wrap); it never searches.

Part XI — Self-Test

Answer before peeking.

  1. Define "Gödel sentence for A." Must a Gödel sentence be true? Give a counterexample.
  2. Define the wrapper E_x[ȳ], derive the closed form of r(x, y), and prove Proposition 2. What does x never undergo in this formula, and why is that the whole trick?
  3. State and prove Lemma 1. Where exactly — and only where — is Proposition 2 consumed in this chapter?
  4. Reproduce the nine-step chain of Theorem 1, citing for each step exactly one definition or theorem.
  5. Prove the equivalence of Φ_lit and Φ_wrap. Which case of the ∀ bears the weight, and how do the other cases pass?
  6. Show that H(h̄) is not a Gödel sentence for A, even though its truth value equals X's. Why can't the equivalence transfer the title?
  7. Prove there is no s with s = g.n.(F(s̄)), and state the moral that dictates the seed-plus-stretch design.
  8. What is Gödel's counterpart to Proposition 2? Name his route (two moves) and the four hazards that make his ladder long. State the three layers and say in which layer all the cost lives.
  9. The two knobs: name them, produce the four-row table, and say which single line each man's matched pair costs him extra.
  10. The three ranks: what is H(v₁), and in what sense is writing it "a substitution that changes nothing"?
  11. Unfold the book's fused line "H[h̄] is true ⟺ h ∈ A*" into its two steps with justifications.
  12. Prove Tarski's theorem from Theorem 1. What does the proof feed the Theorem-1 machine, and why can't that set afford the output?
  13. Give the three statuses, the direction of the inclusion between statuses 1 and 2, the in-house counterexample to the converse, and the selection rule for which sets need status 2.
  14. When does an ∃-definition remain mechanically decidable? State the collapse criterion, give one collapsing example, name the theory where collapse is total, and say why full arithmetic provably never collapses (which theorem, run which way).

Answers

  1. X is a Gödel sentence for A iff (X is true ⟺ g.n.(X) ∈ A). Shape-free — no substitution mentioned. It need not be true: for A = the even numbers, the constructed sentence turns out false with code odd — biconditional satisfied on the false side (Exercise 6, next session).
  2. E_x[ȳ] := ∀v₁(v₁ = ȳ ⊃ E_x). Reading the numbering off the string: prefix "∀v₁(v₁ =" = fixed code k, then 13ʸ (the numeral), 8 (⊃), x, 3 ( ")" ): r(x, y) = k ∗ 13ʸ ∗ 8 ∗ x ∗ 3. Arithmetic by Corollary 1 (5-fold concatenation of Arithmetic pieces). x is never opened — the output code depends on x only as a block, which is what makes the naming formula one line.
  3. Lemma 1: A Arithmetic ⇒ A = {n : d(n) ∈ A} Arithmetic. Proof: d(x) = r(x, x) is Arithmetic (Prop 2), let D express its graph, F express A; H(v₁) = ∃v₂(D(v₁, v₂) ∧ F(v₂)) expresses A. Proposition 2 is consumed here and only here — supplying the D that sits inside H.
  4. See Part V. Justifications: Step 1 Lemma 1 + definition of expresses; Step 4 definition of r; Step 5 the equivalence; Step 6 Step 1 at n = h; Step 7 definition of A*; Step 9 definition of Gödel sentence.
  5. Wrapped true ⟺ every m: (m = n ⊃ F holds of m). For m ≠ n the ⊃-guard passes them vacuously; m = n bears the weight, saying F holds of n — which is F(n̄)'s truth condition exactly.
  6. H(h̄)'s own address is sub(h, h); its truth condition names d(h) — the other sentence's address. The definition compares truth with the sentence's own code, and equivalence preserves what is said (absolute conditions), while addresses differ between the two strings; "my own code ∈ A" re-points with each sentence, so the title doesn't transfer.
  7. F(s̄) contains the numeral s̄ of code 13ˢ, so g.n.(F(s̄)) ≥ 13ˢ > s: no fixed point. Moral: plugging always undershoots the sentence's own address, so the sentence must carry a small seed h plus a stretching instruction (D naming d) with d(h) = its own address.
  8. "sub(x, y) is Arithmetic." Route: (i) sub is mechanical — a ladder of ~31 explicit definitions; (ii) the bridge theorem, mechanical ⇒ Arithmetic. Hazards: occurrence-finding (60 inside 600), freeness (parenthesis scope), replace-all (iteration simulated by coding sequences), leading-zero reassembly. Layers: string operation → code function → naming formula; all cost lives in layer 3.
  9. Knob A: which diagonal is named inside H (fixed at writing). Knob B: which plugging manufactures X (fixes the address). Table in Part VI(e). Smullyan's extra line: Step 5 (equivalence — expressibility only speaks in literal probes). Gödel's extra bill: sub Arithmetic (the ladder), paid inside Lemma 1's counterpart.
  10. H(v₁) is the open formula with its free variable displayed — rank 1, never true or false, carves a set. Substituting v₁ for v₁ returns H itself, so the display-notation and the substitution-notation are one notation, met at the degenerate case.
  11. H[h̄] true ⟺ H(h̄) true (the equivalence) ⟺ h ∈ A* (definition of expresses, instance n = h). The book fuses them because the equivalence was noted once when brackets were introduced.
  12. If T were Arithmetic, so is T̃ (complement closure: ~F). Theorem 1 on T̃ yields X: X true ⟺ g.n.(X) ∈ T̃ ⟺ g.n.(X) ∉ T ⟺ X not true — contradiction. The machine is fed the one set whose Gödel sentence would have to be true-iff-not-true; the set therefore was never Arithmetic.
  13. Status 0 definite (metatheory; free for all sets, including T); status 1 mechanical; status 2 Arithmetic. Status 1 ⇒ status 2 (bridge theorem, later chapter); converse fails — P̃ is Arithmetic but not even listable. Selection rule: a set needs status 2 iff the Gödel sentence's text must mention it (A and d: yes; grammar: no; T: its failure is Tarski).
  14. Decidable iff the search can be cut off: a provable computable bound B(n) with "witness exists ⇒ witness ≤ B(n)." Example: evens, witness ≤ n. Total collapse: Presburger arithmetic (quantifier elimination). Full arithmetic never collapses: mechanical ⇒ Arithmetic plus Tarski (T not Arithmetic) — the theorem run backwards; · is what lets arithmetic code sequences, hence computation histories.

Part XII — What's ahead, state of play, and the method

Position: Chapter II complete through §6: Proposition 2, Lemma 1, Theorem 1, and Theorem 2 (Tarski) proved and — after a long battle — narrated back correctly. The Chapter I ↔ Chapter II correspondence is settled (Part I): Lemma 1 was the only new mathematics; the rest was July 15 wearing base-13 clothing.

Next session: Exercises 6, 7, 8 (book p. 27), deliberately left fresh:

  • Exercise 6 — the alternative base-10 numbering (codes 1, 0, 2, 3, 4, 5, 6, 7, 89, 899, 8999, 89999, 899999): is the Gödel sentence for the set of even numbers true or false? For the odd numbers? Hint: what digit does the constructed sentence always end in, and what does the last digit tell you in base 10 that it wouldn't in base 13?
  • Exercise 7 — a function f such that for every n, f(n) is the Gödel number of a Gödel sentence for A whenever... (build a Gödelizer). Hint: make the code of Hₙ a concatenation with n riding as an unopened block — the wrapper trick, one level up.
  • Exercise 8 — the cross-reference pair: sentences X and Y with X true ⟺ g.n.(Y) ∈ A and Y true ⟺ g.n.(X) ∈ B. Hint: a two-variable wrapper ∀v₁(v₁ = x̄ ⊃ ∀v₂(v₂ = ȳ ⊃ E)) gives an r₂(e, x, y); diagonalize it two ways. Note: the session's diagnosis of H(h̄) as "a sentence about its sibling" is Exercise 8's phenomenon appearing uninvited.

After the exercises: Chapter III — from truth to provability, where "true" is replaced by "provable in a system" and the forward notes of Part VI(d) (the equivalence is provable, not merely true) and Part VIII (the bridge theorem; P̃) come due.

The debt register, updated: (1) Gödel's E-elimination — still the hardest entry. (2) Why prime base 13 — still owed. (3) Property 1 ⇒ property 2 — still owed. (4) Restated with new urgency: mechanical ⇒ Arithmetic (status 1 ⇒ status 2) — this session leaned on it twice (Gödel's route to sub; "truth not mechanical" as Tarski's corollary); the book proves it in the provability chapters.

The method, continued — a lesson about explanations themselves. This session's hardest stretch was not mathematical but expository, and it produced an explicit standard, twice demanded and finally met: no unexplained coinages, no invented metaphor-vocabulary doing load-bearing work, no smuggled baggage. What broke the deadlock each time was the same move: strip the account to a bare numbered chain in which each step cites exactly one definition or theorem already owned (Part V), or run a concrete instance by hand ("6 is even" vs "every number that equals 6 is even"; the +3/+7 example). Terminology invented mid-explanation — however vivid — is a cost, not a gift, unless it is immediately glossed in words already paid for. The complementary reader's-side lesson: three of the session's errors (the two-diagonalizations chain, the definition-with-substitution, the literal-manufacture claim) were each a plausible narrative that collapsed the distinction between what a formula says (fixed by its text) and what is done with it (chosen later) — when a story feels right but won't survive being written as a numbered chain with justifications, the chain is the arbiter.


End of session review · Smullyan, "Gödel's Incompleteness Theorems," Chapter II §6 complete — Tarski's Theorem · Previous files: Godel-Incompleteness-Session-2026-07-15.md (Chapter 1 framework & machine puzzle), Godel-Incompleteness-Session-2026-07-17-Answer-Sheet.md (Chapter 1 exercises 1–7), Godel-Incompleteness-Session-2026-07-19.md (Chapter II §1–§2, language and truth), Godel-Incompleteness-Session-2026-07-20.md (Chapter II §3, Arithmetic sets/relations/functions, Exercises 2–5), Godel-Incompleteness-Session-2026-07-21.md (Chapter II §4–§5, concatenation and Gödel numbering) · Next: Exercises 6–8, then Chapter III.