Transitivität (Mathematik)

Transitivität (Mathematik)
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.

Inhaltsverzeichnis

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

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 >\ , \le\ und \ge \ 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 \neq auf den reellen Zahlen ist hingegen nicht transitiv: 3\neq 5 und 5\neq 3, aber 3\neq 3 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 \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).

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

Transitive Mengen

In der Mengenlehre heißt eine Menge x transitiv, wenn die \in-Relation auf x es ist, falls also z\in y\in x\Rightarrow z\in x gilt. Beispiele für transitive Mengen sind die Ordinalzahlen.

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

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

Siehe auch


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Transitivität — Transitivität, adj. transitiv (von lateinisch transitus ‚Übergang‘) steht für: Transitivität (Grammatik), in der Grammatik Bezeichnung für Verben, die ein Akkusativobjekt binden Transitivität (Mathematik), in der Mathematik die zum… …   Deutsch Wikipedia

  • Transitivität — Tran|si|ti|vi|tät 〈[ vi ] f.; ; unz.〉 das Transitivsein, transitive Beschaffenheit (von Verben) * * * Transitivität,   Logik und Mathematik: Eigenschaft einer zweistelligen Relation R auf einer Menge M, die transitiv ist, d. h., für alle a …   Universal-Lexikon

  • Faktormenge (Mathematik) — In der Mathematik möchte man in vielen Zusammenhängen Objekte, die sich in gewissen Aspekten ähneln, als gleichwertig ansehen. Eine Formalisierung der Mindestanforderungen an einen solchen Gleichwertigkeitsbegriff ist der Begriff der… …   Deutsch Wikipedia

  • Repräsentant (Mathematik) — In der Mathematik möchte man in vielen Zusammenhängen Objekte, die sich in gewissen Aspekten ähneln, als gleichwertig ansehen. Eine Formalisierung der Mindestanforderungen an einen solchen Gleichwertigkeitsbegriff ist der Begriff der… …   Deutsch Wikipedia

  • Vertreter (Mathematik) — In der Mathematik möchte man in vielen Zusammenhängen Objekte, die sich in gewissen Aspekten ähneln, als gleichwertig ansehen. Eine Formalisierung der Mindestanforderungen an einen solchen Gleichwertigkeitsbegriff ist der Begriff der… …   Deutsch Wikipedia

  • Intransitivität (Mathematik) — Eine Relation R in einer Menge M heißt intransitiv, wenn es mindestens drei Zahlen gibt, für die aRb und bRc gelten, aber nicht aRc. Eine Relation ist also intransitiv, wenn sie nicht transitiv ist. Ursprünglich wurden intransitive Relationen vom …   Deutsch Wikipedia

  • Topologische Transitivität — Von topologischer Transitivität spricht man in der Mathematik, wenn ein metrischer Raum unter einer Abbildung durcheinandergewirbelt wird. In der Literatur wird topologische Transitivität daher auch oft als Mischen bezeichnet: „If U is any open… …   Deutsch Wikipedia

  • Negative Transitivität — Die negative Transitivität einer zweistelligen Relation R auf einer Menge ist gegeben, wenn gilt: Strenge schwache Ordnungen erfüllen die negative Transitivität. Beispiel: Wenn Milch nicht weniger kostet als Brot, und Brot nicht weniger als… …   Deutsch Wikipedia

  • Relation (Mathematik) — Eine Relation ist allgemein eine Beziehung, die zwischen Dingen bestehen kann. Relationen im Sinne der Mathematik sind ausschließlich diejenigen Beziehungen, bei denen stets klar ist, ob sie bestehen oder nicht. Zwei Gegenstände können also nicht …   Deutsch Wikipedia

  • Affinität (Mathematik) — In der Geometrie bezeichnet man als Affinität eine strukturerhaltende Abbildung eines affinen Raumes (häufig der Zeichenebene oder des dreidimensionalen Anschauungsraums) auf sich selbst. Der Begriff umfasst und verallgemeinert den Begriff der… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”