Dedekind-Strukturen
Definition (Dedekind-Struktur)
Sei D eine Menge, d ein Element von D, und sei S : D → D eine injektive Funktion mit d ∉ rng(S). Dann heißt (D, S, d) eine Dedekind-Struktur oder eine Zählreihe, falls für alle X ⊆ D das folgende Induktionsaxiom gilt:
(IndX) Ist d ∈ X und ist mit jedem n ∈ X auch S(n) ∈ X, so ist X = D.
Die Funktion S heißt dann die Nachfolgerfunktion und d die Null der Dedekind-Struktur (D, S, d).
Die wesentlichen Struktureigenschaften sind also:
(a) | d ∉ rng(S). |
(b) | S ist injektiv. |
(c) | Für alle X ⊆ D gilt (IndX). |
Sei X eine Teilmenge von D, etwa X = { n ∈ D | ℰ(n) }. Wir wollen zeigen, dass X = D gilt, d. h. jedes n ∈ D erfüllt die Eigenschaft ℰ(n). Wir zeigen hierzu:
(1) | Es gilt d ∈ X. (Induktionsanfang) |
(2) | Sei n ∈ X. Dann gilt S(n) ∈ X. (Induktionsschritt) |
Haben wir (1) und (2) bewiesen, so ist die Menge X gleich der Menge D nach dem Induktionsaxiom (IndX).
Ein Beweis von X = D nach dem Schema (1) und (2) heißt ein Beweis durch Induktion. Im Induktionsschritt (2) darf man „n ∈ X“ verwenden, um „S(n) ∈ X“ zu zeigen. Diese oft sehr hilfreiche zusätzliche Voraussetzung unterscheidet einen induktiven Beweis von einem Beweis, der direkt zeigt, dass jedes n ∈ D ein Element von X ist. Die Aussage „n ∈ X“ nennt man auch die Induktionsvoraussetzung. Wir kürzen sie zuweilen mit I. V. ab.
Wir erläutern den Einsatz der Induktion in Dedekind-Strukturen an einem einfachen Beispiel.
Satz (die Nachfolgerfunktion hat keine Fixpunkte)
Sei (D, S, d) eine Dedekind-Struktur. Dann gilt S(n) ≠ n für alle n ∈ D.
Beweis
Sei X = { n ∈ D | S(n) ≠ n }. Wir zeigen, dass X die Voraussetzungen des Induktionsaxioms erfüllt. Nach (IndX) gilt dann X = D.
Induktionsanfang:
Es gilt S(d) ≠ d, da sonst d im Wertebereich von S liegen würde.
Also ist d ∈ X.
Induktionsschritt von n nach S(n):
Es gelte also n ∈ X (die Induktionsvoraussetzung). Dann gilt S(n) ≠ n.
Da S injektiv ist, haben also S(n) und n verschiedene Nachfolger.
Also gilt S(S(n)) ≠ S(n), d. h. S(n) ∈ X.
Mit Induktion zeigt man z. B. auch, dass rng(S) = D − { d } gilt.
Dem induktiven Beweisen in einer Dedekind-Struktur (D, S, d) steht das rekursive Definieren zur Seite: Wir können eine Funktion f mit Definitionsbereich D definieren, indem wir zunächst f (d) festlegen, und dann weiter für alle n ∈ D festlegen, wie sich f (S(n)) aus f (n) ergibt, d. h. wir dürfen zur Definition von f (S(n)) den Funktionswert f (n) verwenden. Die Funktionswerte können dabei Elemente von D sein, oder auch beliebige Objekte wie z. B. endliche Folgen in D.
Ein Blick auf das Induktionsaxiom macht es glaubhaft, dass dadurch in eindeutiger Weise eine Funktion definiert wird, deren Definitionsbereich die Menge D ist. Eine strenge Rechtfertigung des rekursiven Definierens ist möglich, wir wollen hier aber darauf verzichten.
Schematisch verläuft eine rekursive Definition also wie folgt:
(1) | Wir definieren f (d). (Rekursionsanfang) |
(2) | Wir definieren f (S(n)) unter Verwendung von f (n). (Rekursionsschritt) |
Dadurch wird eine eindeutige Funktion f mit dom(f) = D definiert.
Die Rekursion wird verwendet, um den folgenden fundamentalen Satz zu beweisen, der besagt, dass es bis auf Isomorphie nur eine Dedekind-Struktur gibt. Der Leser kann beim ersten Lesen den Beweis überschlagen.
Satz (Eindeutigkeitssatz für Dedekind-Strukturen)
Je zwei Dedekind-Strukturen (D, S, d) und (E, T, e) sind isomorph, d. h. es gibt eine Bijektion i : D → E mit den Eigenschaften:
(i) | i(d) = e, |
(ii) | i(S(n)) = T(i(n)) für alle n ∈ D. |
Beweis
Wir definieren eine Funktion i : D → E mit Hilfe von Rekursion über die Dedekind-Struktur (D, S, d):
i(d) = e, (Rekursionsanfang)
i(S(n)) = T(i(n)) für alle n ∈ D. (Rekursionsschritt)
Dann gelten die Eigenschaften (i) und (ii) nach Konstruktion. Es ist also nur noch zu zeigen, dass i : D → E bijektiv ist. Wir beginnen mit:
(+) i : D → E ist surjektiv.
Beweis von (+)
Sei Y = rng(i). Dann gilt e ∈ Y. Ist y ∈ Y, so gibt es ein n ∈ D mit i(n) = y. Dann ist aber T(y) = i(S(n)) ∈ Y. Nach dem Induktionsaxiom (IndY) für die Dedekind-Struktur (E, T, e) gilt also Y = E.
Weiter zeigen wir nun:
(++) i ist injektiv.
Beweis von (++)
Wir zeigen durch Induktion nach n ∈ D:
(#) Für alle m ∈ D gilt: Ist m ≠ n, so ist i(m) ≠ i(n).
Induktionsanfang n = d
Für alle m ≠ d gilt i(m) ≠ i(d) = e, denn ist m = S(m′), so ist i(m) = i(S(m′)) = T(i(m′)) ≠ e, da e ∉ rng(T).
Induktionsschritt von n nach S(n)
Wir müssen zeigen, dass für alle m ∈ D gilt:
Ist m ≠ S(n), so ist i(m) ≠ i(S(n)), wobei i(S(n)) = T(i(n)).
Dies ist klar für m = d, da dann wieder i(m) = e ∉ rng(T) gilt.
Sei also m = S(m′) und es gelte m ≠ S(n). Dann gilt S(m′) ≠ S(n), und damit m′ ≠ n. Also ist i(m′) ≠ i(n) nach Induktionsvoraussetzung. Dann ist aber T(i(m′)) ≠ T(i(n)) nach Injektivität von T, also wie gewünscht
i(m) = i(S(m′)) = T(i(m′)) ≠ T(i(n)) = i(S(n)).
Damit haben wir also den richtigen Begriff gefunden − vorausgesetzt, wir können auch einen Existenzsatz nachreichen, der sicherstellt, dass es überhaupt eine Dedekind-Struktur gibt. Die Konstruktion einer solchen Struktur ist eine Aufgabe der Mengenlehre. Eine Möglichkeit, die alles aus der leeren Menge gewinnt, ist die folgende:
Wir definieren die Menge D als die kleinste Menge, die die leere Menge als Element enthält, und die mit jedem n auch die Menge n ∪ { n } als Element enthält. Wir setzen dann d = ∅ und S(n) = n ∪ { n } für alle n ∈ D. Dann ist, wie man zeigen kann, (D, S, d) eine Dedekind-Struktur. Die Existenz der Menge D wird dabei durch das sog. Unendlichkeitsaxiom der Mengenlehre sichergestellt, das im Wesentlichen direkt fordert, dass D existiert. Bei diesem Vorgehen gilt dann:
0 = ∅,
1 = S(0) = 0 ∪ { 0 } = { 0 },
2 = S(1) = 1 ∪ { 1 } = { 0, 1 },
3 = S(2) = 2 ∪ { 2 } = { 0, 1, 2 },
…
S(n) = n ∪ { n } = { 0, …, n }.
Jede natürliche Zahl ist hier also identisch mit der Menge der natürlichen Zahlen, die durch den Zählprozess bis hin zu n entstanden sind. Insbesondere hat jede natürliche Zahl n genau n verschiedene Elemente, und die ∈ -Relation übernimmt die Rolle der Ordnung < auf den natürlichen Zahlen.
Viele andere Konstruktionen sind möglich. Als Nachfolgerbildung können wir z. B. auch S(n) = { n } wählen. Dann ist 0 = ∅, 1 = { 0 }, 2 = { 1 } = { { ∅ } }, usw. Weiter ist auch eine Konstruktion der Form 0 = ∅, 1 = (0), 2 = (0, 0), 3 = (0, 0, 0), usw. denkbar, die vielleicht am ehesten der Vorstellung |, ||, |||, … entspricht.
In allen Fällen erhalten wir eine Dedekind-Struktur, und nach dem Isomorphiesatz sind alle Zugänge prinzipiell gleichwertig. Die spezielle Nachfolgerbildung S(n) = n ∪ { n } besticht allerdings durch ihre guten Eigenschaften und gilt heute als der kanonische Ansatz zur Definition der natürlichen Zahlen innerhalb einer mengentheoretischen Umgebung.
Die natürlichen Zahlen
Wir nehmen im folgenden irgendeine feste Dedekind-Struktur (ℕ, S, d) als gegeben an und nennen die Elemente von ℕ natürliche Zahlen. Wir verwenden die üblichen Zahlzeichen:
0 = d, 1 = S(0), 2 = S(1) = S(S(d)), 3 = S(2), usw.
Bei der Einführung der Arithmetik und der Ordnung auf ℕ greifen wir nur auf die Struktur-Eigenschaften von Dedekind-Strukturen zurück und nicht auf die Eigenheiten einer speziellen Konstruktion.