Aufgaben zum Thema Ordnungsrelationen

1
Was für partielle Ordnungen und was für totale Ordnungen gibt es auf zweielementigen Mengen ${x, y}$ ?

Für diese Aufgabe benötigst Du folgendes Grundwissen: Ordnungsrelationen
Fangen wir mit den Partialordnungen an:
Generell muss diese reflexiv sein, daher müssen $(x, x)$ und $(y, y)$ in unserer Relation sein. Die Antisymmetrie ist dabei auch gegeben, die Transitivität ebenfalls. Zusätzlich können wir, ohne Verletzung der gegebenen Bedingungen noch entweder $(x, y)$ oder $(y, x)$ zu der Relation hinzufügen (aber nicht beide, da dies die Antisymmetrie verletzen würde). Also haben wir:
$R_{1} = {(x, x), (y, y)}$
$R_{2} = {(x, x), (y, y), (x, y)}$
$R_{3} = {(x, x), (y, y), (y, x)}$
Für die Totalordnung muss nun bekanntlich noch die Konnexität gegeben sein (also entweder $(x, y)$ oder $(x, y)$ müssen in der Relation vorhanden sein), daher sind $R_{2}$ und $R_{3}$ ebenfalls eine Totalordnung.
Wir haben dabei alle möglichen Ordnungen betrachtet: Da $(x, x)$ und $(y, y)$ zwingend erforderlich sind und es auf eine 2-elementige Grundmenge maximal $2^{n^{2}}$ Relationen (für $n = 2$ sind das $16$ Möglichkeiten) gibt, haben wir durch unsere Einschränkung nur $2^{n^{2} - 2} = 4$ eigentliche Möglichkeiten, die wir alle durchprobieren konnten.
2
Führe das im Beweis verwendete Sortierverfahren für die Menge $A = {d, b, c, a, f, e}$ mit der alphabetischen Sortierung durch. Verwende als Pivotelement $z$ immer das vorderste Element (am Anfang also $d$ ) und lasse die Reihenfolge der Elemente in $A_{1}$ und $A_{3}$ so, wie sie in $A$ waren (also nicht beim Zerlegen aus Versehen sortieren)!

