Hauptmenü öffnen
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.
Zwei transitive und eine nicht transitive Relation (rechts unten), als gerichtete Graphen dargestellt

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.

Inhaltsverzeichnis

Formale DefinitionBearbeiten

Ist   eine Menge und   eine zweistellige Relation auf  , dann heißt   transitiv, wenn (unter Verwendung der Infixnotation) gilt:

 

Darstellung als gerichteter GraphBearbeiten

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).

EigenschaftenBearbeiten

  • 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  .

BeispieleBearbeiten

Ordnung der reellen ZahlenBearbeiten

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

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 ZahlenBearbeiten

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 ZahlenBearbeiten

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  .

TeilmengeBearbeiten

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 GeradenBearbeiten

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 LogikBearbeiten

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.

Siehe auchBearbeiten