Äquivalenzklassen / Abbildung < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:52 Sa 17.12.2011 | | Autor: | NeverGod |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo liebe Gemeinschaft,
ich befinde mich nun im Grundstudium und kam bislang ganz gut mit, nur die formalien machen mir zuschaffen. entweder verstehe ich direkt die aufgabe nicht, oder meine lösung ist formal nicht korrekt. :(
Deshalb probiere ich mal den Weg über dieses Forum :)
Aufgabe
Sei die folgende Relation R auf [mm] \IN \times \IN [/mm] gegeben:
(a,b)R(c,d):⇔ a+d = b+c.
Sei ferner M die Menge der Äquivalenzklassen von R auf [mm] \IN \times \IN.
[/mm]
Zeigen Sie:
1. R ist eine Äquivalenzrelation
2.Die Abbildung
f : [mm] \IZ [/mm] → M
f(x)= [mm] f(x)=\begin{cases} (1,1−x) falls x <= 0 \\ (x+1,1) falls x > 0 \end{cases}
[/mm]
ist sowohl injektiv als auch surjektiv.
Ansatz:
Äquivalenzrelation: reflexiv,symmetrisch,transitiv. Die Definitionen kenne ich, den Beweis hatte ich bislang immer ausformuliert, da ich die formale schreibweise noch nicht verstanden habe. Wäre lieb, wenn mir die jmd. schreiben könnte, da das für die Modulprüfung bei mir wichtig wäre die formale schreibweise zu können :).
2. Hier verstehe ich leider die Abbildung nicht. injektiv und surjektiv wäre kla, das ist bijektiv. also genau ein element aus [mm] \IZ [/mm] nach M. Demnach entweder ein Gegenbeispiel oder allgemein beweisen, was wieder formal wäre :(
Bitte um formale Ansätze. Lieb wäre zu sagen, wie man aus der Definition, die ich kann, zum formalen Beweis kommt.
LG NeverGod
|
|
| |
|
> Hallo liebe Gemeinschaft,
> ich befinde mich nun im Grundstudium und kam bislang ganz
> gut mit, nur die formalien machen mir zuschaffen. entweder
> verstehe ich direkt die aufgabe nicht, oder meine lösung
> ist formal nicht korrekt. :(
> Deshalb probiere ich mal den Weg über dieses Forum :)
Hallo,
das ist doch schonmal eine außerordentlich gute Idee!
>
> Aufgabe
>
> Sei die folgende Relation R auf [mm]\IN \times \IN[/mm] gegeben:
> (a,b)R(c,d):⇔ a+d = b+c.
> Sei ferner M die Menge der Äquivalenzklassen von R auf
> [mm]\IN \times \IN.[/mm]
> Zeigen Sie:
>
> 1. R ist eine Äquivalenzrelation
> 2.Die Abbildung
> f : [mm]\IZ[/mm] → M
> [mm]f(x)=\begin{cases} (1,1−x) \quad falls\quad x \le 0 \\
(x+1,1) \quad falls\quad x > 0 \end{cases}[/mm]
>
> ist sowohl injektiv als auch surjektiv.
>
> Ansatz:
>
> Äquivalenzrelation: reflexiv,symmetrisch,transitiv. Die
> Definitionen kenne ich, den Beweis hatte ich bislang immer
> ausformuliert, da ich die formale schreibweise noch nicht
> verstanden habe. Wäre lieb, wenn mir die jmd. schreiben
> könnte, da das für die Modulprüfung bei mir wichtig
> wäre die formale schreibweise zu können :).
Gut.
Wir brauchen jetzt mal dreierlei:
- die Definitionen
- Deinen ausformulierten Beweis
- Deinen Versuch, diesen zu formalisieren.
Wir machen am besten nicht alles auf einmal, sondern beginnen mit der Reflexitivität, damit es nicht
>
> 2. Hier verstehe ich leider die Abbildung nicht. injektiv
> und surjektiv wäre kla, das ist bijektiv. also genau ein
> element aus [mm]\IZ[/mm] nach M. Demnach entweder ein Gegenbeispiel
> oder allgemein beweisen, was wieder formal wäre :(
Hier wäre zunächst mal ganz wichtig, daß Du uns auch verrätst, was M sein soll. Sonst kann man ja überhaupt nicht über Surjektivität und Injektivität befinden.
Liefere die Definitionen von injektiv und surjektiv,
vielleicht auch Deine Interpetation dieser Begriffe und sag' was Du Deiner Meinung nach untersuchen mußt.
Ich denke, daß wir mit dieser etwas aufwendigen Vorgehensweise Dein Ziel am besten erreichen können, denn so sehen wir, ob Du die Begriffe/Definitionen wirklich wiedergeben kannst, sie verstanden hast, und wir können Dir dann bei der Umsetzung Deiner Gedanken in mathematische Schreibweisen helfen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:48 So 18.12.2011 | | Autor: | NeverGod |
| Aufgabe | Wir brauchen jetzt mal dreierlei:
- die Definitionen
- Deinen ausformulierten Beweis
- Deinen Versuch, diesen zu formalisieren.
Wir machen am besten nicht alles auf einmal, sondern beginnen mit der Reflexitivität, damit es nicht |
Also erstmal M: M ist die Menge der Äquivalenzklassen von R auf [mm] \IN \times \IN
[/mm]
Reflexivität: (a,b) [mm] \in [/mm] R so wäre Reflexivität (a,a) [mm] \in [/mm] R => aRa. Hier muss man die gewünschte Relation betrachten und gucken, ob es passt, indem man die Realation anwendet.
In diesem Beispiel: [mm] \forall [/mm] a,b [mm] \in [/mm] R ((a,b),(a,b)) [mm] \in [/mm] R. Ich würde nun den satz hinschreiben, dass a+b = a+b gilt und damit reflexiv sei.
Symmetrie:((a,b),(c,d)) [mm] \in [/mm] R => ((c,d),(a,b)) [mm] \in [/mm] R
(a,b)R(c,d) = (c,d)R(a,b) Da bei einer Gleichung beide Seiten stehts gleich sind, gilt die Symmetrie.
Transitivität: (a,b),(b,c) [mm] \in [/mm] R => (a,c) [mm] \in [/mm] R (allgemein)
((a,b),(c,d)) , ((c,d),(e,f)) [mm] \in [/mm] R => ((a,b),(e,f)) [mm] \in [/mm] R
(das die definition, wenn ich mich nicht irre)
ich würde wieder begründen, da wir eine gleichung haben und (a,b) = (c,d) ist, muss (a,b) = (e,f) gelten. Dies wäre jedoch keineswegs angemessen, dass weiß ich. zu schwammig und kein formaler Beweis. Leider könnte ich es jedoch nicht besser formulieren.
Abbildung: Jedes Element aus dem Urbild wird abgebildet.
Injektivität: Jedes Element aus der Abbildung wird höchstens einmal abgebildet.
Surjektivität: Jedes Element aus der Abbildung wird abgebildet. Mind. einmal
=> Bijektivität, wenn genau ein Element aus dem Urbild abgebildet wird (Injektivität + Surjektivität)
Soweit kann ich es lösen.
wie du siehst, fehlt mir jedoch die richtige schreibweise leider komplett :(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:11 So 18.12.2011 | | Autor: | NeverGod |
Für den zweiten Teil ist es hilfreich zu zeigen, dass für alle (a,b) [mm] \in \IN \times \IN [/mm] es ein c [mm] \in \IN
[/mm]
gibt, sodass entweder (a,b)R(1,c) oder (a,b)R(c,1). Welcher der beiden Fälle eintritt hängt im Wesentlichen davon ab, welche der Zahlen a und b größer ist.
Der Hinweis zur Aufgabe 2.
Leider kann ich damit nichts anfangen :(
|
|
|
| |
|
> Also erstmal M: M ist die Menge der Äquivalenzklassen von
> R auf [mm]\IN \times \IN[/mm]
Hallo,
achso.
Was ist denn eine Äqivalenzklasse?
Welche Elemente sind in M?
Das müßte man sich vor Bearbeitung von Aufg. 2 mal überlegen.
Inwiefern hast Du Dich mit M schon beschäftigt?
Es war auf der Menge [mm] \IN\times \IN [/mm] eine Relation erklärt durch
(a,b)R(c,d):⇔ a+d = b+c.
>
> Reflexivität: (a,b) [mm]\in[/mm] R so wäre Reflexivität (a,a) [mm]\in[/mm]
> R => aRa. Hier muss man die gewünschte Relation betrachten
> und gucken, ob es passt, indem man die Realation anwendet.
>
> In diesem Beispiel: [mm]\forall[/mm] a,b [mm]\in[/mm] R: ((a,b),(a,b)) [mm]\in[/mm] R.
Genau, dies würde gelten, wäre die Relation reflexiv.
Und nun solltest Du nachschauen, ob
(a,b)R(a,b) gilt, indem du die Def. der rRelation R verwendest.
> Ich würde nun den satz hinschreiben, dass a+b = a+b gilt
> und damit reflexiv sei.
Das ist zu ungenau. Du mußt jeden Schritt begründen:
Für alle [mm] a,b\in \IN [/mm] gilt:
(a,b)R(a,b) <==> a+b=b+a (nach Def. von R)
=a+b (die Addition in [mm] \IN [/mm] ist kommutativ.
Also ist R reflexiv.
>
> Symmetrie:((a,b),(c,d)) [mm]\in[/mm] R => ((c,d),(a,b)) [mm]\in[/mm] R
Bew.:
Sei ((a,b),(c,d)) [mm] $\in$ [/mm] R, dh. (a,b)R(c,d)
<==> Defininition der Relation verwenden
<==> Eigenschaften des Rechnens in den nat. Zahlen verwenden
<==> (c,d)R(a,b)
Also ist die Relation reflexiv.
>
> Transitivität: (a,b),(b,c) [mm]\in[/mm] R => (a,c) [mm]\in[/mm] R
> (allgemein)
>
> ((a,b),(c,d)) , ((c,d),(e,f)) [mm]\in[/mm] R => ((a,b),(e,f)) [mm]\in[/mm] R
> (das die definition, wenn ich mich nicht irre)
Ja.
Hier machen wir weiter, wenn die Symmetrie steht.
>
> ich würde wieder begründen, da wir eine gleichung haben
> und (a,b) = (c,d) ist, muss (a,b) = (e,f) gelten. Dies
> wäre jedoch keineswegs angemessen, dass weiß ich. zu
> schwammig und kein formaler Beweis. Leider könnte ich es
> jedoch nicht besser formulieren.
>
> Abbildung: Jedes Element aus dem Urbild wird abgebildet.
in eindeutiger Weise.
> Injektivität: Jedes Element aus der Abbildung wird
> höchstens einmal abgebildet.
Unfug! Jedes Element des Bildes hat genau ein Urbild, bzw, auf jedes Element der Wertebereiches wird höchstens ein Element dies Definitionsbereiches abgebildet.
Handlich: [mm] f(x_1)=f(x_2) [/mm] ==> [mm] x-1=x_2
[/mm]
> Surjektivität: Jedes Element aus der Abbildung wird
> abgebildet. Mind. einmal
Blödsinn!
Auf jedes Element des Wertebereiches wird (mindestens ) ein Element des Definitionsbereiches abgebildet.
dh [mm] f:D\to [/mm] W ist surjektiv <==>
(für alle [mm] w\in [/mm] W gibt es ein [mm] d\in [/mm] D mit f(d)=w.)
>
> => Bijektivität, wenn genau ein Element aus dem Urbild
> abgebildet wird (Injektivität + Surjektivität)
Quatsch!
Auf jedes Elemet des Wertebereiches wird genau ein Element des Definitionsbereiches abgebildet.
Ansonsten: s. o.
Gruß v. Angela
>
> Soweit kann ich es lösen.
> wie du siehst, fehlt mir jedoch die richtige schreibweise
> leider komplett :(
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:08 Mi 21.12.2011 | | Autor: | NeverGod |
| Aufgabe | > Symmetrie:((a,b),(c,d)) $ [mm] \in [/mm] $ R => ((c,d),(a,b)) $ [mm] \in [/mm] $ R
Bew.:
Sei ((a,b),(c,d)) $ [mm] \in [/mm] $ R, dh. (a,b)R(c,d)
<==> Defininition der Relation verwenden
<==> Eigenschaften des Rechnens in den nat. Zahlen verwenden
<==> (c,d)R(a,b) |
Okay, dann wäre die Symmetrie, wenn ich das Schema aus der Reflexion benutze...
Symmetrie:((a,b),(c,d)) $ [mm] \in [/mm] $ R => ((c,d),(a,b)) $ [mm] \in [/mm] $ R
Bew.:
Sei ((a,b),(c,d)) $ [mm] \in [/mm] $ R, dh. (a,b)R(c,d)
a+d=b+c => c+b=d+a
aufgrund der kommutativität die in [mm] \IN [/mm] gilt: c+b=a+d
<==> (c,d)R(a,b)
Transitivitaet wäre dann:
((a,b),(c,d),(e,f)) [mm] \in [/mm] R gilt: (a,b)R(c,d) und (c,d)R(e,f), dann gilt auch (a,b)R(e,f)
Bew.:
((a,b),(c,d)) [mm] \in [/mm] R => a+d=b+c
((c,d),(e,f)) [mm] \in [/mm] R => c+f=d+e
=>
((a,b),(e,f)) [mm] \in [/mm] R => a+f=b+e
<=> (a,b)R(e,f)
Injektivität: $f(x)=f(y) => x=y $
kann damit hier leider wenig anfangen :(
hatte nen anderen ansatz, dass a-b = x ist, wenn man eines der fälle annimmt und für c und d die zahlen aus f(x) einsetzt, kommt das heraus. und daran erkennt man, dass alle ergebnisse (1,c) oder (c,1) sind. und alle elemente kommen nur einmal vor. aber jede auch genau einmal. ich gehe von der differenz mal aus. die differenz der beiden zahlen ist ja immer unterschiedlich abhängig von den zahlen die ich einsetze. und abhängig ob a oder b größer ist tritt der erste oder zweite fall ein. also logisch betrachtet verstehe ich die funktion. nur weiß ich leider nicht wie ich das aufschreiben kann :(
LG NeverGod
Surjektivität: Sei y [mm] \in [/mm] R ...
|
|
|
| |
|
>
> Okay, dann wäre die Symmetrie, wenn ich das Schema aus der
> Reflexion benutze...
>
Hallo,
zu zeigen:
> Symmetrie:((a,b),(c,d)) [mm]\in[/mm] R => ((c,d),(a,b)) [mm]\in[/mm] R
>
> Bew.:
> Sei ((a,b),(c,d)) [mm]\in[/mm] R, dh. (a,b)R(c,d)
>
Also ist nach Def. der Relation
> a+d=b+c => c+b=d+a
>
> aufgrund der kommutativität die in [mm]\IN[/mm] gilt: c+b=a+d
>
> <==> (c,d)R(a,b) ,
also ((c,d), [mm] (a,b))\in [/mm] R.
>
> Transitivitaet wäre dann:
>
Für
> (a,b),(c,d),(e,f) [mm]\in[/mm] [mm] [s]R[/s]\IN\times \INgilt:
[/mm]
wenn
>(a,b)R(c,d) und
> (c,d)R(e,f), dann gilt auch (a,b)R(e,f)
>
> Bew.:
> ((a,b),(c,d)) [mm]\in[/mm] R => a+d=b+c
> ((c,d),(e,f)) [mm]\in[/mm] R => c+f=d+e
> =>
> ((a,b),(e,f)) [mm]\in[/mm] R => a+f=b+e
Nein, so schnell folgt das nicht.
Du müßtest schon ein wenig andeuten, wie man auf die Gleichung a+f=b+e kommt, und daraus folgt dann ja erst, daß ((a,b),(e,f)) [mm] $\in$ [/mm] R.
Gruß v. Angela
> <=> (a,b)R(e,f)
>
> Injektivität: [mm]f(x)=f(y) => x=y[/mm]
> kann damit hier leider
> wenig anfangen :(
> hatte nen anderen ansatz, dass a-b = x ist, wenn man eines
> der fälle annimmt und für c und d die zahlen aus f(x)
> einsetzt, kommt das heraus. und daran erkennt man, dass
> alle ergebnisse (1,c) oder (c,1) sind. und alle elemente
> kommen nur einmal vor. aber jede auch genau einmal. ich
> gehe von der differenz mal aus. die differenz der beiden
> zahlen ist ja immer unterschiedlich abhängig von den
> zahlen die ich einsetze. und abhängig ob a oder b größer
> ist tritt der erste oder zweite fall ein. also logisch
> betrachtet verstehe ich die funktion. nur weiß ich leider
> nicht wie ich das aufschreiben kann :(
>
> LG NeverGod
>
> Surjektivität: Sei y [mm]\in[/mm] R ...
>
|
|
|
| |
|
| Aufgabe | > Sei die folgende Relation R auf [mm] \IN \times \IN [/mm] gegeben:
> (a,b)R(c,d):⇔ a+d = b+c.
> Sei ferner M die Menge der Äquivalenzklassen von R auf
> [mm] \IN \times \IN. [/mm]
> Zeigen Sie:
>
> Die Abbildungbeschreibung
> f : [mm] \IZ [/mm] → M
> [mm] f(x)=\begin{cases} \green{[}1,1-x)\green{]} \quad falls\quad x \le 0 \\
\green{[}(x+1,1\green{]} \quad falls\quad x > 0 \end{cases} [/mm]
>
> ist sowohl injektiv als auch surjektiv. |
Hallo,
ich hatte das zuvor übersehen: bei der Abbildungen mußten noch die eingefügten Klammern hin oder ähnliches, denn die Funktionswerte sind ja keine Paare des [mm] \IN\times\IN [/mm] , sondern Restklassen. Wie schreibt Ihr die?
Was weißt Du allgemein über Restklassen? Welche Elemente sind da drin?
Woran erkennt man, ob [a]=[b]?
Hast Du Dich auch bereits speziell mit den Restklassen von M beschäftigt? Ich hatte schonmal gefragt, aber keine Antwort gesehen.
> Injektivität: [mm]f(x)=f(y) => x=y[/mm]
> kann damit hier leider
> wenig anfangen :(
Hier steht, daß eine Funktion f injektiv ist, wenn daraus, daß die Funktionswerte gleich sind, zwingend die Gleichheit der Argumente folgt.
Wo liegt hier Dein Problem? Warum kannst Du nichts damit anfangen?
> hatte nen anderen ansatz, dass a-b = x ist, wenn man eines
> der fälle annimmt und für c und d die zahlen aus f(x)
> einsetzt, kommt das heraus.
Das ist nicht zu verstehen.
Mal gucken, ob ich es trotzdem verstehe:
Du nimmst ein Zahlenpaar (a,b) und sagst x:=a-b.
Was meinst Du mit "wenn man einen der Fälle annimmt." Von welchen Fall redest Du, und was hat das mit dem x zu tun?
Dann berechnest Du f(x), sagst (c,d):=f(x)?
> und daran erkennt man, dass
> alle ergebnisse (1,c) oder (c,1) sind
Wie erkennt man das jetzt genau?
> alle elemente
Was meinst Du jetzt mit alle Elemente?
Welches sind denn die Elemente von M?
> kommen nur einmal vor. aber jede auch genau einmal. ich
> gehe von der differenz mal aus. die differenz der beiden
> zahlen ist ja immer unterschiedlich abhängig von den
> zahlen die ich einsetze. und abhängig ob a oder b größer
> ist tritt der erste oder zweite fall ein. also logisch
> betrachtet verstehe ich die funktion. nur weiß ich leider
> nicht wie ich das aufschreiben kann :(
Und das mit der Beschreibung klappt auch nicht besonders gut...
Und mit diffusen Erzählungen können wir natürlich keinen Beweis führen.
Vielleicht entdeckst Du, in dem Beweis, den wir jetzt entwickeln werden, einige Deiner Gedanken wieder.
Zunächst einmal ist entscheidend, daß Du begreifst, daß man für Injektivität zeigen muß
f(x)=f(y) ==> x=y.
Zu jedem Funktionswert kann nur ein Argument gehören.
Beh.: f ist injektiv
dh. f(x)=f(y) ==> x=y.
Bew: Seien x,y [mm] \in \IZ [/mm] mit f(x)=f(y).
1. Fall: [mm] x\le [/mm] 0, [mm] y\le [/mm] 0
2. Fall: [mm] x\le [/mm] 0, y>0
3. Fall: [mm] x>0,y\le [/mm] 0
4. Fall: x>0, y>0
Diese Fälle kannst du nun ja mal getrennt untersuchen
> Surjektivität: Sei y [mm]\in[/mm] R ...
???
Für Surjektivität mußt Du zeigen, daß Du zu jeder Restklasse aus M ein Element aus [mm] \IZ [/mm] findest, welches darauf abgebildet wird.
Sei also [mm] [(a,b)]\in [/mm] M.
Nun mußt Du sagen, welches Element darauf abgebildet wird.
Gruß v. Angela
|
|
|
|
