Antisymmetrische Relation

Eine antisymmetrische Relation, als gerichteter Graph dargestellt

Eine nicht antisymmetrische Relation, als gerichteter Graph dargestellt

Antisymmetrie ist eine Eigenschaft zweistelliger Relationen. Eine solche Relation $R$ auf einer Menge heißt antisymmetrisch, wenn für je zwei verschiedene Elemente $x$ und $y$ der Menge nicht gleichzeitig $xRy$ und $yRx$ gelten kann. Äquivalent formuliert heißt dies, dass für beliebige Elemente $x$ und $y$ der Menge aus $xRy$ und $yRx$ stets $x=y$ folgt.

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

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$

Beispiel

Die Relationen $\le$ und $\ge$ auf den reellen Zahlen sind antisymmetrisch. Aus $x \le y$ und $y \le x$ folgt $x=y$. Das gleiche gilt für $x \ge y$ und $y \ge x$.

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$.

Beziehung zur Asymmetrie

Jede asymmetrische Relation ist auch antisymmetrisch, denn für asymmetrische Relationen gilt niemals gleichzeitig $xRy$ und $yRx$ (insbesondere ist sogar $xRx$ ausgeschlossen). Deshalb ist der Ausdruck $xRy \and yRx$ immer falsch und infolgedessen die Implikation $xRy \and yRx \Rightarrow x = y$ immer wahr.

Beispiel für asymmetrische Relationen sind die Kleiner-Relation $<$ auf den reellen Zahlen und die Teilmengenbeziehung $\subset$ zwischen Mengen.

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 $\mathrm{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.

Weblinks

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