6.6 Ordnungsrelationen und Hasse-Diagramme

Was ist eine Ordnungsrelation?

Zahlen lassen sich mit \(\leq\) vergleichen. Bei Mengen verwenden wir \(\subseteq\), bei Arbeitsabläufen eine Vorgängerbeziehung. Die gemeinsamen Regeln dieser Beziehungen führen zum Ordnungsbegriff.

Definition 6.17 (Ordnungsrelation). Eine Relation \(T\) auf \(M\) heißt Ordnungsrelation (kurz Ordnung), wenn sie reflexiv, antisymmetrisch und transitiv ist. Wir schreiben häufig \(x\preceq y\) statt \((x,y)\in T\).

Sie heißt vollständige (oder totale) Ordnungsrelation, wenn zusätzlich \[ \forall x,y\in M:\ x\preceq y\ \lor\ y\preceq x. \tag{6.3}\]

Ohne die Zusatzbedingung (6.3) dürfen Elemente unvergleichbar sein.

Eine (nicht notwendigerweise vollständige) Ordnungsrelation wird auch Halbordnung oder partielle Ordnung genannt. In der Vorlesung verwenden wir die Begriffe aus den Definitionen: Ordnung und vollständige (oder totale) Ordnung sowie ihre strikten Varianten (siehe Definition der strikten Ordnungsrelation).

Vollständigkeit einer Ordnung meint Vergleichbarkeit und ist nicht mit der Links- oder Rechtsvollständigkeit einer beliebigen Relation zu verwechseln.

Strikte Ordnungen

Die Beziehungen \(<\) und \(\subsetneq\) schließen Selbstbeziehungen aus. Dafür passt eine zweite, gleichwertig nutzbare Form des Ordnungsbegriffs.

Definition 6.18 (Strikte Ordnungsrelation). Eine Relation \(S\) auf \(M\) heißt strikte Ordnungsrelation (kurz strikte Ordnung), wenn sie asymmetrisch und transitiv ist. Wir schreiben häufig \(x\prec y\).

Sie heißt vollständige (oder totale) strikte Ordnungsrelation, wenn für alle verschiedenen \(x,y\in M\) gilt: \(x\prec y\) oder \(y\prec x\).

Eine nichtstrikte Ordnung und ihre strikte Variante unterscheiden sich nur in den Diagonalpaaren.

Satz 6.7 (Übergang zwischen beiden Ordnungsformen). Ist \(T\) eine Ordnung auf \(M\), so ist \(S=T\setminus I_M\) eine strikte Ordnung. Ist umgekehrt \(S\) eine strikte Ordnung, so ist \(T=S\cup I_M\) eine Ordnung.

Diese Zuordnungen machen einander rückgängig; Vollständigkeit bleibt erhalten.

Antisymmetrie ist dabei die Bedingung, die nach dem Entfernen der Diagonale Asymmetrie sicherstellt.

Beweis

Beweis. Wir verwenden \(I_M=\{(x,x)\mid x\in M\}\) und schreiben alle Beziehungen als Zugehörigkeit von Paaren zu einer Relation.

1. Von einer Ordnung zu einer strikten Ordnung.

Voraussetzung: \(T\) ist eine Ordnung auf \(M\), also reflexiv, antisymmetrisch und transitiv. Wir setzen \(S=T\setminus I_M\).

Zu zeigen: \(S\) ist asymmetrisch und transitiv.

  • Asymmetrie: Sei \((x,y)\in S\). Dann gilt \((x,y)\in T\) und \(x\neq y\). Angenommen, auch \((y,x)\in S\). Dann lägen beide Paare in \(T\), und aus der Antisymmetrie von \(T\) folgte \(x=y\). Das ist ein Widerspruch. Daher ist \((y,x)\notin S\); also ist \(S\) asymmetrisch.
  • Transitivität: Seien \((x,y)\in S\) und \((y,z)\in S\). Beide Paare liegen in \(T\), sodass die Transitivität von \(T\) zunächst \((x,z)\in T\) liefert. Es bleibt \(x\neq z\) zu zeigen. Wäre \(x=z\), so lägen \((x,y)\) und \((y,x)\) in \(T\). Aus der Antisymmetrie von \(T\) folgte \(x=y\), im Widerspruch zu \((x,y)\in S\). Also gilt \(x\neq z\) und damit \((x,z)\in T\setminus I_M=S\). Somit ist \(S\) transitiv.

Damit ist \(S\) eine strikte Ordnung auf \(M\).

