Relation

Bei einer Relation handelt es sich um eine Beziehung, die zwischen Dingen, z. B. zwischen Elementen von Mengen, bestehen kann. Hierbei ist es stets klar, ob bestimmte Elemente in Relation stehen oder nicht; sie stehen niemals ein bisschen oder nur teilweise in Relation.

Sofern nicht ausdrücklich etwas anderes angegeben ist, versteht man unter einer Relation im Normalfall eine zweistellige oder binäre Relation.

Definition

Zweistellige (bzw. binäre) Relation

Bei einer zweistelligen (oder binären) Relation \(\mathbf{R}\) zwischen zwei Mengen \(A\) und \(B\) handelt es sich um eine beliebige Teilmenge des kartesischen Produkts der Mengen \(A\) und \(B\).

Die Menge \(A\) wird hierbei als Quellmenge (engl. set of departure) bezeichnet; die Menge \(B\) als Zielmenge (engl. set of destination). Eine Relation zwischen zwei verschiedenen Mengen \(A\) und \(B\) wird auch als heterogene Relation bezeichnet.

Stehen zwei Elemente \(a,b \in A\) in Relation, so schreibt man \((a,b) \in R\) bzw. \(aRb\). Stehen die beiden Elemente nicht in Relation, so schreibt man analog \((a,b) \notin R\) bzw. \(a \mathord{\not\mathrel{R}} b\).

Zweistellige (bzw. binäre) Relation auf einer Menge

Bei einer zweistelligen (oder binären) Relation \(\mathbf{R}\) auf der Menge \(\mathbf{A}\) handelt es sich um eine beliebige Teilmenge des kartesischen Produkts der Menge \(A\) mit sich selbst.

Eine zweistellige Relation auf einer Menge \(A\) wird auch als homogene Relation bezeichnet.

Dreistellige (bzw. ternäre) Relation

Bei einer dreistelligen (oder ternären) Relation \(\mathbf{R}\) zwischen drei Mengen \(A\), \(B\) und \(C\) handelt es sich um eine beliebige Teilmenge des kartesischen Produkts der Mengen \(A\), \(B\) und \(C\).

\(\mathbf{n}\)-stellige Relation

Bei einer \(\mathbf{n}\)-stelligen Relation \(\mathbf{R}\) zwischen Mengen \(A_1,\ldots,A_n\) handelt es sich um eine beliebige Teilmenge des kartesischen Produkts der Mengen \(A_1,\ldots,A_n\).

Null- und Allrelation

Bei einer Relation handelt es sich um eine beliebige Teilmenge des entsprechenden kartesischen Produkts:

• Handelt es sich bei der Relation \(R\) um die leere Menge, gilt also \(R = \emptyset\), so spricht man von der Nullrelation.
• Handelt es sich bei der Relation \(R\) um das vollständige kartesische Produkt, gilt also \(R = A \times A\), so spricht man von der All- oder Universalrelation.

Umkehrrelation

Die Umkehrrelation \(R^{-1} \subseteq B \times A\) (auch konverse Relation, Konverse oder inverse Relation) einer zweistelligen Relation \(R \subseteq A \times B\) ist definiert als

Beispielsweise handelt es sich bei der Umkehrrelation der Kleinergleich-Relation \(\leq\) um die Größergleich-Relation \(\geq\).

Im Allgemeinen handelt es sich bei der Umkehrrelation einer \(n\)-stelligen Relation um eine Permutation der Koordinaten der in ihr enthaltenen \(n\)-Tupel, beispielsweise die Vertauschung von genau 2 Koordinaten oder die Umkehrung bzw. Spiegelung der Reihenfolge.

Komplementäre Relation

Die komplementäre Relation \(R^c \subseteq A \times B\) einer Relation \(R \subseteq A \times B\) ist definiert als

Beispielsweise handelt es sich bei der komplementären Relation der Kleinergleich-Relation \(\leq\) um die Größer-Relation \(\gt\).

