Transitive Relation - LinkFang.de





Transitive Relation


Eine transitive Relation ist in der Mathematik eine zweistellige Relation [math]R[/math] auf einer Menge, die die Eigenschaft hat, dass für drei Elemente [math]x[/math], [math]y[/math], [math]z[/math] dieser Menge aus [math]x R y[/math] und [math]y R z[/math] stets [math]x R z[/math] 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 [math]M[/math] eine Menge und [math]R \subseteq M \times M[/math] eine zweistellige Relation auf [math]M[/math], dann heißt [math]R[/math] transitiv, wenn (unter Verwendung der Infixnotation) gilt:

[math]\forall x, y, z \in M: xRy \and yRz \Rightarrow xRz .[/math]

Darstellung als gerichteter Graph

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

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

Eigenschaften

  • Die Transitivität einer Relation [math]R[/math] erlaubt auch Schlüsse über mehrere Schritte hinweg (wie man leicht durch vollständige Induktion zeigt):
    [math]a \,R \,b_1 \,R \,b_2 \,R \,\dots \,R \,b_n \,R \,c \implies a \,R \,c[/math]
  • Mit Hilfe der Verkettung [math]\circ[/math] von Relationen lässt sich die Transitivität auch durch die folgende Bedingung charakterisieren:
    [math]R \circ R \subseteq R[/math]
  • Ist die Relation [math]R[/math] transitiv, dann gilt dies auch für die konverse Relation [math]R^{-1}[/math]. Beispiele: die zu [math]\le[/math] konverse Relation ist [math]\ge[/math], die zu [math]\lt\ [/math] konverse ist [math]\gt\ [/math].
  • Sind die Relationen [math]R[/math] und [math]S[/math] transitiv, dann gilt dies auch für ihre Schnittmenge [math]R \cap S[/math]. Diese Aussage lässt sich von zwei Relationen auf den Durchschnitt [math]\cap_{i\in I} R_i [/math] einer beliebigen Familie von transitiven Relationen verallgemeinern.
  • Zu jeder beliebigen Relation [math]R[/math] gibt es eine kleinste transitive Relation [math]S[/math], die [math]R[/math] enthält, die sogenannte transitive Hülle von [math]R[/math].
    Beispiel: [math]R[/math] sei die Vorgängerrelation auf der Menge der natürlichen Zahlen, es gelte also [math]a \,R \,b : \Longleftrightarrow a = b - 1[/math]. Die Relation [math]R[/math] selbst ist nicht transitiv. Als transitive Hülle von [math]R[/math] ergibt sich die Kleiner-Relation [math]\lt\ [/math].

Beispiele

Ordnung der reellen Zahlen

Die Kleiner-Relation [math]\lt\ [/math] auf den reellen Zahlen ist transitiv, denn aus [math]x\lty[/math] und [math]y\ltz[/math] folgt [math]x\ltz[/math]. Sie ist darüber hinaus eine strenge Totalordnung.

Ebenso sind die Relationen [math]\gt\ [/math], [math]\le\ [/math] und [math]\ge \ [/math] transitiv.

Gleichheit der reellen Zahlen

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

Die Ungleichheitsrelation [math]\neq [/math] auf den reellen Zahlen ist hingegen nicht transitiv: [math]3\neq 5[/math] und [math]5\neq 3[/math], aber [math]3\neq 3[/math] gilt natürlich nicht.

Teilbarkeit der ganzen Zahlen

Die Teilbarkeitsrelation [math]|[/math] für ganze Zahlen ist transitiv, denn aus [math]a | b[/math] und [math]b | c[/math] folgt [math]a | c[/math]. 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 [math]12[/math] und [math]5[/math] teilerfremd, ebenso [math]5[/math] und [math]9[/math], jedoch haben [math]12[/math] und [math]9[/math] den gemeinsamen Teiler [math]3[/math].

Teilmenge

Die Teilmengenbeziehung [math]\subseteq[/math] zwischen Mengen ist transitiv, denn aus [math]A\subseteq B[/math] und [math]B\subseteq C[/math] folgt [math]A\subseteq C[/math]. Darüber hinaus ist [math]\subseteq[/math] eine Halbordnung.

Nicht transitiv ist zum Beispiel die Disjunktheit von Mengen. So sind die Mengen [math]\lbrace 1, 2 \rbrace[/math] und [math]\lbrace 3\rbrace[/math] disjunkt, ebenso [math]\lbrace 3\rbrace[/math] und [math]\lbrace 1, 4\rbrace[/math], nicht aber [math]\lbrace 1, 2 \rbrace[/math] und [math]\lbrace 1, 4\rbrace[/math] (da sie das Element 1 gemeinsam haben).

Parallele Geraden

In der Geometrie ist die Parallelität von Geraden transitiv: Sind sowohl die Geraden [math]g_1[/math] und [math]g_2[/math] parallel als auch die Geraden [math]g_2[/math] und [math]g_3[/math], dann sind auch [math]g_1[/math] und [math]g_3[/math] 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 [math]A \Rightarrow B[/math] und [math]B \Rightarrow C[/math] folgt [math]A \Rightarrow C[/math] (vergleiche auch: Schnittregel).

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

Siehe auch


Kategorien: Mathematischer Grundbegriff | Ordnungstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Transitive Relation (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.