Im Jahr 1874 stellte der deutsche Mathematiker Georg Cantor eine Frage, die niemand sonst der Mühe wert hielt: gibt es mehr reelle Zahlen als rationale Zahlen? Beide sind unendlich; die intuitive Antwort lautet daher gleich viele — beide unendlich. Cantor zeigte mit aller Schärfe, dass sie es nicht sind. Es gibt mehr Reelle. Manche Unendlichkeiten sind größer als andere. Der Beweis — das Diagonalargument — passt auf eine Postkarte, und doch brauchte die mathematische Zunft eine Generation, ihm zu verzeihen. Henri Poincaré nannte Cantors Werk eine perverse Pathologie. Die nächste Generation, allen voran Hilbert, nannte es ein Paradies — und Hilbert versprach, aus dem Paradies, das Cantor uns geschaffen hat, soll uns niemand vertreiben können.
Zwei Mengen haben dieselbe Mächtigkeit genau dann, wenn es eine Bijektion zwischen ihnen gibt — eine Funktion, die jedem Element der einen genau ein Element der anderen zuordnet. Diese Definition ist die richtige, denn sie greift für endliche und unendliche Mengen: eine dreielementige Menge hat die Mächtigkeit 3, weil sie sich auf {1, 2, 3} abbilden lässt, und die natürlichen Zahlen haben per Definition die Mächtigkeit ℵ₀ (Aleph-Null). Abzählbar sind die Mengen, die sich auf ℕ abbilden lassen; überabzählbar sind die unendlichen, aber nicht abzählbaren. Cantor zeigte, dass die rationalen Zahlen — Paare ganzer Zahlen, scheinbar zahlreicher als die ganzen Zahlen — abzählbar sind: man ordnet sie in einem 2D-Gitter an und schlängelt sich diagonal hindurch. Die algebraischen Zahlen (Nullstellen ganzzahliger Polynome) sind nach derselben Bauart abzählbar. Die reellen Zahlen hingegen sind überabzählbar. Cantors Diagonalargument: nimm zum Widerspruch an, die reellen Zahlen zwischen 0 und 1 seien abzählbar; liste sie in irgendeiner Reihenfolge mit ihren Dezimalentwicklungen auf; baue eine neue reelle Zahl, deren n-te Dezimalstelle sich von der n-ten Stelle der n-ten gelisteten Zahl unterscheidet; sie steht auf keiner Stelle der Liste — Widerspruch. Die Mächtigkeit der reellen Zahlen beträgt 2^ℵ₀, die Mächtigkeit des Kontinuums. Cantors Satz verallgemeinert: zu jeder Menge X hat die Potenzmenge P(X) eine echt größere Mächtigkeit als X — eine größte Unendlichkeit gibt es nicht. Die Hierarchie ℵ₀ < ℵ₁ < ℵ₂ < … steigt ohne Ende. Die Kontinuumshypothese (CH) — Cantors Frage, ob es eine Unendlichkeit echt zwischen ℵ₀ und 2^ℵ₀ gibt — wurde zu Hilberts erstem Problem von 1900. Gödel (1940) zeigte: CH ist mit ZFC verträglich. Paul Cohen (1963) zeigte: auch ihre Negation ist verträglich. CH ist somit unabhängig von ZFC — in der Standard-Mengenlehre nicht entscheidbar, ein ungelöstes Problem, befördert zu einem unlösbaren.
Cantors Diagonale ist die meistwiederverwendete Beweistechnik der Mathematik. Turings Beweis der Unentscheidbarkeit des Halteproblems ist ein Diagonalargument, auf Programme angewandt. Gödels Unvollständigkeitssatz ist ein Diagonalargument, auf die Logik angewandt. Das Mächtigkeitsargument zeigt überdies, dass fast jede reelle Zahl nicht berechenbar ist: es gibt abzählbar viele Programme (jedes eine endliche Symbolfolge), aber überabzählbar viele Reelle, weshalb die meisten Reellen unsagbar sind — sie existieren, die Theorie braucht sie, doch kein Mensch und kein Computer kann je eine vollständig beschreiben. Die Typentheorie in der Informatik arbeitet mit Mächtigkeitsschranken. Die Kontinuumshypothese bleibt Gegenstand philosophischer Debatte unter Mengentheoretikern; neue Axiomenkandidaten (Forcing-Axiome, Großkardinal-Axiome) beziehen dazu Stellung.