Ordnungsrelationen

Eine Ordnungsrelation ist eine zweistellige Relation auf einer Menge, die reflexiv, antisymmetrisch und transitiv ist.

Motivation

Die Ordnung ist ein gängiger Begriff, mit dem wir auch im Alltag arbeiten. Vieles können wir auf irgendeine Weise ordnen – Wörter nach dem Alphabet, Schüler in der Schule nach der Größe, Waren nach dem Preis. All das beschreibt die Ordnungsrelation, die wir üblicherweise mit dem Symbol ≤ bezeichnen. Verwandte Symbole sind: <, >, ≥. Ihre Bedeutung ist offensichtlich.

Was würden wir von einer solchen Relation erwarten? Schon am Symbol ist klar, dass in einer Ordnungsrelation auch Elemente vorkommen, die gleich sind – es geht uns also darum, die Eigenschaften der Relation „kleiner oder gleich“ festzulegen. Eine solche Relation sollte daher reflexiv sein. Es muss gelten, dass a ≤ a.

Was noch? Symmetrie wird sicher nicht gelten – wenn wir nach dem Preis ordnen und das Auto billiger ist als das Brot, dann ist das Brot bestimmt nicht gleichzeitig billiger als das Auto. Was würden wir im Allgemeinen erwarten, wenn a ≤ b und zugleich b ≤ a gilt? Würde das jemals Sinn ergeben? Ja, wenn a = b gilt. Der einzige Fall, in dem die Reihenfolge der in die Relation eingesetzten Elemente keine Rolle spielt, ist der, dass die Elemente gleich sind – die Ordnung ist also antisymmetrisch.

Wenn wir schließlich wissen, dass das Auto teurer ist als das Brot und das Flugzeug noch teurer als das Auto, dann erwarten wir, dass das Flugzeug sicher teurer ist als das Brot. Das beschreibt die Transitivität.

Halbordnung

Das, was wir gerade definiert haben, ist in Wirklichkeit nur eine Halbordnung (partielle Ordnung), keine vollständige Ordnung. Warum ist sie nicht vollständig? Versuchen wir, eine Ordnung auf Mengen zu definieren. Wie könnten wir zwei Mengen vergleichen?

Wir sagen, dass die Menge A kleiner oder gleich der Menge B ist, wenn A ⊆ B, also wenn A eine Teilmenge von B ist. Das ergibt Sinn, denn wenn wir A = {1; 2} und B = {1; 2; 3} haben, könnten wir von A sagen, dass sie kleiner ist – B enthält dieselben Elemente wie A und zusätzlich noch die Zahl drei. Es gilt also zum Beispiel:

• {a; c} ≤ {a; b; c; d}
• ∅ ≤ {5; n; x}
• {x; e; s} ≤ {x; e; s}

Schwierig wird es aber, wenn wir diese Mengen vergleichen wollen: A = {a; b} und B = {a; c}. Welche von ihnen ist kleiner oder größer? Das Problem ist, dass zwar beide Mengen das Element a enthalten, das zweite Element aber jeweils verschieden ist. Keine der Mengen ist eine Teilmenge der anderen, deshalb gilt weder A ≤ B noch B ≤ A. Solche Mengen sind mit unserer Ordnung unvergleichbar.

Deshalb definieren wir eine total geordnete Menge oder auch Kette, wenn je zwei Elemente der Menge vergleichbar sind. Solche Mengen sind zum Beispiel die Zahlenmengen mit der gewöhnlichen Ordnung. Für je zwei reelle Zahlen a, b kannst du entscheiden, ob a ≤ b oder b ≤ a gilt.

Beispiele aus dem Alltag

Ein Beispiel, bei dem es sich lohnt, nicht zu vergleichen, wäre die Ordnung nach Schönheit; die Relation < würde dann „hässlicher sein“ bedeuten. Vielleicht sollten wir es lieber umgekehrt definieren, nämlich > als „schöner sein“, um korrekter zu sein :-). Es ergibt wohl Sinn, zwei Frauen miteinander zu vergleichen, zum Beispiel „Anna“ < „Lena“ in dem Sinn, dass Lena schöner ist als Anna. Oder zwei Männer: „Max“ < „Tim“ in dem Sinn, dass Tim schöner ist als Max.

Das Problem ist, dass wir die Schönheit eines Mannes und einer Frau wohl kaum vergleichen können. Ist Lena oder Tim schöner? Ist Anna oder Max hässlicher? Lieber nicht näher untersuchen …

Wenn wir uns im letzten Beispiel zum Beispiel nur auf Frauen beschränken, können wir sagen, dass wir eine total geordnete Menge haben, weil wir die Schönheit aller Frauen vergleichen können.

Minimales und maximales Element, kleinstes und größtes Element

Wenn wir eine geordnete Menge M haben, nennen wir ein Element min ∈ M minimal, wenn es kein x ∈ M gibt, für das x < min gilt. Wir können also kein Element finden, das kleiner wäre als das Element min.

Ein Element max ∈ M nennen wir maximal, wenn es kein x ∈ M gibt, für das x > max gilt. Wir können also kein Element finden, das größer wäre.

Die beiden vorherigen Begriffe unterscheiden sich von den Begriffen kleinstes und größtes Element.

Ein Element a ∈ M nennen wir kleinstes, wenn für alle x ∈ M gilt, dass a ≤ x. Das kleinste Element a ist also kleiner oder gleich allen anderen Elementen der Menge M.

