Relationen, Konzept der totalen und partiellen Ordnung verstehen?

Du darfst nicht eine Menge mit einer Relation auf dieser Menge verwechseln: "Wäre also eine Relation auf den natürlichen Zahlen, egal wie sie definiert ist, nur dann eine totale Ordnung, wenn sie die gesamte Menge der natürlichen Zahlen umfasst?" ist daher keine sinnvolle Frage. Eine Relation auf der Menge N der natürlichen Zahlen "umfasst nicht N", sondern ist eine Menge von Paaren natürlicher Zahlen.

Ein gutes Beispiel ist die Relation "teilt" auf N; sie besteht genau aus den Paaren (a,b) (mit a,b in N), bei denen b ein Vielfaches von a ist; also z.B. (3,12), (5,100), (2,2), (2,4) ... - aber nicht z.B. (12,4), denn 4 ist kein Vielfaches von 12. Weder (5,9) noch (9,5) gehört zu der Relation, weil weder 9 ein Vielfaches von 5 noch 5 ein Vielfaches von 9 ist. Man sagt in solchen Fällen: 5 und 9 sind bezüglich der Relation unvergleichbar. Als Symbol für die Relation "teilt" ist üblich: | . Statt zu sagen, dass ein Paar (a,b) ein Element von | ist, sagen wir: "a teilt b" und schreiben dafür: a|b.

(Allgemein benutzt man bei einer Relation R häufig die Schreibweise "aRb" statt zu sagen: "(a,b) ist Element von R".)

Bezüglich | tritt offensichtlich ganz oft der Fall ein, dass zwei Zahlen a, b unvergleichbar sind.

Es gibt aber Relationen, bei denen das nie passiert: Ein sehr wichtiges Beispiel dieser Art ist "kleiner oder gleich" (geschrieben: <=). Denn bei zwei natürlichen Zahlen a,b gilt stets a <= b oder b <= a. Anders gesagt: Je zwei natürliche Zahlen sind bezüglich <= vergleichbar. (Es kann sogar beides gelten: a <= b und b <= a, und zwar ist das genau dann der Fall, wenn a = b gilt.)

So kommt es zu einer wichtigen Definition: Eine Ordnungsrelation heißt totale Ordnung, wenn bezüglich ihr je zwei Elemente der betrachteten Menge vergleichbar sind. (Der Begriff der partiellen Ordnung ist allgemeiner, schließt aber totale Ordnungen nicht aus! Es muss bei einer partiellen Ordnung nicht unbedingt zwei unvergleichbare Elemente geben.)

Wenn dir der Unterschied zwischen | und <= völlig klar ist, ist das schon ein großer Schritt vorwärts. Ein weiteres instruktives Beispiel: Betrachte die Menge {1,2,3} und bilde ihre Potenzmenge, also die Menge, deren Elemente die Teilmengen von {1,2,3} sind. Dann sei R die Menge aller Paare (A,B) solcher Teilmengen, bei denen A eine Teilmenge von B ist.

Zum Beispiel gehört ({1},{1,3}) zu R, ({2},{1,3}) jedoch nicht, auch ({1,3},{2}) nicht. Also sind {2} und {1,3} unvergleichbar bezüglich R. Die Relation R ist reflexiv, antisymmetrisch und transitiv, aber keine vollständige Ordnung.

Hier

https://de.wikipedia.org/wiki/Ordnungsrelation

wird dies meiner Ansicht nach gut erklärt. Ein Beispiel für eine nicht totale Ordnung ist die Teilmengenbeziehung.