6.4 Reflexive, symmetrische und transitive Hüllen
Fehlende Paare gezielt ergänzen
Eine Hülle ergänzt so viele Paare wie nötig, um eine gewünschte Eigenschaft herzustellen. Bereits vorhandene Paare bleiben erhalten.
Definition 6.13 (Reflexive, symmetrische und transitive Hülle). Für \(T\subseteq M\times M\) heißen \[ \begin{aligned} {[T]}_{\mathrm{refl}}&=T\cup I_M,\\ {[T]}_{\mathrm{sym}}&=T\cup T^{-1},\\ {[T]}_{\mathrm{tran}}&=\bigcup_{n=1}^{\infty}T^n \end{aligned} \tag{6.2}\] die reflexive, symmetrische beziehungsweise transitive Hülle. Die reflexiv-transitive Hülle ist \(T^*=I_M\cup[T]_{\mathrm{tran}}\).
In Gleichung 6.2 ergänzt die reflexive Hülle alle Schlingen und die symmetrische Hülle alle Gegenpfeile. Die transitive Hülle verbindet jeden Anfang mit jedem auf einem Weg positiver Länge erreichbaren Ende. Sie wird auch \(T^+\) genannt.
Warum sind dies die kleinsten Ergänzungen?
„Kleinste“ bezieht sich hier auf die Teilmengenbeziehung, nicht auf die Anzahl ergänzter Paare allein.
Satz 6.2 (Minimalität der Hüllen). Für jede der Eigenschaften reflexiv, symmetrisch und transitiv ist die zugehörige Hülle \(H\) die kleinste Relation, die \(T\) enthält und die Eigenschaft besitzt:
- \(T\subseteq H\), und \(H\) besitzt die geforderte Eigenschaft.
- Für jede Relation \(R\) mit \(T\subseteq R\), die diese Eigenschaft besitzt, gilt \(H\subseteq R\).
Wir zeigen für jede Hülle zuerst (1): Sie enthält \(T\) und besitzt die geforderte Eigenschaft. Danach zeigen wir (2): Jede andere Relation mit diesen beiden Voraussetzungen enthält auch die Hülle.
Beweis
Beweis. Reflexive Hülle: Setze \(H=T\cup I_M\).
Zu (1): Wegen der Vereinigung gilt \(T\subseteq H\). Für jedes \(x\in M\) liegt \((x,x)\) in \(I_M\) und damit in \(H\). Also ist \(H\) reflexiv.
Zu (2): Sei \(R\) eine beliebige reflexive Relation auf \(M\) mit \(T\subseteq R\). Weil \(R\) reflexiv ist, enthält sie alle Paare \((x,x)\), also \(I_M\subseteq R\). Damit enthält \(R\) beide Mengen \(T\) und \(I_M\), also auch ihre Vereinigung: \(H=T\cup I_M\subseteq R\). Somit ist \(H\) die kleinste reflexive Relation, die \(T\) enthält. \(\square\)
Symmetrische Hülle: Setze \(H=T\cup T^{-1}\).
Zu (1): Wieder gilt \(T\subseteq H\). Um die Symmetrie zu zeigen, sei \((x,y)\in H\). Dann gibt es zwei Fälle:
- Ist \((x,y)\in T\), so liegt das umgekehrte Paar \((y,x)\) in \(T^{-1}\subseteq H\).
- Ist \((x,y)\in T^{-1}\), so liegt \((y,x)\) bereits in \(T\subseteq H\).
In beiden Fällen gehört \((y,x)\) zu \(H\). Also ist \(H\) symmetrisch.
Zu (2): Sei \(R\) eine beliebige symmetrische Relation auf \(M\) mit \(T\subseteq R\). Für jedes \((x,y)\in T^{-1}\) gilt \((y,x)\in T\subseteq R\). Wegen der Symmetrie von \(R\) liegt dann auch \((x,y)\) in \(R\). Also ist \(T^{-1}\subseteq R\) und somit \(H=T\cup T^{-1}\subseteq R\). Damit ist \(H\) die kleinste symmetrische Relation, die \(T\) enthält. \(\square\)
Transitive Hülle: Setze \(H=\bigcup_{n\geq1}T^n\).
Zu (1): Wegen \(T=T^1\) ist \(T\subseteq H\).
Für \((x,y)\in T^j\) und \((y,z)\in T^k\) ergibt das Aneinanderhängen der Wege \((x,z)\in T^{j+k}\subseteq H\). Also ist \(H\) transitiv.
Zu (2): Enthält eine transitive Relation \(R\) die Relation \(T\), dann enthält sie per Induktion jedes \(T^n\): Der Anfang \(T\subseteq R\) ist gegeben.
Aus \(T^n\subseteq R\) folgt \[ T^{n+1}=T\circ T^n\subseteq R\circ R\subseteq R. \]
Daher ist auch \(H\subseteq R\). \(\square\)
Bei einer kurzen Kette lassen sich die drei Ergänzungen direkt vergleichen.
Beispiel: Drei Knoten in einer Kette
Auf \(M=\{p,q,r\}\) sei \(T=\{(p,q),(q,r)\}\). Bestimmen Sie alle drei Hüllen.
Transitive Hülle und Zyklen
Bei einem Kreisweg kann ein Element sich selbst nach mehreren Schritten erreichen. Deshalb können in einer transitiven Hülle auch neue Schlingen entstehen.
Beachte:
- Enthält \(T\) die Paare \((x,y)\) und \((y,x)\), so enthält \([T]_{\mathrm{tran}}\) auch \((x,x)\) und \((y,y)\). Durch das Bilden der transitiven Hülle können also Schlingen entstehen.
- Auf einer endlichen Menge kann man fehlende Abkürzungen wiederholt ergänzen, bis kein neues Paar hinzukommt. Da es nur \(|M|^2\) mögliche Paare gibt, endet dieses Verfahren nach endlich vielen Schritten.
Eigenschaften mit Mengenoperationen prüfen
Mit Identität, Inverse und Komposition können wir die bisherigen Eigenschaften ohne ausgeschriebene Quantoren formulieren.
Satz 6.3 (Mengenkriterien für Relationseigenschaften). Für \(T\subseteq M\times M\) gilt:
| Eigenschaft | Gleichwertiges Mengenkriterium |
|---|---|
| reflexiv | \(I_M\subseteq T\) |
| symmetrisch | \(T^{-1}=T\) |
| antisymmetrisch | \(T\cap T^{-1}\subseteq I_M\) |
| asymmetrisch | \(T\cap T^{-1}=\emptyset\) |
| transitiv | \(T\circ T\subseteq T\) |
Beispielsweise sammelt \(T\cap T^{-1}\) genau die Paare, deren Gegenpaare auch vorhanden sind. Antisymmetrie erlaubt davon nur Diagonalpaare. Für Symmetrie genügt sogar \(T^{-1}\subseteq T\): Durch Invertieren folgt dann die umgekehrte Inklusion.
Die Relation \(T\circ T\) enthält genau die Paare \((x,z)\), für die es ein \(y\) mit \((x,y)\in T\) und \((y,z)\in T\) gibt. Jedes dieser Paare beschreibt also eine Verbindung über zwei Schritte. Transitivität verlangt, dass die direkte Verbindung \((x,z)\) bereits in \(T\) liegt. Daher lautet das Kriterium \(T\circ T\subseteq T\).
Ist dieses Kriterium erfüllt, kommen auch bei weiteren Kompositionen mit \(T\) keine Paare hinzu, die nicht schon in \(T\) liegen: In einem längeren Weg können wir jeweils zwei aufeinanderfolgende Schritte durch eine direkte Verbindung aus \(T\) ersetzen. So erhalten wir schließlich die direkte Verbindung vom Anfang zum Ende des gesamten Weges. Es gilt also \(T^n\subseteq T\) für jedes \(n\geq1\); die transitive Hülle ist dann bereits \(T\) selbst.
Zusammenfassung
- \(T^n\) beschreibt Wege mit genau \(n\) Schritten.
- Hüllen enthalten die Ausgangsrelation und ergänzen nur notwendige Paare.
- Die transitive Hülle enthält alle durch Wege positiver Länge erreichbaren Paare.
- Zyklen können Schlingen erzwingen; die reflexiv-transitive Hülle enthält stets alle Schlingen.
- Identität, Inverse und Komposition liefern kompakte Kriterien für die Eigenschaften.