Transitive Relation (Transitivität)
Eine transitive Relation ist eine zweistellige Relation $R$ auf einer Menge, bei der für alle Elemente der Menge aus $(a,b) \in R$ und $(b,c) \in R$ stets $(a,c) \in R$ folgt. Diese Eigenschaft wird in der Mathematik auch Transitivität genannt. Sie ist eine der Voraussetzungen für Äquivalenz- und Ordnungsrelationen.
Eine mit der Transitivität eng verwandte Eigenschaft ist die Antitransitivität.
Definition
Sei $A$ eine Menge und $R \subseteq A \times A$ eine auf dieser Menge definierte binäre Relation. Die Relation $R$ heißt transitiv, falls die folgende Eigenschaft gilt:
In Worten: Eine Relation ist genau dann transitiv, wenn für alle Elemente der zugrundeliegenden Menge gilt: Steht ein Element $a$ in Relation mit einem Element $b$, und steht $b$ wiederum in Relation mit einem Element $c$, so stehen stets auch $a$ und $c$ in Relation. Die Elemente $a$, $b$ und $c$ müssen hierbei nicht notwendigerweise verschieden sein. Wird der zur Relation gehörende gerichtete Graph betrachtet, so gibt es entsprechend stets eine direkte Kante von $a$ nach $c$, falls es Kanten von $a$ nach $b$ und von $b$ nach $c$ gibt.
Diese Eigenschaft wird auch als Transitivität bezeichnet. 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 tatsächlich Elemente $a$, $b$ und $c$ existieren, für die $(a,b) \in R$ und $(b,c) \in R$ gilt.
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 eine Ordnungsrelation.
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 bzw. Transitivität 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.