Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Geordnete Mengen

Inhalt

Viele Mengen im täglichen Leben sind geordnet. Nicht unbedingt linear, wie Bundesligavereine nach der Bundesligatabelle, sondern die interessanteren Ordnungen erlauben unvergleichbare Elemente. Da der Weisungsbefugte eines Weisungsbefugten meist auch weisungsbefugt ist, sind Hierarchien in Betrieben Beispiele. Für ein anderes Beispiel nennen wir einen Schüler A "besser" als Schüler B falls in allen Fächern A mindest so gut ist wie B.

Auf dieser Einführungsseite definieren wir Ordnungsrelationen bzw. geordnete Mengen, und stellen einige wichtige Definitionen vor. Endliche Ordnungen werden mittels Hasse-Diagramme dargestellt. Schließlich stellen wir den Satz von Dilworth vor, der eine wichtige und überraschende Beziehung herstellt und als Beispiel und Prototyp für eine Vielzahl ähnlicher Sätze dient.

Auf Folgeseiten werden besonders wichtige Ordnungen behandelt: Lineare Ordnungen und Wohlordnungen und speziellen Wohlordnungen, Ordinalzahlen genannt, sowie Verbände mit den noch spezielleren Booleschen Algebren, die im Endlichen Potenzmengen endlicher Mengen mit der Inklusionsbeziehung versehen sind. Außerdem stellen einige wir Fixpunktsätze vor.


Definition: Eine reflexive, antisymmetrische und transitive binäre Relation auf einer Menge M wird Ordnungsrelation genannt. Die Menge, zusammen mit der Relation heißt dann eine geordnete Menge.
Die Bezeichnungsweise ist hier sehr uneinheitlich. Oft werden geordnete Mengen auch "Halbordnungen" bzw. "Partialordnungen" genannt.

Als Relationszeichen bei geordneten Mengen verwendet man meist " ". Statt "(a,b) " schreibt man "a b". Zwei Elemente a b sind vergleichbar falls a b oder b a, und andernfalls unvergleichbar. Eine Kette ist eine Menge paarweise vergleichbarer Elemente, eine Antikette eine Menge paarweise unvergleichbarer Elemente.

Sei (M, ) eine geordnete Menge und A M.
Ein Element x M mit "a A: a x heisst obere Schranke von A (in (M, )). Genauso ist eine untere Schranke ein y M mit "a A: y a.
Gibt es ein x A (!) mit "a A: a x, so heißt x das (!) grösste Element von A. Genauso ist das kleinste Element von A (falls existent) definiert.
Hat A eine kleinste obere Schranke, so wird es Supremum von A genannt, ebenso wird die größte untere Schranke (falls existent) Infimum von A genannt.
Eine erste kleine Beobachtung, die wir später bei den verbandsgeordneten Mengen benötigen: Ist x y, so ist offensichtlich x eine untere und y eine obere Schranke der Menge {x, y}. Tatsächlich ist dann x Infimum und y Supremum dieser Menge. Ist umgekehrt etwa y Supremum der Menge {x, y} dann folgt x y.

Hat A M das Supremum a, (Infimum a') und ist b A, so hat A {b} genau dann ein Supremum (Infimum), wenn {a,b} ein Supremum (bzw. {a',b} ein Infimum) hat. Die beiden Suprema (bzw. die beiden Infima) sind dann gleich
Beweis: s sei das Supremum von {a,b}. Dann ist s obere Schranke von A {b}. Für jede weitere obere Schranke x von A {b} ist, wegen der Supremumseigenschaft von a, a x. Also ist x obere Schranke von {a,b}, und somit s x.
Sei umgekehrt t das Supremum von A {b}. Da t dann auch obere Schranke von A ist, folgt a t. Somit ist t obere Schranke von {a,b}. Jede weitere obere Schranke y von {a,b} ist obere Schranke von A {b}, folglich y t.
Der Beweis des Infimum-Falles geht analog---vertausche überall "Infimum" und "Supremum" sowie "" und "".

