Isomorphiesatz von Dedekind

Der Isomorphiesatz von Dedekind, benannt nach Richard Dedekind, ist ein mathematischer Satz, der eine Eindeutigkeitsaussage über die natürlichen Zahlen, wie sie durch die Peano-Axiome definiert sind, trifft. Diese Aussage findet sich in Dedekinds klassischem Buch "Was sind und was sollen die Zahlen?" aus dem Jahre 1888 als Satz 132 in folgender Formulierung:

• Alle einfach unendlichen Systeme sind der Zahlenreihe N und folglich auch einander ähnlich.[1]

Einfach unendliche Systeme n​ennt man h​eute Peano-Systeme, s​tatt ähnlich s​agt man h​eute isomorph. Die folgende Darstellung verwendet d​iese moderneren Begriffe u​nd ergänzt einige logische Aspekte dieses Satzes.

Einführung

Die Eigenschaften der natürlichen Zahlen sind von Giuseppe Peano axiomatisch durch die folgenden sogenannten Peano-Axiome charakterisiert worden.[2] Ein Peano-System ist eine Menge ${\displaystyle N}$ mit folgenden Eigenschaften

1. Es gibt ein Element ${\displaystyle 0\in N}$ (dieses Element spielt die Rolle der 0)
2. Es gibt eine Abbildung ${\displaystyle \sigma \colon N\rightarrow N}$ (Nachfolgerabbildung)
3. ${\displaystyle \forall n\in N:\sigma (n)\not =0}$ (0 ist kein Nachfolger)
4. ${\displaystyle \sigma }$ ist injektiv (verschiedene Elemente haben verschiedene Nachfolger)
5. Ist ${\displaystyle X\subseteq N}$ eine Teilmenge mit ${\displaystyle 0\in X}$ und ${\displaystyle \forall n\in N\colon (n\in X\rightarrow \sigma (n)\in X)}$, so folgt ${\displaystyle X=N}$ (Vollständige Induktion)

Genauer bezeichnet man dieses Peano-System mit ${\displaystyle (N,0,\sigma )}$. In Klammern steht jeweils die Bedeutung der Axiome.

Daraus lässt sich die gesamte Theorie der natürlichen Zahlen aufbauen. Daher stellt sich die Frage nach der Eindeutigkeit der Peano-Systeme. Diese Frage wird positiv durch den hier zu besprechenden Isomorphiesatz von Dedekind beantwortet. Natürlich kann man durch Abänderung von Bezeichnungen mehrere Peano-Systeme erhalten, aber diese erweisen sich als im Wesentlichen gleich. Zur Präzisierung dieser Art von Eindeutigkeit muss man festlegen, wann man zwei Peano-Systeme als im Wesentlichen gleich ansehen will, und dazu dient der Begriff des Isomorphismus, der nun geklärt werden soll.

Zur Symbolisierung obiger Axiome wurden ein Konstantensymbol 0 und ein Funktionssymbol ${\displaystyle \sigma }$-verwendet, ein Peano-System ist also eine ${\displaystyle \{0,\sigma \}}$-Struktur mit obigen Eigenschaften. Unter einem Isomorphismus zwischen Peano-Systemen versteht man daher eine bijektive Abbildung, die diese Strukturelemente erhält, genauer:

Ein Isomorphismus zwischen zwei Peano-Systemen ${\displaystyle (N,0,\sigma )}$ und ${\displaystyle ({\tilde {N}},{\tilde {0}},{\tilde {\sigma }})}$ ist eine bijektive Abbildung ${\displaystyle f\colon N\rightarrow {\tilde {N}}}$ mit folgenden zwei Eigenschaften:

• ${\displaystyle f(0)={\tilde {0}}}$
• ${\displaystyle \forall n\in N\colon f(\sigma (n))={\tilde {\sigma }}(f(n))}$.

Leicht z​eigt man, d​ass die Umkehrabbildung dieselben Eigenschaften hat. Zwei Peano-Systeme heißen isomorph, w​enn es e​inen Isomorphismus zwischen i​hnen gibt.

Ein konkretes Peano-System lässt sich wie folgt konstruieren. Definiert man ${\displaystyle 0=\emptyset }$, für jede Menge ${\displaystyle a}$ die sogenannte Nachfolger-Menge ${\displaystyle s(a):=a\cup \{a\}}$ und ${\displaystyle \mathbb {N} }$ als Durchschnitt aller Mengen, die 0 und mit jedem ${\displaystyle a}$ auch ${\displaystyle s(a)}$ enthalten, so ist ${\displaystyle (\mathbb {N} ,0,s|_{\mathbb {N} })}$ ein Peano-System, das man kurz mit ${\displaystyle \mathbb {N} }$ bezeichnet. Dies ist die in der Mengenlehre übliche Konstruktion der natürlichen Zahlen.

Formulierungen des Satzes

• Je zwei Peano-Systeme sind isomorph.

