Antitransitive Relation (Antitransitivität)
Eine antitransitive Relation ist eine eine zweistellige Relation $R$ auf einer Menge, bei der für alle Elemente der Menge aus $(a,b) \in R$ und $(b,c) \in R$ stets $(a,c) \notin R$ folgt. Diese Eigenschaft wird in der Mathematik auch Antitransitivität genannt.
Eine mit der Antitransitivität eng verwandte Eigenschaft ist die Transitivität.
Definition
Sei $A$ eine Menge und $R \subseteq A \times A$ eine auf dieser Menge definierte binäre Relation. Die Relation $R$ heißt antitransitiv, falls die folgende Eigenschaft gilt:
In Worten: Eine Relation ist genau dann antitransitiv, wenn für alle Elemente der zugrundeliegenden Menge gilt: Steht ein Element $a$ in Relation mit einem Element $b$, und steht $b$ wiederum in Relation mit einem Element $c$, so steht $a$ niemals in Relation mit $c$. Die Elemente $a$, $b$ und $c$ müssen hierbei nicht notwendigerweise verschieden sein. Wird der zur Relation gehörende gerichtete Graph betrachtet, so gibt es entsprechend niemals eine direkte Kante von $a$ nach $c$, falls es Kanten von $a$ nach $b$ und von $b$ nach $c$ gibt. Da die Elemente nicht verschieden sein müssen, gilt dies auch für Schlingen von einem Element zu sich selbst; diese dürfen bei antitransitiven Relationen nicht vorkommen.
Diese Eigenschaft wird auch als Antiransitivität bezeichnet. Ist die Antitransitivitätsbedingung verletzt, so ist die Relation nicht antitransitiv.
Hinweis: Eine Relation ist antitransitiv, solange die Antitransitivitätsbedingung nicht explizit verletzt ist. Es ist insbesondere nicht notwendig, dass tatsächlich Elemente $a$, $b$ und $c$ existieren, für die $(a,b) \in R$ und $(b,c) \in R$ gilt.
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 – dass die Transitivitätsbedingung also mindestens einmal verletzt ist. Im Gegensatz zur Antitransitivität ist es nicht explizit verboten, dass Elemente $a$, $b$ und $c$ mit $(a,b) \in R$ und $(b,c) \in R$ existieren, für die $(a,c) \in R$ gilt.
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 bzw. Antitransitivität 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.