Gui Ruiyan

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

Study journals ·

Gödel's Incompleteness — Chapter II, §3: Arithmetic and arithmetic Sets, Relations, and Functions

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 20, 2026 · Smullyan, "Gödel's Incompleteness Theorems," Chapter II §3 (Arithmetic and arithmetic Sets and Relations), with Exercises 2–5 solved in full · Companion to the sessions of July 15, 17, and 19, 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 — binding the output variable with ∃ in a graph formula, three rounds of it — is quarantined in Part IX; if a formula's free-variable count ever feels negotiable again, go straight there.


Part I — Set vs. Relation: the inseparability lives inside the tuple

The suspicion brought to the session: a relation, unlike a set, is "not a collection of individual members" but something that binds members together inseparably. Half right — and the wrong half matters.

The extensional view (Smullyan's, and modern math's): a relation IS a set — a set whose elements are ordered tuples rather than single numbers. The inseparability lives inside each element: the element is the tuple (3, 12), and asking whether 3 alone belongs to the divides relation is a type error — like asking whether the left half of a chair is furniture.

The hierarchy:

set of numbers        elements: single numbers      Evens = {0, 2, 4, …}
2-place relation      elements: ordered pairs       Divides = {(1,1), (2,4), (3,12), …}
3-place relation      elements: ordered triples     Addition = {(x,y,z) : x+y=z}
n-place relation      elements: n-tuples

(3,12) ∈ Divides but (12,3) ∉ Divides — order does real work. And the unification: a set is the degenerate case, a 1-place relation — which is why "expresses" gets defined once for F(v1,…,vn) and the set case is n = 1.

Mental model that stuck: a 2-place relation is a two-column table with infinitely many rows. The relation is the table — the totality of rows — not glue between numbers.


Part II — Tuples and the identity law

An n-tuple (a1, …, an) is a finite ordered list. Three contrasts with sets:

  1. Order matters: (2,3) ≠ (3,2), but {2,3} = {3,2}.
  2. Repetition matters: (1,1) is a real pair; {1,1} = {1}.
  3. Fixed length: a pair and a triple are different kinds of object.

The one law that governs tuples — the entire job description of "ordered":

(a1, …, an) = (b1, …, bn) iff a1 = b1 and … and an = bn.

Same entries, same positions. Nothing else about tuples is ever used, anywhere in mathematics. So "relation = set of tuples," and the database table is the honest picture: each row a tuple, the table the relation.


Part III — The Kuratowski digression: order without a new primitive

The challenge raised: doesn't defining ordered pairs inside unordered set theory smuggle in a new primitive called "order"?

Step 1 — what "remembering order" demands. Pair-formation is an encoding: hand in two things with role labels, get back one object. The object remembers order exactly when the encoding is lossless — two different hand-ins never collide. Losslessness written out is precisely the identity law. It isn't a side-property of order; it IS order, restated.

Step 2 — watch bare sets fail it. Try the naive encoding (a,b) := {a,b}. Then "2 first, 3 second" gives {2,3}, and "3 first, 2 second" gives {3,2} — the same set. Two different hand-ins, identical objects: the law is violated, the information "which was first" destroyed at the moment of collection. This one line — {2,3} = {3,2} — is the precise cash value of "sets are unordered." (Repetition dies too: (1,1) ↦ {1,1} = {1}.)

Step 3 — the nested encoding passes. Define (a,b) := {{a},{a,b}}. Now (2,3) = {{2},{2,3}} and (3,2) = {{3},{2,3}} — different sets, since {2} ≠ {3}. Every set in sight is still unordered ({{a},{a,b}} = {{a,b},{a}} — fine); the encoding recovers order not by positioning but by giving the inputs structurally different roles: a is a member of BOTH members, b (when ≠ a) of only one. "Member of both members" is statable purely with ∈.

