Antisymmetrische Relation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
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.

Formale Definition[Bearbeiten]

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

Sonderfall Asymmetrische Relation[Bearbeiten]

Jede asymmetrische Relation ist auch eine antisymmetrische Relation.[1] Da für eine asymmetrische Relation R auf M

\forall x, y \in M: x R y \Rightarrow \neg (y R x) gilt, also für keines der geordneten Paare (x,y) die Umkehrung zutrifft,

ist die Prämisse xRy \and yRx der Definition der antisymmetrischen Relation stets falsch und nach dem logischen Prinzip Ex falso quodlibet somit die Aussage \forall x, y \in M: xRy \and yRx \Rightarrow x = y erfüllt.

Die Asymmetrie ist eine der Voraussetzungen für eine (irreflexive) Striktordnung.

Beispiele[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

  • 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}_M
Hierbei bezeichnet \mathrm{Id}_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.

Weblinks[Bearbeiten]

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

Einzelnachweise[Bearbeiten]

  1. Ingmar Lehmann, Wolfgang Schulz: Mengen – Relationen – Funktionen. Eine anschauliche Einführung. 3., überarbeitete und erweiterte Auflage. Teubner, Wiesbaden 2007, ISBN 978-3-8351-0162-3.