Natürliche Zahlen als Mengen
Von fundamentaler Bedeutung für die Mathematik ist das Zahlsystem von den natürlichen Zahlen bis zu den reellen und komplexen Zahlen. Auf John von Neumann geht der folgende Ansatz zurück, bei dem eine natürliche Zahl als die Menge ihrer Vorgänger definiert wird:
0 = ∅,
1 = 0 ∪ { 0 } = { 0 },
2 = 1 ∪ { 1 } = { 0, 1 },
3 = 2 ∪ { 2 } = { 0, 1, 2 } ,
n + 1 = n ∪ { n } = { 0, …, n }.
Um die Menge aller natürlichen Zahlen zu erhalten, brauchen wir das Unendlichkeitsaxiom. Wir nennen eine Menge a induktiv, falls gilt:
∅ ∈ a ∧ ∀b ∈ a b ∪ { b } ∈ a.
Das Unendlichkeitsaxiom besagt schlicht: Es existiert eine induktive Menge. Anschaulich wollen wir in den natürlichen Zahlen aber nur diejenigen Elemente haben, die aus der Null durch schrittweise Nachfolgerbildung entstehen. In einer induktiven Menge können noch andere Elemente enthalten sein. Die einzige Möglichkeit, unnötigen Ballast zu entfernen, ist die Schnittbildung. Ist a irgendeine induktive Menge, so setzen wir:
ℕ = ω = ⋂ { b ⊆ a | b induktiv } = { c ∈ a | ∀b ⊆ a (b induktiv → c ∈ b }.
Man kann zeigen, dass die Menge ℕ induktiv ist und dass die Definition nicht von der Wahl von a abhängt. Das Ergebnis lässt sich axiomatisch charakterisieren. Hierzu definieren wir:
Definition (Dedekind-Struktur)
Seien D eine Menge, 0 ∈ D und S : D → D injektiv derart, das 0 nicht im Wertebereich von S liegt. Dann heißt (D, S, 0) eine Dedekind-Struktur, falls für alle A ⊆ D gilt:
0 ∈ A ∧ ∀n ∈ A S(n) ∈ A → A = D.(Induktionsaxiom für D)
Die Funktion S heißt die Nachfolgerfunktion und 0 das Anfangselement von (D, S, 0). Die Elemente von D heißen die Zahlen der Struktur.
Jede Zahl n ∈ D hat einen eindeutigen Nachfolger S(n) (da S eine Funktion ist). Die Zahl 0 ist kein Nachfolger einer Zahl (da 0 ∉ S[ D ]). Haben zwei Zahlen denselben Nachfolger, so sind sie gleich (da S injektiv ist). Zudem gilt das Induktionsprinzip (in der Formulierung für Mengen). Diese auch als Peano-Axiome bekannten Aussagen sind zuerst von Dedekind betrachtet worden.
In einer Dedekind-Struktur (D, S, 0) können wir so arbeiten, wie wir es in den als gegeben betrachteten natürlichen Zahlen tun. Die Arithmetik wird für alle Zahlen m ∈ D rekursiv definiert durch
| m + 0 = m, | m + S(n) = S(m + n) | für alle n ∈ D |
| m · 0 = 0, | m · S(n) = m · n + m | für alle n ∈ D |
| m0 = S(0), | mn + 1 = mn · m | für alle n ∈ D |
Das rekursive Definieren lässt sich mit den Axiomen der Mengenlehre rechtfertigen. Die Formulierung und der (noch nicht auf Axiome gestützte) Beweis eines allgemeinen Rekursionssatzes gehen ebenfalls auf Dedekind zurück.
Weiter können wir eine Ordnung erklären vermöge
m ≤ n falls ∃k ∈ D m + k = n.
Mit Hilfe der Induktionsaxiome können wir alle vertrauten Eigenschaften der Arithmetik und Ordnung nachweisen, etwa
∀m, n ∈ D m + n = n + m, ∀m, n ∈ D (n < m ∨ n = m ∨ m < n).
Zudem gilt folgender Eindeutigkeitssatz:
Satz (Eindeutigkeitssatz für Dedekind-Strukturen)
Je zwei Dedekind-Strukturen (D, S, 0) und (E, T, e) sind isomorph, d. h. es gibt eine Bijektion f : D → E mit f (0) = e und f (S(n)) = T(f (n)) für alle n ∈ D.
Beweiskizze
Wir definieren f : D → E rekursiv durch
f (0) = e,
f (S(n)) = T(f (n)) für alle n ∈ D.
Mit Hilfe der Induktionsaxiome zeigen wir, dass f : D → E bijektiv ist. Die anderen Eigenschaften gelten nach Konstruktion.
Ein Isomorphismus f : D → E zwischen zwei Dedekind-Strukturen.
Dabei schreiben wir kurz Sn statt S(n) und Tn statt T(n).
Der Eindeutigkeitssatz hätte wenig Wert ohne einen Existenzsatz:
Satz (Existenzsatz für Dedekind-Strukturen)
Die Struktur (ℕ, S, 0) mit S(n) = n ∪ { n } und 0 = ∅ ist eine Dedekind-Struktur.
In den natürlichen Zahlen ℕ ist die Ordnung aufgrund der von Neumann Nachfolger-Bildung
S(n) = n + 1 = n ∪ { n } = { 0, …, n }
besonders einfach: Es gilt m < n genau dann, wenn m ∈ n. Die ∈ -Relation ist also eine lineare Ordnung und genauer eine Wohlordnung auf ℕ. Insbesondere ist ∈ transitiv auf den natürlichen Zahlen: Für alle k ∈ m und m ∈ n gilt k ∈ n. Jedes n ∈ ℕ besitzt also die bemerkenswerte Eigenschaft:
(+) Für alle m ∈ n gilt m ⊆ n.(Transitivität von n bzgl. ∈ )
Die Eigenschaft (+) können wir auch in der Form n ⊆ ℘(n) notieren.
Damit sind die natürlichen Zahlen elegant definiert und bis auf Isomorphie charakterisiert. Die Gültigkeit der Induktionsaxiome für (ℕ, S, 0) wird mit Hilfe der ZFC Axiome bewiesen. Die Induktion ist aus der Sicht der Mengenlehre also kein Beweisprinzip oder Axiom, sondern ein beweisbarer Satz.
Die relative Widerspruchsfreiheit der Zahlentheorie
Da in ZFC mit (ℕ, S, 0) ein Modell der Zahlentheorie (der von Dedekind stammenden Peano-Axiome) konstruiert werden kann, folgt aus logischen Gründen: ZFC beweist die Widerspruchsfreiheit der Zahlentheorie. Das heißt noch nicht, dass die Zahlentheorie widerspruchsfrei ist. Jeder Widerspruch in der Zahlentheorie würde aber zeigen, dass ZFC widersprüchlich ist. Man spricht in der Logik auch von relativer Widerspruchsfreiheit: Die Zahlentheorie ist widerspruchsfrei relativ zu ZFC. Aufgrund des zweiten Gödelschen Unvollständigkeitssatzes kann die Zahlentheorie ihre eigene Widerspruchsfreiheit nicht beweisen (es sei denn, sie ist widerspruchsvoll). Die Theorie ZFC hat in diesem Sinne eine höhere Konsistenzstärke als die Zahlentheorie. Jedoch kann auch die Theorie ZFC ihre eigene Widerspruchsfreiheit nicht beweisen (es sei denn, ZFC ist widerspruchsvoll), sodass zum Beweis der Widerspruchsfreiheit von ZFC noch stärkere Theorien betrachtet werden müssen, bei denen sich dann wieder die Frage nach ihrer Widerspruchsfreiheit stellt.
Streicht man das Unendlichkeitsaxiom aus ZFC und fügt man statt dessen seine Verneinung hinzu, so ergibt sich eine Version der Zahlentheorie, die neben den Zahlen 0, 1, 2, … auch endliche Mengen wie { 0, 1, { 2 } } enthält. Eine Welt des Endlichen, in der man sprachlich so flexibel ist wie in der unendlichen Mengenlehre. Die axiomatische Mengenlehre wurde zur Untersuchung des Unendlichen entwickelt, ist aber auch im Endlichen nützlich.