Step 4 — the proof of the identity law (⇐ is substitution; ⇒ by cases):

  • Case a = b: code collapses to {{a}} (one member). So {{c},{c,d}} has one member, forcing {c} = {c,d} = {a}, so c = d = a. ✓
  • Case a ≠ b: code has two members — singleton {a}, doubleton {a,b}. The singleton on the right can't be {c,d} (if c ≠ d, wrong size; if c = d the right side collapses to one member, contradiction). So {c} = {a}, c = a; then {a,d} = {a,b} and b ≠ a forces b = d. ✓

Decoders, definable from ∈ alone: first(x) = the unique u belonging to every member of x; second(x) = if x has one member, first(x), else the u in the doubleton but not the singleton.

Step 5 — why no primitive was smuggled. The primitives of set theory: one non-logical symbol, ∈, plus the logical apparatus (variables, =, ~, ∧, ∨, →, ∀, ∃) and axioms (extensionality: sets equal iff same members; pairing). A definition is an abbreviation — "(a,b)" macro-expands to a formula in ∈ and logic. Contrast the alternative: adding a primitive symbol pair(a,b) with the identity law as a new axiom — postulated content. Kuratowski gets the same law as a theorem. Postulated vs. proved — the entire difference. Definitions are conservative: they can never make new facts about ∈ provable; only notation grew.

The trilogy of the same move, now seen three times:

≤ from + alone:        ∃v3(v1 + v3 = v2)        trivial     (the bracketed remark on p.19)
pairs from ∈ alone:    {{a},{a,b}}              one page    (this digression)
E from + and · alone:  x^y = z arithmetic        HARD        (Gödel's non-trivial result, owed to a later chapter)

Propose a definition in the poorer language; prove it behaves exactly as the richer notion demands. The proof is what earns "no new primitive." When something feels smuggled, ask: what is the specification of this notion, and was it proved or postulated?


Part IV — Metatheory vs. object language: when primitives matter

The deflating question, asked and honored: why ground tuples in set-theoretic primitives at all — doesn't it suffice to take tuples/relations as given? It does. Two projects were being conflated:

  • Project 1 (Smullyan's book): work in ordinary informal mathematics — the metatheory — where sets, tuples, relations, functions are taken as given. Fully rigorous, provided you know the governing law of what you assume (for tuples: the identity law). Nothing in the incompleteness theorem depends on what tuples "are made of."
  • Project 2 (foundational bookkeeping): reduce everything to the smallest base. Interesting, optional, not a prerequisite.

But the exercise wasn't wasted — it's a dress rehearsal. The formal language L_E is not relaxed: it has exactly 0 ' + · E ≤ = and logic, and can talk about nothing but natural numbers. Yet Gödel's proof needs arithmetic to talk about sequences (ultimately: formulas, including the very sentence being constructed). So the same game — "the theory lacks X natively; encode X losslessly using only its primitives" — must be played again on harder ground:

in set theory:   encode a pair of sets as a set        easy (Kuratowski)
in arithmetic:   encode a finite sequence of numbers   real work — §4, Gödel numbering
                 as a single number

Success criterion identical both times: lossless (distinct sequences, distinct codes) and the decoding relations expressible from the primitives. Out in the metatheory we may posit freely; inside the object language every notion must be earned from the primitives, and the earning is the proof.


Part V — Arithmetic vs. arithmetic

Definitions: a set/relation is Arithmetic (capital A) if expressed by some formula of L_E (E allowed); arithmetic (small a; adjective stressed arith-MET-ic — the footnote) if expressed by an E-free formula. Small-a is the harder club to join; every arithmetic relation is trivially Arithmetic.

The foreshadowed non-trivial result (Gödel's): x^y = z is itself definable from + and · alone. Once proved, any formula using E can be rewritten E-free, so Arithmetic = arithmetic and the distinction collapses. Until then, Smullyan works with the convenient capital-A notion and pays the debt later.

Why it matters:

  1. It strengthens incompleteness enormously. Peano Arithmetic's language has only ', +, · — no E. If the coding machinery genuinely needed E, incompleteness would only hit the richer language, leaving hope that plus-and-times arithmetic is complete. Gödel's definability result kills that hope.
  2. The boundary is razor thin, so primitive-bookkeeping is not pedantry: + alone (Presburger) — complete, decidable; add · — incomplete, undecidable. One symbol separates a tame theory from an incompletable one. (Extends the July 19 hierarchy: S < + < ×.)

Part VI — Functions enter through their graphs; properties and conditions

The problem: formulas can only express relations — that's the only "expresses" there is. So how can a function be Arithmetic?

The move: look at the graph, not the rule. The function f(x1,…,xn) is Arithmetic iff the (n+1)-place relation f(x1,…,xn) = y is — one extra place for the output. Book's own statement: f is Arithmetic iff there is a formula F(v1,…,vn,v_{n+1}) such that for all x1,…,xn and y: F(x̄1,…,x̄n,ȳ) is true iff f(x1,…,xn) = y.

Two loud notes on that sentence:

  • "For all … and y" includes wrong y's. The formula must be true at exactly the graph and FALSE everywhere else. It doesn't compute the output; it recognizes correct input–output tuples and rejects impostors — and the rejecting is where all the information lives.
  • Example: f(x) = x² has graph {(0,0),(1,1),(2,4),(3,9),…}, expressed by v2 = v1·v1. F(3̄,9̄) true; F(3̄,1̄0̄) false.

Vocabulary paragraph (pure bookkeeping): a property P is Arithmetic iff the set of numbers having P is (property ↔ set, interchangeable — "even" vs. the evens); condition = umbrella term for "n-place relation, any n ≥ 1." After §3, set, property, relation, function, condition all reduce to one idea: a set of tuples, possibly expressed by a formula.


Part VII — Exercise 2: divides and primes

Part 1 — "x divides y" is arithmetic. Solved first try:

d(x, y):  ∃z(y = x·z)

Edge checks: every x divides 0 (z = 0) ✓; 0 divides only 0 (0·z = 0) ✓. Kept on the bench for reuse.

Part 2 — the primes. Three bugs, found and fixed across two attempts:

  1. The "any" trap: wrote ∀y(x = y·z) for "z times some y gives x." English "any" flips between ∀ and ∃; the intended clause was ∃y(x = z·y) — which is exactly d(z,x). (That's why the book put divides first: part 2 wants it as a component.)
  2. Forgot the divisor x itself: "no z other than 1 divides x" is failed by every x ≥ 2, since x divides x. Primality permits TWO divisors: every divisor is 1 or x.
  3. Boundary off-by-one: ~(0'' ≥ x) says x > 2, i.e. x ≥ 3 — evicting 2, the one even prime. The formula expressed the odd primes. Fix: 0'' ≤ x. (Also: L_E has ≤ only, and the numeral for 1 is 0'.)

The certified formula:

P(x):  0'' ≤ x  ∧  ~∃z( ∃y(x = y·z) ∧ ~(z = 0') ∧ ~(z = x) )

Test battery: 0 fails (2 divides 0, and 2 ∉ {1, 0}); 1 fails (size clause); 2 passes; 7 passes. No E — the primes are arithmetic, small a.


Part VIII — Exercise 3: f⁻¹(A), and how to say "belongs to"

Task: if A and f are Arithmetic, so is f⁻¹(A) = {n : f(n) ∈ A}; same for arithmetic.

First attempt's failure mode — the hand-wave: "since the whole tuple is expressible and one part is, the other part must be — like the chain rule." Diagnosis: expressibility is not a substance that flows through tuples by conservation; it's closure under logical operations, and the proof is the explicit gluing. Standard for this whole genre: to prove something Arithmetic, exhibit the formula and verify the biconditional. "We can always construct" is a claim, not a construction. (Also flagged: "x must be expressible" is a category error — numbers aren't expressible; sets and relations are.)

The key conceptual unlock — L_E has no membership symbol. Sets don't exist inside L_E. "y belongs to A" is asserted by the expressing formula itself: A(n̄) is true iff n ∈ A, so the formula IS the membership test, and "belongs to" = "passes the test." To say "v3 is even," take the evens' formula ∃v2(v1 = 0''·v2) and put v3 in its free slot (renaming bound variables first if they'd collide — the "arithmetically equivalent" paragraph on p. 19 exists precisely to license this gluing). Same for f: no function symbol, only the graph formula.

The construction (derived by the user as a chain of iffs — a genuine proof):

G(x):  ∃y( F(x, y) ∧ A(y) )        official: ∃v2(F(v1,v2) ∧ A(v2))

Verification: forward — a witness y has f(x) = y ∈ A; backward — y = f(x) is a witness (totality of f spent here: every x has an output to witness with). Small-a bonus: the construction added only ∃ and ∧, never E, so the identical proof handles "arithmetic."

The arity principle, coined here: number of free variables = arity of the thing expressed. F(x,y) ∧ A(y) unquantified has two free slots — a fine 2-place relation, but the target was a set; ∃y takes arity 2 to arity 1. Free variables aren't "undefined" — they're the input slots.


Part IX — Exercise 4 and the ∃z saga (the session's main battle)

The exercise: compositions. Given F expressing f(x)=y and G expressing g(x,y)=z (or g one-place for part 1), show f(g(x)), g(f(x),y), g(x,f(y)), f(g(x,y)) Arithmetic.

Bug 1 — the category error: formulas don't nest

First attempt wrote F'(F(x,y), z) — a formula stuffed into an argument slot. Argument slots take terms (things denoting numbers); F(x,y), once instantiated, is a statement. "Is (3 < 5) even?" doesn't typecheck. Nested-function-call habits don't transfer: in L_E there is no term "g(x)" to pass along — g exists only through its graph formula, which asserts rather than computes.

The universal fix — flatten with a fresh temporary (the compiler pass): f(g(x)) = z unpacks as "there exists t such that g(x) = t and f(t) = z." One conjunct per step, ∃ on the temporary. Exercise 3's construction was the template all along.

Bug 2 — binding the output: three rounds, five explanations, one resolution

Three consecutive attempts ended ∃y(∃z(…)) — closing the output slot along with the temporary, leaving only x free. Explanations attempted, in order: (i) the arity principle; (ii) computing what the formula actually expresses — since f, g are total, ∃y∃z(F'(x,y) ∧ F(y,z)) is true for EVERY x: it expresses ℕ, with the same answer-pattern as x = x — all information about the values destroyed; (iii) formula-as-answering-machine: free variables are the dials, ∃ rips a dial off the panel, and after ∃z the question "is 10 the value at 2?" becomes unaskable — a formula that can never say no pins down nothing (∃y(y = x·x) and ∃y(y = x·x·x) become indistinguishable: squaring and cubing, same always-true formula); (iv) asserting vs. defining: "every person has a mother" is true and defines nothing about who anyone's mother is; "y is the mother of x" — the open form — is what defines the relation, because a phrase defines only through its ability to reject ("the smallest prime greater than 10" picks out 11 by failing at 12, 13, …). The y inside "there is a y…" is pinned down by reality, not by the sentence — like "somebody stole the necklace," true and useless to a detective.

What finally clicked — the book-textual route: (Passage 1, p. 20) f is Arithmetic iff the relation f(x) = y is — and that relation's places are x AND y, an (n+1)-place relation. (Passage 2, p. 19) an n-place relation is expressed by F(v1,…,vn), whose free variables receive the n numerals by substitution — and only free variables can receive a substitution; a bound variable is sealed by its quantifier. (Passage 3, p. 20) Smullyan draws the consequence himself: "…F(v1,…,vn,v_{n+1}) such that for all x1,…,xn and y…" — ranging over wrong y's, where the iff forces falsity. Held against the book's test, the ∃z formula cannot even be administered the test: there is no free slot to insert ȳ into.

The user's own final formulation (the session's takeaway principle):

The free variables are exactly the letters the condition itself mentions; everything else is invented scaffolding and gets bound — one quantifier per invented name, none for the condition's own names.

"f(g(x)) = z" mentions x and z; it does not mention y — y was our invention. Hence ∃y right, ∃z wrong.

Where the habit came from (diagnosis): Exercise 3's target was a set, so "quantify everything but x" was correct there — and became a template, over-applied to Exercise 4's targets, which are functions (graphs: 2 or 3 columns). Read the target's arity off the problem statement before writing anything: set → 1 blank; one-input function → 2; two-input function → 3.

The certified answers

f(g(x)) = z:      H (x, z)    = ∃t( G(x, t) ∧ F(t, z) )        [t := g(x); z := f(t)]
g(f(x), y) = z:   H1(x, y, z) = ∃t( F(x, t) ∧ G(t, y, z) )     [t := f(x); z := g(t, y)]
g(x, f(y)) = z:   H2(x, y, z) = ∃t( F(y, t) ∧ G(x, t, z) )     [t := f(y); z := g(x, t)]
f(g(x, y)) = z:   H3(x, y, z) = ∃t( G(x, y, t) ∧ F(t, z) )     [t := g(x, y); z := f(t)]

Trace check for H (g(x) = x+1, f(w) = w²): H(2,9) — witness t = 3 — true ✓; H(2,10) — no t with t = 3 and t² = 10 — false ✓. The second check is the one the ∃z version couldn't fail. Verification pattern each time: the witness t is forced to equal the inner function's value (the graph formula expresses exactly the graph); conversely that value always witnesses. Fresh-variable discipline (Bug 3, attempt three): the temporary must not reuse an input's name — a collision silently changed g(f(x), y) into the diagonal g(f(x), x).


Part X — Exercise 5: the superlative (delivered on request)

Task: A infinite and Arithmetic; R(x,y): "x is the smallest element of A greater than y." Show R Arithmetic.

By the takeaway principle: the condition mentions x and y — both stay free; "smallest" is a claim about every competitor, so ∀ makes its constructive debut, over one invented candidate-name z. Unfold: (1) x ∈ A; (2) x > y; (3) every member of A greater than y is at least x.

R(x, y):  A(x)  ∧  y < x  ∧  ∀z( (A(z) ∧ y < z) ⊃ x ≤ z )

where y < x abbreviates (y ≤ x) ∧ ~(y = x) (July 19 glossary). The ⊃-guard under ∀ is how L_E says "every z such that…" — unqualified z's satisfy the conditional vacuously (same ⊃-with-∀ / ∧-with-∃ asymmetry as the bounded quantifiers). Rejection test, A = primes: R(11, 8) true; R(13, 8) false — conjunct 3 dies at z = 11.

Where "A is infinite" is spent: not in the formula or verification — the formula expresses R regardless. Infinitude guarantees every y has some x with R(x,y): R is the graph of a total function ("next element of A after y"), which is what it's for later. Small-a bonus as always: only ∧, ~, ∀, ⊃, ≤, = added.


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

Confusion raised Resolution
Relation = members bound inseparably, not a collection? Half right: a relation IS a collection — of tuples. The inseparability lives inside each element; asking if 3 alone ∈ Divides is a type error. Set = 1-place relation.
What is a tuple, mathematically? Finite ordered list; order matters, repetition matters, fixed length. Governed by ONE law: componentwise equality. Relation = set of tuples = table of rows.
Doesn't {{a},{a,b}} smuggle in "order" as a new primitive? Order = losslessness of the pairing = the identity law, and Kuratowski's version is a THEOREM from ∈, extensionality, pairing. Postulated vs. proved is the entire difference; definitions are conservative abbreviations.
How does unordered set theory FAIL the identity law? The naive encoding: (2,3) ↦ {2,3} = {3,2} ↤ (3,2) — two hand-ins, one object, information destroyed. That one line IS "sets are unordered." Nesting fixes it by structural asymmetry: a inhabits both members, b only one.
"(a,b) ≠ (b,a) means a can't equal b" No — (2,2) is a fine pair. Order means the positions are distinguishable: WHEN a ≠ b, (a,b) ≠ (b,a). Always state the biconditional; the swap case is a corollary.
What are set theory's primitives? One non-logical symbol: ∈. Plus logic (variables, =, connectives, quantifiers) and axioms (extensionality, pairing). Everything else is defined — macro-expandable abbreviation.
Why assume set-theoretic primitives for Gödel at all? Don't have to — the metatheory takes tuples as given (with their law). But INSIDE L_E nothing may be posited: §4 must encode sequences as numbers from bare primitives. The Kuratowski game was the dress rehearsal.
Arithmetic vs. arithmetic — why care? Capital A: E allowed; small a: E-free. Gödel: x^y = z definable from +,· — so they coincide, and incompleteness hits plus-and-times languages (PA). Boundary razor thin: Presburger (+ only) decidable; add · and it's over.
How is a FUNCTION Arithmetic when formulas express relations? Via its graph: f Arithmetic iff the (n+1)-place relation f(x1,…,xn) = y is. The formula recognizes correct tuples and REJECTS wrong ones — for all y, including wrong y.
Property? Condition? Property ↔ its set (n has P iff n ∈ set). Condition = umbrella for n-place relation, any n ≥ 1. Vocabulary only.
"Any number y" in the primes attempt English "any" flips ∀/∃. Wanted: ∃y(x = z·y) = "z divides x" — reuse the divides formula.
Primes: "no divisor but 1" x divides x — must permit BOTH 1 and x. And ~(0'' ≥ x) means x ≥ 3: evicted the prime 2 (expressed the odd primes). Fix: 0'' ≤ x.
How to say "y belongs to A" in L_E? No ∈ in L_E. Membership is asserted by the expressing formula itself: plug y into A's free slot (renaming bound variables to avoid capture). The formula IS the membership test.
"Expressibility flows through the tuple, like a chain rule" No conservation law — it's CLOSURE under logical operations, and the proof is the explicit gluing. Exhibit the formula, verify the biconditional; "we can always construct" is not a construction.
"x must be expressible" Category error: numbers aren't expressible; sets/relations are. Formulas express sets; numbers belong to them.
F'(F(x,y), z) Formulas don't nest: argument slots take number-denoting terms, not statements. Flatten with a fresh temporary: one conjunct per step, ∃ on the temporary only.
Why is ∃y∃z(F'(x,y) ∧ F(y,z)) wrong? "Isn't that the normal requirement?" The formula's reading is CORRECT and TRUE — "x has an output" — but true-of-every-x, same answer pattern as x = x: an assertion, not a definition. A phrase defines only through its ability to reject, and ∃z removed the slot where wrong answers get rejected.
"The y is pinned down inside ∃" Pinned down by reality, not by the sentence — "somebody stole the necklace" names no one. Whatever ∃ finds, it uses, discards, and reports one bit. Identification needs the open slot.
Where does the BOOK say two free variables? P.20: f Arithmetic iff relation f(x) = y is (places: x AND y); p.19: n-place relation expressed by F(v1,…,vn), numerals substituted into FREE variables — bound ones can't receive substitution; p.20 "Thus…for all x and y" — the test ranges over wrong y's, forcing falsity there. The ∃z formula has no slot to even administer the test.
The takeaway principle (user's own words) Free variables = the letters the condition itself mentions; bound = invented scaffolding. One ∃ per invented name, none for the condition's names. Set → 1 blank; 1-input function → 2; 2-input function → 3.
Where did the ∃z habit come from? Exercise 3's target was a set — "quantify all but x" was right THERE — and the template got over-applied to function targets. Read the target's arity before writing.
Fresh temporaries Attempt three reused y as temporary and second input: silently turned g(f(x), y) into the diagonal g(f(x), x). The p.19 renaming paragraph, live.
"Smallest" in Exercise 5 A superlative = a ∀ claim about all competitors, guarded by ⊃: ∀z((A(z) ∧ y < z) ⊃ x ≤ z). Non-candidates pass vacuously. Infinitude of A isn't used by the formula — it makes R the graph of a total function, for later.

Part XII — Self-Test

Answer before peeking; each was worked (or stumbled through) in the session.

  1. A friend says: "a relation can't be a set, because sets don't have order." Correct them in two sentences.
  2. State the identity law for pairs, and show exactly where the naive encoding (a,b) := {a,b} violates it.
  3. Prove the hard direction of the identity law for {{a},{a,b}} in the case a ≠ b.
  4. Why is "the identity law holds for Kuratowski pairs" not a new assumption of set theory? Name the two statuses a governing law can have.
  5. Define Arithmetic and arithmetic. What is Gödel's foreshadowed non-trivial result, and what does it do to the distinction?
  6. Why does the capital/small-a bookkeeping matter for Peano Arithmetic specifically? And which one-symbol change turns Presburger's complete theory into an incompletable one?
  7. By the book's definition, what must a formula do to show f(x) = x² is Arithmetic — at (3, 9), and at (3, 10)?
  8. Write the arithmetic formula for "x divides y," and the full formula for the primes. Which three bugs did the primes formula have to survive?
  9. L_E has no ∈. How do you say "y belongs to A" inside a construction?
  10. Build the formula for f(g(x)) = z from graph formulas G (for g) and F (for f). Which variable is bound and why that one?
  11. ∃y∃z(G(x,y) ∧ F(y,z)) is a true statement about every x. Give two independent reasons it fails to show f(g(x)) Arithmetic — one about answer patterns, one about the book's own test.
  12. State the takeaway principle relating free variables to the condition being defined, and give the blank-counts for: a set; a one-input function; a two-input function.
  13. Write the Exercise 5 formula for "x is the smallest element of A greater than y." Why ⊃ (not ∧) under the ∀? Where is A's infinitude spent?

Answers

  1. A relation is a set — its elements are ordered tuples, not single numbers. The order lives inside each element (the tuple), so the collection itself needs no order; asking whether 3 alone belongs to Divides is a type error, but (3,12) either belongs or doesn't.
  2. (a,b) = (c,d) iff a = c and b = d. Naive: {2,3} = {3,2}, so the codes of (2,3) and (3,2) are equal while 2 = 3 fails — two different hand-ins collide; the encoding is lossy.
  3. a ≠ b: the code has two members, singleton {a} and doubleton {a,b}. {c} can't equal the doubleton (size), and if {c,d} = {a} then c = d = a collapses the right side to one member — contradiction. So {c} = {a} (c = a), then {a,d} = {a,b} with b ≠ a gives b = d.
  4. It's a THEOREM, proved from extensionality and pairing — not an axiom. A governing law is either postulated (new primitive content) or proved (definition, conservative: no new facts about ∈ become provable; only notation grows).
  5. Arithmetic: expressed by some L_E formula (E allowed). arithmetic: by an E-free formula. Gödel: x^y = z is definable from + and · alone — so every Arithmetic relation is arithmetic and the distinction collapses.
  6. PA's language has no E — if the coding needed E, incompleteness would miss the systems people care about; Gödel's result makes it hit them. Adding · to + (Presburger → full arithmetic) crosses from complete/decidable to incomplete/undecidable.
  7. Exhibit F(v1,v2) with: for ALL x, y — F(x̄,ȳ) true iff x² = y. So F(3̄,9̄) true and F(3̄,1̄0̄) FALSE — the rejection at wrong pairs is what pins the function down.
  8. d(x,y): ∃z(y = x·z). Primes: 0'' ≤ x ∧ ~∃z(∃y(x = y·z) ∧ ~(z = 0') ∧ ~(z = x)). Bugs survived: the "any" trap (∀y for ∃y); forgetting the divisor x itself; the boundary ~(0'' ≥ x) = "x ≥ 3," which evicted 2.
  9. Plug y into the free slot of A's expressing formula (renaming A's bound variables first if they'd collide). A(ȳ) true iff y ∈ A — the formula is the membership test; there is nothing else membership could mean in L_E.
  10. H(x,z) = ∃t(G(x,t) ∧ F(t,z)). Bound: t only — the invented name for the intermediate value g(x). x and z are the condition's own names ("f(g(x)) = z" mentions them) and must stay free.
  11. (a) Since f, g are total it's true at every x — same answer pattern as x = x, so it expresses ℕ; a formula that can never say no defines nothing. (b) The book's test requires forming F(x̄, ȳ) for all y including wrong ones; with z bound there is no free slot to substitute ȳ into — the test can't even be administered.
  12. Free variables = exactly the letters the condition itself mentions; invented scaffolding gets one quantifier each. Set → 1 free; one-input function's graph → 2; two-input function's graph → 3.
  13. A(x) ∧ y < x ∧ ∀z((A(z) ∧ y < z) ⊃ x ≤ z). With ∧ the formula would demand every z be in A and exceed y — false always; ⊃ lets unqualified z's pass vacuously (bounded-quantifier asymmetry). Infinitude isn't used in expressing R — it guarantees every y has a successor-in-A, making R the graph of a total function for later use.

Part XIII — What's ahead in Smullyan, and the state of play

Position: Chapter II §3 complete — Arithmetic/arithmetic sets, relations, functions, properties, conditions, and Exercises 2–5 all solved (2–4 by hand, 5 delivered and verified).

Next: §4, Concatenation to the Base b — the section Part IV was secretly preparing for. The metatheory could posit tuples freely; L_E cannot, so finite sequences of numbers must now be encoded as single numbers, losslessly, with the decoding relations Arithmetic. This is the beginning of Gödel numbering — where the July 19 session's 13-symbol economy pays out, and where the encode/decode discipline of this session (identity law = losslessness; a code is good iff wrong readings get rejected) becomes the working standard. Destination unchanged: Tarski's theorem — the set of Gödel numbers of true sentences is NOT Arithmetic; truth is a set no formula can carve.

Standing connections: "expresses" (July 19) got its workout — five constructions, each ending with the exhibit-and-verify receipt. The closure toolkit is now personal equipment: gluing with ∧, membership via expressing formulas, temporaries with ∃, superlatives with ∀ + ⊃-guard, strictness via ≤ ∧ ~=. The Presburger boundary extends July 19's S < + < × hierarchy. And the debt register is open: Gödel's E-elimination (x^y = z from +,·) is owed by a later chapter — the third and hardest member of the ≤/pairs/E trilogy.

The method, continued: the session's engine was again the refusal to let sentences pass — how does unordered set theory fail the law? where does the BOOK say two free variables? The decisive lesson was epistemic: four intuitive explanations of the ∃z error bounced, and what finally landed was the textual receipt — the definition's own substitution mechanics. When intuition and instruction deadlock, go to the letter of the definition and administer its test by hand. A formula defines only through its ability to reject; the same is true of an understanding.


End of session review · Smullyan, "Gödel's Incompleteness Theorems," Chapter II §3 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), Godel-Incompleteness-Session-2026-07-19.md (Chapter II §1–§2, language and truth) · Next: Chapter II §4, Concatenation to the Base b — Gödel numbering begins.