Transitive Relation

Eine transitive Relation ist in der Mathematik eine zweistellige Relation ${\displaystyle R}$ auf einer Menge, die die Eigenschaft hat, dass für drei Elemente ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle z}$ dieser Menge aus ${\displaystyle xRy}$ und ${\displaystyle yRz}$ stets ${\displaystyle xRz}$ folgt. Beispiele für transitive Relationen sind die Gleich- und die Kleiner-Relationen auf den reellen Zahlen, denn für drei reelle Zahlen ${\displaystyle x}$, ${\displaystyle y}$ und ${\displaystyle z}$ mit ${\displaystyle x=y}$ und ${\displaystyle y=z}$ gilt immer auch ${\displaystyle x=z}$, und aus ${\displaystyle x<y}$ und ${\displaystyle y<z}$ folgt ${\displaystyle x<z}$.

Zwei transitive und eine nicht transitive Relation (rechts unten), als gerichtete Graphen dargestellt

Eine n​icht transitive Relation heißt intransitiv (nicht z​u verwechseln m​it negativer Transitivität). Die Transitivität i​st eine d​er Voraussetzungen für e​ine Äquivalenzrelation o​der eine Ordnungsrelation.

Formale Definition

Ist ${\displaystyle M}$ eine Menge und ${\displaystyle R\subseteq M\times M}$ eine zweistellige Relation auf ${\displaystyle M}$, dann heißt ${\displaystyle R}$ transitiv, wenn (unter Verwendung der Infixnotation) gilt:

${\displaystyle \forall x,y,z\in M:xRy\land yRz\Rightarrow xRz.}$

Darstellung als gerichteter Graph

Jede beliebige Relation ${\displaystyle R}$ auf einer Menge ${\displaystyle M}$ kann als gerichteter Graph aufgefasst werden (Beispiel siehe oben). Die Knoten des Graphen sind dabei die Elemente von ${\displaystyle M}$. Vom Knoten ${\displaystyle a}$ zum Knoten ${\displaystyle b}$ wird genau dann eine gerichtete Kante (ein Pfeil ${\displaystyle a\longrightarrow b}$) gezogen, wenn ${\displaystyle aRb}$ gilt.

Die Transitivität von ${\displaystyle R}$ lässt sich im Graphen nun so charakterisieren: Wann immer zwei Pfeile aufeinanderfolgen (${\displaystyle a\longrightarrow b\longrightarrow c}$), gibt es auch einen Pfeil, der Anfangs- und Endknoten direkt verbindet (${\displaystyle a\longrightarrow c}$) (so auch im Hasse-Diagramm).

Eigenschaften

• Die Transitivität einer Relation ${\displaystyle R}$ erlaubt auch Schlüsse über mehrere Schritte hinweg (wie man leicht durch vollständige Induktion zeigt):

  ${\displaystyle a\,R\,b_{1}\,R\,b_{2}\,R\,\dots \,R\,b_{n}\,R\,c\implies a\,R\,c}$

• Mit Hilfe der Verkettung ${\displaystyle \circ }$ von Relationen lässt sich die Transitivität auch durch die folgende Bedingung charakterisieren:

  ${\displaystyle R\circ R\subseteq R}$

• Ist die Relation ${\displaystyle R}$ transitiv, dann gilt dies auch für die konverse Relation ${\displaystyle R^{-1}}$. Beispiele: die zu ${\displaystyle \leq }$ konverse Relation ist ${\displaystyle \geq }$, die zu ${\displaystyle <\ }$ konverse ist ${\displaystyle >\ }$.
• Sind die Relationen ${\displaystyle R}$ und ${\displaystyle S}$ transitiv, dann gilt dies auch für ihre Schnittmenge ${\displaystyle R\cap S}$. Diese Aussage lässt sich von zwei Relationen auf den Durchschnitt ${\displaystyle \cap _{i\in I}R_{i}}$ einer beliebigen Familie von transitiven Relationen verallgemeinern.
• Zu jeder beliebigen Relation ${\displaystyle R}$ gibt es eine kleinste transitive Relation ${\displaystyle S}$, die ${\displaystyle R}$ enthält, die sogenannte transitive Hülle von ${\displaystyle R}$.
  Beispiel: ${\displaystyle R}$ sei die Vorgängerrelation auf der Menge der natürlichen Zahlen, es gelte also ${\displaystyle a\,R\,b:\Longleftrightarrow a=b-1}$. Die Relation ${\displaystyle R}$ selbst ist nicht transitiv. Als transitive Hülle von ${\displaystyle R}$ ergibt sich die Kleiner-Relation ${\displaystyle <\ }$.

