Transitive Relation
# Transitive Relation

Eine transitive Relation ist in der Mathematik eine zweistellige Relation $R$ auf einer Menge, die die Eigenschaft hat, dass für drei Elemente $x$, $y$, $z$ dieser Menge aus $xRy$ und $yRz$ stets $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$, $y$ und $z$ mit $x=y$ und $y=z$ gilt immer auch $x=z$, und aus $x<y$ und $y<z$ folgt $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.

## Formale Definition

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

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

## 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\longrightarrow b$) gezogen, wenn $aRb$ gilt.

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

## Eigenschaften

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

    $a\,R\,b_{1}\,R\,b_{2}\,R\,\dots \,R\,b_{n}\,R\,c\implies a\,R\,c$
* Mit Hilfe der Verkettung $\circ$ von Relationen lässt sich die Transitivität auch durch die folgende Bedingung charakterisieren:

    $R\circ R\subseteq R$
* Ist die Relation $R$ transitiv, dann gilt dies auch für die konverse Relation $R^{-1}$. Beispiele: die zu $\leq$ konverse Relation ist $\geq$, die zu $<\$ konverse ist $>\$.
* Sind die Relationen $R$ und $S$ transitiv, dann gilt dies auch für ihre Schnittmenge $R\cap S$. Diese Aussage lässt sich von zwei Relationen auf den Durchschnitt $\cap _{i\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\,R\,b:\Longleftrightarrow a=b-1$. Die Relation $R$ selbst ist nicht transitiv. Als transitive Hülle von $R$ ergibt sich die Kleiner-Relation $<\$.

## Beispiele

Wichtiges Beispiel aus der Volkswirtschaftslehre ist das Nichtsättigungsaxiom.

### Ordnung der reellen Zahlen

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

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

### Gleichheit der reellen Zahlen

Die gewöhnliche Gleichheit $=\$ 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 $\neq$ auf den reellen Zahlen ist hingegen nicht transitiv: $3\neq 5$ und $5\neq 3$, aber $3\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 $\subseteq$ zwischen Mengen ist transitiv, denn aus $A\subseteq B$ und $B\subseteq C$ folgt $A\subseteq C$. Darüber hinaus ist $\subseteq$ eine Halbordnung.

Nicht transitiv ist zum Beispiel die Disjunktheit von Mengen. So sind die Mengen $\lbrace 1,2\rbrace$ und $\lbrace 3\rbrace$ disjunkt, ebenso $\lbrace 3\rbrace$ und $\lbrace 1,4\rbrace$, nicht aber $\lbrace 1,2\rbrace$ und $\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 $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\Rightarrow B$ und $B\Rightarrow C$ folgt $A\Rightarrow C$ (vergleiche auch: Schnittregel).

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

