Untersuchungen über die Grundlagen der Mengenlehre I

Reference: Zermelo, Ernst (1908). “Untersuchungen über die Grundlagen der Mengenlehre I.” Mathematische Annalen 65, 261–281. English (“Investigations in the Foundations of Set Theory I”) in van Heijenoort, From Frege to Gödel, Harvard 1967, 199–215.

Summary

The first axiomatization of set theory, and the document from which ZFC descends. Cantor’s set theory had been “naive”: sets were formed by unrestricted comprehension — for any property, the set of all things satisfying it. Russell’s paradox (the set of all sets that do not contain themselves) showed this was inconsistent. Zermelo’s response is to abandon the principle that every property determines a set and to replace it with a small list of axioms specifying exactly which set-formation operations are permitted. He gives seven: Extensionality (a set is determined by its members), Elementary sets (the empty set and singletons/pairs exist), Separation (Aussonderung), Power set, Union, Choice, and Infinity.

The load-bearing innovation is the Axiom of Separation. Instead of “the set of all x such that φ(x)”, Zermelo allows only “the set of all x in an already-given set M such that φ(x)”. Comprehension is permitted but only relative to a set that already exists — you may carve a subset out of something you already have, never conjure a totality from a bare predicate. This single restriction blocks Russell’s paradox (there is no universal set to separate from, so the paradoxical set is never formed) while preserving essentially all of working mathematics. Zermelo also makes the Axiom of Choice an explicit, named postulate — partly to put his controversial 1904 well-ordering theorem on a clear footing, since its use of choice had drawn heavy criticism.

Zermelo’s system “Z” was later strengthened by Fraenkel and Skolem, who added the Axiom of Replacement (and Foundation), yielding ZF, and with Choice, ZFC — the de facto standard foundation of mathematics. The paper’s method matters as much as its content: it established that the cure for foundational paradox is not to abandon set theory but to axiomatize it, fixing by fiat which constructions are legitimate. This is the same disciplined, axiom-first stance that Hilbert’s program would generalise and that Gödel’s incompleteness theorems would later probe for limits.

Key Ideas

Axiomatic set theory: replace naive unrestricted comprehension with an explicit, finite list of permitted set-formation axioms.
Separation / Aussonderung: subsets may be carved only from sets that already exist (φ defines a subset of a given M), not summoned from a predicate alone.
Paradox avoidance: Separation blocks Russell’s paradox; there is no universal set, so the self-membership totality is never formed.
The seven axioms: Extensionality, Elementary sets, Separation, Power set, Union, Choice, Infinity.
Axiom of Choice made explicit, securing the 1904 well-ordering theorem against its critics.
Z → ZF → ZFC: later Replacement (Fraenkel/Skolem) and Foundation complete the standard system.

Connections

Conceptual Contribution

Claim: Set theory can be made consistent (paradox-free) by axiomatizing set formation: replace unrestricted comprehension with separation over already-given sets.
Mechanism: Postulate seven axioms; in particular restrict comprehension (Separation) so that no set is built from a predicate alone, only as a subset of an existing set — depriving Russell’s construction of the universal set it needs.
Concepts introduced/used: Set Theory, Axiom of Choice, Russell’s Paradox, ZFC, Power Set
Stance: foundational axiomatization paper (foundations of mathematics)
Relates to: Tames the naive theory whose power-set hierarchy Cantor 1891 revealed; supplies the system ZFC inside which Cohen 1963 proves CH undecidable and which Gödel 1931 shows cannot prove its own consistency.

Backlinks

Über eine elementare Frage der Mannigfaltigkeitslehre
Zur Einführung der transfiniten Zahlen ×2
The Independence of the Continuum Hypothesis ×2
index
ZFC ×2
Well-Ordering Theorem ×2
Set Theory
Russell's Paradox ×2
Power Set
Cumulative Hierarchy
Axiom of Choice ×2

Linked Pages

Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I

