Kurt Gödel · 库尔特·哥德尔
Gödel’s Incompleteness Theorems · 哥德尔不完备性定理
Study journals ·
Gödel's Incompleteness — Chapter II, §1–§2: The Language L_E, Truth, and Induction
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 — Numbers vs. numerals: why 0'''' and not 4
- Part II — Successor: the atom of counting
- Part III — The quantifiers: infinite meaning at finite cost
- Part IV — Free and bound occurrences: the grammar of slots
- Part V — Vacuous truth, first appearance: sentences without variables
- Part VI — Regular formulas and the abbreviation layer
- Part VII — Inductive definitions: seeds, growth rules, and the shelf cascade
- Part VIII — Big gift vs. small gift: why degree beats parthood
- Part IX — Two machines, and the ⊃ table saga
- Part X — Exercise 1, solved in full
- Part XI — The Distinctions Ledger (every fog of the session, one line each)
- Part XII — Self-Test
- Part XIII — What's ahead in Smullyan, and the state of play
Study session of July 19, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter II ("Tarski's Theorem for Arithmetic"), §1 Syntactic Preliminaries and §2 The Notion of Truth, with Exercise 1 solved in full · Companion to the sessions of July 15 and 17, 2026
How to use this document
This follows the order in which understanding was actually built — each part presupposes the ones before it. For review: read Parts I–X in order the first time; afterwards the Distinctions Ledger (Part XI) alone is a full refresher, and the Self-Test (Part XII) tells you whether it took. The single most damaging bug of the session — reading ⊃ as ≡ — is quarantined in Part IX; if implication ever feels wrong again, go straight there.
Part I — Numbers vs. numerals: why 0'''' and not 4
The master distinction of the day (and of the whole subject): the number 3 is an abstract object; "3", "III", "0'''" are names for it. The formal language L_E needs its own official names — the numerals: 0, 0', 0'', 0''', … The numeral for n (written n̄ in metatheory) is 0 followed by n primes.
Why this scheme instead of decimal — four reasons, in increasing weight:
- Decimal isn't innocent. 1234 secretly means 1·10³ + 2·10² + 3·10 + 4 — positional notation has multiplication and exponentiation baked in. A system meant to prove arithmetic from scratch shouldn't smuggle arithmetic into its notation. 0''' presupposes nothing but "start at 0, step three times."
- Numerals mirror the axioms. PA's primitives are 0 and successor; the canonical name of n is literally n's construction written down.
- Uniformity makes induction glide. Numeral for n+1 = numeral for n plus one stroke. Compare 999 → 1000: every digit changes. Numerals exist to be reasoned about, not computed with; metatheoretic convenience beats human convenience.
- A 13-symbol alphabet keeps Gödel numbering clean (§4 codes strings essentially in base 13; ten digit symbols would be dead weight).
Nothing is lost: decimal could be added as pure abbreviation, and the unary scheme gives every natural number exactly one canonical name automatically, forever — a fact that later pays for the substitutional truth definition (Part III).
The habit of mind installed: always keep two levels separate — the object language (strings of the 13 symbols, meaningless until truth is defined) and the metalanguage (ordinary math-English where we talk about those strings and use 1234 freely).
Part II — Successor: the atom of counting
Successor is not addition; addition is built out of successor. S(n) = "the next one." Taking a successor never combines two quantities — it steps forward once. The recursion that manufactures addition:
n + 0 = n
n + S(m) = S(n + m)
Watched 2 + 2 dissolve into pure primes: 0'' + 0'' = (0'' + 0')' = ((0'' + 0)')' = 0''''. Every + eliminated.
Three answers to "why is successor more primitive?":
- The iteration ladder. Addition = iterate successor m times; multiplication = iterate addition; exponentiation = iterate multiplication. Each rung is "do the previous rung a variable number of times." Successor is the bottom: one fixed step, no parameter. The second argument of addition — the "how many times" — is exactly the generality successor doesn't have.
- Information content. To specify successor: one chain, 0 → 1 → 2 → … To specify addition: an infinite 2-D table — but the table comes for free from the chain via the recursion. Cheap thing assumed, big thing derived — that's what "primitive" means.
- Expressive power (a real theorem). Successor-only arithmetic: decidable, no Gödel phenomenon. Add + (Presburger): richer, still decidable. Add ×: undecidable, incompleteness kicks in. Strict hierarchy: successor < addition < multiplication. (The recursion building + from S lives in the metatheory; no first-order formula defines + from S alone — which is why L_E takes +, ·, E as primitive symbols.)
Resolved en route: 0'' = 0' + 0' is a theorem, not a definition — the numeral 0'' is defined as "one more prime than 0'," no addition anywhere. "One unit larger" was a loose gloss; the honest reading is "the next number."
Part III — The quantifiers: infinite meaning at finite cost
An open formula is a condition, not a statement. v1 ≤ 0'''' has a hole — plug in a number, get a verdict. ∀ closes the hole with "every": ∀v1 (v1 ≤ 0'''') is a genuine sentence (false — 5 refutes it).
Smullyan's truth condition (T3): ∀vi F is true iff F(n̄) is true for every natural number n — substitute the numeral for the free occurrences, demand truth every time. Slogans:
∀ is an infinite conjunction in disguise; ∃ is an infinite disjunction in disguise. The language can't write infinite ANDs; ∀ is the finite trick that means one.
Two loud footnotes on T3:
- Substitution captures "all" only because every number has a name (Part I's numerals). Over the reals this would fail — uncountably many reals, countably many names.
- T3 defines truth of one finite sentence via infinitely many facts. Fine as a definition; not a terminating computation. Truth is not mechanical — the crack through which Tarski's theorem later enters.
∃vi F := ~∀vi ~F — "not: F fails for every vi" = "F holds for at least one." Not one of the 13 symbols; pure shorthand.
Quantifier order is everything:
∀v1 ∃v2 (v1 < v2) true: every number is beaten by some number
∃v2 ∀v1 (v1 < v2) false: one number beating ALL numbers — including itself
The ≤ / < self-inclusion moral (from the drills): "for all v2" always includes the witness itself. ∃v1 ∀v2 (v1 ≤ v2) is true (witness 0; 0 ≤ 0 is fine); the < version dies on self-comparison. The ∀ takes no exceptions unless the formula makes room.
Part IV — Free and bound occurrences: the grammar of slots
Already familiar from ordinary math: in "the sum for k = 1 to 10 of k·x", x is a genuine unknown (free), k is internal machinery (bound) — renaming k changes nothing, asking "what if k = 5?" is nonsense.
The rule: an occurrence of a variable is bound iff it sits inside the scope of a quantifier on that same letter; otherwise free. A quantifier binds its own letter and nothing else. Classified per-occurrence, not per-letter — one letter can play both roles in one formula:
v1 = 0 ⊃ ∀v1 (0 ≤ v1)
↑ free ↑ bound (scope of ∀v1 is only the parenthesized part)
The drill-set trap (#4): ∀v1 (v1 = v2 ⊃ ∃v2 (v2 ≤ v1)) — the first v2 is free (outside ∃v2's scope; ∀v1 can't touch it), the second bound. Recipe: scan left from the occurrence; is there a quantifier on this same letter whose scope covers this spot?
Why it matters — three reasons:
- It draws the sentence/condition boundary. No free occurrences → sentence (true or false outright). Any free occurrence → open formula (a condition with slots). You can't even state Gödel's theorem without knowing which strings are sentences.
- Substitution targets free occurrences only. Free occurrences ask "which number?"; bound ones are the quantifier's spinning wheel. Overwriting bound occurrences yields garbage (∀0''(…) is not a formula).
- Free variables are how formulas name sets (§3's coming payload): F(v1) with one free variable carves out {n : F(n̄) is true} — e.g. ∃v2 (v1 = 0''·v2) carves out the evens. One free variable → set; two → relation; zero → sentence. Tarski's and Gödel's theorems are questions about which sets are carvable.
Bug found and fixed: "starts with a quantifier, so it's closed." No — a quantifier seals only its own letter's slots. ∀v1 (v1 ≤ v2) is OPEN (slot: v2). The mechanical test: after marking every occurrence, search for the word "free"; present → open, absent → sentence. Even ONE free occurrence makes it open.
Part V — Vacuous truth, first appearance: sentences without variables
Is 0' + 0' = 0'' a sentence? Yes. "No variable has any free occurrence" is a prohibition, not a requirement — search for free occurrences; you must find none. With no variables at all, the search comes back empty: satisfied vacuously, like "all the coins in my pocket are gold" said with empty pockets. Variable-free equations (1+1=2, 7·8=56) are the bread-and-butter sentences; terms without variables are constant terms, each designating a fixed number computed mechanically.
Vacuous truth turned out to be the session's recurring guest — it reappeared in bounded quantifiers, in the guarded induction property, and in the ⊃ table. Empty pockets: one idea, four jobs.
Part VI — Regular formulas and the abbreviation layer
Regular formula = free variables are exactly v1, …, vn (first n, no gaps). Purely a filing convention: a relation's arguments come in order, a formula's free variables don't — regularity supplies the correspondence (1st argument ↔ v1, …) once and for all instead of announcing it per theorem. A formula with free variables v13498, v98572498 is legal and instrumentally identical after renaming; nothing deep. Also: writing F(v1, …, vn) is metalanguage shorthand — no symbol "F" occurs in the language.
The complete abbreviation glossary (official symbols: 0 ' ( ) f , v ~ ⊃ ∀ = ≤ ♯):
t1 + t2 term built with f' (addition)
t1 · t2 term built with f'' (multiplication)
t1 E t2 term built with f''' (exponentiation)
n̄ 0 followed by n primes (metalanguage name for numerals)
F ∨ G := ~F ⊃ G "or"
F ∧ G := ~(F ⊃ ~G) "and"
F ≡ G := (F ⊃ G) ∧ (G ⊃ F) "iff"
∃vi F := ~∀vi ~F "there exists"
t1 ≠ t2 := ~(t1 = t2)
t1 < t2 := (t1 ≤ t2) ∧ (t1 ≠ t2)
(∀vi ≤ t) F := ∀vi (vi ≤ t ⊃ F) bounded universal
(∃vi ≤ t) F := ∃vi (vi ≤ t ∧ F) bounded existential
The ⊃/∧ asymmetry in bounded quantifiers is forced: bounded-∀ with ∧ would demand every number be ≤ t; bounded-∃ with ⊃ would be vacuously true via out-of-range vi. (Flag for later: all-quantifiers-bounded formulas = the computationally checkable ones — a main character in the incompleteness proof.)
The two-layer picture: one tiny official language optimized for provability of facts about the language; over it, human-friendly shorthand optimized for readability. Every abbreviation has a unique official expansion; nothing proved about official formulas is endangered by using shorthand. The defined symbols' correct behavior is proved, not assumed — that is Exercise 1 (Part X).
Part VII — Inductive definitions: seeds, growth rules, and the shelf cascade
Induction is the successor function's proof-side twin. N is exactly what's reachable from 0 by finitely many successor steps — so "holds at 0, survives every step" leaves no place to fail. Same architecture, reused:
natural numbers: seed 0 growth: successor
terms: seeds 0, variables growth: ', +, ·, E
formulas: seeds atomic (t1=t2, t1≤t2) growth: ~, ⊃, ∀vi
"Inductively defined" = everything generatable from the seeds by finitely many rule-applications — and nothing else (the implicit closure clause). Rule 1 plants seeds; rule 2 is about arbitrary already-built formulas. Every formula has a finite construction history — a birth certificate; strings without one (⊃⊃v1)( ) are not formulas.
Two confusions dissolved here:
- "Is ~F a formula just by definition?" Yes — and that's not a cop-out. The rules aren't observations about formulas; they create the word. What needs proof is everything claimed about the stipulated species afterwards.
- "Too many variations, unlike the number line." An inductive step is never proven instance-by-instance: the step for ~ is ONE argument about an arbitrary F, covering all applications at a stroke — exactly as "n → n+1" always covered infinitely many n. Total price of the branching: three step-arguments instead of one. The variety is horizontal (within shelves); induction travels vertically (up degrees).
Degree = count of occurrences of ~, ⊃, ∀ (how many growth steps built it). deg(~F) = deg(F)+1; deg(∀vi F) = deg(F)+1; deg(F1 ⊃ F2) = d1 + d2 + 1 — count what's in the string: all of F1's connectives, all of F2's, plus the new ⊃. Building strictly increases degree, so parts always sit on lower shelves.
Smullyan's induction principle, decoded ("it suffices to show it holds for all atomic formulas and that for any F, if it holds for all formulas of lower degree, it holds for F"):
- Sort all formulas onto shelves by degree. Every formula sits on exactly one finitely-numbered shelf.
- Job 1: shelf 0 (atomic) has the property.
- Job 2: for any F — with the gift assumption that all lower shelves are covered — F inherits the property.
- The cascade: shelf 0 by job 1; shelf 1 by job 2 (gift = shelf 0); shelf 2 (gift = shelves 0–1); … Any formula sits on some shelf n; the cascade arrives after n rounds. Nothing escapes.
Demonstration run in session: every formula contains = or ≤ — four lines (seeds have it visibly; each growth rule keeps everything already present).
Part VIII — Big gift vs. small gift: why degree beats parthood
The question that carried the session's deepest content: does job 2's gift mean "all formulas of lower degree" (big gift) or "just the parts that make up F" (small gift)?
Both principles are valid (the cascade covers lower shelves entirely either way), and for string-properties they coincide in practice. But they are not interchangeable as tools, and the book's central definition already forces the big one:
T3 defines the truth of ∀v1 F via the substitution instances F(0̄), F(0̄'), F(0̄''), … — which are lower degree (numerals add no connectives, so deg F(n̄) = deg F < deg ∀v1 F) but are NOT parts (the string 0''=0'' occurs nowhere inside ∀v1 (v1 = v1)).
Three stacked reasons the instances, not the literal part, must carry the recursion:
- The open part has no truth value to transmit. v1 = v1 is open — not in the truth definition's domain at all. The instances are its closed proxies: the mold's castings, and only castings can be true or false.
- Sentences aren't closed under parthood, but are closed under instantiation. Descend through parts and you fall out of the realm where truth exists; descend through instances and you stay among sentences the whole way down.
- Well-groundedness. A recursive definition needs "defined in terms of strictly earlier things." Parthood can't order the instances; degree can, bottoming out at 0. Degree grounds the truth definition AND powers proofs about it — one notion, double duty.
The precision point (from the final rehash): the small-gift conditional isn't false at ∀v1 (v1 = v1) — its antecedent holds (vacuously) and its consequent happens to be true. What fails is that the consequent can't be proved from the antecedent: a vacuous premise carries no information. Induction runs on the inheritance step being provable, not on the facts being true. Job 2 is a proof obligation.
The user's counter-proposal, honored: treat the instances as generalized predecessors and induct along that relation. Fully legitimate — induction works along ANY relation with no infinite descent, and deg strictly decreases to the predecessors (even infinitely many of them: the ∀-node has one per numeral, and well-foundedness doesn't need finite branching). "Induction on degree with the big gift" is exactly this custom relation with the paperwork pre-done. But the instances are still not parts: the semantic "infinite conjunction" must not collapse into the syntax, because the finitude of strings is sacred — infinite strings can't be written, can't have degrees, and fatally can't receive Gödel numbers. ∀ is precisely the device that buys infinite meaning at finite cost; erase the string/meaning distinction and the incompleteness theorem evaporates with it.
Part IX — Two machines, and the ⊃ table saga
The two machines (resolving "you said truth is not a property, now truth is in the induction")
- Machine 1 — definition by recursion on degree. T0–T3 assign every sentence a truth value, level by level: atomic sentences by computing constant terms; ~X flips X's value; X ⊃ Y looked up from both; ∀vi F from all the F(n̄). An assignment procedure — "false" is one of its outputs.
- Machine 2 — proof by induction on degree. The shelf cascade, taking a property P(F) that survives the growth rules.
"Is true" cannot be fed to machine 2 — truth doesn't propagate upward (~ flips it); feeding it in would "prove" all sentences true. What CAN be fed: properties about truth, e.g. the fundamental
P(F): IF F is a sentence, THEN exactly one of F, ~F is true.
— proved in session by induction on degree. Open formulas satisfy P vacuously (empty pockets again); the ∀-case is exactly where the big gift fires (instances: lower degree, not parts, and each IS a sentence). T0–T3 being mere clauses, that they succeed in assigning one and only one value is a theorem someone must prove — and now it's proven.
Why v1 = v1 is open despite "looking true"
- v1 is not 0 — a variable names nothing; 0 = 0 is one casting of the mold.
- The felt "obviously true" is aimed at the universal closure ∀v1 (v1 = v1) — a different, longer string, which is indeed a true sentence. (Some books define "open formula true" as "closure true" — coherent, but Smullyan keeps them distinct: they must be counted and coded as distinct strings.)
- The principled reason: grammar must be mechanical. Sentencehood is decided by form alone — a dumb symbol-scan. If v1 = v1 were classified "sentence" because all its instances are true, then classifying "v1 is not an odd perfect number" would await an unsolved problem of number theory. Syntax decidable, truth bottomless — that mismatch is the phenomenon the incompleteness theorem lives in.
Exercise 1, part 1, and the implication bug
The bug: reading X ⊃ ~Y as if it required the two sides to match (that's ≡), and inferring from it "if X is false, ~Y is false" (that's the inverse — a claim the conditional never made). Diagnosis chain in session: both-false case gave "contradiction" → no: a conditional is silent about the false-antecedent case. "If it's a dog, it's an animal" doesn't legislate about cats.
The table, memorized once and forever:
Z W Z ⊃ W
true true true
true false FALSE ← the only false row: promise broken
false true true ← vacuous
false false true ← vacuous
The court of final appeal: T2 is a definition, not a description you argue with. When English intuition and the rule disagree, compute from the rule. And the rule isn't arbitrary: "for every n, if n < 3 then n < 10" is obviously true, yet its instances at n = 5 (F→T) and n = 20 (F→F) must count as true or T3 kills the obviously-correct universal via numbers it was never about. False-antecedent-defaults-to-true = "not my case, no objection" = vacuous truth, fourth appearance.
The "or" bug underneath: "Z not true, or W true" was being read as exclusive or ("pick exactly one"). Mathematical "or" is inclusive — at least one, both allowed; it rules out only the both-fail row. Smullyan's own T2 phrasing ("X not true, or both X and Y true") carves the same three-row region with non-overlapping cases — same condition, different costume. The user's own paraphrase ("X false: Y unconstrained; X true: Y must be true") was correct all along.
Part X — Exercise 1, solved in full
All three parts proven in session, using only the definitions and T1–T3. The certified results:
1. X ∧ Y (:= ~(X ⊃ ~Y)) is true iff X and Y are both true.
X ∧ Y true iff X ⊃ ~Y not true (T1)
iff X true and ~Y not true (T2 negated: ⊃ fails only on (true, false))
iff X true and Y true. (T1)
2. X ∨ Y (:= ~X ⊃ Y) is true iff at least one of X, Y is true. (Done by the user, four cases, all correct — including both vacuous rows and the broken-promise row.)
~X ⊃ Y true iff ~X not true, or Y true (T2)
iff X true, or Y true. (T1)
3. ∃v1 F (:= ~∀v1 ~F) is true iff F(n̄) is true for at least one n. (Done by the user in one compact chain.)
∃v1 F true iff ∀v1 ~F not true (T1)
iff NOT: for every n, ~F(n̄) true (T3, with ~F as G)
iff for at least one n, ~F(n̄) not true ← the one uncited step: "not all" = "some fail"
iff for at least one n, F(n̄) true. (T1, inside each instance)
Note T1 fires twice at different depths — the ~∀~ double negation cancels through the quantifier, flipping "every" into "some." That's the actual mechanism behind "∃ = ~∀~."
What was accomplished: the official language has only ~, ⊃, ∀ — and it is now proved, not assumed, that the defined ∧ behaves as "and," ∨ as "or," ∃ as "there exists." First genuine metatheory done by hand.
Part XI — The Distinctions Ledger (every fog of the session, one line each)
| Confusion raised | Resolution |
|---|---|
| Why numerals 0'' instead of 1234? | Decimal smuggles in ×/exp; numerals mirror the axioms, make induction one-stroke, keep the alphabet at 13 for coding. Numbers vs. names of numbers — the master distinction. |
| Isn't successor just addition? Doesn't 0' presuppose "+1"? | Reverse: addition is iterated succession (n+0=n, n+S(m)=S(n+m)). 0''=0'+0' is a theorem, not a definition. Successor = "next," no combining. |
| What makes addition more general? | Its second argument = "how many times to step" — the parameter successor lacks. Ladder: S → + → × → exp, each rung iterating the last. Provable hierarchy: S-only and Presburger decidable; × brings incompleteness. |
| What does ∀vi F mean? | T3: true iff F(n̄) true for every n. Infinite conjunction in disguise; legitimate substitutionally only because every number has a numeral name. |
| Unknown symbol ∃ | Abbreviation: ∃v F := ~∀v ~F; binds exactly like ∀; infinite OR in disguise. |
| Free vs. bound — what and why? | Bound = inside the scope of a quantifier on the same letter (the Σ-index k); free = a genuine slot (the x). Decides sentence vs. condition, what substitution touches, and how formulas name sets. |
| Drill trap: v2 in ∀v1 (v1 = v2 ⊃ ∃v2 (v2 ≤ v1)) | First v2 free (outside ∃v2's scope; ∀v1 binds only v1's), second bound. Same letter, two roles. Classify occurrences, not letters. |
| "Starts with a quantifier → closed" | A quantifier seals only its own letter. One free occurrence anywhere → open. Test: mark everything, then search for the word "free." |
| Must a sentence have variables? Is 0'+0'=0'' one? | Yes it is: "no free occurrence" is a prohibition, satisfied vacuously by having no variables — empty pockets. |
| Why do regular formulas matter? Isn't F(v13498, …) the same? | Instrumentally identical after renaming. Regularity is a filing convention: 1st argument ↔ v1, … — the slot-order bookkeeping bought once instead of per theorem. |
| How do rules "about atomic formulas" define all formulas? | They don't alone: rule 1 = seeds, rule 2 = growth on arbitrary formulas, plus the implicit "nothing else." Same architecture as N (seed 0, growth S). Every formula has a finite birth certificate. |
| Is "~F is a formula" just by definition? | Yes — stipulation, not discovery; the rules create the word. What needs proof is everything claimed about the species afterwards. |
| "Prove atomic true, then degree-2 true, then all true???" | Induction never proves truth (~ flips it; you'd prove 0=0' true). It proves string-properties, or truth-about properties like "exactly one of X, ~X is true." |
| Formulas have too many variations vs. the number line | Step-proofs are about arbitrary F — one argument covers infinitely many instances, as "n→n+1" always did. Cost of branching: 3 cases, not 1. Variety is horizontal; induction climbs vertically. |
| The induction principle sentence itself | Shelves by degree; Job 1 = shelf 0; Job 2 = inherit with the gift "all lower shelves covered"; the cascade climbs. Any formula sits at finite height, so nothing escapes. |
| Why is deg(F1 ⊃ F2) = d1+d2+1? | Degree counts occurrences of ~, ⊃, ∀ in the string: all of F1's, all of F2's, plus the new ⊃. |
| Big gift ("all lower degree") vs. small gift ("the parts") — identical? | Both valid; for string-properties they coincide. But T3's instances are lower-degree NON-parts, so proofs through the ∀-clause need the big gift. Degree beats parthood: substitution preserves degree, destroys parthood. |
| "T4" | Book numbering: T0 atomic, T1 ~, T2 ⊃, T3 ∀. It's T3. |
| "Truth isn't a property — now it's in the induction?" | Two machines: recursion on degree defines the truth assignment (T0–T3); induction on degree proves guarded properties like "IF a sentence, THEN exactly one of X, ~X true" (open formulas: vacuous). |
| Why can't the part v1 = v1 transmit upward? | It has no truth value to transmit — open formulas are outside truth's domain. The instances are the closed castings of the mold; sentences are closed under instantiation, not parthood. |
| Aren't the instances "parts, semantically"? | As parthood: no — 0''=0'' occurs nowhere in the string; syntax must stay finite (Gödel numbering!). As induction predecessors: yes — any no-infinite-descent relation works, and degree certifies this one. Big-gift-on-degree = that custom relation, paperwork pre-done. |
| Why is v1 = v1 open when it "looks true"? | The felt truth targets the closure ∀v1 (v1 = v1) — a different string. v1 names nothing (it is not 0). Grammar must be mechanical: sentencehood can't await open problems ("v1 is not an odd perfect number"). |
| "Small gift condition isn't fulfilled" (rehash) | Sharper: the conditional is true but not provable from the vacuous premise. Induction runs on provable inheritance, not true facts. Job 2 is a proof obligation. |
| Both-false case: "X false, ~Y true contradicts X ⊃ ~Y" | The inverse fallacy — the conditional never legislated about the X-false case. ⊃ is false ONLY on (true, false): promise broken. Vacuous rows are true, and must be (else "all n<3 are n<10" dies at n=5). T2 is a definition — compute, don't argue. |
| "Z not true or W true" — can't both hold? | Inclusive or: at least one, both fine. Exclusive reading was the bug. Smullyan's "X not true, or both X and Y true" = same three rows, non-overlapping carving. |
Part XII — Self-Test
Answer before peeking; each was worked (or stumbled through) in the session.
- Write the numeral for 4, and explain in one sentence why the numeral for n+1 relates to the numeral for n more simply than 1000 relates to 999.
- Compute 0'' + 0'' step by step using only the two recursion equations, citing which equation fires at each step.
- In ∀v1 (v1 = v2 ⊃ ∃v2 (v2 ≤ v1)), classify every variable occurrence, and state whether the formula is a sentence.
- Is 0''' ≤ 0'''' a sentence? By what clause of the definition?
- State the degree of ~∀v1 ~(v1 = 0 ⊃ v1 ≤ 0') and show the count.
- State Smullyan's induction principle in the shelves-and-jobs form, and say what "the gift" is.
- Why does proving things about the truth of ∀-sentences need the "all lower degree" gift rather than the "constituent parts" gift? (Two reasons were given — degree/parthood and the open-formula one.)
- Which is the only false row of the ⊃ table? Why must the false-antecedent rows count as true (give the n<3/n<10 argument)?
- Prove from T1 and T2: ~X ⊃ Y is true iff at least one of X, Y is true.
- In the ∃ proof, one step cites no T-rule. Which step, and what plain-logic fact does it use?
- Why is v1 = v1 not a sentence, given that every way of filling the slot yields a truth? (The "mechanical grammar" answer.)
- What property P was fed to the induction to establish that truth is well-defined, and how do open formulas satisfy it?
Answers
- 0''''. Numeral for n+1 = numeral for n with one prime appended — one symbol, no exceptions; 999→1000 changes every digit (carry logic).
- 0'' + 0'' = (0'' + 0')' [second eq.] = ((0'' + 0)')' [second eq.] = (0'')'' [first eq.] = 0''''.
- Both v1's after ∀v1: bound (inside its scope). First v2 (in v1 = v2): FREE — outside ∃v2's scope, and ∀v1 binds only v1. Second v2 (in v2 ≤ v1): bound by ∃v2. One free occurrence → open formula (slot: v2), not a sentence.
- Yes. "No variable has any free occurrence" is satisfied vacuously — there are no variables at all. It's a true atomic sentence (3 ≤ 4).
- Degree 4: one ~ (outer), one ∀, one ~ (inner), one ⊃.
- Sort formulas onto shelves by degree. Job 1: every atomic formula (shelf 0) has the property. Job 2: for any F, given the gift — the property holds for ALL formulas of lower degree — show F has it. Then the cascade covers shelf 0, then 1, then 2, …; every formula sits at finite height.
- (a) T3's instances F(n̄) have the same degree as F (numerals add no connectives) — lower than ∀v1 F — but are not substrings of it; the parts-gift doesn't cover them, the degree-gift does. (b) The literal part F is open, hence has no truth value to transmit; the instances are closed and stay within truth's domain.
- (Z true, W false) — the broken promise. If false-antecedent rows were false, the true universal "for every n, n<3 ⊃ n<10" would be destroyed by its instances at n=5 (F→T) and n=20 (F→F) — refuted by numbers the claim was never about.
- ~X ⊃ Y true iff [T2] ~X not true or Y true iff [T1] X true or Y true.
- "NOT (for every n, ~F(n̄) true)" to "for at least one n, ~F(n̄) not true" — negation of a universal = existence of a counterexample. No T-rule; plain logic.
- Sentencehood must be checkable by a dumb symbol-scan (form alone). If it depended on all instances being true, classifying "v1 is not an odd perfect number" would await an unsolved problem. Syntax stays mechanical; truth is allowed to be bottomless — and that gap is where the incompleteness theorem will live.
- P(F): "IF F is a sentence, THEN exactly one of F, ~F is true." Open formulas satisfy the guard's failure — vacuously (empty pockets).
Part XIII — What's ahead in Smullyan, and the state of play
Position: Chapter II §1–§2 complete — the language L_E, terms, formulas, free/bound, degrees, the truth definition T0–T3, and Exercise 1 (all three parts, proven by hand).
Next: §3, Arithmetic Sets and Relations — the pivotal definition of the chapter: a set A is Arithmetic if some formula F(v1) expresses it, i.e. A = {n : F(n̄) is true}. Everything afterward is a question about which sets are Arithmetic. Tarski's theorem, the chapter's destination, is exactly: the set of Gödel numbers of true sentences is NOT Arithmetic — truth is a set no formula can carve out. First workout waiting: Exercise 2 — show "x divides y" is Arithmetic (the tools: ∃, ·, =, all certified today). Then §4, Concatenation and Gödel Numbering — where the 13-symbol economy of Part I pays out.
Standing connections to the July 15/17 sessions: the machine puzzle's stipulated kit (P, N, ~) is what Chapter II starts earning for real arithmetic — Component B begins here. "Expresses" (today's F(n̄)-true-iff-n∈A) is the semantic grade of capture from the July 17 toolkit; representability, its syntactic sibling, arrives with provability in later chapters.
The method, continued: today's engine was the same refusal to let sentences pass — doesn't 0' presuppose addition? is it just by definition? aren't the two gifts identical? how can v1 = v1 not be true? Sort every claim into stipulated (the rules that create "formula"), provable (that ∧ behaves as "and"; that truth is well-defined), or impossible (inducting on bare truth; infinite strings) — and demand the receipt each time. Four appearances of vacuous truth and one implication table were the day's tuition; both are now permanent equipment.
End of session review · Smullyan, "Gödel's Incompleteness Theorems," Chapter II §1–§2 complete · 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) · Next: Chapter II §3, Arithmetic Sets and Relations, Exercise 2.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
2026年7月19日学习记录 · 斯穆里安《哥德尔不完备性定理》,第二章(“算术的塔斯基定理”),§1句法预备与§2真的概念,附习题1完整解答 · 与2026年7月15日、17日记录配套
如何使用本文
本文依照理解实际形成的顺序展开,每部分都预设前面的部分。复习时,第一次依序阅读第一至第十部分;之后,单看区分清单(第十一部分)就能完整回顾,自测(第十二部分)则检验是否真正掌握。本次最具破坏性的错误——把⊃读成≡——被集中放在第九部分;如果再次觉得蕴涵不对劲,就直接看那里。
第一部分——数与数码:为什么用0''''而不用4
今天的核心区分(也是整个主题的核心):数3是一个抽象对象;“3”“III”“0'''”是它的名称。形式语言L_E需要自己正式的名称,即数码(numerals):0、0'、0''、0'''……n的数码(在元理论中记为n̄)就是0后面接n个撇号。
为什么采用这个方案,而不用十进制?四个理由,依重要性递增:
- 十进制并不中立。1234暗中表示1·10³ + 2·10² + 3·10 + 4:位值记数法已经内置了乘法与指数运算。一个要从头证明算术的系统,不应把算术偷带进自己的记号。0'''只预设“从0出发,走三步”。
- 数码映照公理。PA的原始成分是0和后继;n的规范名称就是n的构造过程的书面记录。
- 统一性使归纳顺畅。n+1的数码=n的数码再加一笔。比较999 → 1000:每一位都变了。数码是用来推理的,不是用来计算的;元理论的便利优先于人的便利。
- 13个符号的字母表使哥德尔编号简洁(§4本质上以13进制编码字符串;十个数字符号会成为多余负担)。
没有任何损失:十进制可以作为纯粹缩写加入,而一元记数方案会自动、永久地为每个自然数提供恰好一个规范名称。这个事实以后会为代入式的真定义提供支持(第三部分)。
由此建立的思维习惯:始终分开两个层次:对象语言(由那13个符号构成的字符串,在定义真之前没有意义),以及元语言(我们用来谈论那些字符串、可以随意使用1234的普通数学语言)。
第二部分——后继:计数的原子
后继不是加法;加法由后继构造。S(n)=“下一个”。取后继从不把两个数量合在一起,只向前走一步。制造加法的递归式是:
n + 0 = n
n + S(m) = S(n + m)
我们看着2 + 2化为纯粹的撇号:0'' + 0'' = (0'' + 0')' = ((0'' + 0)')' = 0''''。每个+都被消去了。
“为什么后继更原始?”有三个回答:
- 迭代的阶梯。加法=把后继迭代m次;乘法=迭代加法;指数运算=迭代乘法。每一级都是“把上一级做可变次数”。后继在最底部:固定的一步,没有参数。加法的第二个自变量——“做多少次”——正是后继所没有的一般性。
- 信息量。规定后继只需要一条链:0 → 1 → 2 → ……规定加法需要一张无穷二维表,但通过递归,这张表可以从链上免费获得。预设成本低的东西,推导规模大的东西,这就是“原始”的意思。
- 表达能力(一个真正的定理)。只有后继的算术:可判定,没有哥德尔现象。加上+(普雷斯堡算术):更丰富,仍可判定。加上×:不可判定,不完备性开始出现。严格层级:后继 < 加法 < 乘法。(从S构造+的递归位于元理论中;没有一阶公式能仅从S定义+,因此L_E把+、·、E作为原始符号。)
过程中解决的问题:0'' = 0' + 0'是一个定理,不是定义。数码0''被定义为“比0'多一个撇号”,其中没有加法。“大一个单位”是宽泛的说法,严格读法是“下一个数”。
第三部分——量词:以有限代价获得无穷意义
开放公式是条件,不是陈述。v1 ≤ 0''''有一个空位,填入一个数才得到判断。∀用“每一个”封闭这个空位:∀v1 (v1 ≤ 0'''')是一个真正的语句(假,因为5反驳它)。
斯穆里安的真条件(T3):∀vi F为真,当且仅当对每个自然数n,F(n̄)都为真:用数码代入自由出现的位置,每次都要求为真。可以这样概括:
∀是隐装的无穷合取;∃是隐装的无穷析取。语言写不出无穷个“且”;∀是用有限形式表达它的技巧。
关于T3的两个醒目注脚:
- 代入之所以能捕捉“全部”,只是因为每个数都有名称(第一部分的数码)。在实数上这会失败:实数不可数,名称却可数。
- T3通过无穷多个事实定义一个有限语句的真。作为定义没有问题,却不是会终止的计算。真不是机械的;塔斯基定理后来就从这道裂缝进入。
∃vi F := ~∀vi ~F:“并非F对每个vi都失败”=“F至少对一个成立”。它不在13个符号之中,只是缩写。
量词顺序至关重要:
∀v1 ∃v2 (v1 < v2) 真:每个数都被某个数超过
∃v2 ∀v1 (v1 < v2) 假:一个数超过所有数——包括它自己
≤ / <的自我包含教训(来自练习):“对所有v2”始终包括见证自身。∃v1 ∀v2 (v1 ≤ v2)为真(见证为0;0 ≤ 0没有问题);换成<就会在自我比较时失败。除非公式留出空间,否则∀没有例外。
第四部分——自由出现与约束出现:空位的语法
这个区别在普通数学中已经很熟悉:在“k从1到10的k·x之和”中,x是真正的未知数(自由),k是内部机制(约束)。重命名k不会改变任何东西,问“如果k=5呢?”则没有意义。
规则:变量的一次出现是约束的,当且仅当它处于针对同一个字母的量词辖域内;否则就是自由的。量词只约束自己的字母,不约束别的字母。分类针对每次出现,而非针对字母;同一个字母能在同一公式中承担两种角色:
v1 = 0 ⊃ ∀v1 (0 ≤ v1)
↑ 自由 ↑ 约束 (∀v1的辖域只有括号内部分)
练习集中的陷阱(第4题):∀v1 (v1 = v2 ⊃ ∃v2 (v2 ≤ v1))。第一个v2是自由的(在∃v2的辖域之外;∀v1管不到它),第二个则被约束。操作方法:从该次出现向左扫描,是否有针对同一字母、其辖域覆盖这一位置的量词?
为什么重要?三个理由:
- 它划出语句与条件的界线。没有自由出现→语句(直接就是真或假)。有任何自由出现→开放公式(带空位的条件)。不知道哪些字符串是语句,就连哥德尔定理都无法陈述。
- 代入只针对自由出现。自由出现问的是“哪个数?”;约束出现则是量词转动的轮子。覆盖约束出现会产生无意义的结果(∀0''(…)不是公式)。
- 自由变量是公式命名集合的方式(即将到来的§3的核心):具有一个自由变量的F(v1)划出{n : F(n̄)为真};例如∃v2 (v1 = 0''·v2)划出偶数。一个自由变量→集合;两个→关系;零个→语句。塔斯基和哥德尔定理问的就是哪些集合能够这样划出。
发现并修复的错误:“开头有量词,所以它是封闭的。”不对,量词只封住它自己字母的空位。∀v1 (v1 ≤ v2)是开放的(空位:v2)。机械检验方法:标记每次出现后,查找“自由”一词;有→开放,没有→语句。哪怕只有一次自由出现,也使它开放。
第五部分——空真首次登场:没有变量的语句
0' + 0' = 0''是语句吗?是。“没有变量具有任何自由出现”是一个禁止条件,而非必备条件:搜索自由出现,必须一个也找不到。完全没有变量时,搜索结果为空,条件便空真地满足;就像空口袋的人说“我口袋里的所有硬币都是金的”。不含变量的等式(1+1=2、7·8=56)是最常见的语句;不含变量的项是常项,各自指称一个可以机械计算的固定数。
空真后来成了本次学习的常客:它又出现在有界量词、带条件的归纳性质以及⊃真值表中。空口袋:一个观念,四种用途。
第六部分——正则公式与缩写层
正则公式=自由变量恰好为v1、…、vn(前n个,不跳号)。这纯粹是一个编排约定:关系的自变量有顺序,公式的自由变量却未必如此;正则性一次性规定对应关系(第一个自变量↔v1,……),不必每个定理都重新说明。自由变量为v13498、v98572498的公式完全合法,重命名后在使用上完全相同,没有深奥之处。另:写F(v1, …, vn)是元语言缩写,语言中并不存在符号“F”。
完整缩写表(正式符号:0 ' ( ) f , v ~ ⊃ ∀ = ≤ ♯):
t1 + t2 用f'构造的项 (加法)
t1 · t2 用f''构造的项 (乘法)
t1 E t2 用f'''构造的项 (指数运算)
n̄ 0后接n个撇号 (数码的元语言名称)
F ∨ G := ~F ⊃ G “或”
F ∧ G := ~(F ⊃ ~G) “且”
F ≡ G := (F ⊃ G) ∧ (G ⊃ F) “当且仅当”
∃vi F := ~∀vi ~F “存在”
t1 ≠ t2 := ~(t1 = t2)
t1 < t2 := (t1 ≤ t2) ∧ (t1 ≠ t2)
(∀vi ≤ t) F := ∀vi (vi ≤ t ⊃ F) 有界全称量词
(∃vi ≤ t) F := ∃vi (vi ≤ t ∧ F) 有界存在量词
有界量词中⊃/∧的不对称是必然的:有界∀若用∧,就会要求每个数都≤t;有界∃若用⊃,则会因为范围之外的vi而空真。(为后文作记号:所有量词都有界的公式,就是可通过计算检查的公式,将是不完备性证明中的重要角色。)
两层图景:一层是极小的正式语言,为证明关于该语言的事实而优化;上面一层是便于人阅读的缩写。每个缩写都有唯一的正式展开;使用缩写不会危及任何关于正式公式的证明。所定义符号的正确行为需要证明,而非预设:这就是习题1(第十部分)。
第七部分——归纳定义:种子、生长规则与层架递推
归纳是后继函数在证明一侧的孪生物。N恰好是从0出发,通过有限次后继步骤所能到达的一切,所以“在0成立,且每一步都保持成立”便不给失败留下位置。同一结构被反复使用:
自然数: 种子0 生长:后继
项: 种子0、变量 生长:'、+、·、E
公式: 种子为原子式(t1=t2、t1≤t2) 生长:~、⊃、∀vi
“归纳定义”=从种子出发,经有限次规则应用所能生成的一切,除此之外再无其他(隐含的封闭条款)。规则1种下种子,规则2针对任意已构造的公式。每个公式都有有限的构造历史,如同出生证明;没有这种证明的字符串(⊃⊃v1)( )不是公式。
这里消除了两个困惑:
- “~F是公式,仅仅因为定义如此吗?”是,而且这不是敷衍。规则不是对公式的观察,而是创造了这个词。随后关于这一被规定的种类所提出的所有主张,才是需要证明的。
- “变体太多,不像数轴。”归纳步骤从来不是逐个实例证明的:关于~的步骤是对任意F所作的一个论证,一次覆盖全部应用,就像“n → n+1”一直覆盖无穷多个n。分支增加的总代价只是:三个步骤论证,而非一个。多样性是横向的(同一层架内部);归纳则纵向推进(沿阶数向上)。
阶数=~、⊃、∀的出现次数(构造它需要多少个生长步骤)。deg(~F) = deg(F)+1;deg(∀vi F) = deg(F)+1;deg(F1 ⊃ F2) = d1 + d2 + 1。数字符串中的符号:F1的全部联结词、F2的全部联结词,再加新的⊃。构造严格增加阶数,因此组成部分总位于较低层架。
解读斯穆里安的归纳原理(“只需证明它对所有原子公式成立,而且对任意F,如果它对所有阶数更低的公式成立,那么它也对F成立”):
- 按阶数把所有公式放上层架。每个公式恰好位于一个以有限数编号的层架上。
- 任务1:第0层架(原子式)具有该性质。
- 任务2:对任意F,在获赠假设——所有更低层架已被覆盖——的条件下,F继承该性质。
- 逐层递推:任务1给出第0层架;任务2给出第1层架(赠予=第0层架);再给出第2层架(赠予=第0–1层架);……任何公式都位于某个第n层架,递推n轮后就能抵达。没有遗漏。
本次演示:每个公式都包含=或≤。只要四行:种子显然包含它们,而每条生长规则都保留原已存在的一切。
第八部分——大赠予与小赠予:为什么阶数胜过部分关系
承载本次最深内容的问题:任务2赠予的是“所有阶数更低的公式”(大赠予),还是“构成F的那些部分”(小赠予)?
两条原理都有效(两种情况下,递推都会完整覆盖较低层架),而对字符串性质而言,实际使用时两者一致。但作为工具,它们不能互换;书中核心定义已经迫使我们使用较大的那个:
T3通过代入实例F(0̄)、F(0̄')、F(0̄'')、……定义∀v1 F的真。这些实例阶数更低(数码不增加联结词,故deg F(n̄) = deg F < deg ∀v1 F),却不是部分(字符串0''=0''根本不出现在∀v1 (v1 = v1)内部)。
递归必须由实例而非字面上的部分承担,有三个层层推进的理由:
- 开放的部分没有可传递的真值。v1 = v1是开放的,根本不在真定义的定义域内。实例是它的封闭替身,就像模具的铸件;只有铸件才有真或假。
- 语句对取部分不封闭,对实例化却封闭。沿部分向下走,就会落出有真的领域;沿实例向下走,则始终留在语句之中。
- 良基性。递归定义需要“根据严格在先的东西进行定义”。部分关系无法为这些实例排序,阶数却可以,而且最终到达0。阶数既奠基真定义,又支持关于它的证明:一个概念,两项任务。
需要精确的地方(来自最后的重述):小赠予的条件句在∀v1 (v1 = v1)那里并非为假;其前件成立(空真),后件碰巧也为真。失败之处在于,后件不能从前件证明出来:空真的前提不携带信息。归纳依赖继承步骤可证明,而不只是事实为真。任务2是一项证明义务。
用户的反提议得到认可:把实例视作广义前驱,沿这个关系归纳。完全正当:归纳适用于任何没有无穷下降的关系,而从公式到前驱,阶数严格下降(即使前驱有无穷多个也无妨:∀节点对每个数码都有一个前驱,良基性不要求有限分支)。“带着大赠予对阶数归纳”,正是这个自定义关系,只不过手续已经办好。但实例仍然不是部分:语义上的“无穷合取”不能坍塌进句法,因为字符串的有限性不可侵犯。无穷字符串写不出来,不能有阶数,更致命的是不能获得哥德尔数。∀恰恰是以有限代价取得无穷意义的装置;抹去字符串与意义的区分,不完备性定理也随之消失。
第九部分——两台机器,以及⊃真值表的曲折
两台机器(解决“你说真不是性质,现在归纳里又有真了”)
- 机器1:对阶数递归定义。T0–T3逐层给每个语句赋予真值:原子语句通过计算常项;~X翻转X的值;X ⊃ Y从两者的值查表;∀vi F则从所有F(n̄)取得。这是赋值程序,“假”也是输出之一。
- 机器2:对阶数归纳证明。沿层架递推,处理一个在生长规则下保持的性质P(F)。
“为真”不能输入机器2:真不会向上传播(~会翻转它);输入它就会“证明”所有语句都真。能输入的是关于真的性质,例如这个根本性质:
P(F):如果F是语句,那么F、~F中恰好有一个为真。
本次通过对阶数归纳证明了它。开放公式空真地满足P(空口袋再次出现);∀情形恰好需要大赠予(实例阶数更低、不是部分,而且每个都是语句)。T0–T3只是条款,它们确实赋予唯一真值是一条必须有人证明的定理,而现在它已得到证明。
为什么v1 = v1“看上去真”却仍是开放的
- v1不是0:变量不命名任何东西;0 = 0是该模具的一个铸件。
- 感到它“显然为真”,针对的是全称闭包∀v1 (v1 = v1),即另一个更长的字符串,它确实是真语句。(有的书把“开放公式真”定义为“其闭包真”,这很一致,但斯穆里安保持两者有别:它们必须作为不同字符串被计数和编码。)
- 原则性理由:语法必须机械。是不是语句,只由形式决定,通过简单的符号扫描即可。如果v1 = v1因其全部实例为真而被归类为“语句”,那么给“v1不是奇完全数”分类,就要等待一个尚未解决的数论问题。句法可判定,真却没有底;不完备性定理就栖居在这一不匹配中。
习题1第一小题与蕴涵错误
错误:把X ⊃ ~Y读成要求两侧相同(那是≡),并由它推出“如果X为假,~Y也为假”(那是否命题,条件句从未提出这个主张)。本次诊断链:两侧都假时觉得“矛盾”→不,条件句对前件为假的情况保持沉默。“如果是狗,就是动物”并未对猫作规定。
一劳永逸记住这张表:
Z W Z ⊃ W
真 真 真
真 假 假 ← 唯一的假行:承诺被打破
假 真 真 ← 空真
假 假 真 ← 空真
最终裁判:T2是定义,不是可以争辩的描述。当自然语言直觉和规则冲突时,按规则计算。而规则并不任意:“对每个n,如果n < 3,那么n < 10”显然为真,但它在n=5(假→真)和n=20(假→假)时的实例必须算真,否则T3会用本来就不在陈述关注范围内的数,杀死这个显然正确的全称句。前件假则默认真=“不属于我的情况,没有异议”=空真第四次出现。
更深处的“或”错误:“Z不真,或W真”被读成了排他的或(“恰好选一个”)。数学的“或”是相容的:至少一个,允许两者都成立;只排除两者都不成立的一行。斯穆里安自己的T2措辞(“X不真,或X与Y都真”)用不重叠的情况划出相同的三行区域:同一条件,不同外衣。用户自己的转述(“X假:Y不受限制;X真:Y必须真”)一直都是对的。
第十部分——习题1完整解答
本次只用定义和T1–T3证明了全部三小题。已确证的结果:
1. X ∧ Y(:= ~(X ⊃ ~Y))为真,当且仅当X、Y都真。
X ∧ Y真 当且仅当 X ⊃ ~Y不真 (T1)
当且仅当 X真且~Y不真 (T2的否定:⊃仅在(真,假)时失败)
当且仅当 X真且Y真。 (T1)
2. X ∨ Y(:= ~X ⊃ Y)为真,当且仅当X、Y中至少一个为真。(用户完成,四种情况全部正确,包括两个空真行和承诺被打破的一行。)
~X ⊃ Y真 当且仅当 ~X不真,或Y真 (T2)
当且仅当 X真,或Y真。 (T1)
3. ∃v1 F(:= ~∀v1 ~F)为真,当且仅当至少存在一个n,使F(n̄)为真。(用户用一条简洁的推导链完成。)
∃v1 F真 当且仅当 ∀v1 ~F不真 (T1)
当且仅当 并非:对每个n,~F(n̄)真 (T3,令G为~F)
当且仅当 至少有一个n,使~F(n̄)不真 ← 唯一未引条款的步骤:“并非全部”=“有些失败”
当且仅当 至少有一个n,使F(n̄)真。 (T1,在每个实例内部)
注意T1在两个不同深度使用了两次:~∀~的双重否定穿过量词而抵消,把“每个”翻转成“某个”。这就是“∃ = ~∀~”背后的实际机制。
我们完成了什么:正式语言只有~、⊃、∀,而现在,定义出的∧表现为“且”、∨表现为“或”、∃表现为“存在”,都已得到证明,而非被预设。第一次亲手完成真正的元理论。
第十一部分——区分清单(本次的每一处迷雾,各用一行澄清)
| 提出的困惑 | 解决 |
|---|---|
| 为什么用0''这样的数码,而不用1234? | 十进制偷带×/指数运算;数码映照公理,使归纳只需加一笔,且让字母表保持13个符号以便编码。数与数的名称,这是核心区分。 |
| 后继不就是加法吗?0'不是预设“+1”吗? | 恰好相反:加法是后继的迭代(n+0=n,n+S(m)=S(n+m))。0''=0'+0'是定理,不是定义。后继=“下一个”,没有合并。 |
| 加法为什么更一般? | 第二个自变量=“走多少步”,这是后继没有的参数。阶梯:S → + → × → 指数,每一级迭代前一级。可证明的层级:只有S以及普雷斯堡算术都可判定;×带来不完备性。 |
| ∀vi F是什么意思? | T3:为真当且仅当每个n的F(n̄)都真。隐装的无穷合取;代入式处理之所以正当,只因每个数都有数码名称。 |
| 不认识符号∃ | 缩写:∃v F := ~∀v ~F;约束方式与∀完全相同;隐装的无穷“或”。 |
| 自由与约束:是什么,为什么? | 约束=位于针对同一字母的量词辖域内(Σ的指标k);自由=真正的空位(x)。它决定语句与条件的区别、代入触及什么,以及公式如何命名集合。 |
| 练习陷阱:∀v1 (v1 = v2 ⊃ ∃v2 (v2 ≤ v1))中的v2 | 第一个v2自由(在∃v2辖域外,∀v1只约束v1),第二个被约束。同一字母,两种角色。分类的是出现,而非字母。 |
| “以量词开头→封闭” | 量词只封闭自己的字母。任何位置只要有一次自由出现→开放。检验:标记全部出现,再查找“自由”一词。 |
| 语句必须有变量吗?0'+0'=0''算吗? | 算:“无自由出现”是禁止条件,没有变量就能空真地满足,如同空口袋。 |
| 正则公式为什么重要?F(v13498, …)不也一样吗? | 重命名后在使用上完全相同。正则性是编排约定:第一个自变量↔v1,……一次做好空位顺序的记账,不必每个定理重来。 |
| “关于原子公式”的规则如何定义全部公式? | 单靠它不行:规则1=种子,规则2=对任意公式的生长,再加隐含的“除此之外没有别的”。结构与N相同(种子0,生长S)。每个公式都有有限的出生证明。 |
| “~F是公式”只是定义如此吗? | 是,规定而非发现;规则创造这个词。此后关于这个种类所说的一切,才需要证明。 |
| “证明原子式真,再证明二阶公式真,再证明全部真???” | 归纳从不证明真(~会翻转它;否则会证明0=0'真)。它证明字符串性质,或关于真的性质,如“X、~X中恰有一个真”。 |
| 公式比数轴的变体多太多 | 步骤证明针对任意F,一个论证覆盖无穷实例,就像“n→n+1”一直如此。分支的代价:三个情形,而非一个。多样性横向展开,归纳纵向攀升。 |
| 归纳原理那句话本身 | 按阶数放层架;任务1=第0层架;任务2=获赠“较低层架全被覆盖”的假设后继承;递推向上。任何公式高度有限,所以没有遗漏。 |
| 为什么deg(F1 ⊃ F2) = d1+d2+1? | 阶数数的是字符串中~、⊃、∀的出现:F1的全部、F2的全部,再加新的⊃。 |
| 大赠予(“所有较低阶”)与小赠予(“部分”)一样吗? | 都有效;对字符串性质两者一致。但T3的实例是较低阶的非部分,因此经过∀条款的证明需要大赠予。阶数胜过部分关系:代入保留阶数,却破坏部分关系。 |
| “T4” | 书中编号:T0原子式,T1 ~,T2 ⊃,T3 ∀。应该是T3。 |
| “真不是性质,现在又进了归纳?” | 两台机器:对阶数递归定义真值赋值(T0–T3);对阶数归纳证明带条件的性质,如“如果是语句,则X、~X中恰有一个真”(开放公式:空真)。 |
| 为什么部分v1 = v1不能向上传递? | 它没有可传递的真值:开放公式在真的定义域之外。实例是模具的封闭铸件;语句对实例化封闭,对部分关系不封闭。 |
| 实例不是“语义上的部分”吗? | 作为部分关系:不是,0''=0''不在字符串中;句法必须有限(哥德尔编号!)。作为归纳前驱:是,任何无无穷下降的关系都行,阶数为此作保。对阶数使用大赠予=该自定义关系,手续已办好。 |
| v1 = v1“看上去真”,为什么开放? | 感到的真针对闭包∀v1 (v1 = v1),是另一个字符串。v1不命名任何东西(它不是0)。语法必须机械:判断语句身份不能等待未解问题(“v1不是奇完全数”)。 |
| “小赠予条件没有满足”(重述) | 更准确地说:条件句为真,却不能从空真前提证明。归纳靠可证明的继承,不是靠真的事实。任务2是证明义务。 |
| 两者都假:“X假、~Y真,与X ⊃ ~Y矛盾” | 否命题谬误:条件句从未规定X假的情况。⊃只在(真,假)时假:承诺被打破。空真行是真,而且必须真(否则“所有n<3都有n<10”会在n=5处失败)。T2是定义:计算,不是争辩。 |
| “Z不真或W真”:两者不能都成立吗? | 相容的或:至少一个,两者都可以。排他读法就是错误。斯穆里安的“X不真,或X与Y都真”=相同的三行,以不重叠的方式划分。 |
第十二部分——自测
先回答,再看答案;每题都在本次学习中做过(或跌跌撞撞地走过)。
- 写出4的数码,并用一句话解释,为什么n+1的数码与n的数码之间的关系,比1000与999之间的关系简单。
- 只用两条递归等式逐步计算0'' + 0'',指出每步使用哪条等式。
- 在∀v1 (v1 = v2 ⊃ ∃v2 (v2 ≤ v1))中,对每次变量出现分类,并说明公式是不是语句。
- 0''' ≤ 0''''是语句吗?根据定义的哪条?
- 说出~∀v1 ~(v1 = 0 ⊃ v1 ≤ 0')的阶数,并展示计数。
- 用层架与任务的方式陈述斯穆里安的归纳原理,说明“赠予”是什么。
- 为什么证明关于∀语句的真的事情,需要“所有较低阶”的赠予,而不只是“组成部分”的赠予?(给过两个理由:阶数/部分关系,以及开放公式问题。)
- ⊃真值表中唯一的假行是什么?为什么前件假的两行必须算真(给出n<3/n<10的论证)?
- 从T1与T2证明:~X ⊃ Y为真,当且仅当X、Y中至少一个真。
- 在∃的证明中,有一步没有引用T规则。是哪一步,用了哪个普通逻辑事实?
- 既然每种填空方式都得到真,为什么v1 = v1不是语句?(用“机械语法”回答。)
- 为证明真被良好定义,归纳中输入了什么性质P?开放公式如何满足它?
答案
- 0''''。n+1的数码=n的数码再附一个撇号:一个符号,没有例外;999→1000每位都变(进位逻辑)。
- 0'' + 0'' = (0'' + 0')'[第二条]= ((0'' + 0)')'[第二条]= (0'')''[第一条]= 0''''。
- ∀v1之后的两个v1都被约束(在其辖域内)。第一个v2(v1 = v2中)自由:在∃v2辖域外,∀v1只约束v1。第二个v2(v2 ≤ v1中)被∃v2约束。一次自由出现→开放公式(空位:v2),不是语句。
- 是。“没有变量有任何自由出现”被空真地满足,因为完全没有变量。它是真原子语句(3 ≤ 4)。
- 阶数4:一个~(外层),一个∀,一个~(内层),一个⊃。
- 按阶数把公式放上层架。任务1:每个原子公式(第0层)有该性质。任务2:对任意F,获赠假设——所有阶数更低的公式都有该性质——后,证明F有该性质。递推依次覆盖第0层、第1层、第2层、……;每个公式都在有限高度。
- (a)T3的实例F(n̄)与F阶数相同(数码不加联结词),低于∀v1 F,却不是它的子串;部分赠予不覆盖它们,阶数赠予覆盖。(b)字面上的部分F是开放的,没有可传递的真值;实例是封闭的,始终在真的定义域内。
- (Z真,W假),即承诺被打破。如果前件假的行是假,那么真全称句“对每个n,n<3 ⊃ n<10”就会被n=5(假→真)和n=20(假→假)的实例破坏,即被原本不在其关注范围内的数反驳。
- ~X ⊃ Y真,当且仅当[T2]~X不真或Y真,当且仅当[T1]X真或Y真。
- 从“并非(每个n都使~F(n̄)真)”到“至少有一个n使~F(n̄)不真”:全称句的否定=反例的存在。没有T规则,只是普通逻辑。
- 语句身份必须能通过简单的符号扫描(仅看形式)检查。如果依赖所有实例都真,给“v1不是奇完全数”分类就得等待一个未解问题。句法保持机械;真可以没有底,而不完备性定理就将处在这个间隙里。
- P(F):“如果F是语句,那么F、~F中恰有一个真。”开放公式因前件不成立而空真地满足它(空口袋)。
第十三部分——斯穆里安后面的内容与当前进度
位置:第二章§1–§2完成:语言L_E、项、公式、自由/约束、阶数、真定义T0–T3,以及习题1(三小题,全部手证)。
下一步:§3,算术集合与关系。本章的关键定义:集合A是算术的(Arithmetic),如果某个公式F(v1)表达它,即A = {n : F(n̄)为真}。此后的一切都在问哪些集合是算术的。本章目标塔斯基定理正是:真语句的哥德尔数集合不是算术的,真是一个没有公式能划出的集合。等待的第一次练习:习题2,证明“x整除y”是算术的(工具:∃、·、=,今天都已确证)。然后是§4,拼接与哥德尔编号,第一部分13符号方案的经济性将在那里兑现。
与7月15日/17日记录的持续联系:机器谜题所规定的工具包(P、N、~),是第二章开始为真正算术逐步挣得的东西:组件B从这里开始。“表达”(今天的F(n̄)真当且仅当n∈A)是7月17日工具包中语义层次的捕捉;其句法兄弟可表示性,将随可证明性在后面章节出现。
继续沿用的方法:今天的动力仍是拒绝放过每句话:0'不预设加法吗?它只是定义如此吗?两种赠予不是一样吗?v1 = v1怎么能不真?把每个主张归入规定的(创造“公式”的规则)、可证明的(∧表现为“且”;真被良好定义)或不可能的(对裸露的真作归纳;无穷字符串),而且每次都要求凭据。空真的四次登场与一张蕴涵表,是今天的学费;两者如今都成为了常备工具。
本次复习结束 · 斯穆里安《哥德尔不完备性定理》第二章§1–§2完成 · 前序文件:Godel-Incompleteness-Session-2026-07-15.md(第一章框架与机器谜题)、Godel-Incompleteness-Session-2026-07-17-Answer-Sheet.md(第一章习题1–7)· 下一步:第二章§3,算术集合与关系,习题2。