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 auf einer Menge, wenn für beliebige Elemente und der Menge mit nicht zugleich die Umkehrung gelten kann, es sei denn, und sind gleich. Äquivalent formuliert gilt damit für beliebige Elemente und dieser Menge, dass aus und stets folgt.

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

Formale Definition[Bearbeiten | Quelltext bearbeiten]

Ist eine Menge und eine zweistellige Relation auf , dann heißt antisymmetrisch, wenn (unter Verwendung der Infixnotation) gilt:

Sonderfall Asymmetrische Relation[Bearbeiten | Quelltext bearbeiten]

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

gilt, also für keines der geordneten Paare die Umkehrung zutrifft,

ist die Prämisse der Definition der antisymmetrischen Relation stets falsch und nach dem logischen Prinzip Ex falso quodlibet somit die Aussage erfüllt.

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

Beispiele[Bearbeiten | Quelltext bearbeiten]

Antisymmetrisch sind die Relationen und auf den reellen Zahlen. Aus und folgt . Das Gleiche gilt für und .

Auch die Teilbarkeitsrelation für natürliche Zahlen ist antisymmetrisch, denn aus und folgt . Die Teilbarkeit auf den ganzen Zahlen ist hingegen nicht antisymmetrisch, weil beispielsweise und gilt, obwohl .

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

Darstellung als gerichteter Graph[Bearbeiten | Quelltext bearbeiten]

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

Die Antisymmetrie von lässt sich im Graphen nun so charakterisieren: Wann immer es einen Pfeil zwischen verschiedenen Knoten und des Graphen gibt, dann kann es nicht gleichzeitig einen Pfeil geben.

Schleifen brauchen bei diesem Kriterium nicht untersucht zu werden.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

  • Mit Hilfe der konversen Relation lässt sich die Antisymmetrie auch durch die folgende Bedingung charakterisieren:
Hierbei bezeichnet die identische Relation auf der Grundmenge , also die Menge aller Paare .
  • Sind die Relationen und antisymmetrisch, dann gilt dies auch für ihre Schnittmenge . Diese Aussage lässt sich von zwei Relationen auf den Durchschnitt einer beliebigen (nichtleeren) Familie von antisymmetrischen Relationen verallgemeinern.
  • Jede Teilmenge einer antisymmetrischen Relation ist wieder antisymmetrisch.

Weblinks[Bearbeiten | Quelltext bearbeiten]

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

Einzelnachweise[Bearbeiten | Quelltext 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.