Die komplementäre Relation für \(n\)-stellige Relationen \(R \subseteq A_1 \times \ldots \times A_n\) werden analog definiert. Es gilt

Für die komplementäre Relation gilt stets \({\left( R^c \right)}^c = \overline{\overline{R}} = R\).

Darstellung

Darstellung als Menge

Da es sich bei einer Relation um eine Teilmenge eines kartesischen Produkts handelt, ist es naheliegend, diese direkt als Menge von Paaren, Tripeln oder allgemein von Tupeln anzugeben. Im Gegensatz zu den nachfolgenden Darstellungsmethoden ist die Darstellung als Menge für beliebige \(n\)-stellige Relationen stets möglich.

Darstellung über gerichtete Graphen

Zweistellige Relationen \(R\) auf einer Menge \(A\) können als gerichtete Graphen dargestellt werden. Jedes Element entspricht dabei einem Knoten des Graphen. Zwei Knoten \(a\) und \(b\) sind genau dann durch eine gerichtete Kante \((a,b)\) von \(a\) nach \(b\) verbunden, wenn das Element \(a\) in Relation mit dem Element \(b\) steht, wenn also \((a,b) \in R\) bzw. \(aRb\) gilt. Existiert keine Kante zwischen den Elementen \(a\) und \(b\), so stehen diese nicht in Relation – es gilt also \((a,b) \notin R\) bzw. \(a\mathord{\not\mathrel{R}}b\).

Kanten \((a,a)\) von einem Element \(a\) zu sich selbst werden als Schlingen bezeichnet.

Die Relation bestimmt lediglich, welche Knoten durch Kanten verbunden sind – die konkrete Anordnung der Knoten und Kanten ist keine Eigenschaft der Relation und kann beliebig gewählt werden.

Darstellung über Adjazenzmatrizen

Da zweistellige Relationen \(R\) auf einer Menge \(A\) als gerichtete Graphen dargestellt werden können, sind auch andere Darstellungsformen für gerichtete Graphen – wie beispielsweise Adjazenzmatrizen – möglich. Der Eintrag in Zeile \(a\) und Spalte \(b\) ist genau dann eine \(1\), wenn \(a\) in Relation mit \(b\) steht, wenn also \((a,b) \in R\) gilt; andernfalls ist der Eintrag eine \(0\).

Die Darstellung als Adjazenzmatrix bietet unter anderem Vorteile beim Überprüfen der Eigenschaften von Relationen.

Beispiel

Gegeben sei eine Menge \(A = \bigl\{ a,b,c,d,e \bigr\}\). Auf dieser Menge wird eine zweistellige Relation \(R \subseteq A \times A\) exemplarisch wie folgt definiert:

Als gerichteter Graph kann die Relation \(R\) beispielsweise wie folgt dargestellt werden. Jede Kante entspricht dabei einem der Wertepaare aus der Menge \(R\).

Für die Relation \(R\) ergibt sich außerdem die folgende Adjazenzmatrix:

Eigenschaften

Symmetrie

Hauptartikel: Symmetrie, Antisymmetrie, Asymmetrie

Eine zweistellige Relation \(R\) auf einer Menge \(A\) heißt

• symmetrisch, falls gilt:
  \[ \forall a,b \in A: (a,b) \in R \Rightarrow (b,a) \in R. \]
• nicht symmetrisch, falls gilt:
  \[ \exists a,b \in A: (a,b) \in R \wedge (b,a) \notin R. \]
• antisymmetrisch, falls gilt:
  \[ \forall a,b \in A \text{ mit } a \neq b: (a,b) \in R \Rightarrow (b,a) \notin R. \]
• nicht antisymmetrisch, falls gilt:
  \[ \exists a,b \in A \text{ mit } a \neq b: (a,b) \in R \wedge (b,a) \in R. \]
• asymmetrisch, falls gilt:
  \[ \forall a,b \in A: (a,b) \in R \Rightarrow (b,a) \notin R. \]

Reflexivität

Hauptartikel: Reflexivität, Irreflexivität

