Beweis
Wir betrachten Teilmengen
mit den Eigenschaften
.
- Für jedes
,
,
gibt es ein
mit
.
- Es gibt eine eindeutig bestimmte Abbildung
-
mit
und
-
![{\displaystyle {}\varphi _{S}(n')=F(\varphi _{S}(n))\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd5c38b7c2b234d31c94c1aecd3ffc86f7deaa69)
für alle
mit
.
Wir betrachten nun die Menge
-
![{\displaystyle T={\left\{k\in N\mid {\text{Es gibt ein }}S{\text{ mit den beschriebenen Eigenschaften und mit }}k\in S\right\}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6873516c539380a545a1e463a7ac6bc23559ebd8)
Wir zeigen durch Induktion, dass
ist. Für
können wir
-
![{\displaystyle {}S=\{0\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/374bddfe0071d54c89459f0a15b92eff9d2f5a33)
wählen, wobei
durch die erste Abbildungseigenschaft eindeutig festgelegt ist. Es sei nun
vorausgesetzt. Das bedeutet, dass es
und eine Abbildung
mit den angegebenen Eigenschaften gibt. Bei
sind wir fertig, sei also
.
Wir setzen
und wir definieren
-
![{\displaystyle {}\varphi _{S'}(n)={\begin{cases}\varphi _{S}(n)\,,{\text{ falls }}n\in S\,,\\F(\varphi _{S}(k))\,,{\text{ falls }}n=k'\,.\end{cases}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f13fade21e2163729e4ef470a8b5ea933b2b043)
Dies erfüllt die Eigenschaften und ist auch die einzige Möglichkeit, da die Einschränkung von
auf
wegen der Eindeutigkeit mit
übereinstimmen muss. Also ist
.
Wir zeigen nun durch Induktion über
, dass
unabhängig von der gewählten Menge
ist. Bei
ist dies klar, sei diese Aussage für ein gewisses
schon bekannt, und sei
mit zugehörigen Abbildungen
. Aufgrund der zweiten Eigenschaft ist
,
daher ist nach Induktionsvoraussetzung
-
![{\displaystyle {}\varphi _{1}(k')=F(\varphi _{1}(k))=F(\varphi _{2}(k))=\varphi _{2}(k')\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02c27ce4bba493dbd5f05dad360234e1af2fa2c4)
Damit erhält man durch
-
![{\displaystyle {}\varphi (k):=\varphi _{S}(k)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83dc5af7b01b37155670dc01e4384b58ef674ed1)
mit einem beliebigen
eine wohldefinierte Abbildung auf ganz
mit den in der Formulierung des Satzes geforderten Eigenschaften. Die Eindeutigkeit von
ergibt sich aus der Eindeutigkeit der Einschränkungen.