Zeige Äquivalenzrelation < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:14 Do 26.04.2012 | | Autor: | elmanuel |
| Aufgabe | Sei n [mm] \in \IN. [/mm] Betrachte die Relation ~ auf [mm] \IZ, [/mm] welche durch
a~b [mm] :\gdw [/mm] n | (b- a)
de niert ist.
i) Zeige das ~ eine Äquivalenzrelation ist.
ii) Beschreibe die Quotientenmenge [mm] \IZ [/mm] / ~
iii) Zeige, dass Z / ~ mit der Menge [mm] \{1, 2, ... , n-1\} [/mm] identi ziert werden kann. Genauer: die Abbildung R: [mm] \IZ [/mm] / ~ [mm] \to [/mm] [mm] \{1, 2, ... , n-1\}, [/mm] R(M) = min(M [mm] \cap [/mm] N) |
Hallo lieber Gemeinde!
also ich scheitere schon an der ÄR
um zu zeigen dass ~ ÄR muss ich transitivität, reflexivität und symmetrie zeigen das ist klar...
aber ich verstehe nichtmal was das für eine relation sein soll
n|(b-a) ??
n aus [mm] \IN [/mm] für dass gilt b-a? was soll das für einen sinn machen
vielleicht kann mir das jemand anhand eines beispiels verdeutlichen welche relation hier gemeint ist...
danke
ps: zu ii) und iii) hab ich auch noch keine idee :(
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:41 Do 26.04.2012 | | Autor: | Lippel |
Nabend,
> Sei n [mm]\in \IN.[/mm] Betrachte die Relation ~ auf [mm]\IZ,[/mm] welche
> durch
> a~b [mm]:\gdw[/mm] n | (b- a)
> de niert ist.
>
> i) Zeige das ~ eine Äquivalenzrelation ist.
> ii) Beschreibe die Quotientenmenge [mm]\IZ[/mm] / ~
> iii) Zeige, dass Z / ~ mit der Menge [mm]\{1, 2, ... , n-1\}[/mm]
> identi ziert werden kann. Genauer: die Abbildung R: [mm]\IZ[/mm] / ~
> [mm]\to[/mm] [mm]\{1, 2, ... , n-1\},[/mm] R(M) = min(M [mm]\cap[/mm] N)
> Hallo lieber Gemeinde!
>
> also ich scheitere schon an der ÄR
>
> um zu zeigen dass ~ ÄR muss ich transitivität,
> reflexivität und symmetrie zeigen das ist klar...
>
> aber ich verstehe nichtmal was das für eine relation sein
> soll
> n|(b-a) ??
>
> n aus [mm]\IN[/mm] für dass gilt b-a? was soll das für einen sinn
> machen
Das bedeutet "$n$ teilt $b-a$".
Also, nehmen wir mal als Beispiel $n=3$. Dann stehen 1 und 7 in Relation, da $7-1=6$ durch 3 teilbar ist, 1 und 2 stehen hingegen nicht in Relation, da $2-1=1$ nicht durch 3 teilbar ist.
>
> vielleicht kann mir das jemand anhand eines beispiels
> verdeutlichen welche relation hier gemeint ist...
Kommst du jetzt selbst weiter?
Grüße, Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:19 Do 26.04.2012 | | Autor: | elmanuel |
Danke Lippel!
ahja... :) ... stimmt der | steht ja auch für "teilt"
nunja denn:
1. Reflexivität:
n|(a-a) = n|0
wahr da 0 durch alles teilbar
2. Transitivität
n|(a-b) [mm] \wedge [/mm] n|(b-c) [mm] \wedge [/mm] n|(a-c)
wundersamer weise stimmt das... aber mir ist gerade nicht klar warum eigentlich... hat das was mit restklassenringen zu tun ?
3. Symmetrie
n|(a-b) [mm] \wedge [/mm] n|(b-a)
stimmt weil
n|(a-b) [mm] \wedge [/mm] n| |a-b|
und |a-b| = b-a oder a-b
nachdem diese Eigensch. erfüllt sind ist ~ eine ÄR.
zu ii)
die Quotientenmenge ist ja nun die Menge der Äquivalenzklassen... also die Äquivalenzklassen sind ja die mengen in denen die elemente zusammengefasst sind für welche die ÄR gilt ... könnte mir jemand ein konkretes beispiel zu so einer äquivalenzklasse geben?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:34 Do 26.04.2012 | | Autor: | Lippel |
Hi,
> ahja... :) ... stimmt der | steht ja auch für "teilt"
>
> nunja denn:
>
> 1. Reflexivität:
>
> n|(a-a) = n|0
>
> wahr da 0 durch alles teilbar
Alles teilt 0, also gilt auch, dass n teilt 0. 0 selbst teilt gar nichts!
> 2. Transitivität
>
> n|(a-b) [mm]\wedge[/mm] n|(b-c) [mm]\wedge[/mm] n|(a-c)
>
> wundersamer weise stimmt das... aber mir ist gerade nicht
> klar warum eigentlich... hat das was mit restklassenringen
> zu tun ?
Ich verstehe deine Argumentation nicht wirklich. Du sollst doch zeigen: $a [mm] \sim [/mm] b, [mm] b\sim [/mm] c [mm] \Rightarrow [/mm] a [mm] \sim [/mm] c$. Also: wenn gilt $n|(a-b)$ und $n|(c-b)$, dann musst du begründen, dass $n|(c-a)$ gilt. Ich sehe bei dir keine Begründung.
> 3. Symmetrie
>
> n|(a-b) [mm]\wedge[/mm] n|(b-a)
Du musst zeigen $n|(a-b) [mm] \Rightarrow [/mm] n|(b-a)$
>
> stimmt weil
> n|(a-b) [mm]\wedge[/mm] n| |a-b|
>
> und |a-b| = b-a oder a-b
>
> nachdem diese Eigensch. erfüllt sind ist ~ eine ÄR.
Du meinst glaube ich das richtige. Aber das ist unstrukturiert.
> zu ii)
>
> die Quotientenmenge ist ja nun die Menge der
> Äquivalenzklassen... also die Äquivalenzklassen sind ja
> die mengen in denen die elemente zusammengefasst sind für
> welche die ÄR gilt ... könnte mir jemand ein konkretes
> beispiel zu so einer äquivalenzklasse geben?
Wieder zum Beislpiel n=3, dann wäre eine Aquivalenzklasse [mm] $\{\ldots,-6,-3,0,3,6,9,\ldots\}$. [/mm] Eine andere wäre [mm] $\{\ldots -7,-4,-1,2,5,8,\dots\}$
[/mm]
Viele Grüße, Lippel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:59 Do 26.04.2012 | | Autor: | Marcel |
Hallo,
> Danke Lippel!
>
> ahja... :) ... stimmt der | steht ja auch für "teilt"
>
> nunja denn:
>
> 1. Reflexivität:
>
> n|(a-a) = n|0
>
> wahr da 0 durch alles teilbar
>
> 2. Transitivität
>
> n|(a-b) [mm]\wedge[/mm] n|(b-c) [mm]\wedge[/mm] n|(a-c)
>
> wundersamer weise stimmt das... aber mir ist gerade nicht
> klar warum eigentlich... hat das was mit restklassenringen
> zu tun ?
sowas braucht man da nicht (kann man sicher aber auch irgendwie verwenden).
Mach's doch elementar:
Für ganze Zahlen [mm] $n,m\,$ [/mm] gilt
$$n | m [mm] \gdw \exists [/mm] k [mm] \in \IZ \text{ mit }m=k*n\,.\$$
[/mm]
Also:
Gelte $a [mm] \sim [/mm] b$ und $b [mm] \sim c\,.$ [/mm] Zu zeigen: Dann folgt $a [mm] \sim c\,,$ [/mm] also $n | [mm] (c-a)\,.$ [/mm] (Du dürftest hier am Ende nur [mm] $n|(a-c)\,$ [/mm] schreiben, wenn [mm] $\sim$ [/mm] schon als symmetrisch erkannt wurde. Bis dahin musst Du Dich STRIKT an die Definition von [mm] $\sim$ [/mm] halten - und die war nun mal formal gegeben durch $a [mm] \sim [/mm] b [mm] :\gdw [/mm] n [mm] |(b-a)\,,$ [/mm] und NICHT durch $a [mm] \sim [/mm] b [mm] :\gdw [/mm] n | [mm] (a-b)\,$!)
[/mm]
Aus $a [mm] \sim [/mm] b$ bzw. $b [mm] \sim [/mm] c$ folgt [mm] $n|(b-a)\,$ [/mm] bzw. [mm] $n|(c-b)\,.$ [/mm] Daher existieren [mm] $k_1,k_2 \in \IZ$ [/mm] so, dass sowohl
[mm] $$(\*)\;\;\;b-a=k_1 [/mm] n$$
als auch
[mm] $$(\*\*)\;\;c-b=k_2 [/mm] n$$
gelten.
Wieso kann man nun auch $c-a=k'*n$ mit einem $k' [mm] \in \IZ$ [/mm] schreiben? (Tipp: Bilde "die Summe [mm] $(\*\*)\mathbf{+}(\*)$").
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:21 Fr 27.04.2012 | | Autor: | elmanuel |
OK. Danke Leute!
Next Try:
1. Reflexivität:
n|(a-a) = n|0
wahr da 0*n =0 [mm] \forall [/mm] n [mm] \in \IZ [/mm] und somit teilen alle n die 0.
2. Transitivität
n|(b-a) [mm]\wedge[/mm] n|(c-b) [mm]\Rightarrow[/mm] n|(c-a)
mit marcells tipp
> Für ganze Zahlen [mm]n,m\,[/mm] gilt
> [mm]n | m \gdw \exists k \in \IZ \text{ mit }m=k*n\,.\[/mm]
>
> Also:
> Gelte [mm]a \sim b[/mm] und [mm]b \sim c\,.[/mm] Zu zeigen: Dann folgt [mm]a \sim c\,,[/mm]
> also [mm]n | (c-a)\,.[/mm] [/mm]
> Aus [mm]a \sim b[/mm] bzw. [mm]b \sim c[/mm] folgt [mm]n|(b-a)\,[/mm] bzw. [mm]n|(c-b)\,.[/mm]
> Daher existieren [mm]k_1,k_2 \in \IZ[/mm] so, dass sowohl
> [mm](\*)\;\;\;b-a=k_1 n[/mm]
> als auch
> [mm](\*\*)\;\;c-b=k_2 n[/mm]
> gelten.
jetzt addieren wir die beiden gleichungen
[mm] b-a=k_1 [/mm] n
[mm] c-b=k_2 [/mm] n
---------------- +
[mm] c-a=(k_1+k_2)n
[/mm]
da [mm] k_1 [/mm] und [mm] k_2 \in \IZ \Rightarrow [/mm] n|(c-a)
nachdem diese Eigensch. erfüllt sind ist ~ eine ÄR.
ist der Punkt i) damit jetzt erfüllt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:43 Fr 27.04.2012 | | Autor: | fred97 |
> OK. Danke Leute!
>
> Next Try:
>
> 1. Reflexivität:
>
> n|(a-a) = n|0
>
> wahr da 0*n =0 [mm]\forall[/mm] n [mm]\in \IZ[/mm] und somit teilen alle n
> die 0.
>
> 2. Transitivität
>
> n|(b-a) [mm]\wedge[/mm] n|(c-b) [mm]\Rightarrow[/mm] n|(c-a)
>
> mit marcells tipp
>
> > Für ganze Zahlen [mm]n,m\,[/mm] gilt
> > [mm]n | m \gdw \exists k \in \IZ \text{ mit }m=k*n\,.\[/mm]
> >
> > Also:
> > Gelte [mm]a \sim b[/mm] und [mm]b \sim c\,.[/mm] Zu zeigen: Dann folgt [mm]a \sim c\,,[/mm]
> > also [mm]n | (c-a)\,.[/mm][/mm]
>
> > Aus [mm]a \sim b[/mm] bzw. [mm]b \sim c[/mm] folgt [mm]n|(b-a)\,[/mm] bzw. [mm]n|(c-b)\,.[/mm]
> > Daher existieren [mm]k_1,k_2 \in \IZ[/mm] so, dass sowohl
> > [mm](\*)\;\;\;b-a=k_1 n[/mm]
> > als auch
> > [mm](\*\*)\;\;c-b=k_2 n[/mm]
> > gelten.
>
> jetzt addieren wir die beiden gleichungen
>
> [mm]b-a=k_1[/mm] n
> [mm]c-b=k_2[/mm] n
> ---------------- +
> [mm]c-a=(k_1+k_2)n[/mm]
>
> da [mm]k_1[/mm] und [mm]k_2 \in \IZ \Rightarrow[/mm] n|(c-a)
>
> nachdem diese Eigensch. erfüllt sind ist ~ eine ÄR.
>
> ist der Punkt i) damit jetzt erfüllt?
Ja
FRED
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:13 Mi 02.05.2012 | | Autor: | elmanuel |
danke allen beteiligten! mittlerweile hab ich den rest übrigens auch rausbekommen
|
|
|
|
