Transitive Relation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Zwei transitive und eine nicht transitive Relation (rechts unten), als gerichtete Graphen dargestellt

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 x R y und y R z stets x R z folgt. Eine nicht transitive Relation heißt intransitiv. Die Transitivität ist eine der Voraussetzungen für eine Äquivalenzrelation oder eine Ordnungsrelation.

Formale Definition[Bearbeiten]

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 \and yRz \Rightarrow xRz .

Darstellung als gerichteter Graph[Bearbeiten]

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 a R b 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).

Eigenschaften[Bearbeiten]

  • 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 \le konverse Relation ist \ge, 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[Bearbeiten]

Ordnung der reellen Zahlen[Bearbeiten]

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 >\ , \le\ und \ge \ transitiv.

Gleichheit der reellen Zahlen[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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.

Siehe auch[Bearbeiten]