Relationen, Konzept der totalen und partiellen Ordnung verstehen?
Nabend liebe Community,
ich tue mich etwas schwer damit, die Konzepte der partiellen und totalen Ordnung im Zusammenhang mit Relationen zu verstehen. Ich versuche mal zu erläutern, wie ich die Konzepte verstehe:
Wenn ich richtig liege, zählen sowohl die partielle als auch die totale Ordnung zu den sogenannten Ordnungsrelationen. Eine Ordnungsrelation zeichnet sich durch drei Eigenschaften aus: Reflexivität, Antisymmetrie und Transitivität.
Partielle Ordnung bedeutet, dass einige Elemente der Menge miteinander vergleichbar sind.
Totale Ordnung hingegen bedeutet, dass alle Elemente der Menge miteinander vergleichbar sind.
Doch was genau bedeutet das, wie sehen Beispiele dazu aus? Verstehe ich es richtig, dass bei einer totalen Ordnung alle Elemente der Menge zueinander in Relation stehen müssen? 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?
Vielleicht kann mir jemand erklären, wo es in meiner Erklärung hapert... :D
2 Antworten
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.
Die Definitionen sind da nicht einheitlich. Ihr habt offenbar "Ordnung" so definiert, dass kein Unterschied zu "partielle Ordnung" besteht. Das machen nicht alle (und ist auch nicht günstig...) Dann dient das Attribut "partielle" nur dazu, eine Verwechslung mit "totale Ordnung" auszuschließen. Das bloße Wort "Ordnung" führt nämlich regelmäßig zu der Rückfrage: "Was denn für eine? Partiell oder total?"
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.
Ach, die Totalität ist die Eigenschaft, die bis zur totalen Ordnung fehlt. Den Begriff kannte ich noch nicht; er beschreibt also genau das, was ich oben auch schon versucht habe, in meiner Erklärung zu beschreiben. Danke, vielleicht sollte ich mal öfter dort reinschauen! :)
Vielen Dank für die Antwort. Ich habe mir jetzt jedes Beispiel noch einmal auf Papier angeschaut und die totale Ordnung damit nun deutlich besser verstanden! Die partielle Ordnung verwirrt mich jedoch noch etwas. Wozu dient dieser Begriff denn dann? Soweit ich das verstanden habe, ist doch jede Ordnungsrelation auch gleichzeitig eine partielle Ordnung, oder? Ist es einfach ein anderer Begriff für Ordnungsrelation? Ich weise ja mit den Eigenschaften der Ordnungsrelation auch gleichzeitig schon die partielle Ordnung nach, oder?