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.