Antisymmetrische Relation (Antisymmetrie)
Eine antisymmetrische Relation ist eine zweistellige Relation $R$ auf einer Menge, bei der für alle Elemente der Menge aus $(a,b) \in R$ stets $(b,a) \notin R$ folgt, falls $a \neq b$ gilt. Diese Eigenschaft wird in der Mathematik auch Antisymmetrie genannt. Sie ist eine der Voraussetzungen für eine Halbordnung.
Mit der Antisymmetrie eng verwandte Eigenschaften sind die Symmetrie und die Asymmetrie.
Definition
Sei $A$ eine Menge und $R \subseteq A \times A$ eine auf dieser Menge definierte binäre Relation. Die Relation $R$ heißt antisymmetrisch, falls die folgende Eigenschaft gilt:
In Worten: Eine Relation ist genau dann antisymmetrisch, wenn für alle Elemente der zugrundeliegenden Menge gilt: Steht ein Element $a$ in Relation mit einem von $a$ verschiedenen Element $b$, so steht $b$ niemals in Relation mit $a$. Wird der zur Relation gehörende gerichtete Graph betrachtet, so gibt es folglich zu keiner Kante die entgegengesetzte Kante. Schlingen von einem Element zu sich selbst sind hiervon ausgenommen.
Diese Eigenschaft wird auch als Antisymmetrie bezeichnet. Ist die Antisymmetriebedingung verletzt, so ist die Relation nicht antisymmetrisch.
Die Antisymmetriebedingung lässt sich alternativ auch wie folgt ausdrücken:
In Worten: Eine Relation ist genau dann antisymmetrisch, wenn für alle Elemente der zugrundeliegenden Menge gilt: Steht ein Element $a$ in Relation mit einem Element $b$, und steht $b$ darüber hinaus in Relation mit $a$, so muss es sich bei $a$ und $b$ um dasselbe Element handeln.
Hinweis: Eine Relation ist antisymmetrisch, solange die Antisymmetriebedingung nicht explizit verletzt ist. Es ist insbesondere nicht notwendig, dass tatsächlich Elemente $a$ und $b$ existieren, für die $(a,b) \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 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$ für natürliche, ganze, rationale oder reelle Zahlen handelt es sich um eine antisymmetrische Relation. 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 eine Ordnungsrelation.
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 antisymmetrische Relationen bzw. Antisymmetrie 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 $\mathrm{I}_A$ ist, wenn also gilt: \[ R \cap R^{-1} \subseteq \mathrm{I}_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.