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^{\prime }$, für die gilt: $R\subseteq R^{\prime }$ und beweisen für $R^{\prime }$, 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^{\prime }$ und übernehmen zuerst alle Paare aus $R$. Jetzt fügen wir zu $R^{\prime }$ jedes Paar $(x_i,x_j)$ ein, für das $i\le 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\le j$ erzeugt dasselbe Ergebnis; selbiges gilt für die Ausschlussbedingung $\neg (x_{i}R{x}_j)$, wir würden ohne diesen dasselbe $R^{\prime }$ erhalten). Damit wäre $R^{\prime }$ konstruiert.

Nun zeigen wir zuerst, dass $R^{\prime }$ 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}^{\prime }{x}_j\wedge x_j{R}^{\prime }{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\le 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^{\prime }$ 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\wedge x_{j}R{x}_k$, aber nicht $x_{i}R{x}_k$ gilt. Bei $i\le j\le k$ brauchen wir hierbei den Fall $x_i{R}^{\prime }{x}_j,x_j{R}^{\prime }{x}_k,x_i{R}^{\prime }{x}_k$ gar nicht betrachten, für diesen Fall gilt die Transitivität sowieso (da $R^{\prime }$ hier alle Verbindungen enthält). Interessant ist also der Fall wenn $x_j{R}^{\prime }{x}_i\vee x_k{R}^{\prime }{x}_i\vee x_k{R}^{\prime }{x}_j$ gilt. Würde diese Formel wahr sein (exemplarisch ist dies hier für $x_j{R}^{\prime }{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\le j$ auch dann auch $x_i{R}^{\prime }{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\ne j$ gibt…), wir haben somit wieder einen Widerspruch zur Aussage.

Da wir nun all diese Eigenschaften bewiesen haben, muss $R^{\prime }$ eine Totalordnung mit $R\subseteq R^{\prime }$ (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^{\prime }$ immer existieren muss, gezeigt.