Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 12/latex
\setcounter{section}{12}
Wir haben bisher nur Axiomensysteme in Sinne einer beliebigen Ausdrucksmenge
\mathl{\Gamma \subseteq L^S}{} gesprochen, die im Allgemeinen eine Vielzahl von Modellen besitzt und aus der gewisse Ableitungen bzw. Folgerungen gezogen werden können, die für alle Modelle gelten. Es gibt aber auch Axiomensysteme, mit denen man ein intendiertes mathematisches Objekt wie beispielsweise die vertrauten natürlichen Zahlen charakterisieren möchte. Die natürlichen Zahlen haben wir bisher nur zum Indizieren von Aussage- oder Termvariablen verwendet
\zusatzklammer {wobei wir an einzelnen Stellen Induktion über die natürlichen Zahlen geführt haben} {} {}
und als wichtige Quelle für offene mathematische Probleme erwähnt. Hier sprechen für von Axiomensystemen für die natürlichen Zahlen, und zwar sowohl von zweitstufigen als auch von erststufigen. Der Sprachgebrauch ist in der Literatur nicht einheitlich, wir werden von den
\zusatzklammer {zweitstufigen} {} {}
\stichwort {Dedekind-Peano-Axiomen} {} und den erststufigen \stichwort {Peano-Axiomen} {} sprechen.
\zwischenueberschrift{Dedekind-Peano-Axiome}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Dedekind.jpeg} }
\end{center}
\bildtext {Richard Dedekind (1831 - 1916)} }
\bildlizenz { Dedekind.jpeg } {unbekannt} {Jean-Luc W} {Commons} {PD} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Giuseppe_Peano.jpg} }
\end{center}
\bildtext {Giuseppe Peano (1858 - 1932)} }
\bildlizenz { Giuseppe Peano.jpg } {unbekannt} {Kalki} {Commons} {PD} {}
Wir besprechen nun die Dedekind-Peano-Axiome, eine zweitstufige Axiomatik, die eine vollständige Charakterisierung der natürlichen Zahlen erlauben.
\inputaxiom
{}
{
Eine Menge $N$ mit einem ausgezeichneten Element
\mavergleichskette
{\vergleichskette
{0
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {die \stichwort {Null} {}} {} {}
und einer
\zusatzklammer {Nachfolger} {} {-}Abbildung
\maabbeledisp {'} { N} {N
} {n} {n'
} {,}
heißt \definitionswort {natürliche Zahlen}{} \zusatzklammer {oder \stichwort {Dedekind-Peano-Modell} {} für die natürlichen Zahlen} {} {,}
wenn die folgenden
\definitionswortenp{Dedekind-Peano-Axiome}{} erfüllt sind.
\aufzaehlungdrei{Das Element $0$ ist kein Nachfolger
\zusatzklammer {die Null liegt also nicht im Bild der Nachfolgerabbildung} {} {.}
}{Jedes
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist Nachfolger höchstens eines Elementes
\zusatzklammer {d.h. die Nachfolgerabbildung ist injektiv} {} {.}
}{Für jede Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt: Wenn die beiden Eigenschaften
\auflistungzwei{
\mavergleichskette
{\vergleichskette
{0
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
}{mit jedem Element
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist auch
\mavergleichskette
{\vergleichskette
{n'
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
}
gelten, so ist
\mavergleichskette
{\vergleichskette
{T
}
{ = }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
} Mit zweitstufig ist gemeint, dass nicht nur über die Elemente der Menge $N$, die man axiomatisch charakterisieren will, quantifiziert wird, sondern \zusatzklammer {im dritten sogenannten \stichwort {Induktionsaxiom} {}} {} {} auch über beliebige Teilmengen dieser Menge. Eine solche Situation wird erststufig nicht \zusatzklammer {zumindest nicht unmittelbar} {} {} erfasst\zusatzfussnote {Eine andere wichtige Frage ist, inwiefern man in der ersten Stufe zweitstufige Phänome nachbilden kann. Das ist weitgehend möglich} {.} {.} Mit dieser Axiomatik werden wir zeigen, dass je zwei Modelle für diese zweistufigen Dedekind-Peano-Axiome \anfuehrung{isomorph}{} sind, dass es also zwischen ihnen eine strukturerhaltende Bijektion gibt, und dass man ausgehend von der Nachfolgerfunktion die Addition und die Multiplikation rekursiv einführen kann.
Die folgende Aussage ist das \stichwort {induktive Definitionsprinzip für Abbildungen} {.}
\inputfaktbeweis
{Natürliche Zahlen/Induktionsprinzip zur Definition von Abbildungen/Fakt}
{Satz}
{}
{
\faktsituation {Es sei
\mathl{(N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen und es sei $M$ eine Menge mit einem fixierten Element
\mavergleichskette
{\vergleichskette
{s
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und einer
\definitionsverweis {Abbildung}{}{}
\maabb {F} {M} {M
} {.}}
\faktfolgerung {Dann gibt es genau eine Abbildung
\maabbeledisp {\varphi} {N} {M
} {n} {\varphi(n)
} {,}
die die beiden Eigenschaften
\mathdisp {\varphi(0) = s \text{ und } \varphi(n^\prime) = F ( \varphi(n)) \text { für alle } n \in \N} { }
erfüllt.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir betrachten Teilmengen
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit den Eigenschaften
\aufzaehlungdrei{
\mavergleichskette
{\vergleichskette
{0
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Für jedes
\mathbed {n \in S} {,}
{n \neq 0} {}
{} {} {} {,}
gibt es ein
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{n
}
{ = }{k'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Es gibt eine eindeutig bestimmte Abbildung
\maabbdisp {\varphi_S} {S} {M
} {}
mit
\mavergleichskette
{\vergleichskette
{\varphi_S(0)
}
{ = }{ s
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{\varphi_S (n')
}
{ =} { F( \varphi_S (n) )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ n,n'
}
{ \in }{ S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Wir betrachten nun die Menge
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{T
}
{ =} { { \left\{ k \in N \mid \text{Es gibt ein } S \text{ mit den beschriebenen Eigenschaften und mit } k \in S \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir zeigen durch Induktion, dass
\mavergleichskette
{\vergleichskette
{T
}
{ = }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Für
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
können wir
\mavergleichskettedisp
{\vergleichskette
{S
}
{ =} {\{0\}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
wählen, wobei $\varphi_{ \{0\} }$ durch die erste Abbildungseigenschaft eindeutig festgelegt ist. Es sei nun
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vorausgesetzt. Das bedeutet, dass es
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und eine Abbildung $\varphi_S$ mit den angegebenen Eigenschaften gibt. Bei
\mavergleichskette
{\vergleichskette
{k'
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind wir fertig, sei also
\mavergleichskette
{\vergleichskette
{k'
}
{ \notin }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir setzen
\mavergleichskette
{\vergleichskette
{S'
}
{ = }{ S \cup \{k'\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und wir definieren
\mavergleichskettedisp
{\vergleichskette
{ \varphi_{S'} ( n)
}
{ =} { \begin{cases} \varphi_{S} ( n)\, , \text{ falls } n \in S \, , \\ F(\varphi_S(k)) \, , \text{ falls } n = k' \, .\end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Dies erfüllt die Eigenschaften und ist auch die einzige Möglichkeit, da die Einschränkung von
\mathl{\varphi_{S'}}{} auf $S$ wegen der Eindeutigkeit mit $\varphi_S$ übereinstimmen muss. Also ist
\mavergleichskette
{\vergleichskette
{T
}
{ = }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir zeigen nun durch Induktion über $k$, dass
\mathl{\varphi_S(k)}{} unabhängig von der gewählten Menge
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Bei
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist dies klar, sei diese Aussage für ein gewisses $k$ schon bekannt, und sei
\mavergleichskette
{\vergleichskette
{k'
}
{ \in }{ S_1, S_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit zugehörigen Abbildungen
\mathl{\varphi_1=\varphi_{S_1},\varphi_2=\varphi_{S_2}}{.} Aufgrund der zweiten Eigenschaft ist
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{ S_1, S_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
daher ist nach Induktionsvoraussetzung
\mavergleichskettedisp
{\vergleichskette
{ \varphi_1(k')
}
{ =} { F( \varphi_1 (k))
}
{ =} { F( \varphi_2 (k))
}
{ =} { \varphi_2(k')
}
{ } {
}
}
{}{}{.}
Damit erhält man durch
\mavergleichskettedisp
{\vergleichskette
{\varphi(k)
}
{ \defeq} { \varphi_S(k)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit einem beliebigen
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine wohldefinierte Abbildung auf ganz $N$ mit den in der Formulierung des Satzes geforderten Eigenschaften. Die Eindeutigkeit von $\varphi$ ergibt sich aus der Eindeutigkeit der Einschränkungen.
\inputfaktbeweis
{Natürliche Zahlen/Dedekind-Peano/Eindeutige Isomorphie/Fakt}
{Satz}
{}
{
\faktsituation {Es seien
\mathkor {} {N_1} {und} {N_2} {}
\definitionsverweis {Dedekind-Peano-Modelle}{}{}
für die natürlichen Zahlen.}
\faktfolgerung {Dann gibt es eine eindeutig bestimmte
\definitionsverweis {bijektive Abbildung}{}{}
\maabbdisp {\varphi} {N_1} {N_2
} {}
mit
\mavergleichskette
{\vergleichskette
{\varphi (0_1)
}
{ = }{ 0_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{\varphi(n')
}
{ =} { (\varphi(n))'
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{N_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {Insbesondere sind je zwei Dedekind-Peano-Modelle isomorph.}
\faktzusatz {}
}
{
Aufgrund von
Satz 12.2,
angewendet auf $N_1$ und die Nachfolgerabbildung auf $N_2$,
gibt es genau eine Abbildung
\maabbdisp {\varphi} {N_1} {N_2
} {}
mit den angegebenen Eigenschaften. Wenn man die Rollen vertauscht, so erhält man eine eindeutige Abbildung
\maabbdisp {\psi} {N_2} {N_1
} {}
mit den gleichen Eigenschaften. Wir betrachten nun die Verknüpfung
\maabbdisp {\psi \circ \varphi} {N_1} {N_1
} {.}
Diese erfüllt ebenfalls diese Eigenschaften. Da aber die Identität auf $N_1$ auch diese Eigenschaften erfüllt, folgt aus der Eindeutigkeitsaussage aus
Satz 12.2,
dass
\mavergleichskette
{\vergleichskette
{ \psi \circ \varphi
}
{ = }{
\operatorname{Id}_{ N_1 }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Ebenso ist
\mavergleichskette
{\vergleichskette
{ \varphi \circ \psi
}
{ = }{
\operatorname{Id}_{ N_2 }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit sind
\mathkor {} {\varphi} {und} {\psi} {}
invers zueinander.
Für das im Wesentlichen eindeutig bestimmte Modell der Dedekind-Peano-Axiome verwenden wir das Symbol $\N$ und sprechen von den \stichwort {natürlichen Zahlen} {.}
\zwischenueberschrift{Addition auf natürlichen Zahlen}
Wir wollen die Addition auf den natürlichen Zahlen definieren, und zwar ausgehend von den Dedekind-Peano-Axiomen. Die Addition mit $0$ soll dabei das Element wiedergeben
\zusatzgs {d.h. $0$ soll das neutrale Element der Addition sein} {}
und die Addition eines Elementes $n$ mit
\mavergleichskette
{\vergleichskette
{1
}
{ \defeq }{0'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
soll der Nachfolger von $n$ sein. Die Grundidee ist dabei, die Summe
\mathl{n+k}{} dadurch zu definieren, dass man sukzessive den ersten Summanden um eins erhöht
\zusatzklammer {also den Nachfolger nimmt} {} {}
und den zweiten um eins vermindert
\zusatzklammer {also den Vorgänger nimmt, falls
\mavergleichskettek
{\vergleichskettek
{k
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist} {} {.}
Man spricht vom \stichwort {Umlegungsprinzip} {}
\zusatzklammer {oder Umlegungsmodell} {} {}
für die Addition. Um dies präzise durchzuführen verwenden wir das
induktive Definitionsprinzip für Abbildungen.
Wir wenden dieses Prinzip für die Nachfolgerabbildung und für eine natürliche Zahl
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als Startglied an. Die daraus gewonnene Abbildung beschreibt das Addieren mit dieser Zahl $n$
\zusatzklammer {es wird also die zweistellige Addition auf einstellige Operationen zurückgeführt} {} {.}
\inputdefinition
{}
{
Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen und
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann definieren wir die \stichwort {Addition mit $n$} {} als diejenige aufgrund von
Satz 12.2
eindeutig bestimmte Abbildung
\maabbeledisp {\alpha_n} {\N} {\N
} {k} { \alpha_n(k)
} {,}
für die
\mathdisp {\alpha_n(0)=n \text{ und } \alpha_n(k') = ( \alpha_n(k))' \text { für alle } k \in \N} { }
gilt.
}
Damit definieren wir
\mavergleichskettedisp
{\vergleichskette
{n+k
}
{ \defeq} {\alpha_n(k)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und nennen das die \stichwort {Addition von natürlichen Zahlen} {.} Man beachte, dass hier die Addition in einer Weise definiert wird, in der die Kommutativität keineswegs offensichtlich ist.
{Natürliche Zahlen/Dedekind-Peano/Eindeutigkeit der Addition/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen.}
\faktfolgerung {Dann gibt es genau eine
\definitionsverweis {Verknüpfung}{}{}
\maabbeledisp {} {\N \times \N} {\N
} {(x,y)} { x+y
} {,}
mit
\mathdisp {x+0=x \text { für alle } x \in \N \text{ und } x+y' =(x+y)' \text { für alle } x,y \in \N} { . }
}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 12.4. }
\inputfaktbeweis
{Natürliche Zahlen/Addition mit n/Als Verschiebung/Hilfseigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen mit der in
Definition 12.4
festgelegten Addition.}
\faktfolgerung {Dann gelten folgende Aussagen.
\aufzaehlungfuenf{
\mavergleichskettedisp
{\vergleichskette
{n+0
}
{ =} {n
}
{ =} { 0+n
}
{ } {
}
{ } {
}
}
{}{}{}
für alle $n$, d.h. $0$ ist das
\definitionsverweis {neutrale Element}{}{}
für die Addition.
}{
\mavergleichskettedisp
{\vergleichskette
{n+k'
}
{ =} {(n+k)'
}
{ =} {n' +k
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{n,k
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Die Addition ist
\definitionsverweis {kommutativ}{}{.}
}{Die Addition ist
\definitionsverweis {assoziativ}{}{.}
}{Aus einer Gleichung
\mavergleichskette
{\vergleichskette
{n+k
}
{ = }{m+k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {m
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {\stichwort {Abziehregel} {}} {} {.} }}
\faktzusatz {}
\faktzusatz {}
}
{
(1). Die Gleichung links ergibt sich direkt aus der Definition, die rechte Gleichung, also
\mavergleichskette
{\vergleichskette
{ \alpha_0(n)
}
{ = }{ n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
folgt aus einer einfachen Induktion nach $n$.
(2). Die linke Gleichung folgt direkt aus der Definition, die rechte besagt
\mavergleichskette
{\vergleichskette
{ \alpha_{n^\prime }(k)
}
{ = }{ (\alpha_n(k))^\prime
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir beweisen sie für beliebiges $n$ durch Induktion über $k$. Bei
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
steht beidseitig $n^\prime$. Es sei die Aussage nun für $k$ schon bewiesen und betrachten wir $k^\prime$. Dann ist
\mavergleichskettedisp
{\vergleichskette
{ \alpha_{n^\prime} (k^\prime)
}
{ =} { (\alpha_{n^\prime}(k))^\prime
}
{ =} { ((\alpha_n(k))^\prime )^\prime
}
{ =} { (\alpha_n(k^\prime))^\prime
}
{ } {
}
}
{}{}{.}
Für die anderen Aussagen siehe
Aufgabe 12.5.
\zwischenueberschrift{Multiplikation auf natürlichen Zahlen}
Zur Definition der Multiplikation verwenden wir erneut das Prinzip der induktiven Definition. Zu einer natürlichen Zahl
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
betrachten wir den Startwert $0$ und die durch die Addition mit $n$ definierte Abbildung
\maabb {\alpha_n} {\N} {\N
} {.}
\inputdefinition
{}
{
Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen und
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann definieren wir die \stichwort {Multiplikation mit $n$} {} als diejenige aufgrund von
Satz 12.2
eindeutig bestimmte Abbildung
\maabbeledisp {\mu_n} {\N} {\N
} {k} { \mu_n(k)
} {,}
für die
\mathdisp {\mu_n (0)=0 \text{ und } \mu_n(k') = \mu_n(k) +n \text { für alle } k \in \N} { }
gilt.
}
Damit definieren wir die Multiplikation von zwei natürlichen Zahlen
\mavergleichskette
{\vergleichskette
{ n,k
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
durch
\mavergleichskettedisp
{\vergleichskette
{ n \cdot k
}
{ \defeq} {\mu_n(k)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es gilt also
\mavergleichskette
{\vergleichskette
{ n \cdot 0
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ n \cdot k^\prime
}
{ = }{n \cdot k +n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Diese beiden Eigenschaften legen bereits die Multiplikationsverknüpfung eindeutig fest.
{Natürliche Zahlen/Dedekind-Peano/Eindeutigkeit der Multiplikation/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen.}
\faktfolgerung {Dann gibt es eine eindeutig bestimmte
\definitionsverweis {Verknüpfung}{}{}
\maabbeledisp {} {\N \times \N} { \N
} {(x,y)} {x \cdot y
} {,}
die
\mathdisp {x \cdot 0=0 \text { für alle } x \in \N \text{ und } x \cdot y' = x \cdot y +x \text { für alle } x,y \in \N} { }
erfüllt.}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 12.6. }
{Natürliche Zahlen/Eigenschaften der Multiplikation/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen mit der in
Definition 12.7
festgelegten Multiplikation.}
\faktfolgerung {Dann gelten folgende Aussagen.
\aufzaehlungsieben{Es gilt
\mavergleichskettedisp
{\vergleichskette
{ 0 \cdot n
}
{ =} { 0
}
{ =} {n \cdot 0
}
{ } {
}
{ } {
}
}
{}{}{}
für alle $n$,
}{Es gilt
\mavergleichskettedisp
{\vergleichskette
{ 1 \cdot n
}
{ =} {n
}
{ =} {n \cdot 1
}
{ } {
}
{ } {
}
}
{}{}{}
für alle $n$, d.h.
\mavergleichskette
{\vergleichskette
{1
}
{ = }{ 0^\prime
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist das
\definitionsverweis {neutrale Element}{}{}
für die Multiplikation.
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ n \cdot k'
}
{ =} { n \cdot k + n
}
{ =} { k' \cdot n
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{n,k
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Die Multiplikation ist
\definitionsverweis {kommutativ}{}{.}
}{Die Multiplikation ist
\definitionsverweis {assoziativ}{}{.}
}{Aus einer Gleichung
\mavergleichskette
{\vergleichskette
{ n \cdot k
}
{ = }{m \cdot k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{k
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{n
}
{ = }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {\stichwort {Kürzungsregel} {}} {} {.}
}{Für beliebige
\mavergleichskette
{\vergleichskette
{ k,m,n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mavergleichskettedisp
{\vergleichskette
{ k \cdot (m+n)
}
{ =} {k \cdot m + k \cdot n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {Distributivgesetz} {} {.}
}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 12.12. }
\zwischenueberschrift{Erststufige Peanoaxiome}
Wir betrachten zwei erststufige Varianten der Dedekind-Peano-Axiome. Dabei wird in der ersten Variante die Nachfolgerfunktion beibehalten und das Induktionsaxiom, das oben für beliebige Teilmengen formuliert wurde, wird durch ein Induktionsaxiom für die in der Sprache erster Stufe formulierbaren Ausdrücke ersetzt. Das Induktionsaxiom gilt somit lediglich für Teilmengen, die in der gegebenen Sprache charakterisierbar sind. Man spricht vom \stichwort {Induktionsschema} {,} da es sich nicht um ein einzelnes Axiom handelt, sondern um eine ganze Familie von Axiomen.
\inputaxiom
{}
{
Die \stichwort {Peano-Axiome für die Nachfolgerfunktion in der ersten Stufe} {} werden
\zusatzklammer {in der Sprache $L$ zur Symbolmenge mit einer Konstanten $0$ und einem einstelligen Funktionssymbol $N$} {} {}
folgendermaßen definiert.
\aufzaehlungdrei{
\mathl{\forall x ( \neg ( Nx = 0))}{.}
}{
\mathl{\forall x \forall y ( ( Nx = Ny) \rightarrow (x=y) )}{.}
}{Für jeden Ausdruck $\alpha$ von $L$ mit einer freien Variablen $x$ gilt
\mathdisp {\alpha \frac{0}{x} \wedge \forall x { \left( \alpha \rightarrow \alpha \frac{N x}{x} \right) } \rightarrow \forall x \alpha} { . }
}
}
Aus der obigen zweitstufigen Formulierung der Axiomatik, die nur die Nachfolgerabbildung verwendet, kann man in jedem Modell in eindeutiger Weise eine Addition und eine Multiplikation definieren. Dafür ist das obige erststufige Axiomensystem zu schwach. Stattdessen werden wir unter der \stichwort {Peano-Arithmetik} {} das folgende Axiomensystem verstehen, das mit zwei Konstanten
\mathkor {} {0} {und} {1} {}
und zwei zweistelligen Operationen
\mathkor {} {+} {und} {\cdot} {}
auskommt. Die Nachfolgerfunktion ist dann durch
\mavergleichskette
{\vergleichskette
{Nx
}
{ = }{x+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
definiert und es braucht dafür kein eigenes Funktionssymbol.
\inputaxiom
{}
{
Die \stichwort {Peano-Axiome für Addition und Multiplikation in der ersten Stufe} {} werden
\zusatzklammer {in der Sprache $L^{\rm Ar}$ zur Symbolmenge mit den beiden Konstanten $0$ und $1$ und zwei zweistelligen Funktionssymbolen
\mathkor {} {+} {und} {\cdot} {}} {} {}
folgendermaßen definiert.
\aufzaehlungsieben{
\mathl{\forall x ( \neg ( x+ 1 = 0))}{.}
}{
\mathl{\forall x \forall y ( ( x+1 = y+1) \rightarrow (x=y) )}{.}
}{
\mathl{\forall x ( x+ 0 = x)}{.}
}{
\mathl{\forall x \forall y ( x+ (y+1) = ( x +y)+1))}{.}
}{
\mathl{\forall x ( x \cdot 0 = 0)}{.}
}{
\mathl{\forall x \forall y ( x \cdot (y+1) = (x \cdot y) +x)}{.}
}{Für jeden Ausdruck $\alpha$ von $L^{Ar}$ mit einer freien Variablen $x$ gilt
\mathdisp {\alpha \frac{0}{x} \wedge \forall x { \left( \alpha \rightarrow \alpha \frac{x+1}{x} \right) } \rightarrow \forall x \alpha} { . }
}
}
Die Axiome \mathkor {} {(1), (2)} {und} {(7)} {} entsprechen dabei direkt den Nachfolgeraxiomen von oben. Die Axiome \mathkor {} {(3)} {und} {(4)} {} spiegeln die Grundregeln in der zweistufigen Peano-Arithmetik für die rekursive Definition der Addition wider, und die Axiome \mathkor {} {(5)} {und} {(6)} {} entsprechen den Grundregeln für die rekursive Definition der Multiplikation. Diese Axiome gelten für die \zusatzklammer {zweitstufig festgelegten} {} {} natürlichen Zahlen. Anders als bei der obigen zweitstufigen Axiomatik gibt es aber von $\N$ verschiedene Modelle \zusatzklammer {nicht Standard-Arithmetiken} {} {,} die die erststufige Peano-Arithmetik erfüllen. Dies ist aber kein \anfuehrung{zufälliges}{} Defizit der gewählten Axiomatik, sondern dahinter verbirgt sich eine grundsätzliche Schwäche der Sprache erster Stufe, die durch die Gödelschen Unvollständigkeitssätze präzisiert werden wird.