2. Von einer strikten Ordnung zu einer Ordnung.

Voraussetzung: \(S\) ist eine strikte Ordnung auf \(M\), also asymmetrisch und transitiv. Wir setzen \(T=S\cup I_M\).

Zu zeigen: \(T\) ist reflexiv, antisymmetrisch und transitiv.

  • Reflexivität: Für jedes \(x\in M\) gilt \((x,x)\in I_M\subseteq T\). Also ist \(T\) reflexiv.
  • Antisymmetrie: Seien \((x,y)\in T\) und \((y,x)\in T\). Angenommen, \(x\neq y\). Dann gehört keines der beiden Paare zu \(I_M\); beide müssten also in \(S\) liegen. Das widerspricht der Asymmetrie von \(S\). Daher gilt \(x=y\), und \(T\) ist antisymmetrisch.
  • Transitivität: Seien \((x,y)\in T\) und \((y,z)\in T\). Ist \(x=y\), so ist \((x,z)=(y,z)\in T\). Ist \(y=z\), so ist \((x,z)=(x,y)\in T\). Im verbleibenden Fall \(x\neq y\) und \(y\neq z\) liegen beide Ausgangspaare in \(S\). Dessen Transitivität liefert \((x,z)\in S\subseteq T\). In allen Fällen gilt also \((x,z)\in T\); somit ist \(T\) transitiv.

Damit ist \(T\) eine Ordnung auf \(M\).

3. Die Zuordnungen machen einander rückgängig und erhalten Vollständigkeit.

Für jede Ordnung \(T\) gilt wegen ihrer Reflexivität \(I_M\subseteq T\), also \[ (T\setminus I_M)\cup I_M=T. \] Für jede strikte Ordnung \(S\) gilt wegen ihrer Asymmetrie \(S\cap I_M=\varnothing\): Ein Paar \((x,x)\in S\) würde unmittelbar der Asymmetrie widersprechen. Daher gilt \[ (S\cup I_M)\setminus I_M=S. \] Damit sind die beiden Zuordnungen zueinander invers.

Für verschiedene \(x,y\in M\) bleiben die Paare \((x,y)\) und \((y,x)\) beim Entfernen oder Hinzufügen von \(I_M\) unverändert. Daher enthält \(T\) genau dann für jedes Paar verschiedener Elemente mindestens eine der beiden Richtungen, wenn \(S\) dies tut. Für gleiche Elemente enthält \(T\) ohnehin alle Diagonalpaare. Also ist \(T\) genau dann vollständig, wenn \(S\) vollständig ist. \(\square\)

Teilbarkeit ordnet positive ganze Zahlen nach einem anderen Kriterium als ihrer Größe.

Beispiel: Teilbarkeit als Ordnung

Auf \(M=\{1,2,3,6,12\}\) sei \(x\preceq y\iff x\mid y\). Ist dies eine totale Ordnung?

Jede positive ganze Zahl teilt sich selbst. Aus \(x\mid y\) und \(y\mid x\) folgt für positive Zahlen \(x=y\). Aus \(x\mid y\) und \(y\mid z\) folgt \(x\mid z\). Also liegt eine Ordnung vor. Sie ist nicht total: Weder \(2\mid3\) noch \(3\mid2\) gilt. Die Einschränkung auf positive Zahlen ist wesentlich; auf \(\mathbb Z\) würden etwa \(2\mid-2\) und \(-2\mid2\) die Antisymmetrie verletzen.

Direkte Nachfolger und Überdeckungsrelation

Im vollständigen Graphen einer Ordnung sind viele Pfeile durch Transitivität bereits festgelegt. Für endliche Mengen genügt es, die unmittelbaren Schritte zu zeichnen.

Definition 6.19 (Direkter Nachfolger und Überdeckungsrelation). Sei \(T\) eine Ordnung auf \(M\). Wir schreiben \(x\preceq y\) für \((x,y)\in T\) und \(x\prec y\) für \((x,y)\in T\setminus I_M\). Die Überdeckungsrelation \(C\subseteq T\setminus I_M\) ist definiert durch \[ (a,b)\in C\iff a\prec b\ \land\ \nexists c\in M:\ a\prec c\prec b. \] Für \((a,b)\in C\) heißt \(a\) direkter Vorgänger von \(b\) und \(b\) direkter Nachfolger von \(a\).

Die Bedingung \(a\neq b\) steckt in \(a\prec b\): Schlingen sind keine Überdeckungen. „Direkt“ bezieht sich außerdem auf die festgelegte Menge \(M\); entfernt man Zwischenknoten, kann eine neue Überdeckung entstehen.

