Äquivalenzrelation beweisen

20.02.2014, 18:42

HerbertB

Auf diesen Beitrag antworten »

Äquivalenzrelation beweisen

Hallo,

ich befasse mich gerade mit Äquivalenzrelationen, und komme nicht mehr weiter.

Was ich bisher weiß ist:

Eine Äquivalenzrelation ist reflexiv, symmetrisch und transitiv.

Gegeben ist folgender Graph $\begin{eqnarray*} [M, R] \end{eqnarray*}$ mit $\begin{eqnarray*} M = \{1, 2, 3, 4, 5, 6\} \end{eqnarray*}$ und der Relation $\begin{eqnarray*} R = \{(1,3), (3,2), (2,1), (6,3), (6,5), (5,4), (4,6)\} \end{eqnarray*}$

Laut Angabe ist auf M folgende Relation definiert: $\begin{eqnarray*} a \sim b :\Longleftrightarrow (\exists_{n\in\mathbb N_{0}} (a,b) \in \mathbb{R}^n) \wedge (\exists_{m\in\mathbb N_{0}} (b,a) \in \mathbb{R}^m) \end{eqnarray*}$

Es gilt zu beweisen, ob das eine Äquivalenzrelation auf M ist.

Ich stehe schon bei der Interpretation der Angabe an, besonders $\begin{eqnarray*} \mathbb{R}^n \end{eqnarray*}$ irritiert mich. Was mache ich mit dieser Deffinition?

Weiters habe ich das Problem mit a und b, wenn ich zuerst einmal reflexiv beweisen soll. Wie mache ich das? Reflexsiv ist ja $\begin{eqnarray*} \forall x \in M : xRx \end{eqnarray*}$ , aber was mache ich mit dem b?

Danke.

20.02.2014, 19:36

micha_L

Auf diesen Beitrag antworten »

RE: Äquivalenzrelation beweisen
Hallo,

sehr wahrscheinlich steht in der Originalaufgabenstellung (die du in weier Voraussicht nicht mitgepostet hast) statt $\begin{eqnarray*} \mathbb{R}^n \end{eqnarray*}$ ein $\begin{eqnarray*} R^n \end{eqnarray*}$ und statt $\begin{eqnarray*} \mathbb{R}^m \end{eqnarray*}$ ein $\begin{eqnarray*} R^m \end{eqnarray*}$ .

Wenn es so sein sollte, dann musst du jetzt wohl nochmal über die veränderte Aufgabenstellung nachdenken. Wenn nicht, dann sollte ein Scan der Originalaufgabenstellung mehr bringen, als weiter meine (zugegebenermaßen nicht besonders gute) Kristallkugel zu befragen.

Mfg Michael

PS: Ein Scan der Originalaufgabenstellung sollte zum Standard gehören. Das erspart unnötiges Rätselraten.

20.02.2014, 19:52

HerbertB

Auf diesen Beitrag antworten »

Hi, danke für den Hinweis. Es soll wirklich $\begin{eqnarray*} R^n \end{eqnarray*}$ und $\begin{eqnarray*} R^m \end{eqnarray*}$ heißen.

Originalaufgabe habe ich 1 : 1 abgeschrieben, also bringt ein Scan davon nicht wirklich was.

Hier noch einmal die richtige Definition:

$\begin{eqnarray*} a \sim b :\Longleftrightarrow (\exists_{n\in\mathbb N_{0}} (a,b) \in R^n) \wedge (\exists_{m\in\mathbb N_{0}} (b,a) \in R^m) \end{eqnarray*}$

Mein Problem besteht darin, wie ich fogende Punkte angehe:

Reflexivität
Symmetrie
Transitivität

