MP: Konstruktion der Zahlenmengen - Teil 1 (Matroids Matheplanet)

Zur Einführung der natürlichen Zahlen und dem 2. Teil dieser Artikelserie stellen wir ein paar einfünhrende Ergebnisse zu Ordinalzahlen zusammen, die hier bis einschließlich Seite 11 weiter ausgeführt werden. Eine \big\darkblue Ordinalzahl \normal\black ist eine Menge \alpha, die transitiv ist, d.h. jedes Element von \alpha ist eine Teilmenge von \alpha, und durch \in wohlgeordnet ist, d.h. für alle x,y,z \in \alpha gilt - Irreflexivität: x \notin x - Trichotomie: x \in y \or y \in x \or x = y - Transitivität: x \in y \in z => x \in z - Jede nichtleere Teilmenge von \alpha hat ein \in-kleinstes Element. Ordinalzahlen kennzeichnen wir stets mit griechischen Buchstaben, und in ihrem Zusammenhang schreiben wir oft < anstatt \in. Jedes Element einer Ordinalzahl ist wieder eine Ordinalzahl, ferner ist S(\alpha) := \alpha \union {\alpha} für jede Ordinalzahl \alpha auch eine Ordinalzahl. Es gilt \alpha \in S(\alpha), also anders notiert \alpha < S(\alpha). Wenn wir nun die ersten Ordinalzahlen 0 := \0 , 1 := S(0), 2 := S(1) , 3 := S(2), ... definieren, so gilt also 0 < 1 < 2 < 3 < ..., wie es anders auch nicht sein sollte. Je zwei Ordinalzahlen durch \in vergleichbar, und bei Isomorphie bereits identisch. Anstatt \alpha<\beta\or\alpha=\beta schreiben wir wie üblich \alpha<=\beta. Dies ist genau dann der Fall, wenn \alpha eine Teilmenge von \beta ist. Somit ist \alpha < S(\beta) mit \alpha <= \beta äquivalent. Jede Wohlordnung M ist zu genau einer Ordinalzahl isomorph, man nennt sie den Ordnungstyp von M und bezeichnet sie mit type(M). Dies waren die Ergebnisse über Ordinalzahlen, die wir hier voraussetzen werden. Ganz entscheidend für die Existenz der Menge der natürlichen Zahlen 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... ist das \big\darkblue Unendlichkeitsaxiom \normal\black in ZF: Es gibt eine induktive Menge. Dabei heißt eine Menge \big\darkblue induktiv \normal\black , wenn sie die 0 enthält und für jedes Element x auch S(x) eines davon ist. Ferner heißt eine Ordinalzahl \alpha \big\darkblue Nachfolgerordinalzahl \normal\black , wenn es eine Ordinalzahl \beta mit \alpha=S(\beta) gibt. \big\darkblue Limesordinalzahlen \normal\black seien die nichtleeren Ordinalzahlen, die keine Nachfolgerordinalzahl sind. Mit diesen Begriffen können wir nun natürliche Zahlen definieren: Eine Ordinalzahl \alpha heißt \big\darkblue natürliche Zahl \normal\black , wenn es keine Limesordinalzahl \beta <= \alpha gibt. Jede nichtleere natürliche Zahl ist eine Nachfolgerzahl. Das bekannte und anschaulich klare Prinzip der vollständigen Induktion sagt aus, dass jede induktive Teilmenge der natürlichen Zahlen die gesamte Menge der natürlichen Zahlen umfasst, die außerdem induktiv ist. Weil wir noch gar nicht wissen, dass diese Menge überhaupt existiert, muss man den ersten Sachverhalt so ausdrücken: Ist \alpha eine natürliche Zahl und x eine induktive Menge, so ist \alpha \in x. Wenn wir das beweisen könnten, so findet man alle natürlichen Zahlen in der nach dem Unendlichkeitsaxiom existierenden induktiven Menge und die Existenz der Menge der natürlichen Zahlen folgt aus dem Ausson- derungsschema in ZF. Nun angenommen, es gibt doch eine natürliche Zahl \alpha und eine induktive Menge x mit \alpha \notin x. Für \alpha \subsetequal x setze \beta = \alpha. Ansonsten gibt es ein kleinstes Element \beta von \alpha - x. So ist \beta = \alpha oder \beta \in \alpha, und sicher \beta \notin x. Wegen 0 \in x ist \beta != 0. Wenn es eine Limesordinalzahl \gamma <= \beta gäbe, so wäre auch \gamma <= \alpha wegen \beta <= \alpha, womit aber \alpha keine natürliche Zahl mehr wäre. Also ist \beta eine nichtleere natürliche Zahl, sodass es eine Ordinalzahl \gamma mit \beta=S(\gamma) gibt. Im Fall \alpha \subsetequal x ist \gamma \in x wegen \gamma \in S(\gamma) = \beta = \alpha. Im anderen Fall ist \gamma \in \beta \in \alpha, also \gamma \in \alpha. Dann würde \gamma \notin x der Minimalität von \beta in \alpha - x widersprechen. In jedem Fall gilt also \gamma \in x. Dann wäre aber auch wegen der Induktivität \beta = S(\gamma) \in x, Widerspruch zu \beta \notin x. Also muss doch \alpha \in x sein. \bigbox Also existiert die Menge der natürlichen Zahlen. Wir bezeichnen sie mit \IN. Wenn man nun eine Aussage \phi(n) für alle n\in\IN beweisen möchte, dann kann man sich also der \big\darkblue vollständigen Induktion \normal\black bedienen: Angenommen man zeigt \phi(0) und \phi(n) => \phi(S(n)). Sei T die Menge aller n\in\IN, die \phi(n) erfüllen. Man hat bereits gezeigt, dass T induktiv ist. Daher ist \IN\subsetequal T, wie wir eben bewiesen haben. Also ist \phi(n) für alle n\in\IN erfüllt. Leicht sieht man ein, dass \IN induktiv und die kleinste Limesordinalzahl ist. Es ist wichtig, dass man Folgen rekursiv definieren kann. Dies sagt der folgende \big\darkblue Dedekindsche Rekursionssatz \normal\black aus: Es sei A eine Menge, a \in A und R eine Abbildung von \IN \cross A in A. Dann gibt es genau eine Abbildung von f von \IN in A mit f(0)=a und f(S(n))=R(n,f(n)) für alle n \in \IN. Zum Beweis setzen wir \nogreeks H={F\subsetequal\IN\cross\A :(0,a)\in\F\and\forall (n,s)\in\F : (S(n),R(n,s))\in\F} \greeks und f = cut(H). Offenbar ist f \in H. Wenn wir zeigen könnten, dass f eine Abbildung ist, so wären wir mit dem Existenz-Beweis schon fertig. Und das bedeutet, dass die Menge X aller n \in \IN, für die es genau ein s \in A mit (n,s) \in f gibt, ganz \IN umfasst, also induktiv ist: Es ist (0,a) \in f. Angenommen es gibt ein b \in A-{a} mit (0,b) \in f. Setze g = f-{(0,b)}. Dann kann man einfach g \in H nachrechnen. Daraus folgt aber der Widerspruch (0,b) \in f \subsetequal g. Damit ist 0 \in X. Nun sei n \in X, es gibt also genau ein s \in A mit (n,s) \in f, also (S(n),R(n,s)) \in f. Um S(n) \in X indirekt zu zeigen, nehmen wir an, dass es ein t \in A - {R(n,s)} mit (S(n),t) \in f gibt. Setze g =f - {(S(n),t)}. Wegen S(n) != 0 ist (0,a) \in g. Sei (m,r) \in g. Es folgt (S(m),R(m,r)) \in f. Für m != n ist S(m) != S(n), also sogar (S(m),R(m,r)) \in g. Für m=n ist f \supseteq g \contains (m,r)=(n,r) und folglich r=s. Wegen R(n,s) != t ist dann auch g \contains (S(m),R(m,r)). Damit haben wir g \in H gezeigt und es folgt der Widerspruch (S(n),t) \in f \subsetequal g. Gibt es eine weitere Abbildung mit den Eigenschaften von f, so muss sie in H liegen und damit f eine Teilmenge davon sein. Dann sind aber, weil sie beide Abbildungen von \IN sind, identisch. Damit ist auch die Eindeu- tigkeit gezeigt und der dedekindsche Rekursionssatz bewiesen. Die all- gemeinere Fassung, die sog. transfinite Rekursion würde hier über das Ziel hinausschießen. Zum Schluss sehen wir noch ein, warum 0,1,2,3,... wirklich genau die natürlichen Zahlen sind. Dies kann überhaupt erst mit dem dedekindschen Rekursionssatz formuliert werden! Damit lässt sich nämlich die n-fache Hintereinanderausführung von Abbildungen definieren, also insbesondere von S bei einer natürlichen Zahl n. Induktion nach n ergibt dann leicht n = S^n(0), und 0,1,2,3,... sind ja gerade die S-Potenzen von 0. Man kann sie formal sogar nur so insgesamt definieren. Was man mit natürlichen Zahlen sonst noch alles anstellen kann, wird hier sehr ausführlich behandelt. Die natürlichen Zahlen können als einzige Grundlage für die weiteren Zahlenmengen angesehen werden, weil wir in den folgenden Teilen dieser Artikelserie nur noch die Eigenschaften der natürlichen Zahlen und nicht mehr konkret ZF benötigen werden. Dies drückte der berühmte Zahlentheoretiker Leopold Kronecker im nachstehenden Zitat aus. Die natürlichen Zahlen hat der liebe Gott erschaffen,
alles andere ist Menschenwerk. So, das war's erst einmal. Im nächsten Teil werden wir sehen, wie man mit unseren natürlichen Zahlen, ja sogar ganz allgemein mit Ordinalzahlen, addiert und multipliziert.