Transitive Hülle (Menge)

Die transitive Hülle einer Menge $X$ (oft mit $TC(X)$ für transitive closure bezeichnet) ist die kleinste Obermenge von $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 $TC(X)$ die kleinste transitive Obermenge von $X$ ist, gilt $TC(X)=X$ genau dann, wenn $X$ transitiv ist.

Konstruktion

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

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

erfüllt. Das Ersetzungsschema sichert nun die Existenz der Menge

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

und aufgrund des Vereinigungsaxioms existiert

$\bigcup M_{X}$,

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

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

Bemerkungen

Es wird hier eine iterierte Mengenvereinigung definiert, nämlich

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

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

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

$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 wird dann zu

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

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 $X$ gilt, wenn man eine Obermenge $Y\supseteq X$ findet, für die sie gilt, so bietet es sich an, von $X$ zur transitiven Hülle überzugehen.

Eine ähnliche Vorgehensweise findet man zum Beispiel im Beweis des Epsilon-Induktions-Verfahren wieder.

Verallgemeinerung

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

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

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

Siehe auch

• Transitive Hülle (Relation)