Äquivalenzrelation

13.03.2012, 11:36

Wundi

Auf diesen Beitrag antworten »

Äquivalenzrelation

Meine Frage:
Sei f \subseteq X x X eine (totale) Funktion auf einer gegebenen Menge X.
Zeigen Sie, dass durch
xRy <-> f(x) = f(y)
eine Aquivalenzrelation auf X x X defi niert wird.

Meine Ideen:
Ich bin mir nicht sicher, wie ich die Äquivalenzrelation zeigen kann?

Beweise ich reflexiv, symmetrisch & transitiv im Allgemeinen oder spezifisch auf das Bsp.?

bzw. wie funktioniert das?

Vielen Dank im Voraus!

13.03.2012, 11:47

wundi

Auf diesen Beitrag antworten »

\subseteq = Teilmenge

sry

13.03.2012, 11:56

Mazze

Auf diesen Beitrag antworten »

So,

Latexcode kommt in die Latexumgebung

code:
1:	[latex] f \subseteq X \times X [/latex]

ergibt $\begin{eqnarray*} f \subseteq X \times X \end{eqnarray*}$ . Gewöhne Dir direkt an Formeln vollständig in Latex zu schreiben. Latex ist kein Mittel um Sonderzeichen darzustellen, sondern vollständige Formeln.

$\begin{eqnarray*} f \subseteq X \times X \end{eqnarray*}$ sieht besser aus als f $\begin{eqnarray*} \subseteq \end{eqnarray*}$ X x X

Zur Aufgabe:

Zitat:

Beweise ich reflexiv, symmetrisch & transitiv im Allgemeinen oder spezifisch auf das Bsp.?

Zunächst mal ist eine Äquivalenzrelation eine Relation, die bestimmte Eigenschaften erfüllt. Wenn Du überprüfen willst, ob eine Relation eine Äquivalenzrelation ist, so musst Du nachweisen, dass diese Relation die Eigenschaften erfüllt. Fangen wir an :

Reflexivität : Was ist zu zeigen ? Schreibe das ordentlich auf!

13.03.2012, 14:24

wundi

Auf diesen Beitrag antworten »

zu zeigen ist (?):

x~y <-> f(x)=f(y)

13.03.2012, 14:29

Mazze

Auf diesen Beitrag antworten »

Zitat:

zu zeigen ist (?): x~y <-> f(x)=f(y)

Nein, das ist die Definition unserer Relation. Wir sagen x ist äquivalent zu y , genau dann wenn f(x) = f(y) ist. Damit drücken wir nur aus , wie wir unsere Äquivalenz beschreiben wollen. Wir müssen zeigen, dass diese Definition eine Äquivalenzrelation beschreibt.

Schreib mal auf was Reflexivität für diese Definition heißt.

13.03.2012, 15:28

wundi

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \forall x,y \in X : x R y \end{eqnarray*}$

Anzeige

13.03.2012, 15:32

Mazze

Auf diesen Beitrag antworten »

So ist das falsch.

Reflexivität

Eine Relation $\begin{eqnarray*} R \subseteq X \times X \end{eqnarray*}$ heißt Reflexiv, wenn $\begin{eqnarray*} \forall x \in X : xRx \end{eqnarray*}$ gilt. Unsere Relation ist definiert durch $\begin{eqnarray*} xRy \Leftrightarrow f(x) = f(y) \end{eqnarray*}$ .

Zu Zeigen für die Reflexivität :

$\begin{eqnarray*} \forall x \in X : f(x) = f(x) \end{eqnarray*}$

Das ist aber äußerst trivial Augenzwinkern

Augenzwinkern

.

13.03.2012, 15:48

wundi

Auf diesen Beitrag antworten »

okay, danke smile

smile

!

dann wäre die Symmetrie so zu zeigen (?):

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

bzw. zeig ich noch transitiv und das Beispiel ist gelöst?

13.03.2012, 15:53

Mazze

Auf diesen Beitrag antworten »

Zitat:

dann wäre die Symmetrie so zu zeigen (?): $\begin{eqnarray*} \forall x,y \in X : (xRy\Rightarrow yRx) \end{eqnarray*}$

Genau, du musst den Beweis aber auch wirklich führen. Nicht nur hinschreiben was zu tun ist Augenzwinkern

Augenzwinkern

. Bei der Reflexivität etwa fehlt noch ein kurzer Satz warum sie denn nun gilt (auch wenn sie äußerst trivial zu zu zeigen ist).

Zitat:

bzw. zeig ich noch transitiv und das Beispiel ist gelöst?

Genau, wenn Du die drei Eigenschaften nachweisen konntest ist die Aufgabe erledigt.

13.03.2012, 16:17

wundi

Auf diesen Beitrag antworten »

kannst du mir vielleicht noch ein kurzes Bespiel zeigen, wie ich den Beweis führe in diesem Fall?

13.03.2012, 16:23

Mazze

Auf diesen Beitrag antworten »

