Äquivalenzklassen bestimmen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Aufgabe:
Für alle a,b,c,d∈N
Sei R⊆(N×N)×(N×N) definiert durch
(a,b) R (c,d)⇔ a+d=c+b
Zeigen Sie, dass dies eine Äquivalenzrelation auf M ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
---
Die Reflexivität, Symmetrie und Transitivität habe ich bereits nachgewiesen.
reflexiv:
(a,b) R (a,b) , da a+b=b+a
Symmetrie:
Sei (a,b) R (c,d) ⇒
a+d=c+b ⇒^(Symmetrie von "=")
c+b=a+d ⇒
(c,d) R (a,b)
Trans:
a+d=c+b ∧ c+f=e+d ⇒
a+d+c+f=c+b+e+d ⇒^(-(d+c) ) □( )
a+f=e+b ⇒
(a,b) R (e,f)
Nun stellt sich mir die Frage wie man die zugehörigen Äquivalenzklassen zu der Relation aussehen.
Vielen Dank im Voraus Leute
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:33 Mi 12.08.2015 | | Autor: | Marc |
Hallo sarah_0815,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
> Aufgabe:
> Für alle a,b,c,d∈N
> Sei R⊆(N×N)×(N×N) definiert durch
> (a,b) R (c,d)⇔ a+d=c+b
>
> Zeigen Sie, dass dies eine Äquivalenzrelation auf M ist.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
> ---
> Die Reflexivität, Symmetrie und Transitivität habe ich
> bereits nachgewiesen.
> reflexiv:
> (a,b) R (a,b) , da a+b=b+a
>
> Symmetrie:
> Sei (a,b) R (c,d) ⇒
> a+d=c+b ⇒^(Symmetrie von "=")
> c+b=a+d ⇒
> (c,d) R (a,b)
>
> Trans:
> a+d=c+b ∧ c+f=e+d ⇒
> a+d+c+f=c+b+e+d ⇒^(-(d+c) ) □( )
> a+f=e+b ⇒
> (a,b) R (e,f)
Das sieht gut aus.
> Nun stellt sich mir die Frage wie man die zugehörigen
> Äquivalenzklassen zu der Relation aussehen.
Dir ist hoffentlich klar, dass lt. Aufgabenstellung danach eigentlich nicht gefragt ist, aber ich nehme an, es handelt sich um eine weitere Teilaufgabe.
Eine Möglichkeit, sich der Lösung zu nähern, ist durch Ausprobieren. Versuche doch mal, mehrere äquivalente Paare, z.B. zu
(1,5) R ... R ... R ...
und
(9,3) R ... R ... R ...
(gerne noch mehr)
Was fällt dir auf, wenn du eine Zeile mit äquivalenten Paaren anschaust? Wenn dir da eine Eigenschaft auffällt, die diese Paare erfüllen, dann kannst du deine Vermutung formalisieren und beweisen.
Übrigens ist diese Äquivalenzrelation eine Möglichkeit, die Zahlenmenge [mm] $\IN$ [/mm] zu erweitern...
Viele Grüße
Marc
|
|
|
| |
|
| Aufgabe | > Aufgabe:
> Für alle a,b,c,d∈N
> Sei R⊆(N×N)×(N×N) definiert durch
> (a,b) R (c,d)⇔ a+d=c+b
>
> Zeigen Sie, dass dies eine Äquivalenzrelation auf M ist.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
> ---
> Die Reflexivität, Symmetrie und Transitivität habe ich
> bereits nachgewiesen.
> reflexiv:
> (a,b) R (a,b) , da a+b=b+a
>
> Symmetrie:
> Sei (a,b) R (c,d) ⇒
> a+d=c+b ⇒^(Symmetrie von "=")
> c+b=a+d ⇒
> (c,d) R (a,b)
>
> Trans:
> a+d=c+b ∧ c+f=e+d ⇒
> a+d+c+f=c+b+e+d ⇒^(-(d+c) ) □( )
> a+f=e+b ⇒
> (a,b) R (e,f)
Das sieht gut aus.
> Nun stellt sich mir die Frage wie man die zugehörigen
> Äquivalenzklassen zu der Relation aussehen.
Dir ist hoffentlich klar, dass lt. Aufgabenstellung danach eigentlich nicht gefragt ist, aber ich nehme an, es handelt sich um eine weitere Teilaufgabe.
Eine Möglichkeit, sich der Lösung zu nähern, ist durch Ausprobieren. Versuche doch mal, mehrere äquivalente Paare, z.B. zu
(1,5) R ... R ... R ...
und
(9,3) R ... R ... R ...
(gerne noch mehr)
Was fällt dir auf, wenn du eine Zeile mit äquivalenten Paaren anschaust? Wenn dir da eine Eigenschaft auffällt, die diese Paare erfüllen, dann kannst du deine Vermutung formalisieren und beweisen.
Übrigens ist diese Äquivalenzrelation eine Möglichkeit, die Zahlenmenge $ [mm] \IN [/mm] $ zu erweitern...
Viele Grüße
Marc |
Also ich würde meinen dass
[a]= alles positiven Zahlen aus N repäsentiert.
Welche Eigenschaft meinst du ? Ich stehe echt auf dem Schlauch
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:52 Mi 12.08.2015 | | Autor: | Marc |
> Also ich würde meinen dass
>
> [a]= alles positiven Zahlen aus N repäsentiert.
?
> Welche Eigenschaft meinst du ? Ich stehe echt auf dem
> Schlauch
Finde doch mal zu (1,5) ein äquivalentes Paar.
Ist z.B. (1,5) R (2,3) ? (nein, aber warum nicht?)
(1,5) R (2,4) ?
(1,5) R (2,5) ?
(1,5) R (2,6) ?
...
|
|
|
| |
|
| Aufgabe | > Also ich würde meinen dass
>
> [a]= alles positiven Zahlen aus N repäsentiert.
?
> Welche Eigenschaft meinst du ? Ich stehe echt auf dem
> Schlauch
Finde doch mal zu (1,5) ein äquivalentes Paar.
Ist z.B. (1,5) R (2,3) ? (nein, aber warum nicht?)
(1,5) R (2,4) ?
(1,5) R (2,5) ?
(1,5) R (2,6) ?
... |
Wenn (1,5) R (2,3) dann würde 4=7 sein, das geht nicht.
Aber wenn a=c und b=d sind dann könnte es aufgehen oder a=b=c=d sind gleich.
Aber ich weiß immernoch nicht wie die Äquivalenzklassen aussehen :(
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:13 Mi 12.08.2015 | | Autor: | abakus |
> > Also ich würde meinen dass
> >
> > [a]= alles positiven Zahlen aus N repäsentiert.
>
> ?
>
>
> > Welche Eigenschaft meinst du ? Ich stehe echt auf dem
> > Schlauch
>
> Finde doch mal zu (1,5) ein äquivalentes Paar.
> Ist z.B. (1,5) R (2,3) ? (nein, aber warum nicht?)
> (1,5) R (2,4) ?
> (1,5) R (2,5) ?
> (1,5) R (2,6) ?
> ...
> Wenn (1,5) R (2,3) dann würde 4=7 sein, das geht
> nicht.
>
> Aber wenn a=c und b=d sind dann könnte es aufgehen oder
> a=b=c=d sind gleich.
>
> Aber ich weiß immernoch nicht wie die Äquivalenzklassen
> aussehen :(
Hallo,
in keiner der vier vorgestellten Möglichkeiten gilt a=b=c=d.
Ausflüchte in "günstige" Sonderfälle verhindern manchmal den Erkenntnisgewinn.
Spiele wirklich die vier Möglichkeiten durch, dann sehen wir weiter.
Gruß Abakus
|
|
|
| |
|
| Aufgabe | > > Also ich würde meinen dass
> >
> > [a]= alles positiven Zahlen aus N repäsentiert.
>
> ?
>
>
> > Welche Eigenschaft meinst du ? Ich stehe echt auf dem
> > Schlauch
>
> Finde doch mal zu (1,5) ein äquivalentes Paar.
> Ist z.B. (1,5) R (2,3) ? (nein, aber warum nicht?)
> (1,5) R (2,4) ?
> (1,5) R (2,5) ?
> (1,5) R (2,6) ?
> ...
> Wenn (1,5) R (2,3) dann würde 4=7 sein, das geht
> nicht.
>
> Aber wenn a=c und b=d sind dann könnte es aufgehen oder
> a=b=c=d sind gleich.
>
> Aber ich weiß immernoch nicht wie die Äquivalenzklassen
> aussehen :(
Hallo,
in keiner der vier vorgestellten Möglichkeiten gilt a=b=c=d.
Ausflüchte in "günstige" Sonderfälle verhindern manchmal den Erkenntnisgewinn.
Spiele wirklich die vier Möglichkeiten durch, dann sehen wir weiter. |
Okay, also folgendes erhalte ich
(1,5) R (2,3) nein, weil 4=7
(1,5) R (2,4) nein , weil 5=7
(1,5) R (2,5) nein, weil 6=7
(1,5) R (2,6) ja, weil 7=7
(1,5) R (3,7) ja, weil 8=8
(1,5) R (4,8) ja weil 9=9
(2,5) R (3,6) ja, weil 8=8
(2,5) R (3,7) ja, weil 9=9
Ich erkenne ,dass bei (1,5) R (2,6) (c=a+1,d=b+1) und für die daraufolgenden sich immer um 1 erhöht.
Was nun
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:17 Mi 12.08.2015 | | Autor: | abakus |
> > > Also ich würde meinen dass
> > >
> > > [a]= alles positiven Zahlen aus N repäsentiert.
>
> >
> > ?
>
> >
> >
> > > Welche Eigenschaft meinst du ? Ich stehe echt auf dem
> > > Schlauch
>
> >
> > Finde doch mal zu (1,5) ein äquivalentes Paar.
> > Ist z.B. (1,5) R (2,3) ? (nein, aber warum nicht?)
> > (1,5) R (2,4) ?
> > (1,5) R (2,5) ?
> > (1,5) R (2,6) ?
> > ...
> > Wenn (1,5) R (2,3) dann würde 4=7 sein, das geht
> > nicht.
>
> >
> > Aber wenn a=c und b=d sind dann könnte es aufgehen
> oder
> > a=b=c=d sind gleich.
>
> >
> > Aber ich weiß immernoch nicht wie die
> Äquivalenzklassen
> > aussehen :(
>
> Hallo,
> in keiner der vier vorgestellten Möglichkeiten gilt
> a=b=c=d.
> Ausflüchte in "günstige" Sonderfälle verhindern
> manchmal den Erkenntnisgewinn.
> Spiele wirklich die vier Möglichkeiten durch, dann sehen
> wir weiter.
> Okay, also folgendes erhalte ich
> (1,5) R (2,3) nein, weil 4=7
> (1,5) R (2,4) nein , weil 5=7
> (1,5) R (2,5) nein, weil 6=7
>
> (1,5) R (2,6) ja, weil 7=7
> (1,5) R (3,7) ja, weil 8=8
> (1,5) R (4,8) ja weil 9=9
>
> (2,5) R (3,6) ja, weil 8=8
> (2,5) R (3,7) ja, weil 9=9
>
>
> Ich erkenne ,dass bei (1,5) R (2,6) (c=a+1,d=b+1) und
> für die daraufolgenden sich immer um 1 erhöht.
>
> Was nun
>
Du setzt jetzt c in Beziehung zu a und d in Beziehung zu b. Schau mal INNERHALB eines Paares (a,b) nach. Gibt es zwischen a und b eine Beziehung, die sich auf c und d übertragen lässt?
Dafür wäre übrigens nicht einmal die Suche nach solchen äquivalenten Paaren erforderlich gewesen.
Stelle die Gleichung a+d=b+c einfach mal so um, dass a und b auf einer Seite und c und d auf der anderen stehen.
|
|
|
| |
|
| Aufgabe | > > > Also ich würde meinen dass
> > >
> > > [a]= alles positiven Zahlen aus N repäsentiert.
>
> >
> > ?
>
> >
> >
> > > Welche Eigenschaft meinst du ? Ich stehe echt auf dem
> > > Schlauch
>
> >
> > Finde doch mal zu (1,5) ein äquivalentes Paar.
> > Ist z.B. (1,5) R (2,3) ? (nein, aber warum nicht?)
> > (1,5) R (2,4) ?
> > (1,5) R (2,5) ?
> > (1,5) R (2,6) ?
> > ...
> > Wenn (1,5) R (2,3) dann würde 4=7 sein, das geht
> > nicht.
>
> >
> > Aber wenn a=c und b=d sind dann könnte es aufgehen
> oder
> > a=b=c=d sind gleich.
>
> >
> > Aber ich weiß immernoch nicht wie die
> Äquivalenzklassen
> > aussehen :(
>
> Hallo,
> in keiner der vier vorgestellten Möglichkeiten gilt
> a=b=c=d.
> Ausflüchte in "günstige" Sonderfälle verhindern
> manchmal den Erkenntnisgewinn.
> Spiele wirklich die vier Möglichkeiten durch, dann sehen
> wir weiter.
> Okay, also folgendes erhalte ich
> (1,5) R (2,3) nein, weil 4=7
> (1,5) R (2,4) nein , weil 5=7
> (1,5) R (2,5) nein, weil 6=7
>
> (1,5) R (2,6) ja, weil 7=7
> (1,5) R (3,7) ja, weil 8=8
> (1,5) R (4,8) ja weil 9=9
>
> (2,5) R (3,6) ja, weil 8=8
> (2,5) R (3,7) ja, weil 9=9
>
>
> Ich erkenne ,dass bei (1,5) R (2,6) (c=a+1,d=b+1) und
> für die daraufolgenden sich immer um 1 erhöht.
>
> Was nun
>
Du setzt jetzt c in Beziehung zu a und d in Beziehung zu b. Schau mal INNERHALB eines Paares (a,b) nach. Gibt es zwischen a und b eine Beziehung, die sich auf c und d übertragen lässt?
Dafür wäre übrigens nicht einmal die Suche nach solchen äquivalenten Paaren erforderlich gewesen.
Stelle die Gleichung a+d=b+c einfach mal so um, dass a und b auf einer Seite und c und d auf der anderen stehen. |
Wenn ich die Gleichung a+d=b+c umstelle erhalte ich d-c =b-a .
Die Beziehung die ich sehe ist ,dass a ist ungleich b und b>a.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:55 Mi 12.08.2015 | | Autor: | abakus |
> > > > Also ich würde meinen dass
> > > >
> > > > [a]= alles positiven Zahlen aus N repäsentiert.
>
> >
> > >
> > > ?
>
> >
> > >
> > >
> > > > Welche Eigenschaft meinst du ? Ich stehe echt auf
> dem
> > > > Schlauch
>
> >
> > >
> > > Finde doch mal zu (1,5) ein äquivalentes Paar.
> > > Ist z.B. (1,5) R (2,3) ? (nein, aber warum nicht?)
> > > (1,5) R (2,4) ?
> > > (1,5) R (2,5) ?
> > > (1,5) R (2,6) ?
> > > ...
> > > Wenn (1,5) R (2,3) dann würde 4=7 sein, das geht
> > > nicht.
>
> >
> > >
> > > Aber wenn a=c und b=d sind dann könnte es aufgehen
> > oder
> > > a=b=c=d sind gleich.
>
> >
> > >
> > > Aber ich weiß immernoch nicht wie die
> > Äquivalenzklassen
> > > aussehen :(
>
> >
> > Hallo,
> > in keiner der vier vorgestellten Möglichkeiten gilt
> > a=b=c=d.
> > Ausflüchte in "günstige" Sonderfälle verhindern
> > manchmal den Erkenntnisgewinn.
> > Spiele wirklich die vier Möglichkeiten durch, dann
> sehen
> > wir weiter.
> > Okay, also folgendes erhalte ich
> > (1,5) R (2,3) nein, weil 4=7
> > (1,5) R (2,4) nein , weil 5=7
> > (1,5) R (2,5) nein, weil 6=7
>
> >
> > (1,5) R (2,6) ja, weil 7=7
> > (1,5) R (3,7) ja, weil 8=8
> > (1,5) R (4,8) ja weil 9=9
>
> >
> > (2,5) R (3,6) ja, weil 8=8
> > (2,5) R (3,7) ja, weil 9=9
>
> >
> >
> > Ich erkenne ,dass bei (1,5) R (2,6) (c=a+1,d=b+1) und
> > für die daraufolgenden sich immer um 1 erhöht.
>
> >
> > Was nun
>
> >
> Du setzt jetzt c in Beziehung zu a und d in Beziehung zu
> b. Schau mal INNERHALB eines Paares (a,b) nach. Gibt es
> zwischen a und b eine Beziehung, die sich auf c und d
> übertragen lässt?
> Dafür wäre übrigens nicht einmal die Suche nach solchen
> äquivalenten Paaren erforderlich gewesen.
> Stelle die Gleichung a+d=b+c einfach mal so um, dass a und
> b auf einer Seite und c und d auf der anderen stehen.
>
>
> Wenn ich die Gleichung a+d=b+c umstelle erhalte ich d-c
> =b-a .
> Die Beziehung die ich sehe ist ,dass a ist ungleich b und
> b>a.
Ich sehe, dass b-a die gleiche Differenz ergibt wie d-c. Das Paar (a,b) soll zu (c,d) äquivalent sein, damit haben wir jetzt das Äquvalenz-"merkmal" und damit die Ä.-Klassen.
Alle Paare mit der gleichen Differenz sind äquivalent zueinander.
|
|
|
| |
|
| Aufgabe | >
> >
> Du setzt jetzt c in Beziehung zu a und d in Beziehung zu
> b. Schau mal INNERHALB eines Paares (a,b) nach. Gibt es
> zwischen a und b eine Beziehung, die sich auf c und d
> übertragen lässt?
> Dafür wäre übrigens nicht einmal die Suche nach solchen
> äquivalenten Paaren erforderlich gewesen.
> Stelle die Gleichung a+d=b+c einfach mal so um, dass a und
> b auf einer Seite und c und d auf der anderen stehen.
>
>
> Wenn ich die Gleichung a+d=b+c umstelle erhalte ich d-c
> =b-a .
> Die Beziehung die ich sehe ist ,dass a ist ungleich b und
> b>a.
Ich sehe, dass b-a die gleiche Differenz ergibt wie d-c. Das Paar (a,b) soll zu (c,d) äquivalent sein, damit haben wir jetzt das Äquvalenz-"merkmal" und damit die Ä.-Klassen.
Alle Paare mit der gleichen Differenz sind äquivalent zueinander. |
Aso, ich habe es nun verstanden vielen lieben dank für deine Geduld und deine Hilfe Abakus. Auch danke an Marc
Meine Professorin meinte diese Äquivalenzklassen spielen in der Mathematik eine große Rolle, kannst du dir vorstellen was sie damit gemeint hat?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:42 Mi 12.08.2015 | | Autor: | Marc |
> Aso, ich habe es nun verstanden vielen lieben dank für
> deine Geduld und deine Hilfe Abakus. Auch danke an Marc
Nochmal der Vollständigkeit halber:
Eine Äquivalenzklasse ist eindeutig durch die Differenz der Paareinträge bestimmt, so ist z.B.
[(1,5)]={ (0,4), (1,5), (2,6), (3,7),... } (falls bei euch die Null zu [mm] $\IN$ [/mm] gehört)
bzw.
[(1,5)]={ (1,5), (2,6), (3,7),... } (falls bei euch die Null nicht zu [mm] $\IN$ [/mm] gehört)
> Meine Professorin meinte diese Äquivalenzklassen spielen
> in der Mathematik eine große Rolle, kannst du dir
> vorstellen was sie damit gemeint hat?
Ja, das hatte ich doch schon in meiner ersten Antwort angedeutet.
Die Äquivalenzklasse oben steht doch sozusagen für "-4", da dies die Eigenschaft ist, die alle Elemente der Klasse gemeinsam haben.
Wenn du alle Äquivalenzklassen betrachtest, dann kommen doch genau die ganzen Zahlen als heraus. Das heißt, wenn die Menge der natürlichen Zahlen [mm] $\IN$ [/mm] bekannt ist, kann man durch deine Äquivalenzrelation darauf aufbauend die Menge der ganzen Zahlen sauber definieren:
[mm] $\IZ:=$Menge [/mm] aller Äquivalenzklassen bzgl. R, also
[mm] $\IZ=\{\ldots,\underbrace{[(1,3)]}_{=:-2},\underbrace{[(1,2)]}_{=:-1},\underbrace{[(1,1)]}_{=:0},\underbrace{[(2,1)]}_{=:1},\underbrace{[(3,1)]}_{=:2},\ldots\}$
[/mm]
Ebenso kann man nun darauf aufbauend die rationalen Zahlen durch eine Äquivalenzrelation erhalten.
|
|
|
|