Für diese Aufgabe benötigst Du folgendes Grundwissen: Ordnungsrelation
Wir sortieren $A = {d, b, c, a, f, e}$ mit Quicksort:
Menge $A$
Wir wählen $d$ als Pivot.
$A_{1} = {b, c, a}$
$A_{2} = {d}$
$A_{3} = {f, e}$
Bevor wir $A$ wieder zusammenfügen können, müssen wir die Teilmengen betrachten:
Teilmenge $A_{1}$
Wir wählen $b$ als Pivot.
$A_{11} = {a}$
$A_{12} = {b}$
$A_{13} = {c}$
$A_{1} = A_{11} \cup A_{12} \cup A_{13} = {a, b, c}$
Außerdem: $x_{1,1} : = a, x_{1,2} : = b, x_{1,3} : = c$
Teilmenge $A_{3}$
Wir wählen $f$ als Pivot.
$A_{31} = {e}$
$A_{32} = {f}$
$A_{33} = \emptyset$
$A_{3} = A_{31} \cup A_{32} \cup A_{33} = {e, f}$
Außerdem: $x_{3,1} : = e, x_{3,2} : = f$
Zusammenfügen von $A$
$A = A_{1} \cup A_{2} \cup A_{3} = {a, b, c} \cup {d} \cup {e, f} = {a, b, c, d, e, f}$
Mit: $x_{1} : = x_{1,1} = a, x_{2} : = x_{1,2} = b, x_{3} : = x_{1,3} = c, x_{4} : = d, x_{5} : = x_{3,1} = e, x_{6} : = x_{3,2} = f$
$A$ ist nun sortiert.
3
Wenn man für eine endliche Menge $A$ mit $n = | A |$ Elementen nur eine partielle Ordnung hat, funktioniert das Sortieren nicht. (Warum nicht?)
Es gibt aber einen entsprechenden Satz, der besagt, dass man $A$ mit seiner partiellen Ordnung topologisch sortieren kann, d.h. es gibt immer (mindestens) eine Nummerierung $A = {x_{1}, x_{2}, \dots, x_{n}}$ , für die gilt:
$\forall i, j \in {1, \dots, n} : x_{i} R x_{j} \Rightarrow i \leq j$ .
Beweise mithilfe dieses Satzes folgende Aussage: Zu jeder partiellen Ordnung $R$ auf einer endlichen Menge $A$ gibt es eine totale Ordnung $R^{'}$ mit $R \subseteq R^{'}$ . (In Worten: Jede partielle Ordnung auf einer endlichen Menge kann ich "durch Hinzufügen von Pfeilen"' zu einer totalen Ordnung ausbauen.)

Für diese Aufgabe benötigst Du folgendes Grundwissen: Ordnungsrelation
Um nochmal kurz die Ausgangsbedingungen zusammenzufassen:
Wir haben eine partielle Ordnung $R$ gegeben. Nach Definition gilt für diese die Reflexivität, Antisymmetrie und Transitivität. Nun konstruieren wir uns mithilfe der ebenfalls gegebenen topologischen Sortierung eine Totalordnung $R^{'}$ , für die gilt: $R \subseteq R^{'}$ und beweisen für $R^{'}$ , dass sie reflexiv, antisymmetrisch, transitiv und konnex ist. Die Grundmenge bleibt dabei natürlich gleich.
Fangen wir also an und sortieren $R$ topologisch. Da $R$ eine partielle Ordnung ist, muss es eine entsprechende topologische Sortierung geben. Nun beginnen wir mit der Konstruktion von $R^{'}$ und übernehmen zuerst alle Paare aus $R$ . Jetzt fügen wir zu $R^{'}$ jedes Paar $(x_{i}, x_{j})$ ein, für das $i \leq j$ und nicht $x_{i} R x_{j}$ gilt (eigentlich ist nur der Vergleich $i < j$ nötig, da die Reflexivität ja bereits durch die Übernahme der Verbindungen aus $R$ gegeben ist… Aber $i \leq j$ erzeugt dasselbe Ergebnis; selbiges gilt für die Ausschlussbedingung $\neg (x_{i} R x_{j})$ , wir würden ohne diesen dasselbe $R^{'}$ erhalten). Damit wäre $R^{'}$ konstruiert.
Nun zeigen wir zuerst, dass $R^{'}$ reflexiv ist: Dies ist recht offensichtlich, da die Grundmenge dieselbe geblieben ist, $R$ bereits reflexiv war und die Reflexivität nicht durch das Hinzufügen von Paaren zu einer Relation zerstört werden kann.
Machen wir weiter mit der Konnexität. Diese gilt nun auch, da die Nummerierung der Elemente eindeutig ist. Da wir zwischen jedem möglichen Nummernpaar eine Verbindung eingefügt haben, gilt auch die Konnexität.
Kommen wir nun zu den etwas interessanteren Fällen und betrachten die Antisymmetrie: Diese beweisen wir indirekt und nehmen an, dass es ein $x_{i}, x_{j}$ gibt, für das die Bedingung der Antisymmetrie nicht gilt (also $x_{i} R^{'} x_{j} \land x_{j} R^{'} x_{i} \Rightarrow x_{i} = x_{j}$ falsch ist). Betrachten wir nochmal unseren Konstruktionsvorgang: Wir fügen maximal eine Verbindung in eine Richtung ein, sodass $i \leq j$ . Daher muss die Verbindung in die Gegenrichtung bereits in $R$ gewesen sein. Dann aber wiederum wären die $x_{i}$ und $x_{j}$ in der topologischen Sortierung vertauscht gewesen, was aber dazu geführt hätte, dass wir keine neue Verbindung bei der Konstruktion von $R^{'}$ hinzugefügt hätten. Damit ist die Bedingung für die Antisymmetrie nicht erfüllbar und wir haben einen Widerspruch zur Annahme.
Bleibt noch die Transitivität, die wir wieder indirekt beweisen: Wir nehmen an, dass es ein Tripel $x_{i}, x_{j}, x_{k}$ gibt, für das $x_{i} R x_{j} \land x_{j} R x_{k}$ , aber nicht $x_{i} R x_{k}$ gilt. Bei $i \leq j \leq k$ brauchen wir hierbei den Fall $x_{i} R^{'} x_{j}, x_{j} R^{'} x_{k}, x_{i} R^{'} x_{k}$ gar nicht betrachten, für diesen Fall gilt die Transitivität sowieso (da $R^{'}$ hier alle Verbindungen enthält). Interessant ist also der Fall wenn $x_{j} R^{'} x_{i} \lor x_{k} R^{'} x_{i} \lor x_{k} R^{'} x_{j}$ gilt. Würde diese Formel wahr sein (exemplarisch ist dies hier für $x_{j} R^{'} x_{i}$ gezeigt, für die anderen Paare $i, k$ und $j, k$ lässt sich der Fall analog beweisen), so gilt aufgrund unserer Konstruktion und $i \leq j$ auch dann auch $x_{i} R^{'} x_{j}$ , da wir dieses Paar bei der Konstruktion eingefügt haben oder es schon in $R$ vorhanden war. Die Existenz der Verbindung in beide Richtungen verletzt aber die bereits bewiesene Antisymmetrie (da es auch Fälle mit $i \neq j$ gibt…), wir haben somit wieder einen Widerspruch zur Aussage.
Da wir nun all diese Eigenschaften bewiesen haben, muss $R^{'}$ eine Totalordnung mit $R \subseteq R^{'}$ (da wir bei der Konstruktion erst die Paare von $R$ übernommen und dann weitere hinzugefügt haben). Damit ist die Aussage, dass so ein $R^{'}$ immer existieren muss, gezeigt.

Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das?