Zitat:

kannst du mir vielleicht noch ein kurzes Bespiel zeigen, wie ich den Beweis führe in diesem Fall?

Im ersten Schritt schreibst Du exakt auf was Du zeigen musst.

13.03.2012, 16:33

wundi

Auf diesen Beitrag antworten »

zeigen muss ich:

$\begin{eqnarray*} f\subseteq X x X \end{eqnarray*}$

13.03.2012, 16:42

Mazze

Auf diesen Beitrag antworten »

Wie kommst Du darauf? Das sind alles Voraussetzungen, diese Dinge sind gegeben. Zu zeigen sind andere Dinge.

Ich sortiere das mal :

Voraussetzungen:

$\begin{eqnarray*} f \subseteq X \times X \end{eqnarray*}$ sei eine totale Funktion auf X. Wir definieren

$\begin{eqnarray*} x R y \Leftrightarrow f(x) = f(y) \end{eqnarray*}$

Zu Zeigen:

R Reflexiv

$\begin{eqnarray*} \forall x \in X : x R x \end{eqnarray*}$

R Symmetrisch

$\begin{eqnarray*} \forall x,y \in X : x R y \Rightarrow y R x \end{eqnarray*}$

R Transitiv

$\begin{eqnarray*} \forall x,y,z \in X : x R y \land y R z \Rightarrow x R z \end{eqnarray*}$

So, Du musst auf schreiben was $\begin{eqnarray*} xRy \end{eqnarray*}$ genau für unsere Definierte Relation heißt. Bei der Reflexivität hab ichs dir ja schon gezeigt. Nach dem Du es aufgeschrieben hast siehst Du auch sofort wie man den Beweis führt.

13.03.2012, 17:16

wundi

Auf diesen Beitrag antworten »

für Symmetrisch würde dann gelten:

$\begin{eqnarray*} \forall x,y \in X : xRy \Rightarrow yRx \end{eqnarray*}$

$\begin{eqnarray*} \forall x,y \in X : f(x) = f(y) \end{eqnarray*}$

?

sry, Quereinstieg ins Studium und versuche nun im 1.Semester ohne Vorkenntnisse nach 2 Vorlesungen eine Übung für "Formale Grundlagen" zu bewältigen.

13.03.2012, 17:42

Mazze

Auf diesen Beitrag antworten »

Zitat:

sry, Quereinstieg ins Studium und versuche nun im 1.Semester ohne Vorkenntnisse nach 2 Vorlesungen eine Übung für "Formale Grundlagen" zu bewältigen.

Tatsächlich ist der mathematische Inhalt dieser Aufgabe äußerst gering. Ich dachte mir schon dass die Aufgabe eher auf formale Grundlagen abzielt.

Zitat:

für Symmetrisch würde dann gelten: $\begin{eqnarray*} \forall x,y \in X : xRy \Rightarrow yRx \end{eqnarray*}$ $\begin{eqnarray*} \forall x,y \in X : f(x) = f(y) \end{eqnarray*}$

Das ergibt keinen Sinn. Der logische Ausdruck

$\begin{eqnarray*} xRy \Rightarrow yRx \end{eqnarray*}$

bedeutet sprachlich, wenn xRy gilt, dann gilt auch yRx. Der Ausdruck $\begin{eqnarray*} f(x) = f(y) \end{eqnarray*}$ bedeutet lediglich f(x) ist gleich f(y). Versuchs nochmal.

13.03.2012, 18:26

wundi

Auf diesen Beitrag antworten »

kann ich die Symmetrie so beweisen:

$\begin{eqnarray*} \forall x,y \in X : f(xy) = f(yx) \end{eqnarray*}$

13.03.2012, 19:08

Mazze

Auf diesen Beitrag antworten »

Einfach blindes raten führt dich nicht zum erfolg. Du solltest Dich auch fragen was Du dort schreibst. Was soll $\begin{eqnarray*} f(xy) \end{eqnarray*}$ denn sein? Das ergibt doch bezüglich der Aufgabe keinen Sinn.

Symmetrie

Zu zeigen ist :

$\begin{eqnarray*} \forall x,y \in X : xRy \Rightarrow yRx \end{eqnarray*}$ , für unsere Relation also :

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

was auch trivial ist.

13.03.2012, 19:41

wundi

Auf diesen Beitrag antworten »

okay, so ähnlich habe ich es mir gedacht, konnte es aber nicht ausdrücken Augenzwinkern

Augenzwinkern

so, einen Versuch wage ich noch zu transitiv...

R Transitiv

$\begin{eqnarray*} \forall x,y,z \in X : xRy \wedge yRz \Rightarrow xRz \end{eqnarray*}$

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

danke!

13.03.2012, 19:48

Mazze

Auf diesen Beitrag antworten »

Ja, so ist die formulierung richtig. Was dir natürlich fehlt ist der Beweis der Aussagen, aber die sind ja wirklich leicht.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »