6.2 Eigenschaften binärer Relationen
Hat jedes Element einen Partner?
Zuerst untersuchen wir eine Relation \(T\subseteq A\times B\) zwischen zwei möglicherweise verschiedenen Mengen. Vollständigkeit fragt nach dem Vorhandensein von Partnern; Eindeutigkeit begrenzt deren Anzahl.
Definition 6.4 (Links- und Rechtsvollständigkeit). Eine Relation \(T\subseteq A\times B\) heißt
- linksvollständig (linkstotal), wenn \(\forall x\in A\;\exists y\in B:\ (x,y)\in T\);
- rechtsvollständig (rechtstotal), wenn \(\forall y\in B\;\exists x\in A:\ (x,y)\in T\).
Links beziehungsweise rechts darf kein Element ohne Partner bleiben.
Ist der Partner eindeutig?
Die Anzahl möglicher Partner wird unabhängig davon geprüft, ob es überhaupt einen gibt.
Definition 6.5 (Rechts- und Linkseindeutigkeit). Eine Relation \(T\subseteq A\times B\) heißt
- rechtseindeutig, wenn aus \((x,y_1)\in T\) und \((x,y_2)\in T\) stets \(y_1=y_2\) folgt;
- linkseindeutig, wenn aus \((x_1,y)\in T\) und \((x_2,y)\in T\) stets \(x_1=x_2\) folgt.
Bei Rechtseindeutigkeit hat jedes \(x\in A\) höchstens einen Partner in \(B\); bei Linkseindeutigkeit hat jedes \(y\in B\) höchstens einen Partner in \(A\).
Der Übergang zum Funktionsbegriff
Eine Funktion verlangt für jeden Eingang genau einen Ausgang. Dafür müssen Existenz und Eindeutigkeit zusammenkommen.
Funktionen als Relationen. Eine linksvollständige und rechtseindeutige Relation \(T\subseteq A\times B\) ist der Graph einer Funktion \(A\to B\). Jedes Element von \(A\) hat dann genau einen Partner in \(B\).
Im Kapitel Funktionen beschäftigen wir uns näher mit diesen speziellen Relationen.
Schon ein zusätzliches Element in der Zielmenge kann die Rechtsvollständigkeit verändern.
Beispiel: Räume und Etagen
Seien \(A=\{r_1,r_2,r_3\}\), \(B=\{0,1,2\}\) und \(T=\{(r_1,0),(r_2,0),(r_3,1)\}\). Prüfen Sie die vier Eigenschaften.
Eigenschaften auf derselben Menge
Nun sei \(T\subseteq M\times M\). Erst auf derselben Grundmenge können wir unmittelbar nach Selbstbeziehungen und nach der umgekehrten Beziehung fragen.
Definition 6.6 (Reflexivität und Symmetrie). Eine Relation \(T\) auf \(M\) heißt
- reflexiv, wenn \(\forall x\in M:\ (x,x)\in T\);
- irreflexiv, wenn \(\forall x\in M:\ (x,x)\notin T\);
- symmetrisch, wenn \(\forall x,y\in M:\ (x,y)\in T\Rightarrow (y,x)\in T\).
Reflexivität verlangt eine Schlinge an jedem Knoten, Irreflexivität verbietet alle Schlingen. Eine Relation mit nur einigen Schlingen ist weder reflexiv noch irreflexiv. Symmetrie verlangt zu jedem Pfeil den Gegenpfeil; im Koordinatenbild ist das eine Spiegelung an der Diagonalen.
Antisymmetrie und Asymmetrie
Antisymmetrie verbietet Gegenpfeile zwischen verschiedenen Knoten. Asymmetrie verbietet zusätzlich alle Schlingen. Genauer gesagt gilt:
Definition 6.7 (Antisymmetrie und Asymmetrie). Eine Relation \(T\) auf \(M\) heißt
- antisymmetrisch, wenn \(\forall x,y\in M:\ ((x,y)\in T\land (y,x)\in T)\Rightarrow x=y\);
- asymmetrisch, wenn \(\forall x,y\in M:\ (x,y)\in T\Rightarrow(y,x)\notin T\).
Die Vorsilbe „anti“ bedeutet hier nicht die logische Verneinung von Symmetrie.
Beachte:
- \(I_M\) ist symmetrisch und antisymmetrisch zugleich.
- Für \(M\neq\emptyset\) ist \(I_M\) nicht asymmetrisch.
- Eine Relation ist genau dann asymmetrisch, wenn sie antisymmetrisch und irreflexiv ist.
Transitivität
Eine Beziehung kann sich entlang zweier aufeinanderfolgender Pfeile fortsetzen. Transitivität fordert dann auch die direkte Verbindung.
Definition 6.8 (Transitivität). Eine Relation \(T\) auf \(M\) heißt transitiv, wenn \[ \forall x,y,z\in M: ((x,y)\in T\land (y,z)\in T)\Rightarrow (x,z)\in T. \]
Schematische Darstellung:
In der Darstellung als gerichteter Graph: Jeder Weg aus zwei Pfeilen muss also einen direkten Pfeil vom Anfang zum Ende haben.
Die Variablen müssen nicht verschieden sein: Gilt in einer transitiven Relation \((x,y)\in T\) und \((y,x)\in T\), so muss auch \((x,x)\in T\) gelten.
Ein einziges passendes Gegenbeispiel genügt, um eine allgemeine Eigenschaft zu widerlegen.
Beispiel: Ein Weg ohne Abkürzung
Prüfen Sie \(T=\{(a,b),(b,c)\}\) auf \(M=\{a,b,c\}\) auf die Eigenschaften Reflexivität, Irreflexivität, Symmetrie, Antisymmetrie, Asymmetrie und Transitivität.
Zusammenfassung
- Vollständigkeit bedeutet „mindestens ein“, Eindeutigkeit „höchstens ein“.
- Linksvollständigkeit und Rechtseindeutigkeit ergeben einen Funktionsgraphen.
- Reflexivität, Symmetrie und Transitivität lassen sich an Schlingen, Gegenpfeilen und Abkürzungen prüfen.
- Antisymmetrie erlaubt Schlingen; Asymmetrie verbietet sie.
- Für einen Nachweis sind alle möglichen Fälle zu berücksichtigen; zum Widerlegen genügt ein Gegenbeispiel.