Äquivalenzrelationen - Transitivität

24.01.2011, 07:34

seroland

Äquivalenzrelationen - Transitivität

Hallo zusammen,

kurze Frage zur Definition der transitivität:

$\begin{eqnarray*} xRy, yRz \rightarrow xRz \end{eqnarray*}$

Bedeutet das, dass y und z verschiedene Elemente sein müssen? Hintergrund ist folgende Aufgabe:

M ist eine nichtleere Menge, $\begin{eqnarray*} R \subseteq \wp(M) \times \wp(M) \text{ und } xRy \text{ gdw. } X \cup Y = M \end{eqnarray*}$

Die Transitivität wurde nun wie folgt bewiesen:

$\begin{eqnarray*} \phi \cup M = M, M \cup \phi = M \rightarrow \phi R M \text{ und } m R \phi \text{ es gilt aber nicht } \phi R \phi, da M \neq \phi \end{eqnarray*}$

Bin bisher, davon ausgegangen, dass y und z zwei komplett verschiedene Elemente seien müssen. Sind diese nicht extra so gekennzeichnet (mit verschiedenen Variablen), sodass sie verschieden seien müssen? Oder gilt nur, wenn ich 2 gleiche Variablen habe, dass dann das Element gleich ist. Sind es 2 verschiedene, so können sie verschieden sein aber auch gleich?

Vielen Dank schon mal

24.01.2011, 07:46

Mystic

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen - Transitivität
Wenn du eine Funktionsgleichung hast, wie z.B.

$\begin{eqnarray*} y=x^2 \end{eqnarray*}$

würdest du auch die Punkte x=y=0 und x=y=1 ausschließen, weil ja x und y verschiedene Variablen sind?

Übrigens, warum ist das Folgende ein Beweis der Transitivität?

Zitat:

Original von seroland
Die Transitivität wurde nun wie folgt bewiesen:

$\begin{eqnarray*} \phi \cup M = M, M \cup \phi = M \rightarrow \phi R M \text{ und } m R \phi \text{ es gilt aber nicht } \phi R \phi, da M \neq \phi \end{eqnarray*}$

24.01.2011, 08:14

seroland

Auf diesen Beitrag antworten »

Hi,

es ist natürlich nicht transitiv sorry... smile

Aber das eigentliche Problem hatte ich ja mit den Variablen. Also wenn ich eine Definition xRx habe, dann ist x zwingend gleich, habe ich allerdings so etwas wie hier xRy, yRz .... dann kann z auch gleich y sein.

Macht eigentlich auch Sinn, wenn man es auf Programmiersprachen und Variablen dort überträgt ist es ja das gleiche, ist mir nie so wirklich bewusst gewesen.

Dank dir!

24.01.2011, 18:03

seroland

Auf diesen Beitrag antworten »

Hi,

noch einmal zu dem Thema, ist folgendes dann ein gültiger Beweis?

$\begin{eqnarray*} R \subseteq A \times B \end{eqnarray*}$ ist eine Äquivalenzrelation.

Jetzt soll gezeigt werden, dass die Umkehrrelation auch eine Äquivalenzrelation:

Kann man so die Reflexivität zeigen:

Es gilt $\begin{eqnarray*} xRy \Rightarrow yRx \end{eqnarray*}$ wegen Symmetrie. Wegen Transitivität gilt dann auch $\begin{eqnarray*} yRx \Rightarrow xRy \Rightarrow yRy \end{eqnarray*}$

Ist das so korrekt?

24.01.2011, 21:17

Mystic

Auf diesen Beitrag antworten »

Wo nimmst du denn zu $\begin{eqnarray*} y \end{eqnarray*}$ das $\begin{eqnarray*} x \end{eqnarray*}$ her, sodass $\begin{eqnarray*} x R y \end{eqnarray*}$ ganz zu Beginn deiner Schlusskette gilt?

