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

Beweis

Wir betrachten Teilmengen mit den Eigenschaften

  1. .
  2. Für jedes  , , gibt es ein mit .
  3. Es gibt eine eindeutig bestimmte Abbildung

    mit und

    für alle mit .

Wir betrachten nun die Menge

Wir zeigen durch Induktion, dass ist. Für können wir

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

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

Damit erhält man durch

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.