Reference: Gödel, Kurt (1931). “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” [“On formally undecidable propositions of Principia Mathematica and related systems I”]. Monatshefte für Mathematik und Physik 38, 173–198. English translation in van Heijenoort (ed.), From Frege to Gödel (Harvard 1967), and in Gödel, Collected Works I (Oxford 1986). Scan: monatshefte-fuer-mathematik @ archive.org; English: Meltzer/Braithwaite 1962.

Summary

Gödel’s 1931 paper proves the two incompleteness theorems that permanently reshaped mathematical logic. The first theorem states that for any ω-consistent, effectively axiomatised formal system P strong enough to formalise elementary arithmetic, there exists a sentence G in the language of P such that neither G nor ¬G is provable in P. The second theorem states that if P is consistent, then P cannot prove its own consistency statement Con(P). Together they show that Hilbert’s programme — to secure classical mathematics by a finitary consistency proof of a sufficiently strong formal system — cannot succeed in its original form.

The technical machinery is the one mathematicians still use. Gödel introduces Gödel numbering, an injective encoding of formulas and proofs as natural numbers, which allows syntactic notions (“x is the Gödel number of a proof of the formula with Gödel number y”) to be expressed as arithmetic predicates. He then establishes the representability of all primitive recursive predicates in P and constructs, via a fixed-point / diagonal lemma, a sentence G that is in effect self-referential: G says “I am not provable in P.” An analysis of the two cases — G provable, ¬G provable — using ω-consistency yields the first theorem. Formalising that analysis inside P itself yields the second.

The paper is the mathematical origin of self-reference as a tool, of arithmetisation of syntax, and of the technique — later generalised by Tarski, Church, Turing, and Kleene — for transferring undecidability phenomena between formal systems. It also establishes the class of primitive recursive functions as the workhorse notion of effectivity in the paper, the direct ancestor of Kleene’s general recursive functions. The incompleteness theorems remain the single most cited and philosophically consequential results of twentieth-century logic.

Key Ideas

Gödel numbering: arithmetisation of syntax, turning formulas and proofs into natural numbers.
First incompleteness theorem: every ω-consistent, effectively axiomatised, sufficiently expressive theory contains a true-but-unprovable sentence.
Second incompleteness theorem: no such theory can prove its own consistency.
Diagonal / fixed-point lemma: every arithmetic predicate has a self-referential instance.
Primitive recursive functions as the effective-syntax layer (precursor to general recursive functions).
Representability: every primitive recursive relation is definable in P.
The shattering of Hilbert’s programme in its finitist form.

Connections

Conceptual Contribution

Claim: No effectively axiomatised, ω-consistent theory that interprets arithmetic is complete; no such consistent theory proves its own consistency.
Mechanism: Encode syntax as natural numbers (Gödel numbering). Represent primitive recursive predicates (including the proof relation Bew) inside the theory. Construct a self-referential sentence G ≡ ¬∃y. Bew(y, ⌜G⌝) via a diagonal lemma; analyse cases using ω-consistency for theorem I; formalise that analysis to obtain theorem II.
Concepts introduced/used: Gödel numbering, primitive recursive functions, representability, diagonal lemma, ω-consistency, Consistency and Completeness, First-Order Logic
Stance: foundational theorem paper (mathematical logic)
Relates to: The methodological parent of Church 1936 and Turing 1936; sharpened by Rosser 1936 (dropping ω-consistency); the arithmetisation technique underwrites all later work on effectively axiomatised theories, including the hierarchies of Kleene 1943 and Mostowski 1946.

The Independence of the Continuum Hypothesis

Reference: Cohen, Paul J. (1963, 1964). “The Independence of the Continuum Hypothesis” (I & II). Proceedings of the National Academy of Sciences 50(6), 1143–1148 and 51(1), 105–110. DOI 10.1073/pnas.50.6.1143.

Summary

The papers that resolve Hilbert’s first problem and introduce forcing, the most powerful technique in modern set theory. Cantor’s continuum hypothesis (CH) asserts that there is no cardinality strictly between that of the integers and that of the reals — that |𝒫(ℕ)| is the least uncountable cardinal ℵ₁. Gödel had shown in 1938–40, via the constructible universe L, that CH and the axiom of choice cannot be disproved from the ZF axioms (they hold in L, an inner model of any model of ZF). Cohen supplies the other half: he constructs models of ZFC in which CH fails, and models in which the axiom of choice fails. Together these establish that CH is independent of ZFC — neither provable nor refutable — and likewise that AC is independent of ZF.

The method is forcing. Starting from a countable transitive model M of ZFC, Cohen adjoins a new “generic” object G (for ¬CH, enough generic subsets of ℕ to make the continuum larger than ℵ₁) to form an extension M[G]. The delicate point is that M cannot “see” G, yet one must guarantee M[G] still satisfies all the ZFC axioms and controls exactly which new statements become true. Cohen manages this with the forcing relation p ⊩ φ — a condition p (a finite fragment of the generic object) “forces” a sentence φ — defined entirely inside M, so that truth in the extension is decided by the ground model even though the generic object lies outside it. Genericity (the filter G meets every dense set of M) ensures the construction is consistent and that the intended statement holds.

Forcing turned independence from an exotic curiosity into a routine instrument: it is now the standard way to show a statement undecidable in ZFC, and it reframes the foundational picture. Where Gödel’s incompleteness theorems show that any sufficiently strong consistent theory leaves arithmetic sentences undecided, Cohen shows that one of the most basic questions about the size of the continuum is itself undecided by our standard foundation — not for want of cleverness but in principle. The combined Gödel–Cohen result is the canonical example of a natural mathematical statement that is independent of its axioms. Cohen received the Fields Medal (1966) for it.

Key Ideas

Continuum Hypothesis: there is no cardinality strictly between |ℕ| and |ℝ|; equivalently |𝒫(ℕ)| = ℵ₁.
Independence of CH from ZFC: Gödel (1940, via L) shows CH is consistent; Cohen shows ¬CH is consistent — so CH is undecidable in ZFC.
Independence of AC from ZF, by the same model-building technique.
Forcing: extend a countable transitive model M by a generic object G to get M[G] satisfying ZFC plus the desired (in)dependence.
The forcing relation p ⊩ φ: definable inside the ground model, lets M control truth in M[G] without seeing G.
Genericity: G meets every dense subset of the forcing poset that lies in M, guaranteeing consistency.
Meta-mathematical limit: a basic question of set size is in-principle undecidable from the standard axioms.

Connections

Conceptual Contribution

Claim: The continuum hypothesis (and the axiom of choice) is independent of the standard axioms of set theory — neither ZFC ⊢ CH nor ZFC ⊢ ¬CH.
Mechanism: Forcing — adjoin a generic filter G to a countable transitive model M of ZFC, with a forcing relation defined inside M that fixes truth in M[G]; choose the forcing poset so the extension satisfies ¬CH (or ¬AC), complementing Gödel’s L model where CH holds.
Concepts introduced/used: Forcing, Continuum Hypothesis, Constructible Universe, ZFC, Cardinality
Stance: foundational independence-result paper (set theory / model theory)
Relates to: Settles the cardinality question opened by Cantor 1891 as undecidable in Zermelo’s ZFC; the set-theoretic counterpart of the syntactic undecidability in Gödel 1931.

Über eine elementare Frage der Mannigfaltigkeitslehre

Reference: Cantor, Georg (1891). “Über eine elementare Frage der Mannigfaltigkeitslehre.” Jahresbericht der Deutschen Mathematiker-Vereinigung 1, 75–78. English (“On an Elementary Question of the Theory of Manifolds”) in Ewald, From Kant to Hilbert, vol. 2, Oxford 1996.

Summary

