Session Anordnung

Eine Ordnungsrelation ist eine binäre Relation auf einer Menge, die reflexiv, antisymmetrisch und transitiv ist.

Begründung

Ordnung ist ein gängiges Konzept, mit dem wir im täglichen Leben arbeiten. Wir können viele Dinge in irgendeiner Weise anordnen - Wörter nach dem Alphabet, Schüler in der Schule nach ihrer Größe, Waren nach ihrem Preis. All dies wird durch eine Ordnungsbeziehung beschrieben, die wir gewöhnlich mit dem Symbol ≤ bezeichnen. Die verwandten Symbole sind: <, >, ≥. Ihre Bedeutung ist offensichtlich.

Was würden wir von einer solchen Sitzung erwarten? Aus dem Symbol geht bereits hervor, dass es in der Ordnungssitzung Elemente geben wird, die gleich sind - es geht also darum, die Eigenschaften der Sitzung als kleiner als oder gleich zu definieren. Eine solche Sitzung sollte also reflexiv sein. Es muss wahr sein, dass a ≤ a.

Was nun? Sicherlich gilt die Symmetrie nicht - wenn wir eine Ordnung nach dem Preis haben, dann wird, wenn ein Auto billiger ist als Brot, sicherlich Brot nicht auch billiger sein als ein Auto. Was würden wir allgemein erwarten, wenn es so wäre, dass a ≤ b und gleichzeitig b ≤ a? Würde das überhaupt einen Sinn ergeben? Ja, wenn a = b gilt. Der einzige Fall, in dem die Reihenfolge der in die Sitzung eingebetteten Elemente keine Rolle spielt, ist, wenn die Elemente gleich sind - die Reihenfolge ist also antisymmetrisch.

Denn wenn wir wissen, dass ein Auto teurer ist als Brot und ein Flugzeug noch teurer als ein Auto, erwarten wir, dass das Flugzeug mit Sicherheit teurer ist als das Brot. Das ist es, was die Transitivität beschreibt.

Partielle Ordnung

Was wir soeben definiert haben, ist in Wirklichkeit nur eine Teilordnung, sie ist nicht vollständig. Warum ist sie nicht vollständig? Versuchen wir einmal, eine Ordnung für Mengen zu definieren. Auf welche Weise könnten wir zwei Mengen vergleichen?

Wir sagen, dass die Menge A kleiner oder gleich der Menge B ist, wenn A ⊆ B, d. h. wenn A eine Teilmenge von B ist. Das macht Sinn, denn wenn wir A = {1, 2} und B = {1, 2, 3} haben, dann könnten wir sagen, dass A kleiner ist - B enthält die gleichen Elemente wie A, und es enthält auch die Zahl drei. Es würde also zum Beispiel Folgendes gelten:

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

Aber das Problem ist, wenn wir diese Mengen vergleichen wollen: A = {a, b} und B = {a, c}. Welche ist kleiner oder größer? Das Problem ist, dass beide Mengen zwar das Element a enthalten, das zweite Element aber immer unterschiedlich ist. Keine der beiden Mengen ist eine Teilmenge der anderen, also trifft weder A ≤ B noch B ≤ A zu. Solche Mengen sind mit unserer Ordnung nicht vergleichbar.

Daher definieren wir eine vollständig geordnete Menge oder auch eine Zeichenkette, wenn jeweils zwei Elemente der Menge vergleichbar sind. Zum Beispiel sind numerische Mengen mit klassischer Ordnung solche Mengen. Für je zwei reelle Zahlen a, b kann man entscheiden, ob a ≤ b oder b ≤ a.

Beispiele aus dem Leben

Ein Beispiel, bei dem es sich lohnt, nicht zu vergleichen, wäre eine Ordnung nach Schönheit, so dass die Sitzung < "hässlicher sein" bedeuten würde. Vielleicht sollten wir es andersherum definieren > als "hübscher sein", um korrekter zu sein :-). Es macht wahrscheinlich Sinn, zwei Frauen miteinander zu vergleichen, zum Beispiel "Helenka Vondráčková" < "Agáta Hanychová" in dem Sinne, dass Agáta hübscher ist als Helenka. Oder zwei Männer: "Jirka Paroubek" < "Vojta Kotek" in dem Sinne, dass Kotek hübscher ist als Paroubek.

Das Problem ist, dass wir die Schönheit eines Mannes und einer Frau kaum vergleichen können. Ist Agata oder Vojta hübscher? Ist unser Nationalschatz Helen oder das sexy Gehirn Jirka hässlicher? Das möchte ich lieber nicht erforschen...

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

Das minimale und maximale Element, das kleinste und größte Element

Wenn wir eine geordnete Menge M haben, dann nennen wir das Element min ∈ M das minimale Element, wenn es kein x ∈ M gibt, das so groß ist wie x < m. Wir sind also nicht in der Lage, ein Element zu finden, das kleiner ist als das Element min.

Wir nennen ein Element max ∈ M maximal, wenn es kein x ∈ M gibt, das so groß ist wie x > max. Das heißt, wir können kein Element finden, das größer ist.

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

Wir nennen ein Element a ∈ M das kleinste, wenn für alle x ∈ M gilt, dass a ≤ x. Das heißt, das kleinste Element a ist kleiner als oder gleich allen anderen Elementen in der Menge M.

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

