Warum eine Ordnung eine Ordnung ist

Fürwahr, es ist gefährlich. Erst schaue ich mir meine Lieblingsamigademos an, dann lande ich beim C64 und schließlich denke ich über Sortieralgorithmen nach.

Wenn man das vorbildlich objektorientiert angeht, wird man eine Funktion zum Vergleich zweier Daten entgegennehmen. Und da stellt sich nun natürlich die Frage, welche Bedingungen man sinnvollerweise an die Relation zwischen einem geordneten Datenpaar stellt.

Wenn man großzügig ist, und ich bin großzügig, wird man nichts weiter als eine Halbordnung verlangen.

Was eine Halbordnung ist?

Bittesehr. Eine Halbordnung ist eine Relation R zwischen den geordneten Paaren (a,b) aus einer Menge M, derart daß (a,a) in R liegt für jedes a aus M und daß, falls (a,b) in R und (b,c) in R liegen, dann auch (a,c) in R liegt.

Natürlich fängt einen sogleich die Frage an zu quälen, ob man nicht noch großzügiger sein könnte. In gewisser Weise schon, schließlich ließen sich auch zyklische Daten sortieren, wenn auch nicht eindeutig, aber das behandelte man offensichtlich besser durch einen TYPECAST, und auch wenn da jetzt jemand schreit, daß TYPECASTS nie gerechtfertigt sind, in diesem Fall sind sie es einmal, denn besser zwei TYPECASTS als eine dreistellige Relation ohne handliche Eigenschaften.

Aber vielleicht findet unser Gemüt ja auf anderem Wege Frieden.

Wozu will man denn überhaupt etwas ordnen? Angenommen, wir könnten diese Frage beantworten, dann besteht immerhin die Hoffnung, daß wir finden, daß Halbordnungen unseren Ansprüchen genügen.

Tja... jetzt muß man zwei Dinge wissen, dann stolpert man wie von selbst über die Antwort.

1. Die Beziehungen zwischen unseren Begriffen entsprechen den Beziehungen zwischen Mengen.
2. Jede endliche geordnete Menge ist isomorph zu einer Teilmenge der Potenzmenge der natürlichen Zahlen, und jede halbgeordnete Menge läßt sich durch Übergang zu ihren Äquivalenzklassen in eine geordnete Menge verwandeln.
   

(In einer geordneten Menge gilt statt (a,a) in R, daß, wenn (a,b) in R liegt, dann (b,a) nicht in R liegt. Den Rest lese man bei Belieben bei Wikipedia nach.)

Mit anderen Worten, jede endliche geordnete Menge entspricht einer Begriffshierarchie. Das kann man auch ohne weiteres beweisen und die verwendeten Begriffe konkret angeben, aber allzu sinnvoll ist es nicht, denn nicht von der Ordnung kommt die Begriffshierarchie, sondern von einer Begriffshierarchie kommt noch jede Ordnung.

Nichts anderes bedeutet es, etwas zu ordnen, als es unter eine Begriffshierarchie zu bringen, welche wir zum Zwecke des schnelleren Zugriffs auf das Geordnete gebildet haben. Eine Halbordnung entsteht dabei, wenn wir die ihr unterworfenen Gegenstände nicht durch diese Begriffshierarchie von einander unterscheiden können, wobei vorausgesetzt ist, daß eine Begriffshierarchie zu je zwei ihrer Begriffe auch deren Konjunktion enthält, eine Voraussetzung, welche in unserem Denken stets erfüllt ist.

Um das einfachste Beispiel anzugeben, wir numerieren Dinge, damit wir die Begriffe Unter-den-ersten und Unter-den-letzten anwenden können, wenn wir etwas suchen, also beispielsweise nicht in der ersten Hälfte, im dritten Viertel, nicht im fünften Achtel usw., wobei die Begriffshierarchie über den Zahlen aus den Begriffen Höchstens-Eins, Höchstens-Zwei, Höchstens-Drei usw. besteht, von welchen wir dann nach Gusto durch die logischen Operationen der Negation und Konjunktion (also durch Nicht und Und) die Begriffe ableiten, welche wir im Laufe der Suche benötigen.