Es seien R1 ,R2 ⊆ M × M zwei Äquivalenzrelationen über der Menge M

Question

ich brauche Hilfe bei folgender Aufgabe.

Es seien R₁ ,R₂ ⊆ M × M zwei Äquivalenzrelationen über der Menge M. Entscheiden Sie, ob die folgende Relation ebenfalls reflexiv, symmetrisch oder transitiv ist und ob es sich um eine Äquivalenzrelation handelt. Geben Sie zu jeder Aussage jeweils ein Beweis oder ein Gegenbeispiel an.

R₁ ∪ R₂

Ich erwarte nicht, dass mir hier jemand die ganze Lösung präsentiert aber ein, zwei Denkanstöße wären nett. Vielleicht kommen wir ja gemeinsam zu einer Lösung.

Ich weiß was eine Äquivalenzrelation und ich weiß auch was mit Reflexivität, Symmetrie und Transitivität gemeint ist, nur verwirrt mich die Vereinigung von R₁ und R₂ ein bisschen.

Comments

Vom Duplikat:

Titel: Äquivalenzrelationen reflexiv, symmetrisch oder transitiv? R1,R2 ⊆ M × M

Stichworte: äquivalenzrelation

Es seien \( \mathcal { R } _ { 1 } , \mathcal { R } _ { 2 } \subseteq M \times M \) zwei Äquivalenzrelationen über der Menge M. Entscheiden Sie, ob die folgenden Relationen ebenfalls reflexiv, symmetrisch oder transitiv sind und ob es sich um Äquivalenzrelationen handelt. Geben Sie zu jeder Aussage jeweils einen Beweis oder ein Gegenbeispiel an.

$$ \begin{array} { l } { \text { a) } \mathcal { R } _ { 1 } \cap \mathcal { R } _ { 2 } } \\ { \text { b) } \mathcal { R } _ { 1 } \cup \mathcal { R } _ { 2 } } \end{array} $$

Answer 1

Hallo MatheJu,

Dann versuche ich doch einfach mal dir Denkanstöße zu geben:

Reflexivität ist erfüllt: Nimm dir ein x aus M, dann ist (x,x) in R1 und (x,x) in R2 also auch in der Vereinigung:

Symmetrie auch: Sei (x,y) in der Vereinigung dann ist (x,y) in R1 oder in R2 (def. Vereinigung) und da diese Relationen symmetrisch sind, folgt (y,x) in R1 oder R2, also ist (y,x) auch in der Vereinigung.

Transitivität? Betrachte mal M={1,2,3} mit

R1={(1,1),(2,2),(3,3),(1,2),(2,1)}

R2={(1,1),(2,2),(3,3),(2,3),(3,2)}

Sind das Äq.rel? Wenn ja, wie sieht die Vereinigung aus? Ist diese transitiv?

Grüße

Comments

Okay danke, ich versuche mal was draus zu basteln.

---

(1) Die Reflexivität von R1 ∪ R2 folgt aus der Reflexivität von R1 und R2. Für alle x ∈ M gilt nämlich xR1x und xR2x und damit nach Definition von ∪ auch x(R1∪R2)x.

(2) Zum Nachweis der Symmetrie von R1 ∪ R2 sei für zwei beliebige aber feste x,y ∈ M angenommen, dass x(R1∪R2)y und damit sowohl xR1y als auch xR2y gilt. Da R1 und R2 als Äquivalenzrelation symmetrisch sind, folgt daraus yR1x und yR2x, also y(R1∪R2)x. R1∪R2 ist folglich symmetrisch.

(3) Zum Nachweis der Transitivität von R1∪R2 betrachten wir drei Elemente (ich nehme mal x, y, z) x, y, z ∈ M mit x(R1∪R2)y und y(R1∪R2)z. In der formalen Sprache der mathematischen Logik formuliert, gilt also (xR1y ∨ xR2y) ∨ (yR1z ∨ yR2z). Da ∨ assoziativ und kommutativ ist, folgt (xR1y ∨ yR1x) ∨ (xR2y ∨ yR2x). Da R1 und R2 als Äquivalenzrelation transitiv sind, folgt weiter xR1z ∨ xR2z oder gleichbedeutend x(R1 ∨ R2)z. R1 ∨ R2 ist also transitiv.

Ist das so richtig?

---

1 und 2 ja, 3 nicht.

Richtig: x(R1∪R2)y und y(R1∪R2)z,

Falsch: (xR1y ∨ xR2y) ∧ (yR1z ∨ yR2z)

Du musst das und auch in ein und (∧) übersetzen, nicht in ein oder (∨).

Die Umformungen und Folgerungen sind dementsprechend auch falsch.

Hast du dir mein Beispiel dazu oben nicht angeschaut?

(1,2) ist in der Vereinigung, (2,3) ist in der Vereinigung. Ist (1,3) in der Vereinigung?

---

Nein (1,3) ist nicht in der Vereinigung, dementsprechend kann es nicht transitiv sein.

Ja okay jetzt weiß ich was du meinst, ich hatte das nur überflogen. Und das ich aus einem "und" ein "oder" gemacht habe ist auch ein dummer schussel Fehler von mir, oh man.

also müsste es lauten:

(3) Zum Nachweis der Transitivität betrachten wir drei Elemente 1, 2, 3 ∈ M und R1 = {(1,1),(2,2),(3,3),(1,2),(2,1)} und R2 = {(1,1),(2,2),(3,3),(2,3),(3,2)}.

Die Vereinigung von R1 und R2 lautet {(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)}.

Da das Tupel (1,3) aus M nicht in der Vereinigung von R1 und R2 vorkommt, kann R1 ∪ R2 nicht transitiv sein.

---

Ich würde zwar nicht "zum Nachweis der Transitivität" schreiben, da du sie ja widerlegst und nicht nachweist, aber sonst sieht das doch gut aus.

---

ja stimmt, das formulier ich nochmal um.

Aber vielen lieben dank für deine Unterstützung! DANKE

---

Bitte beachtet:

∩ ... unten offen .. entspricht "und" also dem Durchschnitt

∪ ... oben offen .. entspricht "oder" also der Vereinigung

Ich glaube das wurde hier an einigen Stellen verwechselt.

---

@Van wen genau meinst du damit? Falls mich: präzisiere bitte die Stelle an der ich mich vertan habe. Dann kann ich es korrigieren.

---

Tut mir leid, ich bin soeben nochmal euren Beweis durchgegangen. Habe mich doch nur vertan, bzw. getäuscht bei Aussagen wie z.B. "Die Vereinigung von R1 und R2."

Hat alles seine Richtigkeit