Die Philosophie der Mathematik

Ordinalzahlen und Kardinalzahlen

Kardinalzahlen geben an, wie viele Objekte einer bestimmten Art vorhanden sind; Ordinalzahlen geben die Stellung eines Glieds in einer wohlgeordneten Folge an. Frege identifizierte die natürlichen Zahlen als endliche Kardinalzahlen, doch sie dienen ebenso gut als endliche Ordinalzahlen. Es lässt sich sogar argumentieren, dass der Begriff der Ordinalzahl der grundlegendere der beiden ist. Wenn wir zählen, ordnen wir die gezählten Objekte notwendigerweise in eine Reihenfolge, indem wir ihnen der Reihe nach Zahlwörter zuweisen. Die Zahl der gezählten Objekte ergibt sich dann aus der größten Zahl, die einem von ihnen zugewiesen wurde, wenn wir – wie im Alltag üblich – mit eins beginnen; oder aus der kleinsten Zahl, die keinem von ihnen zugewiesen wurde, wenn wir mit null beginnen. Ebenso genügt es, um die Zahl der Häuser in einer Straße zu bestimmen, die höchste Hausnummer zu finden. Wenn wir jedoch Haus Nummer 37 in der Cambridge Street suchen, können wir die Häuser nicht in beliebiger Reihenfolge bis 37 zählen: Wir müssen sie in der Reihenfolge betrachten, in der sie nummeriert wurden. Wenn wir hingegen nur feststellen wollen, wie viele Objekte einer bestimmten Art es gibt, spielt die Reihenfolge keine Rolle. Das liegt daran, dass jede lineare Anordnung einer endlichen Menge (oder zweier gleich großer endlicher Mengen) ähnlich ist. Aus diesem Grund können die natürlichen Zahlen gleichermaßen als endliche Ordinalzahlen oder als endliche Kardinalzahlen dienen.

Die kleinste transfinite Ordinalzahl ist diejenige, die dem Ordnungstyp der natürlichen Zahlen nach Größe entspricht. Wie jede Ordinalzahl besitzt sie einen Nachfolger. Es trifft keineswegs zu, dass alle Wohlordnungen unendlicher Mengen ähnlich wären. So entspricht etwa die Ordinalzahl, die sich ergibt, wenn die natürlichen Zahlen so angeordnet sind, dass jede positive Zahl der Null vorausgeht, einem anderen Ordnungstyp. Hilfreich für das Verständnis einer Ordinalzahl ist, dass jede Ordinalzahl der Ordnungstyp aller kleineren Ordinalzahlen in aufsteigender Folge ist. So ist beispielsweise der Nachfolger der Ordnungstyp der wohlgeordneten Folge 0, 1, 2 und so weiter bis zur kleinsten unendlichen Ordinalzahl. Diese unendliche Ordinalzahl, multipliziert mit zwei, entspricht der Ordnung, in der alle geraden Zahlen allen ungeraden vorausgehen, ebenso wie der unendlichen Fortsetzung 0, 1, und danach der unendlichen Folge dieser Ordnung.

Jede Ordinalzahl gehört zu einer von drei Arten: entweder sie ist null, eine Nachfolgerordinalzahl wie die unendliche Ordinalzahl plus eins, oder eine Grenzordinalzahl wie die unendliche selbst oder ihr Vielfaches. Eine Grenzordinalzahl ist eine, die weder null noch Nachfolger ist, sondern die Grenze aller kleineren Ordinalzahlen – also die kleinste Ordinalzahl, die größer oder gleich allen kleineren ist. Transfinite Induktion ist eine Methode, um zu beweisen, dass eine Aussage für alle Ordinalzahlen gilt; sie ist eine Verallgemeinerung der endlichen Induktion. Um zu beweisen, dass eine Aussage P(a) für jede Ordinalzahl a gilt, muss man drei Dinge zeigen: Erstens, dass P(0) gilt; zweitens, dass für jede Ordinalzahl β gilt: wenn P(β), dann auch P(β plus eins); und drittens, dass, wenn λ eine Grenzordinalzahl ist und P(η) für jede kleinere η gilt, auch P(λ) gilt.

