Äquivalenzrelationen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:52 Fr 07.01.2011 | | Autor: | SolRakt |
| Aufgabe | a) Es sei f : M [mm] \to [/mm] N eine Funktion. Für x,y [mm] \in [/mm] M sei x ~ y definiert durch
f(x) = f (y). Zeigen Sie,
dass ~ eine Äquivalenzrelation auf M ist. Bestimmen Sie die Äquivalenzklasse von x [mm] \in [/mm] M. Wann
ist ~ eine Ordnung?
b) Bestimmen Sie die kleinste Äquivalenzrelation auf M = {0;1;2;3;4}, die
(i) (1;2), (ii) (1;2) und (3;4), (iii) (1;2) und (2;3)
enthält. (Mit “kleinste“ ist hier das bezüglich [mm] \subseteq [/mm] kleinste Element in der Menge aller Äquivalenzrelationen)
mit den gew¨unschten Eigenschaften gemeint.) |
Hallo.
Tut mir jetzt schonmal leid, wenn ich zurzeit mehrere Themen erstelle. ;)
Kann mir hier jemand helfen? Bei der a z.B:
Ich kenne die Kriterien (refl., symm., trans.) zwar, aber das ist hier ziemlich allgemein gehalten. Reflexiv ist ja klar wegen f(x) = f(x) und Symmetrie auch wegen f(x) = f(y) und f(y) = f(x). Muss man das noch genau zeigen oder kann man die Gleichheit als bekannt vorausetzen? Stimmt das denn bisher? Kann mir jemand beim rest helfen? Find da keinen Ansatz.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:25 Sa 08.01.2011 | | Autor: | Lippel |
Nabend,
> a) Es sei f : M [mm]\to[/mm] N eine Funktion. Für x,y [mm]\in[/mm] M sei x ~
> y definiert durch
> f(x) = f (y). Zeigen Sie,
> dass ~ eine Äquivalenzrelation auf M ist. Bestimmen Sie
> die Äquivalenzklasse von x [mm]\in[/mm] M. Wann
> ist ~ eine Ordnung?
>
> b) Bestimmen Sie die kleinste Äquivalenzrelation auf M =
> {0;1;2;3;4}, die
> (i) (1;2), (ii) (1;2) und (3;4), (iii) (1;2) und (2;3)
> enthält. (Mit “kleinste“ ist hier das bezüglich
> [mm]\subseteq[/mm] kleinste Element in der Menge aller
> Äquivalenzrelationen)
> mit den gew¨unschten Eigenschaften gemeint.)
> Hallo.
>
> Tut mir jetzt schonmal leid, wenn ich zurzeit mehrere
> Themen erstelle. ;)
Solange du selbst Ansätze hast ist das ja kein Thema.
> Kann mir hier jemand helfen? Bei der a z.B:
>
> Ich kenne die Kriterien (refl., symm., trans.) zwar, aber
> das ist hier ziemlich allgemein gehalten. Reflexiv ist ja
> klar wegen f(x) = f(x) und Symmetrie auch wegen f(x) = f(y)
> und f(y) = f(x). Muss man das noch genau zeigen oder kann
> man die Gleichheit als bekannt vorausetzen? Stimmt das denn
> bisher?
![[ok]](/images/smileys/ok.gif "[ok]")
Du kannst es vielleicht noch ein bisschen formaler aufschreiben, aber im Prinzip hast du Reflexivität und Symmetrie richtig gezeigt. Etwas formaler wäre es so:
1. Reflexivität: [mm] $\forall [/mm] x [mm] \in [/mm] M$ gilt: $f(x) = f(x) [mm] \Rightarrow [/mm] x [mm] \sim [/mm] x$.
2. Symmetrie: Seien $x,y [mm] \in [/mm] M$ mit [mm] $x\sim [/mm] y [mm] \Rightarrow [/mm] f(x)=f(y) [mm] \Rightarrow [/mm] f(y) =f(x) [mm] \Rightarrow y\sim [/mm] x$
3. Transitivität: Seien $x,y,z [mm] \in [/mm] M$ mit [mm] $x\sim [/mm] y, [mm] y\sim [/mm] z [mm] \Rightarrow [/mm] f(x)=f(y), f(y)=f(z) [mm] \Rightarrow [/mm] f(x)=f(z) [mm] \Rightarrow x\sim [/mm] z$
Damit hast du formal korrekt ausgeführt, dass es sich um eine Äquivalenzrelation handelt.
Nun zu den Klassen: Eine Äquivalenzklasse fast ja immer Elemente zusammen, die miteinander in Relation stehen. Sie unterteilt die ursprüngliche Menge, auf der die Relation definiert ist (hier also M), in Partitionen auf, das heißt in diesjunkte Teilmengen
Zwei Elemente aus M liegen in einer Klasse, wenn sie den gleichen Funktionswert unter f haben. Wie sieht dann z.B. die Klasse von $x [mm] \in [/mm] M$ aus?
Zur Ordnung: Wie ist denn eine Ordnung definiert?
Zu (b):
(i) Hier musst du dich Fragen, welche Elemente außer (1,2) noch zur Relation gehören müssen, damit die drei oben ausgeführten Bedingungen erfüllt sind. Zum Beispiel kannst du aus der Symmetrie folgern, dass wenn (1,2) dazugehört, also [mm] $1\sim [/mm] 2$, dann auch (2,1) dazu gehören muss.
Gleiches musst du dir für Refelxivität und Transitivität überlegen.
Hoffe das hilft dir weiter.
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:15 Sa 08.01.2011 | | Autor: | SolRakt |
Danke erstmal für deine Antwort.
Eine Ordnung ist es dann, wenn die Relation reflexiv, antisymmetrisch und transitiv ist. Müsste ich also nur noch die Antisymmetrie zeigen? Hmm..und jetzt wieder formal. Ich lass das "für alle" mal weg.
x [mm] \sim [/mm] y , y [mm] \sim [/mm] x [mm] \Rightarrow [/mm] f(x) = f(y), f(y) = f(x) ?
Das bedeutet aber nicht, dass x und y gleich sein müssen. Dazu müsste die Abbildung mind. injektiv sein, oder? Dann wär die Relation eine Ordnung.
Bei den Äquivalenzklassen hab ich aber noch große Probleme, befürchte ich. Auch wenn ich genau verstehe, was du da geschrieben hast. Nur die Anwendung fällt mir schwer. Kannst du mir da nochmal helfen?
die b versuch ich jetzt auch mal.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:20 Sa 08.01.2011 | | Autor: | fred97 |
> Danke erstmal für deine Antwort.
>
> Eine Ordnung ist es dann, wenn die Relation reflexiv,
> antisymmetrisch und transitiv ist. Müsste ich also nur
> noch die Antisymmetrie zeigen? Hmm..und jetzt wieder
> formal. Ich lass das "für alle" mal weg.
>
> x [mm]\sim[/mm] y , y [mm]\sim[/mm] x [mm]\Rightarrow[/mm] f(x) = f(y), f(y) = f(x) ?
>
> Das bedeutet aber nicht, dass x und y gleich sein müssen.
> Dazu müsste die Abbildung mind. injektiv sein, oder? Dann
> wär die Relation eine Ordnung.
Ja
>
> Bei den Äquivalenzklassen hab ich aber noch große
> Probleme, befürchte ich. Auch wenn ich genau verstehe, was
> du da geschrieben hast. Nur die Anwendung fällt mir
> schwer. Kannst du mir da nochmal helfen?
Sei [x] die Äquivivalenzklasse von x. Dann:
y [mm] \in [/mm] [x] [mm] \gdw [/mm] x [mm] \sim [/mm] y [mm] \gdw [/mm] f(y)=f(x)
FRED
>
> die b versuch ich jetzt auch mal.
>
>
>
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:36 Sa 08.01.2011 | | Autor: | SolRakt |
Danke. Kann man das so denn einfach hinschreiben?
Wegen der b). Ich hab das mal ganz genau gemacht, damit ich das verstehe. Also. zu (i) (1,2)
Wegen Reflexivität ist also (1,1) und (2,2) drin.
Wegen Symmetrie auch (2,1)
Aber die Transitivität hat hier keinen Einfluss.
Das kleinste Element müsste also (1,1) sein. Kann mir denn jemand beim Formalen helfen. Oder kann ich einfach das kleinste Element nennen? Wär mir irgendwie zu einfach.
zur (ii)
(1,2) und (3,4)
Wegen Reflexivität ist (1,1),(2,2),(3,3),(4,4) drin
Wegen Symmetrie auch (2,1) und (4,3)
Wegen Transitivität auch (1,3) und (2,4)???
Kann mir da jemand helfen? xD Danke.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:06 Sa 08.01.2011 | | Autor: | Lippel |
> Danke. Kann man das so denn einfach hinschreiben?
Ja, bzw. für $x [mm] \in [/mm] M: [mm] [x]=\{y \in M\: | \: f(y)=f(x)\}$ [/mm]
>
> Wegen der b). Ich hab das mal ganz genau gemacht, damit ich
> das verstehe. Also. zu (i) (1,2)
>
> Wegen Reflexivität ist also (1,1) und (2,2) drin.
Was ist mit (3,3) und (4,4). Alle Elemente der Menge, auf der die Realtion definiert ist, müssen mit sich selbst in Relation stehen!
>
> Wegen Symmetrie auch (2,1)
Genau
>
> Aber die Transitivität hat hier keinen Einfluss.
Ja, es kommen keine weiteren hinzu.
>
> Das kleinste Element müsste also (1,1) sein. Kann mir denn
> jemand beim Formalen helfen. Oder kann ich einfach das
> kleinste Element nennen? Wär mir irgendwie zu einfach.
Es ist nicht nach dem kleinsten Element gefragt, sondern nach der kleinsten Relation! Die Relation besteht aus Tupeln (x,y) und du sollst eine Menge an Tupeln so wählen, dass die Relation möglichst klein ist, aber trotzdem eine Äquivalenzrelation ist.
Wenn du nun zu [mm] $\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\} [/mm] noch (1,3) und (3,1) hinzu nimmst, dann ist es wieder eine Äquivalenzrelation, die wie in der Aufgabenstellung verlangt (1,2) enthält, aber eben nicht mehr die kleinste. Du musst also begründen, warum du von den gefundenen Elementen keine mehr weglassen kannst.
>
> zur (ii)
>
> (1,2) und (3,4)
>
> Wegen Reflexivität ist (1,1),(2,2),(3,3),(4,4) drin
>
> Wegen Symmetrie auch (2,1) und (4,3)
>
> Wegen Transitivität auch (1,3) und (2,4)???
Nein, wie kommst du darauf!?
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:53 Sa 08.01.2011 | | Autor: | SolRakt |
> > Danke. Kann man das so denn einfach hinschreiben?
>
> Ja, bzw. für [mm]x \in M: [x]=\{y \in M\: | \: f(y)=f(x)\}[/mm]
>
Danke nochmal dafür ;)
> Was ist mit (3,3) und (4,4). Alle Elemente der Menge, auf
> der die Realtion definiert ist, müssen mit sich selbst in
> Relation stehen!
Ok, stimmt ja.
> Wenn du nun zu [mm]$\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}[/mm]
> noch (1,3) und (3,1) hinzu nimmst, dann ist es wieder eine
> Äquivalenzrelation, die wie in der Aufgabenstellung
> verlangt (1,2) enthält, aber eben nicht mehr die kleinste.
> Du musst also begründen, warum du von den gefundenen
> Elementen keine mehr weglassen kannst.
Hmm..wie soll man das denn begründen? Hab da irgendwie keinen Ansatz.
> Nein, wie kommst du darauf!?
Sry, war irgendwie durcheinander. Aber finde einfach nichts passendes. Oder hat die Trans. hier wieder keinen Einfluss?
Danke schonmal.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:46 Sa 08.01.2011 | | Autor: | Lippel |
Hallo,
> > Wenn du nun zu [mm]$\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}[/mm]
> > noch (1,3) und (3,1) hinzu nimmst, dann ist es wieder eine
> > Äquivalenzrelation, die wie in der Aufgabenstellung
> > verlangt (1,2) enthält, aber eben nicht mehr die kleinste.
> > Du musst also begründen, warum du von den gefundenen
> > Elementen keine mehr weglassen kannst.
>
> Hmm..wie soll man das denn begründen? Hab da irgendwie
> keinen Ansatz.
Naja, die $(1,1), [mm] \ldots [/mm] (4,4)$ kann man nicht weglassen, weil sonst die Reflexivität verletzt ist, (1,2) liegt laut Aufgabenstellung in der Relation, damit kannst du auch (2,1) nicht weglassen, sonst ist die Symmetrie verletzt.
Ist ja eigentlich schon fast klar aus der Konstruktion.
>
>
> > Nein, wie kommst du darauf!?
>
> Sry, war irgendwie durcheinander. Aber finde einfach nichts
> passendes. Oder hat die Trans. hier wieder keinen Einfluss?
Genau, die hat hier keinen Einfluss.
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:15 Sa 08.01.2011 | | Autor: | SolRakt |
Danke.
Sry, hab mich geirrt. die 0 ist auch in der Menge, aber dann kommt ja nur (0,0) dazu.
Ähm, beim zweiten wäre dann die kleinste Relation (?):
{(0,0),(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)} Oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:28 Sa 08.01.2011 | | Autor: | Lippel |
Hallo,
> Sry, hab mich geirrt. die 0 ist auch in der Menge, aber
> dann kommt ja nur (0,0) dazu.
Genau, hatte ich aber auch übersehen.
>
> Ähm, beim zweiten wäre dann die kleinste Relation (?):
>
> {(0,0),(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)}
> Oder?
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:40 Sa 08.01.2011 | | Autor: | SolRakt |
Ok, danke. Beim iii) hab ich aber noch eine Frage. Da kommt ja die Transitivität hinzu. Also gehört (1,3) auch zur Menge. Gehört dann aber auch (3,1) wegen Symmetrie zur Menge?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:58 Sa 08.01.2011 | | Autor: | Lippel |
Nabend,
> Ok, danke. Beim iii) hab ich aber noch eine Frage. Da kommt
> ja die Transitivität hinzu. Also gehört (1,3) auch zur
> Menge. Gehört dann aber auch (3,1) wegen Symmetrie zur
> Menge?
Ja, am Ende müssen immer alle drei Bedingungen: Reflexivität, Symmetrie und Transitivität gegben sein.
LG Lippel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:59 Sa 08.01.2011 | | Autor: | SolRakt |
Ok, danke ;)
|
|
|
|
