Repräsentantensystem mit Abb. < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | A1a.) Sei $n [mm] \in \mathbb{N}$ [/mm] und [mm] $\mathbb{Z}_n$ [/mm] die Menge aller Äquivalenzklassen modulo n.
Zeigen Sie, dass folgende Elemente von [mm] $\mathbb{Z}_n$ [/mm] ein Repräsentantensystem für die Kongruenz modulo n bilden:
[mm] -\frac{n}{2} +1,-\frac{n}{2} [/mm] + 2, ... ,0, 1, ..., [mm] \frac{n}{2}, [/mm] falls n gerade ist, [mm] \\
[/mm]
[mm] -\frac{(n-1)}{2},-\frac{(n-1)}{2}+1, [/mm] ..., 0, 1, ..., [mm] \frac{(n-1)}{2}, [/mm] falls n ungerade ist.
b.) Geben Sie eine Abb. $f: [mm] \mathbb{Z}_n \rightarrow \mathbb{Z}_n$ [/mm] an, für welche sich die sämtlichen Bilder der obigen Repräsentantensysteme wesentlich effizienter berechnen lassen, als bzgl. der Repräsentantensysteme $0,1,2,...,n-1$ oder $1,2,3,...,n$ |
Hallo,
habe mal wieder Fragen zu den Relationen.
Bei der a.) weiß ich einfach nicht, wie ich das zeigen soll und mein Skript hilft mir auch nicht weiter. Mein erster Gedanke Induktion nach [mm] $n_1 \in 2\mathbb{N}$ [/mm] und [mm] $n_2 \in 2\mathbb{N}-1$ [/mm] ist glaube ich der falsche Weg.
Ich weiß, dass ein Repräsentantensystem aus einzelnen Repräsentanten der Äquivalenzklassen besteht, also bspw. [mm] $\mathbb{Z}_2 [/mm] = [mm] \{[0],[1]\}$ [/mm] zur Rechnung modulo 2. Hier könnten wir als Repräsentanten einfach eine ungerade und eine gerade Zahl nennen.
Bei der b.) habe ich auch keinen Ansatz, denn ich verstehe einfach nicht was gemacht werden soll. Schließlich ist die Abb. aus der Menge aller Äquivalenzklassen in die Menge aller Äquivalenzklassen, jedoch verstehe ich nicht, was das Bild sein soll. Vllt: $f: [mm] \mathbb{Z}_n \rightarrow \mathbb{Z}_n [/mm] : [z] [mm] \mapsto [/mm] [nz]$?, bildet ja eine Äquivalenzklasse auf ihr Vielfaches, was ja ebenfalls in der Klasse liegt.
Danke euch für eure Hilfe.
Grüße
Joe
|
|
| |
|
> A1a.) Sei [mm]n \in \mathbb{N}[/mm] und [mm]\mathbb{Z}_n[/mm] die Menge aller
> Äquivalenzklassen modulo n.
>
> Zeigen Sie, dass folgende Elemente von [mm]\mathbb{Z}_n[/mm] ein
> Repräsentantensystem für die Kongruenz modulo n bilden:
>
> [mm]-\frac{n}{2} +1,-\frac{n}{2}[/mm] + 2, ... ,0, 1, ...,
> [mm]\frac{n}{2},[/mm] falls n gerade ist, [mm]\\
[/mm]
> [mm]-\frac{(n-1)}{2},-\frac{(n-1)}{2}+1,[/mm] ..., 0, 1, ...,
> [mm]\frac{(n-1)}{2},[/mm] falls n ungerade ist.
>
> b.) Geben Sie eine Abb. [mm]f: \mathbb{Z}_n \rightarrow \mathbb{Z}_n[/mm]
> an, für welche sich die sämtlichen Bilder der obigen
> Repräsentantensysteme wesentlich effizienter berechnen
> lassen, als bzgl. der Repräsentantensysteme [mm]0,1,2,...,n-1[/mm]
> oder [mm]1,2,3,...,n[/mm]
>
> Hallo,
>
> habe mal wieder Fragen zu den Relationen.
> Bei der a.) weiß ich einfach nicht, wie ich das zeigen
> soll und mein Skript hilft mir auch nicht weiter.
Hallo,
Dein Skript sollte Dir aber insofern weiterhelfen, als daß Du dort sicher nachlesen kannst, unter welchen Bedingungen eine Menge ein Repäsentantensystem der Äquivalenzrelation ist.
Das müßten wir erstmal wissen, wenn wir es zeigen wollen.
Die Äquivalenzrelation "kongruent modulo n" hast Du verstanden?
Nehmen wir n=5.
Du hast verstanden, wie man prüft, ob zwei ganze Zahlen kongruent modulo 5 sind?
Hast Du verstanden, daß z.B. [mm] \{0,1,2,3,4\} [/mm] ein Repräsentantensystem dieser Äquivalenzrelation ist?
Weißt Du, welche Elemente z.B. in der Äquivalenzklasse [3] enthalten sind?
(Du müßtest nun zeigen, daß [mm] \{ -2, -1, 0, 1, 2\} [/mm] ebenfalls ein Repräsentantensystem ist.)
>
> Bei der b.)
kapiere ich die Frage bisher auch nicht.
LG Angela
> habe ich auch keinen Ansatz, denn ich verstehe
> einfach nicht was gemacht werden soll. Schließlich ist die
> Abb. aus der Menge aller Äquivalenzklassen in die Menge
> aller Äquivalenzklassen, jedoch verstehe ich nicht, was
> das Bild sein soll. Vllt: [mm]f: \mathbb{Z}_n \rightarrow \mathbb{Z}_n : [z] \mapsto [nz][/mm]?,
> bildet ja eine Äquivalenzklasse auf ihr Vielfaches, was ja
> ebenfalls in der Klasse liegt.
>
> Danke euch für eure Hilfe.
>
> Grüße
> Joe
|
|
|
| |
|
Hallo angela,
erstmal danke ich dir für deine Antwort. Ja die "Kongruenz modulo n" habe ich verstanden, es bezieht auf den Rest der ganzzahligen Division. Bei deinem Beispiel mit [mm] $\mathbb{Z}_5 [/mm] ist [mm] \{ -2, -1, 0, 1, 2\} [/mm] ein Repräsentantensystem, da -2 mod 5 = 3 und -1 mod 5 = 4 (vllt. nicht mathematisch formal korrekt, aber in der Informatik ist die Schreibweise erlaubt :) ) ist und somit alle Elemente der Äquivalenzklassen abgedeckt werden. In der Äquivalenzklasse [3] sind alle Zahlen drin, die modulo 5 den Rest 3 ergeben, also wären potentielle Repräsentanten ...,-7,-2,3,8,13,18,23,...
Bei der b.) hier nochmal die eingescannte Aufgabenstellung (wenn hier externe Links erlaubt sind), vllt. habe ich mich ja unglücklich formuliert: https://www.dropbox.com/s/ipn52pkgjtrewas/aufgabe1.PNG - ich verstehe einfach nicht die Aufgabenstellung :(
Grüße
Joe
|
|
|
| |
|
Hallo,
gut, für [mm] \IZ_5 [/mm] hast Du ja eine Beweisidee geliefert:
Es sind
-2 und 3,
-1 und 4,
daher sind die beiden Restklassen jeweils gleich.
Da [mm] \{0,1,2,3,4\} [/mm] ein Vertretersystem ist,
ist also auch {-2,-1,0,1,2} eins.
Nun würde ich versuchen, das so ähnlich allgemein für gerades und ungerades n durchzuführen.
Die andere Aufgabe erschließt sich mir nach wie vor nicht.
LG Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:23 Di 13.11.2012 | | Autor: | JoeSunnex |
Hallo Angela,
habe jetzt einfach einen allgemeinen Ansatz gewählt mit einer geraden und ungeraden Zahl und eine Art "reduzierte" Induktion gezeigt, indem ich ein Beispiel gewählt habe und dadurch gezeigt habe, dass dies ein vollwertiges Repräsentantensystem daher ist, da alle Äquivalenzklassen genau einmal vorkommen - laut meinem Tutor sollte dies reichen :)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:40 Mo 12.11.2012 | | Autor: | tobit09 |
Hallo Joe,
> Bei der b.) habe ich auch keinen Ansatz, denn ich verstehe
> einfach nicht was gemacht werden soll.
Das ist in der Tat eine ungewöhnliche Aufgabenstellung.
> Vllt: [mm]f: \mathbb{Z}_n \rightarrow \mathbb{Z}_n : [z] \mapsto [nz][/mm]?,
> bildet ja eine Äquivalenzklasse auf ihr Vielfaches, was ja
> ebenfalls in der Klasse liegt.
Es gilt [nz]=[0] für alle [mm] $z\in\IZ$.
[/mm]
Betrachte mal im Falle n gerade die Abbildung
[mm] $f\colon\IZ_n\to\IZ_n,\quad [z]\mapsto[-z+1]$
[/mm]
und im Falle n ungerade die Abbildung
[mm] $f\colon\IZ_n\to\IZ_n,\quad [z]\mapsto[-z]$.
[/mm]
Zeige jeweils, dass f wohldefiniert ist.
Betrachten wir etwa n=5.
Es gilt dann z.B. f([2])=[-2]. Also wird die durch den Repräsentanten 2 gegebene Äquivalenzklasse auf die durch -2 gegebene Äquivalenzklasse abgebildet.
Wollte man die gleiche Überlegung bezüglich des Repräsentantensystems 0,1,2,3,4 oder 1,2,3,4,5 anstellen, müsste man zunächst $[-2]=[3]$ überlegen.
Ich glaube, so etwas ist mit der effizienteren Berechnung bezüglich der gegebenen Repräsentantensysteme gemeint.
Viele Grüße
Tobias
|
|
|
| |
|
Hallo Tobias,
meine Abbildung war eher ein Schuss in den Ofen, weil ich einfach an der Aufgabenstellung saß und mich gefragt habe, was ich denn eigentlich machen sollte.
Laut meinem Tutor ist dieses symmetrische Repräsentantensystem gerade bei großen n effizient, da man dann nicht alle Zahlen von 1 bis n bestimmen muss für die Äquivalenzklassen, sondern nur die Hälfte der Bilder.
Jedoch fällt mir da keine Abbildung ein.
Zu deinen Vorschlägen: $ [mm] f\colon\IZ_n\to\IZ_n,\quad [z]\mapsto[-z+1] [/mm] $ Diese Abbildung ist wohldefiniert genau dann, wenn sie linkstotal und rechtseindeutig ist. Linkstotal ist sie nach Definition: jedem $[z] [mm] \in \IZ_n$ [/mm] wird etwas zugewiesen. Des Weiteren ist sie rechtseindeutig, da [mm] $\forall [/mm] [z] [mm] \in \IZ_n [/mm] ~ [mm] \exists_{1} [/mm] [-z+1] [mm] \in \IZ_n \Rightarrow [/mm] f([z])=[-z+1]$
Bei deiner zweiten Abbildung wäre es analog, aber bezieht sich diese Abbildung jetzt wirklich auf obiges Repräsentantensystem - oder habe ich immernoch Probleme die Aufgabenstellung zu verstehen :)?
Grüße
Joe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:41 Di 13.11.2012 | | Autor: | tobit09 |
> meine Abbildung war eher ein Schuss in den Ofen, weil ich
> einfach an der Aufgabenstellung saß und mich gefragt habe,
> was ich denn eigentlich machen sollte.
Damit bist du offenbar nicht alleine. Die Aufgabenstellung ist auch ungewöhnlich.
> Laut meinem Tutor ist dieses symmetrische
> Repräsentantensystem gerade bei großen n effizient, da
> man dann nicht alle Zahlen von 1 bis n bestimmen muss für
> die Äquivalenzklassen, sondern nur die Hälfte der
> Bilder.
> Jedoch fällt mir da keine Abbildung ein.
Mit dem Hinweis kann ich leider auch nichts anfangen.
> Zu deinen Vorschlägen: [mm] f\colon\IZ_n\to\IZ_n,\quad [z]\mapsto[-z+1][/mm]
> Diese Abbildung ist wohldefiniert genau dann, wenn sie
> linkstotal und rechtseindeutig ist.
Du fasst also f als die Relation [mm] $R=\{([z],[-z+1])\;|\;z\in\IZ\}$ [/mm] auf [mm] $\IZ_n$ [/mm] auf.
> Linkstotal ist sie nach
> Definition: jedem [mm][z] \in \IZ_n[/mm] wird etwas zugewiesen.
Ja. Jedes [mm] $a\in\IZ_n$ [/mm] hat die Gestalt $a=[z]$ für ein [mm] $z\in\IZ$. [/mm] Somit [mm] $(a,[-z+1])\in [/mm] R$.
> Des
> Weiteren ist sie rechtseindeutig, da [mm]\forall [z] \in \IZ_n ~ \exists_{1} [-z+1] \in \IZ_n \Rightarrow f([z])=[-z+1][/mm]
Hier musst du aufpassen: Warum existiert zu [mm] $[z]\in\IZ_n$ [/mm] höchstens ein [mm] $b\in\IZ_n$ [/mm] mit [mm] $([z],b)\in [/mm] R$?
Du behauptest, dass $b=[-z+1]$ das einzige b mit dieser Eigenschaft sei.
Angenommen wir haben ein weiteres Element [mm] $b'\in \IZ_n$ [/mm] mit [mm] $([z],b')\in [/mm] R$. Zu zeigen ist, dass dann $b'=[-z+1]$ gilt.
Jetzt kommt der wichtigste Punkt:
Wegen [mm] $([z],b')\in [/mm] R$ wissen wir ersteinmal nur, dass ein [mm] $z'\in\IZ$ [/mm] existiert mit [z]=[z'] und b'=[-z'+1].
Daraus folgt NICHT etwa $z=z'$, sondern nur [mm] $z\sim [/mm] z'$.
Zu zeigen ist nun [-z+1]=[-z'+1], d.h. zu zeigen ist [mm] $-z+1\sim-z'+1$.
[/mm]
Nocheinmal ohne Bezugnahme auf die Relation R erklärt:
Wir wollen einer Äquivalenzklasse [mm] $a\in\IZ_n$ [/mm] mittels f eine neue Äquivalenzklasse wie folgt zuordnen: Wir WÄHLEN ein Element [mm] $z\in\IZ$ [/mm] mit $a=[z]$ und wollen $f(a):=[-z+1]$ definieren.
Jemand anderes wendet vielleicht ebenfalls unsere beabsichtigte Definition an, wählt ein anderes Element [mm] $z'\in\IZ$ [/mm] mit $a=[z']$ und kommt somit zum Ergebnis $f(a)=[-z'+1]$.
Nun kann $f(a)$ nur dann wohldefiniert sein, wenn $[-z+1]=[-z'+1]$ gilt.
Lange Rede, kurzer Sinn:
Gegeben [z]=[z'] für [mm] $z,z'\in\IZ$ [/mm] (d.h. [mm] $z\sim [/mm] z'$) ist $[-z+1]=[-z'+1]$ (d.h. [mm] $-z+1\sim [/mm] -z'+1$) zu zeigen.
> Bei deiner zweiten Abbildung wäre es analog, aber bezieht
> sich diese Abbildung jetzt wirklich auf obiges
> Repräsentantensystem - oder habe ich immernoch Probleme
> die Aufgabenstellung zu verstehen :)?
Sei [mm] $B_n$ [/mm] das in a) gegebene Repräsentantensystem.
Ich war davon ausgegangen, dass eine Abbildung [mm] $f\colon\IZ_n\to\IZ_n$ [/mm] mit folgender Eigenschaft gesucht ist:
Gegeben ein [mm] $z\in [/mm] B$ soll der zugehörige Repräsentant aus B von $f([z])$ einfach zu bestimmen sein. Jedenfalls einfacher als für [mm] $z\in\{0,1,2,\ldots,n-1\}$ [/mm] der Repräsentant aus [mm] $\{0,1,2,\ldots,n-1\}$ [/mm] von $f([z])$.
Mein f leistet dies aus meiner Sicht:
Für [mm] $z\in [/mm] B$ ist -z+1 (falls n gerade) bzw. -z (falls n ungerade) wieder in B und damit der Repräsentant aus B von $f([z])$.
Dagegen ist für [mm] $z\in\{0,1,2,\ldots,n-1\}$ [/mm] der Repräsentant aus [mm] $\{0,1,2,\ldots,n-1\}$ [/mm] gegeben durch $n-z+1$ (falls n gerade) bzw. $n-z$ für $z>0$ und 0 für $z=0$ (falls n ungerade).
Zu einer Zahl z die zugehörigen Zahlen -z+1 bzw. -z zu bestimmen erscheint mir leichter als die Zahlen $n-z+1$ bzw. gar mit Fallunterscheidung $n-z$ im Falle $z>0$ und 0 im Falle $z=0$ zu bestimmen.
Ob der Aufgabensteller die Aufgabe so gemeint hat, wie ich sie verstanden habe, weiß ich leider nicht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:24 Di 13.11.2012 | | Autor: | JoeSunnex |
Ich danke dir für deine ausführliche und somit für einen Ersti mit Schwierigkeiten einleuchtende Antwort :)
Man muss also explizit einen Rechtseindeutigkeitsbeweis führen? Ich habe aus Zeitgründen im Grunde "gezeigt", dass eine Addition bzw. Subtraktion von einer Konstante bei zwei unterschiedlichen Zahlen aus [mm] $\mathbb{Z}$ [/mm] zu unterschiedlichen Zahlen führen muss.
Ich verstehe deine Ausführung unten, jedoch meine ich so langsam zu kapieren was mein Tutor mit Hälfte der Bilder gemeint hat. Nehmen wir mal [mm] $\IZ_7 [/mm] = [mm] \{-3,-2,-1,0,1,2,3\}$ [/mm] nach obigem Repräsentantensystem, dann sehen wir wenn wir alle negativen oder positiven Repräsentanten bis 0 bestimmen und dann einfach später die bekannten auf -z abbilden, die restlichen Repräsentanten herauskommen, ähnlich funktioniert das bei den geraden Zahlen. Ich habe einfach deinen und meinen Ansatz zusammengemixt ob das jetzt die Aufgabe trifft oder sie verfehlt - war einen Versuch wert :)
Grüße
Joe
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:26 Mi 14.11.2012 | | Autor: | tobit09 |
> Man muss also explizit einen Rechtseindeutigkeitsbeweis
> führen?
Man kann zwei Sichtweisen einnehmen:
1. Wir erklären f als Relation und zeigen, dass f eine Funktion ist. Dann ist die Rechtseindeutigkeit explizit zu zeigen.
2. Wir wollen f direkt als Funktion definieren. Dann ist die Wohldefiniertheit von f zu zeigen.
Bisher ist mir in Vorlesungen und Büchern nur Sichtweise 2. begegnet. Da du aber mit 1. angesetzt hast, habe ich auch diese Sichtweise erläutert.
In beiden Fällen ist letztlich das gleiche zu tun: Aus $[z]=[z']$ für [mm] $z,z'\in\IZ$ [/mm] auf $[-z+1]=[-z'+1]$ schließen.
> Ich habe aus Zeitgründen im Grunde "gezeigt",
> dass eine Addition bzw. Subtraktion von einer Konstante bei
> zwei unterschiedlichen Zahlen aus [mm]\mathbb{Z}[/mm] zu
> unterschiedlichen Zahlen führen muss.
Da erkenne ich leider nicht den Zusammenhang mit dem Beweis, dass aus $[z]=[z']$ für [mm] $z,z'\in\IZ$ [/mm] auch $[-z+1]=[-z'+1]$ folgt.
|
|
|
|
