Gui Ruiyan

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

Study journals ·

Gödel's Incompleteness Theorem — A Complete Session Review

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 15, 2026 · From Smullyan's machine puzzle to the abstract framework of "Gödel's Incompleteness Theorems," Chapter 1


How to use this document

This follows the order in which understanding was actually built during the session — each part presupposes the ones before it. For review: read Parts I–IX in order the first time; afterwards, the Distinctions Ledger (Part X) alone is a full refresher, and the Self-Test (Part XII) tells you whether the refresher took. When Smullyan's notation fogs up in later chapters, come back to the Translation Table at the very end.


Part I — The Machine Puzzle: the skeleton of the whole proof

The setup

A machine prints strings over five symbols: P N ~ ( ). Any finite string is an expression. Exactly four shapes count as sentences, with fixed meanings:

Sentence True exactly when…
P(X) X is printable
PN(X) the norm of X is printable
~P(X) X is not printable
~PN(X) the norm of X is not printable

The norm of X is the string X(X) — X followed by itself in parentheses.

One assumption only: the machine never prints a false sentence (it is honest / sound). Nothing guarantees it prints all true ones — and the theorem is that nothing could.

The strategy: weaponize honesty

We know nothing about the machine's program, so the only way to prove "the machine can't print this" is to show that printing it would force the machine to lie. Hence the hunt: build a sentence G that is true if and only if it is not printable. For such a G, a two-case argument settles everything at once:

  1. If the machine prints G: everything printed is true, so G is true; but G's truth means G is unprintable — contradiction. This case is impossible.
  2. If the machine never prints G: then G is in fact unprintable — which is exactly what G asserts. So G is true.

Case 1 being impossible, Case 2 holds: G is true and never printed. We never inspect the machine; the sentence is designed so that the machine's own honesty traps it.

Why direct self-reference is impossible

A sentence refers to a string only by physically containing it between its parentheses — this language has no pronouns, no "this sentence." But no finite string can contain a full copy of itself:

If S = ~P( + S + ), then length(S) = length(S) + 4, i.e. 0 = 4. Impossible.

Like a poster required to contain a full-size copy of itself. Direct self-reference is dead.

The loophole: refer by recipe, not by copy

The norm-sentences do something sneaky: ~PN(X) contains only X, but talks about the longer string X(X). The N acts as a build instruction: "double the material X, then talk about the result." A sentence can carry a blueprint plus instructions whose output is bigger than anything it contains — blueprints can be smaller than what they describe; copies can't.

The solution

Choose X = ~PN (three symbols). Its norm is ~PN(~PN) — which is exactly the sentence-form ~PN(X) with X = ~PN. So:

G = ~PN(~PN) says "the norm of ~PN is not printable" — and that norm is G itself. G says: "I am not printable."

Nine symbols, containing only a three-symbol blueprint. No length paradox. By the two-case argument: G is true, and the machine can never print it. No honest machine prints all truths.


Part II — Why this is NOT a paradox (and why that is the theorem)

The Liar sentence — "this sentence is false" — is a genuine paradox: true implies false, false implies true, no consistent resolution exists.

G — "this sentence is not printable" — is the Liar with the fuse removed. Test it: G true → G is true and unprintable: odd but consistent. G false → G is printable → the machine printed a falsehood → violates honesty → this branch dies. One consistent branch survives, and it is forced: true and unprintable.

Why does G escape? Because "true" and "printable" are different properties that can come apart — nothing forbids a sentence being true yet never printed. That gap is the escape valve; the self-referential pressure discharges into it, forcing one sentence to fall in.

The theorem from this angle: if some machine printed exactly the true sentences, "printable" and "true" would be the same property — and G would become the Liar, a genuine paradox inside a consistent setup. Impossible. Hence for every honest machine, truth and printability must come apart somewhere; G is the explicit witness of where.

Gödel's trick = the Liar paradox with "false" weakened to "uncertifiable," converting an explosion into a theorem about limits. (Keep "false" instead, and the same engine yields Tarski's theorem: no language can define its own truth.)


