Äquivalenzrelation für eine reflexive Relation

26.10.2008, 15:39

stereo

Äquivalenzrelation für eine reflexive Relation

Aufgabe:

Man zeige: Eine reflexive Relation R auf der nichtleeren Menge X ist genau dann eine Äquivalenzrelation, wenn gilt:

$\begin{eqnarray*} \forall x,y,z \in X (x\sim z) \wedge (y\sim z) \Rightarrow x\sim y \end{eqnarray*}$

Also meine Gedanken waren folgende:
Gegeben ist die Reflexivität, sofern muss ich beweisen dass R symmetrisch und transitiv ist.

Gegeben ist:

(i) $\begin{eqnarray*} X \neq \{\varnothing\} \end{eqnarray*}$
(ii) $\begin{eqnarray*} R \subset X \times X \end{eqnarray*}$

Symmetrie gilt, wenn $\begin{eqnarray*} y \sim z \Rightarrow z\sim y \end{eqnarray*}$
Transitivität gilt, wenn $\begin{eqnarray*} (x\sim z) \wedge (z\sim y) \Rightarrow x\sim y \end{eqnarray*}$

Mein Behauptung:

Wenn $\begin{eqnarray*} y\sim z \Rightarrow z\sim y \end{eqnarray*}$ gilt, gilt sowohl Symmetrie und Transitivität.

Zu zeigen Sei:
(1) $\begin{eqnarray*} z\sim y \Longleftrightarrow [z] = [y]\quad ; \quad [z]:=\{x\in X: x\sim z\} \Rightarrow x\sim z \end{eqnarray*}$

$\begin{eqnarray*} x\sim z \wedge z\sim y \Rightarrow x\sim y \end{eqnarray*}$

(2) $\begin{eqnarray*} z \nsim y \Longleftrightarrow [z] \cap [y] = \varnothing \end{eqnarray*}$

Angenommen $\begin{eqnarray*} [z] \cap [y] \neq \varnothing \Rightarrow z \sim y \quad \rightarrow \end{eqnarray*}$ Widerspruch zu Annahme in (2) $\begin{eqnarray*} z\nsim y \end{eqnarray*}$

Inwiefern hab ich die Lösung, weil ich mir hier nicht sicher bin

26.10.2008, 15:53

tmo

Auf diesen Beitrag antworten »

Irgendwie ist das schwer nachzuvollziehen. Warum bringst du Äquivalenzklassen ins Spiel? Du musst doch erst noch beweisen, dass es eine Äquivalenzrelation ist. Also weißt du gar nicht ob diese existieren.

Immerhin hast du richtig erkannt, dass man zunächst die Symmetrie beweisen sollte. Die Transitivität folgt dann direkt.

Das funktioniert dann so:

Sei $\begin{eqnarray*} x \sim y \end{eqnarray*}$ . Zusätzlich gilt wegen der Reflexivität noch $\begin{eqnarray*} x \sim x \end{eqnarray*}$ und $\begin{eqnarray*} y \sim y \end{eqnarray*}$ .

Nun wende
$\begin{eqnarray*} \forall x,y,z \in X: (x\sim z) \wedge (y\sim z) \Rightarrow x\sim y \end{eqnarray*}$
2 mal geschickt an.

Übrigens musst du auch noch die Gegenrichtung zeigen. Die ist aber trivial.

26.10.2008, 16:14

stereo

Auf diesen Beitrag antworten »

Ach ich hab die Definiton der Äquivalenzklassen falsch aufgefasst.

Bin noch am Suchen nach der Lösung

26.10.2008, 16:30

stereo

Auf diesen Beitrag antworten »

$\begin{eqnarray*} (z \sim x) \wedge (x\sim y) \Rightarrow z\sim y \end{eqnarray*}$

Also das muss ich beweisen, die Aussage hat den Wahrheitswert 1, wenn auch $\begin{eqnarray*} (z \sim x) \wedge (x\sim y) \end{eqnarray*}$ wahr ist.

Da $\begin{eqnarray*} x\sim y \end{eqnarray*}$ wahr ist, muss $\begin{eqnarray*} z\sim x \end{eqnarray*}$ auch wahr sein.

$\begin{eqnarray*} (z\sim x \Rightarrow z\sim y) \Longleftrightarrow (\neg (z \sim y) \Rightarrow \neg(z\sim x)) \end{eqnarray*}$

Weiter Umformung sehe ich nicht, da ich ja auch noch nicht bewiesen hab dass die Relationen transitiv sind. Ob die Negation mir weiter hilft weiß ich nicht, da ich mir nicht sicher bin was die Negation bedeutet - bedeutet sie automatisch $\begin{eqnarray*} z\nsim y \end{eqnarray*}$ ?

26.10.2008, 18:54

stereo

Auf diesen Beitrag antworten »

Oh, ich sehe grad dass ich in meiner 1. Überlegung von Transitivität ausgehe

Zitat:

Also, ich habe 4 was gegeben, nämlich:

Zitat:

