Rekursive Mengen

Eine Menge kann rekursiv definiert werden, wenn wir einen Startpunkt (Basis) und eine Regel (rekursiver Schritt) angeben können, wie neue Elemente hinzukommen. Auf diese Weise kann eine unendliche Menge Schritt für Schritt aufgebaut werden.

 

Beispiel: Zahlen, die durch 3 teilbar sind

Wir definieren die Menge \( \large M \) der positiven ganzen Zahlen, die durch 3 teilbar sind, rekursiv:

 

$$ \large 3 \in M \quad \text{(Basis)} $$

$$ \large x \in M \;\Rightarrow\; x + 3 \in M \quad \text{(rekursiver Schritt)} $$

 

Erster Schritt

Die Basis sagt, dass 3 in der Menge enthalten ist. Wendet man die Regel an, erhält man:

 

$$ \large 3 \in M \;\Rightarrow\; 3 + 3 = 6 \in M $$

 

Zweiter Schritt

Wenn wir wissen, dass 6 enthalten ist, liefert die Regel sofort ein neues Element:

 

$$ \large 6 \in M \;\Rightarrow\; 6 + 3 = 9 \in M $$

 

Weitere Schritte

Wenn wir den Prozess wiederholen, erhalten wir:

 

$$ \large 9 \Rightarrow 12, \quad 12 \Rightarrow 15, \quad 15 \Rightarrow 18, \ldots $$

 

Am Ende sehen wir, dass die gesamte Menge lautet

 

$$ \large M = \{3,6,9,12,15,\ldots\} $$

 

Andere Beispiele

Auf die gleiche Weise kann man die Menge der geraden Zahlen definieren, indem man mit 0 beginnt und immer 2 addiert. Oder die Menge der ungeraden Zahlen, indem man mit 1 beginnt und 2 addiert. Rekursive Definitionen von Mengen werden auch für fortgeschrittenere Konstruktionen verwendet, zum Beispiel beim Aufbau von Baumstrukturen oder beim Bestimmen sprachlicher Muster in formalen Sprachen.

 

Zusammenfassung

Eine rekursive Menge wird mit einem klaren Basiselement und einer Regel definiert, um neue Elemente zu erzeugen. Durch unendliches Wiederholen der Regel erhält man die gesamte Menge. Diese Methode ermöglicht es, große oder unendliche Mengen mit einer einfachen Definition zu beschreiben.