Hasse-Diagramme

Ein Hasse-Diagramm stellt die Überdeckungsrelation als Graphen dar.

Definition 6.20 (Hasse-Diagramm). Sei \(T\) eine Ordnung auf \(M\) mit Überdeckungsrelation \(C\). Ihr Hasse-Diagramm hat die Elemente von \(M\) als Knoten und genau dann eine gerichtete Kante von \(a\) nach \(b\), wenn \((a,b)\in C\).

Für endliche Mengen verwenden wir folgende Zeichnung:

  1. einen Knoten für jedes Element,
  2. eine Verbindung für jedes Paar der Überdeckungsrelation,
  3. den größeren Knoten jeweils oberhalb des kleineren.

Die Richtung von unten nach oben erlaubt es, die Pfeilspitzen wegzulassen.

Alternativ kann man von links nach rechts anordnen; die Leserichtung muss dann angegeben werden. Hier verwenden wir durchgehend „nach oben = größer“. Linienkreuzungen sind keine zusätzlichen Knoten.

Eine endliche Ordnung rekonstruieren

Die verkürzte Zeichnung verliert bei einer endlichen Ordnung keine Information.

Satz 6.8 (Rekonstruktion aus der Überdeckungsrelation). Ist \(M\) endlich, \(T\) eine Ordnung auf \(M\) und \(C\) ihre Überdeckungsrelation, so gilt \[ T=I_M\cup[C]_{\mathrm{tran}},\qquad T\setminus I_M=[C]_{\mathrm{tran}}. \]

Die Endlichkeit verhindert, dass immer weitere Zwischenknoten eingefügt werden müssen.

Beweis

Beweis. Da \(C\subseteq T\setminus I_M\) und \(T\setminus I_M\) transitiv ist, gilt \([C]_{\mathrm{tran}}\subseteq T\setminus I_M\).

Umgekehrt sei \((a,b)\in T\setminus I_M\). Liegt \((a,b)\) bereits in \(C\), so liegt es auch in \([C]_{\mathrm{tran}}\). Andernfalls gibt es nach Definition von \(C\) ein Element \(c\) mit \(a\prec c\prec b\). Wir fügen \(c\) zwischen \(a\) und \(b\) ein. Solange ein geordnetes Paar benachbarter Elemente der Kette nicht in \(C\) liegt, fügen wir zwischen diesen beiden Elementen ein weiteres Element ein. Da \(M\) endlich ist und die Kette strikt aufsteigt, endet dieses Verfahren. Dann liegt jedes geordnete Paar benachbarter Elemente in \(C\). Die entstandene Kette zeigt daher \((a,b)\in[C]_{\mathrm{tran}}\).

Damit gilt \(T\setminus I_M=[C]_{\mathrm{tran}}\). Wegen der Reflexivität von \(T\) folgt daraus \(T=I_M\cup[C]_{\mathrm{tran}}\). \(\square\)

Die Endlichkeit kann nicht ersatzlos entfallen: In \((\mathbb Q,\leq)\) liegt zwischen \(a<b\) stets \(\frac{a+b}{2}\). Daher ist \(C=\varnothing\).

Ein Hasse-Diagramm lesen

Bei der Teilbarkeitsordnung lässt sich der Unterschied zwischen Überdeckung und bloßer Vergleichbarkeit an wenigen Knoten erkennen.

Beispiel: Teilbarkeit auf fünf Zahlen

Auf \(M=\{1,2,3,6,12\}\) sind die Überdeckungen \((1,2),(1,3),(2,6),(3,6),(6,12)\). Obwohl \(1\mid12\) gilt, wird dafür keine eigene Verbindung gezeichnet.

Hasse-Diagramm der Teilbarkeit auf 1, 2, 3, 6 und 12. Unten steht 1, darüber unvergleichbar 2 und 3, darüber 6 und ganz oben 12. Verbindungen nur zwischen benachbarten Ebenen.

Größte, kleinste und maximale Elemente

In einer Ordnung kann es mehrere Elemente geben, oberhalb derer nichts mehr liegt. Das bedeutet noch nicht, dass eines größer als alle anderen ist.