The four-page note in which Cantor introduces the diagonal argument and, with it, the modern proof that there are different sizes of infinity. Having already shown in 1874 (by a nested-intervals argument) that the real numbers cannot be enumerated, Cantor here gives a far simpler and more general method. He considers the collection of all infinite sequences over two symbols (he uses m and w) — equivalently, all functions from the natural numbers into a two-element set. Assume such sequences could be listed as E₁, E₂, E₃, …. Define a new sequence E₀ whose n-th entry is chosen to differ from the n-th entry of Eₙ (flip m↔w down the diagonal). Then E₀ differs from every Eₙ in at least one place, so it is absent from the list — contradiction. The collection of such sequences is therefore not enumerable.

Cantor immediately generalises. For any set M, the totality of functions from M into a two-element set — i.e. the power set of M — has a strictly greater cardinality than M itself. This is Cantor’s theorem: |M| < |𝒫(M)|. Its consequence is that there is no largest cardinality and no “set of all sets” of maximal size; instead the transfinite cardinalities form an unending ascending hierarchy. The argument is purely combinatorial — no analysis, no topology of the line — which is exactly why it became the template for every later self-referential limitative result.

The diagonal method is the paper’s lasting bequest. Gödel’s incompleteness construction, Turing’s and Church’s undecidability proofs, Russell’s paradox, and Tarski’s undefinability of truth are all recognisably the same move: build an object that disagrees, along the diagonal, with every member of a purported complete enumeration. The 1891 note is where that move is first made explicit and abstracted away from the particular case of the reals.

Key Ideas

The diagonal argument: from any enumeration of sequences, construct one differing from the n-th at position n; it cannot be in the list.
Uncountability of the set of infinite binary sequences (hence of the reals, of 𝒫(ℕ)).
Cantor’s theorem: for every set M, |M| < |𝒫(M)| — the power set is strictly larger.
No largest cardinal: transfinite cardinalities form an unbounded ascending hierarchy.
Combinatorial, not analytic: the proof needs nothing about the continuum beyond counting, making it general.
Template for self-reference: the structural seed of Gödel, Turing, Church, Russell, Tarski.

Connections

Conceptual Contribution

Claim: For any set M, there are strictly more subsets of M than elements of M; hence infinite sets come in distinct, unboundedly increasing sizes.
Mechanism: Suppose an enumeration of all sequences/subsets exists; diagonalise to manufacture one that differs from each listed item at its own index; the manufactured item is therefore unlisted — contradiction.
Concepts introduced/used: Diagonalization, Cardinality, Power Set, Cantor’s Theorem, Transfinite Numbers
Stance: foundational theorem paper (set theory / foundations of mathematics)
Relates to: Furnishes the diagonal method later turned into a limitative weapon by Gödel 1931 and Church 1936; the cardinality questions it opens (how large is 𝒫(ℕ)?) become the Continuum Hypothesis, settled as independent by Cohen 1963.

Power Set

The set 𝒫(M) of all subsets of a set M. Its existence is guaranteed by the power-set axiom of ZFC. By Cantor’s Theorem it always has strictly greater Cardinality than M, so iterating it generates ever-larger infinities and, transfinitely, the Cumulative Hierarchy.

In this vault

ZFC

Zermelo–Fraenkel set theory with the Axiom of Choice — the de facto standard axiomatic foundation of mathematics. Begins with Zermelo’s 1908 axioms (Extensionality, Separation, Power set, Union, Choice, Infinity, Elementary sets), strengthened by Fraenkel and Skolem with the Axiom of Replacement (and Foundation). Russell’s Paradox is blocked by Separation. Famously incomplete in a strong sense: the Continuum Hypothesis and the Axiom of Choice are independent of it (Gödel + Cohen).

In this vault

Russell's Paradox

Russell’s Paradox

The contradiction (Russell 1901) that sank naive set theory: let R = {x : x ∉ x}, the set of all sets that are not members of themselves; then R ∈ R iff R ∉ R. It shows that unrestricted comprehension — “every property determines a set” — is inconsistent. Zermelo’s Axiom of Separation is the standard cure: predicates may only carve subsets out of already-given sets, so the universal set R is never formed.

In this vault

Axiom of Choice

