1.1 Der Begriff der Ordnung von Mengen
Intuitiv ist klar, dass man die Menge von ganz bestimmten Dingen im Sinne einer zu bestimmenden Ordnungsrelation ordnen kann. Nimmt man z.B. die Menge aller Schüler in einer Klasse, so kann man sie nach dem Alter ordnen ( "älter oder gleichalt"). Es gibt dann einen/eine älteste/n (oder im Falle gleicher Geburtstage mehrere älteste) SchülerIn. Man kann die Schüler aber auch der Körpergrösse nach ordnen ("grösser oder gleichgross"). In beiden Fällen ist es möglich, die Schüler dieser Klasse im Sinne der Ordnungsrelation so in einer Reihe aufzustellen, dass links der/die "kleinste/jüngste" SchülerIn, rechts die/die "grösste/älteste" SchülerIn steht. Es ist offensichtlich, dass die beiden Reihenfolgen in unserem Beispiel im allgemeinen nicht identisch sein werden.
Aus unserem Beispiel können wir lernen, dass die Ordnung ein Relation (Beziehung) ist, in der die Elemente der Menge (die SchülerInnen der Klasse) zu einander stehen. Nun ist nicht jede Relation eine Ordnung. Die Relation "Mitglied im Schülerclub sein" ist bestimmt eine Relation im Sinne der Element-Relation, aber intuitiv sieht man, dass damit keine Ordnung gegeben wird, weil man die SchülerInnen der Klasse nicht gegenseitig damit vergleichen und "ordnen" kann.
Allgemein sagt man, dass man unter einer Teilordnung R auf einer Menge E eine binäre (zweiwertige) Relation versteht (aRb), die folgende Eigenschaften hat:
1. Für jedes Element a der Menge gilt: aRa - a steht in Relation R zu sich selbst. Diese Eigenschaft nennt man Reflexivität .
2. Für zwei beliebige Element a und b aus E gilt: Wenn aRb und bRa, dann a = b. Wenn a in Relation R zu b steht und gleichzeitig b in Relation R zu a, so sind a und b identisch. Mit anderen Worten, R ist so beschaffen, das zwei ungleiche Element a und b nicht gleichzeitig aRb und bRa erfüllen können. Diese Eigenschaft nennt man Anti-Symmetrie .
3. Für drei beliebige Element a,b und c aus E muss gelten: Wenn aRb und bRc, dann auch aRc. Wenn also a in Relation R zu b steht und gleichzeitig b zu c, so muss auch a in Relation R zu c stehen. Diese Eigenschaft nennt man Transitivität.
Beispiele für eine Teilordnung sind die "Vorgänger-Relation" oder die "Vorfahrts-Beziehung" im Strassenverkehr. Wir legen einfach fest, dass jedes Element zu sich selbst Vorganger ist, dann lassen sich die Eigenschaften ganz leicht interpretieren. Bei der Vorfahrtsbeziehung gehen wir ähnlich vor, wir legen einfach fest, dass ein stimmtes Objekt im Strassenverkehr zu sich selbst Vorfahrt hat, in dem es mit sich selbst gleichrangig ist.
Wenn nun zusätzlich gelten soll, dass für beliebige Element a und b aus E gilt, dass entweder aRb oder bRa, so nennt man die Ordnung eine vollständige Ordnung . Jede Teilordnung auf einer endlichen Menge lässt sich in eine vollständige Ordnung umwandeln. Es gibt aber Beispiele für Teilordnungen, die keine vollständige Ordnung sind (die Teilmengen-Beziehung z.B.)
Ordnen kann man u.a. auch Mengen, die aus Zahlen bestehen. Der Unterschied zu den bisherigen Beispielen besteht "nur" darin, dass wir es jetzt mit unendlichen Mengen zu tun haben. So ist es z.B. möglich die Menge der natürlichen Zahlen mit der Relation n£m zu ordnen und ein kleinstes oder Anfangselement zu bestimmen (0 oder 1), aber für die Menge der ganzen Zahlen kann man schon kein Anfangselement mehr angeben. Gleiches gilt auch für die reellen Zahlen.