Antisymmetrische Relation
Bei einer antisymmetrischen Relation handelt es sich um eine zweistellige Relation \(R\) auf einer Menge, bei der aus \((a,b) \in R\) stets \((b,a) \notin R\) folgt, falls \(a \neq b\) gilt. Antisymmetrie ist eine der Voraussetzungen für eine Halbordnung.
Mit der Antisymmetrie eng verwandte Eigenschaften von Relationen sind Symmetrie und Asymmetrie.
Definition
Sei \(A\) eine Menge und \(R \subseteq A \times A\) eine auf dieser Menge definierte zweistellige Relation. Die Relation \(R\) heißt antisymmetrisch, falls gilt:
Steht ein Element \(a\) also in Relation mit einem von \(a\) verschiedenen Element \(b\), so stehen umgekehrt niemals \(b\) und \(a\) in Relation. Betrachtet man den zur Relation gehörenden gerichteten Graphen, so gibt es also zu keiner Kante von \(a\) nach \(b\) die entgegengesetzte Kante von \(b\) nach \(a\). Schlingen von einem Element zu sich selbst sind hiervon ausgenommen.
Die Antisymmetriebedingung lässt sich alternativ auch wie folgt ausdrücken:
Ist die Antisymmetriebedingung verletzt, so ist die Relation nicht antisymmetrisch.
Hinweis: Eine Relation ist antisymmetrisch, solange die Antisymmetriebedingung nicht explizit verletzt ist. Es ist insbesondere nicht notwendig, dass Elemente \(a,b \in A\) mit \((a,b) \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 antisymmetrisch, da für alle Elemente \(x,y \in A\) mit \(x \neq y\) stets gilt: Aus \((x,y) \in R_1\) folgt \((y,x) \notin 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 antisymmetrisch, da die Antisymmetriebedingung verletzt ist:
- Es gilt \((b,d) \in R_2\) und \((d,b) \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 antisymmetrisch, da für alle Elemente \(x,y \in A\) mit \(x \neq y\) stets gilt: Aus \((x,y) \in R_3\) folgt niemals \((y,x) \in R_3\).
Beispiel 4
Gegeben sei die Menge \(A = \bigl\{ a,b,c,d \bigr\}\) sowie eine auf dieser Menge definierte zweistellige Relation \(R_4\) mit
Die Relation \(R_4\) ist antisymmetrisch, da für alle Elemente \(x,y \in A\) mit \(x \neq y\) stets gilt: Aus \((x,y) \in R_4\) folgt niemals \((y,x) \in R_4\). Da die Relation \(R_4\) keine Elemente enthält, existieren insbesondere auch keine Verletzungen der Antisymmetriebedingung.
Beispiele in der Mathematik
Anordnen von Zahlen
Bei der Kleinergleich-Relation \(\leq\) von natürlichen, ganzen, rationalen oder reellen Zahlen handelt es sich um antisymmetrische Relationen. Gilt sowohl \(a \leq b\) als auch \(b \leq a\), so folgt stets \(a=b\). Dasselbe gilt analog für die Größergleich-Relation \(\geq\). In beiden Fällen handelt es sich um Ordnungsrelationen.
Teilbarkeit
Die Teilbarkeitsrelation \(\mid\) für natürliche Zahlen ist antisymmetrisch. Gilt für natürliche Zahlen \(a\) und \(b\) sowohl \(a \mid b\) als auch \(b \mid a\), so folgt stets \(a=b\). Es handelt sich bei der Teilbarkeitsrelation um eine Ordnungsrelation.
Die Teilbarkeitsrelation \(\mid\) für ganze Zahlen ist hingegen nicht antisymmetrisch, da beispielsweise sowohl \(2 \mid -2\) als auch \(-2 \mid 2\) gilt, obwohl \(-2\) und \(2\) verschiedene Zahlen sind.
Teilmenge
Die Teilmengenbeziehung \(\subseteq\) ist antisymmetrisch. Gilt für Mengen \(A\) und \(B\) sowohl \(A \subseteq B\) als auch \(B \subseteq A\), so folgt stets \(A=B\). Es handelt sich bei der Teilmengenbeziehung um eine Ordnungsrelation.
Eigenschaften
Für Relationen gelten unter anderem die folgenden Eigenschaften:
- Eine Relation \(R\) ist genau dann antisymmetrisch, wenn die Schnittmenge mit ihrer Umkehrrelation \(R^{-1}\) eine Teilmenge der Identitätsrelation \({Id}_A\) ist, wenn also gilt: \[ R \cap R^{-1} \subseteq {Id}_A. \]
- Jede Teilmenge einer antisymmetrischen Relation ist wieder eine antisymmetrische Relation.
- Sind \(R\) und \(S\) antisymmetrische Relationen, so ist auch ihr Schnitt \(R \cap S\) eine antisymmetrische Relation. Die Aussage gilt analog für den Schnitt von mehr als zwei Relationen.