Antisymmetrische Relation

Eine antisymmetrische Relation, als gerichteter Graph dargestellt

Eine nicht antisymmetrische Relation, als gerichteter Graph dargestellt

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 \land yRx \Rightarrow x = y</math>

Sonderfall Asymmetrische Relation

Jede asymmetrische Relation ist auch eine antisymmetrische Relation.<ref>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.</ref> 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 \land 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 \land 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><</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 also 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

[[wikt:{{#if:|{{{lang}}}:}}{{#if:antisymmetrisch|antisymmetrisch|{{#invoke:WLink|getArticleBase}}}}|Wiktionary: {{#if:|{{{2}}}|{{#if:antisymmetrisch|antisymmetrisch|{{#invoke:WLink|getArticleBase}}}}}}]]{{#switch: 1

|1|= – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen |0|-= |X|x= |#default= –

}}{{#if:| {{#ifeq: {{{lang}}} | de | {{#ifeq: 0 | 0 | }} | ({{#invoke:Multilingual|format|{{{lang}}}|slang=!|shift=m}}) }}}}

{{#invoke:TemplatePar|check

  |opt= 1= 2= lang= suffix=
  |template=Vorlage:Wiktionary
  |cat=Wikipedia:Vorlagenfehler/Schwesterprojekt
  }}

Einzelnachweise