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 $\mathrm{dom}(f_X)={\mathbb{N}}_0$ existiert, die

• $f_X(0)=X$
• $\mathrm{\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|(\mathrm{\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,\dots \}$.

Die transitive Hülle wird dann zu

$TC(X)=\bigcup M_X=\bigcup _{n=1}^{\mathrm{\infty }}\{x|x{\in }^{n}X\}=\bigcup _{n=0}^{\mathrm{\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

$T{C}_R(X):=\bigcup _{n=0}^{\mathrm{\infty }}\{x|(\mathrm{\exists }y\in X)x{R}^{n}y\}=\{x|(\mathrm{\exists }y\in X)x{R}^{*}y\}$ 

Dies ist das Urbild von $X$ unter $R^{*}$, der reflexiv-transitiven Hülle der Relation $R$. $T{C}_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)