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

Beweis

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
$φ_{S} : S ⟶ M$

mit $φ_{S} (0) = s$ und

$φ_{S} (n^{'}) = F (φ_{S} (n))$

für alle $n \in N$ mit $n, n^{'} \in S$ .

Wir betrachten nun die Menge

T = {k \in N ∣ Es gibt ein S mit den beschriebenen Eigenschaften und mit k \in S} .

Wir zeigen durch Induktion, dass $T = N$ ist. Für $k = 0$ können wir

S = {0}

wählen, wobei $φ_{{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 $φ_{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

φ_{S^{'}} (n) = {\begin{matrix} φ_{S} (n), falls n \in S, \\ F (φ_{S} (k)), falls n = k^{'} . \end{matrix}

Dies erfüllt die Eigenschaften und ist auch die einzige Möglichkeit, da die Einschränkung von $φ_{S^{'}}$ auf $S$ wegen der Eindeutigkeit mit $φ_{S}$ übereinstimmen muss. Also ist $T = N$ .

Wir zeigen nun durch Induktion über $k$ , dass $φ_{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 $φ_{1} = φ_{S_{1}}, φ_{2} = φ_{S_{2}}$ . Aufgrund der zweiten Eigenschaft ist $k \in S_{1}, S_{2}$ , daher ist nach Induktionsvoraussetzung

φ_{1} (k^{'}) = F (φ_{1} (k)) = F (φ_{2} (k)) = φ_{2} (k^{'}) .

Damit erhält man durch

φ (k) := φ_{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 $φ$ ergibt sich aus der Eindeutigkeit der Einschränkungen.

Zur bewiesenen Aussage