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 / 篇目
- How to use this document
- Part I — The Machine Puzzle: the skeleton of the whole proof
- Part II — Why this is NOT a paradox (and why that is the theorem)
- Part III — The companion sentence and the full incompleteness picture
- Part IV — Smullyan's abstract framework: the puzzle with serial numbers filed off
- Part V — Arithmetization: how numbers carry syntax without category-mixing
- Part VI — Diagonalization as geometry: the infinite table
- Part VII — Number, numeral, address: what n really is
- Part VIII — Two senses of "prove"; who dictates the rulebook
- Part IX — The two-level pattern (the session's master key)
- Part X — The Distinctions Ledger (every fog of the session, one line each)
- Part XI — The theorem, final form
- Part XII — Self-Test
- Part XIII — What's ahead in Smullyan, and the method
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:
- 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.
- 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~PNis 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
PorNsymbols — 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.
- Why can't the machine print
~PN(~PN), and why is it true? - Is
PN(~PN)self-referential? True? Printable? - Compute the norm of
Punder the digit-coding, both by string-building and by the formula. - State the difference between Φ and the Gödel numbering g in one sentence each.
- Why must the norm's arithmetic mirror be one universal formula rather than per-case recipes?
- Give an example of a Φ that violates item 6's condition.
- What property must the rulebook have for provability to be arithmetizable, and what famous notion fails that property?
- In H(h), what two roles does the number h play?
Answers
- 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.
- No (it talks about G, a different string); false (it claims G printable, G isn't); unprintable — because false, the boring reason.
- String:
P(P)→ digits 1 4 1 5 → 1415. Formula: x=1, k=1: 1·10³ + 4·10² + 10·1 + 5 = 1415. ✓ - Φ 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.
- 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.
- Φ′(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).
- Mechanicality — proof-checking must be a rote, judgment-free procedure. Truth fails it (and Tarski proves no formula expresses it).
- 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.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月15日学习记录 · 从Smullyan的机器谜题,到《哥德尔不完备定理》第一章的抽象框架
如何使用本文
本文按照本次学习中理解实际形成的顺序展开,每一部分都预设前面的部分。复习时,第一次按顺序阅读第一至第九部分;之后,只看区别清单,第十部分就能完整回顾,而自测,第十二部分可以检验复习是否有效。后续章节中,如果Smullyan的记号又变得模糊,就回到文末的对照表。
第一部分——机器谜题:整个证明的骨架
设定
一台机器打印由五个符号P N ~ ( )组成的符号串。任何有限串都是一个表达式。只有恰好四种形式算作语句,其含义固定:
| 语句 | 为真当且仅当…… |
|---|---|
P(X) |
X可打印 |
PN(X) |
X的范式可打印 |
~P(X) |
X不可打印 |
~PN(X) |
X的范式不可打印 |
X的范式(norm)是符号串X(X),即X后面跟着括号内的自身。
只有一个假设: 机器从不打印假句,即它是诚实的或可靠的。没有任何保证说它会打印所有真句,而定理正是:没有什么能够保证这一点。
策略:利用诚实
我们对机器的程序一无所知,因此要证明“机器不能打印这个”,唯一办法就是证明,打印它会迫使机器说谎。于是目标明确:构造一个语句G,使它为真当且仅当它不可打印。对于这样的G,分两种情况就能一次解决全部问题:
- 如果机器打印G: 打印出来的都为真,所以G为真;但G的真意味着G不可打印,矛盾。这种情况不可能。
- 如果机器从不打印G: 那么G事实上不可打印,而这恰好就是G断言的内容。所以G为真。
第一种情况不可能,因此第二种成立:G为真,却从未被打印。 我们从不检查机器;语句的设计使机器自身的诚实困住了它。
为什么直接自指不可能
一个语句只能通过在括号内实际包含某个符号串来指涉它;这种语言没有代词,也没有“这个语句”。但任何有限串都不可能包含自身的完整副本:
如果S =
~P(+ S +),那么length(S) = length(S) + 4,即0 = 4。不可能。
就像要求一张海报包含自身原尺寸的完整副本。直接自指走不通。
突破口:通过操作方法而非副本来指涉
范式语句玩了一个技巧:~PN(X)只包含X,却谈论更长的符号串X(X)。N充当构造指令:“把材料X加倍,再谈论结果。”语句可以携带一份蓝图加指令,其输出比它所包含的任何东西都大。蓝图可以小于它描述的东西,副本却不行。
解法
选择X = ~PN,三个符号。其范式是~PN(~PN),恰好就是把X = ~PN代入语句形式~PN(X)的结果。所以:
G =
~PN(~PN)说的是“~PN的范式不可打印”,而那个范式就是G自身。G说:“我不可打印。”
九个符号,只包含一个三个符号的蓝图。没有长度悖论。由两种情况的论证,G为真,而机器永远不能打印它。 没有诚实机器能打印所有真理。
第二部分——为什么这不是悖论,以及为什么这正是定理
说谎者语句“这个语句是假的”是真正的悖论:真蕴含假,假蕴含真,没有一致的解决方式。
G“这个语句不可打印”则是拆掉引信的说谎者。检验一下:G为真 → G真且不可打印,奇怪但一致。G为假 → G可打印 → 机器打印了假句 → 违反诚实性,这一支被排除。剩下一个一致分支,而且是被迫的:真且不可打印。
G为什么能够逃脱?因为“真”与“可打印”是不同的性质,可以分离。没有什么禁止一个语句为真却永远不被打印。这道间隙就是泄压阀;自指压力在这里释放,迫使一个语句落入其中。
从这个角度看定理: 如果某台机器打印的恰好是真句,那么“可打印”与“真”就是同一性质,G就会变成说谎者,在一致设定内部产生真正悖论。不可能。因此,对每台诚实机器,真理与可打印性都必须在某处分离;G明确见证了这一位置。
哥德尔的技巧,就是把说谎者悖论中的“假”弱化为“不可认证”,把爆炸转化为关于限度的定理。如果保留“假”,同一机制就得到塔斯基定理:没有语言能定义自身的真理。
第三部分——伴随语句与不完备性的完整图景
本次学习做过的练习:PN(~PN)如何,即声称“G可打印”的语句?
- 它不自指,因为它谈论的是另一个符号串G。不自指的语句是容易的情形:检查其断言是否属实即可。
- 它断言G可打印,而G不可打印。因此
PN(~PN)为假,进而不可打印;原因很普通:机器不说谎。
| 语句 | 断言 | 实际情况 | 可打印吗? |
|---|---|---|---|
PN(~PN) |
G可打印 | 假 | 不可,机器不会说谎 |
~PN(~PN) = G |
G不可打印 | 真 | 不可,打印它会使它为假 |
机器永远不能从任何一个方向解决“G可打印吗”:两个方向都沉默,尽管答案存在,我们从外部能看见它。这就是不完备性的经典形式:既不可证,又不可反驳。
注意方向,这是反复出现的误区: - 有效:可打印 ⟹ 真,等价于假 ⟹ 不可打印。 - 绝不有效:真 ⟹ 可打印。G证明了这个方向确实失败。
第四部分——Smullyan的抽象框架:抹去具体标记后的谜题
第一章的七个项目,是谜题的一般化:
| 项目 | 抽象名称 | 在谜题中 |
|---|---|---|
| 1 | 表达式£,可数无限 | 五个符号组成的所有符号串 |
| 2 | 语句S | 四种语法形式 |
| 3 | 可证句P | 可打印者 |
| 4 | 可反驳句R | 新增:系统正式否决的语句;使“既不可证又不可反驳”无须预设否定符号就能被表述 |
| 5 | 谓词H | P、PN、~P、~PN,即带空位的语句 |
| 6 | 函数Φ: (E, n) → E(n) | 代入操作:“把自变量放进括号” |
| 7 | 真句T | 含义表:从外部给予的简易塔斯基式真理定义 |
三个结构事实
1. 谓词是带有经语法认可之空位的符号串。 第6项的条件“H(n)总是语句”不是连接符号的奇迹,而是第5、6项之间的校准:谓词恰好是那些因自身形式而使填入结果符合语法的表达式。在玩具系统中,这是规定;在真实算术中,它是引理,即以数码替换自由变量保持合式性,通过对公式结构的归纳证明。
2. 真理与可证性之所以分列,是因为定理就存在于二者的间隙。 两套裁定系统,绝不能合并:
| 裁定 | 穷尽吗? | 谁来决定 | |
|---|---|---|---|
| 语义层 | 真/假 | 是 | 现实,第7项的真理定义,外部 |
| 系统层 | 可证/可反驳/两者都不 | 否 | 系统规则,第3–4项,内部 |
真理像一枚总会落定的硬币。可证性像一枚可以正面朝上、反面朝上,也可以立在边缘上的硬币;展示一个立边情形,就是定理。
3. 内部与外部是核心区别。 £内部有表达式、语句、谓词。外部,即我们在元理论中的工具,有Φ、编码、真理定义,以及我们关于系统的全部推理。哥德尔的工作,是把外部事物拖入内部;塔斯基定理则说,有一样东西,真理,可以证明无法被拖进去。
谓词作为集合的名称
第5–6项的括注才是关键内容:谓词H命名集合。这两项设置的不只是语句工厂,还有语言的命名装置,即其表达能力。整个证明的承重问题,是一个命名问题:某个特定集合能否被命名?
为什么没有与P和N并列的“S”符号
“系统处理性质Q”有两个层次:
1. 外部可识别:机械检查可以检测Q,例如检查形式来判断是否为语句。
2. 内部可命名:语言包含表达Q的谓词,使语句能够谈论Q,例如可打印性有符号P。
只有当哥德尔句必须谈论某个性质时,该性质才需要第二层。G说“我的对角化不可打印”,提到了可打印性与对角化,所以它们需要内部名称P、N。它从不谈论语句性本身,所以语法只需第一层。这不是遗漏,而是精确反映了对角句需要提到什么。
第五部分——算术化:数如何承载句法而不混淆范畴
真正的算术只谈数,不谈符号串。哥德尔的桥梁有三步,没有一步混淆范畴。
第一步——对象:词典,而非同一
给每个表达式分配编码数,即哥德尔编号。本次使用的方案,把符号变成数字:P=1、N=2、~=3、(=4、)=5,所以~PN ↦ 312,~PN(~PN) ↦ 31243125。哥德尔自己的方案是素数幂:2^c¹·3^c²·5^c³…,简直就是莱布尼茨式的。
编码是纯粹约定,像Unicode一样;任何单射、可机械解码的方案都行,没有哪种选择比另一种“更真”。数仍是数,串仍是串,词典是第三样东西,由我们掌握。你的电脑正把这段文字存成数,哥德尔在1931年发明了这一步。
第二步——操作:附有凭据的镜像
每种机械的符号串操作,都在编码上投下算术影子。由“在m后附加数字d,得到10m + d”可推出范式函数:
norm(x) = x·10^(k+2) + 4·10^(k+1) + 10x + 5,其中k为x的位数。
已经手算验证P→1415、PN→124125、~P→314315、~PN→31243125,并对全部780个长度≤4的符号串进行机器验证,零不匹配。通过简单归纳可证明所有情形。
更一般地,把编码为x的自变量X代入编码为e的E:
sub(e, x) = e·10^(k+2) + 4·10^(k+1) + 10x + 5,而范式就是其对角线:norm(x) = sub(x, x)。
合法性从不靠裁定,而总要展示出来。 每个镜像都附有可证明的恒等式code(op(X)) = f(code(X)),这是凭据,不是判断。这正是哥德尔与莱布尼茨的不同:莱布尼茨的普遍文字试图编码概念,需要一套从未实现的形而上学;哥德尔退而只编码符号痕迹与机械规则,即精确的组合对象。这次退却赢得了战争。
第三步——普遍性才是真正收益
范式公式是适用于所有输入的一条法则。k由x计算,是满足10^(k−1) ≤ x < 10^k的唯一k,不是逐例调整的常数。这至关重要:谓词是一个有限串,却必须对每个代入的数都有意义,包括写出它时未知的数,而其中致命的一个就是它自己的地址。逐例查询表无法装进有限公式;只有统一法则才能作为谓词写进语言内部。 “算术可以表达范式”说的就是这种普遍性。
补充细节:正式算术没有把幂运算作为基本运算;哥德尔的β函数通过+与×模拟它,虽然繁琐,却是统一的,而这就够了。
边界:机械性进入,真理留在外部
什么能够经受算术化?恰好是那些机械性概念,可以不作判断而按固定步骤检查:是否为语句、是否为某句的证明、对角化。希尔伯特设计形式系统,就是为了让证明检查无须判断,而这恰好使可证性能够算术化。真理不是机械性的,塔斯基定理证明,没有算术公式能定义真句编码的集合。 可证性落在边界之内,真理落在之外;不完备定理衡量的就是这道间隙。图灵后来给这条边界命名:可计算性。现代计算机,就是这一洞见的工程成果。
双重读法
哥德尔句按字面读,是一条纯粹关乎数的庞大陈述;一个没有词典的火星人,读到的是合法但古怪的数论。“它断言自身不可证”这一读法,则是我们通过登记表得到的;两种读法可证明地等价,因为编码就是为此设计的。意义从来不内在于符号;同一串比特既可以是一个素数,也可以是一张猫的照片。
第六部分——作为几何的对角化:无限表格
画出表格:行是表达式E,列是自变量X,单元格(E, X)是代入结果E(X)。
列P |
列PN |
列~P |
列~PN |
|
|---|---|---|---|---|
行P |
P(P) | P(PN) | P(~P) | P(~PN) |
行PN |
PN(P) | PN(PN) | PN(~P) | PN(~PN) |
行~P |
~P(P) | ~P(PN) | ~P(~P) | ~P(~PN) |
行~PN |
~PN(P) | ~PN(PN) | ~PN(~P) | ~PN(~PN) |
对角线上,行标签等于列标签,收集的恰好就是范式X(X)。“X的范式”就是“X所在行的对角单元格”。
机制: ~PN这一行是评论行,每个格子都断言“与本列同名的那一行,其对角格不可打印”。但评论行仍是一行,而每行恰好与对角线相交一次,就在与自身同名的那一列。交点处的格子评论的,是自己所在行的对角格,即自身。自指从未被直接写出,而是由表格的几何结构强迫产生。有人写了一条无害的一般评论,交点完成了其余工作。
谱系: 这是康托尔1891年对角论证的新用途:沿对角线走,再将它翻转。~ … P … N,即“……的范式不可打印”,恰好就是翻转后的对角行。康托尔的交点产生缺失的一行,即不可数性;哥德尔的交点产生评论自身的格子,即不可证性。同一个几何想法,两个划时代的定理。
算术版本中,列以数为序号,通过登记表成为地址;格子(e, x)放的是sub(e, x),对角线放的是sub(x, x),哥德尔句则是H(h),即在评论谓词H自身的地址h处求值。
第七部分——数、数码、地址:n究竟是什么
三样东西,绝不能合并:
- 数n:抽象的,位于语言之外、我们的普通数学之中。一般而言,它只代表自身。若H是“为偶数”,H(12)就说十二是偶数,没有任何编码。框架的第1–7项根本没有提到编码。
- 数码n̄:墨迹,语言内部命名n的符号串,是Φ实际写入空位的东西。
- 地址读法:可选且外在。如果设置了哥德尔编号,n又恰好是编码,我们的登记表就在地址n处列出一个表达式,于是可以另外把H(n)读作关于那个表达式。数从不改变,只是我们的记账更丰富。“12是数还是员工?”问法不当:12是数;公司名册把一位员工与它关联起来。
对角时刻: 证明只代入一个有意思的数h,即H自身的地址。在H(h)中,同一个h同时戴两顶帽子:作为自变量,它只是交给谓词的数;作为地址,它是H在登记表中的位置。自变量与地址的这一重合,就是“表达式吃下自己的地址”的完整含义。
为什么一定要绕道数?因为算术语句只能关于数;编码是算术为其对象领域的贫乏支付的通行费。谜题语言被规定为丰富的,自变量直接就是表达式,所以无须支付这笔费用。
第八部分——“证明”的两种意义:谁规定规则
意义A——凭据,元理论。 “词典的忠实性被证明”,是说在我们的普通数学中被证明,与“素数有无限多个”背后的权威相同。不完备定理本身也是在意义A上被证明的。
意义B——集合P,被研究系统的规则。 在£中可证,就是能从列出的公理、按照列出的规则推导。没有谁规定唯一的规则:每个形式系统,如皮亚诺算术PA、ZFC、你明天设计的系统,都是一项提案;定理量化遍及所有提案。任何诚实的机械性规则体系,都会由同一对角方法获得其自身真而不可证的语句。规则的任意性不是漏洞,而就是量词。“公理是所有真句”的规则体系能逃过定理,但它不是机械的,而塔斯基证明没有公式能够表达它。
厉害之处: 意义A自身也可以被形式化为一套规则,而定理随即适用于它,产生一个我们自己的形式化数学也无法证明的真理。没有终极视角能够逃脱,元理论的层级永不封闭。这是内容,不是缺陷。
第九部分——两层模式:本次学习的总钥匙
几乎每个困惑最终都归结为同一形状:抽象层是规定的要求,具体层是可证明的引理。
| 主张 | 抽象上,框架 | 具体上,给定语言 |
|---|---|---|
| H(n)总是语句 | 选出类似代入的Φ的可接受性公理 | 语法引理,对公式归纳 |
| 编码忠实 | 无须要求,抽象项目中没有编码 | 每种操作都有经证明的凭据 |
| 可证性可以被命名 | 抽象定理的假设 | 通过算术化获得,即困难的90% |
相应地,哥德尔定理有难度极不对等的两个组成部分:
- 部分A,容易,即谜题:任何具有这些能力的语言,即可命名的可证性、对角化、否定,都包含真而不可证句。五符号机器让部分A变得可见:
P、N、~是最小工具箱,被规定为基本符号。谜题是框架的一个实例,但也是最小实例:框架把骨架穿在了外面。 - 部分B,困难,即哥德尔真正的工作: 证明真实算术虽然从未按
P或N符号设计,却仍拥有这些能力:命名可证性的真正算术公式,以及映照对角化的真正算术函数。哥德尔编号、sub、β函数、四十六个定义。哥德尔论文的大部分,以及Smullyan接下来的章节,都是部分B。
那么第6项的条件是空洞的吗? 不是。记号“E(n)”悄悄带入了括号图景,但抽象地说,Φ是表达式与数的有序对上的任意函数,而几乎所有这类函数都违反条件:取E的第一个符号、把E反转、算术中简单地在尾部连接,都会产生不合式串。公理选出类似代入的函数,正如结合律筛选群运算。只有当你只见过一种Φ时,它才显得多余;正如只见过整数加法时,群公理也显得多余。
H必须是算术的吗? 抽象上不必,谜题中的~PN就不是。对真正的定理而言则需要,因为对角论证要求语言足够丰富,能够命名自身的可证性,而算术是足够丰富的经典最小语言。任何包含它的系统,例如集合论或任何基础理论,都会继承不完备性;真正较弱的语言可以逃脱,有些还可证明地完备。
第十部分——区分清单:本次学习的每处迷雾,各用一行澄清
| 提出的困惑 | 解答 |
|---|---|
| 为什么直接自指需要无限字符串? | 一个句子只指称其括号中逐字包含的内容;没有字符串包含自身,因这要求length(S) = length(S) + 4。通过配方指称,而非复制。 |
| “所以这是自指悖论” | 是有意拆除了引信的近乎悖论:“假”被弱化为“不可打印”。说谎者爆炸,G则被迫进入真理与认证的间隙。拆除引信就是定理。 |
| “如果PN(~PN)是真的,它就应该可打印” | 它其实就是假的,它声称G可打印,但G不可打印,因此它因平淡的理由不可打印。只有可打印⟹真成立;真⟹可打印恰是定理摧毁的方向。 |
| 数怎么能同时遵循算术和语言规律? | 它们并没有;它们只遵循算术。语言规律通过词典在算术内部被模拟,每种操作都有一张经证明的凭据。这是翻译,不是混合。 |
| 什么决定哪些操作“合法”或“为真”? | 没有什么被裁定;对应关系要被证明,即提供凭据,可定义性由语言的资源清单确定,而编码从不赋予真理。深层边界:机械过程可以算术化,真理不行。 |
| 范式公式难道不是专用于312的吗? | 它是普遍的:k由x计算出来;公式从追加数位的算术推导;已用机器检验780个案例,并可对所有案例证明。普遍性=规律而非查找表=可用一个谓词表达。 |
| Φ就是词典吗? | 不是,是两种独立的外部工具。Φ:字符串→字符串,做代入。词典g:字符串↔数,做标记。代入从不触及编码。 |
| “可推导”“被替换为”“可证或可反驳” | 用词要清洁:代入≠推导,推导即证明;编码≠替换,而是映照;可证/可反驳并不穷尽可能,“两者都不是”存在,而这就是定理。 |
| 单纯连接怎么能保证H(n)是句子? | 它不能,也无须保证:条件限定在谓词上,而谓词经过校准,恰好就是其空位获语法认证的表达式。 |
| n代表什么? | 它自己,一个数,仅此而已。登记表可以选择在该地址列出表达式。在对角时刻,同一个数h同时既是自变量又是地址。 |
| 谜题就是框架本身吗? | 它是最小实例,即删掉一切非必要内容,并把关键能力给作基本符号的框架。它展示部分A;哥德尔的工作是部分B:证明算术暗中包含这套工具。 |
| 第6项的条件是空洞的吗? | 不是:抽象上Φ是任意的,几乎所有Φ都违反它;条件是可接受性公理,类似群公理。具体上它成为可证明的引理,因此感觉是自动成立的。 |
| H必须是算术的吗?n是地址吗? | 同一设计事实的两面:算术只能谈数,因此H必须是算术公式,而表达式只能经编码地址抵达;这是那个被规定为丰富的谜题从未支付的费用。 |
第十一部分——定理的最终形式
对任何语言包含算术、规则体系是机械性的、并且只证明真句的形式系统:都存在一个句子,可由对角配方显式构造,它是真的,却在该系统内既不可证也不可反驳。
它的姊妹定理,使用同一引擎,但保留“假”而不将其弱化,即塔斯基定理:这样的语言不能定义自己的真理。
它并没有说什么,为流行误用预先接种:它并不说真理是相对的,不说数学坏了,也不说什么都无法被认识。哥德尔句是被知道为真的,由我们从外部知道。限制在于任何单一机械规则体系能够从内部认证什么;而系统的诚实性恰恰造就其盲点。把系统升级到能打印G,会使它成为说谎者;每个诚实系统都有其自身的G,包括升级后的系统。
跨越所有表述层次的一行压缩:运用普通数学,意义A,我们表明,对任何诚实的机械规则体系,意义B,代入操作Φ与词典g复合起来,会制造一个真而超出该规则体系能力范围的句子。
第十二部分——自测
先作答再看答案;每题都在本次学习中处理过。
- 机器为什么不能打印
~PN(~PN),而它为什么是真的? PN(~PN)是自指的吗?是真的吗?可打印吗?- 在数位编码下计算
P的范式,分别用构造字符串和公式两种方式。 - 各用一句话说明Φ与哥德尔编号g的区别。
- 为什么范式的算术映照必须是一个普遍公式,而不能是逐案配方?
- 举一个违反第6项条件的Φ的例子。
- 为了使可证性能够算术化,规则体系必须具有什么性质,哪个著名概念不具备该性质?
- 在H(h)中,数h扮演哪两个角色?
答案
- 打印它会使它变假,因为它声称自己不可打印,从而违反诚实性;因此它永远不会被打印。而永远不被打印恰是它所声称的,所以它是真的。
- 不是,它谈的是G,另一个字符串;假,它声称G可打印,而G不可打印;不可打印,因为它是假的,这个平淡的理由。
- 字符串:
P(P)→数位1 4 1 5→1415。公式:x=1,k=1:1·10³ + 4·10² + 10·1 + 5 = 1415。✓ - Φ把一个数的数码代入表达式的空位,从字符串到字符串,从不触及编码。g给每个表达式标上编码数,是字符串世界与数世界之间的桥梁。
- 谓词是一个有限字符串,必须对每个代入值都有意义,包括写下它时尚不知道的值,即它自身的地址;只有统一规律能装进有限公式,查找表不行。
- Φ′(E, n)=E的第一个符号,它永远不是句子;或者反转E;或者把数码简单连接到公式尾部,造成不合式表达式。
- 机械性:检查证明必须是一种机械重复、无须判断的程序。真理不具备它,而塔斯基证明没有公式表达真理。
- 自变量,即谓词在其上求值的一个普通数,如“是偶数”中的12;以及地址,即H自身在登记表中所在的位置。两者的重合就是对角交叉。
第十三部分——Smullyan后面会讲什么,以及方法
接下来的章节,为你已有的骨架添上血肉: 构造一个具体算术语言;精确界定可表达性与可表示性;真正的哥德尔编号和代入函数,认识β函数,从+和×得到幂运算;然后是改进,即Rosser技巧,用单纯的一致性代替真理/可靠性假设,以及哥德尔第二定理,这类一致系统不能证明自身的一致性。
翻译表:记号令你迷惑时,翻译回火柴盒大小的机器:
| 形式术语 | 机器谜题 |
|---|---|
| 形式系统/可证 | 机器/可打印 |
| 可靠 | 机器从不说谎 |
| 谓词 | ~PN |
| E的对角化 | 范式X(X) |
| 哥德尔编号 | 从符号到数位的词典 |
| 哥德尔句 | ~PN(~PN) |
| 真而不可证 | 真而不可打印 |
| 不可判定,既不可证也不可反驳 | 机器对PN(~PN)与~PN(~PN)都保持沉默 |
带你走到这里的方法,值得有意保留:每一步进展都来自拒绝让一个说法轻易过关——为什么无限?那个公式难道不是专用于312的吗?谁规定规则?这个条件难道不是空洞的吗? 每一步都要求凭据;对每种似乎不付代价就能奏效的记号保持怀疑。把每个主张分进三个盒子之一:规定的,如谜题的P;可证明的,如范式公式;或者不可能的,如命名真理。这样就不会有迷雾残留。
本次学习回顾结束 · Smullyan《哥德尔不完备定理》第一章完成。