Transitive Hülle (Menge)

Die transitive Hülle einer Menge ${\displaystyle X}$ (oft mit ${\displaystyle TC(X)}$ für transitive closure bezeichnet) ist die kleinste Obermenge von ${\displaystyle X}$, die transitiv ist. Die Existenz und Eindeutigkeit lassen sich in ZF (das Auswahlaxiom ist dafür nicht notwendig) beweisen. Maßgeblich gehen dabei das Ersetzungsschema und Unendlichkeitsaxiom ein. Da ${\displaystyle TC(X)}$ die kleinste transitive Obermenge von ${\displaystyle X}$ ist, gilt ${\displaystyle TC(X)=X}$ genau dann, wenn ${\displaystyle X}$ transitiv ist.

Konstruktion

Durch Induktion über ${\displaystyle \mathbb {N} }$ lässt sich zeigen, dass für jede Menge ${\displaystyle X}$ eine Funktion ${\displaystyle f_{X}}$[1] mit ${\displaystyle \operatorname {dom} (f_{X})=\mathbb {N} _{0}}$ existiert, die

• ${\displaystyle f_{X}(0)=X}$
• ${\displaystyle \forall n\in \mathbb {N} _{0}:f_{X}(n+1)=\bigcup f_{X}(n)}$

erfüllt. Das Ersetzungsschema sichert n​un die Existenz d​er Menge

${\displaystyle M_{X}:=\{f_{X}(n)|n\in \mathbb {N} _{0}\}}$[1]

und aufgrund d​es Vereinigungsaxioms[A 1] existiert

${\displaystyle \bigcup M_{X}}$,

welchem man schnell die von ${\displaystyle TC(X)}$ geforderten Eigenschaften nachweist. Es gilt also

${\displaystyle TC(X)=\bigcup _{n\in \mathbb {N} _{0}}f_{X}(n)}$.

Bemerkungen

Es w​ird hier e​ine iterierte Mengenvereinigung definiert, nämlich

${\displaystyle f_{X}(n)={\bigcup }^{n}X}$, speziell ${\displaystyle X=\{x|x\in X\},\ \;\bigcup X=\{x|(\exists y\in X)x\in y\}}$.

Fasst man die Element-Relation ${\displaystyle \in }$ als homogene Relation auf, dann steht auf der rechten Seite gerade die n-fache Verkettung von ${\displaystyle \in }$ mit sich selbst, also deren n. Potenz ${\displaystyle {\in }^{n}}$ (siehe Relation §Homogene Relationen: Potenzen). Damit kann weiter vereinfacht werden zu

${\displaystyle f_{X}(n)={\bigcup }^{n}X=\{x|x{\in }^{n+1}X\}}$, sowie

${\displaystyle M_{X}=\{{\bigcup }^{n}X|n\in \mathbb {N} _{0}\}=\{X,\bigcup X,\bigcup \bigcup X,\bigcup \bigcup \bigcup X,\bigcup \bigcup \bigcup \bigcup X,\ldots \}}$.

Die transitive Hülle w​ird dann zu

${\displaystyle TC(X)=\bigcup M_{X}=\bigcup _{n=1}^{\infty }\{x|x\in ^{n}X\}=\bigcup _{n=0}^{\infty }{\bigcup }^{n}X}$.[2][3]

Anwendung

In vielen Beweisen in der Mengenlehre braucht man für ein bestimmtes Argument die Transitivität einer Menge. Kann man zusätzlich zeigen, dass die Aussage für eine Menge ${\displaystyle X}$ gilt, wenn man eine Obermenge ${\displaystyle Y\supseteq X}$ findet, für die sie gilt, so bietet es sich an, von ${\displaystyle X}$ zur transitiven Hülle überzugehen.

Eine ähnliche Vorgehensweise findet m​an zum Beispiel i​m Beweis d​es Epsilon-Induktions-Verfahren wieder.

Verallgemeinerung

Sei ${\displaystyle X}$ eine Menge mit einer homogene Relation ${\displaystyle R}$ darauf. Die ${\displaystyle R}$-transitive Hülle ist dann gegeben durch

${\displaystyle TC_{R}(X):=\bigcup _{n=0}^{\infty }\{x|(\exists y\in X)x\,R^{n}y\}=\{x|(\exists y\in X)x\,R^{*}y\}}$ [2][4]

Dies ist das Urbild von ${\displaystyle X}$ unter ${\displaystyle R^{*}}$, der reflexiv-transitiven Hülle der Relation ${\displaystyle R}$. ${\displaystyle TC_{R}(X)}$ ist die kleinste Obermenge von ${\displaystyle X}$, die ${\displaystyle R}$-transitiv ist. Im Fall ${\displaystyle R=\in }$ repliziert die verallgemeinerte Definition den obigen Spezialfall.

Siehe auch

• Transitive Hülle (Relation)

Anmerkungen

1. Das Vereinigungsaxiom wurde natürlich schon vorher zum Existenzbeweis der Funktion ${\displaystyle f_{X}}$ benötigt.

1. ${\displaystyle f_{X},M_{X}}$ sind ad-hoc-Bezeichnungen
2. Mit ${\displaystyle \in }$ aufgefasst als homogene Relation und ${\displaystyle {\in }^{+}:=\textstyle \bigcup _{n\in {\mathbb {N} }}{\in }^{n}}$ lässt sich die transitive Hülle auch noch verstehen als

   ${\displaystyle TC(X)=\{x|x{\in }^{+}X\}}$.

   Siehe z. B. G. O'Regan: ${\displaystyle R^{*}:=\textstyle \bigcup _{n\in {\mathbb {N} _{0}}}R^{n},\ \;R^{+}:=\textstyle \bigcup _{n\in {\mathbb {N} }}R^{n}}$ für homogene Relationen ${\displaystyle R}$, Gerard O’Regan: Guide to Discrete Mathematics. Sets, Relations and Functions (= Texts in Computer Science (TCS)). Springer International Publishing, Schweiz 2016, S. 25–51, doi:10.1007/978-3-319-44561-8_2. Seite 39.
3. Using Replacement to prove transitive closure is a set without recursion, auf: StackExchange Mathematics, Stand: 2018
4. Wolfram Pohlers: Mengenlehre (PDF), Universität Münster, Institut für mathematische Logik und Grundlagenforschung, Vorlesungsskript, SS 1994, Seite 31. Die dort angegebene Definition ähnelt der hier unter Konstruktion angegebenen, und wurde aber in eine äquivalente, leichter lesbare überführt.