Eine transitive Relation ist in der Mathematik eine zweistellige Relation R {\displaystyle R} auf einer Menge, die die Eigenschaft hat, dass für drei Elemente x {\displaystyle x} , y {\displaystyle y} , z {\displaystyle z} dieser Menge aus x R y {\displaystyle xRy} und y R z {\displaystyle yRz} stets x R z {\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 x {\displaystyle x} , y {\displaystyle y} und z {\displaystyle z} mit x = y {\displaystyle x=y} und y = z {\displaystyle y=z} gilt immer auch x = z {\displaystyle x=z} , und aus x < y {\displaystyle x<y} und y < z {\displaystyle y<z} folgt x < z {\displaystyle x<z} .
Eine nicht transitive Relation heißt intransitiv (nicht zu verwechseln mit negativer Transitivität). Die Transitivität ist eine der Voraussetzungen für eine Äquivalenzrelation oder eine Ordnungsrelation.
Ist M {\displaystyle M} Infixnotation) gilt:
∀ x , y , z ∈ M : x R y ∧ y R z ⇒ x R z . {\displaystyle \forall x,y,z\in M:xRy\land yRz\Rightarrow xRz.} eine Menge und R ⊆ M × M {\displaystyle R\subseteq M\times M} eine zweistellige Relation auf M {\displaystyle M} , dann heißt R {\displaystyle R} transitiv, wenn (unter Verwendung derJede beliebige Relation R {\displaystyle R} gerichteter Graph aufgefasst werden (Beispiel siehe oben). Die Knoten des Graphen sind dabei die Elemente von M {\displaystyle M} . Vom Knoten a {\displaystyle a} zum Knoten b {\displaystyle b} wird genau dann eine gerichtete Kante (ein Pfeil a ⟶ b {\displaystyle a\longrightarrow b} ) gezogen, wenn a R b {\displaystyle aRb} gilt.
auf einer Menge M {\displaystyle M} kann alsDie Transitivität von R {\displaystyle R} Hasse-Diagramm).
lässt sich im Graphen nun so charakterisieren: Wann immer zwei Pfeile aufeinanderfolgen ( a ⟶ b ⟶ c {\displaystyle a\longrightarrow b\longrightarrow c} ), gibt es auch einen Pfeil, der Anfangs- und Endknoten direkt verbindet ( a ⟶ c {\displaystyle a\longrightarrow c} ) (so auch imWichtiges Beispiel aus der Volkswirtschaftslehre ist das Nichtsättigungsaxiom.
Die Kleiner-Relation < {\displaystyle <\ } reellen Zahlen ist transitiv, denn aus x < y {\displaystyle x<y} und y < z {\displaystyle y<z} folgt x < z {\displaystyle x<z} . Sie ist darüber hinaus eine strenge Totalordnung.
auf denEbenso sind die Relationen > {\displaystyle >\ }
, ≤ {\displaystyle \leq \ } und ≥ {\displaystyle \geq \ } transitiv.Die gewöhnliche Gleichheit = {\displaystyle =\ } Äquivalenzrelation.
auf den reellen Zahlen ist transitiv, denn aus x = y {\displaystyle x=y} und y = z {\displaystyle y=z} folgt x = z {\displaystyle x=z} . Sie ist darüber hinaus eineDie Ungleichheitsrelation ≠ {\displaystyle \neq }
auf den reellen Zahlen ist hingegen nicht transitiv: 3 ≠ 5 {\displaystyle 3\neq 5} und 5 ≠ 3 {\displaystyle 5\neq 3} , aber 3 ≠ 3 {\displaystyle 3\neq 3} gilt natürlich nicht.Die Teilbarkeitsrelation | {\displaystyle |} für ganze Zahlen ist transitiv, denn aus a | b {\displaystyle a|b} und b | c {\displaystyle b|c} folgt a | c {\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 12 {\displaystyle 12} und 5 {\displaystyle 5} teilerfremd, ebenso 5 {\displaystyle 5} und 9 {\displaystyle 9} , jedoch haben 12 {\displaystyle 12} und 9 {\displaystyle 9} den gemeinsamen Teiler 3 {\displaystyle 3} .
Die Teilmengenbeziehung ⊆ {\displaystyle \subseteq } zwischen Mengen ist transitiv, denn aus A ⊆ B {\displaystyle A\subseteq B} und B ⊆ C {\displaystyle B\subseteq C} folgt A ⊆ C {\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 { 1 , 2 } {\displaystyle \lbrace 1,2\rbrace } und { 3 } {\displaystyle \lbrace 3\rbrace } disjunkt, ebenso { 3 } {\displaystyle \lbrace 3\rbrace } und { 1 , 4 } {\displaystyle \lbrace 1,4\rbrace } , nicht aber { 1 , 2 } {\displaystyle \lbrace 1,2\rbrace } und { 1 , 4 } {\displaystyle \lbrace 1,4\rbrace } (da sie das Element 1 gemeinsam haben).
In der Geometrie ist die Parallelität von Geraden transitiv: Sind sowohl die Geraden g 1 {\displaystyle g_{1}} und g 2 {\displaystyle g_{2}} parallel als auch die Geraden g 2 {\displaystyle g_{2}} und g 3 {\displaystyle g_{3}} , dann sind auch g 1 {\displaystyle g_{1}} und g 3 {\displaystyle g_{3}} parallel. Darüber hinaus ist die Parallelität eine Äquivalenzrelation.
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 ⇒ B {\displaystyle A\Rightarrow B} Schnittregel).
und B ⇒ C {\displaystyle B\Rightarrow C} folgt A ⇒ C {\displaystyle A\Rightarrow C} (vergleiche auch:Die Implikation definiert eine Quasiordnung auf den Formeln der jeweils betrachteten Logik.