Antisymmetrische Relation

Eine antisymmetrische Relation, als gerichteter Graph dargestellt

Eine nicht antisymmetrische Relation, als gerichteter Graph dargestellt

Antisymmetrisch heißt eine zweistellige Relation $R$ auf einer Menge, wenn für beliebige Elemente $x$ und $y$ der Menge mit $xRy$ nicht zugleich die Umkehrung $yRx$ gelten kann, es sei denn, $x$ und $y$ sind gleich. Äquivalent formuliert gilt damit für beliebige Elemente $x$ und $y$ dieser Menge, dass aus $xRy$ und $yRx$ stets $x=y$ folgt.

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

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:

$\mathrm{\forall }x,y\in M:xRy\wedge yRx\Rightarrow x=y$

Sonderfall Asymmetrische Relation

Jede asymmetrische Relation ist auch eine antisymmetrische Relation. Da für eine asymmetrische Relation $R$ auf $M$

$\mathrm{\forall }x,y\in M:xRy\Rightarrow \mathrm{\neg }(yRx)$

gilt, also für keines der geordneten Paare $(x,y)$ die Umkehrung zutrifft, ist die Prämisse $xRy\wedge yRx$ der Definition der antisymmetrischen Relation stets falsch und nach dem logischen Prinzip Ex falso quodlibet somit die Aussage $\mathrm{\forall }x,y\in M:xRy\wedge yRx\Rightarrow x=y$ erfüllt. Die Asymmetrie ist eine der Voraussetzungen für eine (irreflexive) Striktordnung.

Beispiele

Antisymmetrisch sind die Relationen $\le$ und $\ge$ auf den reellen Zahlen. Aus $x\le y$ und $y\le x$ folgt $x=y$. Das Gleiche gilt für $x\ge y$ und $y\ge x$.

Auch die Teilbarkeitsrelation $\mid$ für natürliche Zahlen ist antisymmetrisch, denn aus $a\mid b$ und $b\mid a$ folgt $a=b$. Die Teilbarkeit auf den ganzen Zahlen ist hingegen nicht antisymmetrisch, weil beispielsweise $3\mid -3$ und $-3\mid 3$ gilt, obwohl $-3\ne 3$.

Asymmetrische Relationen sind die Kleiner-Relation $<$ auf den reellen Zahlen und die Teilmengenbeziehung $\subset$ zwischen Mengen. Verglichen mit $\le$ beziehungsweise $\subseteq$ fehlt diesen Beziehungen die Reflexivität.

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⟶b$) gezogen, wenn $aRb$ gilt.

Die Antisymmetrie von $R$ lässt sich im Graphen nun so charakterisieren: Wann immer es einen Pfeil $a⟶b$ zwischen verschiedenen Knoten $a$ und $b$ des Graphen gibt, dann kann es nicht gleichzeitig einen Pfeil $b⟶a$ geben. Schleifen $\stackrel{a}{\circlearrowright }$ brauchen also 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{I}\mathrm{d}}_M$

Hierbei bezeichnet ${\mathrm{I}\mathrm{d}}_M$ die identische Relation auf der Grundmenge $M$, 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.