Wie gesagt, ich weiß wie Reflexivität deffiniert ist (siehe Post #1), kann aber im Bezug auf die deffinierte Relation nichts damit anfangen. Mir fehlt der Ansatz.

20.02.2014, 20:15

Bluee

Auf diesen Beitrag antworten »

Hallo,
du brauchst kein b, glaube ich, um die Reflexivität zu beweisen. Reflexivität heißt ja, dass jedes Element in Relation zu sich selbst steht.

20.02.2014, 21:07

HerbertB

Auf diesen Beitrag antworten »

Ok, also kein b, das leuchtet ein, aber wie gehe ich das mit der Reflexivität an?

20.02.2014, 22:28

Bluee

Auf diesen Beitrag antworten »

Reflexivität:
$\begin{eqnarray*} a \sim a :\Longleftrightarrow (\exists_{n\in\mathbb N_{0}} (a,a) \in R^n) \wedge (\exists_{m\in\mathbb N_{0}} (a,a) \in R^m) \end{eqnarray*}$ für jedes a aus M.

Das heißt, denke ich, dass es so ein Paar (a,a) in der Relationsmenge für jedes Element aus M geben soll. Aber es gibt keine solche Paaren, deshalb ist die Relation nicht reflexiv. Das meine ich, aber ich bin überhaupt nicht sicher, ob es richtig ist. Ich hatte eine ähnliche Hausaufgabe zu beweisen, aber es war viel einfacher als diese.

Anzeige

21.02.2014, 07:49

micha_L

Auf diesen Beitrag antworten »

Hallo,

Zitat:

Original von Bluee
Reflexivität:
$\begin{eqnarray*} a \sim a :\Longleftrightarrow (\exists_{n\in\mathbb N_{0}} (a,a) \in R^n) \wedge (\exists_{m\in\mathbb N_{0}} (a,a) \in R^m) \end{eqnarray*}$ für jedes a aus M.

[...] deshalb ist die Relation nicht reflexiv.

Leider doch.

Vermutlich besteht bei dir ebenso wie beim OP das Problem, die Schreibweise (die ich oben angemerkt habe) nicht zu verstehen.
$\begin{eqnarray*} R^2 \end{eqnarray*}$ etwa ist als Relationenprodukt zu verstehen.
Vielleicht hilft ja schon dieser Hinweis?!

Mfg Michael

21.02.2014, 10:39

HerbertB

Auf diesen Beitrag antworten »

Hi,

danke, die Schreibweise wars... smile

smile

Wenn ich für $\begin{eqnarray*} n = 3 \end{eqnarray*}$ annehme, dann ist die Relation reflexiv.

Beispiel: $\begin{eqnarray*} R = \{(1,3), (3,2), (2,1), ...\} \end{eqnarray*}$

$\begin{eqnarray*} (1,3) \rightarrow (3,2) \rightarrow (2,1) \end{eqnarray*}$ somit ist die reflexivität erfüllt.

Meine argumentation stimmt doch, oder?

21.02.2014, 11:55

Elvis

Auf diesen Beitrag antworten »

Stimmt für $\begin{eqnarray*} 1\in M \end{eqnarray*}$ , muss aber für alle $\begin{eqnarray*} a\in M \end{eqnarray*}$ stimmen.

21.02.2014, 11:56

HerbertB

Auf diesen Beitrag antworten »

Und wie beweise ich das dann?

21.02.2014, 11:59

Elvis

Auf diesen Beitrag antworten »

Alle aufschreiben, sind ja nur 6 Elemente.

21.02.2014, 12:03

HerbertB

Auf diesen Beitrag antworten »

Wie meinst du das, alle aufschreiben? Kannst du mir da ein Beispiel geben?

21.02.2014, 12:50

Elvis

Auf diesen Beitrag antworten »

Du hast ein Beispiel für die 1 gemacht, ich mache ein Beispiel für die 2 : $\begin{eqnarray*} (2,1),(1,3),(3,2)\in R\Rightarrow 2\sim 2 \end{eqnarray*}$ .

21.02.2014, 12:59

HerbertB

Auf diesen Beitrag antworten »

Ok, jetzt da ich es aufgeschrieben habe, sehe ich es das es reflexiv ist.

Wie verfahre ich jetzt mit symmetrisch? Laut Deffinition $\begin{eqnarray*} \forall x,y\in M: xRy\Rightarrow yRx \end{eqnarray*}$

Aber wie zeige ich das anhand des Beispiels in Post #1?

21.02.2014, 13:34

Elvis

Auf diesen Beitrag antworten »

Ich habe mir den Graphen gezeichnet, er enthält 6 Knoten aus der Menge M und gerichtete Kanten (Pfeile) für jedes Paar (a,b) in R. Die Relation ~ , die wir jetzt untersuchen, bedeutet gerade, dass a~b genau dann gilt, wenn es einen Weg von a nach b und einen Weg von b nach a gibt.

Egal, wo du anfängst, es gibt immer einen Weg von a nach a, das zeigt noch einmal die Reflexivität.

Jetzt sollte es leichter fallen, die übrigen Eigenschaften zu untersuchen. (Es ergibt sich noch ein einfacheres Argument, weil jede Äquivalenzrelation zu einer Klasseneinteilung gehört und umgekehrt.)

21.02.2014, 15:08

HerbertB

Auf diesen Beitrag antworten »

Ich habe das jetzt auch gezeichnet, jedoch erschließt sich für mich noch nicht, wie es einen Weg von a nach b und auch einen Weg von b nach a geben kann.

Nehmen wir das Beispiel: $\begin{eqnarray*} (2,1),(1,3),(3,2)\in R \end{eqnarray*}$ es existiert ein Weg von 2,1 über 1,3 nach 3,2, aber die Pfeile in der Zeichnung haben eine bestimmte Richtung., wie komme ich jetzt darauf, das die umgekehrte Richtung auch möglich ist?

Bei der Definition:
$\begin{eqnarray*} a \sim b :\Longleftrightarrow (\exists_{n\in\mathbb N_{0}} (a,b) \in R^n) \wedge (\exists_{m\in\mathbb N_{0}} (b,a) \in R^m) \end{eqnarray*}$

Wenn ich für den Weg a nach b für n = 2 nehme, ist es dann egal das ich für den Weg von b nach a für m = 1 wähle?

Dadurch ergibt sich für mich gleich die nächste Frage, und zwar die Transitivität.

Wenn ein Weg von 1 nach 2 existiert und von 2 nach 3 existiert, dann muss auch ein Weg von 1 nach 3 existieren. Aber da stehe ich wieder vor dem Problem mit den Pfeilen.

21.02.2014, 18:31

Elvis

Auf diesen Beitrag antworten »

Zur Reflexivität: Es gibt einen Weg von 2 nach 2 und einen Weg von 2 nach 2. (Wenn es einen Weg von a nach a gibt, gibt es trivialerweise einen Weg von a nach a.)

Auch die Transitivität ist in diesem Beispiel kein Problem: 1 nach 2 geht (über 3), 2 nach 3 geht (über 1), und 1 nach 3 geht (direkt). Also hast du kein Problem, sondern genügend Wege.
In der Definition von ~ : $\begin{eqnarray*} (1,3)(3,2)\in R^2, (2,1)\in R\Rightarrow 1\sim 2,(2,1)(1,3)\in R^2,(3,2)\in R\Rightarrow 2\sim 3, (1,3)\in R,(3,2)(2,1)\in R^2\Rightarrow 1\sim 3 \end{eqnarray*}$ .

21.02.2014, 18:37

HerbertB

Auf diesen Beitrag antworten »

Also muss es nicht immer ein Weg der Länge n (in dem Fall der Länge 2) sein, um die Transitivität zu beweisen? Es geht auch ein Weg der Länge 2 und ein Weg der Länge 1 um das in diesem konkreten Beispiel zu beweisen?

Für die Symmetrie: von 1 über 3 nach 2 und von 2 direkt zu 1?

21.02.2014, 18:40

Elvis

Auf diesen Beitrag antworten »

Ja, so ist die Definition von ~ . a~b genau dann, wenn es einen Weg von a nach b und einen Weg von b nach a gibt.

Das habe ich um 13:34 schon einmal geschrieben.

21.02.2014, 18:43

HerbertB

Auf diesen Beitrag antworten »

Ah ok, das erklärt die Definition etwas genauer. Daher das $\begin{eqnarray*} \wedge \end{eqnarray*}$ zwischen den Existenzquantoren, quasi zwei unabhängige Wege, die die Relation erfüllen.

Sorry, das ist aus dem Text um 13:43 nicht so hervor gegangen, trotzdem danke.

21.02.2014, 18:45

Elvis

Auf diesen Beitrag antworten »

Genau

Freude

Deshalb gibt es n und m in der Definition von ~ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »