Aufgaben zum Thema 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:

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.

Wir sortieren $A=\{d, b, c, a, f, e\}$ mit Quicksort:

Menge $A$

Wir wählen $d$ als Pivot.

Bevor wir $A$ wieder zusammenfügen können, müssen wir die Teilmengen betrachten:

Teilmenge $A_1$

Wir wählen $b$ als Pivot.

Außerdem: $x_{1{,}1}:=a,x_{1{,}2}:=b,x_{1{,}3}:=c$

Teilmenge $A_3$

Wir wählen $f$ als Pivot.

Außerdem: $x_{3{,}1}:=e,x_{3{,}2}:=f$

Zusammenfügen von $A$

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.

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_iRx_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_iRx_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_iR'x_j\wedge x_jR'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_iRx_j\wedge x_jRx_k$, aber nicht $x_iRx_k$ gilt. Bei $i\leq j\leq k$ brauchen wir hierbei den Fall $x_iR'x_j,x_jR'x_k,x_iR'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_jR'x_i\vee x_kR'x_i\vee x_kR'x_j$ gilt. Würde diese Formel wahr sein (exemplarisch ist dies hier für $x_jR'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_iR'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.