6.3 Projektionen, inverse Relationen und Komposition

Mit Relationen als Mengen rechnen

Weil Relationen Mengen sind, gelten die bekannten Mengenoperationen auch für sie. Dabei bleiben die Grundmengen und die Bedeutung der Paare festgelegt.

Mengenoperationen. Für \(R,S\subseteq A\times B\) sind auch \(R\cup S\), \(R\cap S\) und \(R\setminus S\) Relationen von \(A\) nach \(B\).

• \((x,y)\in R\cup S\): mindestens eine der beiden Beziehungen gilt.
• \((x,y)\in R\cap S\): beide Beziehungen gelten.
• \((x,y)\in R\setminus S\): \((x,y)\in R\) und \((x,y)\notin S\).

Bei endlichen Paarmengen lässt sich jede Operation durch direkten Vergleich ausführen.

Beispiel: Zwei Pfeillisten

Seien \(R=\{(a,b),(b,c)\}\) und \(S=\{(b,c),(c,a)\}\) auf \(\{a,b,c\}\). Bestimmen Sie Vereinigung, Schnitt und Differenz.

HinweisLösungsweg

Es gilt \(R\cup S=\{(a,b),(b,c),(c,a)\}\), \(R\cap S=\{(b,c)\}\) und \(R\setminus S=\{(a,b)\}\). Das gemeinsame Paar \((b,c)\) steht in der Vereinigung nur einmal.

Welche Elemente kommen vor?

Eine Projektion behält nur eine Koordinate der Paare. Sie zeigt damit, welche Elemente überhaupt an der Beziehung beteiligt sind.

Definition 6.9 (Projektionen). Für \(T\subseteq A\times B\) heißen \[ \begin{aligned} \Pi_1(T)&=\{x\in A\mid\exists y\in B:\ (x,y)\in T\},\\ \Pi_2(T)&=\{y\in B\mid\exists x\in A:\ (x,y)\in T\} \end{aligned} \] die Projektionen von \(T\) auf den ersten beziehungsweise zweiten Faktor.

Die Projektionen übersetzen die Vollständigkeitsbedingungen in Mengengleichheiten.

\(T\) ist linksvollständig genau dann, wenn \(\Pi_1(T)=A\), und rechtsvollständig genau dann, wenn \(\Pi_2(T)=B\).

Die Richtung umkehren

Durch Vertauschen der Einträge wird aus „Stadt liegt in Land“ die Beziehung „Land enthält Stadt“. Dabei kann sich auch die Eindeutigkeit ändern.

Definition 6.10 (Inverse Relation). Die inverse Relation zu \(T\subseteq A\times B\) ist \[ T^{-1}=\{(y,x)\mid(x,y)\in T\}\subseteq B\times A. \] Im Pfeildiagramm kehren wir alle Pfeile um; im Koordinatenbild vertauschen wir die Achsenrollen.

Zweimaliges Vertauschen macht die Änderung rückgängig: \((T^{-1})^{-1}=T\). Außerdem ist \(\Pi_1(T^{-1})=\Pi_2(T)\) und umgekehrt. Links- und Rechtsvollständigkeit sowie Links- und Rechtseindeutigkeit wechseln jeweils ihre Rollen. Die inverse Relation existiert immer; sie muss kein Funktionsgraph sein.

Bei einer Aufgabenverteilung zeigt die Umkehrung, wer eine bestimmte Aufgabe übernimmt.

Beispiel: Personen und Aufgaben

Für \(A=\{p,q,r\}\), \(B=\{u,v,w\}\) sei \(T=\{(p,u),(p,v),(q,v)\}\). Bestimmen Sie Projektionen und Inverse.

HinweisLösungsweg

\(\Pi_1(T)=\{p,q\}\) und \(\Pi_2(T)=\{u,v\}\). Durch Vertauschen folgt \(T^{-1}=\{(u,p),(v,p),(v,q)\}\). Die inverse Relation ist nicht rechtseindeutig: \(v\) hat zwei Partner.

Beziehungen hintereinander ausführen

Zwei Beziehungen lassen sich über ein gemeinsames Zwischenelement verbinden. Dieses Zwischenelement muss existieren, braucht aber nicht eindeutig zu sein.

Definition 6.11 (Komposition von Relationen). Für \(S\subseteq A\times B\) und \(T\subseteq B\times C\) definieren wir \[ \begin{aligned} T\circ S=\{&(x,z)\in A\times C\mid\\ &\exists y\in B:\ (x,y)\in S\land (y,z)\in T\}. \end{aligned} \tag{6.1}\]

Achtung: Reihenfolge der Auswertung ist von rechts nach links.

Eine Komposition lässt sich berechnen, indem man zu jedem ersten Pfeil alle passenden Fortsetzungen sucht.

Beispiel: Zwei Schritte zwischen drei Mengen

Seien \(A=\{a,b\}\), \(B=\{1,2,3\}\) und \(C=\{u,v\}\) sowie \(S=\{(a,1),(a,2),(b,3)\}\) und \(T=\{(1,u),(2,u),(2,v)\}\). Bestimmen Sie \(T\circ S\).

HinweisLösungsweg

Von \(a\) führen Wege über \(1\) nach \(u\) und über \(2\) nach \(u\) und \(v\). Von \(b\) führt der erste Pfeil nach \(3\); dort gibt es keine Fortsetzung. Also ist \(T\circ S=\{(a,u),(a,v)\}\). Zwei Wege nach \(u\) ergeben nur ein Paar \((a,u)\).

Klammern und Reihenfolge

Bei der Komposition von Relationen gilt die Assoziativität.

Satz 6.1 (Rechenregeln der Komposition). Für \(S\subseteq A\times B\), \(T\subseteq B\times C\), \(U\subseteq C\times D\) gilt \[ (U\circ T)\circ S=U\circ(T\circ S), \] \[ I_B\circ S=S=S\circ I_A,\qquad (T\circ S)^{-1}=S^{-1}\circ T^{-1}. \] Komposition ist assoziativ, im Allgemeinen aber nicht kommutativ.

Der Nachweis der Assoziativität beschreibt auf beiden Seiten denselben Weg.

Beweis

Beweis. Assoziativität. \((x,w)\) liegt genau dann in der linken Seite, wenn es \(z\in C\) und \(y\in B\) gibt mit \((x,y)\in S\), \((y,z)\in T\) und \((z,w)\in U\). Dies ist auch die Bedingung für die rechte Seite. Die Identitätsregeln folgen daraus, dass \(I_A\) und \(I_B\) nur Paare mit gleichen Einträgen enthalten. Beim Umkehren eines Weges werden sowohl die Pfeile als auch ihre Reihenfolge umgekehrt. \(\square\)

Wege mit mehreren Schritten

Eine Relation kann direkte Verbindungen beschreiben. Um auch indirekte Verbindungen zu erfassen, verketten wir sie mit sich selbst.

Definition 6.12 (Potenzen einer Relation). Für eine Relation \(T\) auf \(M\) setzen wir \[ T^0:=I_M,\qquad T^1:=T,\qquad T^{n+1}:=T\circ T^n\quad(n\geq1). \] \((x,y)\in T^n\) bedeutet: Es gibt einen gerichteten Weg von \(x\) nach \(y\) mit genau \(n\) Schritten; Knoten dürfen mehrfach vorkommen.

Hier bezeichnet \(T^n\) eine wiederholte Komposition, kein kartesisches Produkt. \(T^2\) enthält Wege mit genau zwei Schritten; es muss die direkten Pfeile von \(T\) nicht enthalten.

Zusammenfassung

• Projektionen sammeln vorkommende erste beziehungsweise zweite Einträge.
• Die inverse Relation vertauscht alle Paare und die Rollen von links und rechts.
• \(T\circ S\) bedeutet wie bei Funktionen: zuerst \(S\), dann \(T\).
• Bei der Komposition genügt ein passender Zwischenknoten; doppelte Wege erzeugen keine doppelten Paare.
• Klammern dürfen verschoben werden, die Reihenfolge im Allgemeinen nicht.
• \(T^n\) beschreibt Wege mit genau \(n\) Schritten in derselben Relation.