Äquivalenzrelation Beweis < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei M = N × N. Für a, b, c, d e N wird durch
(a, b) ~ (c, d) genau dann, wenn a + d = b + c
eine Relation auf M definiert.
Zeigen Sie, dass dies eine Äquivalenzrelation auf M ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
erstmal Respekt für diese super Community (mir wurde hier durch Lesen schon einige Male sehr geholfen)!
Nun zum Eigentlichen...
Ich soll die oben definierte Aufgabe lösen und bin mir bei meiner Lösung ein wenig unsicher.
Es wäre also super, wenn hier sich jmd. meine Lösung mal anschauen könnte und ggf. korrigieren könnte.
Vielen Dank.
Lösung:
Sei M = N×N mit a , b , c , d ∈ℕ
Sei R eine Relation auf M mit (a , b)~(c , d):⇔a+d = b+c
Reflexivität :
z.z.: (a , b)R(a , b)
a+b = b+a
Da die Gleichung stimmt , ist R reflexiv
.
Symmetrie:
z.z.: (a , b)R(c , d) ⇒ (c , d)R(a , b)
a+d = b+c ⇔ c+b = d+a
Da (c , d)R(a , b):⇔c+b = d+a, ist R symmetrisch.
Transitivität :
z.z.: ((a ,b)R(c , d) ∧ (c , d)R(e , f)) ⇒ (a ,b)R(e , f) mit (e , f) ∈ R
I :(a , b)R(c , d):⇔a+d=b+c
II :(c , d)R(e , f):⇔c+f = d+e
III :(a , b)R(e , f):⇔a+ f = b+e
a+d=b+c |+f
⇔ a+f+d = b+c+f |II
⇔ a+f+d=b+d+e |-d
⇔ a+f = b+e
Da (a , b)R(e , f):⇔a+f = b+e ,ist R somit transistiv.
Da R Reflexivität , Symmetrie und Transistivität aufweist ist R eine Äquivalenzrelation auf M.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:41 Fr 05.11.2010 | | Autor: | fred97 |
Alles O.K.
FRED
|
|
|
| |
|
| Aufgabe | (ii) Definieren Sie die Addition von Äquivalenzklassen durch
[(a, b)] + [(c, d)] = [(a + c, b + d)].
Zeigen Sie, dass diese Addition wohldefiniert ist, d.h. unabhängig von den gewählten Repräsentanten der Äquivalenzklassen ist.
(iii) Zeigen Sie, dass [(a, b)] + [(2, 2)] = [(a, b)] und [(2, 5)] + [(7, 5)] = [(1, 2)]» gilt. |
Ich habe mich nun auch an den Rest der Aufgaben getraut und hätte auch hier sehr gerne, dass sich jmd. meine Lösungen zur Kontrolle durchliest.
Gruß.
Lösungen:
(ii)
z.z.:[(a ,b)]+[(c ,d)] = [(a+c ,b+d)]
[(a ,b)]={(x , y)∈ℕ×ℕ∣a+y = b+x <=> a−b = x−y}
[(c ,d)]={( x', y')∈ℕ×ℕ∣c+y' = d+x' <=> c−d = x'−y'}
[(a+c ,b+d)]={( x'' , y'')∈ℕ×ℕ∣a+c+y'' = b+d+x'' <=> a+c−b−d = x''−y ''}
Die Äquivalenzrelation von[(a ,b)]+[(c ,d)]ist a−b+c−d = x−y + x'−y'
⇔ a+c−b−d = x''+y''
Da dieseGleichung die Äquivalenzrelationder Äquivalenzklasse [(a+c,b+d)] ist , ist die zu zeigende Addition wohldefiniert.
(iii)
z.z.:[(a ,b)]+[(2,2)] = [(a ,b)]
Die Äquivalenzrelation von[(a ,b)]+[(2,2)]ist a+2−b−2 = x ''+y ' ' (siehe (ii))
a+2−b−2 = x ' '+y ' ' ⇔ a−b = x ' '+y ' '
Die Äquvalenzklasse von a−b = x ' '+y ' ' ist [(a ,b)] (siehe(ii)).
z.z.:[(2,5)]+[(7,5)] = [(1,2)]
[(1,2)]={( x , y)∈ℕ×ℕ∣1+y = 2+x <=> y−x = 1}
Die Äquivalenzrelation von[(2,5)]+[(7,5)]ist (2+7)+y = (5+5)+x (siehe (ii))
(2+7)+y = (5+5)+x ⇔ 9+y = 10+x ⇔ y−x = 1
Diese Gleichung wiederumist die Äquivalenzelation der Äquivalenzklasse [(1,2)].
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:03 Mo 08.11.2010 | | Autor: | felixf |
Moin!
> (ii) Definieren Sie die Addition von Äquivalenzklassen
> durch
> [(a, b)] + [(c, d)] = [(a + c, b + d)].
> Zeigen Sie, dass diese Addition wohldefiniert ist, d.h.
> unabhängig von den gewählten Repräsentanten der
> Äquivalenzklassen ist.
>
> (iii) Zeigen Sie, dass [(a, b)] + [(2, 2)] = [(a, b)] und
> [(2, 5)] + [(7, 5)] = [(1, 2)]» gilt.
>
> Ich habe mich nun auch an den Rest der Aufgaben getraut
> und hätte auch hier sehr gerne, dass sich jmd. meine
> Lösungen zur Kontrolle durchliest.
>
> Gruß.
>
> Lösungen:
>
> (ii)
> z.z.:[(a ,b)]+[(c ,d)] = [(a+c ,b+d)]
> [(a ,b)]={(x , y)∈ℕ×ℕ∣a+y = b+x <=> a−b =
> x−y}
So wuerde ich es nicht aufschreiben, da es streng logisch fasch ist, aber man sieht was du meinst.
Und noch etwas: da hier die ganzen Zahlen konstruiert werden, finde ich es keine gute Idee, bereits mit ihnen zu arbeiten. Beschraenke dich doch auf die natuerlichen Zahlen!
> [(c ,d)]={( x', y')∈ℕ×ℕ∣c+y' = d+x' <=> c−d =
> x'−y'}
> [(a+c ,b+d)]={( x'' , y'')∈ℕ×ℕ∣a+c+y'' = b+d+x''
> <=> a+c−b−d = x''−y ''}
Soweit ok. Wobei du hier eigentlich schon verwendest, dass es wohldefiniert ist.
> Die Äquivalenzrelation von[(a ,b)]+[(c ,d)]ist
> a−b+c−d = x−y + x'−y'
> ⇔ a+c−b−d = x''+y''
Das macht keinen Sinn mehr.
> Da dieseGleichung die Äquivalenzrelationder
> Äquivalenzklasse [(a+c,b+d)] ist , ist die zu zeigende
> Addition wohldefiniert.
Du meinst das richtige, hast es aber ziemlich falsch aufgeschrieben.
Mach es doch so. Seien $[(a, b)] = [(a', b')]$ und $[(c, d)] = [(c', d')]$; dann gilt $a + b' = a' + b$ und $c + d' = c' + d$.
Du musst jetzt zeigen: $[(a + c, b + d)] = [(a' + c', b' + d')]$, also $(a + c) + (b' + d') = (b + d) + (a' + c')$.
Kannst du das aus den beiden Gleichungen oben herleiten?
Und zwar ohne auf die ganzen Zahlen zurueckzugreifen, also ohne Subtraktion zu verwenden?
> (iii)
> z.z.:[(a ,b)]+[(2,2)] = [(a ,b)]
> Die Äquivalenzrelation von[(a ,b)]+[(2,2)]ist a+2−b−2
> = x ''+y ' ' (siehe (ii))
Das macht immer noch keinen Sinn.
Nach (ii) ist $[(a, b)] + [(2, 2)] = [(a + 2, b + 2)]$.
Du musst also zeigen, dass $[(a + 2, b + 2)] = [(a, b)]$ ist. Das kannst du jetzt wieder umschreiben in eine Gleichung mit $a$, $b$ und $2$.
> a+2−b−2 = x ' '+y ' ' ⇔ a−b = x ' '+y ' '
> Die Äquvalenzklasse von a−b = x ' '+y ' ' ist [(a ,b)]
> (siehe(ii)).
>
> z.z.:[(2,5)]+[(7,5)] = [(1,2)]
Auch hier: mach es doch einfach direkt, also benutze $[(2, 5)] + [(7, 5)] = [(2+7, 5+5)] = [(9,10)]$.
Dann musst du nur noch $[(9, 10)] = [(1, 2)]$ verifizieren.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:09 Mo 08.11.2010 | | Autor: | jikz |
"Kannst du das aus den beiden Gleichungen oben herleiten? "
Nein. Aus welchen Gleichungen denn genau? Also ich verstehe das Vorgehen folgermaßen: Ich nehme mir Vertreter aus den jeweiligen Äquivalenzklassen (oder was genau soll das Ganze mit a=a' ?!) & zeige dann dadurch, dass die definierte Addition auch für diese möglich ist & das Ganze somit davon unabhängig ist welche Repräsentanten einer Äquivalenzklasse ich jetzt nehme.
Muss ich nun zeigen, dass beispielsweise [(a',b')] der Äquivalenzklasse [(a,b)] entspricht bzw. (a',b') in Relation zu (a,b) steht??
Sorry, wenn sich das alles arg verplant anhört, aber ich steh grad echt mega auf dem Schlauch.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:21 Mo 08.11.2010 | | Autor: | jikz |
Nein. ich bin auf diese Aufgabe gestoßen und sah mich vor das gleiche Problem gestellt und hatte Fragen dazu. Ich kenn den Topic-Ersteller nicht; Dachte mir aber, da wir das gleiche Problem haben, dass ich mich hier einklinken kann..
|
|
|
| |
|
> Dachte mir aber, da wir das
> gleiche Problem haben, dass ich mich hier einklinken kann..
Hallo,
ja, natürlich!
Das ist sogar erwünscht, denn es hat keiner ein Interesse daran, hier mehrere Diskussionen, die sich um dieselbe Aufgabe drehen, gleichzeitig zu haben.
Guß v. Angela
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:26 Mo 08.11.2010 | | Autor: | felixf |
Moin
> "Kannst du das aus den beiden Gleichungen oben herleiten?
> "
>
> Nein. Aus welchen Gleichungen denn genau?
Aus denen in dieser Zeile: Mach es doch so. Seien $ [(a, b)] = [(a', b')] $ und $ [(c, d)] = [(c', d')] $; dann gilt $ a + b' = a' + b $ und $ c + d' = c' + d $.
> Also ich verstehe
> das Vorgehen folgermaßen: Ich nehme mir Vertreter aus den
> jeweiligen Äquivalenzklassen (oder was genau soll das
> Ganze mit a=a' ?!)
Da steht nirgendwo $a = a'$?
> & zeige dann dadurch, dass die
> definierte Addition auch für diese möglich ist & das
> Ganze somit davon unabhängig ist welche Repräsentanten
> einer Äquivalenzklasse ich jetzt nehme.
Gezeigt wird: nimmt man zwei verschiedene Repraesentanten, kommt bei beiden Moeglichkeiten die selbe Aequivalenzklasse als Ergebis heraus.
> Muss ich nun zeigen, dass beispielsweise [(a',b')] der
> Äquivalenzklasse [(a,b)] entspricht bzw. (a',b') in
> Relation zu (a,b) steht??
Nein, das ist die Annahme. Daraus, und daraus dass $(c, d) [mm] \sim [/mm] (c', d')$ ist, musst du $(a + c, b + d) [mm] \sim [/mm] (a' + c', b' + d')$ folgern.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:49 Do 11.11.2010 | | Autor: | jikz |
Ich bin's wieder.. ich hab jetzt ein wenig probiert und nochmal drüber geschaut und versucht aus folgendem Ansatz
> [mm][(a, b)] = [(a', b')][/mm]
> und [mm][(c, d)] = [(c', d')] [/mm]; dann gilt [mm]a + b' = a' + b[/mm] und > [mm]c + d' = c' + d [/mm].
> [mm](a + c, b + d) \sim (a' + c', b' + d')[/mm]
> [zu] folgern.
indem ich schreibe, dass gilt:
(a,b) ~ (c',d') wenn a+d' = b+c' und (a',b') ~ (c,d) wenn a'+d = b'+c
a + d' - b - c' = 0
a' + d' - b' - c = 0
=> a + d' - b - c' = a' + d' - b' - c
durch umformen dann:
a+c+b'+d' = b+d+a'+c'
und das gilt wenn [(a+c, b+d)] = [(a'+c', b'+d')]
.. so richtig? oder alles quatsch?
falls richtig, dann ist mir aber glaub ich noch nicht ganz bewusst, warum ich ausgerechnet (a,b) und (c',d') in Relation setzen möchte.. hmm..!
Aufgabe 3 werd ich dann später versuchen zu lösen.. Vielen Dank für die Mühe und Hilfe!
|
|
|
| |
|
> Ich bin's wieder.. ich hab jetzt ein wenig probiert und
> nochmal drüber geschaut und versucht aus folgendem Ansatz
>
Hallo,
> > [mm][(a, b)] = [(a', b')][/mm]
> > und [mm][(c, d)] = [(c', d')] [/mm]; dann gilt [mm]a + b' = a' + b[/mm] und >
> [mm]c + d' = c' + d [/mm].
>
> > [mm](a + c, b + d) \sim (a' + c', b' + d')[/mm]
> > [zu] folgern.
Felix hat ja auch schon gesagt, daß hierfür zu zeigen ist: $ [(a + c, b + d)] = [(a' + c', b' + d')] $, also $ (a + c) + (b' + d') = (b + d) + (a' + c') $.
Ist Dir klar, warum man das zeigen muß?
>
> indem ich schreibe, dass gilt:
>
> (a,b) ~ (c',d') wenn a+d' = b+c' und (a',b') ~ (c,d) wenn
> a'+d = b'+c
Das stimmt ja zwar, aber was hat das mit der Aufgabe zu tun?
Es ist doch nirgends die Rede davon, daß man nur gleiche Äquivalenzklassen addieren möchte?
Worum geht es?
Du willst zeigen, daß die folgendermaßen definierte Addition von Äquivalenzklassen wohldefiniert ist: [(a,b)]+[(c,d)]:=[(a+c, b+d)].
Dazu ist zu zeigen, daß sie unabhängig vom jeweils gewählten repräsentanten der Äquivalenzklasse ist, daß also, sofern [(a,b)]=[(a',b')] und [(c,d)]=[(c', d')],
das Ergebnis der Addition der gestricelten Äquivalenzklassen dasselbe ist wie bei der Addition der ungestrichelten. (Sonst wäre die Addition ja ziemlich witzlos...)
Felix hat Dir das Ziel genannt und auch gesagt, was zu zeigen ist.
Mach jetzt eine Gleichungskette
(a + c) + (b' + d') = ...=...=...=...=...=(b + d) + (a' + c').
Vergiß dabei nicht, jeden Schitt, den Du gehst, mit einem bereits bekannten Gesetz zu begründen.
Wenn Du die Gleichungskette hast, folgt hieraus, daß
(a + c, b + d) = (a' + c', b' + d')][(a + c, b + d)] = [(a' + c', b' + d'), also
[(a + c, b + d)] = [(a' + c', b' + d')].
Gruß v. Angela
|
|
|
|
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
einen Account wieder zu löschen (außer ihr könnt beweisen, dass ihr nur im Rahmen einer Gruppenarbeit zu vernünftigen Ergebnissen kommt).
