Antisymmetrische Relation - LinkFang.de





Antisymmetrische Relation


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

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

Definition

Ist [math]M[/math] eine Menge und [math]R \subseteq M \times M[/math] eine zweistellige Relation auf [math]M[/math], dann heißt [math]R[/math] antisymmetrisch, wenn (unter Verwendung der Infixnotation) gilt:

[math]\forall x, y \in M: xRy \and yRx \Rightarrow x = y[/math]

Sonderfall Asymmetrische Relation

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

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

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

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

Beispiele

Antisymmetrisch sind die Relationen [math]\le[/math] und [math]\ge[/math] auf den reellen Zahlen. Aus [math]x \le y[/math] und [math]y \le x[/math] folgt [math]x=y[/math]. Das Gleiche gilt für [math]x \ge y[/math] und [math]y \ge x[/math].

Auch die Teilbarkeitsrelation [math]\mid[/math] für natürliche Zahlen ist antisymmetrisch, denn aus [math]a \mid b[/math] und [math]b \mid a[/math] folgt [math]a=b[/math]. Die Teilbarkeit auf den ganzen Zahlen ist hingegen nicht antisymmetrisch, weil beispielsweise [math]3 \mid -3[/math] und [math]-3 \mid 3[/math] gilt, obwohl [math]-3 \ne 3[/math].

Asymmetrische Relationen sind die Kleiner-Relation [math]\lt[/math] auf den reellen Zahlen und die Teilmengenbeziehung [math]\subset[/math] zwischen Mengen. Verglichen mit [math]\le[/math] beziehungsweise [math]\subseteq[/math] fehlt diesen Beziehungen die Reflexivität.

Darstellung als gerichteter Graph

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

Die Antisymmetrie von [math]R[/math] lässt sich im Graphen nun so charakterisieren: Wann immer es einen Pfeil [math]a \longrightarrow b[/math] zwischen verschiedenen Knoten [math]a[/math] und [math]b[/math] des Graphen gibt, dann kann es nicht gleichzeitig einen Pfeil [math]b \longrightarrow a[/math] geben.

Schleifen [math]\stackrel{a}\circlearrowright[/math] brauchen bei diesem Kriterium nicht untersucht zu werden.

Eigenschaften

  • Mit Hilfe der konversen Relation [math]R^{-1}[/math] lässt sich die Antisymmetrie auch durch die folgende Bedingung charakterisieren:
    [math]R \cap R^{-1} \subseteq \mathrm{Id}_M[/math]
Hierbei bezeichnet [math]\mathrm{Id}_M[/math] die identische Relation auf der Grundmenge [math]M[/math], also die Menge aller Paare [math](x,x)[/math].
  • Sind die Relationen [math]R[/math] und [math]S[/math] antisymmetrisch, dann gilt dies auch für ihre Schnittmenge [math]R \cap S[/math]. Diese Aussage lässt sich von zwei Relationen auf den Durchschnitt [math]\cap_{i\in I} R_i [/math] einer beliebigen (nichtleeren) Familie von antisymmetrischen Relationen verallgemeinern.
  • Jede Teilmenge einer antisymmetrischen Relation ist wieder antisymmetrisch.

Weblinks

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

Einzelnachweise

  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.

Kategorien: Ordnungstheorie | Mengenlehre

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Antisymmetrische Relation (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.