Natürliche Zahlen/Induktionsprinzip zur Definition von Abbildungen/Fakt/Beweis1

Beweis

Wir zeigen zuerst durch Induktion über ${}k$, dass es auf der Menge ${}\{0,\ldots ,k\}={\left\{n\in N\mid n\leq k\right\}}$ eine eindeutig bestimmte Abbildung

$\varphi _{k}\colon \{0,\ldots ,k\}\longrightarrow M,\,n\longmapsto \varphi _{k}(n),$

gibt, die die erste Bedingung und die zweite Bedingung für alle ${}n<k$ erfüllt. Bei ${}k=0$ besteht die Menge aus dem einzigen Element ${}0$ und dafür legt die erste Bedingung ${}\varphi _{0}(0)=s$ die Abbildung eindeutig fest. Sei die Aussage nun für ${}k$ bewiesen und betrachte ${}k^{\prime }$. Es ist ${}\{0,\ldots ,k^{\prime }\}=\{0,\ldots ,k\}\cup \{k^{\prime }\}$ und die Bedingungen legen nach Induktionsvoraussetzung eine eindeutige Abbildung ${}\varphi =\varphi _{k}\colon \{0,\ldots ,k\}\rightarrow M$ fest. Für das zusätzliche Element ${}k^{\prime }$ muss ${}\varphi (k^{\prime })=F(\varphi (k))$ gelten, wodurch die Abbildung auch auf der größeren Menge eindeutig festgelegt ist.

Aufgrund der Eindeutigkeit gilt insbesondere, dass wenn man ${}\varphi _{k}$ auf ${}\{1,\ldots ,\ell \}$ mit ${}\ell \leq k$ einschränkt, sich ${}\varphi _{\ell }$ ergibt. Daher gilt auch, dass die zu konstruierende Abbildung ${}\varphi \colon N\rightarrow M$ eingeschränkt auf jeden Abschnitt ${}\{1,\ldots ,k\}$ mit ${}\varphi _{k}$ übereinstimmen muss. Daher setzen wir ${}\varphi (n):=\varphi _{n}(n)$, und diese Abbildung erfüllt die Eigenschaften für alle ${}n$.

Zur bewiesenen Aussage