Sei $\begin{eqnarray*} x \sim y \end{eqnarray*}$ . Zusätzlich gilt wegen der Reflexivität noch $\begin{eqnarray*} x \sim x \end{eqnarray*}$ und $\begin{eqnarray*} y \sim y \end{eqnarray*}$ .

Nun wende
$\begin{eqnarray*} \forall x,y,z \in X: (x\sim z) \wedge (y\sim z) \Rightarrow x\sim y \end{eqnarray*}$
2 mal geschickt an.

Ich finde den Anfang nicht, kannst du mir bitte helfen?

26.10.2008, 21:47

stereo

Auf diesen Beitrag antworten »

Kann mir niemand einen Tip geben?

26.10.2008, 22:14

Romaxx

Auf diesen Beitrag antworten »

Schau dir doch den Tip von tmo an.
Da steckt alles wesentliche drin.

Zitat:

Das funktioniert dann so:

Sei $\begin{eqnarray*} x \sim y \end{eqnarray*}$ . Zusätzlich gilt wegen der Reflexivität noch $\begin{eqnarray*} x \sim x \end{eqnarray*}$ und $\begin{eqnarray*} y \sim y \end{eqnarray*}$ .

Nun wende
$\begin{eqnarray*} \forall x,y,z \in X: (x\sim z) \wedge (y\sim z) \Rightarrow x\sim y \end{eqnarray*}$
2 mal geschickt an.

Übrigens musst du auch noch die Gegenrichtung zeigen. Die ist aber trivial.

26.10.2008, 22:21

stereo

Auf diesen Beitrag antworten »

Ja also meine Ansätze auf diesen Tip würde alle beinhalten dass die Elemente transitiv sind.

Jedoch hat mto gesagt, dass ich richtig liege wenn ich die Symmetrie beweise.

Nun müsste ich ja beweisen, dass:

$\begin{eqnarray*} y\sim z \Longleftrightarrow z\sim y \end{eqnarray*}$

Nun, wo liegt mein Ansatz? Der liegt in der Aussage von mto.

ich weiß das

$\begin{eqnarray*} (x\sim x) \wedge (x\sim y) \Longleftrightarrow (x\sim y) \wedge (y\sim y) \end{eqnarray*}$

Jetzt habe ich versucht die Aussagen zusammen zu fassen, aber wie wende ich es jetzt auf die eigentliche Aussage an?

26.10.2008, 22:44

Romaxx

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} (x\sim y) \end{eqnarray*}$ . Wegen der Reflexiviät gilt $\begin{eqnarray*} (x\sim x) \end{eqnarray*}$ , $\begin{eqnarray*} (y\sim y) \end{eqnarray*}$ .

Nun gilt:

$\begin{eqnarray*} \forall x,y \in X: (y\sim y) \wedge (x\sim y) \Rightarrow y\sim x \end{eqnarray*}$

Daraus folgt $\begin{eqnarray*} \sim \end{eqnarray*}$ ist symmetrisch.

Die andere Richtung ist trivial.

26.10.2008, 22:53

stereo

Auf diesen Beitrag antworten »

Zitat:

Original von Roman Föll
Sei $\begin{eqnarray*} (x\sim y) \end{eqnarray*}$ . Wegen der Reflexiviät gilt $\begin{eqnarray*} (x\sim x) \end{eqnarray*}$ , $\begin{eqnarray*} (y\sim y) \end{eqnarray*}$ .

Nun gilt:

$\begin{eqnarray*} \forall x,y \in X: (y\sim y) \wedge (x\sim y) \Rightarrow y\sim x \end{eqnarray*}$

Wie kommt man denn darauf? Auch in meinen Mitschrifter finde ich keine Definition für Reflexivität außer es gilt $\begin{eqnarray*} x\sim x \end{eqnarray*}$ .

27.10.2008, 01:18

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Roman Föll
Sei $\begin{eqnarray*} (x\sim y) \end{eqnarray*}$ .

Das nimmt man einfach an. Denn für Symmetrie muss man ja gerade $\begin{eqnarray*} x \sim y \Longrightarrow y \sim x \end{eqnarray*}$ zeigen.

Zitat:

Original von Roman Föll
Wegen der Reflexiviät gilt $\begin{eqnarray*} (x\sim x) \end{eqnarray*}$ , $\begin{eqnarray*} (y\sim y) \end{eqnarray*}$ .

Das ist Vorraussetzung.

Zitat:

Original von Roman Föll
Nun gilt:

$\begin{eqnarray*} \forall x,y \in X: (y\sim y) \wedge (x\sim y) \Rightarrow y\sim x \end{eqnarray*}$

Daraus folgt $\begin{eqnarray*} \sim \end{eqnarray*}$ ist symmetrisch.

Hier wurde die Eigenschaft der Relation benutzt, welche auch Vorraussetzung ist.

05.11.2008, 16:07

stereo

Auf diesen Beitrag antworten »

Ok, ich hab die Aufgabe verstanden - ihr habt in der Ausgangsaussage z = x gesetzt.

Tut mir leid dass ich erst so spät schreibe, aber ich hatte keine Zeit mich ans Internet zu setzen.

Neue Frage »

Antworten »

Äquivalenzrelation für eine reflexive Relation

Verwandte Themen