Transfinite Induktion bis zu einer Ordinalzahl λ ist ein Mittel, um zu zeigen, dass eine Aussage für jede Ordinalzahl kleiner als λ gilt. Ihre Bedingungen ähneln denen der unbegrenzten transfiniten Induktion, nur dass hinzugefügt wird, dass β plus eins kleiner als λ und λ kleiner als die betrachtete Grenze ist. Transfinite Induktion bis λ kann auch verwendet werden, um eine Aussage Q(n) für alle natürlichen Zahlen zu beweisen, indem man eine Wohlordnung der natürlichen Zahlen vom Ordnungstyp λ heranzieht. Dabei lautet die Aussage P(a): wenn n die a-te natürliche Zahl in dieser Wohlordnung ist, dann gilt Q(n).

Endliche Induktion kann in einer anderen Form auftreten, manchmal vollständige Induktion genannt, deren Voraussetzung stärker ist als die der gewöhnlichen endlichen Induktion. Um P(n) für jede natürliche Zahl n zu beweisen, genügt es zu zeigen, dass für jede natürliche Zahl k gilt: wenn P(m) für alle m kleiner als k, dann auch P(k). Dies gilt zunächst für null, da es keine kleineren Zahlen gibt; daraus folgt P(1), dann P(2) und so weiter. Die gewöhnliche endliche Induktion beruht darauf, dass die natürlichen Zahlen eine Ordnung vom Typ der kleinsten unendlichen Ordinalzahl haben; die vollständige Induktion hingegen nur darauf, dass sie wohlgeordnet sind. Sie entspricht der Methode des unendlichen Abstiegs: Um zu zeigen, dass P(n) für alle n gilt, genügt es, zu zeigen, dass, wenn es eine Zahl k gäbe, für die P(k) nicht gilt, dann eine kleinere Zahl m existieren müsste, für die ebenfalls P(m) nicht gilt. Gäbe es eine solche Zahl, so ließe sich nach endlich vielen Schritten zeigen, dass P(0) nicht gilt, was unmöglich ist, da es keine kleinere Zahl gibt. Diese Methode beruht darauf, dass es keine unendliche absteigende Folge natürlicher Zahlen gibt; und zu sagen, dass keine solche existiert, heißt, dass die Ordnung eine Wohlordnung ist. Vollständige Induktion lässt sich daher als eine Variante der transfiniten Induktion formulieren: Um zu beweisen, dass P(a) für alle Ordinalzahlen gilt, genügt es zu zeigen, dass für jede Ordinalzahl λ gilt: wenn P(η) für alle η kleiner als λ, dann auch P(λ).

Wie weit auch immer eine auf den Ordinalzahlen definierte Funktion springen mag, der langsame Marsch der Ordinalzahlen wird sie stets einholen. Sei φ eine monoton wachsende Funktion, deren Wert für eine Grenzordinalzahl λ immer das Limit der Werte φ(a) für a kleiner als λ ist. Dann besitzt φ für jede Ordinalzahl η einen Fixpunkt α größer als η, also eine Ordinalzahl, für die φ(α) gleich α ist. Der erste solche Fixpunkt ist die Grenze einer unendlichen Folge.

