Unterschied Ordnungsrelation und Äquivalenzrelation
Vorweg: das ist keine Hausaufgabe, ich muss das für die Uni verstehen und ich komme mit sämtlichen Erklärungen bis jetzt nicht weiter.
Kann mir einer vielleicht den Unterschied erklären? So mit "Äpfeln und Birnen" also für ganz Doofe? ;-)
Ich weiß nur, dass der Unterschied darin besteht, dass die Ordnungsrelation neben reflexiv und trasitiv, anti-symmetrisch sein muss und die Äquivalenzrelation symmetrisch.
Aber die Definiton verstehe ich einfach nicht, ich habe das nie in der Schule gehabt.
- Ordnungsrelation Anti-Symmetrisch:
- Wenn x R y und y R x --> x = y
- wenn (a,b) dann nicht (b,a)
Warum bedeutet das "gleich" eine anti-symmetrie? und ich versteh nicht wie man den unterschied konkret jetzt zu dem anderen feststellen kann:
- Äquivalenzrelation
- Wenn x R y --> y R x
- wenn (a,b) dann (a,b)
Und was ich auch nicht verstehe: Frage: ist x R y <--> x < y eine Ordnungsrelation? Antwort: Nein, da x < x falsch ist
Ich verstehe einfach nur Bahnhof. ;-)
3 Antworten
R ist dann eine Äquivalenzrelation über X, wenn für alle x, y, z in X:
- x R x (Reflexivität)
- x R y ==> y R x (Symmetrie)
- x R y & y R z ==> x R z (Transitivität)
Wäre so ein R auch ein Ordnungsrelation, würde gelten:
- Für alle x in X gilt: sei y=x, dann x R y (da y=x und R reflexiv ist). Es gilt x R y und daher NICHT(y R x). Also NICHT (x R x). Dies ist ein Widerspruch!
Daraus ergibt sich, dass eine Äquivalenzrelation nicht gleichzeitig eine Ordnungsrelation sein kann.
Du hast eine Menge gegeben, meinetwegen die Menge aller reellen Zahlen. Eine "Ordnungsrelation" ist - wie der Name schon sagt - eine Relation, die die Elemente dieser Menge anordnet. Eine sehr bekannte Relation ist die "kleinergleich"-Relation der reellen Zahlen. Wenn also R die Relation "≤" ist, dann bedeutet die Antisymmetrie folgendes:
Ist x ≤ y und y ≤ x, dann muss bereits x = y sein.
Das heißt übersetzt soviel wie: sind x und y zwei verschiedene Zahlen, dann kann nicht gleichzeitig x < y und x > y gelten.
Nun ist die Ordnung auf den reellen Zahlen eine ziemlich schöne, weil dort alle Zahlen miteinander vergleichbar sind. Das ist im Allgemeinen nicht gefordert. Die Axiome für eine Ordnungsrelation lauten lediglich:
x ≤ x für alle Elemente x (Reflexivität)
x ≤ y und y ≤ x --> x = y (Anti-symmetrie)
x ≤ y und y ≤ z --> x ≤ z (Transitivität).
Äquivalenzrelationen haben teilweise ähnliche Eigenschaften, erfüllen aber einen ganz anderen Zweck. Sie geben dir keine "Reihenfolge", wie die Ordnungsrelationen, sondern teilen dir deine gesamte Menge in disjunkte Teilmengen auf.
Beispiel: Die Menge aller Autos wird aufgeteilt in die Menge aller roten Autos, die Menge aller gelben Autos, die Menge aller grünen Autos, ...
Und die Relationsvorschrift für diese Zerlegung würde dann halt lauten:
x ~ y (bzw x R y) genau dann, wenn x und y dieselbe Farbe haben.
Die Symmetrie sagt dir jetzt: Wenn x und y dieselbe Farbe haben, dann haben auch y und x dieselbe Farbe. In Formeln:
x ~ y --> y ~ x.
Hier ergibt aber die Antisymmetrie (x ~ y und y ~ x --> x = y) keinen Sinn! Denn sonst wären alle Autos, die z.B. rot sind, dieselben. D.h. es gäbe höchstens ein rotes Auto, was offenbar falsch ist.
Das ist anfangs alles etwas abstrakt, aber wenn du eine Weile damit arbeitest, kommt dir das alles gar nicht mehr so schwer vor ;)
Das ist mir auch unklar. Die Formulierung ist zumindest ziemlich unsauber. Schließlich muss nach Definition (a,a) stets in der Relation vorhanden sein. Was ich mir vorstellen kann ist, dass das eine alternative Definition für die Antisymmetrie ist. Ungefähr:
Sind a und b zwei verschiedene Elemente der Menge, dann gilt:
a R b --> nicht b R A
Also eben genau das, was ich im dritten Absatz erläutert hab. Man muss halt nur fordern, dass a und b nicht gleich sind.
x R y UND y R x --> x = y
bedeutet: Wenn in einer Ordnungsrelation "xRy" die Umkehrung gilt, dann und nur dann weil in diesem `Sonderfall´ x = y sein muß. Der Pfeil liest sich: Aus der gültigen Umkehrung folgt --> x = y, x kann nur gleich y sein.
In einer Äquivalenzrelation "a~b" sind sie sowieso (!) gleich (oder "ähnlich" oder "kongruent").
Den letzten Satz versteh' ich auch nicht. Und wann x,y oder a,b benutzt wird?
(a,b) ist ein Paar (in dieser Reihenfolge!) aus der Menge mit der Ordnungsrelation. Z.B.: a < b, aber nicht umgekehrt (b,a), was b < a hieße. (Daß im Sonderfall a = b bei der Ordnungsrelation "kleinergleich" gilt, trifft nicht auf alle beliebigen x und y der Menge mit der Ordnungsrelation zu, daher auch die mögliche Schlußfolgerung darauf). In einer Äquivalenzrelation gilt: "Wenn (a,b), dann (b,a)."
Also: "Wenn das Paar (a,b) Element der Äquivalenzrelation ist, dann ist es auch das Paar (b,a)."
Ich versteh' auch nicht, warum auf Wikipedia "R" für Ordnungsrelationen benutzt wird und "~" für Äquivalenzrelationen, und hier Beispiele mit "R" für Relation, die beides sein kann .. vielleicht veraltete Schreibweise?
Danke, das macht es für mich schon verständlicher :)
Das einzige was für mich noch unklar ist, ist der Satz "wenn (a,b) dann nicht (b,a)". Bei einer Ordnungsrelation ist doch a = a und b=b. ?