Antisymmetrie

aus Wikipedia, der freien Enzyklopädie

Eine antisymmetrische Relation, als gerichteter Graph dargestellt

Eine nicht antisymmetrische Relation, als gerichteter Graph dargestellt

Die Antisymmetrie einer zweistelligen Relation R auf einer Menge ist gegeben, wenn für zwei beliebige verschiedene Elemente x und y der Menge nicht gleichzeitig x R y und y R x gelten kann. Äquivalent formuliert heißt dies, dass für beliebige Elemente x und y der Menge aus x R y und y R x stets x = y folgt. Man nennt R dann antisymmetrisch.

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

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

[Bearbeiten] Beispiele

[Bearbeiten] Ordnung der reellen Zahlen

Die Kleiner-Relation $\!\,<$ auf den reellen Zahlen ist antisymmetrisch, denn für verschiedene Zahlen $x$ und $y$ kann nicht gleichzeitig $x < y$ und $y < x$ gelten. Sie ist darüber hinaus eine strenge Totalordnung.

Ebenso sind die Relationen $\!\,>$ , $\le$ und $\ge$ Ordnungsrelationen, also antisymmetrisch.

[Bearbeiten] Teilbarkeit der natürlichen Zahlen

Die Teilbarkeitsrelation $\mid$ für natürliche Zahlen ist antisymmetrisch, denn aus $a \mid b$ und $b \mid a$ folgt $a = b$ . Sie ist darüber hinaus eine Halbordnung.

Betrachtet man hingegen die Teilbarkeit auf den ganzen Zahlen, dann ist sie nicht mehr antisymmetrisch, weil zum Beispiel für die (verschiedenen) Zahlen $3$ und $- 3$ sowohl $3 \mid -3$ als auch $-3 \mid 3$ gilt.

[Bearbeiten] Teilmenge

Die Teilmengenbeziehung $\subseteq$ zwischen Mengen ist antisymmetrisch, denn aus $A\subseteq B$ und $B\subseteq A$ folgt $\!\,A=B$ . Darüber hinaus ist $\subseteq$ eine Halbordnung.

Auch die echte Teilmengenbeziehung $\subsetneq$ ist antisymmetrisch, da für verschiedene Mengen $A$ und $B$ nicht gleichzeitig $A \subsetneq B$ und $B \subsetneq A$ gelten kann. Sie ist darüber hinaus eine strenge Halbordnung.

[Bearbeiten] Nachfolgerbeziehung

Die durch $x R y :\Leftrightarrow x = y+1$ definierte Relation auf den ganzen Zahlen ( $x$ ist der Nachfolger von $y$ ) ist antisymmetrisch, denn zwei verschiedene Zahlen können nicht gegenseitig Nachfolger voneinander sein. Es liegt allerdings keine Ordnungsrelation vor.

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

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