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

Konstruktion

Bearbeiten

Durch Induktion über   lässt sich zeigen, dass für jede Menge   eine Funktion  [1] mit   existiert, die

  •  
  •  

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

 [1]

und aufgrund des Vereinigungsaxioms[A 1] existiert

 ,

welchem man schnell die von   geforderten Eigenschaften nachweist. Es gilt also

 .

Bemerkungen

Bearbeiten

Es wird hier eine iterierte Mengenvereinigung definiert, nämlich

 , speziell  .

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

 , sowie
 .

Die transitive Hülle wird dann zu

 .[2][3]

Anwendung

Bearbeiten

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

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

Verallgemeinerung

Bearbeiten

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

  [2][4]

Dies ist das Urbild von   unter  , der reflexiv-transitiven Hülle der Relation  .   ist die kleinste Obermenge von  , die  -transitiv ist. Im Fall   repliziert die verallgemeinerte Definition den obigen Spezialfall.

Siehe auch

Bearbeiten

Anmerkungen

Bearbeiten
  1. Das Vereinigungsaxiom wurde natürlich schon vorher zum Existenzbeweis der Funktion   benötigt.
  1. a b   sind ad-hoc-Bezeichnungen
  2. a b Mit   aufgefasst als homogene Relation und   lässt sich die transitive Hülle auch noch verstehen als
     .
    Siehe z. B. G. O’Regan:   für homogene Relationen  , Gerard O’Regan: Guide to Discrete Mathematics. Sets, Relations and Functions (= Texts in Computer Science (TCS)). Springer International Publishing, Schweiz 2016, S. 25–51, hier S. 39, doi:10.1007/978-3-319-44561-8_2 (springer.com [PDF; 1000 kB]).
  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.