imported>Christian1985: HC: Entferne Kategorie:Mathematischer Grundbegriff

2025-12-23T15:48:36Z

HC: Entferne Kategorie:Mathematischer Grundbegriff

Neue Seite

[[Datei:Transitivität Graph.png|mini|Zwei transitive und eine nicht transitive Relation (rechts unten), als [[Gerichteter Graph|gerichtete Graphen]] dargestellt]]

Eine '''transitive Relation''' ist in der [[Mengenlehre]] eine zweistellige [[Relation (Mathematik)|Relation]] <math>R</math> auf einer [[Menge (Mathematik)|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. Beispiele für transitive Relationen sind die Gleich- und die Kleiner-Relationen auf den [[Reelle Zahl|reellen Zahlen]], denn für drei reelle Zahlen <math>x</math>, <math>y</math> und <math>z</math> mit <math>x = y</math> und <math>y = z</math> gilt immer auch <math>x = z</math>, und aus <math>x < y</math> und <math>y < z</math> folgt <math>x < z</math>.

Eine nicht transitive Relation heißt [[Intransitive Relation|intransitiv]] (nicht zu verwechseln mit [[Negative Transitivität|negativer Transitivität]]). 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:<ref>{{Literatur |Autor=Seymor Lipschutz, Marc Lipson |Titel=Schaum's Outline of Discrete Mathematics |Verlag=McGraw Hill Professional |Datum=1997-06-22 |ISBN=978-0-07-136841-4 |Seiten=33 |Online=https://books.google.de/books?id=6A5g3RiYiBUC&pg=PA33&dq=Transitive+Relation&hl=de&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwjE6fru2_7-AhXFhP0HHZqRA3gQ6AF6BAgBEAI#v=onepage&q=Transitive%20Relation&f=false |Abruf=2023-05-18}}</ref>
:<math>\forall x, y, z \in M\colon xRy \land 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 {{nowrap|(<math>a \longrightarrow b \longrightarrow c</math>),}} gibt es auch einen Pfeil, der Anfangs- und Endknoten direkt verbindet {{nowrap|(<math>a \longrightarrow c</math>)}}.

== 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):<ref name=":0">{{Literatur |Autor=Seymor Lipschutz, Marc Lipson |Titel=Schaum's Outline of Discrete Mathematics |Verlag=McGraw Hill Professional |Datum=1997-06-22 |ISBN=978-0-07-136841-4 |Seiten=34 |Online=https://books.google.de/books?id=6A5g3RiYiBUC&pg=PA33&dq=Transitive+Relation&hl=de&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwjE6fru2_7-AhXFhP0HHZqRA3gQ6AF6BAgBEAI#v=onepage&q=Transitive%20Relation&f=false |Abruf=2023-05-18}}</ref>
*:<math>a \,R \,b_1 \,R \,b_2 \,R \,\dots \,R \,b_n \,R \,c \implies a \,R \,c</math>
* Mit Hilfe der [[Komposition (Mathematik)#Komposition von Relationen|Verkettung]] <math>\circ</math> von Relationen lässt sich die Transitivität auch durch die folgende Bedingung charakterisieren:<ref name=":0" />
*:<math>R \circ R \subseteq R</math>
* Ist die Relation <math>R</math> transitiv, dann gilt dies auch für die [[Umkehrrelation|konverse Relation]] <math>R^{-1}</math>.<ref>{{Literatur |Autor=Dov M. Gabbay, John Woods |Titel=The Rise of Modern Logic: from Leibniz to Frege |Verlag=Elsevier |Datum=2004-03-08 |ISBN=978-0-08-053287-5 |Seiten=509 |Online=https://books.google.de/books?id=74-g3vSAbnoC&pg=PA509&dq=convers+relation+transitive&hl=de&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwi9xb_I4_7-AhWrgf0HHSIECpcQ6AF6BAgcEAI#v=onepage&q=convers%20relation%20transitive&f=false |Abruf=2023-05-18}}</ref> Beispiele: die zu <math>\le</math> konverse Relation ist <math>\ge</math>, die zu <math><\ </math> konverse ist <math>>\ </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 (Mathematik)|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 (Relation)|transitive Hülle]] von <math>R</math>.<ref>{{Literatur |Autor=Seymor Lipschutz, Marc Lipson |Titel=Schaum's Outline of Discrete Mathematics |Verlag=McGraw Hill Professional |Datum=1997-06-22 |ISBN=978-0-07-136841-4 |Seiten=35 |Online=https://books.google.de/books?id=6A5g3RiYiBUC&pg=PA33&dq=Transitive+Relation&hl=de&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwjE6fru2_7-AhXFhP0HHZqRA3gQ6AF6BAgBEAI#v=onepage&q=Transitive%20Relation&f=false |Abruf=2023-05-18}}</ref><br />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><\ </math>.
* Jede Relation auf einer Menge <math>M</math> mit <math>|M| < 3 </math> ist transitiv oder symmetrisch.

== Beispiele ==
Wichtiges Beispiel aus der [[Volkswirtschaftslehre]] ist das [[Nichtsättigungsaxiom]].

=== Ordnung der reellen Zahlen ===
[[Datei:Relacion transitiva.svg|mini|Aus a > b und b > c folgt a > c]]
Die Kleiner-Relation <math><\ </math> auf den [[Reelle Zahl|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 [[strenge Totalordnung]].

Ebenso sind die Relationen <math>>\ </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 [[Teilbarkeit#Definition|Teilt-Relation]] <math>|</math> für [[ganze Zahl]]en 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ürliche Zahl|natürlichen Zahlen]] erhält man eine [[Halbordnung]].

Nicht transitiv ist zum Beispiel die [[Teilerfremdheit]] in der Menge der natürlichen oder ganzen Zahlen. 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 [[Gemeinsamer Teiler|gemeinsamen Teiler]] <math>3</math>.

=== Teilmenge ===
Die [[Teilmenge]]nbeziehung <math>\subseteq</math> zwischen [[Menge (Mathematik)|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 [[Disjunkt]]heit von Mengen in jedem [[Mengensystem]] <math>M</math>, das zwei verschiedene disjunkte Mengen enthält. So sind in der [[Potenzmenge]] <math>M = \mathcal P(\mathbb N)</math> 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 [[Parallel (Geometrie)|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.

== Weblinks ==
* {{EoM |Autor= |Titel=Transitivity |Url=https://www.encyclopediaofmath.org/index.php/Transitivity |id=}}

== Einzelnachweise ==
<references />

[[Kategorie:Ordnungstheorie]]

Transitive Relation - Versionsgeschichte

imported>Christian1985: HC: Entferne Kategorie:Mathematischer Grundbegriff