de.wikipedia.org

Transitive Relation – Wikipedia

Zwei transitive und eine nicht transitive Relation (rechts unten), als gerichtete Graphen dargestellt

Eine transitive Relation ist in der Mengenlehre eine zweistellige Relation {\displaystyle R} auf einer Menge, die die Eigenschaft hat, dass für drei Elemente {\displaystyle x}, {\displaystyle y}, {\displaystyle z} dieser Menge aus {\displaystyle xRy} und {\displaystyle yRz} stets {\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 {\displaystyle x}, {\displaystyle y} und {\displaystyle z} mit {\displaystyle x=y} und {\displaystyle y=z} gilt immer auch {\displaystyle x=z}, und aus {\displaystyle x<y} und {\displaystyle y<z} folgt {\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 {\displaystyle M} eine Menge und {\displaystyle R\subseteq M\times M} eine zweistellige Relation auf {\displaystyle M}, dann heißt {\displaystyle R} transitiv, wenn (unter Verwendung der Infixnotation) gilt:[1]

{\displaystyle \forall x,y,z\in M\colon xRy\land yRz\Rightarrow xRz.}

Jede beliebige Relation {\displaystyle R} auf einer Menge {\displaystyle M} kann als gerichteter Graph aufgefasst werden (Beispiel siehe oben). Die Knoten des Graphen sind dabei die Elemente von {\displaystyle M}. Vom Knoten {\displaystyle a} zum Knoten {\displaystyle b} wird genau dann eine gerichtete Kante (ein Pfeil {\displaystyle a\longrightarrow b}) gezogen, wenn {\displaystyle aRb} gilt.

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

Wichtiges Beispiel aus der Volkswirtschaftslehre ist das Nichtsättigungsaxiom.

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

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

Ebenso sind die Relationen {\displaystyle >\ }, {\displaystyle \leq \ } und {\displaystyle \geq \ } transitiv.

Die gewöhnliche Gleichheit {\displaystyle =\ } auf den reellen Zahlen ist transitiv, denn aus {\displaystyle x=y} und {\displaystyle y=z} folgt {\displaystyle x=z}. Sie ist darüber hinaus eine Äquivalenzrelation.

Die Ungleichheitsrelation {\displaystyle \neq } auf den reellen Zahlen ist hingegen nicht transitiv: {\displaystyle 3\neq 5} und {\displaystyle 5\neq 3}, aber {\displaystyle 3\neq 3} gilt natürlich nicht.

Die Teilt-Relation {\displaystyle |} für ganze Zahlen ist transitiv, denn aus {\displaystyle a|b} und {\displaystyle b|c} folgt {\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 in der Menge der natürlichen oder ganzen Zahlen. So sind {\displaystyle 12} und {\displaystyle 5} teilerfremd, ebenso {\displaystyle 5} und {\displaystyle 9}, jedoch haben {\displaystyle 12} und {\displaystyle 9} den gemeinsamen Teiler {\displaystyle 3}.

Die Teilmengenbeziehung {\displaystyle \subseteq } zwischen Mengen ist transitiv, denn aus {\displaystyle A\subseteq B} und {\displaystyle B\subseteq C} folgt {\displaystyle A\subseteq C}. Darüber hinaus ist {\displaystyle \subseteq } eine Halbordnung.

Nicht transitiv ist zum Beispiel die Disjunktheit von Mengen in jedem Mengensystem {\displaystyle M}, das zwei verschiedene disjunkte Mengen enthält. So sind in der Potenzmenge {\displaystyle M={\mathcal {P}}(N)} die Mengen {\displaystyle \lbrace 1,2\rbrace } und {\displaystyle \lbrace 3\rbrace } disjunkt, ebenso {\displaystyle \lbrace 3\rbrace } und {\displaystyle \lbrace 1,4\rbrace }, nicht aber {\displaystyle \lbrace 1,2\rbrace } und {\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 {\displaystyle g_{1}} und {\displaystyle g_{2}} parallel als auch die Geraden {\displaystyle g_{2}} und {\displaystyle g_{3}}, dann sind auch {\displaystyle g_{1}} und {\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 {\displaystyle A\Rightarrow B} und {\displaystyle B\Rightarrow C} folgt {\displaystyle A\Rightarrow C} (vergleiche auch: Schnittregel).

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

  1. ↑ Seymor Lipschutz, Marc Lipson: Schaum's Outline of Discrete Mathematics. McGraw Hill Professional, 1997, ISBN 978-0-07-136841-4, S. 33 (google.de [abgerufen am 18. Mai 2023]).
  2. ↑ a b Seymor Lipschutz, Marc Lipson: Schaum's Outline of Discrete Mathematics. McGraw Hill Professional, 1997, ISBN 978-0-07-136841-4, S. 34 (google.de [abgerufen am 18. Mai 2023]).
  3. ↑ Dov M. Gabbay, John Woods: The Rise of Modern Logic: from Leibniz to Frege. Elsevier, 2004, ISBN 978-0-08-053287-5, S. 509 (google.de [abgerufen am 18. Mai 2023]).
  4. ↑ Seymor Lipschutz, Marc Lipson: Schaum's Outline of Discrete Mathematics. McGraw Hill Professional, 1997, ISBN 978-0-07-136841-4, S. 35 (google.de [abgerufen am 18. Mai 2023]).