Transitive Hülle einer Menge
(Abkürzung: TC)
Eine transitive Menge enthält alle Elemente ihrer Elemente (die wieder Mengen sind). Jede Menge lässt sich zu einer transitiven machen, indem man die fehlenden Elemente hinzufügt.
Beispiele
Zahlen als Mengen:
0 = ∅
1 = {0}
2 = {0, 1}
3 = {0, 1, 2}
...
n = {0, 1, 2, ..., n – 1}
| Ausgangsmenge | 1. Schritt | 2. Schritt | Ergebnis | ||
|---|---|---|---|---|---|
| = | {1} | ∪ {0} | = {1, 0} | |
| = | {{1}} | ∪ {1} | ∪ {0} | = {{1}, 1, 0} |
| = | {1, 2, {2}} | ∪ {0} ∪ {0, 1} ∪ {2} | = {1, 2, {2}, 0} | |
Man fügt also in jedem Schritt die Elemente der (neuen) Elemente hinzu. Da es nicht endlos immer neue Elemente in den Elementen geben darf (Fundierungsaxiom), sind wir nach höchstens abzählbar vielen Schritten fertig. (Für jedes einzelne Element reichen endlich viele Schritte, aber wenn die Ausgangsmenge unendlich ist, kann es für jedes n ∈ ℕ ein Element geben, das n Schritte braucht.)
Formal wird das Verfahren geschrieben als
⋃X = Vereinigung aller Elemente von X = ⋃x∈X x
TC(X) = X ∪ ⋃X ∪ ⋃⋃X ∪ ⋃⋃⋃X ∪ ...
Eigenschaften
- Die so gewonnene Menge heißt transitive Hülle (englisch: transitive closure) oder transitiver Abschluss der Ausgangsmenge.
- Sie ist die kleinste transitive Menge, die die Ausgangsmenge enthält.
