„Transitive Hülle (Menge)“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[gesichtete Version]

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

Inhalt gelöscht Inhalt hinzugefügt

Inline

Version vom 26. März 2018, 19:37 Uhr

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}$ ^[1] 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}\}

^[1]

und aufgrund des Vereinigungsaxioms^{[A 1]} 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 Megenvereinigung 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 }\{y|y\in ^{n}X\}=\bigcup _{n=0}^{\infty }{\bigcup }^{n}X

.^[2]

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.

Siehe auch

Transitive Hülle (Relation)

Anmerkungen

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

↑ ^a ^b $f_{X},M_{X}$ snd ad-hoc-Bezeichnungen
↑ Mit $\in$ aufgefasst als homogene Relation und ${\in }^{+}:=\textstyle \bigcup _{n\in {\mathbb {N} }}{\in }^{n}$ lässt sich die transitive Hülle auch noch verstehen als
$TC(X)=\{y|y{\in }^{+}X\}$ .
Siehe z. B. G. O'Regan: $R^{*}:=\textstyle \bigcup _{n\in {\mathbb {N} _{0}}}R^{n},\ \;R^{+}:=\textstyle \bigcup _{n\in {\mathbb {N} }}R^{n}$ für homogene Relationen $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.

[2] Das Vereinigungsaxiom wurde natürlich schon vorher zum Existenzbeweis der Funktion $f_{X}$ benötigt.

[adhoc-1] $f_{X},M_{X}$ snd ad-hoc-Bezeichnungen

[3] Mit $\in$ aufgefasst als homogene Relation und ${\in }^{+}:=\textstyle \bigcup _{n\in {\mathbb {N} }}{\in }^{n}$ lässt sich die transitive Hülle auch noch verstehen als
$TC(X)=\{y|y{\in }^{+}X\}$ .
Siehe z. B. G. O'Regan: $R^{*}:=\textstyle \bigcup _{n\in {\mathbb {N} _{0}}}R^{n},\ \;R^{+}:=\textstyle \bigcup _{n\in {\mathbb {N} }}R^{n}$ für homogene Relationen $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.

[1]

[A 1]

[2]

@@ Zeile 1: / Zeile 1: @@
-Die '''transitive Hülle''' einer Menge <math>x</math> (oft mit <math>TC(x)</math> für ''transitive closure'' bezeichnet) ist die kleinste Obermenge von <math>x</math>, die [[Transitive Menge|transitiv]] ist. Die Existenz und Eindeutigkeit lassen sich in [[Zermelo-Fraenkel-Mengenlehre|ZF]] (das [[Auswahlaxiom]] ist dafür nicht notwendig) beweisen. Maßgeblich gehen dabei das [[Ersetzungsaxiom|Ersetzungsschema]] und [[Unendlichkeitsaxiom]] ein. Da <math>TC(x)</math> die kleinste transitive Obermenge von <math>x</math> ist, gilt <math>TC(x)=x</math> genau dann, wenn <math>x</math> transitiv ist.
+Die '''transitive Hülle''' einer Menge <math>X</math> (oft mit <math>TC(X)</math> für ''transitive closure'' bezeichnet) ist die kleinste Obermenge von <math>X</math>, die [[Transitive Menge|transitiv]] ist. Die Existenz und Eindeutigkeit lassen sich in [[Zermelo-Fraenkel-Mengenlehre|ZF]] (das [[Auswahlaxiom]] ist dafür nicht notwendig) beweisen. Maßgeblich gehen dabei das [[Ersetzungsaxiom|Ersetzungsschema]] und [[Unendlichkeitsaxiom]] ein. Da <math>TC(X)</math> die kleinste transitive Obermenge von <math>X</math> ist, gilt <math>TC(X)=X</math> genau dann, wenn <math>X</math> transitiv ist.
 ==Konstruktion==
-Durch Induktion über <math>\mathbb{N}</math> lässt sich zeigen, dass eine Funktion <math>f</math> mit <math>\operatorname{dom}(f)=\mathbb{N}</math> existiert, die
+Durch Induktion über <math>\mathbb{N}</math> lässt sich zeigen, dass für jede Menge <math>X</math> eine Funktion <math>f_X</math><ref name=adhoc><math>f_X, M_X</math> snd ad-hoc-Bezeichnungen</ref> mit <math>\operatorname{dom}(f_X)=\mathbb{N}_0</math> existiert, die
-*<math>f(0)=x</math>
+*<math>f_X(0)=X</math>
-*<math>\forall n\in\mathbb{N}: f(n+1)=\bigcup f(n)</math>
+*<math>\forall n\in\mathbb{N}_0: f_X(n+1)=\bigcup f_X(n)</math>
 erfüllt. Das Ersetzungsschema sichert nun die Existenz der Menge