Ich verstehe auch nicht, warum du die Reflexivität der Umkehrrelation $\begin{eqnarray*} R^{-1} \end{eqnarray*}$ von $\begin{eqnarray*} R \end{eqnarray*}$ überhaupt zeigen willst, denn die entsprechende Bedingung dafür schaut ja für $\begin{eqnarray*} R^{-1} \end{eqnarray*}$ genau gleich aus wie für $\begin{eqnarray*} R \end{eqnarray*}$ , und in $\begin{eqnarray*} R \end{eqnarray*}$ ist sie ja nach Voraussetzung erfüllt...

25.01.2011, 11:22

seroland

Auf diesen Beitrag antworten »

Hi,

die Umkehrrelation dreht die Elemente doch um. Und wenn ich weiss, dass wegen Symmetrie xRy bei der normalen Relation gilt, dann gilt bei der Umkehrrelation doch auch yRx... Naja war ein Versuch Augenzwinkern

25.01.2011, 16:52

Mystic

Auf diesen Beitrag antworten »

Nimm als Beispiel die Relation $\begin{eqnarray*} R=\{(1,1),(1,2),(2,1),(2,2)\} \end{eqnarray*}$ auf der Menge $\begin{eqnarray*} M=\{1,2,3\} \end{eqnarray*}$ . Diese Relation ist zwar keine Äquivalenzrelation auf $\begin{eqnarray*} M \end{eqnarray*}$ , sie ist aber symmetrisch und transitiv, d.h., sie hat alle Eigenschaften, welche du für deinen Schluß verwendest. Um damit $\begin{eqnarray*} 3 R 3 \end{eqnarray*}$ zu zeigen, müsste man dann nach deinem Vorschlag wie folgt vorgehen:

Wenn $\begin{eqnarray*} 3R x \end{eqnarray*}$ gilt, so auch $\begin{eqnarray*} x R 3 \end{eqnarray*}$ wegen der Symmetrie und dann auch $\begin{eqnarray*} 3 R 3 \end{eqnarray*}$ wegen der Transitivität... Das Problem ist nur: Es gibt hier gar kein $\begin{eqnarray*} x \end{eqnarray*}$ mit $\begin{eqnarray*} 3Rx \end{eqnarray*}$ ...

Aber noch einmal: Die von dir betrachteten Relationen sind ja sogar Äquivalenzrelationen und enthalten daher alle Paare $\begin{eqnarray*} (x,x), x \in M, \end{eqnarray*}$ woran sich dann auch beim Übergang zu $\begin{eqnarray*} R^{-1} \end{eqnarray*}$ , also durch eine Vertauschung der Koordinaten offensichtlich nichts ändert!

27.01.2011, 08:47

ReneR

Auf diesen Beitrag antworten »

Transitivität
Hey Hallo,
ich habe eine Frage zu Transitivität und zwar hab ich folgende Aufgabe....

Sei R = {(x,y) $\begin{eqnarray*} \in \end{eqnarray*}$ IN² |x*2y=32}
Zählen Sie alle geoordneten Paare der Relation auf.
Welche der Eigenschaften reflexiv, symmetrisch, transitiv, antisymmetrisch hat R.

Sooo die geeordneten Parre müßten so aussehen :
(1,16) , (2,8) , (4,4) , (16,1) , (8,2)

