Äquivalenzrelation zeigen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:36 So 03.11.2013 | | Autor: | Petrit |
| Aufgabe | | $ [mm] M:=\IZ; R:=\left\{(m,n)\in \IZx\IZ|\[\exists\]k\in\IZ : m-n = k*p\right\}, [/mm] wobei [mm] p\in\IN [/mm] fest gewählt sei; und x:=1 $ |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo erstmal!
Ich bin neu hier im Forum und möchte um eure Mithilfe bitten. Ich bin am Anfang meines Studiums und habe daher noch nicht so viel Ahnung. Ich soll bei dieser Aufgabe zeigen, dass es sich um eine Äquivalenzrelation handelt. Nun, ich weiß, dass man nach Reflexivität, Symmetrie und Transitivität untersuchen muss, allerdings fällt mir hierfür kein Anstatz ein und hoffe ihr könnt mir da weiterhelfen. Außerdem soll ich beschreiben, was die Äquivalenzklasse x zu bedeuten hat. Ich habe schon viel im Internet durchsucht, bin aber noch auf keine Antwort gekommen.
Vielen Dank schonmal im Voraus für eure Hilfe!
Viele Grüße!!!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:07 So 03.11.2013 | | Autor: | Marcel |
Hallo,
> [mm]M:=\IZ; R:=\left\{(m,n)\in \IZ \times \IZ|\;\exists k\in\IZ : m-n = k*p\right\}[/mm], wobei [mm] $p\in\IN$ [/mm] fest gewählt sei; und $x:=1$
>
was soll das [mm] $x\,$ [/mm] dabei für eine Rolle spielen?
Gegeben ist die Menge [mm] $M=\IZ\,.$ [/mm] Dann ist [mm] $R\,$ [/mm] eine zweistellige Relation auf [mm] $M=\IZ\,,$
[/mm]
das bedeutet, dass $R [mm] \subseteq [/mm] M [mm] \times M=\IZ \times \IZ$ [/mm] sein sollte, was ja auch so ist, wie
Du der Definition von [mm] $R\,$ [/mm] entnimmst. (Ich habe Dein x durch [mm] $\times$ [/mm] (anklicken!) ersetzt!)
Vielleicht würde man hier besser [mm] $R=R_p$ [/mm] schreiben, aber das [mm] $R\,$ [/mm] bleibt ja für
festes [mm] $p\,$ [/mm] auch fest.
Sei also $p [mm] \in \IN$ [/mm] beliebig, aber fest.
Du hast nun zu zeigen:
1.) [mm] $R=R_p$ [/mm] ist reflexiv, das bedeutet, zu zeigen ist:
Für alle $m [mm] \in \IZ$ [/mm] gilt $(m,m) [mm] \in R\,.$
[/mm]
Das ist einfach, denn:
Sei $m [mm] \in \IZ\,.$ [/mm] Es ist per Definitionem genau dann $(m,m) [mm] \in R\,,$ [/mm] wenn gilt:
Es existiert ein $k [mm] \in \IZ$ [/mm] mit [mm] $m-m=k*p\,.$ [/mm]
Also: $k:=0 [mm] \in \IZ$ [/mm] tut's!
2.) [mm] $R=R_p$ [/mm] ist symmetrisch. Das bedeutet, Du hast zu zeigen:
Ist $(m,n) [mm] \in \IZ \times \IZ$ [/mm] so, dass zudem $(m,n) [mm] \in [/mm] R$ gilt, dann muss nachgewiesen
werden, dass daraus schon folgt, dass auch $(n,m) [mm] \in [/mm] R$ gilt. Auch das ist
nicht sonderlich schwer:
Sind $m,n [mm] \in \IZ$ [/mm] so, dass $(m,n) [mm] \in [/mm] R$ gilt, so folgt per Definitionem von [mm] $R\,,$ [/mm] dass
es ein $k [mm] \in \IZ$ [/mm] gibt mit [mm] $m-n=k*p\,.$ [/mm] Letzteres läßt sich äquivalent umschreiben zu
[mm] $(n-m)=(-k)*p\,.$ [/mm] Warum folgt damit dann $(n,m) [mm] \in [/mm] R$?
3.) Zu zeigen ist: Sind $(m,n) [mm] \in [/mm] R$ und [mm] $(n,\red{\tilde{p}}) \in R\,,$ [/mm] so folgt auch schon [mm] $(m,\red{\tilde{p}}) \in R\,.$ [/mm]
Also: $(m,n) [mm] \in [/mm] R$ liefert ein ganzzahliges [mm] $k_1$ [/mm] mit [mm] $m-n=k_1*p\,.$
[/mm]
[mm] $(n,\red{\tilde{p}}) \in [/mm] R$ analog ein ganzzahliges [mm] $k_2$ [/mm] mit [mm] $n-\red{\tilde{p}}=k_2*p\,.$
[/mm]
Was bedeutet das für [mm] $(k_1+k_2)*p$ [/mm] und was folgerst Du daraus?
P.S. Beachte bitte die feinen Unterschiede in den Formulierungen:
Bei Reflexivität steht, dass "die ganze $M [mm] \times [/mm] M$-Diagonale" zu [mm] $R\,$ [/mm] gehören
muss. Bei Symmetrie steht:
Für jedes Element aus [mm] $R\,$ [/mm] muss "das zugehörige mit vertauschter Komponentenreihenfolge"
wieder zu [mm] $R\,$ [/mm] gehören (analog bei Transitivität).
Damit ist die Diagonale
[mm] $D_M:=\{(m,m):\;\; m \in M\}$
[/mm]
schonmal stets eine ÄR auf [mm] $M\,.$ [/mm] (Was Du ja auch mal beweisen kannst.)
Wenn ich aber nur ein Element aus [mm] $D_M$ [/mm] entferne ($M [mm] \not=\varnothing$),
[/mm]
dann ist [mm] $D_M$ [/mm] keine ÄR auf [mm] $M\,$ [/mm] mehr.
Den Hinweis im P.S. schreibe ich auch deshalb, weil oft die Frage gestellt
wird:
Warum folgt aus der Symmetrie und der Transitivität zusammen nicht schon
die Reflexivität? Es gilt doch
$(m,n) [mm] \in [/mm] R$ [mm] $\Rightarrow$ [/mm] $(n,m) [mm] \in [/mm] R$ wegen Symmetrie
und damit
$(m,m) [mm] \in [/mm] R$ wegen Transitivität
bei einer zweistelligen Relation auf [mm] $M\,,$ [/mm] die symmetrisch und transitiv ist?
Was "fehlt" hier bei den Überlegungen?
(Edit: Aus dem [mm] $p\,$ [/mm] habe ich oben in sinnvoller Weise mal ein [mm] $\red{\tilde{p}}$ [/mm] gemacht!)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:35 So 03.11.2013 | | Autor: | Petrit |
| Aufgabe | | $ [mm] M:=\IZ; R:=\left\{(m,n)\in \IZx\IZ|\[\exists\]k\in\IZ : m-n = k\cdot{}p\right\}, [/mm] wobei [mm] p\in\IN [/mm] fest gewählt sei; und x:=1 $ |
Hi!
Danke erstmal für die schnelle Antwort.
Das x:=1 soll die Äquivalenzklasse darstellen und ich soll beschreiben, was das bedeutet, hab aber keine Ahnung, wie das geht.
Die Reflexivitäts- und Symmetriebeweise habe ich verstanden. Allerdings weiß ich nicht, wie ich bei der Transitivität weitermachen soll. Ich könnte ja auch noch [mm] m-p=k_{3}*p [/mm] schreiben und was dann. Es existiert ja nur ein k und somit müssten ja alle k gleich sien oder verstehe ich da was falsch? Vielleicht könnte mir da noch jemand weiterhelfen.
Danke schonmal!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:46 So 03.11.2013 | | Autor: | Marcel |
Hallo,
> [mm]M:=\IZ; R:=\left\{(m,n)\in \IZx\IZ|\[\exists\]k\in\IZ : m-n = k\cdot{}p\right\}, wobei p\in\IN fest gewählt sei; und x:=1[/mm]
>
> Hi!
> Danke erstmal für die schnelle Antwort.
> Das x:=1 soll die Äquivalenzklasse darstellen
??? Siehst Du da irgendeinen Sinn drin? Das ist so, wie, wenn ich sage, dass
[mm] $y:=12\,$ [/mm] sagen soll, dass 17 eine Primzahl ist... ?!?!
> und ich
> soll beschreiben, was das bedeutet, hab aber keine Ahnung,
> wie das geht.
> Die Reflexivitäts- und Symmetriebeweise habe ich
> verstanden. Allerdings weiß ich nicht, wie ich bei der
> Transitivität weitermachen soll. Ich könnte ja auch noch
> [mm]m-p=k_{3}*p[/mm] schreiben und was dann. Es existiert ja nur ein
> k und somit müssten ja alle k gleich sien oder verstehe
> ich da was falsch? Vielleicht könnte mir da noch jemand
> weiterhelfen.
Na dann nochmal:
Seien $(m,n) [mm] \in [/mm] R$ und $(n,q) [mm] \in R\,.$ [/mm] Nach Definition von [mm] $R\,$
[/mm]
$(m,n) [mm] \in [/mm] R$ [mm] $\Rightarrow$ [/mm] $m,n [mm] \in \IZ$ [/mm] und [mm] $\exists k_1 \in \IZ$ [/mm] mit [mm] $m-n=k_1*p\,.$
[/mm]
$(n,q) [mm] \in [/mm] R$ [mm] $\Rightarrow$ [/mm] $n,q [mm] \in \IZ$ [/mm] und [mm] $\exists k_2 \in \IZ$ [/mm] mit [mm] $n-q=k_1*p\,.$
[/mm]
(Hinweis: Ich hatte in meiner ersten Antwort [mm] $p\,$ [/mm] geschrieben, obwohl das
natürlich schlecht war, weil [mm] $p\,$ [/mm] ja schon benutzt wird - in der alten Antwort
habe ich das [mm] $p\,$ [/mm] zu [mm] $\tilde{p}$ [/mm] geändert, hier schreibe ich lieber [mm] $q\,$...!)
[/mm]
Was damit schonmal klar ist, ist, dass $(m,q) [mm] \in \IZ \times \IZ$ [/mm] gilt (da $m,q [mm] \in \IZ$).
[/mm]
Wie finden wir nun raus, ob $(m,q) [mm] \in [/mm] R$ gilt? Naja, nach Definition von [mm] $R\,$ [/mm] gilt:
[mm] $(\star)$ [/mm] $(m,q) [mm] \in [/mm] R$ [mm] $\iff$ [blue]($\red{(m,q) \in \IZ \times \IZ}$ [/mm] und es ex. ein [mm] $k_3 \in \IZ$ [/mm] mit [mm] $\blue{m-q}=k_3*p$)[/blue]
[/mm]
Den roten Teil rechterhand wissen wir schon. Wir müssen also noch zeigen:
Es gibt ein [mm] $k_3 \in \IZ$ [/mm] mit [mm] $m-q=k_3*p\,.$
[/mm]
Und dafür haben wir das vorausgesetzte Wissen:
[mm] $m-n=k_1*p$ [/mm] und [mm] $n-q=k_2*q$ [/mm] mit einem [mm] $k_1,k_2 \in \IZ\,.$
[/mm]
Ich behaupte nun: Mit
[mm] $k_3:=k_1+k_2$
[/mm]
gilt [mm] $k_3 \in \IZ$ [/mm] und [mm] $m-q=k_3*p\,.$ [/mm] (Beweis?)
Somit gilt bei [mm] $(\star)$ [/mm] die rechte Seite und die Folgerung [mm] $\Longleftarrow$ [/mm] von [mm] $(\star)$
[/mm]
kann angewendet werden, um $(m,q) [mm] \in [/mm] R$ zu erhalten.
So: Ergänze mal die fehlende, kleine Zwischenüberlegung!
Gruß,
Marcel
|
|
|
|
