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.

In this vault

Backlinks

Linked Pages

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)

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

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.

Ordinals

Numbers that generalise “position in a well-ordering” into the transfinite (0, 1, …, ω, ω+1, …). In modern set theory each ordinal is realised as a von Neumann ordinal — the set of all smaller ordinals, well-ordered by ∈ — so that “<” is literally “∈”. Ordinals index transfinite recursion and the Cumulative Hierarchy. Their constructive, computable fragment is the subject of the Church–Kleene ordinal-notation system.