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