Eine transitive Relation ist in der Mathematik eine zweistellige Relation auf einer Menge, die die Eigenschaft hat, dass für drei Elemente , , dieser Menge aus und stets folgt. Beispiele für transitive Relationen sind die Gleich- und die Kleiner-Relationen auf den reellen Zahlen, denn für drei reelle Zahlen , und mit und gilt immer auch , und aus und folgt .
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 Bearbeiten
Ist eine Menge und eine zweistellige Relation auf , dann heißt transitiv, wenn (unter Verwendung der Infixnotation) gilt:
Darstellung als gerichteter Graph Bearbeiten
Jede beliebige Relation auf einer Menge kann als gerichteter Graph aufgefasst werden (Beispiel siehe oben). Die Knoten des Graphen sind dabei die Elemente von . Vom Knoten zum Knoten wird genau dann eine gerichtete Kante (ein Pfeil ) gezogen, wenn gilt.
Die Transitivität von lässt sich im Graphen nun so charakterisieren: Wann immer zwei Pfeile aufeinanderfolgen (), gibt es auch einen Pfeil, der Anfangs- und Endknoten direkt verbindet () (so auch im Hasse-Diagramm).
Eigenschaften Bearbeiten
- Die Transitivität einer Relation erlaubt auch Schlüsse über mehrere Schritte hinweg (wie man leicht durch vollständige Induktion zeigt):
- Mit Hilfe der Verkettung von Relationen lässt sich die Transitivität auch durch die folgende Bedingung charakterisieren:
- Ist die Relation transitiv, dann gilt dies auch für die konverse Relation . Beispiele: die zu konverse Relation ist , die zu konverse ist .
- Sind die Relationen und transitiv, dann gilt dies auch für ihre Schnittmenge . Diese Aussage lässt sich von zwei Relationen auf den Durchschnitt einer beliebigen Familie von transitiven Relationen verallgemeinern.
- Zu jeder beliebigen Relation gibt es eine kleinste transitive Relation , die enthält, die sogenannte transitive Hülle von .
Beispiel: sei die Vorgängerrelation auf der Menge der natürlichen Zahlen, es gelte also . Die Relation selbst ist nicht transitiv. Als transitive Hülle von ergibt sich die Kleiner-Relation .
Beispiele Bearbeiten
Wichtiges Beispiel aus der Volkswirtschaftslehre ist das Nichtsättigungsaxiom.
Ordnung der reellen Zahlen Bearbeiten
Die Kleiner-Relation auf den reellen Zahlen ist transitiv, denn aus und folgt . Sie ist darüber hinaus eine strenge Totalordnung.
Ebenso sind die Relationen , und transitiv.
Gleichheit der reellen Zahlen Bearbeiten
Die gewöhnliche Gleichheit auf den reellen Zahlen ist transitiv, denn aus und folgt . Sie ist darüber hinaus eine Äquivalenzrelation.
Die Ungleichheitsrelation auf den reellen Zahlen ist hingegen nicht transitiv: und , aber gilt natürlich nicht.
Teilbarkeit der ganzen Zahlen Bearbeiten
Die Teilbarkeitsrelation für ganze Zahlen ist transitiv, denn aus und folgt . 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 und teilerfremd, ebenso und , jedoch haben und den gemeinsamen Teiler .
Teilmenge Bearbeiten
Die Teilmengenbeziehung zwischen Mengen ist transitiv, denn aus und folgt . Darüber hinaus ist eine Halbordnung.
Nicht transitiv ist zum Beispiel die Disjunktheit von Mengen. So sind die Mengen und disjunkt, ebenso und , nicht aber und (da sie das Element 1 gemeinsam haben).
Parallele Geraden Bearbeiten
In der Geometrie ist die Parallelität von Geraden transitiv: Sind sowohl die Geraden und parallel als auch die Geraden und , dann sind auch und 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 und folgt (vergleiche auch: Schnittregel).
Die Implikation definiert eine Quasiordnung auf den Formeln der jeweils betrachteten Logik.
Weblinks Bearbeiten
- Transitivity. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org).
Einzelnachweise Bearbeiten
- 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]).
- ↑ 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]).
- 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]).
- 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]).