Transitive Relation

Bei einer transitiven Relation handelt es sich um eine zweistellige Relation \(R\) auf einer Menge, bei der aus \((a,b) \in R\) und \((b,c) \in R\) stets \((a,c) \in R\) folgt. Transitivität ist eine der Voraussetzungen für Äquivalenz- und Ordnungsrelationen.

Eine mit der Transitivität eng verwandte Eigenschaft von Relationen ist Antitransitivität.

Definition

Sei \(A\) eine Menge und \(R \subseteq A \times A\) eine auf dieser Menge definierte zweistellige Relation. Die Relation \(R\) heißt transitiv, falls gilt:

Steht ein Element \(a\) also in Relation mit einem Element \(b\), und steht \(b\) in Relation mit einem Element \(c\), so stehen auch stets \(a\) und \(c\) in Relation. Betrachtet man den zur Relation gehörenden gerichteten Graphen, so gibt es also stets eine direkte Kante von \(a\) nach \(c\), falls es Kanten von \(a\) nach \(b\) und von \(b\) nach \(c\) gibt. Die Elemente \(a\), \(b\) und \(c\) müssen hierbei nicht notwendigerweise verschieden sein.

Ist die Transitivitätsbedingung verletzt, so ist die Relation nicht transitiv bzw. intransitiv.

Hinweis: Eine Relation ist transitiv, solange die Transitivitätsbedingung nicht explizit verletzt ist. Es ist insbesondere nicht notwendig, dass Elemente \(a,b,c \in A\) mit \((a,b) \in R\) und \((b,c) \in R\) tatsächlich existieren.

Beispiele

Beispiel 1

Gegeben sei die Menge \(A = \bigl\{ a,b,c,d \bigr\}\) sowie eine auf dieser Menge definierte zweistellige Relation \(R_1\) mit

Die Relation \(R_1\) ist transitiv, da für alle Elemente \(x,y,z \in A\) stets gilt: Aus \((x,y) \in R_1\) und \((y,z) \in R_1\) folgt \((x,z) \in R_1\).

Beispiel 2

Gegeben sei die Menge \(A = \bigl\{ a,b,c,d \bigr\}\) sowie eine auf dieser Menge definierte zweistellige Relation \(R_2\) mit

Die Relation \(R_2\) ist nicht transitiv, da die Transitivitätsbedingung verletzt ist:

• Es gilt \((a,c) \in R_2\) und \((c,d) \in R_2\), aber \((a,d) \notin R_2\).
• Hinweis: \((a,b) \notin R_2\) ist trotz \((b,c) \in R_2\) und \((a,c) \in R_2\) keine Verletzung der Transitivitätsbedingung, da es nicht notwendig ist, die Voraussetzungen für Transitivität zu schaffen, sondern lediglich das Erfülltsein der Bedingung zu prüfen, falls die Voraussetzungen erfüllt sind.

Beispiel 3

Gegeben sei die Menge \(A = \bigl\{ a,b,c,d \bigr\}\) sowie eine auf dieser Menge definierte zweistellige Relation \(R_3\) mit

Die Relation \(R_3\) ist nicht transitiv, da die Transitivitätsbedingung verletzt ist:

• Es gilt \((a,b) \in R_3\) und \((b,a) \in R_3\), aber \((a,a) \notin R_3\).
• Es gilt \((b,a) \in R_3\) und \((a,b) \in R_3\), aber \((b,b) \notin R_3\).

Beispiel 4

Gegeben sei die Menge \(A = \bigl\{ a,b,c,d \bigr\}\) sowie eine auf dieser Menge definierte zweistellige Relation \(R_4\) mit

Die Relation \(R_4\) ist transitiv, da für alle Elemente \(x,y,z \in A\) stets gilt: Aus \((x,y) \in R_4\) und \((y,z) \in R_4\) folgt \((x,z) \in R_4\). Da die Relation \(R_4\) keine Elemente enthält, existieren insbesondere auch keine Verletzungen der Transitivitätsbedingung.

Beispiele in der Mathematik

Gleichheit von Zahlen

Bei der Gleichheit \(=\) von natürlichen, ganzen, rationalen, reellen oder komplexen Zahlen handelt es sich um transitive Relationen. Aus \(x=y\) und \(y=z\) folgt stets \(x=z\). Es handelt sich bei der Gleichheit \(=\) sogar um eine Äquivalenzrelation.

Bei der Ungleichheit \(\neq\) handelt es sich um eine intransitive Relation, da aus \(x \neq y\) und \(y \neq z\) nicht immer \(x \neq z\) folgt: Beispielsweise gilt \(1 \neq 2\) und \(2 \neq 1\), aber nicht \(1 \neq 1\).

Anordnen von Zahlen

Bei der Kleinergleich-Relation \(\leq\) von natürlichen, ganzen, rationalen oder reellen Zahlen handelt es sich um transitive Relationen. Gilt sowohl \(a \leq b\) als auch \(b \leq c\), so folgt stets \(a \leq c\). Dasselbe gilt analog für die Kleiner-Relation \(\lt\), die Größergleich-Relation \(\geq\) und die Größer-Relation \(\gt\) . In allen Fällen handelt es sich um Ordnungsrelationen.

Teilbarkeit

Die Teilbarkeitsrelation \(\mid\) für natürliche und ganze Zahlen ist transitiv. Gilt \(a \mid b\) und \(b \mid c\), so folgt stets \(a \mid c\). Es handelt sich bei der Teilbarkeitsrelation (für natürliche Zahlen) um eine Ordnungsrelation.

Kongruenz modulo \(m\)

Zwei ganze Zahlen \(a\) und \(b\) heißen kongruent modulo \(m\), wenn sie bei Division durch \(m\) denselben Rest lassen. Gilt \(a \equiv b \pmod{m}\) und \(b \equiv c \pmod{m}\), so gilt auch \(a \equiv c \pmod{m}\). Die Kongruenzrelation ist transitiv und sogar eine Äquivalenzrelation.

Teilmenge

Die Teilmengenbeziehung \(\subseteq\) ist transitiv. Gilt für Mengen \(A\), \(B\) und \(C\) sowohl \(A \subseteq B\) als auch \(B \subseteq C\), so folgt stets \(A \subseteq C\). Dies gilt analog für die echte Teilmengenbeziehung \(\subset\). Es handelt sich bei der (echten) Teilmengenbeziehung um eine Ordnungsrelation.

Eigenschaften

Für transitive Relationen gelten unter anderem die folgenden Eigenschaften:

• Die Transitivität einer Relation \(R\) erlaubt auch Aussagen über mehrere (Zwischen-)Schritte \(b_1,\ldots,b_n\) hinweg:
  \[ (a,b_1) \in R \cap (b_1,b_2) \in R \cap \ldots \cap (b_n,c) \in R \Rightarrow (a,c) \in R. \]
• Ist eine Relation \(R\) transitiv, so ist auch ihre Umkehrrelation \(R^{-1}\) transitiv.
• Sind \(R\) und \(S\) transitive Relationen, so sind auch ihr Schnitt \(R \cap S\) eine transitive Relation. Die Aussage gilt analog für den Schnitt von mehr als zwei Relationen.
• Die kleinste transitive Relation \(S\), die eine gegebene Relation \(R\) vollständig enthält, wird transitive Hülle genannt.