Mengentheorie/Rekursive Definitionen/Wörter/Einführung/Textabschnitt

Ein wichtiges Prinzip, Mengen zu definieren, ist das der rekursiven Definition. Eine rekursive Definition besteht aus zwei Sorten von Regeln. (1) Einerseits gewisse Startregeln, die sagen, was direkt zu der Menge gehört, und (2) Rekursionsregeln (Generierungsregeln), die die Form einer Bedingung haben, und besagen, dass wenn gewisse Objekte zu der Menge gehören, und wenn neue Objekte aus diesen Objekten in bestimmter Weise gebildet sind, dass dann diese neuen Objekte ebenfalls dazu gehören (die dritte stillschweigende Bedingung an eine rekursive Definition ist, dass es keine weitere Möglichkeit gibt, zu der Menge zu gehören, außer den in (1) und (2) genannten).

Beispiel

Die Menge der Wörter über einem Alphabet ${}A$ kann man auch folgendermaßen rekursiv definieren.

1. ${}\emptyset$ ist ein Wort über ${}A$.
2. Wenn ${}x$ ein Wort ist und ${}a\in A$ ein Buchstabe, so ist auch ${}xa$ ein Wort.

Hier repräsentiert ${}x$ (eine Variable) ein beliebiges schon konstruiertes Wort. Dabei ist ${}\emptyset a$ als ${}a$ zu lesen, so dass die beiden erlaubten Konstruktionsschritte (also der Anfangsschritt und der Rekursionsschritt) sichern, dass die einzelnen Symbole aus ${}A$ Wörter sind. Wenn das Alphabet durch ${}A=\{a,b,c\}$ gegeben ist, so würde der rekursive Nachweis, dass ${}abbac$ ein Wort ist, folgendermaßen gehen.

1. Wegen der Anfangsbedingung ist ${}\emptyset$ ein Wort.
2. Deshalb und wegen des Rekursionsschrittes ist ${}\emptyset a=a$ ein Wort.
3. Deshalb und wegen des Rekursionsschrittes ist ${}ab$ ein Wort (hier ist also ${}x=a$ das schon nachgewiesene Wort und der Buchstabe ${}b$ wird angehängt).
4. Deshalb und wegen des Rekursionsschrittes ist ${}abb$ ein Wort (hier ist also ${}x=ab$ das schon nachgewiesene Wort und der Buchstabe ${}b$ wird angehängt).
5. Deshalb und wegen des Rekursionsschrittes ist ${}abba$ ein Wort (hier ist also ${}x=abb$ das schon nachgewiesene Wort und der Buchstabe ${}a$ wird angehängt).
6. Deshalb und wegen des Rekursionsschrittes ist ${}abbac$ ein Wort (hier ist also ${}x=abba$ das schon nachgewiesene Wort und der Buchstabe ${}c$ wird angehängt).

Natürlich kann man ${}abbac$ sofort ansehen, dass es sich um eine linear angeordnete Zeichenreihe über ${}\{a,b,c\}$ handelt, und der rekursive Nachweis scheint übertrieben pedantisch zu sein. Bei komplexer gebildeten Mengen ist aber die rekursive Definition unerlässlich, vor allem auch deshalb, da sie ermöglicht, Eigenschaften der Elemente einer Menge über den rekursiven Aufbau nachzuweisen.

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

Ein Spezialfall dieses Beweisprinzips ist das Prinzip der vollständigen Induktion für natürliche Zahlen. Die natürlichen Zahlen sind rekursiv durch das Startelement ${}0$ und eine einzige Rekursionsregel, nämlich die Nachfolgerregel festgelegt: Wenn ${}n$ eine natürliche Zahl ist, so ist auch der Nachfolger ${}n'=n+1$ von ${}n$ eine natürliche Zahl.

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.