Nun versteh ich die Eigenschaft transitiv bei diesem Beispiel nich so ganz.
Antisymmetrisch schon garnich aber nun ja erst mal transitiv.
Transitiv bedeutet ja :
wenn (xRy $\begin{eqnarray*} \wedge \end{eqnarray*}$ yRz $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ xRz für alle x,y,z $\begin{eqnarray*} \in \end{eqnarray*}$ M

Ich verstehe nich, wo ich das z hernehmen soll ? Denk ich mir das aus oder wo soll das herkommen ? x und y ist klar z.B. (2,8) 2 ist x und 8 ist y aber wo nehm ich da z her ?

Könnte mir dafür jemand mal ein Beispiel geben ?
Vielen Dank schon mal !

Gruß René

27.01.2011, 10:10

Mystic

Auf diesen Beitrag antworten »

RE: Transitivität

Zitat:

Original von ReneR
Ich verstehe nich, wo ich das z hernehmen soll ? Denk ich mir das aus oder wo soll das herkommen ? x und y ist klar z.B. (2,8) 2 ist x und 8 ist y aber wo nehm ich da z her ?

Was mir an der Sache seltsam vorkommt, dass du zwar kein Problem damit hast, x und y aus dem Hut zu zaubern, aber dann eine unerklärliche Scheu davor hast, dasselbe mit z zu machen... Das einzige, worauf dun bei der Wahl von z achten musst ist, dass es zu dem y "passt", wenn du vorher schon (x,y) so ausgewählt hast, dass x R y gilt, d.h., dass auch y R z gilt... Findest du zu deiner Wahl von (x,y) kein passendes z, dann solltest du bei der Suche nach einem Gegenbeispiel zur Transitivität das Paar (x,y) austauschen, was aber hier nicht notwendig ist, denn es gilt ja 2 R 8 und 8 R 2, aber nicht 2 R 2...

27.01.2011, 10:30

ReneR

Auf diesen Beitrag antworten »

RE: Transitivität
Hmm ok aber x und y hab ich ja nicht aus dem Hut gezaubert ;-)
sondern (2,8) z.B. kommt ja aus meiner Menge (also die geordneten Paare)
Ich hab ja nur immer 2 Paare x und y.
Also z.B. halt (2,8) oder (16,1) also x=2 y=8 oder x=16 y=1
aber kein z....

27.01.2011, 12:13

Mystic

Auf diesen Beitrag antworten »

RE: Transitivität
Bin ein bißchen ratlos, denn wie mir scheint, hat du da ein ganz grundlegendes Verständnisproblem, das mit dieser Aufgabe im Grunde nur wenig zu tun hat... Aber machen wir trotzdem noch einen Versuch.. Wenn es um die Überprüfung der Relation

R={(1,16),(2,8),(4,4),(8,2),(16,1)}

auf Transitivität geht, also

x R y, y R z => x R z (y,y,z, beliebige natürliche Zahlen)

so darst du hier x und y zunächst beliebig wählen, soferne x R y gilt, für die zweite Beziehung y R z ist aber danach y schon festgelegt und du musst nur mehr ein z finden, sodass auch y R z gilt... Gelingt das nicht, ist die ganze Prämisse x R y, y R z falsch, der Schluss für diese konkrete Wahl von x,y,z aber richtig ("Ex falso quodlibet"). Hat man den Verdacht, dass die Transitivität nicht gilt, sollte man sich daher auf die Suche nach einem anderen Gegenbeispiel machen, das es ja dann auch gibt, wie ich oben schon erwähnt habe...

27.01.2011, 13:24

ReneR

Auf diesen Beitrag antworten »

RE: Transitivität
Hmm vllt hab ich da echt ein Verständnisproblem...
Also heißt das,
ich darf x und y beliebig wählen aber es muß aus meiner Relation kommen
also wie gesagt aus R={(1,6) , (2,8) ....}
und z such ich mir so das yRz gilt?

UND noch eine kleine Frage

x*2y=32

Z.B. 2R8 geht weil 2*2*8=32
8R2 geht weil 2*2*8=32 also setzt man hier für x einfach z ein ?

Is bestimmt alles ein bisschen arg dumm beschrieben aber sonst check ich das nich so richtig.. traurig

27.01.2011, 14:16

Mystic

Auf diesen Beitrag antworten »

RE: Transitivität

Zitat:

Original von ReneR
UND noch eine kleine Frage

x*2y=32

Z.B. 2R8 geht weil 2*2*8=32
8R2 geht weil 2*2*8=32 also setzt man hier für x einfach z ein ?

x ist ein "Platzhalter" für die linke Seite in x R y und y ein Platzhalthalter für die rechte Seite... Du könntest diese auch anders nennen, z.B. u bzw. v... Dann müsste für sie eben u*2v=32 gelten... Übrigens: Warum kürzt du hier nicht durch 2, wodurch die einfachere Bedingung xy=16 bzw. uv=16 draus wird? Du könntest auch die Relation direkt so anschreiben:

R={(x,16/x) | x ist positiver Teiler von 16}

obwohl es wenig bringt...

Neue Frage »

Antworten »

Äquivalenzrelationen - Transitivität

Verwandte Themen