The axiom (AC) that for any collection of non-empty sets there exists a choice function selecting one element from each. Equivalent to the Well-Ordering Theorem and to Zorn’s lemma. Made an explicit postulate by Zermelo, partly to ground his 1904 well-ordering proof against critics who objected to non-constructive choice. Independent of the other ZF axioms: consistent (Gödel, via the Constructible Universe) and unprovable (Cohen, via Forcing).

In this vault

Set Theory

The branch of mathematical logic that treats sets — arbitrary collections — as the basic objects from which all other mathematical structures can be built, and the de facto foundation of mathematics. Founded by Cantor, who showed (via Diagonalization) that infinite sets come in distinct, unboundedly increasing sizes (Cardinality, Cantor’s Theorem). Cantor’s “naive” theory permitted unrestricted comprehension and so fell to Russell’s Paradox; Zermelo’s axiomatization replaced comprehension with Separation, yielding the system that — strengthened with Replacement, Foundation, and Choice — became ZFC, the standard foundation. Ordinals and cardinals are realised concretely as sets (the von Neumann ordinals), indexing the Cumulative Hierarchy. The discipline’s deepest results are limitative: the Continuum Hypothesis and the Axiom of Choice are independent of ZFC (Gödel’s constructible universe + Cohen’s Forcing), the set-theoretic counterpart to Gödel incompleteness.

In this vault

Über eine elementare Frage der Mannigfaltigkeitslehre — Cantor 1891 (diagonal argument, Cantor’s theorem)
Untersuchungen über die Grundlagen der Mengenlehre I — Zermelo 1908 (axiomatization)
Zur Einführung der transfiniten Zahlen — von Neumann 1923 (ordinals as sets)
The Independence of the Continuum Hypothesis — Cohen 1963/64 (forcing, independence)
On Notation for Ordinal Numbers — Church & Kleene (constructive ordinals)
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I — Gödel 1931 (the limitative sibling)

Foundations of Logic Programming - Lloyd

Foundations of Logic Programming (Chapter 1: Preliminaries)

Reference: J. W. Lloyd (1987). Springer-Verlag, Second Extended Edition. Source file: 2022-08-18 13-38-01-Lloyd.pdf. URL

Summary

The opening chapter of Lloyd’s canonical textbook on the mathematical foundations of logic programming. It introduces first-order theories, syntax (alphabets, terms, well-formed formulas, clauses, Horn clauses), interpretations and models, and Herbrand semantics as the preferred route for reasoning about logical consequence of a program.

Lloyd motivates logic programming as Kowalski’s insight that “algorithm = logic + control”: a definite program is a set of Horn clauses (the logic), and the inference strategy (SLD-resolution, search order) is the control. He distinguishes “system” languages (committed-choice, concurrent) from “application” languages (PROLOG-style), and sets up the semantic machinery — Herbrand interpretations, models, logical consequence, unsatisfiability — needed for the rest of the book.

Key Ideas

Algorithm = Logic + Control (Kowalski’s principle)
Horn clauses as the executable fragment of first-order logic
Herbrand universe and base; Herbrand interpretations suffice for clause sets
Definite programs vs normal programs (negation)
SLD-resolution as refutation procedure (developed in later chapters)

Connections

Conceptual Contribution

Claim: Logic — specifically first-order Horn-clause logic with SLD-resolution — can serve as a programming language, where a program is a set of definite clauses, a computation is resolution refutation, and the declarative semantics (Herbrand models, least fixpoint) coincides with the procedural semantics.
Mechanism: Rigorously build up first-order theories, interpretations, Herbrand interpretations/bases, unification, and the T_P fixpoint operator; prove soundness and completeness of SLD-resolution; develop negation-as-failure, the Closed World Assumption, and semantics of normal programs; treat Prolog as the canonical realisation of the Kowalski slogan “algorithm = logic + control”.
Concepts introduced/used: Logic Programming, Horn Clauses, SLD Resolution, Herbrand Universe, Unification, Negation as Failure, Fixpoint Semantics, Prolog, Closed World Assumption, First-Order Logic, Algorithm = Logic + Control
Stance: formal / foundational textbook
Relates to: Theoretical substrate for Agent-Oriented Programming, ACRE Agent Conversation Reasoning Engine, and Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents (all of which assume BDI agents implemented in logic-programming languages). The mentalistic-semantics side of ACLs (KQML as an Agent Communication Language, FIPA-ACL) presupposes Lloyd-style logical machinery.

