Antisymmetrische Relation

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

Eine antisymmetrische Relation, als gerichteter Graph dargestellt

Eine nicht antisymmetrische Relation, als gerichteter Graph dargestellt

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

Definition

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

${\displaystyle \forall x,y\in M:xRy\land yRx\Rightarrow x=y}$

Sonderfall Asymmetrische Relation

Jede asymmetrische Relation ist auch eine antisymmetrische Relation.^[1] Da für eine asymmetrische Relation ${\displaystyle R}$ auf ${\displaystyle M}$

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

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

Beispiele

Antisymmetrisch sind die Relationen ${\displaystyle \leq }$ und ${\displaystyle \geq }$ auf den reellen Zahlen. Aus ${\displaystyle x\leq y}$ und ${\displaystyle y\leq x}$ folgt ${\displaystyle x=y}$. Das Gleiche gilt für ${\displaystyle x\geq y}$ und ${\displaystyle y\geq x}$.

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

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

Darstellung als gerichteter Graph

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

Die Antisymmetrie von ${\displaystyle R}$ lässt sich im Graphen nun so charakterisieren: Wann immer es einen Pfeil ${\displaystyle a\longrightarrow b}$ zwischen verschiedenen Knoten ${\displaystyle a}$ und ${\displaystyle b}$ des Graphen gibt, dann kann es nicht gleichzeitig einen Pfeil ${\displaystyle b\longrightarrow a}$ geben. Schleifen ${\displaystyle {\stackrel {a}{\circlearrowright }}}$ brauchen also bei diesem Kriterium nicht untersucht zu werden.

Eigenschaften

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

  ${\displaystyle R\cap R^{-1}\subseteq \mathrm {Id} _{M}}$

Hierbei bezeichnet ${\displaystyle \mathrm {Id} _{M}}$ die identische Relation auf der Grundmenge ${\displaystyle M}$, also die Menge aller Paare ${\displaystyle (x,x)}$.

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

Weblinks

Wiktionary: antisymmetrisch – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen