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