Part III — The companion sentence and the full incompleteness picture

Exercise worked during the session: what about PN(~PN) — the sentence claiming "G is printable"?

  • It is not self-referential (it talks about G, a different string). Non-self-referential sentences are the easy case: just check whether what they claim is so.
  • It claims G is printable. G is not. So PN(~PN) is false — and therefore unprintable for the boring reason: the machine doesn't lie.
Sentence Claims Actually Printable?
PN(~PN) G is printable false no — machine won't lie
~PN(~PN) = G G is not printable true no — printing it would falsify it

The machine can never settle "is G printable?" in either direction — silence both ways — though the answer exists and we see it from outside. This is the classic form of incompleteness: neither provable nor refutable.

Direction hygiene (a recurring trap): - Valid: printable ⟹ true (equivalently: false ⟹ unprintable). - Never valid: true ⟹ printable. G is the proof this direction genuinely fails.


Part IV — Smullyan's abstract framework: the puzzle with serial numbers filed off

Chapter 1's seven items are the puzzle generalized:

Item Abstract name In the puzzle
1 Expressions £ (denumerable) all strings of the five symbols
2 Sentences S the four grammatical shapes
3 Provable sentences P the printable ones
4 Refutable sentences R (new) sentences the system officially rejects — lets "neither provable nor refutable" be stated without assuming a negation symbol
5 Predicates H P, PN, ~P, ~PN — sentences with a blank
6 Function Φ: (E, n) → E(n) the plugging-in operation: "wrap the argument in parentheses"
7 True sentences T the meaning table (a baby Tarski-style truth definition, given from outside)

Three structural facts

1. A predicate is a string with a grammatically certified blank. Item 6's condition ("H(n) is always a sentence") is not a miracle of concatenation — it is a calibration between items 5 and 6: predicates are precisely the expressions whose shape makes the filled-in result grammatical. Stipulated in the toy; in real arithmetic it's a lemma (substituting a numeral for a free variable preserves well-formedness, proved by induction on formula structure).

2. Truth and provability are separate items because the theorem lives in their gap. Two verdict systems, never to be merged:

Verdicts Exhaustive? Who decides
Semantic layer true / false yes reality (truth definition, item 7, outside)
System layer provable / refutable / neither no the system's rulebook (items 3–4, inside)

Truth is a coin that always lands. Provability is a coin that can land heads, tails, or on its edge — and exhibiting an edge-case is the theorem.

3. Inside vs. outside is the master distinction. Inside £: expressions, sentences, predicates. Outside (our tools, in the metatheory): Φ, the coding, the truth definition, all our reasoning about the system. Gödel's labor is dragging outside-things inside; Tarski's theorem says one thing — truth — provably cannot be dragged in.

Predicates as names of sets

The bracketed remarks in items 5–6 are the payload: a predicate H names the set {n : H(n) is true}. Items 5–6 install not just a sentence factory but the language's naming apparatus — its expressive power. The load-bearing question of the whole proof is a naming question: is one particular set nameable?

Why there's no "S" symbol on par with P and N

Two grades of "the system deals with property Q": 1. Externally recognizable — a mechanical check can detect Q (sentencehood: check the shape). 2. Internally nameable — the language contains a predicate expressing Q, so sentences can talk about Q (printability: the symbol P).

A property needs grade 2 only if the Gödel sentence must talk about it. G says "my diagonalization is not printable" — it mentions printability and diagonalization, so those need internal names (P, N). It never talks about sentencehood, so grammar needs only grade 1. Not an oversight — a precise reflection of what the diagonal sentence needs to mention.


Part V — Arithmetization: how numbers carry syntax without category-mixing

Real arithmetic talks only about numbers, never strings. Gödel's bridge has three steps, none of which mixes categories.

Step 1 — Objects: a dictionary, not an identity

