Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Auf der Menge A={0....9}x{0....9} ist folgende Äquivalenzrelation R definiert:
[mm] ((n_{1},m_{1}),(n_{2},m_{2})\in [/mm] R genau dann, wenn [mm] n_{1} \equiv n_{2}(mod3) [/mm] und [mm] m_{1} \equiv m_{2}(mod3)
[/mm]
a)
n = 7
m = 8
Aus wie vielen Elementen besteht die Äquivalenzklasse bezüglich R, in der (n,m) liegt ?
b)
Für welchen Wert k ist R auch eine Halbordnung ? |
Hallo!
Ich habe riesen Probleme beim Verständnis dieser Zeile
[mm] ((n_{1},m_{1}),(n_{2},m_{2})\in [/mm] R
A={0....9}x{0....9}
bedeutet ich verknüpfe jedes Element mit sich selbst
(0 0) (0 1) ....... (0 9)
(1 0) (1 1).........(1 9)
(2 0) (2 1).........(2 9)
usw.........................
[mm] n_{1} \equiv n_{2}(mod3)
[/mm]
bedeutet die Differenz zwischen [mm] n_{1} [/mm] und [mm] n_{2} [/mm] und diesen Wert mod3
0 - 0 mod 3 = 0
1 - 0 mod 3 = 1
2 - 0 mod 3 = 2
3 - 0 mod 3 = 3
usw.......
Für n = 7
Würde ich sagen gibt es folgende Mengen:
(0 0) (0 3) (0 6)
(1 1) (1 4) (1 7)
(2 2) (2 5)
(3 0) (3 3) (3 6)
(4 1) (4 4) (4 7)
(5 2) (5 5)
(6 0) (6 3) (6 6)
(7 1) (7 4) (7 7)
Für m = 8
(0 0) (0 3) (0 6)
(1 1) (1 4) (1 7)
(2 2) (2 5) (2 8)
(3 0) (3 3) (3 6)
(4 1) (4 4) (4 7)
(5 2) (5 5) (5 8)
(6 0) (6 3) (6 6)
(7 1) (7 4) (7 7)
(8 2) (8 5) (8 8)
Stimmt das soweit ?
Mfg
Frankster
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:58 Fr 19.05.2006 | | Autor: | Frankster |
Könnte es vielleicht 3 Äquivalenzklassen geben ?
(0,3,6)
(1 4 7)
(2 5 8)
Oder gehört der 9er auch noch rein ?
(0 3 6 9)????
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:16 Fr 19.05.2006 | | Autor: | piet.t |
Hallo Frankster,
>
> A={0....9}x{0....9}
> bedeutet ich verknüpfe jedes Element mit sich selbst
An dieser Stelle wird ja eigentlich nichts "verknüpft", es werden einfach Paare gebildet, wo das erste Element aus {0...9} und auch das zweite Element aus {0...9} stammt.
> (0 0) (0 1) ....... (0 9)
> (1 0) (1 1).........(1 9)
> (2 0) (2 1).........(2 9)
> usw.........................
>
Aber das ist wieder richtig, oben wahr vielleicht nur die Formulierung etwas unglücklich.
> [mm]n_{1} \equiv n_{2}(mod3)[/mm]
> bedeutet die Differenz zwischen
> [mm]n_{1}[/mm] und [mm]n_{2}[/mm] und diesen Wert mod3
>
Von einer Differenz sehe ich hier erst mal nichts - [mm] n_1 [/mm] und [mm] n_2 [/mm] sind einfach mod3 zu vergleichen, d.h. es ist zu prüfen, ob sie bei Division durch 3 den gleichen Rest ergeben.
Bezüglich der gegebenen Relation wird es dann etwas unübersichtlich, ich versuche daher mal ein paar Sätze darüber zu verlieren:
Die Relation R "vergleicht" zwei Zahlenpaare aus A miteinander. Wenn [mm] ((n_1,m_1) ,(n_2,m_2)) [/mm] (hier haben wir also in "Paar von Paaren"...) in R liegt schreibt man oft auch (etwas) kürzer [mm] (n_1,m_1)R(n_2,m_2). [/mm] Ist R eine Äquivalenzrelation sagt man auch [mm] (n_1,m_1) [/mm] und [mm] (n_2,m_2) [/mm] sind äquivalent bezüglich R.
Die Definition der Relation liefert dann die Verfahrensvorschrift wie man prüfen kann, ob [mm] (n_1,m_1)R(n_2,m_2). [/mm]
Beispiel: Prüfe die Äquivalenz von (1,3) und (4,7) bezüglich R.
Laut Vorschrift muss man jetzt jeweils die ersten und die zweiten Elemente mod3 vergleichen. Wir haben also:
[mm]1 \equiv 4 \mod 3[/mm] -> O.K.
[mm]3 \not\equiv 7 \mod 3[/mm] -> nicht O.K.
Also [mm](1,3)\neg R (4,7)[/mm], d.h. die beiden Paare sind nicht äquivalent bezüglich R.
Vielleicht ist damit etwas klarer, wie die Relation eigentlich anzuwenden ist.
Bezüglich des zweiten Artikels: gesucht sind in der Aufgabe ja nicht die Zahl der verscheidenen Äquivalenzklassen, sondern nur die größe einer bestimmten, nämlich der, in der (7,8) liegt. Anders formuliert: Wie viele Elemente (n,m) gibt es in A, so dass (n,m)R(7,8) gilt?
Zusatzaufgabe: welche sind das?
Bezüglich b) kann ich erst mal gar nichts sagen, denn da taucht auf einmal ein k auf, das nirgends definiert wurde ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
Aber vielleicht kommst Du damit ja schon mal ein kleines Stückchen weiter!
Gruß
piet
|
|
|
| |
|
Das k bedeutet
A= {0...k}
ad Bsp1)
Das bedeutet
(1 2) (1 5) (1 8)
(4 2) (4 5) (4 8)
(7 2) (7 5) (7 8)
Sind meine Lösung ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:32 Fr 19.05.2006 | | Autor: | piet.t |
Hallo,
> Das k bedeutet
> A= {0...k}
Also wahrscheinlich A= [mm] \{0...k\}\times\{0...k\}
[/mm]
>
> ad Bsp1)
>
> Das bedeutet
> (1 2) (1 5) (1 8)
> (4 2) (4 5) (4 8)
> (7 2) (7 5) (7 8)
> Sind meine Lösung ?
...das hätte ich zumindest auch raus.
Zu b) erstmal nur ein paar Gedanken:
R ist ja schon eine Äquivalenzrelation und soll nun gleichzeitig noch eine Halbordnung sein. Das bedeutet also
- R ist symmetrisch: aRb [mm] \gdw [/mm] bRa
und gleichzeitig
- R ist antisymmetrisch: aRb [mm] \wedge [/mm] bRa [mm] \Rightarrow [/mm] a=b
Was folgt daraus für die Größe der Äquivalenzklassen bezüglich R?
Für welche k kann das nur der Fall sein?
Gruß
piet
|
|
|
| |
|
Sagen wir ich hätte jetzt ein Menge A mit
A={0 1} x {0 1}
Eigentlich bei jeder Zahl so lange sie gleich sind ?
(0 0) passt
(1 0) passt nicht
(0 1) passt nicht
(1 1) passt
Nur da könnte ja k unendlich sein ?
PS: das ist ja IMMER symmetrisch, wie kann das anti symm werden ?
PPS: Meine obige Darstellung der Lösung -> sind das meine Äquivalenzklassen ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:51 Sa 20.05.2006 | | Autor: | piet.t |
> Sagen wir ich hätte jetzt ein Menge A mit
> A={0 1} x {0 1}
>
> Eigentlich bei jeder Zahl so lange sie gleich sind ?
> (0 0) passt
> (1 0) passt nicht
> (0 1) passt nicht
> (1 1) passt
Was bedeutet jezt hier "passt"? Wenn Du damit "liegt in R" meinst, dann Vorsicht: R bezieht sich immer auf 2 Zahlenpaare, also z.B. (0 0)R(0 0).
>
> Nur da könnte ja k unendlich sein ?
...siehe später
>
> PS: das ist ja IMMER symmetrisch, wie kann das anti symm
> werden ?
>
Da R ja eine Äquivalenzrelation ist (und auch bleibt) gilt natürlich immer die Symmetrie, d.h. (n,m)R(n,m) gilt immer.
Wenn man sich aber die Definitionen von symmetrisch und antisymmetrisch anschaut stellt man fest, dass sie sich nicht unbedingt ausschließen.
Betrachten wir jetzt einmal den Fall, dass R gleichzeitig symmetrisch und antisymmetrisch ist. Seien dann [mm] (n_1,m_1) [/mm] und [mm] (n_2,m_2) [/mm] aus A mit [mm] (n_1,m_1)R(n_2,m_2). [/mm] Dann gilt ja:
[mm] (n_1,m_1)R(n_2,m_2) \Rightarrow (n_2,m_2)R(n_1,m_1) [/mm] (Symmetrie), also auch
[mm] (n_1,m_1)R(n_2,m_2) \wedge (n_2,m_2)R(n_1,m_1)
[/mm]
und damit wegen der Antisymmetrie
[mm] (n_1,m_1) [/mm] = [mm] (n_2,m_2).
[/mm]
Also kann jede Äquivalenzklasse nur genau ein Element enthalten. Für welche k-Werte ist das der Fall, wann finden wir Äquivalenzklassen mit 2 oder mehr Elementen?
> PPS: Meine obige Darstellung der Lösung -> sind das meine
> Äquivalenzklassen ?
Deine Aufzählung oben stellt ja alle Elemente aus A dar, und da da keine Äquivalenten dabei sind: ja!
Allgemein könnte man die Äquivalenzklassen so bilden:
Man schreibt sich alle Elemente der Grundmenge auf und verteilt sie dann so auf unterschiedliche "Töpfe", dass in einem Topf nur äquivalente Elemente liegen und zwei Elemente aus unterschiedlichen Töpfen nicht äquivalent sind.
Gruß
piet
|
|
|
| |
|
Irgendwie steh ich auf der Leitung
Wenn wir sagen
$ [mm] (n_1,m_1)R(n_2,m_2) \wedge (n_2,m_2)R(n_1,m_1) [/mm] $ genau dann wenn [mm] (n_1,m_1)=(n_2,m_2)
[/mm]
Wir sollen prüfen ob [mm] (n_1,m_1)mod3 [/mm] das gleiche wie [mm] (n_2,m_2)mod3 [/mm] ist
Nur sobald unsere Menge A ={0,1}x{0,1} besteht
habe ich (0 0) (1 0) (0 1) (1 1)
(0 0)R(1 0) -> ist nicht erfüllt
usw....
Ich würde sagen das geht nur wenn k null ist ?
Weil sobald k > 0 ist kann ich paar bilden und somit ist die Relationsbedingung nicht mehr erfüllt ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:29 Sa 20.05.2006 | | Autor: | piet.t |
Du hast doch vorhin schon die Äquivalenzklassen zu k = 1 gebildet. Wie groß waren die jeweils? Und wie schauen im Gegensatz dazu die Äquivalenzklassen zu k = 4 aus (insbesondere z.B. die mit (1,0))?
|
|
|
| |
|
Kann es vielleicht so sein ?
Bei k = 1
gibt es keine Äquivalenzklassen
Bei k = 2
Gibts auch keine
Erst bei k =3
(1 0) == (1 3)
(0 1) == (3 1)
(0 2) == (3 2)
usw...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:10 Sa 20.05.2006 | | Autor: | piet.t |
> Kann es vielleicht so sein ?
>
> Bei k = 1
> gibt es keine Äquivalenzklassen
Doch, es gibt schon welche, allerdings enthält jede davon nur ein Element.
Damit ist in diesem Fall also R auch eine Halbordnung. Das musst Du allerdings noch zeigen, denn oben habe ich ja nur bewiesen, dass falls R eine Halbordnung ist alle Äquivalenzklassen nur ein Element haben können, d.h. die Rückrichtung fehlt noch.
>
> Bei k = 2
> Gibts auch keine
>
Siehe oben....
> Erst bei k =3
> (1 0) == (1 3)
> (0 1) == (3 1)
> (0 2) == (3 2)
> usw...
Genau, d.h. hier kann R keine Halbordnung mehr sein!
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:47 Sa 20.05.2006 | | Autor: | Frankster |
Danke :)
|
|
|
|
