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