Ordinalzahlen, die Ordnungstypen von Wohlordnungen sind, die auf den natürlichen Zahlen gebildet werden können, heißen abzählbare Ordinalzahlen. Nach den Ordnungen der Form ω mal zwei, ω mal drei und so weiter folgt ω hoch zwei, der Ordnungstyp einer Anordnung, in der zunächst alle Primzahlpotenzen nach Größe kommen, dann alle Zahlen mit genau zwei verschiedenen Primfaktoren, dann die mit drei und so fort. Eine Folge vom Ordnungstyp ω hoch zwei kann als Folge von Folgen des Typs ω betrachtet werden, und eine vom Typ ω² als Folge vom Typ ω von Folgen des Typs ω. Eine Folge vom Typ ω³ ist entsprechend eine Folge vom Typ ω von Folgen des Typs ω von Folgen des Typs ω. Nach diesen folgt ω hoch ω. Die Folge ω, ω², ω³ und so weiter hat ebenfalls eine Grenze, die als ε₀ bezeichnet wird. Dies ist die kleinste Ordinalzahl, die sich nicht durch Addition, Multiplikation oder Potenzierung aus ω und eins darstellen lässt; zugleich ist sie der kleinste Fixpunkt der Exponentialfunktion über ω. Wer bisher mit transfiniten Ordinalzahlen nicht vertraut war, mag sich nun schwindlig fühlen, und wird kaum getröstet sein zu erfahren, dass ε₀ als eine relativ kleine abzählbare Ordinalzahl gilt.

Bei weitem nicht alle Ordinalzahlen in Cantors Theorie sind endlich oder abzählbar. Die endlichen und abzählbaren Ordinalzahlen bilden selbst eine wohlgeordnete Folge und haben daher eine Grenze, die als ω₁ bezeichnet wird. Diese ist größer als alle abzählbaren Ordinalzahlen und daher selbst nicht abzählbar. Ein neuer Grund, die Ordinalzahlen für grundlegender zu halten als die Kardinalzahlen, liegt darin, dass die Theorie der Ordinalzahlen das Fundament von Cantors Theorie der Kardinalzahlen bildet. Es gibt zwei transfinite Kardinalzahlen: die Anzahl der natürlichen Zahlen, bezeichnet als Aleph-Null, und die größere Zahl der reellen Zahlen, bezeichnet als zwei hoch Aleph-Null. Die arithmetischen Operationen haben bei Kardinalzahlen eine andere Bedeutung als bei Ordinalzahlen: wenn m und n Kardinalzahlen sind, dann ist n hoch m die Anzahl der Abbildungen von einer Menge der Mächtigkeit m in eine der Mächtigkeit n. Die Operation, die von Aleph-Null zu zwei hoch Aleph-Null führt, kann zwar unbegrenzt wiederholt werden, doch war sie nicht der zentrale Schritt in Cantors Theorie. Die Gesamtheit aller endlichen und abzählbaren Ordinalzahlen bildet eine nicht abzählbar unendliche Menge, deren Kardinalität Cantor als Aleph-Eins bezeichnete; sie ist größer als Aleph-Null, und es gibt keine Kardinalzahl zwischen beiden. Dies bildet den Beginn einer neuen Folge. Die Gesamtheit aller Ordinalzahlen der Kardinalität Aleph-Eins hat eine Grenze, deren Kardinalität Aleph-Zwei ist; allgemein gilt: Für jede Ordinalzahl α gibt es eine Ordinalzahl ωα und eine entsprechende Kardinalzahl Aleph-α.

Cantor interessierte sich besonders für das Verhältnis zwischen der Mächtigkeit des Kontinuums, also der reellen Zahlen, und den Alephs. Er nahm an, dass jede Menge wohlgeordnet werden könne; daraus folgte, dass die Mächtigkeit des Kontinuums einer der Aleph-Zahlen entsprechen müsse. Doch ließ sich weder damals noch heute beweisen, welcher. Sicher ist, dass es nicht Aleph-Null ist, doch keine obere Grenze konnte bestimmt werden. Cantor stellte die berühmte Kontinuumshypothese auf, wonach die Mächtigkeit des Kontinuums Aleph-Eins sei. Wäre dies zutreffend, dann würde folgen, dass jede unendliche Teilmenge der reellen Zahlen entweder abzählbar oder gleichmächtig mit der Menge aller reellen Zahlen ist. Die Kontinuumshypothese hat sich als äußerst tiefgehend erwiesen. Die Ergebnisse von Gödel und Cohen haben gezeigt, dass sie mit den derzeitigen Mitteln der Mengenlehre weder bewiesen noch widerlegt werden kann.