Transitive Relation

Transitive Graphen

Eine transitive Matrix

Die Transitivität einer binären Relation R ist gegeben, wenn aus xRy und yRz stets xRz folgt. Die Transitivität ist eine der Voraussetzungen, damit R eine Äquivalenzrelation oder eine Ordnungsrelation ist.

Beispiele

Ordnung der reellen Zahlen

Das Kleiner-Zeichen < auf den reellen Zahlen ist transitiv und definiert darüber hinaus eine strenge Halbordnung:

Aus x<y und y<z folgt immer x<z.

Ebenso sind die Relationen $x>y\!$, $x\leq y\!$ und $x\geq y\!$ transitiv.

Das Ungleichheitszeichen $\neq$ auf den reellen Zahlen ist hingegen nicht transitiv:

$3\neq 5$ und $5\neq 3$, aber $3\neq 3$ gilt natürlich nicht.

Identität der reellen Zahlen

Die gewöhnliche Identität = auf den reellen Zahlen ist transitiv und eine Äquivalenzrelation:

Aus x=y und y=z folgt immer x=z.

Teilbarkeit der ganzen Zahlen

Die Teilbarkeit der ganzen Zahlen ist transitiv und definiert eine partielle Halbordnung:

Aus a | b und b | c folgt a | c.

Eine nicht transitive Relation 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 Teilmengenrelation von Mengen ist transitiv und definiert eine partielle Halbordnung:

Aus $A\subseteq B$ und $B\subseteq C$ folgt $A\subseteq C$.

Eine nicht transitive Relation ist zum Beispiel die disjunkt-Relation. So sind die Mengen $A=\lbrace 1,2\rbrace$ und $B=\lbrace 3\rbrace$ disjunkt, ebenso sind $B$ und $C=\lbrace 1,4\rbrace$ disjunkt, nicht aber $A$ und $C$, denn $A\cap C=\lbrace 1\rbrace \neq \emptyset$.

Geometrisches Beispiel: parallele Geraden

In der Geometrie ist die Parallelität von Geraden ein Beispiel einer transitiven Relation: Sind sowohl die Geraden $g_{1}$ und $g_{2}$ parallel als auch die Geraden $g_{2}$ und $g_{3}$, so sind auch die Geraden $g_{1}$ und $g_{3}$ parallel.

Die Relation "ist parallel zu" ist eine Äquivalenzrelation.

Implikation der Prädikatenlogik

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

Aus $(a\Rightarrow b)$ und $(b\Rightarrow c)$ folgt $(a\Rightarrow c)$. (vergleiche auch: Schnittregel)

Die Implikation definiert eine Quasiordnung auf den logischen Aussagen.

Verallgemeinerungen

Die Transitivtät erlaubt auch Schlüsse über mehrere Schritte hinweg. So folgt aus $x_{1}Rx_{2}\!$, $x_{2}Rx_{3}\!$ und $x_{3}Rx_{4}\!$ zunächst wegen der Transitivität $x_{1}Rx_{3}\!$ und durch nochmalige Anwendung der Transitivität auch $x_{1}Rx_{4}\!$.

Allgemein lässt sich durch vollständige Induktion zeigen, dass sich die Transitivität auf eine beliebig große, aber endliche Anzahl von Schritten anwenden lässt: Gilt für $i=1,\dots ,n-1$ jeweils die Relation $x_{i}Rx_{i+1}\!$, so folgt aus der Transitivität auch $x_{1}Rx_{n}\!$.

Siehe auch

Relation (Mathematik)#Klassen von Relationen