Gui Ruiyan

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 / 篇目

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:

  1. 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."
  2. Numerals mirror the axioms. PA's primitives are 0 and successor; the canonical name of n is literally n's construction written down.
  3. 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.
  4. 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?":

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

  1. 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.
  2. 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).
  3. 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:

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

  1. v1 is not 0 — a variable names nothing; 0 = 0 is one casting of the mold.
  2. 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.)
  3. 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.

  1. 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.
  2. Compute 0'' + 0'' step by step using only the two recursion equations, citing which equation fires at each step.
  3. In ∀v1 (v1 = v2 ⊃ ∃v2 (v2 ≤ v1)), classify every variable occurrence, and state whether the formula is a sentence.
  4. Is 0''' ≤ 0'''' a sentence? By what clause of the definition?
  5. State the degree of ~∀v1 ~(v1 = 0 ⊃ v1 ≤ 0') and show the count.
  6. State Smullyan's induction principle in the shelves-and-jobs form, and say what "the gift" is.
  7. 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.)
  8. 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)?
  9. Prove from T1 and T2: ~X ⊃ Y is true iff at least one of X, Y is true.
  10. In the ∃ proof, one step cites no T-rule. Which step, and what plain-logic fact does it use?
  11. Why is v1 = v1 not a sentence, given that every way of filling the slot yields a truth? (The "mechanical grammar" answer.)
  12. What property P was fed to the induction to establish that truth is well-defined, and how do open formulas satisfy it?

Answers

  1. 0''''. Numeral for n+1 = numeral for n with one prime appended — one symbol, no exceptions; 999→1000 changes every digit (carry logic).
  2. 0'' + 0'' = (0'' + 0')' [second eq.] = ((0'' + 0)')' [second eq.] = (0'')'' [first eq.] = 0''''.
  3. 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.
  4. Yes. "No variable has any free occurrence" is satisfied vacuously — there are no variables at all. It's a true atomic sentence (3 ≤ 4).
  5. Degree 4: one ~ (outer), one ∀, one ~ (inner), one ⊃.
  6. 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.
  7. (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.
  8. (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.
  9. ~X ⊃ Y true iff [T2] ~X not true or Y true iff [T1] X true or Y true.
  10. "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.
  11. 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.
  12. 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.