Natürliche Zahlen/Zweitstufig/Induktion und Verknüpfung/Textabschnitt

Die folgende Aussage ist das induktive Definitionsprinzip für Abbildungen.

Satz

Es sei ${}(N,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen und es sei ${}M$ eine Menge mit einem fixierten Element ${}s\in M$ und einer Abbildung ${}F\colon M\rightarrow M$.

Dann gibt es genau eine Abbildung

$\varphi \colon N\longrightarrow M,\,n\longmapsto \varphi (n),$

die die beiden Eigenschaften

$\varphi (0)=s{\text{ und }}\varphi (n^{\prime })=F(\varphi (n)){\text{ für alle }}n\in \mathbb {N}$

erfüllt.

Beweis

Wir betrachten Teilmengen ${}S\subseteq N$ mit den Eigenschaften

1. ${}0\in S$.
2. Für jedes ${}n\in S$ , ${}n\neq 0$, gibt es ein ${}k\in S$ mit ${}n=k'$.
3. Es gibt eine eindeutig bestimmte Abbildung

   $\varphi _{S}\colon S\longrightarrow M$

   mit ${}\varphi _{S}(0)=s$ und

   ${}\varphi _{S}(n')=F(\varphi _{S}(n))\,$

   für alle ${}n\in N$ mit ${}n,n'\in S$.

Wir betrachten nun die Menge

$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 ${}T=N$ ist. Für ${}k=0$ können wir

${}S=\{0\}\,$

wählen, wobei ${}\varphi _{\{0\}}$ durch die erste Abbildungseigenschaft eindeutig festgelegt ist. Es sei nun ${}k\in T$ vorausgesetzt. Das bedeutet, dass es ${}k\in S$ und eine Abbildung ${}\varphi _{S}$ mit den angegebenen Eigenschaften gibt. Bei ${}k'\in S$ sind wir fertig, sei also ${}k'\notin S$. Wir setzen ${}S'=S\cup \{k'\}$ und wir definieren

${}\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 ${}\varphi _{S'}$ auf ${}S$ wegen der Eindeutigkeit mit ${}\varphi _{S}$ übereinstimmen muss. Also ist ${}T=N$.

Wir zeigen nun durch Induktion über ${}k$, dass ${}\varphi _{S}(k)$ unabhängig von der gewählten Menge ${}k\in S$ ist. Bei ${}k=0$ ist dies klar, sei diese Aussage für ein gewisses ${}k$ schon bekannt, und sei ${}k'\in S_{1},S_{2}$ mit zugehörigen Abbildungen ${}\varphi _{1}=\varphi _{S_{1}},\varphi _{2}=\varphi _{S_{2}}$. Aufgrund der zweiten Eigenschaft ist ${}k\in S_{1},S_{2}$, daher ist nach Induktionsvoraussetzung

${}\varphi _{1}(k')=F(\varphi _{1}(k))=F(\varphi _{2}(k))=\varphi _{2}(k')\,.$

Damit erhält man durch

${}\varphi (k):=\varphi _{S}(k)\,$

mit einem beliebigen ${}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.

$\Box$

Satz

Es seien ${}N_{1}$ und ${}N_{2}$ Dedekind-Peano-Modelle für die natürlichen Zahlen.

Dann gibt es eine eindeutig bestimmte bijektive Abbildung

$\varphi \colon N_{1}\longrightarrow N_{2}$

mit ${}\varphi (0_{1})=0_{2}$ und

${}\varphi (n')=(\varphi (n))'\,$

für alle ${}n\in N_{1}$.

Insbesondere sind je zwei Dedekind-Peano-Modelle isomorph.

Beweis

Aufgrund von Fakt, angewendet auf ${}N_{1}$ und die Nachfolgerabbildung auf ${}N_{2}$, gibt es genau eine Abbildung

$\varphi \colon N_{1}\longrightarrow N_{2}$

mit den angegebenen Eigenschaften. Wenn man die Rollen vertauscht, so erhält man eine eindeutige Abbildung

$\psi \colon N_{2}\longrightarrow N_{1}$

mit den gleichen Eigenschaften. Wir betrachten nun die Verknüpfung

$\psi \circ \varphi \colon N_{1}\longrightarrow 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 Fakt, dass ${}\psi \circ \varphi =\operatorname {Id} _{N_{1}}$ ist. Ebenso ist ${}\varphi \circ \psi =\operatorname {Id} _{N_{2}}$ und somit sind ${}\varphi$ und ${}\psi$ invers zueinander.

$\Box$

Für das im Wesentlichen eindeutig bestimmte Modell der Dedekind-Peano-Axiome verwenden wir das Symbol ${}\mathbb {N}$ und sprechen von den natürlichen Zahlen.

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 - d.h. ${}0$ soll das neutrale Element der Addition sein - und die Addition eines Elementes ${}n$ mit ${}1:=0'$ soll der Nachfolger von ${}n$ sein. Die Grundidee ist dabei, die Summe ${}n+k$ dadurch zu definieren, dass man sukzessive den ersten Summanden um eins erhöht (also den Nachfolger nimmt) und den zweiten um eins vermindert (also den Vorgänger nimmt, falls ${}k\neq 0$ ist). Man spricht vom Umlegungsprinzip (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 ${}n\in \mathbb {N}$ als Startglied an. Die daraus gewonnene Abbildung beschreibt das Addieren mit dieser Zahl ${}n$ (es wird also die zweistellige Addition auf einstellige Operationen zurückgeführt).

Definition

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen und ${}n\in \mathbb {N}$. Dann definieren wir die Addition mit ${}n$ als diejenige aufgrund von Fakt eindeutig bestimmte Abbildung

$\alpha _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \alpha _{n}(k),$

für die

$\alpha _{n}(0)=n{\text{ und }}\alpha _{n}(k')=(\alpha _{n}(k))'{\text{ für alle }}k\in \mathbb {N}$

gilt.

Damit definieren wir

${}n+k:=\alpha _{n}(k)\,$

und nennen das die Addition von natürlichen Zahlen. Man beachte, dass hier die Addition in einer Weise definiert wird, in der die Kommutativität keineswegs offensichtlich ist.

Lemma

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen.

Dann gibt es genau eine Verknüpfung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(x,y)\longmapsto x+y,$

mit

$x+0=x{\text{ für alle }}x\in \mathbb {N} {\text{ und }}x+y'=(x+y)'{\text{ für alle }}x,y\in \mathbb {N} .$

Beweis

Siehe Aufgabe.

$\Box$

Lemma

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen mit der in Definition festgelegten Addition.

Dann gelten folgende Aussagen.

1. ${}n+0=n=0+n\,$

   für alle ${}n$, d.h. ${}0$ ist das neutrale Element für die Addition.

2. ${}n+k'=(n+k)'=n'+k\,$

   für alle ${}n,k\in \mathbb {N}$.

3. Die Addition ist kommutativ.
4. Die Addition ist assoziativ.
5. Aus einer Gleichung ${}n+k=m+k$ folgt

   ${}n=m\,$

   (Abziehregel).

Beweis

(1). Die Gleichung links ergibt sich direkt aus der Definition, die rechte Gleichung, also ${}\alpha _{0}(n)=n$, folgt aus einer einfachen Induktion nach ${}n$.

(2). Die linke Gleichung folgt direkt aus der Definition, die rechte besagt ${}\alpha _{n^{\prime }}(k)=(\alpha _{n}(k))^{\prime }$. Wir beweisen sie für beliebiges ${}n$ durch Induktion über ${}k$. Bei ${}k=0$ steht beidseitig ${}n^{\prime }$. Es sei die Aussage nun für ${}k$ schon bewiesen und betrachten wir ${}k^{\prime }$. Dann ist

${}\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.

$\Box$

Multiplikation auf natürlichen Zahlen

Zur Definition der Multiplikation verwenden wir erneut das Prinzip der induktiven Definition. Zu einer natürlichen Zahl ${}n\in \mathbb {N}$ betrachten wir den Startwert ${}0$ und die durch die Addition mit ${}n$ definierte Abbildung ${}\alpha _{n}\colon \mathbb {N} \rightarrow \mathbb {N}$.

Definition

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen und ${}n\in \mathbb {N}$. Dann definieren wir die Multiplikation mit ${}n$ als diejenige aufgrund von Fakt eindeutig bestimmte Abbildung

$\mu _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \mu _{n}(k),$

für die

$\mu _{n}(0)=0{\text{ und }}\mu _{n}(k')=\mu _{n}(k)+n{\text{ für alle }}k\in \mathbb {N}$

gilt.

Damit definieren wir die Multiplikation von zwei natürlichen Zahlen ${}n,k\in \mathbb {N}$ durch

${}n\cdot k:=\mu _{n}(k)\,.$

Es gilt also ${}n\cdot 0=0$ und ${}n\cdot k^{\prime }=n\cdot k+n$. Diese beiden Eigenschaften legen bereits die Multiplikationsverknüpfung eindeutig fest.

Lemma

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen.

Dann gibt es eine eindeutig bestimmte Verknüpfung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(x,y)\longmapsto x\cdot y,$

die

$x\cdot 0=0{\text{ für alle }}x\in \mathbb {N} {\text{ und }}x\cdot y'=x\cdot y+x{\text{ für alle }}x,y\in \mathbb {N}$

erfüllt.

Beweis

Siehe Aufgabe.

$\Box$

Lemma

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen mit der in Definition festgelegten Multiplikation.

Dann gelten folgende Aussagen.

1. Es gilt

   ${}0\cdot n=0=n\cdot 0\,$

   für alle ${}n$,

2. Es gilt

   ${}1\cdot n=n=n\cdot 1\,$

   für alle ${}n$, d.h. ${}1=0^{\prime }$ ist das neutrale Element für die Multiplikation.

3. Es ist

   ${}n\cdot k'=n\cdot k+n=k'\cdot n\,$

   für alle ${}n,k\in \mathbb {N}$.

4. Die Multiplikation ist kommutativ.
5. Die Multiplikation ist assoziativ.
6. Aus einer Gleichung ${}n\cdot k=m\cdot k$ mit ${}k\neq 0$ folgt ${}n=m$ (Kürzungsregel).
7. Für beliebige ${}k,m,n\in \mathbb {N}$ gilt

   ${}k\cdot (m+n)=k\cdot m+k\cdot n\,$

   (Distributivgesetz).

Beweis

Siehe Aufgabe.

$\Box$