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 / 篇目
- How to use this document
- Part I — Set vs. Relation: the inseparability lives inside the tuple
- Part II — Tuples and the identity law
- Part III — The Kuratowski digression: order without a new primitive
- Part IV — Metatheory vs. object language: when primitives matter
- Part V — Arithmetic vs. arithmetic
- Part VI — Functions enter through their graphs; properties and conditions
- Part VII — Exercise 2: divides and primes
- Part VIII — Exercise 3: f⁻¹(A), and how to say "belongs to"
- Part IX — Exercise 4 and the ∃z saga (the session's main battle)
- Part X — Exercise 5: the superlative (delivered on request)
- 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 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:
- Order matters: (2,3) ≠ (3,2), but {2,3} = {3,2}.
- Repetition matters: (1,1) is a real pair; {1,1} = {1}.
- 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:
- 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.
- 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:
- 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.)
- 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.
- 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.
- A friend says: "a relation can't be a set, because sets don't have order." Correct them in two sentences.
- State the identity law for pairs, and show exactly where the naive encoding (a,b) := {a,b} violates it.
- Prove the hard direction of the identity law for {{a},{a,b}} in the case a ≠ b.
- 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.
- Define Arithmetic and arithmetic. What is Gödel's foreshadowed non-trivial result, and what does it do to the distinction?
- 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?
- By the book's definition, what must a formula do to show f(x) = x² is Arithmetic — at (3, 9), and at (3, 10)?
- 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?
- L_E has no ∈. How do you say "y belongs to A" inside a construction?
- 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?
- ∃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.
- 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.
- 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
- 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.
- (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.
- 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.
- 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).
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- (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.
- 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.
- 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.
本文由 AI 从英文原文翻译。请以原文为准。
In this note / 篇目
- 如何使用本文
- 第一部分——集合与关系:不可分离性位于元组内部
- 第二部分——元组与同一律
- 第三部分——库拉托夫斯基的岔题:不增加原始项而得到次序
- 第四部分——元理论与对象语言:原始项何时重要
- 第五部分——大写Arithmetic与小写arithmetic
- 第六部分——函数通过图进入;性质与条件
- 第七部分——练习2:整除与素数
- 第八部分——练习3:f⁻¹(A),以及如何说“属于”
- 第九部分——练习4与∃z历险:本次学习的主要战斗
- 第十部分——练习5:最高级,应要求给出
- 第十一部分——区分清单:本次学习的每处迷雾,各用一行澄清
- 第十二部分——自测
- 第十三部分——Smullyan后面会讲什么,以及当前局面
2026年7月20日学习记录 · Smullyan《哥德尔不完备定理》第二章§3,大写Arithmetic与小写arithmetic的集合和关系,练习2–5完整解答 · 2026年7月15、17、19日学习记录的续篇
如何使用本文
本文依理解实际建立的次序展开,每部分预设前面的部分。复习时:第一次依次读第一至十部分;之后单看区分清单,第十一部分就能全面温习,自测,第十二部分则检验是否掌握。本次破坏性最强的错误,即在图公式中用∃约束输出变量,连续三轮,隔离在第九部分;如果再觉得公式的自由变量数目可以商量,直接去那里。
第一部分——集合与关系:不可分离性位于元组内部
带入本次学习的怀疑: 关系不同于集合,“不是个体成员的汇集”,而是把成员不可分地联结起来的东西。一半对,而错的另一半很重要。
外延观点,Smullyan与现代数学的观点:关系就是集合,只不过其元素是有序元组,而非单个数。不可分离性位于每个元素内部:元素是元组(3,12),问单独的3是否属于整除关系,是类型错误,就像问椅子的左半边是不是家具。
层级:
数的集合 元素:单个数 偶数 = {0, 2, 4, …}
二元关系 元素:有序对 整除 = {(1,1), (2,4), (3,12), …}
三元关系 元素:有序三元组 加法 = {(x,y,z) : x+y=z}
n元关系 元素:n元组
(3,12)∈整除关系,但(12,3)∉整除关系,次序有实质作用。统一在于:集合是退化情形,即一元关系,因此对F(v1,…,vn)只需定义一次“表达”,集合情形就是n=1。
留下印象的心智图景: 二元关系是一张有无限多行的两列表。关系就是表,即行的总体,而非数之间的黏合剂。
第二部分——元组与同一律
n元组(a1,…,an)是有限有序列表。与集合的三个对比:
- 次序重要: (2,3)≠(3,2),但{2,3}={3,2}。
- 重复重要: (1,1)是真正的数对;{1,1}={1}。
- 长度固定: 数对与三元组是不同种类的对象。
支配元组的唯一规律,也就是“有序”的全部工作说明:
(a1,…,an)=(b1,…,bn),当且仅当a1=b1且…且an=bn。
相同条目,相同位置。数学中的任何地方都不曾使用元组的其他性质。因此“关系=元组的集合”,而数据库表就是准确的图景:每行是元组,表是关系。
第三部分——库拉托夫斯基的岔题:不增加原始项而得到次序
提出的挑战: 在无序集合论内部定义有序对,难道不是偷偷引入一个名叫“次序”的新原始项?
步骤1,“记住次序”要求什么。 形成数对是一种编码:提交带有角色标签的两个东西,拿回一个对象。对象恰好在编码无损时记住次序,即不同的两次提交从不碰撞。把无损性写出来,恰好就是同一律。它不是次序的附带性质,而就是次序的重述。
步骤2,看裸集合如何失败。 尝试朴素编码(a,b) := {a,b}。那么“2在先,3在后”给出{2,3},“3在先,2在后”给出{3,2},相同集合。两次不同提交,相同对象:规律被违反,“谁在先”的信息在收集那一刻毁掉。这一行,{2,3}={3,2},就是“集合无序”的精确兑现。 重复也消失:(1,1)↦{1,1}={1}。
步骤3,嵌套编码通过。 定义(a,b) := {{a},{a,b}}。现在(2,3)={{2},{2,3}},(3,2)={{3},{2,3}},是不同集合,因为{2}≠{3}。眼前每个集合仍无序,{{a},{a,b}}={{a,b},{a}},没问题;编码不靠位置,而靠赋予输入结构上不同的角色恢复次序:a是两个成员的共同成员,b在≠a时只是其中一个的成员。“是两个成员共同的成员”纯粹用∈就能陈述。
步骤4,同一律的证明,⇐是替换,⇒分情况:
- 情形a=b: 编码坍缩为{{a}},一个成员。所以{{c},{c,d}}有一个成员,迫使{c}={c,d}={a},因此c=d=a。✓
- 情形a≠b: 编码有两个成员,单元集{a}与二元集{a,b}。右侧的单元集不能是{c,d};若c≠d,大小不对;若c=d,右侧坍缩为一个成员,矛盾。所以{c}={a},c=a;于是{a,d}={a,b},而b≠a迫使b=d。✓
只用∈可定义的解码器:first(x)=属于x每个成员的唯一u;second(x)=若x有一个成员,则为first(x),否则为二元集中而不在单元集中的u。
步骤5,为什么没有偷渡原始项。 集合论的原始项:一个非逻辑符号∈,加逻辑装置,变量、=、~、∧、∨、→、∀、∃,以及公理,外延性:集合相等当且仅当成员相同;配对公理。定义是缩写,“(a,b)”宏展开为∈与逻辑中的公式。对比替代方式:增加原始符号pair(a,b),以同一律作为新公理,即被假定的内容。库拉托夫斯基把同一规律作为定理得到。假定与证明,全部差别。定义是保守的:它们永远不能让关于∈的新事实变得可证,只是记号增长了。
同一动作的三部曲,现在已经看过三遍:
只从+得到≤: ∃v3(v1 + v3 = v2) 显然 (第19页括号内评注)
只从∈得到数对: {{a},{a,b}} 一页 (这次岔题)
只从+与·得到E: x^y = z为小写算术的 困难 (哥德尔的非平凡结果,后面章节待完成)
在更贫乏的语言中提出定义;证明它的行为恰好符合更丰富概念的要求。证明才赚得“没有新原始项”。当觉得有东西被偷渡,问:这个概念的规格是什么,它被证明了,还是被假定了?
第四部分——元理论与对象语言:原始项何时重要
令人泄气但被认真对待的问题: 为什么要把元组奠基在集合论原始项中,难道把元组/关系当作给定还不够?够的。 两个项目被混同了:
- 项目1,Smullyan的书: 在普通非形式数学,即元理论中工作,把集合、元组、关系、函数当作给定。完全严谨,只要知道所假定东西的支配规律,对元组来说是同一律。不完备定理没有任何部分依赖元组“由什么做成”。
- 项目2,基础记账: 把一切归约到最小基础。有趣,可选,不是前提。
但这项练习没有浪费,它是彩排。 形式语言L_E没有那么宽松:它恰好只有0 ' + · E ≤ =与逻辑,而且能谈论的只有自然数。但哥德尔证明需要算术谈论序列,最终是公式,包括正在构建的那个句子本身。因此相同的游戏,即“理论原生地缺少X;只用其原始项无损编码X”,必须在更困难的地面上再玩一次:
在集合论中:把集合对编码为一个集合 容易,库拉托夫斯基
在算术中: 把有限的数序列 真正的工作,§4、哥德尔编号
编码为单个数
两次成功标准相同:无损,不同序列、不同编码,而且解码关系可由原始项表达。在元理论外部,我们可以自由设定;在对象语言内部,每个概念都必须从原始项中赚得,而赚得的过程就是证明。
第五部分——大写Arithmetic与小写arithmetic
定义: 若集合/关系被L_E的某个公式表达,允许E,就称为Arithmetic,大写A;若被不含E的公式表达,则称为arithmetic,小写a,形容词重音为arith-MET-ic,见脚注。小写a的俱乐部更难进入;每个小写arithmetic关系显然也是大写Arithmetic。
预告的非平凡结果,哥德尔的结果: x^y=z本身只用+与·即可定义。一旦证明,任何使用E的公式都能改写为不含E,因此Arithmetic=arithmetic,区分坍缩。在此之前,Smullyan使用方便的大写A概念,把代价留到后面支付。
为何重要:
- 它极大加强不完备性。 皮亚诺算术语言只有'、+、·,没有E。若编码机器确实需要E,不完备性只会打中更丰富的语言,还能寄希望于只有加与乘的算术是完备的。哥德尔的可定义性结果摧毁了这种希望。
- 边界极薄,因此原始项记账不是迂腐: 只有+,Presburger,完备、可判定;加上·,不完备、不可判定。一个符号隔开温顺理论与不可完备化的理论。扩展7月19日的层级:S < + < ×。
第六部分——函数通过图进入;性质与条件
问题: 公式只能表达关系,只有这一种“表达”。那么函数如何能是Arithmetic?
动作:看图,而非规则。 函数f(x1,…,xn)是Arithmetic,当且仅当(n+1)元关系f(x1,…,xn)=y是Arithmetic,多一个位置留给输出。书中自己的陈述:f是Arithmetic,当且仅当存在公式F(v1,…,vn,v_{n+1}),使对所有x1,…,xn和y:F(x̄1,…,x̄n,ȳ)真,当且仅当f(x1,…,xn)=y。
关于这句话的两条醒目注释:
- “对所有…和y”包括错误的y。 公式必须恰好在图上为真,在其他所有地方为假。它不计算输出,而是识别正确的输入—输出元组,并拒绝冒充者;拒绝恰恰是一切信息所在。
- 例子:f(x)=x²的图为{(0,0),(1,1),(2,4),(3,9),…},由v2=v1·v1表达。F(3̄,9̄)真;F(3̄,1̄0̄)假。
词汇段,纯记账:性质P是Arithmetic,当且仅当具有P的数的集合是Arithmetic,性质↔集合,可互换,“是偶数”与偶数集合;条件=“n元关系,任意n≥1”的总称。§3之后,集合、性质、关系、函数、条件全部归约到一个想法:元组的集合,可能被公式表达。
第七部分——练习2:整除与素数
第一小题,“x整除y”是小写arithmetic。 第一次就解决:
d(x, y): ∃z(y = x·z)
边界检查:每个x都整除0,z=0✓;0只整除0,0·z=0✓。放在工作台上供复用。
第二小题,素数。两次尝试中发现并修正三个错误:
- “any”的陷阱: 为“z乘以某个y得到x”写了∀y(x=y·z)。英语“any”在∀与∃之间摇摆;原意应为∃y(x=z·y),恰好就是d(z,x)。这就是书先安排整除的原因,第二小题需要它作部件。
- 忘了因子x自身: “除1之外没有z整除x”被每个x≥2反驳,因为x整除x。素性允许两个因子:每个因子都是1或x。
- 边界差一: ~(0''≥x)说x>2,即x≥3,赶走了唯一偶素数2。公式表达的是奇素数。修正:0''≤x。另外,L_E只有≤,而1的数码是0'。
认证后的公式:
P(x): 0'' ≤ x ∧ ~∃z( ∃y(x = y·z) ∧ ~(z = 0') ∧ ~(z = x) )
测试组:0失败,2整除0且2∉{1,0};1失败,大小条件;2通过;7通过。没有E,素数集合是小写a的arithmetic。
第八部分——练习3:f⁻¹(A),以及如何说“属于”
任务: 若A与f是Arithmetic,则f⁻¹(A)={n : f(n)∈A}也是;小写arithmetic同理。
初次尝试的失败模式,挥手略过: “既然整个元组可表达,一部分也可表达,另一部分必然也可表达,像链式法则。”诊断:可表达性不是依守恒在元组中流动的物质,而是对逻辑操作的封闭性,证明就是明确的拼接。这整个类型的标准是:要证明某物为Arithmetic,就展示公式,并验证双条件关系。 “我们总能构造”是主张,不是构造。也指出:“x必须可表达”是范畴错误,数不是可表达的,集合与关系才是。
关键概念突破:L_E没有成员符号。 集合不存在于L_E内部。“y属于A”由表达公式自身断言:A(n̄)真,当且仅当n∈A,因此公式就是成员测试,“属于”=“通过测试”。要说“v3是偶数”,取偶数公式∃v2(v1=0''·v2),把v3放进其自由槽位;若约束变量会冲突,先改名,第19页“算术等价”的段落恰是为许可这种拼接而存在。f同样如此:没有函数符号,只有图公式。
构造,用户通过一串当且仅当推导,是真正的证明:
G(x): ∃y( F(x, y) ∧ A(y) ) 正式写法:∃v2(F(v1,v2) ∧ A(v2))
验证:正向,一个见证y满足f(x)=y∈A;反向,y=f(x)是见证,这里使用f的全定义性,每个x都有一个输出可作见证。小写a的额外收获:构造只加∃和∧,从未加E,因此同一证明适用于“arithmetic”。
在此提出的元数原则:自由变量数=所表达对象的元数。 未量化的F(x,y)∧A(y)有两个自由槽位,是合格的二元关系,但目标是集合;∃y把元数从2降为1。自由变量不是“未定义”,而是输入槽位。
第九部分——练习4与∃z历险:本次学习的主要战斗
练习: 复合。给定F表达f(x)=y,G表达g(x,y)=z,或第一小题中g为一元函数,证明f(g(x))、g(f(x),y)、g(x,f(y))、f(g(x,y))是Arithmetic。
错误1,范畴错误:公式不能嵌套
第一次尝试写了F'(F(x,y),z),把公式塞进自变量槽位。自变量槽位接收项,即指称数的东西;F(x,y)一旦实例化,是陈述。“(3<5)是偶数吗?”通不过类型检查。嵌套函数调用的习惯不能照搬:L_E中没有“g(x)”这个项可以传下去,g只通过其图公式存在,而图公式断言,不计算。
普遍修复:用全新临时变量展平,即编译器的一道处理。f(g(x))=z展开为“存在t,使g(x)=t且f(t)=z”。每步一个合取项,∃只加在临时变量上。练习3的构造一直就是模板。
错误2,约束输出:三轮、五种解释、一个解决
连续三次尝试都以∃y(∃z(…))结束,把输出槽位与临时变量一起封闭,只留下x自由。依次尝试的解释:(i)元数原则;(ii)计算公式实际表达什么,由于f、g是全函数,∃y∃z(F'(x,y)∧F(y,z))对每个x为真:它表达ℕ,与x=x有相同的回答模式,所有关于值的信息被摧毁;(iii)公式作为回答机器,自由变量是旋钮,∃从面板上拆掉一个旋钮,∃z之后,“2处的值是10吗?”变成无法提出的问题,永远不能说不的公式什么也固定不了,∃y(y=x·x)与∃y(y=x·x·x)变得无法区分,平方与立方成了相同的恒真公式;(iv)断言与定义,“每个人都有母亲”为真,却没有定义任何人的母亲是谁;“y是x的母亲”,开放形式,才定义关系,因为短语只有通过拒绝的能力才进行定义,“大于10的最小素数”通过在12、13、…处失败而选出11。“存在一个y…”中的y由现实固定,而非由句子固定,就像“有人偷了项链”,为真,却对侦探无用。
终于理解的方式,回到原书文本: 第一段,第20页,f是Arithmetic,当且仅当关系f(x)=y是Arithmetic,而该关系的位置是x与y,是(n+1)元关系。第二段,第19页,n元关系由F(v1,…,vn)表达,其自由变量通过代入接收n个数码,而且只有自由变量能接收代入;约束变量被量词封住。第三段,第20页,Smullyan自己推出后果:“…F(v1,…,vn,v_{n+1})使得对所有x1,…,xn和y…”,包括错误y,在这些位置,当且仅当强迫为假。对照书中的测试,∃z公式甚至无法接受测试:没有自由槽位可以放入ȳ。
用户最终自己的表述,本次学习带走的原则:
自由变量恰好就是条件本身提到的字母;其他一切都是发明的支架,要被约束。每个发明的名字配一个量词,条件自身的名字一个也不配。
“f(g(x))=z”提到x、z;没有提到y,y是我们发明的。因此∃y对,∃z错。
习惯从哪里来,诊断: 练习3的目标是集合,因此“除了x全都量化”在那里正确,随后成了模板,被过度应用于练习4的目标,而那些是函数,即图,两列或三列。写任何东西之前,先从题目陈述读出目标的元数:集合→1个空位;单输入函数→2个;双输入函数→3个。
认证后的答案
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)]
对H的追踪检查,g(x)=x+1,f(w)=w²:H(2,9),见证t=3,真✓;H(2,10),没有t既满足t=3又满足t²=10,假✓。第二项检查正是∃z版本无法失败的那一项。每次的验证模式:见证t被迫等于内部函数的值,图公式恰好表达图;反之,该值总是见证。新变量纪律,错误3,第三次尝试:临时变量不能复用输入的名字,一次冲突悄悄把g(f(x),y)变成了对角式g(f(x),x)。
第十部分——练习5:最高级,应要求给出
任务: A无限且Arithmetic;R(x,y):“x是A中大于y的最小元素。”证明R是Arithmetic。
依据带走的原则:条件提到x、y,两者都保持自由;“最小”是关于每个竞争者的主张,因此∀首次建设性地登场,作用于一个发明的候选者名字z。展开:(1)x∈A;(2)x>y;(3)A中每个大于y的成员都至少为x。
R(x, y): A(x) ∧ y < x ∧ ∀z( (A(z) ∧ y < z) ⊃ x ≤ z )
其中y<x是(y≤x)∧~(y=x)的缩写,见7月19日术语表。∀下面的⊃限定条件,是L_E说“每个满足…的z”的方式;不合资格的z使条件句空真,与有界量词中∀配⊃、∃配∧的不对称性相同。拒绝测试,A=素数:R(11,8)真;R(13,8)假,第三个合取项在z=11处失败。
“A无限”用在哪里: 不在公式或验证中,公式无论如何都表达R。无限性保证每个y都有某个x满足R(x,y):R是全函数的图,“A中y之后的下一个元素”,这就是它后面的用途。小写a的额外收获如常:只增加∧、~、∀、⊃、≤、=。
第十一部分——区分清单:本次学习的每处迷雾,各用一行澄清
| 提出的困惑 | 解答 |
|---|---|
| 关系=成员不可分地绑定,而不是汇集? | 一半对:关系就是汇集,元组的汇集。不可分离性在每个元素内部;问单独3是否∈整除关系,是类型错误。集合=一元关系。 |
| 数学上什么是元组? | 有限有序列表;次序重要、重复重要、长度固定。由一条规律支配,逐分量相等。关系=元组集合=行组成的表。 |
| {{a},{a,b}}难道没有把“次序”作为新原始项偷渡进来? | 次序=配对的无损性=同一律,而库拉托夫斯基版本是从∈、外延性、配对公理得出的定理。假定与证明是全部区别;定义是保守的缩写。 |
| 无序集合论如何不满足同一律? | 朴素编码:(2,3)↦{2,3}={3,2}↤(3,2),两次提交,一个对象,信息摧毁。这一行就是“集合无序”。嵌套通过结构不对称修复:a位于两个成员中,b只在一个中。 |
| “(a,b)≠(b,a)意味着a不能等于b” | 不对,(2,2)是合格的数对。次序意味着位置可区分:当a≠b时,(a,b)≠(b,a)。总要陈述双条件关系,交换情形是推论。 |
| 集合论的原始项是什么? | 一个非逻辑符号:∈。加逻辑,变量、=、联结词、量词,与公理,外延性、配对。其他一切通过定义,是可宏展开的缩写。 |
| 为什么哥德尔需要假定集合论原始项? | 不需要,元理论把元组及其规律当作给定。但在L_E内部不能任意设定:§4必须从裸原始项出发,把序列编码为数。库拉托夫斯基游戏是彩排。 |
| Arithmetic与arithmetic,为什么要关心? | 大写A允许E;小写a不含E。哥德尔:x^y=z可从+、·定义,因此两者重合,不完备性打中加与乘语言,PA。边界极薄:Presburger,只有+,可判定;加入·就结束。 |
| 公式表达关系时,函数怎么是Arithmetic? | 通过其图:f是Arithmetic,当且仅当(n+1)元关系f(x1,…,xn)=y是Arithmetic。公式识别正确元组,并拒绝错误者,对所有y,包括错误y。 |
| 性质?条件? | 性质↔其集合,n有P当且仅当n∈集合。条件是n元关系的总称,任意n≥1。只是词汇。 |
| 素数尝试中的“任何数y” | 英语“any”在∀/∃之间摇摆。想要的是∃y(x=z·y)=“z整除x”,复用整除公式。 |
| 素数:“除了1没有因子” | x整除x,必须同时允许1与x。而~(0''≥x)意味着x≥3,赶走了素数2,表达了奇素数。修正:0''≤x。 |
| 在L_E中如何说“y属于A”? | L_E中没有∈。成员关系由表达公式自身断言:把y放进A的自由槽位,给约束变量改名以避免捕获。公式就是成员测试。 |
| “可表达性像链式法则一样在元组中流动” | 没有守恒律,而是对逻辑操作的封闭性,证明就是明确拼接。展示公式,验证双条件关系;“我们总能构造”不是构造。 |
| “x必须可表达” | 范畴错误:数不是可表达的,集合/关系才是。公式表达集合;数属于集合。 |
| F'(F(x,y),z) | 公式不能嵌套:自变量槽位接收指称数的项,不接收陈述。用全新临时变量展平:每步一个合取项,只对临时变量用∃。 |
| 为什么∃y∃z(F'(x,y)∧F(y,z))错?“这不是正常要求吗?” | 公式读法正确且为真,“x有输出”,但对每个x为真,与x=x回答模式相同,是断言而非定义。短语只有通过拒绝能力才定义,而∃z移除了拒绝错误答案的槽位。 |
| “y在∃内部被固定了” | 被现实固定,而非被句子固定,“有人偷了项链”没指名任何人。∃找到什么,就使用、丢弃,并报告一比特信息。识别需要开放槽位。 |
| 书中哪里说两个自由变量? | 第20页:f是Arithmetic,当且仅当关系f(x)=y是,其位置是x与y;第19页:n元关系由F(v1,…,vn)表达,数码代入自由变量,约束变量不能接收代入;第20页“因此…对所有x和y”,测试包含错误y,迫使那里为假。∃z公式甚至没有槽位来接受测试。 |
| 带走的原则,用户自己的话 | 自由变量=条件本身提到的字母;约束变量=发明的支架。每个发明的名字一个∃,条件的名字一个也不配。集合→1空位;单输入函数→2;双输入函数→3。 |
| ∃z习惯从哪里来? | 练习3目标是集合,“除x外全部量化”在那里正确;模板被过度用于函数目标。写之前读出目标元数。 |
| 全新临时变量 | 第三次尝试把y同时用作临时变量与第二输入,悄悄将g(f(x),y)变为对角式g(f(x),x)。第19页改名段落的现场演示。 |
| 练习5中的“最小” | 最高级=关于所有竞争者的∀主张,以⊃限定:∀z((A(z)∧y<z)⊃x≤z)。非候选者空真通过。公式不使用A的无限性,它让R成为全函数的图,以供后用。 |
第十二部分——自测
先回答再看答案;每题都在本次学习中完成,或磕磕绊绊地走过。
- 朋友说:“关系不可能是集合,因为集合没有次序。”用两句话纠正。
- 陈述数对的同一律,准确展示朴素编码(a,b) := {a,b}在哪里违反它。
- 在a≠b情形中,证明{{a},{a,b}}同一律的困难方向。
- 为什么“库拉托夫斯基数对满足同一律”不是集合论的新假设?命名支配规律可以具有的两种地位。
- 定义Arithmetic与arithmetic。预告的哥德尔非平凡结果是什么,它对区分做了什么?
- 大写/小写a的记账为什么对皮亚诺算术尤其重要?哪一个符号的改变把Presburger的完备理论变成不可完备化的理论?
- 按书中定义,要表明f(x)=x²是Arithmetic,公式在(3,9)与(3,10)处必须做什么?
- 写出“x整除y”的小写算术公式,以及素数的完整公式。素数公式必须克服哪三个错误?
- L_E没有∈。在构造内部如何说“y属于A”?
- 从图公式G,关于g,与F,关于f,构建f(g(x))=z的公式。哪个变量被约束,为什么是它?
- ∃y∃z(G(x,y)∧F(y,z))是关于每个x的真陈述。给出两个独立理由说明它不能表明f(g(x))是Arithmetic,一个关于回答模式,一个关于书中自己的测试。
- 陈述联系自由变量与所定义条件的带走原则,并给出空位数:集合;单输入函数;双输入函数。
- 写出练习5中“x是A中大于y的最小元素”的公式。为什么∀下面用⊃而不用∧?A的无限性在哪里使用?
答案
- 关系是集合,其元素是有序元组,不是单个数。次序在每个元素,即元组内部,因此汇集本身无须次序;问单独3是否属于整除关系是类型错误,而(3,12)要么属于,要么不属于。
- (a,b)=(c,d)当且仅当a=c且b=d。朴素编码:{2,3}={3,2},所以(2,3)与(3,2)的编码相等,而2=3不成立;两次不同提交碰撞,编码有损。
- a≠b:编码有两个成员,单元集{a}与二元集{a,b}。{c}不能等于二元集,大小不对;若{c,d}={a},则c=d=a,让右侧坍缩为一个成员,矛盾。所以{c}={a},c=a;然后{a,d}={a,b}且b≠a,给出b=d。
- 它是定理,从外延性与配对公理证明,不是公理。支配规律要么被假定,新原始内容,要么被证明,定义、保守:没有关于∈的新事实变得可证,只有记号增长。
- Arithmetic:被某个L_E公式表达,允许E。arithmetic:被不含E的公式表达。哥德尔:x^y=z只从+与·即可定义,因此每个Arithmetic关系都是arithmetic,区分坍缩。
- PA语言没有E;若编码需要E,不完备性会错过人们关心的系统,哥德尔结果让它打中这些系统。在+中加入·,从Presburger到完整算术,就从完备/可判定跨到不完备/不可判定。
- 展示F(v1,v2),使对所有x、y,F(x̄,ȳ)真当且仅当x²=y。因此F(3̄,9̄)真,而F(3̄,1̄0̄)假;对错误数对的拒绝才固定函数。
- d(x,y):∃z(y=x·z)。素数:0''≤x ∧ ~∃z(∃y(x=y·z) ∧ ~(z=0') ∧ ~(z=x))。克服的错误:“any”陷阱,用∀y代替∃y;忘记因子x自身;边界~(0''≥x)=“x≥3”,赶走了2。
- 把y代入表达A的公式的自由槽位,若A的约束变量会冲突,先改名。A(ȳ)真当且仅当y∈A,公式就是成员测试;L_E中成员关系不可能有其他含义。
- H(x,z)=∃t(G(x,t)∧F(t,z))。只约束t,为中间值g(x)发明的名字。x、z是条件自身的名字,“f(g(x))=z”提到它们,必须保持自由。
- (a)由于f、g是全函数,它对每个x为真,与x=x回答模式相同,因此表达ℕ;永远不能说不的公式什么也不定义。(b)书中测试要求对所有y,包括错误y,形成F(x̄,ȳ);z被约束后没有自由槽位可代入ȳ,甚至无法施行测试。
- 自由变量恰好等于条件本身提到的字母;每个发明的支架配一个量词。集合→1个自由变量;单输入函数的图→2个;双输入函数的图→3个。
- A(x)∧y<x∧∀z((A(z)∧y<z)⊃x≤z)。若用∧,公式会要求每个z都在A中且大于y,永远为假;⊃让不合资格的z空真通过,有界量词的不对称性。表达R不使用无限性;无限性保证每个y在A中都有后继,使R成为全函数的图,以供后用。
第十三部分——Smullyan后面会讲什么,以及当前局面
进度: 第二章§3完成,Arithmetic/arithmetic的集合、关系、函数、性质、条件,以及练习2–5全部解决,2–4亲手完成,5给出并验证。
下一步:§4,以b为底的连接,第四部分暗中为之准备的那一节。元理论可以自由设定元组;L_E不行,因此有限数序列现在必须被无损编码为单个数,且解码关系为Arithmetic。这是哥德尔编号的开端,7月19日学习的13符号经济在此兑现,本次学习的编码/解码纪律也成为工作标准:同一律=无损性;编码合格当且仅当错误读法被拒绝。目的地不变:塔斯基定理,真句子的哥德尔数集合不是Arithmetic;真理是没有公式能够划出的集合。
持续联系: “表达”,7月19日,得到锻炼:五项构造,每个都以展示并验证的凭据结尾。封闭性工具箱现在成为个人装备:用∧拼接,通过表达公式给出成员关系,用∃引入临时变量,用∀+⊃限定表达最高级,通过≤∧~=表达严格性。Presburger边界扩展7月19日S < + < ×的层级。而未清事项登记仍开放:哥德尔的E消去,从+、·得到x^y=z,留待后续章节;这是≤/数对/E三部曲的第三个、最困难的成员。
方法续篇: 本次学习的引擎仍是拒绝让句子轻易过关,无序集合论如何不满足规律?书中哪里说两个自由变量? 决定性教训在认识层面:对∃z错误的四种直观解释都弹回来了,最终落地的是文本凭据,即定义自身的代入机制。当直观与指导僵持,回到定义的字面,亲手施行其测试。公式只有通过拒绝能力才定义;理解也是如此。
本次学习回顾结束 · Smullyan《哥德尔不完备定理》第二章§3完成 · 此前文件:Godel-Incompleteness-Session-2026-07-15.md,第一章框架与机器谜题;Godel-Incompleteness-Session-2026-07-17-Answer-Sheet.md,第一章练习1–7;Godel-Incompleteness-Session-2026-07-19.md,第二章§1–§2、语言与真理 · 下一步:第二章§4,以b为底的连接,哥德尔编号开始。