Wohldefiniertheit von Relationen zeigen und Antisymmetrie beweisen

Question

Aufgabe:

Teilbarkeit in K[X] ist mangels Antisymmetrie keine Ordnungsrelation (außer im Fall K = Z₂). Jede reflexive und transitive Relation lässt sich aber mithilfe einer geeigneten Äquivalenzrelation zu einer Ordnungsrelation machen. Und zwar so:

a) Auf einer Menge A sei eine reflexive und transitive Relation R gegeben. Zeigen Sie, dass durch
a ∼ b ⇐⇒ a R b ∧ b R a auf A eine Äquivalenzrelation erklärt wird.

b) Auf der Menge A/∼ wird die Relation R' erklärt durch [a]_∼ R' [b]_∼ ⇐⇒ a R b. Zeigen Sie, dass
R' wohldefiniert ist.

c) Zeigen Sie, dass die Relation R' eine Ordnungsrelation auf A/∼ ist.

Problem/Ansatz:

Aufgabe a) habe ich, aber bei b) und c) komme ich nicht weiter. Muss ich beim Beweis von Teilbarkeit ausgehen oder ist es egal, worauf die Relation basiert? Wenn [a]_∼ R' [b]_{∼ ,} dann ist [a]_∼ = [b]_∼ oder? Wenn ich als wären dann, wenn man als Beispiel die natürlichen Zahlen nimmt, 2 und 4 in der selben Klasse, auch wenn 4 2 nicht teilt?

Comments

Ich verstehe die Aufgabe so, dass sie allgemein bewiesen werden soll, unabhängig vom Beispiel der Teilbarkeitsrelation. Natürlich kann es helfen, das Ganze mal für Teilbarkeit durchzugehen.

Deine Bemerkung am Ende verstehe ich nicht. Warum sollten die Klassen dann übereinstimmen?

---

Ok, danke!

Ich habe Äquivalenzklassen noch nicht ganz verstanden. Wenn ich die Klassen durch Teilbarkeit einteile, wären 2 und 4 gar nicht in der selben Klasse?

---

Von Klasseneinteilung spricht man nur bei Äquivalenzrelationen, Teilbarkeit ist keine Äquivalenzrelation

---

Oh, könntest Du mir dann bitte erklären, wie genau es in Aufgabe b) zu verstehen ist? Wie kann ich hier die Wohldefiniertheit zeigen?

Answer 1

Ich vereinfache mir die Schreibarbeit ein wenig. Gegeben ist ein reflexive und transitive Relation R auf der Menge A. Dazu wird eine Relation S definiert durch

$$aSb :\iff aRb \land bRa$$

Dies ist nach a) eine Äquivalenzrelation. Ihre Klassen bezeichne ich einfach mit \([..]\). Nun wird eine Relation T auf \(A/S\) definiert durch

$$[a]T[b] :\iff aRb$$

Jetzt ist Wohldefiniertheit zu prüfen: Die Definition von T für Paare von Klassen \([a],[b]\) erfolgt ja mit Hilfe der Repräsentanten a,b. Wenn ich die Klassen aber durch andere Elemente \(a',b'\) repräsentiere, darf dies nicht zu einem anderen Ergebnis führen. Also ist zu zeigen:

$$[a]=[a'] \land [b]=[b'] \land aRb \Rightarrow a'Rb' \quad (1)$$

Nun gilt:

$$[a]=[a'] \land [b]=[b']\Rightarrow aRa' \land a'Ra \land bRb' \land b'Rb$$

Damit folgt (1):

$$a'Ra \land aRb \Rightarrow a'Rb, \quad a'Rb \land bRb' \Rightarrow a'Rb'$$

Also ist T wohlefiniert