Transitivität (Mathematik)

aus Wikipedia, der freien Enzyklopädie

Zwei transitive und eine nicht transitive Relation, als gerichtete Graphen dargestellt

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.

[Bearbeiten] Formale Definition

Ist $M$ eine Menge und $R \subseteq M \times M$ eine zweistellige Relation auf $M$ , dann heißt $R$ transitiv, wenn (unter Verwendung der Infixnotation) gilt:

$\forall x, y, z \in M: xRy \and yRz \Rightarrow xRz$

[Bearbeiten] Beispiele

[Bearbeiten] 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 $>\$ , $\le\$ und $\ge \$ transitiv.

[Bearbeiten] 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 $\neq$ auf den reellen Zahlen ist hingegen nicht transitiv: $3\neq 5$ und $5\neq 3$ , aber $3\neq 3$ gilt natürlich nicht.

[Bearbeiten] 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.

[Bearbeiten] Teilmenge

Die Teilmengenbeziehung $\subseteq$ zwischen Mengen ist transitiv, denn aus $A\subseteq B$ und $B\subseteq C$ folgt $A\subseteq C$ . Darüber hinaus ist $\subseteq$ 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).

[Bearbeiten] Parallele Geraden

In der Geometrie ist die Parallelität von Geraden transitiv: Sind sowohl die Geraden $g 1$ und $g 2$ parallel als auch die Geraden $g 2$ und $g 3$ , dann sind auch $g 1$ und $g 3$ parallel. Darüber hinaus ist die Parallelität eine Äquivalenzrelation.

[Bearbeiten] 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 $A \Rightarrow B$ und $B \Rightarrow C$ folgt $A \Rightarrow C$ (vergleiche auch: Schnittregel).

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

[Bearbeiten] 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 $a \longrightarrow b$ ) gezogen, wenn a R b gilt.

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

[Bearbeiten] Eigenschaften

Die Transitivität einer Relation R erlaubt auch Schlüsse über mehrere Schritte hinweg (wie man leicht durch vollständige Induktion zeigt):

$a \,R \,b_1 \,R \,b_2 \,R \,\dots \,R \,b_n \,R \,c \implies a \,R \,c$
Mit Hilfe der Verkettung $\circ$ von Relationen lässt sich die Transitivität auch durch die folgende Bedingung charakterisieren:

$R \circ R \subseteq R$
Ist die Relation $R$ transitiv, dann gilt dies auch für die konverse Relation $R - 1$ . Beispiele: die zu $\le$ konverse Relation ist $\ge$ , die zu $<\$ konverse ist $>\$ .
Sind die Relationen $R$ und $S$ transitiv, dann gilt dies auch für ihre Schnittmenge $R \cap S$ . Diese Aussage lässt sich von zwei Relationen auf den Durchschnitt $\cap_{i\in I} R_i$ 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 $a \,R \,b : \Longleftrightarrow a = b - 1$ . Die Relation $R$ selbst ist nicht transitiv. Als transitive Hülle von $R$ ergibt sich die Kleiner-Relation $<\$ .