Rekursive Definition/Beweisprinzip/Bemerkung

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Es sei eine rekursiv definierte Menge, die durch eine Startmenge und gewisse Rekursionsvorschriften gegeben sei. Nehmen wir an, wir möchten für alle Elemente der Menge eine gewisse Eigenschaft 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 erfüllt (Rekursionsanfang).
  2. Man zeigt für jede Rekursionsvorschrift, dass unter der Voraussetzung, dass die in dieser Vorschrift verwendeten Elemente die Eigenschaft besitzen, dann auch das durch die Vorschrift produzierte Element die Eigenschaft besitzt (Rekursionsschritt).

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