Antitransitive Relation

Bei einer antitransitiven Relation handelt es sich um eine zweistellige Relation \(R\) auf einer Menge, bei der aus \((a,b) \in R\) und \((b,c) \in R\) stets \((a,c) \notin R\) folgt.

Eine mit der Antitransitivität eng verwandte Eigenschaft von Relationen ist Transitivität.

Definition

Sei \(A\) eine Menge und \(R \subseteq A \times A\) eine auf dieser Menge definierte zweistellige Relation. Die Relation \(R\) heißt antitransitiv, falls gilt:

Steht ein Element \(a\) also in Relation mit einem Element \(b\), und steht \(b\) in Relation mit einem Element \(c\), so stehen niemals \(a\) und \(c\) in Relation. Betrachtet man den zur Relation gehörenden gerichteten Graphen, so gibt es also nie eine direkte Kante von \(a\) nach \(c\), falls es Kanten von \(a\) nach \(b\) und von \(b\) nach \(c\) gibt. Die Elemente \(a\), \(b\) und \(c\) müssen hierbei nicht notwendigerweise verschieden sein, so dass auch Elemente \((a,a) \in R\) nicht zulässig sind.

Ist die Antitransitivitätsbedingung verletzt, so ist die Relation nicht antitransitiv.

Hinweis: Teilweise wird anstelle von antitransitiv fälschlicherweise auch der Begriff intransitiv verwendet. Intransitivität fordert jedoch lediglich, dass es Elemente \(a,b,c \in A\) mit \((a,b) \in R\) und \((b,c) \in R\) gibt, für die \((a,c) \notin R\) gilt. Im Gegensatz zur Antitransitivität ist es nicht explizit verboten, dass Elemente \(a,b,c \in A\) mit \((a,b) \in R\) und \((b,c) \in R\) existieren, für die \((a,c) \in R\) gilt.

Hinweis: Eine Relation ist antitransitiv, solange die Antitransitivitätsbedingung nicht explizit verletzt ist. Es ist insbesondere nicht notwendig, dass Elemente \(a,b,c \in A\) mit \((a,b) \in R\) und \((b,c) \in R\) tatsächlich existieren.

Beispiele

Beispiel 1

Gegeben sei die Menge \(A = \bigl\{ a,b,c,d \bigr\}\) sowie eine auf dieser Menge definierte zweistellige Relation \(R_1\) mit

Die Relation \(R_1\) ist antitransitiv, da für alle Elemente \(x,y,z \in A\) stets gilt: Aus \((x,y) \in R_1\) und \((y,z) \in R_1\) folgt \((x,z) \in R_1\).

Beispiel 2

Gegeben sei die Menge \(A = \bigl\{ a,b,c,d \bigr\}\) sowie eine auf dieser Menge definierte zweistellige Relation \(R_2\) mit

Die Relation \(R_2\) ist nicht antitransitiv, da die Antitransitivitätsbedingung verletzt ist:

• Es gilt \((a,a) \in R_2\).
• Es gilt \((a,b) \in R_2\) und \((b,c) \in R_2\), aber ebenso \((a,c) \in R_2\).
• Es gilt \((a,d) \in R_2\) und \((d,c) \in R_2\), aber ebenso \((a,c) \in R_2\).

Beispiel 3

Gegeben sei die Menge \(A = \bigl\{ a,b,c,d \bigr\}\) sowie eine auf dieser Menge definierte zweistellige Relation \(R_3\) mit

Die Relation \(R_3\) ist antitransitiv, da für alle Elemente \(x,y,z \in A\) stets gilt: Aus \((x,y) \in R_3\) und \((y,z) \in R_3\) folgt \((x,z) \notin R_3\). Da die Relation \(R_3\) keine Elemente enthält, existieren insbesondere auch keine Verletzungen der Antitransitivitätsbedingung.

Beispiele in der Praxis

Schere, Stein, Papier

Die Gewinnt-Beziehung beim Spiel Schere, Stein, Papier ist antitransitiv. Es gilt:

• Schere gewinnt gegen Papier, Papier gewinnt gegen Stein, Schere gewinnt aber nicht gegen Stein;
• Papier gewinnt gegen Stein, Stein gewinnt gegen Schere, Papier gewinnt aber nicht gegen Schere;
• Stein gewinnt gegen Schere, Schere gewinnt gegen Papier, Stein gewinnt aber nicht gegen Papier.

Ist-Mutter/Vater-Beziehung

Die Ist Mutter von-Beziehung ist antitransitiv. Ist \(A\) die Mutter von \(B\), und ist \(B\) die Mutter von \(C\), so ist \(A\) niemals die Mutter von \(C\). Dies gilt analog auch für die Ist Vater von-Beziehung.

Eigenschaften

Für antitransitive Relationen gelten unter anderem die folgenden Eigenschaften:

• Eine antitransitive Relation ist stets irreflexiv. Umgekehrt ist eine irreflexive Relation aber nicht immer antitransitiv.
• Ist eine Relation \(R\) antitransitiv, so ist auch ihre Umkehrrelation \(R^{-1}\) antitransitiv.
• Sind \(R\) und \(S\) antitransitive Relationen, so sind auch ihr Schnitt \(R \cap S\) eine antitransitive Relation. Die Aussage gilt analog für den Schnitt von mehr als zwei Relationen.
• Ist \(R\) eine antitransitive Relation, so ist auch jede Teilmenge von R eine antitransitive Relation.