Da wir mit ${\displaystyle \mathbb {N} }$ ein konkretes Peano-System angegeben haben, können wir äquivalent umformulieren:

• Jedes Peano-System ist isomorph zu ${\displaystyle \mathbb {N} }$.[3][4]

Bemerkungen

Die o​ben gegebene Definition verwendet d​ie Prädikatenlogik zweiter Stufe, d​enn die formale Wiedergabe d​es Induktionsaxioms lautet

${\displaystyle \forall X\,((0\in X\land \forall n\,(Xn\rightarrow X\sigma (n)))\rightarrow \forall n\,Xn)}$.

Die Schreibweise ${\displaystyle Xn}$ bedeutet in jeder Interpretation, dass ${\displaystyle n}$ in der Teilmenge ${\displaystyle X}$ enthalten ist.

Hier wird also über die einstellige Relation ${\displaystyle X}$ quantifiziert, und das ist in der Prädikatenlogik erster Stufe nicht möglich. Tatsächlich gibt es zu ${\displaystyle \mathbb {N} }$ elementar äquivalente aber nicht isomorphe Strukturen, das heißt diese und ${\displaystyle \mathbb {N} }$ erfüllen dieselben in der Prädikatenlogik erster Stufe formulierbaren Aussagen, sind aber dennoch nicht isomorph. Solche Strukturen nennt man Nichtstandardmodelle. Nach dem Satz von Skolem gibt es sogar abzählbare Nichtstandardmodelle.[5]

Ersetzt m​an also d​as Induktionsaxiom 5 d​urch die unendlich vielen Axiome

${\displaystyle (\varphi (0)\land \forall n\,(\varphi (n)\rightarrow \varphi (\sigma (n)))\rightarrow \forall n\,\varphi (n)}$,

das heißt für jede ${\displaystyle \{0,\sigma \}}$-Formel ${\displaystyle \varphi }$ der Prädikatenlogik erster Stufe mit einer freien Variable hat man ein Axiom, so erhält man die sogenannte Peano-Arithmetik. Die Existenz abzählbarer Nichtstandardmodelle zeigt also, dass der Satz von Dedekind nicht auf die Peano-Arithmetik übertragen werden kann. Dieses historisch überraschende Resultat wird plausibel, wenn man bedenkt, dass es nur abzählbar viele ${\displaystyle \{0,\sigma \}}$-Formeln gibt und man daher nur abzählbar viele Induktionsaxiome in der Peano-Arithmentik hat. Das Induktionsaxiom 5 trifft aber eine Aussage über alle Teilmengen eines Peano-Systems, und das sind überabzählbar viele, ist also formal stärker.

Wie oben erwähnt kann man die natürlichen Zahlen in der Mengenlehre konstruieren, das heißt man kann sie mit dem Symbol ${\displaystyle \in }$ in der Sprache der Prädikatenlogik erster Stufe definieren und auch der Satz von Dedekind wird beweisbar. Das widerspricht nicht obigen Ausführungen zum Satz von Skolem. Letzterer bezieht sich auf Peano-Systeme in der Prädikatenlogik erster Stufe, in dieser kann man nur über die Elemente der Grundklasse quantifizieren und da gehören die Teilmengen der Grundklasse nicht dazu. In der Mengenlehre ist die Grundklasse aber das gesamte Mengenuniversum, das heißt das Induktionsaxiom lässt sich mittels Quantifizierung über die Elemente der Grundklasse beschreiben:

${\displaystyle \forall x\,((\emptyset \in x\land \forall y\,(y\in x\rightarrow y\cup \{y\}\in x))\rightarrow \mathbb {N} \subset x)}$

Dazu beachte, dass die Symbole ${\displaystyle \emptyset ,\cup ,\{y\},\mathbb {N} ,\subset }$ mittels ${\displaystyle \in }$ definierbar sind, auf diese könnte also auf Kosten der leichteren Lesbarkeit prinzipiell verzichtet werden, so dass es sich tatsächlich um eine ${\displaystyle \in }$-Aussage handelt. Damit ist der Beweis zum Satz von Dedekind übertragbar.[6][7]

Einzelnachweise

1. R. Dedekind: Was sind und was sollen die Zahlen?, 1. Auflage, Vieweg, Braunschweig 1888, Satz 132
2. G. Peano: Opere scelte III, S. 216, original mit Operator n+ statt σ(n)
3. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, III, Satz 7.4
4. Dirk W. Hoffmann: Die Gödel’schen Unvollständigkeitssätze: Eine geführte Reise durch Kurt Gödels historischen Beweis, Springer-Verlag (2013), ISBN 3-827-43000-3, Satz 2.3: Isomorphiesatz von Dedekind
5. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, VI, Satz 4.6
6. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, Kapitel VII: Zur Tragweite der ersten Stufe
7. Dirk Siefkes: Formalisieren und Beweisen: Logik für Informatiker, Springer-Verlag (2013), ISBN 3-322-85621-6, Ausführungen ab Seite 218.