Assign every expression a code number (Gödel numbering). Session scheme: symbols become digits — P=1, N=2, ~=3, (=4, )=5 — so ~PN ↦ 312, ~PN(~PN) ↦ 31243125. (Gödel's own scheme was prime-powers: 2^c¹·3^c²·5^c³…, literally Leibnizian.)

The coding is pure convention — like Unicode; any injective, mechanically decodable scheme works, and no choice is "truer" than another. Numbers stay numbers; strings stay strings; the dictionary is a third thing, owned by us. Your computer stores this very text as numbers — Gödel invented that move in 1931.

Step 2 — Operations: mirrors with receipts

Every mechanical string-operation casts an arithmetic shadow on codes. The norm, derived from "appending digit d to m gives 10m + d":

norm(x) = x·10^(k+2) + 4·10^(k+1) + 10x + 5 (k = digit-count of x)

Verified by hand (P→1415, PN→124125, ~P→314315, ~PN→31243125) and by machine over all 780 strings of length ≤ 4: zero mismatches. Provable for all cases by an easy induction.

More generally, substitution of argument X (code x) into E (code e):

sub(e, x) = e·10^(k+2) + 4·10^(k+1) + 10x + 5 — and the norm is its diagonal: norm(x) = sub(x, x).

Legitimacy is never decided, always demonstrated. Each mirror comes with a provable identity — code(op(X)) = f(code(X)) — a receipt, not a judgment. This is where Gödel differs from Leibniz: Leibniz's characteristica universalis tried to encode concepts (requiring metaphysics that never materialized); Gödel retreats to encoding only marks and mechanical rules — exact combinatorial objects. The retreat wins the war.

Step 3 — Universality is the cash value

The norm formula is one law for all inputs (k is computed from x — the unique k with 10^(k−1) ≤ x < 10^k — not a constant tuned per case). This matters absolutely: a predicate is one finite string that must make sense for every plugged-in number, including numbers unknown when it was written (fatally, its own address). A per-case lookup table cannot be packed into a finite formula; only uniform laws can be written inside the language as predicates. "Arithmetic can express the norm" means this universality.

(Fine print: official arithmetic lacks exponentiation as a primitive; Gödel's β-function simulates it from + and × — laborious but uniform, which is all that counts.)

The boundary: mechanical in, truth out

What survives arithmetization? Exactly the mechanical notions — checkable by rote with no judgment: is-a-sentence, is-a-proof-of, diagonalization. Formal systems were designed (by Hilbert) so proof-checking is judgment-free — which is precisely what makes provability arithmetizable. Truth is not mechanical, and Tarski's theorem proves no arithmetic formula defines the set of true sentences' codes. Provability lands inside the boundary; truth lands outside; the incompleteness theorem is the measurement of that gap. Turing later named the boundary: the computable — and the modern computer is the engineering payoff of this exact insight.

The dual reading

The Gödel sentence, read literally, is a monstrous statement purely about numbers — a Martian without the dictionary reads legitimate (if bizarre) number theory. The reading "this asserts its own unprovability" is ours, through the registry — and the two readings are provably equivalent, because the coding was engineered so. Meaning was never intrinsic to symbols; the same bits can be a prime number and a photo of a cat.


Part VI — Diagonalization as geometry: the infinite table

Draw the table: rows = expressions E, columns = arguments X, cell (E, X) = the plugged-in result E(X).

col P col PN col ~P col ~PN
row P P(P) P(PN) P(~P) P(~PN)
row PN PN(P) PN(PN) PN(~P) PN(~PN)
row ~P ~P(P) ~P(PN) ~P(~P) ~P(~PN)
row ~PN ~PN(P) ~PN(PN) ~PN(~P) ~PN(~PN)

The diagonal (row label = column label) collects exactly the norms: X(X). "The norm of X" = "the diagonal cell of X's row."

The mechanism: row ~PN is a commentary row — each of its cells claims "the diagonal cell of this column's row is not printable." But a commentary row is still a row, and every row crosses the diagonal exactly once, at the column bearing its own label. At that crossing, the cell comments on the diagonal cell of its own row — itself. Self-reference is never written; it is forced by the geometry of the table. Someone wrote an innocent general commentary; the crossing point did the rest.

The lineage: this is Cantor's diagonal argument (1891) repurposed — walk the diagonal, flip it (~ … P … N = "not-printable-the-norm-of" is precisely a flipped diagonal row). Cantor's crossing point produced a missing row (uncountability); Gödel's produces a self-commenting cell (unprovability). One geometric idea, two landmark theorems.

In the arithmetic version: columns are indexed by numbers (addresses via the registry), the cell (e, x) holds sub(e, x), the diagonal holds sub(x, x), and the Gödel sentence is H(h) — the commentary predicate H evaluated at its own address h.


Part VII — Number, numeral, address: what n really is

Three things, never to be merged:

  • The number n — abstract, lives outside the language in our ordinary mathematics. In general it stands for nothing but itself: H(12) with H = "is even" says twelve is even; no coding anywhere. The framework's items 1–7 mention no coding at all.
  • The numeral n̄ — the ink: the string inside the language that names n. What Φ physically writes into the blank.
  • The address reading — optional and external: if a Gödel numbering is installed and n happens to be a code, our registry lists an expression at address n, and we may additionally read H(n) as being about that expression. The number never changes; only our bookkeeping is enriched. ("Is 12 a number or an employee?" is malformed — 12 is a number; the company registry associates an employee with it.)

The diagonal moment: the proof plugs in exactly one interesting number — h, the address of H itself. In H(h), the single number h wears both hats at once: as argument (a mere number handed to a predicate) and as address (where H lives in the registry). That coincidence of argument and address is "an expression eats its own address," unpacked.

Why route through numbers at all? Because arithmetic's sentences can only be about numbers — coding is the toll arithmetic pays for its poverty of subject matter. The puzzle's language was stipulated rich (arguments were expressions directly), so it paid no toll.


Part VIII — Two senses of "prove"; who dictates the rulebook

Sense A — receipts (metatheory). "The dictionary's faithfulness is proven" means proven in our ordinary mathematics — the same authority behind "there are infinitely many primes." The incompleteness theorem itself is proved in Sense A.

Sense B — the set P (the specimen's rulebook). Provable-in-£ = derivable from the listed axioms by the listed rules. Nobody dictates the rulebook: each formal system (Peano's PA, ZFC, yours tomorrow) is an offer — and the theorem quantifies over all offers: every honest, mechanical rulebook whatsoever gets handed its own true-but-unprovable sentence by the same diagonal recipe. The rulebook's arbitrariness is not a loophole; it is the quantifier. (A "rulebook" whose axioms are "all true sentences" would evade the theorem — but it isn't mechanical, and Tarski proves no formula can express it.)

The sting: Sense A can itself be formalized into a rulebook — which the theorem then applies to, producing a truth our own formalized mathematics can't prove. No final vantage point escapes; the hierarchy of metatheories never closes. That's content, not defect.


Part IX — The two-level pattern (the session's master key)

Almost every confusion resolved into the same shape: abstract level = stipulated requirement; concrete level = provable lemma.

Claim Abstractly (framework) Concretely (given language)
H(n) is always a sentence admissibility axiom selecting substitution-like Φ's grammar lemma (induction on formulas)
Coding is faithful (not needed — no coding in the abstract items) receipt per operation, proved
Provability is nameable hypothesis of the abstract theorem earned via arithmetization (the hard 90%)

Correspondingly, Gödel's theorem has two components of very unequal difficulty:

  • Component A (easy, = the puzzle): any language with the capacities — nameable provability, diagonalization, negation — contains a true unprovable sentence. The five-symbol machine is Component A made visible: P, N, ~ are the minimal kit, stipulated as primitives. The puzzle is an instance of the framework, but the minimal instance — the framework wearing its skeleton on the outside.
  • Component B (hard, = Gödel's actual labor): proving that real arithmetic — never designed with P or N symbols — nonetheless has these capacities: a genuine arithmetic formula naming provability, a genuine arithmetic function mirroring diagonalization. Gödel numbering, sub, the β-function, the forty-six definitions. Most of Gödel's paper, and the next chapters of Smullyan, are Component B.

And is the item-6 condition vacuous? No — the notation "E(n)" smuggles in the parenthesis picture, but abstractly Φ is an arbitrary function on (expression, number) pairs, and almost all such functions breach the condition (first-symbol-of-E; E-reversed; naive tail-concatenation in arithmetic, which yields ill-formed strings). The axiom selects the substitution-like ones — the way associativity selects group operations. It feels needless only if you've met just one Φ, as group axioms feel needless if the only operation you've met is integer addition.

Does H have to be arithmetic? Abstractly no (the puzzle's ~PN isn't). For the real theorem yes — because the diagonal argument requires the language to be rich enough to name its own provability, and arithmetic is the classic minimal language rich enough (anything containing it — set theory, any foundation — inherits the incompleteness; genuinely weaker languages can escape and some are provably complete).


Part X — The Distinctions Ledger (every fog of the session, one line each)

Confusion raised Resolution
Why would direct self-reference need an infinite string? A sentence refers only to what its parentheses literally contain; no string contains itself (length(S) = length(S) + 4). Refer by recipe, not copy.
"So it's a self-reference paradox" Near-paradox, deliberately defused: "false" weakened to "unprintable." The Liar explodes; G is forced into the truth-vs-certification gap. The defusing is the theorem.
"If PN(~PN) is true it should be printable" It's simply false (claims G printable; G isn't), hence unprintable for the boring reason. Only printable ⟹ true is valid; true ⟹ printable is the direction the theorem kills.
How can numbers obey both arithmetic and linguistic laws? They don't; they obey arithmetic only. Linguistic laws are simulated inside arithmetic via the dictionary — one proven receipt per operation. Translation, not mixing.
What decides which operations are "legit"/"true"? Nothing is decided; correspondences are proved (receipts), definability is fixed by the language's inventory, and coding never confers truth. Deep boundary: mechanical arithmetizes; truth doesn't.
Isn't the norm formula particular to 312? Universal: k is computed from x; the formula derives from digit-appending arithmetic; machine-checked over 780 cases, provable for all. Universality = law-not-lookup-table = expressibility as one predicate.
Is Φ the dictionary? No — two separate outside tools. Φ: strings → strings (plugging in). Dictionary g: strings ↔ numbers (labeling). Substitution never touches codes.
"Derivable," "replaced by," "provable-or-refutable" Word hygiene: substitution ≠ derivation (derivation = proof); coding ≠ replacement (mirroring); provable/refutable is NOT exhaustive — "neither" exists, and that's the theorem.
How does dumb concatenation guarantee H(n) is a sentence? It doesn't and needn't: the condition is scoped to predicates, which are by calibration exactly the expressions whose blanks the grammar certifies.
What does n stand for? Itself — a number, period. The registry optionally lists an expression at that address. At the diagonal moment, one number h is both argument and address at once.
Is the puzzle the framework itself? It's the minimal instance — the framework with everything inessential deleted, key capacities given as primitive symbols. It exhibits Component A; Gödel's labor is Component B: proving arithmetic secretly contains the kit.
Is the item-6 condition vacuous? No: abstractly Φ is arbitrary and almost all Φ's breach it; the condition is an admissibility axiom (like group axioms). Concretely it becomes a provable lemma — hence feels automatic.
Must H be arithmetic? Is n an address? Two faces of one design fact: arithmetic can only talk about numbers, so H must be an arithmetic formula and expressions are reachable only via coded addresses — the toll the stipulated-rich puzzle never paid.

Part XI — The theorem, final form

For any formal system whose language includes arithmetic, whose rulebook is mechanical, and which proves only true sentences: there exists a sentence — constructible explicitly by the diagonal recipe — that is true, but neither provable nor refutable in that system.

Its sibling, same engine with "false" kept instead of weakened (Tarski): no such language can define its own truth.

What it does NOT say (inoculation against popular abuse): not that truth is relative, not that mathematics is broken, not that nothing can be known. The Gödel sentence is known to be true — by us, from outside. The limit is on what any single mechanical rulebook can certify from inside; and the system's honesty is precisely what creates its blind spot. Upgrading the system to print G makes it a liar; every honest system has its own G, including the upgraded one.

One-line compression across all registers: Using ordinary mathematics (Sense A), we show that for any honest mechanical rulebook (Sense B), the plugging operation (Φ) composed with the dictionary (g) manufactures a sentence that is true but outside the rulebook's reach.


Part XII — Self-Test

Answer before peeking; each was worked in the session.

  1. Why can't the machine print ~PN(~PN), and why is it true?
  2. Is PN(~PN) self-referential? True? Printable?
  3. Compute the norm of P under the digit-coding, both by string-building and by the formula.
  4. State the difference between Φ and the Gödel numbering g in one sentence each.
  5. Why must the norm's arithmetic mirror be one universal formula rather than per-case recipes?
  6. Give an example of a Φ that violates item 6's condition.
  7. What property must the rulebook have for provability to be arithmetizable, and what famous notion fails that property?
  8. In H(h), what two roles does the number h play?

Answers

  1. Printing it would make it false (it claims its own unprintability), violating honesty — so it's never printed; and being never printed is exactly what it claims, so it's true.
  2. No (it talks about G, a different string); false (it claims G printable, G isn't); unprintable — because false, the boring reason.
  3. String: P(P) → digits 1 4 1 5 → 1415. Formula: x=1, k=1: 1·10³ + 4·10² + 10·1 + 5 = 1415. ✓
  4. Φ plugs a number's numeral into an expression's blank — strings to strings, never touches codes. g labels each expression with a code number — the bridge between the string world and the number world.
  5. A predicate is one finite string that must make sense for every plugged-in value, including values unknown when it was written (its own address); only a uniform law fits in a finite formula — lookup tables don't.
  6. Φ′(E, n) = the first symbol of E (never a sentence); or E reversed; or naive concatenation of a numeral onto a formula's tail (ill-formed).
  7. Mechanicality — proof-checking must be a rote, judgment-free procedure. Truth fails it (and Tarski proves no formula expresses it).
  8. Argument (a mere number the predicate is evaluated at, like 12 for "is even") and address (the registry location where H itself lives). Their coincidence is the diagonal crossing.

Part XIII — What's ahead in Smullyan, and the method

Coming chapters (the flesh on the skeleton you own): constructing a concrete language of arithmetic; expressibility and representability made precise; the real Gödel numbering and substitution function (meet the β-function — exponentiation from + and ×); then the refinements — Rosser's trick (replacing the truth/soundness assumption with mere consistency) and Gödel's second theorem (no consistent system of this kind proves its own consistency).

The translation table — when notation fogs, translate back to the matchbox machine:

Formal term Machine puzzle
formal system / provable the machine / printable
sound the machine never lies
predicate ~PN
diagonalization of E the norm X(X)
Gödel numbering symbols-to-digits dictionary
the Gödel sentence ~PN(~PN)
true but unprovable true but unprintable
undecidable (neither provable nor refutable) machine silent on both PN(~PN) and ~PN(~PN)

The method that got you here (worth keeping deliberately): every step forward came from refusing to let a sentence pass — why infinite? isn't that formula particular to 312? who dictates the rulebook? isn't this condition vacuous? Demand the receipt at every step; distrust every notation that seems to work for free. Sort each claim into one of three bins — stipulated (the puzzle's P), provable (the norm formula), or impossible (naming truth) — and no fog survives.


End of session review · Smullyan, "Gödel's Incompleteness Theorems," Chapter 1 complete.