Rekursive Definition/Abbildung/Definition/Bemerkung

Es sei ${}M$ eine rekursiv definierte Menge mit der Startmenge ${}S\subseteq M$. Verwandt mit dem Beweisprinzip über den rekursiven Aufbau der Menge ist das Prinzip, eine Abbildung ${}\varphi$ von ${}M$ in eine weitere Menge ${}N$ rekursiv zu definieren. Dazu geht man folgendermaßen vor.

1. Man legt eine Abbildung

   $\varphi _{0}\colon S\longrightarrow N$

   fest.

2. Für jede Rekursionsvorschrift erklärt man, wie man aus den schon festgelegten Werten ${}\varphi (m_{1}),\ldots ,\varphi (m_{k})$ der Elemente ${}m_{1},\ldots ,m_{k}$, auf die die Vorschrift Bezug nimmt, den Wert unter ${}\varphi$ für das durch die Vorschrift produzierte Element ${}m$ festlegt.
3. Man muss sicherstellen, dass, falls es für ein Element mehrere Möglichkeiten gibt, dieses rekursiv zu erzeugen, die verschiedenen Möglichkeiten zum gleichen Wert führen.

Wenn diese Bedingungen erfüllt sind, ist eine wohldefinierte Abbildung

$\varphi \colon M\longrightarrow N$

definiert.