Beispiele

Ordnung der reellen Zahlen

Aus a > b und b > c folgt a > c

Die Kleiner-Relation ${\displaystyle <\ }$ auf den reellen Zahlen ist transitiv, denn aus ${\displaystyle x<y}$ und ${\displaystyle y<z}$ folgt ${\displaystyle x<z}$. Sie ist darüber hinaus eine strenge Totalordnung.

Ebenso sind die Relationen ${\displaystyle >\ }$, ${\displaystyle \leq \ }$ und ${\displaystyle \geq \ }$ transitiv.

Gleichheit der reellen Zahlen

Die gewöhnliche Gleichheit ${\displaystyle =\ }$ auf den reellen Zahlen ist transitiv, denn aus ${\displaystyle x=y}$ und ${\displaystyle y=z}$ folgt ${\displaystyle x=z}$. Sie ist darüber hinaus eine Äquivalenzrelation.

Die Ungleichheitsrelation ${\displaystyle \neq }$ auf den reellen Zahlen ist hingegen nicht transitiv: ${\displaystyle 3\neq 5}$ und ${\displaystyle 5\neq 3}$, aber ${\displaystyle 3\neq 3}$ gilt natürlich nicht.

Teilbarkeit der ganzen Zahlen

Die Teilbarkeitsrelation ${\displaystyle |}$ für ganze Zahlen ist transitiv, denn aus ${\displaystyle a|b}$ und ${\displaystyle b|c}$ folgt ${\displaystyle a|c}$. Sie ist darüber hinaus eine Quasiordnung. Bei der Einschränkung auf die Menge der natürlichen Zahlen erhält man eine Halbordnung.

Nicht transitiv ist zum Beispiel die Teilerfremdheit. So sind ${\displaystyle 12}$ und ${\displaystyle 5}$ teilerfremd, ebenso ${\displaystyle 5}$ und ${\displaystyle 9}$, jedoch haben ${\displaystyle 12}$ und ${\displaystyle 9}$ den gemeinsamen Teiler ${\displaystyle 3}$.

Teilmenge

Die Teilmengenbeziehung ${\displaystyle \subseteq }$ zwischen Mengen ist transitiv, denn aus ${\displaystyle A\subseteq B}$ und ${\displaystyle B\subseteq C}$ folgt ${\displaystyle A\subseteq C}$. Darüber hinaus ist ${\displaystyle \subseteq }$ eine Halbordnung.

Nicht transitiv ist zum Beispiel die Disjunktheit von Mengen. So sind die Mengen ${\displaystyle \lbrace 1,2\rbrace }$ und ${\displaystyle \lbrace 3\rbrace }$ disjunkt, ebenso ${\displaystyle \lbrace 3\rbrace }$ und ${\displaystyle \lbrace 1,4\rbrace }$, nicht aber ${\displaystyle \lbrace 1,2\rbrace }$ und ${\displaystyle \lbrace 1,4\rbrace }$ (da sie das Element 1 gemeinsam haben).

Parallele Geraden

In der Geometrie ist die Parallelität von Geraden transitiv: Sind sowohl die Geraden ${\displaystyle g_{1}}$ und ${\displaystyle g_{2}}$ parallel als auch die Geraden ${\displaystyle g_{2}}$ und ${\displaystyle g_{3}}$, dann sind auch ${\displaystyle g_{1}}$ und ${\displaystyle g_{3}}$ parallel. Darüber hinaus ist die Parallelität eine Äquivalenzrelation.

Implikation in der Logik

In d​er Logik g​ilt die Transitivität bezüglich d​er Implikation, w​obei dies i​n der Prädikatenlogik a​uch als Modus barbara bekannt ist:

Aus ${\displaystyle A\Rightarrow B}$ und ${\displaystyle B\Rightarrow C}$ folgt ${\displaystyle A\Rightarrow C}$ (vergleiche auch: Schnittregel).

Die Implikation definiert e​ine Quasiordnung a​uf den Formeln d​er jeweils betrachteten Logik.

Siehe auch

• Transitive Hülle
• Negative Transitivität

Weblinks

• Transitivity. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (englisch, online).