Eine zweistellige Relation \(R\) auf einer Menge \(A\) heißt

• reflexiv, falls gilt:
  \[ \forall a \in A: (a,a) \in R. \]
• nicht reflexiv, falls gilt:
  \[ \exists a \in A: (a,a) \notin R. \]
• irreflexiv, falls gilt:
  \[ \forall a \in A: (a,a) \notin R. \]
• nicht irreflexiv, falls gilt:
  \[ \exists a \in A: (a,a) \in R. \]

Transitivität

Hauptartikel: Transitivität, Antitransitivität

Eine zweistellige Relation \(R\) auf einer Menge \(A\) heißt

• transitiv, falls gilt:
  \[ \forall a,b,c \in A: (a,b) \in R \wedge (b,c) \in R \Rightarrow (a,c) \in R. \]
• nicht transitiv bzw. intransitiv, falls gilt:
  \[ \exists a,b,c \in A: (a,b) \in R \wedge (b,c) \in R \wedge (a,c) \notin R. \]
• antitransitiv, falls gilt:
  \[ \forall a,b,c \in A: (a,b) \in R \wedge (b,c) \in R \Rightarrow (a,c) \notin R. \]
• nicht antitransitiv, falls gilt:
  \[ \exists a,b,c \in A: (a,b) \in R \wedge (b,c) \in R \wedge (a,c) \in R. \]

Allgemeine Eigenschaften

Eine zweistellige Relation \(R\) auf einer Menge \(A\) heißt

• total bzw. vollständig, falls gilt:
  \[ \forall a,b \in A: (a,b) \in R \vee (b,a) \in R. \]
• konnex bzw. verbunden, falls gilt:
  \[ \forall a,b \in A \text{ mit } a \neq b: (a,b) \in R \vee (b,a) \in R. \]
• trichotom, falls gilt:
  \[ \forall a,b \in A: \bigl( (a,b) \in R \cap (b,a) \notin R \bigr) \vee \bigl( (b,a) \in R \cap (a,b) \notin R \bigr) \vee a=b. \]

Äquivalenzrelation

Hauptartikel: Äquivalenzrelation

Bei einer Äquivalenzrelation handelt es sich um eine zweistellige Relation \(R\) auf einer Menge \(A\), die symmetrisch, reflexiv und transitiv ist. Sie fasst äquivalente Elemente – beispielsweise Elemente mit gleichen Eigenschaften – zu disjunkten Äquivalenzklassen zusammen. Jedes Element steht mit allen Elementen derselben Äquivalenzklasse in Relation. Kein Element steht mit einem Element einer anderen Äquivalenzklasse in Relation.

Ordnungsrelation

Hauptartikel: Ordnungsrelation

Bei einer Ordnungsrelation handelt es sich um eine zweistellige Relation \(R\) auf einer Menge \(A\), die antisymmetrisch, reflexiv und transitiv ist. Sie ordnet die Elemente der Menge nach einem bestimmten Kriterium an – beispielsweise nach der Größe. Hierbei ist es prinzipiell zulässig, dass nicht alle Elemente angeordnet werden können, dass also weder \((a,b) \in R\) noch \((b,a) \in R\) gilt; die Elemente \(a\) und \(b\) sind in diesem Fall unvergleichbar.

Hüllenbildung

Zu einer zweistelligen Relation \(R\) über einer Menge \(A\) können verschiedene Hüllen gebildet werden, die bestimmte Eigenschaften vorweisen:

• Bei der reflexiven Hülle handelt es sich um die kleinste reflexive Relation, die die gegebene Relation \(R\) vollständig enthält.
• Bei der symmetrischen Hülle handelt es sich um die kleinste symmetrische Relation, die die gegebene Relation \(R\) vollständig enthält.
• Bei der transitiven Hülle handelt es sich um die kleinste transitive Relation, die die gegebene Relation \(R\) vollständig enthält.
• Bei der reflexiven und transitiven Hülle handelt es sich um die kleinste reflexive und transitive Relation, die die gegebene Relation \(R\) vollständig enthält.