Natürliche Zahlen/Induktionsprinzip zur Definition von Abbildungen/Fakt/Beweis/Aufgabe/Lösung

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

${}0\in S$ .
Für jedes ${}n\in S$ , ${}n\neq 0$ , gibt es ein ${}k\in S$ mit ${}n=k'$ .
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