Transitivität (Mathematik)

Die Transitivität einer zweistelligen Relation R auf einer Menge ist gegeben, wenn aus x R y und y R z stets x R z folgt. Man nennt R dann transitiv.

Die Transitivität ist eine der Voraussetzungen für eine Äquivalenzrelation oder eine Ordnungsrelation.

Formale Definition

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

$\backslash forall\; x,\; y,\; z\; \backslash in\; M:\; xRy\; \backslash and\; yRz\; \backslash Rightarrow\; xRz$

Beispiele

Ordnung der reellen Zahlen

Die Kleiner-Relation auf den reellen Zahlen ist transitiv, denn aus

Ebenso sind die Relationen $>\backslash$, $\backslash le\backslash$ und $\backslash ge\; \backslash$ transitiv.

Gleichheit der reellen Zahlen

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

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

Teilbarkeit der ganzen Zahlen

Die Teilbarkeitsrelation | für ganze Zahlen ist transitiv, denn aus a | b und b | c folgt 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 12 und 5 teilerfremd, ebenso 5 und 9, jedoch haben 12 und 9 den gemeinsamen Teiler 3.

Teilmenge

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

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

Parallele Geraden

In der Geometrie ist die Parallelität von Geraden transitiv: Sind sowohl die Geraden $g\_1$ und $g\_2$ parallel als auch die Geraden $g\_2$ und $g\_3$, dann sind auch $g\_1$ und $g\_3$ parallel. Darüber hinaus ist die Parallelität eine Äquivalenzrelation.

Implikation in der Logik

In der Logik gilt die Transitivität bezüglich der Implikation, wobei dies in der Prädikatenlogik auch als Modus barbara bekannt ist:

Aus $A\; \backslash Rightarrow\; B$ und $B\; \backslash Rightarrow\; C$ folgt $A\; \backslash Rightarrow\; C$ (vergleiche auch: Schnittregel).

Die Implikation definiert eine Quasiordnung auf den Formeln der jeweils betrachteten Logik.

Darstellung als gerichteter Graph

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

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

Eigenschaften

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

  $a\; \backslash ,R\; \backslash ,b\_1\; \backslash ,R\; \backslash ,b\_2\; \backslash ,R\; \backslash ,\backslash dots\; \backslash ,R\; \backslash ,b\_n\; \backslash ,R\; \backslash ,c\; \backslash implies\; a\; \backslash ,R\; \backslash ,c$

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

  $R\; \backslash circ\; R\; \backslash subseteq\; R$

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

Siehe auch

• Äquivalenzrelation
• Halbordnung
• Quasiordnung
• transitive Hülle
• negative Transitivität
• Relation (Mathematik)