Mathe für Nicht-Freaks: Ordnungsrelation

Ordnungen sind eine besondere Klasse binärer, homogener Relationen. Sie sind eine Verallgemeinerung der Ordnungsrelationen wie $\le$ oder $<$, die du bereits für die Zahlbereiche $\mathbb{N}$, $\mathbb{Z}$ und $ℝ$ kennst. Mit Hilfe von Ordnungsrelationen können Elemente einer Grundmenge ihrer Größe nach geordnet und miteinander verglichen werden.

Um eine Ordnung auf einer Menge zu definieren, reicht es, eine der beiden Relationen $\le$ oder $<$ zu definieren. Die jeweils andere Relation lässt sich dann mit den folgenden Beziehungen darauf zurückführen:

• $x<y$ genau dann, wenn $x\le y$ und $x\ne y$,
• $x\le y$ genau dann, wenn $x<y$ oder $x=y$.

Ordnungsrelationen lassen sich umdrehen: so wird aus der Kleiner-Gleich-Relation $\le$ die Grösser-Gleich-Relation $\ge$ und aus der Echt-Kleiner-Relation $<$ wird die Echt-Größer-Relation $>$. In Listen im Internet kann in der Regel gewählt werden, ob die Ergebnisse aufsteigend oder absteigend sortiert werden sollten.

Ordnungsrelationen gibt es auch außerhalb der Zahlen. So sind beispielsweise die Wörter im Lexikon alphabetisch geordnet.

Totalordnung

Transitivität: Aus $a\le b$ und $b\le c$ folgt $a\le c$

Totalordnungen sind direkte Verallgemeinerungen der Kleiner-Gleich-Relation auf den Zahlen. Genau wie andere binäre homogene Relationen wird die Totalordnung über ihre Eigenschaften bestimmt.

Eine Relation ist dann eine Totalordnung, wenn sie diejenigen vier Eigenschaften hat, die auch die Kleiner-Gleich-Relation für die Zahlen besitzt:

Da eine Totalordnung die direkte Verallgemeinerung der Ordnung auf der Zahlengeraden ist, welche eine „Linie“ ist, wird eine Totalordnung auch lineare Ordnung genannt.

Die Ordnungen $\le$ auf den Zahlbereichen $\mathbb{N}$, $\mathbb{Z}$ und $ℝ$ sind zwar alle Totalordnungen, aber sie unterscheiden sich auch! So hat $\mathbb{N}$ ein kleinstes Element, nämlich die $1$, aber weder $\mathbb{Z}$ noch $ℝ$ haben ein kleinstes Element. In $ℝ$ gibt es zwischen zwei verschiedenen Elementen $x\ne y$ mit $x\le y$ immer ein weiteres Element $z$ mit $z\ne x$, $z\ne y$ und $x\le z\le y$. Das gilt für $\mathbb{N}$ und $\mathbb{Z}$ nicht.

Wie bereits gesagt, ist auch die Umkehrung $\ge$ einer Totalordnung $\le$ wieder eine Totalordnung:

Während $\ge$ ebenfalls eine Totalordnung ist, ist das bei $<$ und $>$ nicht der Fall. Diese beiden Relationen sind strikte Totalordnungen:

Strikte Totalordnung

Analog zur Totalordnung, soll auch die Relation $<$ die Kleiner-Relation der reellen Zahlen verallgemeinern. Wenn eine Relation das tut, nennt man sie strikte Totalordnung. Welche Eigenschaften muss nun aber $<$ besitzen, um als strikte Totalordnung zu gelten?

Aus dem Abschnitt zu den Eigenschaften binärer Relationen wissen wir, dass eine binäre Relation genau dann trichotom ist, wenn sie gleichzeitig irreflexiv, asymmetrisch, konnex und antisymmetrisch ist. Dementsprechend müssen wir von einer binären Relation nur die Trichotomie und die Transitivität fordern und es folgt dann bereits, dass diese Relation genau dieselben Eigenschaften wie die Echt-Kleiner-Relation besitzt. Deswegen wählen wir die Trichotomie und die Transitivität als die charakteristischen Eigenschaften einer strikten Totalordnung:

Das Symbol $\dot{\vee }$ ist dabei die Kontravalenz, also die Entweder-Oder-Verknüpfung zwischen Aussagen. Wir zeigen nun, dass die mit Hilfe einer Totalordnung $\le$ definierte Relation $<$ eine strikte Totalordnung ist.

Sobald eine strikte Totalordnung $<$ definiert wurde, können ähnlich wie bei der Totalordnung weitere Ordnungsrelationen auf $<$ zurückgeführt werden:

Die Beweis, dass $\ge$ eine Totalordnung ist verläuft analog.

Zusammenhang von strikter Totalordnung zur Totalordnung

In den vorherigen beiden Abschnitten haben wir dargelegt, wie man aus einer Totalordnung und einer strikten Totalordnung einer Menge die jeweils andere Ordnung definieren kann. Es fehlt aber noch der Beweis, dass beide Wege gleichwertig sind, dass es also egal ist, welchen Weg man geht. Um dies zu zeigen, muss Zweierlei gezeigt werden:

1. Sei ${\le }_1$ eine Totalordnung, von der man die strikte Totalordnung $<$ über $x<y:\iff x{\le }_{1}y\wedge x\ne y$ bildet. Wenn man nun wieder die von $<$ induzierte Totalordnung ${\le }_2$ über $x{\le }_{2}y:\iff x<y\vee x=y$ bildet, dann müssen die beiden Relationen ${\le }_1$ und ${\le }_2$ identisch sein. Es muss also gelten $x{\le }_{2}y\iff x{\le }_{1}y$.
2. Analoges muss gelten, wenn man bei einer strikten Totalordnung ${<}_1$ beginnt und über den Zwischenschritt der von ${<}_1$ induzierten Totalordnung $\le$ die von $\le$ induzierte strikte Totalordnung ${<}_2$ bildet: $x{<}_{2}y\iff x{<}_{1}y$.

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):

Aus der Definition folgt, dass jede Totalordnung eine Halbordnung ist. Aber nicht jede Halbordnung ist eine Totalordnung.

Quasiordnung

Quasiordnungen sind sowohl Verallgemeinerungen der Halbordnung als auch der Äquivalenzrelation

Noch allgemeiner sind Quasiordnungen, auch Präordnungen genannt. Bei ihnen wird die Antisymmetrie nicht mehr verlangt. Mathe für Nicht-Freaks: Vorlage:Definition

Der Begriff der Quasiordnung verallgemeinert nicht nur den der Halbordnung, sondern zugleich auch den der Äquivalenzrelation.

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:

Entscheidungsbaum zum Nachweis von Ordnungsrelationen