Ein maximales Element von (M,) ist ein x M mit der Eigenschaft, daß aus x y immer x=y folgt. Entsprechend ist ein minimales Element jedes x M mit (" y M : y x x=y).

Sind x y M, x y, und folgt aus x z y immer z = x oder z = y, so ist y oberer Nachbar von x und x unterer Nachbar von y.

Darstellung durch Hasse-Diagramme

Ordnungsrelationen auf einer endlichen Menge A lassen sich natürlich als gerichtete Graphen auf A darstellen. Dieser gerichtete Graph enthält allerdings redundante Information. Sie kann man folgendermaßen eliminieren: Zuerst ordnet man die Elemente von A so in der Ebene an, daß aus a b (a b) immer folgt, daß die y-Koordinate des Bildes von a kleiner als die y-Koordinate des Bildes von b ist (Wie?). Damit sind alle gerichteten Kanten von unten nach oben orientiert, weshalb die Pfeile durch Linien ersetzt werden können. Weiterhin ersetzen wir eine Kante von a nach b wenn es ein c a,b gibt mit a c b (also ein c "zwischen" a und b), denn dann ergibt sich die Beziehung a b transitiv aus a c b. (Mit anderen Worten: Wir zeichnen eine Kante von x nach y nur dann wenn y oberer Nachbar von x ist.)

Das so entstehende Bild wird Hasse-Diagramm der endlichen geordneten Menge genannt. Hier ist ein Beispiel (wobei im Digraphen links alle Schlingen vergessen wurden und dazugedacht werden sollten):

Kartesische Produkte

Das kartesische Produkt von geordneten Mengen (Xi,i) hat i I Xi als Grundmenge. Es gilt (xi) (yi) falls für alle Indizes i gilt xi i yi.

Es gibt noch eine zweite Möglichkeit kartesische Produkte zu ordnen, die sogenannte lexikographische Ordnung. Dazu muß die Indexmenge I allerdings wohlgeordnet sein. Wir definieren es hier nur für I = {1,2,...,n}. Dann ist (x1,x2,...,xn) <Lex (y1,y2,...,yn) falls es ein 1 t n gibt mit xt <t yt und xi = yi für alle 1 i < t.
Beispiel:

Ideale

Jede Menge M P(X) von Mengen ist bzgl. "" geordnet. Wir werden sehen, daß wir so (bis auf Isomorphie) alle geordneten Mengen erhalten. Ein Ideal (genauer "lower order ideal") ist eine Teilmenge A einer geordneten Menge (M,) mit der Eigenschaft, daß aus x a und a A immer schon x A folgt. Die primitiven Ideale sind die Mengen Mx = {y M/y x}. Man kann leicht zeigen:
Jede geordnete Menge (M,) ist zur geordneten Menge ({Mx/x M},) isomorph.

Übungsaufgabe: Es seien zwei lineare Ordnungen L1, L2, auf {a,b,c,d,e} gegeben, siehe die Hasse Diagramme rechts. Zeigen Sie, daß der Durchschnitt der Relationen L1 L2 wieder eine Ordnungsrelation ist, und zeichnen Sie das Hasse Diagramm.
b) Ist der Durchschnitt zweier Ordnungsrelationen immer wieder Ordnungsrelationen?
c) Falls ja, gibt es einen Zusammenhang zwischen den
Dilworth-Zahlen von R1, R2 und R1 R2?


Test

Welches dieser fnf Diagramme

ist kein Hasse Diagramm einer geordneten Menge?

Welches von ihnen ist Hasse Diagramm eines Verbandes?


Weiter zu Verbänden, speziellen geordneten Mengen, bei denen jede zweielementige Teilmenge ein Supremum und ein Infimum hat, oder zu linear geordneten Mengen, oder zu Fixpunktsätzen, oder zum Satz von Dilworth.
Erich Prisner
File partially translated from TEX by T TH, version 2.53.
erstellt im Februar 2000.