Definition 6.21 (Minimum, Maximum, minimale und maximale Elemente). Sei \(A\subseteq M\) in einer geordneten Menge \((M,\preceq)\).

  • \(m\in A\) heißt das Minimum von \(A\), wenn \(m\preceq x\) für alle \(x\in A\) gilt.
  • \(m\in A\) heißt ein minimales Element von \(A\), wenn aus \(x\in A\) und \(x\preceq m\) stets \(x=m\) folgt.
  • \(m\in A\) heißt das Maximum von \(A\), wenn \(x\preceq m\) für alle \(x\in A\) gilt.
  • \(m\in A\) heißt ein maximales Element von \(A\), wenn aus \(x\in A\) und \(m\preceq x\) stets \(x=m\) folgt.

Das Minimum bezeichnen wir mit \(\min A\), das Maximum mit \(\max A\), sofern sie existieren.

Ein Maximum ist mit allen Elementen von \(A\) vergleichbar und ist das einzige maximale Element. Mehrere unvergleichbare maximale Elemente sind dagegen möglich. Jede nichtleere endliche geordnete Menge hat minimale und maximale Elemente. Bei einer totalen Ordnung sind sie zugleich Minimum und Maximum. Die entsprechende Aussage gilt nicht für beliebige unendliche Mengen.

Schranken, Infimum und Supremum

Die Schrankenbegriffe aus den reellen Zahlen verwenden nur eine Ordnung und lassen sich deshalb übertragen.

Definition 6.22 (Schranken, Infimum und Supremum in einer Ordnung). Sei \(T\) eine Ordnungsrelation auf \(M\). Wir schreiben \(x\preceq y\) für \((x,y)\in T\).

Für \(A\subseteq M\) heißt \(u\in M\) obere Schranke, wenn \(x\preceq u\) für alle \(x\in A\) gilt; \(\ell\in M\) heißt untere Schranke, wenn \(\ell\preceq x\) für alle \(x\in A\) gilt.

Das Supremum \(\sup A\) ist die kleinste obere Schranke, falls sie existiert. Das Infimum \(\inf A\) ist die größte untere Schranke, falls sie existiert.

Für eine strikte Ordnungsrelation \(S\) auf \(M\) definieren wir Schranken, Supremum und Infimum bezüglich der zugehörigen Ordnung \(T=S\cup I_M\), also nach dem Übergang zur reflexiven Hülle von \(S\).

Bemerkung. Liegt \(\sup A\) in \(A\), ist es zugleich \(\max A\); liegt \(\inf A\) in \(A\), ist es zugleich \(\min A\).

Schranken werden in der umgebenden Menge \(M\) gesucht; ein Minimum oder Maximum muss zusätzlich in \(A\) liegen. Auch wenn obere Schranken existieren, muss unter ihnen keine kleinste sein.

Im Teilbarkeitsdiagramm liegen gemeinsame obere Schranken oberhalb beider ausgewählter Knoten.

Beispiel: Schranken von zwei unvergleichbaren Zahlen

In \(M=\{1,2,3,6,12\}\) mit der Teilbarkeit sei \(A=\{2,3\}\). Bestimmen Sie Schranken, Infimum, Supremum und Extremalelemente.

Die oberen Schranken in \(M\) sind \(6,12\); davon ist bezüglich Teilbarkeit \(6\) die kleinste. Also ist \(\sup A=6\). Die einzige untere Schranke ist \(1\), daher \(\inf A=1\).

Beide liegen außerhalb von \(A\): Minimum und Maximum existieren nicht. Die Elemente \(2\) und \(3\) sind beide minimal und beide maximal in \(A\), weil sie unvergleichbar sind.

Auch die Existenz oberer Schranken allein genügt nicht: In der durch Inklusion geordneten Menge \(M=\{\{a\},\{b\},\{a,b,c\},\{a,b,d\}\}\) haben \(\{a\}\) und \(\{b\}\) zwei gemeinsame obere Schranken. Diese sind unvergleichbar, und keine kleinere gemeinsame obere Schranke gehört zu \(M\). Das Supremum existiert hier nicht.

Zusammenfassung

  • Ordnungen sind reflexiv, antisymmetrisch und transitiv; vollständige Ordnungen machen alle Elemente vergleichbar.
  • Strikte Ordnungen entstehen durch Entfernen der Diagonalpaare.
  • Hasse-Diagramme endlicher Ordnungen zeigen nur direkte Nachfolger; aufsteigende Wege liefern die weiteren Vergleiche.
  • „Maximal“ bedeutet, dass kein echt größeres Element in der betrachteten Teilmenge liegt; ein Maximum muss größer oder gleich jedem Element sein.
  • Schranken liegen in der umgebenden Menge. Infimum und Supremum können fehlen oder außerhalb der betrachteten Teilmenge liegen.