Summary

The paper that gives ordinals a concrete set-theoretic identity. Cantor had introduced ordinals as order types — abstract equivalence classes of well-ordered sets sharing the same order structure — which left them mathematically real but representationally vague. Writing at twenty, von Neumann proposes instead to pick a canonical representative for each: an ordinal simply is the set of all ordinals below it. So 0 = ∅, 1 = {∅}, 2 = {∅, {∅}}, 3 = {∅, {∅}, {∅, {∅}}}, …, and the first infinite ordinal ω = {0, 1, 2, …}. Each ordinal is a transitive set well-ordered by the membership relation ∈; “less than” is “is a member of.” These are the von Neumann ordinals, still the standard definition.

The construction does real work beyond tidiness. Because each ordinal is built explicitly from its predecessors as sets, ordinals can be defined within axiomatic set theory rather than presupposed, and von Neumann justifies definition by transfinite recursion — defining a function on all ordinals by specifying its value at α in terms of its values below α — which Cantor had used but not rigorously grounded. Von Neumann’s later 1925/1928 axiomatization carries the idea further, distinguishing classes from sets (the precursor of NBG/von Neumann–Bernays–Gödel set theory) and proposing a limitation-of-size principle and the axiom of foundation, under which all sets sit in the cumulative hierarchy V indexed by exactly these ordinals.

For this vault the paper closes a loop. It is the classical, set-theoretic account of the ordinals whose constructive, computable counterpart is the Church–Kleene system of ordinal notations — the same objects approached from the standpoint of what a machine can name and recurse over. And it is of a piece with von Neumann’s lifelong habit, visible across his work here, of finding the minimal concrete structure that lets an informal mathematical notion be manipulated rigorously.

Key Ideas

Von Neumann ordinals: each ordinal is the set of all smaller ordinals; ∈ is the well-ordering, so “<” = “∈”.
Canonical representatives: replace Cantor’s abstract order types with concrete sets — 0 = ∅, n+1 = n ∪ {n}, ω = {0,1,2,…}.
Ordinals internal to set theory: definable from the axioms rather than assumed; transitive sets well-ordered by membership.
Transfinite recursion rigorously justified: define f(α) from {f(β) : β < α}.
Classes vs. sets (in the 1925 sequel): the NBG lineage, limitation of size, axiom of foundation.
Cumulative hierarchy V is indexed by the ordinals so defined.

Connections

Conceptual Contribution

Claim: Every ordinal can be canonically realised as a set — the set of its predecessors — so ordinals become objects definable inside axiomatic set theory rather than abstract order types taken on faith.
Mechanism: Define an ordinal as a transitive set well-ordered by ∈; build them by α+1 = α ∪ {α} and unions at limits; ground definition-by-transfinite-recursion on this representation.
Concepts introduced/used: Ordinals, Transfinite Numbers, Cumulative Hierarchy, Set Theory
Stance: foundational construction paper (set theory)
Relates to: Gives the classical set-theoretic ordinals whose computable analogue is Church–Kleene; supplies the ordinal scaffolding for the cumulative hierarchy built on Zermelo’s axioms; shares its author with Theory of Self-Reproducing Automata and Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components.

Well-Ordering Theorem

Every set can be well-ordered (given a total order in which every non-empty subset has a least element). Proved by Zermelo (1904) using the Axiom of Choice, to which it is in fact equivalent. The controversy over its non-constructive use of choice is what led Zermelo to isolate AC as an explicit axiom in his 1908 axiomatization. Well-orderings are what the Ordinals are the order types of.

Untersuchungen über die Grundlagen der Mengenlehre I

Summary

Key Ideas

Connections

Conceptual Contribution

Tags

Backlinks