Äquivalenzrelationen - richtig gedacht?

12.11.2011, 10:47	applebite	Auf diesen Beitrag antworten »
Äquivalenzrelationen - richtig gedacht? Meine Frage: Hallo, ich bin mir nicht sicher ob ich folgenden Aufgabe richtig gelöst habe: Sei $\begin{eqnarray} \Sigma \end{eqnarray}$ ein beliebiges Alphabet, S eine Äquivalenzrelation auf $\begin{eqnarray} \Sigma^ \end{eqnarray}$ und $\begin{eqnarray} R \subseteq \Sigma^* \times \Sigma^* , \forall x,y \in \Sigma^* : (xRy :\Leftrightarrow \forall w\in \Sigma^: xwSyw) \end{eqnarray}$ . Ist R dann auch eine Äquivalenzrelation? Verwenden Sie, dass S reflexiv, symmetrisch sowie transitiv ist. Meine Ideen: Da xwSyw für alle $\begin{eqnarray} w\in \Sigma^ \end{eqnarray}$ gilt, muss es auch gelten wenn wie w dem leeren Wort entspricht. Daraus folgt: $\begin{eqnarray} \forall x,y \in \Sigma^: x \varepsilon S y\varepsilon \Rightarrow \forall x,y \in \Sigma^: xSy \end{eqnarray*}$ Da offensichtlich alle Element zueinander in einer Äquivalenzrelation stehen, ist R auch eine Äquivalenzrelation. Oder habe ich da etwas übersehen? Was mich verunsichert, ist folgender Satz: "Verwenden Sie, dass S reflexiv, symmetrisch sowie transitiv ist." Das habe ich ja eigentlich nur indirekt gemacht.
12.11.2011, 16:22	Elvis	Auf diesen Beitrag antworten »
Du hast bewiesen: R Äquivalenzrelation, dann S Äquivalenzrelation. Du sollst beweisen: S Äquivalenzrelation, dann R Äquivalenzrelation.
12.11.2011, 18:47	applebite	Auf diesen Beitrag antworten »
Ok, jetzt ist mir mein Denkfehler klar. Ich muss die Sache von der anderen Seite angehen. Also liegt z.B. Reflexivität vor, weil $\begin{eqnarray} \forall w \in \Sigma^: \exists x,y \in \Sigma^: x=y=w \Rightarrow wwSww \end{eqnarray}$ Ist das richtig? Und wie kann ich dann Transitivität und Symmetrie zeigen? Es wäre nett, wenn ihr mir einen Tipp geben könntet, so dass ich selber darauf komme.
13.11.2011, 16:59	applebite	Auf diesen Beitrag antworten »
Kann ich denn bei einer so abstrakt gestellten Aufgabe überhaupt Transitivität anders zeigen also so: Es existiert ein z so dass gilt: xSy ySz -> xSz
15.11.2011, 18:51	Elvis	Auf diesen Beitrag antworten »
Deinen Beweis für die Reflexivität von R verstehe ich nicht. Ich würde es so beweisen: $\begin{eqnarray} \forall x\in \Sigma^ : xSx\Rightarrow \forall x,w\in \Sigma^* : xwSxw\Rightarrow \forall x\in \Sigma^* : xRx \end{eqnarray*}$ Beweisidee: Nutze die Reflexivität von S, bringe alle w ins Spiel, benutze die Definition von R .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »