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.

Backlinks

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.

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.

Ü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.

Cardinality

A measure of the “size” of a set, generalised to infinite sets via bijection: two sets have the same cardinality iff their elements can be put in one-to-one correspondence. Cantor showed that this notion is non-trivial in the infinite — ℕ and ℝ have different cardinalities — and that cardinalities form an unbounded ascending hierarchy (ℵ₀ < ℵ₁ < …). See Cantor’s Theorem for the strict-increase result and Continuum Hypothesis for the size of the continuum.

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

Constructible Universe

Gödel’s inner model L, built like the Cumulative Hierarchy but admitting at each stage only the sets definable from earlier ones. L is a model of ZFC in which both the Axiom of Choice and the Continuum Hypothesis hold, which is how Gödel (1938–40) proved AC and CH consistent with ZF. It is the complement to Cohen’s construction of models where they fail — together establishing independence.

In this vault

Continuum Hypothesis

Cantor’s conjecture (CH) that there is no Cardinality strictly between that of the integers and that of the reals — equivalently |𝒫(ℕ)| = ℵ₁. The first of Hilbert’s 1900 problems. Shown to be independent of ZFC: Gödel (1938–40) proved it consistent via the Constructible Universe, and Cohen (1963) proved its negation consistent via Forcing. It is therefore neither provable nor refutable from the standard axioms.

In this vault

Forcing

Cohen’s (1963) technique for building models of set theory to prove independence results. Starting from a countable transitive model M of ZFC, one adjoins a “generic” object G to form an extension M[G], with a forcing relation (p ⊩ φ) defined inside M that controls which sentences hold in M[G] without M being able to see G. By choosing the forcing poset appropriately one makes the extension satisfy, e.g., ¬Continuum Hypothesis or ¬Axiom of Choice. Forcing is now the standard instrument for showing a statement undecidable in ZFC; it earned Cohen the Fields Medal.

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)

The Independence of the Continuum Hypothesis

Summary

Key Ideas

Connections

Conceptual Contribution

Tags

Backlinks