Ein Element b ∈ M nennen wir größtes, wenn für alle x ∈ M gilt, dass b ≥ x. Das größte Element b ist größer oder gleich allen anderen Elementen der Menge M.

Was ist der Unterschied zwischen dem größten und dem maximalen Element? Es kann mehrere maximale Elemente geben, weil die Menge nicht unbedingt total geordnet sein muss. Wenn wir zum Beispiel zum Vergleich von Menschen nach ihrem Aussehen zurückkehren, können wir sagen, dass Lena die schönste Frau und Tim der schönste Mann ist. Diese beiden Personen können wir aber untereinander nicht mehr vergleichen, wir wissen nicht, ob Lena oder Tim schöner ist.

Beide Elemente sind also maximal. Wir können keine Person finden, die schöner wäre als Tim – Tim ist schöner als alle anderen Männer, und mit Frauen können wir ihn nicht vergleichen. Ähnlich für Lena – sie ist schöner als alle Frauen, und mit Männern können wir sie nicht vergleichen.

Aber keiner von beiden ist der größte, in diesem Sinn der schönste. Denn damit Tim der schönste bzw. größte wäre, müsste er schöner sein als alle Personen, also auch als alle Frauen. Wir haben aber schon gesagt, dass wir ihn mit Frauen nicht vergleichen können; deshalb kann er nicht der schönste Mensch sein, er ist, in der Terminologie der Ordnungstheorie, nur maximal.

Es ist wohl leicht einzusehen, dass ein größtes Element einer Menge zugleich auch maximal ist. Wenn das Element a größer ist als alle anderen Elemente der Menge (Definition des größten Elements), dann finden wir sicher kein Element, das noch größer wäre (Definition des maximalen Elements).

Ein Beispiel für eine Menge, die ein größtes und ein kleinstes Element hat, ist das abgeschlossene Intervall [0; 1]. Wenn wir dasselbe Intervall wählen, aber offen, hätte es weder ein größtes noch ein kleinstes Element: ]0; 1[.

Wenn wir unendlich viele minimale Elemente haben wollten, könnten wir die Ordnung R folgendermaßen definieren. Zuerst definieren wir Hilfsmengen M_x. Die Mengen haben diese Gestalt: Für alle x aus dem Intervall ]0; 1[ definieren wir die Menge M_x = {y ∣ y = x + n}, wobei n eine nichtnegative ganze Zahl ist. So erhalten wir zum Beispiel solche Mengen:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Auf jeder Menge M_x definieren wir die gewöhnliche Ordnung, die wir mit R_x bezeichnen. Am Ende vereinigen wir diese Ordnungen einfach: R = ∪ R_x. In dieser Ordnung können wir also immer nur innerhalb der ursprünglichen Ketten vergleichen. Wir können feststellen, ob 0,5 ≤ 2,5, aber nicht mehr, ob 0,5 ≤ 2,7, weil sich diese Zahlen nicht in derselben Menge M_x befanden und ihre Beziehung deshalb nicht definiert ist.

In dieser Ordnungsrelation gilt dann, dass jedes Element aus dem Intervall ]0; 1[ ein minimales Element ist.

Hasse-Diagramme

Geordnete Mengen können wir mithilfe eines Hasse-Diagramms darstellen. Das ist ein Graph, in dem die Knoten die Elemente der Menge darstellen und eine Kante zwischen den Knoten (a, b) uns sagt, dass a < b gilt und zugleich kein c existiert, für das a < c < b gilt. Zwischen den Elementen a und b liegt also kein weiteres Element. Dabei muss gelten, dass im Graphen der Knoten a tiefer liegt als der Knoten b. Beispiel eines Hasse-Diagramms:

Dieses Hasse-Diagramm stellt die geordnete Menge {A; B; C; D; E; F} dar. Dabei gilt: A < B, B < E, außerdem gilt natürlich A < E, aber zwischen diesen Knoten gibt es keine Kante, weil es den Knoten B gibt, für den A < B < E gilt. Die Elemente E und D sind unvergleichbar, weil keines über oder unter dem anderen liegt.

Obwohl Hasse-Diagramme üblicherweise so schön ausgerichtet gezeichnet werden, ist das nicht unbedingt nötig. Das vorherige Hasse-Diagramm kann auch so aussehen:

Ein weiteres Beispiel kann die Menge A = {1; 2; 3; 4; 5; 6; 10; 12; 15; 20; 30; 60} sein. Das sind die positiven Teiler der Zahl 60. Die Ordnung nach Teilbarkeit kann so dargestellt werden:

Die Ordnung nach Teilbarkeit bedeutet, dass (a, b) ∈ R genau dann, wenn a ein Teiler von b ist. Im Diagramm können wir erkennen, dass über jeder Zahl die Zahlen liegen, die sie teilt. Über der Zahl 6 liegen zum Beispiel die Zahlen 12, 30 und 60. Über der Zahl 4 liegen die Zahlen 12, 20 und 60. Usw. Dagegen hat die Zahl 3 die Zahl 10 nicht über sich, weil sie sie nicht teilt – Vorsicht, die Zahl 10 liegt optisch über der Zahl 3, aber es führt keine Linie „von unten nach oben“ zu ihr. Wenn wir uns von der Zahl 3 aus nur nach oben bewegen, können wir zu den Zahlen 15 und 6 gehen und von ihnen zur Zahl 30. Zur Zahl 10 würden wir nur gelangen, indem wir nach unten gehen, was wir nicht dürfen.