Äquivalenzrelation? < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:33 So 28.11.2004 | | Autor: | Shaguar |
Moin,
ich weiß mal wieder nicht, wie ich es aufschreiben soll. Die Frage sieht für mich ziemlich einfach aus ich weiß bloß nicht, was ich verwenden darf und was nicht und wie ich es am besten aufschreibe.
Sei X eine Menge ~ eine Relation auf X. Angenommen es gilt x~x für alle x [mm] \in [/mm] X, und für alle x,y [mm] \in [/mm] X mit x~y gilt auch y~x. Definieren sie eine neue Relation ~' auf X, für die x~'y genau dann gilt, wenn es eine natürliche Zahl k und Elemente [mm] z_1,....,z_k \in [/mm] X gibt mit
[mm] x~z_1, z_1~z_2, [/mm] ... [mm] z_{k-1}~z_k, z_k~y.
[/mm]
Zeigen Sie, dass ~' eine Äquivalenzrelation ist!
~' ist eine ÄR dann gilt
1. x~'x
2. x~'y y~'x
3. x~'y y~'z dann x~'z
Wie Beweis ich dass denn? Kann es sein dass es in der Zeile mit der Transivität nicht eigentlich ~' heißen müsste?
Man sieht es ja eigentlich schon ich weiß bloß nicht wie ich es aufschreiben soll.
Für Tipps und Hilfen bin ich dankbar.
MFG Shaguar
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:14 Mo 29.11.2004 | | Autor: | Julius |
Hallo Shaguar!
Wegen $x [mm] \sim [/mm] x$ gilt natürlich auch $x [mm] \sim' [/mm] x$ für alle $x [mm] \in [/mm] X$, d.h. [mm] $\sim'$ [/mm] ist reflexiv.
Gilt für $x,y [mm] \in [/mm] $ [mm] $x\sim' [/mm] y$, so gibt es Elemente [mm] $z_1,z_2,\ldots, z_k \in [/mm] X$ mit
$x [mm] \sim z_1$, $z_1 \sim z_2$, $\ldots$, $z_{k-1} \sim z_k$, $z_k \sim [/mm] y$.
Dann gilt aber wegen der Symmetrie von [mm] $\sim$ [/mm] auch
$y [mm] \sim z_k$, $z_k \sim z_{k-1}$, $\ldots$, $z_2 \sim z_1$, $z_1 \sim [/mm] x$, also:
$y [mm] \sim w_1$, $w_1 \sim w_2$, $\ldots$, $w_{k-1} \sim w_k$, $w_k \sim [/mm] x$
für [mm] $w_i:=z_{k-i} \in [/mm] X$, und somit:
$y [mm] \sim' [/mm] x$, d.h. [mm] $\sim'$ [/mm] ist symmetrisch.
Nun gelte: $x [mm] \sim' [/mm] y$ und $y [mm] \sim' [/mm] z$.
Dann gibt es [mm] $z_1,z_2,\ldots, z_k \in [/mm] X$ und [mm] $w_1,w_2,\ldots,w_l \in [/mm] X$ mir
$x [mm] \sim z_1$, $z_1 \sim z_2$, $\ldots$, $z_{k-1} \sim z_k$, $z_k \sim [/mm] y$
und
$y [mm] \sim w_1$, $w_1 \sim w_2$, $\ldots$, $w_{l-1} \sim w_l$, $w_l \sim [/mm] z$.
Definiere nun:
[mm] $v_i:= \left\{ \begin{array}{ccc} z_i & \mbox{für} & i=1,\ldots,k,\\[5pt]
y & \mbox{für} & i=k+1,\\[5pt] w_{i-(k+1)} & \mbox{für} & i=k+2,\ldots,k+l+1. \end{array} \right.$
[/mm]
Dann sind [mm] $v_1,v_2,\ldots, v_{k+l+1} \in [/mm] X$ mit
$x [mm] \sim v_1 [/mm] = [mm] z_1$, $v_1 \sim v_2$, $z_k [/mm] = [mm] v_k \sim v_{k+1} [/mm] = y, [mm] y=v_{k+1} \sim v_{k+2} [/mm] = [mm] w_1$, $\ldots$, $v_{k+l} \sim v_{k+l+1}$, $v_{k+l+1} [/mm] = [mm] w_l \sim [/mm] z$,
d.h. es gilt nach Definition:
$x [mm] \sim' [/mm] z$.
Somit ist [mm] $\sim'$ [/mm] auch transitiv und damit eine Äquivalenzrelation auf $X$.
Liebe Grüße
Julius
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:46 Mo 29.11.2004 | | Autor: | Shaguar |
Moin Julius,
klasse Antwort ich hab geh sie mal ein wenig durch, wenn ich sie komplett verstanden habe schreibe ich sie dann mal so auf, dass mir mein Tutor, das ganze auch abnimmt. Ich glaube nicht, dass ein Ottonormalstudent, sowas nach 6Wochen Studium aufschreiben kann.
> Hallo Shaguar!
>
> Wegen [mm]x \sim x[/mm] gilt natürlich auch [mm]x \sim' x[/mm] für alle [mm]x \in X[/mm],
> d.h. [mm]\sim'[/mm] ist reflexiv.
Das hab ich mir schon fast gedacht. Die Symetrie für [mm]x\sim' y[/mm] ist jedoch an die Bedingung mit der Zeile gebunden kann ich also nicht übernehmen.
> Gilt für [mm]x,y \in[/mm] [mm]x\sim' y[/mm], so gibt es Elemente
> [mm]z_1,z_2,\ldots, z_k \in X[/mm] mit
Hier setzt du die Symetrie vorraus und dann kommt ein Beweis, dass diese Annahme auch stimmt.
Müsste es hier nicht heißen [mm]x,y \in X[/mm], oder tatsächlich so, wie du es oben geschrieben hast?
> [mm]x \sim z_1[/mm], [mm]z_1 \sim z_2[/mm], [mm]\ldots[/mm], [mm]z_{k-1} \sim z_k[/mm], [mm]z_k \sim y[/mm].
>
>
> Dann gilt aber wegen der Symmetrie von [mm]\sim[/mm] auch
>
> [mm]y \sim z_k[/mm], [mm]z_k \sim z_{k-1}[/mm], [mm]\ldots[/mm], [mm]z_2 \sim z_1[/mm], [mm]z_1 \sim x[/mm],
In den beiden Zeilen definerst du erstmal auf [mm] \sim [/mm] Symetrische Elemente aus X
also:
>
> [mm]y \sim w_1[/mm], [mm]w_1 \sim w_2[/mm], [mm]\ldots[/mm], [mm]w_{k-1} \sim w_k[/mm], [mm]w_k \sim x[/mm]
>
>
> für [mm]w_i:=z_{k-i} \in X[/mm], und somit:
>
> [mm]y \sim' x[/mm], d.h. [mm]\sim'[/mm] ist symmetrisch.
Hier stellt sich mir die Frage, warum du [mm] w_i [/mm] einführst.
>
> Nun gelte: [mm]x \sim' y[/mm] und [mm]y \sim' z[/mm].
>
> Dann gibt es [mm]z_1,z_2,\ldots, z_k \in X[/mm] und
> [mm]w_1,w_2,\ldots,w_l \in X[/mm] mir
>
> [mm]x \sim z_1[/mm], [mm]z_1 \sim z_2[/mm], [mm]\ldots[/mm], [mm]z_{k-1} \sim z_k[/mm], [mm]z_k \sim y[/mm]
>
>
> und
>
> [mm]y \sim w_1[/mm], [mm]w_1 \sim w_2[/mm], [mm]\ldots[/mm], [mm]w_{l-1} \sim w_l[/mm], [mm]w_l \sim z[/mm].
>
>
> Definiere nun:
>
> [mm]$v_i:= \left\{ \begin{array}{ccc} z_i & \mbox{für} & i=1,\ldots,k,\\[5pt]
y & \mbox{für} & i=k+1,\\[5pt] w_{i-(k+1)} & \mbox{für} & i=k+2,\ldots,k+l+1. \end{array} \right.$
[/mm]
>
Hier definierst du alle Elemente aus X als [mm] v_i [/mm] und mit dem Wert von i setzt du dann [mm] v_i=x [/mm] oder y oder z, so dass die Relation passt.
> Dann sind [mm]v_1,v_2,\ldots, v_{k+l+1} \in X[/mm] mit
>
> [mm]x \sim v_1 = z_1[/mm], [mm]v_1 \sim v_2[/mm], [mm]z_k = v_k \sim v_{k+1} = y, y=v_{k+1} \sim v_{k+2} = w_1[/mm],
> [mm]\ldots[/mm], [mm]v_{k+l} \sim v_{k+l+1}[/mm], [mm]v_{k+l+1} = w_l \sim z[/mm],
>
>
> d.h. es gilt nach Definition:
>
> [mm]x \sim' z[/mm].
>
> Somit ist [mm]\sim'[/mm] auch transitiv und damit eine
> Äquivalenzrelation auf [mm]X[/mm].
Am Anfang hast du die Symetrie einfach übernommen, könnte man nicht die Transivität aus der den Zeilen von [mm] \sim [/mm] in denen die [mm] z_k [/mm] vorkommen nicht auch einfach auch übernehmen? Ich habe deine Antwort zu 70% verstanden schätze ich. Mir ist aber vollkommen schleierhaft, wie man auf sowas kommen soll. Wahrscheinlich nach dem tausendsten Mathebuch wenn man solche Sachen eh nur noch im Kopf hat.
Vielen Dank für die Mühe.
Gruß Shaguar
|
|
|
| |
|
Gruß!
Im Grunde ist das alles sehr natürlich... und keine Sorga, auch Du wirst auf woas kommen und auch nicht erst nach dem 1000. Mathebuch - spätestens nach dem 2. Semester werden Dir Beweise dieser Art ohne Probleme aufs Papier fließen, glaub mir. 
Zu Deinen Fragen: stell es Dir doch so vor:die Relation [mm] $\sim$ [/mm] ist gegeben und die ist reflexiv und symmetrisch.
Jetzt führst Du eine Relation [mm] $\sim'$ [/mm] ein und Du sagst, 2 Elemente sollen in der neuen Relation stehen, wenn es eine Kette gibt, die beide über die Relation [mm] $\sim$ [/mm] verbindet. (Das ist jetzt anschaulich formuliert, die mathematisch korrekte Formulierung steht ja in der Aufgabe).
Wieso ist diese neue Relation symmetrisch? Was eißt überhaupt symmetrisch bei einer Relation?
Symmetrisch heißt: sind $x,y [mm] \in [/mm] X$ gegeben mit $x [mm] \sim' [/mm] y$, dann gilt auch $y [mm] \sim' [/mm] x$.
Das heißt, Du mußt $x [mm] \sim' [/mm] y $ VORAUSSETZEN und daraus dann $y [mm] \sim' [/mm] x$ folgern! Und genau das ist beim Beweis der Symmetrie geschehen! Die formal korrekte Schreibweise entnehme bitte dem anderen Post, hier nur fürs Verständnis: die Idee ist schlicht, dass Du ja aufgrund der Voraussetzung eine "Kette" von Elementen von $x$ nach $y$ gegeben hast und Du mußt nun eine Kette in der Gegenrichtung finden. Die Relation [mm] $\sim$ [/mm] ist aber symmetrisch, also kannst Du Deine Kette einfach umdrehen und gelangst so von $y$ nach $x$ und zwar wieder über die Relation [mm] $\sim$!
[/mm]
Dieses "Umdrehen" geschieht formal durch eine Verschiebung des Indexes, darum wurden diese Elemente [mm] $w_i$ [/mm] eingeführt, die im Grunde die [mm] $z_i$ [/mm] sind, nur anders numeriert.
Alles klar? Also zur Transitivität!
Da gibst Du Dir 3 Elemente $x,y,z [mm] \in [/mm] X$ vor und setzt wieder voraus, dass bereits gilt: $x [mm] \sim' [/mm] y$ und $y [mm] \sim' [/mm] z$. Jetzt willst Du $x [mm] \sim' [/mm] z$ beweisen.
Du hast also "Ketten" - zwei Stück, eine von $x$ nach $y$ und eine von $y$ nach $z$. Wie also kommst Du von $x$ nach $z$? Nun, Du baust diese Ketten einfach zusammen! Und das geschieht mit Hilfe der [mm] $v_i$. [/mm] Die formale Schreibweise steht im anderen Post - hier geht es um die Idee.
Alles klar soweit? Sobald Dir so etwas anschaulich klar ist, kannst Du drangehen das Ganze formal aufzuschreiben. Da werden dann Indizes verschoben und Elemente definiert... aber die Anschauung darf nicht verloren gehen, die Idee auf der der Beweis beruht.
Viel Spaß noch im Studium!
Lars
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:27 Mi 01.12.2004 | | Autor: | Shaguar |
Moin,
saß gestern nen bischen mit nen paar anderen über der Aufgabe als wir dann irgendwann den Sinn dieser Aufgabe richtig rausgelesen hatten sind wir auf was sehr ähnliches gekommen. Mein Tutor hat die ganze Zeit etwas davon gefaselt, dass man doch die Existenz dieses k beweisen soll/muß was ja Schwachsinn ist.
> Das heißt, Du mußt [mm]x \sim' y[/mm] VORAUSSETZEN und daraus dann [mm]y \sim' x[/mm]
> folgern! Und genau das ist beim Beweis der Symmetrie
> geschehen!
Wenn man das macht ist die Aufgabe ja dann doch machbar. Und mit deiner Erklärung habe ich jetzt den vollen Durchblick und kann das ganze in einer eigenen Version aufschreiben.
Vielen Dank
Shaguar
|
|
|
|
