Mathe für Nicht-Freaks: Relation: Ordnungsrelation

Ordnungsrelation

Eine Ordnungsrelation ist wie die Äquivalenzrelation eine besondere Klasse binärer, homogener Relationen. Sie ist eine Verallgemeinerung der Kleiner-Gleich-Relation $\le$, die du bereits auf der Menge der reellen Zahlen $\R$ kennst. Mit Hilfe von Ordnungsrelationen kannst du also Elemente einer Grundmenge ihrer Größe nach ordnen und miteinander vergleichen. Genau wie die Äquivalenzrelation werden Ordnungsrelationen über ihre Eigenschaften definiert.

Frage: Welche Eigenschaft besitzt die Relation „$x\le y$“ auf der Grundmenge $\R$?

Die Kleiner-Gleich-Relation „$x\le y$“ besitzt folgende Eigenschaften:

• reflexiv (Für alle $x\in\R$ ist $x\le x$)
• nicht irreflexiv (Diese Relation ist reflexiv und die Grundmenge ist nicht leer)
• nicht symmetrisch (Gegenbeispiel: Es ist $23\le 42$ aber $42 \not\le 23$ und damit kann die Relation nicht symmetrisch sein)
• antisymmetrisch (Aus $x\le y$ und $y\le x$ folgt $x=y$)
• transitiv (Aus $x\le y$ und $y\le z$ folgt $x\le z$)
• linear (Für alle reellen Zahlen $x$ und $y$ ist entweder $x\le y$ oder $y\le x$)

Totalordnung

Totalordnungen sind direkte Verallgemeinerungen der Kleiner-Gleich-Relation auf den reellen Zahlen, die genau diejenigen Eigenschaften besitzt, die auch die Kleiner-Gleich-Relation besitzt:

Definition (Totalordnung): Eine Totalordnung $R\subseteq M\times M$ ist eine binäre und homogene Relation auf der Grundmenge $M$, die folgende Eigenschaften besitzt: reflexiv antisymmetrisch transitiv linear

Beispiel (Totalordnung): Die $x\le y$ Relation auf der Grundmenge $\R$ ist eine Totalordnung. Die $x\ge y$ Relation auf der Grundmenge $\R$ ist eine Totalordnung. Die lexikographische Ordnung der Wörter im Duden ist eine Totalordnung

Halbordnung

Es gibt Relationen, die bis auf die Linearität alle Eigenschaften der Totalordnung erfüllen. Damit verhalten sie sich fast wie Totalordnungen. Jedoch können bei diesen Relationen nicht alle Paare von Elemente der Grundmenge miteinander verglichen werden. Diese Relationen werden Halbordnungen oder partielle Ordnungen genannt (eben weil diese Ordnungen nur „zur Hälfte“ Totalordnungen sind):

Definition (Halbordnung): Eine Halbordnung $R\subseteq M\times M$ ist eine binäre und homogene Relation auf der Grundmenge $M$, die folgende Eigenschaften besitzt: reflexiv antisymmetrisch transitiv

Beispiel (Halbordnung): Die $x\le y$ Relation auf der Grundmenge $\R$ ist eine Halbordnung. Die Teilmengenbeziehung auf jeder Menge von Mengen ist eine Halbordnung.

Aus der Definition folgt, dass jede Totalordnung eine Halbordnung ist, aber nicht jede Halbordnung ist eine Totalordnung (die Teilmengenbeziehung ist eine Halbordnung, die keine Totalordnung ist).

Nachweis von Ordnungsrelationen

Wenn du die Aufgabe hast zu entscheiden, ob eine gegebene Relation eine Totalordnung bzw. eine Halbordnung ist, so musst du schauen, ob diese Relation alle notwendigen Eigenschaften für diese Art von Relation erfüllt. Der folgende Entscheidungsbaum demonstriert dir die Vorgehensweise:

Beispielaufgabe

Stell dir vor, du musst folgende Aufgabe lösen:

Ist die Relation „$x$ ist eine Teilmenge von $y$“ auf der Grundmenge $\mathcal P(\R)$, der Menge aller Teilmengen von $\R$, eine Halbordnung bzw. eine Totalordnung?

Hier kannst du schrittweise vorgehen:

Frage: Ist die Relation reflexiv?

Ja, die Relation ist reflexiv, denn jede Menge ist nach Definition eine Teilmenge von sich selbst (Für alle Mengen $M$ gilt $M\subseteq M$).

Frage: Ist die Relation antisymmterisch?

Ja, die Relation ist antisymmetrisch, weil aus $A\subseteq B$ und $B\subseteq A$ die Gleichheit $A=B$ folgt.

Frage: Ist die Relation transitiv?

Ja, die Relation ist transitiv, weil aus $A\subseteq B$ und $B\subseteq C$ die Beziehung $A\subseteq C$ folgt.

Frage: Ist die Relation linear?

Nein, die Relation ist nicht linear. So ist weder $\{1,2,3\}\subseteq \{4,5,6\}$ noch ist $\{4,5,6\}\subseteq\{1,2,3\}$.

Frage: Ist die Relation eine Halbordnung bzw. eine Totalordnung?

Da die Relation reflexiv, antisymmetrisch und transitiv ist, ist sie eine Halbordnung. Da die Relation aber nicht linear ist, ist sie keine Totalordnung.