Antisymmetrie

Eine antisymmetrische Relation, als gerichteter Graph dargestellt

Eine nicht antisymmetrische Relation, als gerichteter Graph dargestellt

Die Antisymmetrie einer zweistelligen Relation R auf einer Menge ist gegeben, wenn für zwei beliebige verschiedene Elemente x und y der Menge nicht gleichzeitig x R y und y R x gelten kann. Äquivalent formuliert heißt dies, dass für beliebige Elemente x und y der Menge aus x R y und y R x stets x = y folgt. Man nennt R dann antisymmetrisch.

Die Antisymmetrie ist eine der Voraussetzungen für eine Ordnungsrelation.

Formale Definition

Ist M eine Menge und $R \subseteq M \times M$ eine zweistellige Relation auf M, dann heißt R antisymmetrisch, wenn (unter Verwendung der Infixnotation) gilt:

$\forall x, y \in M: xRy \and yRx \Rightarrow x = y$

Beispiele

Ordnung der reellen Zahlen

Die Kleiner-Relation $\!\,&amp;amp;lt;$ auf den reellen Zahlen ist antisymmetrisch, denn für verschiedene Zahlen x und y kann nicht gleichzeitig x < y und y < x gelten. Sie ist darüber hinaus eine strenge Totalordnung.

Ebenso sind die Relationen $\!\,&amp;amp;gt;$, $\le$ und $\ge$ Ordnungsrelationen, also antisymmetrisch.

Teilbarkeit der natürlichen Zahlen

Die Teilbarkeitsrelation $\mid$ für natürliche Zahlen ist antisymmetrisch, denn aus $a \mid b$ und $b \mid a$ folgt a = b. Sie ist darüber hinaus eine Halbordnung.

Betrachtet man hingegen die Teilbarkeit auf den ganzen Zahlen, dann ist sie nicht mehr antisymmetrisch, weil zum Beispiel für die (verschiedenen) Zahlen 3 und − 3 sowohl $3 \mid -3$ als auch $-3 \mid 3$ gilt.

Teilmenge

Die Teilmengenbeziehung $\subseteq$ zwischen Mengen ist antisymmetrisch, denn aus $A\subseteq B$ und $B\subseteq A$ folgt $\!\,A=B$. Darüber hinaus ist $\subseteq$ eine Halbordnung.

Auch die echte Teilmengenbeziehung $\subsetneq$ ist antisymmetrisch, da für verschiedene Mengen A und B nicht gleichzeitig $A \subsetneq B$ und $B \subsetneq A$ gelten kann. Sie ist darüber hinaus eine strenge Halbordnung.

Nachfolgerbeziehung

Die durch $x R y :\Leftrightarrow x = y+1$ definierte Relation auf den ganzen Zahlen (x ist der Nachfolger von y) ist antisymmetrisch, denn zwei verschiedene Zahlen können nicht gegenseitig Nachfolger voneinander sein. Es liegt allerdings keine Ordnungsrelation vor.

Darstellung als gerichteter Graph

Jede beliebige Relation R auf einer Menge M kann als gerichteter Graph aufgefasst werden (Beispiel siehe oben). Die Knoten des Graphen sind dabei die Elemente von M. Vom Knoten a zum Knoten b wird genau dann eine gerichtete Kante (ein Pfeil $a \longrightarrow b$) gezogen, wenn $a\,R\, b$ gilt.

Die Antisymmetrie von R lässt sich im Graphen nun so charakterisieren: Wann immer es einen Pfeil $a \longrightarrow b$ zwischen verschiedenen Knoten a und b des Graphen gibt, dann kann es nicht gleichzeitig einen Pfeil $b \longrightarrow a$ geben.

Schleifen $\stackrel{a}\circlearrowright$ brauchen bei diesem Kriterium nicht untersucht zu werden.

Eigenschaften

• Mit Hilfe der konversen Relation R ^{− 1} lässt sich die Antisymmetrie auch durch die folgende Bedingung charakterisieren:

  $R \cap R^{-1} \subseteq \mathrm{Id}_X$

Hierbei bezeichnet Id_X die identische Relation auf der Grundmenge X, also die Menge aller Paare (x,x).

• Sind die Relationen R und S antisymmetrisch, dann gilt dies auch für ihre Schnittmenge $R \cap S$. Diese Aussage lässt sich von zwei Relationen auf den Durchschnitt $\cap_{i\in I} R_i$ einer beliebigen (nichtleeren) Familie von antisymmetrischen Relationen verallgemeinern.
• Jede Teilmenge einer antisymmetrischen Relation ist wieder antisymmetrisch.

Siehe auch

• Symmetrie (Mengenlehre)
• Halbordnung
• Relation (Mathematik)