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$.