Transitive Relation

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

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

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

Beispiele

Ordnung der reellen Zahlen

Aus a > b und b > c folgt a > c.

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

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.

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

Trenner
Basierend auf Artikeln in: externer Link Wikipedia.de
 
Seitenende
Seite zurück
©  biancahoegel.de;
Datum der letzten Änderung: Jena, den: 21.01. 2019