Schnitt von Äquivalenzrelationen

16.11.2021, 09:20

Dereineda

Schnitt von Äquivalenzrelationen

Ich tu mich immer noch sehr schwer, nachdem ich eine Idee entwickelt habe diese auch umzusetzen und überhaupt aufs Papier zu bringen..

Seien R1 und R2 jeweils Äquivalenzrelationen über der nicht-leeren Menge A.
Zeige oder widerlege: R1 ∩ R2 ist auch eine Äquivalenzrelation.

Sei R1, R2 Äquivalenzrelationen

Z.Z $\begin{eqnarray*} R1\cap R2 \end{eqnarray*}$ Äquivalenzrelation

$\begin{eqnarray*} \forall a \in A: (a,a)\in R1 \land (a,a) \in R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \forall a \in A: (a,b)\in R1 \land (a,b) \in R2 \Rightarrow (b,a)\in R1 \land (b,a) \in R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \forall a,b,c \in A: \underbrace{(a,b)\in R1 \land (b,c) \in R1}_{\Rightarrow ((a,c) \in R1} \land \underbrace{(a,b)\in R2 \land (b,c) \in R2}_{\Rightarrow ((a,c) \in R2} \end{eqnarray*}$

Wenn ich dann aber als nächstes hinschreibe:

Dann gilt auch $\begin{eqnarray*} \forall a \in A: (a,a) \in R1 \cap R2 \end{eqnarray*}$ etc pp, habe ich den Eindruck dass dies nicht so gedacht ist..

16.11.2021, 11:20

Elvis

Auf diesen Beitrag antworten »

Doch, genau so ist es gedacht, denn das ist vollkommen richtig. Für die Symmetrie musst du für alle a,b in A schreiben.

16.11.2021, 11:23

URL

Auf diesen Beitrag antworten »

RE: Schnitt von Äquivalenzrelationen
Aus meiner Sicht hast du drei Behauptungen aufgeschrieben aber noch nichts gezeigt.
Du musst schon begründen, warum die Reflexivität $\begin{eqnarray*} \forall a \in A: (a,a)\in R1 \land (a,a) \in R2 \end{eqnarray*}$ gilt.
Das geht etwa so: Für beliebiges $\begin{eqnarray*} a\in A \end{eqnarray*}$ ist $\begin{eqnarray*} (a,a)\in R1 \end{eqnarray*}$ , weil R1 nach Voraussetzung reflexiv ist. Ebenso gilt $\begin{eqnarray*} (a,a)\in R2 \end{eqnarray*}$ , weil R2 nach Voraussetzung reflexiv ist. Damit ist $\begin{eqnarray*} (a,a)\in R1\cap R2 \end{eqnarray*}$ .

Für die Symmetrie ganz ähnlich. Wenn $\begin{eqnarray*} (a,b)\in R1\cap R2 \end{eqnarray*}$ , dann ist erst recht $\begin{eqnarray*} (a,b)\in R1 \end{eqnarray*}$ . Wegen der vorausgesetzten Symmetrie von R1 ist dann auch $\begin{eqnarray*} (b,a)\in R1 \end{eqnarray*}$ .
Kannst du den Beweis jetzt abschließen?

16.11.2021, 18:01

Dereineda

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Doch, genau so ist es gedacht, denn das ist vollkommen richtig. Für die Symmetrie musst du für alle a,b in A schreiben.

Also wäre das schon komplett? Ist das wirklich so simpel?

Sei R1, R2 Äquivalenzrelationen

Z.Z $\begin{eqnarray*} R1\cap R2 \end{eqnarray*}$ Äquivalenzrelation

$\begin{eqnarray*} \forall a \in A: (a,a)\in R1 \land (a,a) \in R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \forall a,b \in A: (a,b)\in R1 \land (a,b) \in R2 \Rightarrow (b,a)\in R1 \land (b,a) \in R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \forall a,b,c \in A: \underbrace{(a,b)\in R1 \land (b,c) \in R1}_{\Rightarrow ((a,c) \in R1} \land \underbrace{(a,b)\in R2 \land (b,c) \in R2}_{\Rightarrow ((a,c) \in R2} \end{eqnarray*}$

Dann gilt auch:
$\begin{eqnarray*} \forall a \in A: (a,a) \in R1 \cap R2 \land \end{eqnarray*}$

Sorry falls das alles kein Sinn macht, ich tu mich mit der Notation/führung noch echt schwer.
$\begin{eqnarray*} \forall a,b \in A: (a,b)\in R1 \cap R2 \Rightarrow (b,a)\in R1 \cap R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \forall a,b,c \in A: (a,b)\in R1\cap R2 \land (b,c) \in R1\cap R2 \Rightarrow (a,c) \in R1\cap R2 \end{eqnarray*}$

Somit ist auch $\begin{eqnarray*} R1\cap R2 \end{eqnarray*}$ eine Äquivalenzrelation.

Zitat:

Original von URL
Aus meiner Sicht hast du drei Behauptungen aufgeschrieben aber noch nichts gezeigt.
Du musst schon begründen, warum die Reflexivität $\begin{eqnarray*} \forall a \in A: (a,a)\in R1 \land (a,a) \in R2 \end{eqnarray*}$ gilt.
Das geht etwa so: Für beliebiges $\begin{eqnarray*} a\in A \end{eqnarray*}$ ist $\begin{eqnarray*} (a,a)\in R1 \end{eqnarray*}$ , weil R1 nach Voraussetzung reflexiv ist. Ebenso gilt $\begin{eqnarray*} (a,a)\in R2 \end{eqnarray*}$ , weil R2 nach Voraussetzung reflexiv ist. Damit ist $\begin{eqnarray*} (a,a)\in R1\cap R2 \end{eqnarray*}$ .

Für die Symmetrie ganz ähnlich. Wenn $\begin{eqnarray*} (a,b)\in R1\cap R2 \end{eqnarray*}$ , dann ist erst recht $\begin{eqnarray*} (a,b)\in R1 \end{eqnarray*}$ . Wegen der vorausgesetzten Symmetrie von R1 ist dann auch $\begin{eqnarray*} (b,a)\in R1 \end{eqnarray*}$ .
Kannst du den Beweis jetzt abschließen?

Das sind ja die Definitionen für Reflexivität, Symmetrie und transivität. Die sind ja gegeben da der Aufgabentext besagt dass R, S jeweils Äquivalenzrelationen sind. Das ist doch schon die Begründung?

Oder würdest du es eher in dieser Form aufschreiben:

$\begin{eqnarray*} R1\cap R2 \end{eqnarray*}$ ist eine Äquivalenzrelation
gdw. $\begin{eqnarray*} (a,a) \in R1 \cap R2 \land \end{eqnarray*}$
$\begin{eqnarray*} (a,b)\in R1 \cap R2 \Rightarrow (b,a)\in R1 \cap R2 \land \end{eqnarray*}$
$\begin{eqnarray*} (a,b)\in R1\cap R2 \land (b,c) \in R1\cap R2 \Rightarrow (a,c) \in R1\cap R2 \end{eqnarray*}$ [Def. $\begin{eqnarray*} \cap \end{eqnarray*}$ ]
gdw $\begin{eqnarray*} (a,a)\in R1 \land (a,a) \in R2 \land \end{eqnarray*}$
$\begin{eqnarray*} (a,b)\in R1 \land (a,b) \in R2 \Rightarrow (b,a)\in R1 \land (b,a) \in R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \underbrace{(a,b)\in R1 \land (b,c) \in R1}_{\Rightarrow ((a,c) \in R1} \land \underbrace{(a,b)\in R2 \land (b,c) \in R2}_{\Rightarrow ((a,c) \in R2} \end{eqnarray*}$ [R1 und R2 sind Äquivalenzrelationen]

Oder als dritte Variante, mit deiner Notation für transivität noch:
Wenn $\begin{eqnarray*} (a,b)\in R1 \cap R2 \land (b,c)\in R1 \cap R2, \rightarrow (a,c)\in R1 \cap R2 \end{eqnarray*}$
Dann gilt $\begin{eqnarray*} (a,c) \in R1 und (a,c) \in R2[Wegen der vorausgesetzten transivität] \end{eqnarray*}$
somit gilt auch $\begin{eqnarray*} (a,c) \in R1\cap R2 \end{eqnarray*}$

16.11.2021, 18:17

URL

Auf diesen Beitrag antworten »

Ich habe jedenfalls auf Anhieb nicht verstanden, was du da gemacht hast. Ich bin aber auch kein Freund von solchen Symbolwüsten, wahrscheinlich genau deshalb, weil ich sie nicht verstehe. Mir sind ein paar erklärende Worte lieber. Von daher halte ich mich jetzt lieber raus Wink

16.11.2021, 18:33

Dereineda

Auf diesen Beitrag antworten »

Ich sehe gerade ich hatte im oberen Teil einen copypaste Fehler.. Muss mich die Tage mal registrieren, dann kann ich auch editieren..

das ist was da hin sollte:

Sei R1, R2 Äquivalenzrelationen

Z.Z $\begin{eqnarray*} R1\cap R2 \end{eqnarray*}$ Äquivalenzrelation

$\begin{eqnarray*} \forall a \in A: (a,a)\in R1 \land (a,a) \in R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \forall a,b \in A: (a,b)\in R1 \land (a,b) \in R2 \Rightarrow (b,a)\in R1 \land (b,a) \in R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \forall a,b,c \in A: \underbrace{(a,b)\in R1 \land (b,c) \in R1}_{\Rightarrow ((a,c) \in R1} \land \underbrace{(a,b)\in R2 \land (b,c) \in R2}_{\Rightarrow ((a,c) \in R2} \end{eqnarray*}$

Dann gilt auch:
$\begin{eqnarray*} \forall a \in A: (a,a) \in R1 \cap R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \forall a,b \in A: (a,b)\in R1 \cap R2 \Rightarrow (b,a)\in R1 \cap R2 \land \end{eqnarray*}$
$\begin{eqnarray*} \forall a,b,c \in A: (a,b)\in R1\cap R2 \land (b,c) \in R1\cap R2 \Rightarrow (a,c) \in R1\cap R2 \end{eqnarray*}$

Somit ist auch $\begin{eqnarray*} R1\cap R2 \end{eqnarray*}$ eine Äquivalenzrelation.

16.11.2021, 19:51

Elvis

Auf diesen Beitrag antworten »

Ich verstehe was du meinst, und ich könnte das als Beweis akzeptieren. Am Ende einiger Formeln steht ein überflüssiges $\begin{eqnarray*} \wedge \end{eqnarray*}$ .
Damit der Beweis leichter lesbar wird, könnte man ihn auch zeilenweise aufschreiben, also eine Eigenschaft nach der anderen.

Reflexiv:
$\begin{eqnarray*} \forall a\in A: (a,a)\in R_1\wedge \forall a\in A: (a,a)\in R_2\Rightarrow \forall a\in A: (a,a)\in R_1\wedge (a,a) \in R_2\Rightarrow \forall a\in A: (a,a)\in R_1\cap R_2 \end{eqnarray*}$

Du lässt für jede Eigenschaft am Anfang die Formeln weg, die für die beiden Relationen gelten, deshalb scheint es so, als ob du nur die Behauptungen aufschreibst, statt sie zu beweisen. Wohlwollend interpretiert ist das in Ordnung, an URLs Reaktion erkennst du, dass man auch anderer Meinung sein kann. Wenn du sicher gehen willst, schreibe nicht nur, dass $\begin{eqnarray*} R_1,R_2 \end{eqnarray*}$ Äquivalenzrelationen sind, sondern schreibe jeweils hin, was das bedeutet.

17.11.2021, 09:12

Dereineda

Auf diesen Beitrag antworten »

Das $\begin{eqnarray*} \land \end{eqnarray*}$ habe ich gemacht weil eine Äquivalenzrelation reflexiv, symmetrisch und transitiv sein muss. So wie ich das verstehe, ist das dann falsch wenn ich das so aufschreibe? Also die Definitionen mit einem und verbinde um zu zeigen dass alle 3 sein müssen.

Aber deine Notation macht durchaus Sinn für mich, werde das mal so aufschreiben. Ich danke dir.

17.11.2021, 12:51

Elvis

Auf diesen Beitrag antworten »

Jetzt verstehe ich was du mit dem zusätzlichen UND meinst. Das ist nicht falsch, also richtig, aber ungewöhnlich, es so aufzuschreiben.

Neue Frage »

Antworten »

Schnitt von Äquivalenzrelationen

Verwandte Themen