-:<math>M:=\{f(n)|n\in\mathbb{N}\}</math>
+:<math>M_X:=\{f_X(n)|n\in\mathbb{N}_0\}</math><ref name=adhoc />
-und aufgrund des [[Vereinigungsaxiom]]s<ref group="A">Das Vereinigungsaxiom wurde natürlich schon vorher zum Existenzbeweis der Funktion <math>f</math> benötigt.</ref> existiert
+und aufgrund des [[Vereinigungsaxiom]]s<ref group="A">Das Vereinigungsaxiom wurde natürlich schon vorher zum Existenzbeweis der Funktion <math>f_X</math> benötigt.</ref> existiert
-:<math>\bigcup M</math>,
+:<math>\bigcup M_X</math>,
-welchem man schnell die von <math>TC(x)</math> geforderten Eigenschaften nachweist. Es gilt also
+welchem man schnell die von <math>TC(X)</math> geforderten Eigenschaften nachweist. Es gilt also
-:<math>TC(x)=\bigcup_{n\in\mathbb{N}} f(n)</math>.
+:<math>TC(X)=\bigcup_{n\in\mathbb{N}_0} f_X(n)</math>.
+==Bemerkungen==
+Es wird hier eine iterierte Megenvereinigung definiert, nämlich
+:<math>f_X(n) = {\bigcup}^n X</math>,&nbsp; speziell <math>X=\{x|x \in X\},\ \;\bigcup X = \{x|(\exist y \in X) x \in y\}</math>.
+Fasst man die Element-Relation <math>\in</math> als homogene Relation auf, dann steht auf der rechten Seite gerade die ''n''-fache Verkettung von <math>\in</math> mit sich selbst, also deren ''n''. Potenz <math>{\in}^n</math> (siehe [[Relation (Mathematik)#Homogene Relationen|Relation §Homogene Relationen]]: Potenzen).<!-- die Elementketten spielen auch beim [[Fundierungsaxiom]] eine Rolle--> Damit kann weiter vereinfacht werden zu
+:<math>f_X(n) = {\bigcup}^n X  = \{x|x {\in}^{n+1} X\}</math>, sowie
+:<math>M_X = \{ {\bigcup}^n X|n \in \N_0\} = \{ X, \bigcup X, \bigcup \bigcup X, \bigcup \bigcup \bigcup X, \bigcup \bigcup \bigcup \bigcup X, \ldots \}</math>.
+Die transitive Hülle wird dann zu
+:<math>TC(X) = \bigcup M_X = \bigcup_{n=1}^\infty \{y|y\in^n X\} = \bigcup_{n=0}^\infty {\bigcup}^n X</math>.<ref>Mit <math>\in</math> aufgefasst als homogene Relation und <math>{\in}^+ := \textstyle\bigcup_{n\in{\N}} {\in}^n</math> lässt sich die transitive Hülle auch noch verstehen als
+:<math>TC(X) = \{y|y {\in}^+ X\}</math>.
+Siehe z.&nbsp;B. G. O'Regan: <math>R^* := \textstyle\bigcup_{n\in{\N_0}} R^n,\ \;R^+ := \textstyle\bigcup_{n\in{\N}} R^n</math> für homogene Relationen <math>R</math>, {{Literatur
+   |Autor=Gerard O’Regan
+   |Titel=[http://www.springer.com/cda/content/document/cda_downloaddocument/9783319445601-c2.pdf?SGWID=0-0-45-1588706-p180199599 Guide to Discrete Mathematics. Sets, Relations and Functions]
+   |Reihe=Texts in Computer Science (TCS)
+   |Verlag=Springer International Publishing
+   |Ort=Schweiz
+   |Datum=2016
+   |Seiten=25–51
+   |Online=
+   |Format=PDF
+   |KBytes=1000
+   |DOI=10.1007/978-3-319-44561-8_2}} Seite 39.</ref>
 ==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 <math>x</math> gilt, wenn man eine Obermenge <math>y\supseteq x</math> findet, für die sie gilt, so bietet es sich an, von <math>x</math> zur transitiven Hülle überzugehen.
+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 <math>X</math> gilt, wenn man eine Obermenge <math>Y\supseteq X</math> findet, für die sie gilt, so bietet es sich an, von <math>X</math> zur transitiven Hülle überzugehen.
 Eine ähnliche Vorgehensweise findet man zum Beispiel im Beweis des [[Epsilon-Induktion|Epsilon-Induktions-Verfahren]] wieder.

„Transitive Hülle (Menge)“ – Versionsunterschied

Version vom 26. März 2018, 19:37 Uhr

Inhaltsverzeichnis

Konstruktion

Bemerkungen

Anwendung

Siehe auch

Anmerkungen

Navigationsmenü

„Transitive Hülle (Menge)“ – Versionsunterschied

Version vom 26. März 2018, 19:37 Uhr

Konstruktion

Bemerkungen

Anwendung

Siehe auch

Anmerkungen

Navigationsmenü

Suche