Rekursive Definition/Beweisprinzip/Bemerkung

Es sei $M$ eine rekursiv definierte Menge, die durch eine Startmenge  $S\subseteq M$  und gewisse Rekursionsvorschriften gegeben sei. Nehmen wir an, wir möchten für alle Elemente der Menge $M$ eine gewisse Eigenschaft $E$ nachweisen. Das Beweisprinzip durch Rekursion oder Beweisprinzip über den rekursiven Aufbau der Menge funktioniert folgendermaßen.

1. Man zeigt, dass jedes Element aus der Startmenge die Eigenschaft $E$ erfüllt (Rekursionsanfang).
2. Man zeigt für jede Rekursionsvorschrift, dass unter der Voraussetzung, dass die in dieser Vorschrift verwendeten Elemente die Eigenschaft $E$ besitzen, dann auch das durch die Vorschrift produzierte Element die Eigenschaft besitzt (Rekursionsschritt).

Daraus kann man dann schließen, dass jedes Element aus $M$ die Eigenschaft erfüllt. Die Richtigkeit dieses Beweisprinzips beruht auf folgender Betrachtung: Es sei  $N\subseteq M$  die Menge aller Elemente, für die die Eigenschaft $E$ gilt. Aufgrund des Rekursionsanfangs gilt  $S\subseteq N$.  Aufgrund des Rekursionsschrittes ist $N$ abgeschlossenen unter sämtlichen Rekursionsvorschriften. Dies ist aber die Definition für $M$, also ist  $N=M$  und die Eigenschaft gilt für ganz $M$.