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

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.

Zur bewiesenen Aussage