- Transitivitätssatz der Implikation
-
Die Transitivität einer zweistelligen Relation R auf einer Menge ist gegeben, wenn aus x R y und y R z stets x R z folgt. Man nennt R dann transitiv.
Die Transitivität ist eine der Voraussetzungen für eine Äquivalenzrelation oder eine Ordnungsrelation.
Inhaltsverzeichnis
Formale Definition
Ist M eine Menge und
eine zweistellige Relation auf M, dann heißt R transitiv, wenn (unter Verwendung der Infixnotation) gilt:
Beispiele
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
,
und
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
auf den reellen Zahlen ist hingegen nicht transitiv:
und
, aber
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
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 {1,2} und {3} disjunkt, ebenso {3} und {1,4}, nicht aber {1,2} und {1,4} (da sie das Element 1 gemeinsam haben).
Parallele Geraden
In der Geometrie ist die Parallelität von Geraden transitiv: Sind sowohl die Geraden g1 und g2 parallel als auch die Geraden g2 und g3, dann sind auch g1 und g3 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
und
folgt
(vergleiche auch: Schnittregel).
Die Implikation definiert eine Quasiordnung auf den Formeln der jeweils betrachteten Logik.
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
) gezogen, wenn a R b gilt.
Die Transitivität von R lässt sich im Graphen nun so charakterisieren: Wann immer zwei Pfeile aufeinanderfolgen (
), gibt es auch einen Pfeil, der Anfangs- und Endknoten direkt verbindet (
).
Eigenschaften
- Die Transitivität einer Relation R 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 R transitiv, dann gilt dies auch für die konverse Relation R − 1. Beispiele: die zu
konverse Relation ist
, die zu
konverse ist
.
- Sind die Relationen R und S 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 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. Die Relation R selbst ist nicht transitiv. Als transitive Hülle von R ergibt sich die Kleiner-Relation
.
Siehe auch
Wikimedia Foundation.