Was ist der Unterschied zwischen dem größten Element und dem maximalen Element? Es kann mehr als ein maximales Element geben, da die Menge nicht unbedingt vollständig geordnet ist. Um auf das Beispiel des Vergleichs von Menschen aufgrund ihres Aussehens zurückzukommen, können wir sagen, dass Carmen Electra die hübscheste Frau und Johnny Depp der hübscheste Mann ist. Aber wir sind nicht mehr in der Lage, diese beiden Personen miteinander zu vergleichen, wir wissen nicht, ob Carmen Electra oder Johnny Depp hübscher ist.

Beide Elemente sind also maximal. Wir sind nicht in der Lage, eine Person zu finden, die hübscher ist als Johnny Depp - Johnny ist hübscher als alle anderen Männer und wir können ihn nicht mit Frauen vergleichen. Ähnlich verhält es sich mit Carmen Electra - sie ist hübscher als alle Frauen und wir können sie nicht mit Männern vergleichen.

Aber keiner von beiden ist in diesem Sinne der Größte, der Hübscheste. Denn damit Johnny Depp der Hübscheste/Größte ist, müsste er hübscher sein als alle Menschen, einschließlich aller Frauen. Aber wir haben bereits festgestellt, dass wir ihn nicht mit Frauen vergleichen können, also kann er nicht die schönste Person sein, er ist nur, in der Terminologie der Ordnungstheorie, das Maximum.

Es ist wahrscheinlich leicht einzusehen, dass, wenn eine Menge ein größtes Element hat, dieses Element auch ein Maximum ist. Wenn das Element a größer ist als alle anderen Elemente der Menge (die Definition des größten Elements), dann können wir sicher kein Element finden, das noch größer ist (die Definition des maximalen Elements).

Ein Beispiel für eine Menge, die ein größtes und ein kleinstes Element hat, ist das geschlossene Intervall <0, 1>. Wenn wir dasselbe Intervall wählen, das aber offen ist, hat es weder das größte noch das kleinste Element: (0, 1).

Wenn wir unendlich viele minimale Elemente haben wollen, können wir die Ordnung von R wie folgt definieren. Zunächst definieren wir die Hilfsmengen M_x. Die Mengen haben folgende Form: Für alle x des Intervalls (0, 1) definieren wir die Menge M_x = {y | y = x + n}, wobei n eine nichtnegative ganze Zahl ist. Damit erhalten wir Mengen wie die folgenden:

$$\begin{eqnarray} M_{0{,}5}&=&\left\{0{,}5;, 1{,}5;, 2{,}5;, 3{,}5; \ldots\right\}\\ M_{0{,}7}&=&\left\{0{,}7;, 1{,}7;, 2{,}7;, 3{,}7; \ldots\right\}\\ M_{0{,}8}&=&\left\{0{,}8;, 1{,}8;, 2{,}8;, 3{,}8; \ldots\right\} \end{eqnarray}$$

Für jede Menge M_x definieren wir eine klassische Ordnung, die wir mit R_x bezeichnen. Am Ende vereinheitlichen wir diese Anordnungen einfach: R = ∪ R_x Bei dieser Anordnung können wir also immer nur innerhalb der ursprünglichen Zeichenketten vergleichen. So können wir herausfinden, ob 0,5 ≤ 2,5, aber wir können nicht mehr herausfinden, ob 0,5 ≤ 2,7, weil diese Zahlen nicht in der gleichen M_x Menge waren und wir daher ihre Beziehung nicht definiert haben.

In dieser Ordnungsbeziehung ist also jedes Element im Intervall (0, 1) ein minimales Element.

Hasse-Diagramme

Wir können geordnete Mengen mithilfe eines Hasse-Diagramms darstellen. Dabei handelt es sich um einen Graphen, in dem die Eckpunkte Elemente der Menge darstellen, und die Kante zwischen den Eckpunkten von (a, b) sagt uns, dass a < b so ist, während es kein c gibt, das so ist, dass a < c < b. Es gibt also kein weiteres Element zwischen den Elementen von a und b. Dabei muss es wahr sein, dass in dem Graphen der Knoten a niedriger ist als der Knoten b. Beispiel für ein Hasse-Diagramm:

Dieses Hasse-Diagramm zeigt die geordnete Menge {A, B, C, D, E, F}. Hier gelten A < B, B < E und natürlich A < E, aber es gibt keine Kante zwischen diesen Eckpunkten, weil es einen Eckpunkt B gibt, für den A < B < E gilt. Die Elemente E und D sind nicht vergleichbar, weil keines über oder unter dem anderen liegt.

Obwohl Hasse-Diagramme normalerweise auf diese Weise gezeichnet werden, ist dies nicht unbedingt erforderlich. Das vorangehende Hasse-Diagramm könnte so aussehen:

Ein anderes Beispiel könnte eine Menge sein: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} Sie sind natürliche Teiler einer Zahl 60. Die Ordnung nach Teilbarkeit kann wie folgt dargestellt werden:

Ordnung nach Teilbarkeit bedeutet, dass [a, b] ∈ R nur dann teilbar ist, wenn a b teilt. Aus dem Diagramm können wir ersehen, dass jede Zahl Zahlen über sich hat, die sie teilt. Zum Beispiel stehen über der Zahl 6 die Zahlen 12, 30 und 60. Über der Zahl 4 stehen die Zahlen 12, 20 und 60. usw. Umgekehrt hat die Zahl 3 nicht die Zahl 10 über sich, weil sie sie nicht teilt - beachten Sie, dass die Zahl 10 visuell über der Zahl 3 liegt, aber es gibt keine Linie, die "von unten nach oben" zu ihr führt. Wenn wir von 3 aus nur nach oben gehen, können wir zu 15 und 6 gehen und von dort aus zu 30. Wir würden nur zu 10 gelangen, wenn wir nach unten gehen, was wir nicht tun dürfen.