Permutationsgr./ Transposition < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:59 Mi 22.11.2017 | | Autor: | Tobikall |
| Aufgabe | I)
Es sei f : {1,...,n} → {1,...,n} eine Abbildung. Beweisen Sie, dass folgende Aussagen äquivalent sind.
(i) f ist injektiv.
(ii) f ist surjektiv.
(iii) f ist Permutation.
II)
Wir bezeichnen mit τ(j,k) die Transposition in Sn, die j und k tauscht für 1 ≤ j,k ≤ n. Es sei nun Sn mit n≥2
(i) Bestimmen Sie für l < m die Fehlstände, die Anzahl der Fehlstände und das Vorzeichen von τ(l,m).
(ii) Berechnen Sie die Anzahl der Fehlstände und das Vorzeichen von σ [mm] =\pmat{ 1 & (...) & (n-r+1) & (n-r+2) & (...) & n \\ r & (...) & n & 1 & (...) & (r-1) }∈ [/mm] Sn für 1 ≤ r ≤ n.
(iii) Geben Sie σ [mm] =\pmat{ 1 & 2 & 3 & (...) & n\\ n & (n-1) & (n-2) & (...) & 1 }∈ [/mm] Sn als eine Komposition von Transpositionen an. |
Hallo Matheraum-Gemeinde
die obenstehenden Aufgaben bereiten mir noch einige Probleme, da ich so gar nicht weiß wie ich die einelenen Dinge zeigen kann. Bei II) ist mir bewusst, was eine Transposition ist, nur ist das so allgemein gehalten, dass ich aktuell auf keinen richtigen Lösungsansatz komme.
ich poche auf eure Hilfe liebe Matheraummitglieder!!!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:45 Mi 22.11.2017 | | Autor: | hilbert |
Überleg bei der ersten Aufgabe mal was es heißt, wenn eine Funktion injektiv ist und wenn sie surjektiv ist und nutze dann aus, dass der Startmenge genau so viele Elemente hat, wie die Zielmenge.
Überlege, was Permutation im Bezug auf injektiv und surjektiv heißt?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:20 Do 23.11.2017 | | Autor: | Tobikall |
Hallo hilbert,
i) injektiv bedeutet in diesem Fall ja, dass für alle a,b, die Element von (1,...,n) sind mit (a ungleich b), dann auch f a ungleich f b ist, wieder aus der Menge (1,...,n).
ii) surjektiv bedeutet dann, dass es für jedes d aus (1,...,n) ein c aus (1,...,n) gibt, mit f c=d.
iii) und die Permutation bedeutet so viel, dass sämtliches Elemente von (1,...,n) dann genau einmal, aber in beliebiger Reihenfolge, abgebildet werden.
Aber wie genau zeige ich jetzt i)<=>ii) oder ii)<=> iii)? Dafür benötige ich ja jeweils auch die Hin-und Rückrichtung, um die Äquivalenz zu zeigen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:34 Do 23.11.2017 | | Autor: | fred97 |
Sei [mm] A=\{1,2,..,n\}
[/mm]
1. Sei f injektiv. Dann enthält f(A) genau n Elemente. Wegen f(A) [mm] \subseteq [/mm] A folgt dann f(A)=A. f ist also surjektiv.
2. Sei f surjektiv, also f(A)=A. f(A) enthält also n Elemente. Annahme: es gibt i,j [mm] \in [/mm] A mit i [mm] \ne [/mm] j und f(i)=f(j). Dann enthält aber f(A) weniger als n Elemente, Widerspruch. f ist also injektiv.
Damit ist gezeigt: (i) [mm] \gdw [/mm] (ii).
f ist eine Permutation bedeutet gerade, dass f bijektiv ist.
Nun zeige Du (i) [mm] \gdw [/mm] (iii).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:49 Do 23.11.2017 | | Autor: | Tobikall |
Ok, soweit habe ich die Äquivalenz verstanden, und wüsste jetzt auch wie ich die beiden anderen Äquivalenzen zeigen könnte, nur ist mir nicht ganz geläufig, wie ich Bijektivität zeigen kann.
Wir hatten als Definition von Bijektivität nur, dass eine Abbildung sofort bijektiv ist, falls Surjektivität und Injektivität zutreffen.
Man könnte mit gegebenem i) wieder die Surjektvität wie bei i) <=>ii) zeigen und daraus schließen, dass es bijektiv ist und somit i)<=>iii) gilt, nur dass das ja ziemlich schwachsinnig wäre, oder?
|
|
|
| |
|
Hallo,
> Ok, soweit habe ich die Äquivalenz verstanden, und wüsste
> jetzt auch wie ich die beiden anderen Äquivalenzen zeigen
> könnte, nur ist mir nicht ganz geläufig, wie ich
> Bijektivität zeigen kann.
> Wir hatten als Definition von Bijektivität nur, dass eine
> Abbildung sofort bijektiv ist, falls Surjektivität und
> Injektivität zutreffen.
> Man könnte mit gegebenem i) wieder die Surjektvität wie
> bei i) <=>ii) zeigen und daraus schließen, dass es
> bijektiv ist und somit i)<=>iii) gilt, nur dass das ja
> ziemlich schwachsinnig wäre, oder?
So würde ich das nicht ausdrücken. Du sollst hier vermutlich zeigen, dass dir die Definition der Bijektivität geläufig ist. Da du mittlerweile mit i) und ii) gezeigt hast, dass f bijektiv ist, ist dann auch gezeigt, dass f Permutation ist. Das muss man halt nur nochmal hinschreiben.
Anmerkung:
So wie du die Aufgabe mit den Teilen I und II hier eingestellt hast, ist der Teil I wohl eher zum 'Warmrechnen' gedacht. Dies nur zu deiner Bewertung hinsichtlich der Schwierigkeit.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:16 Do 23.11.2017 | | Autor: | Tobikall |
Also wäre die Aufgabe jetzt schon gelöst?
Weil ich dachte, da man Äquivalenz zeigen muss, dass man zeigen muss i)<=>ii) und ii)<=>iii) und iii)<=>i)?
Das wären dann drei Beweise mit jeweils Hin-und Rückrichtung.??
Bei II) brauche ich dann aber auch noch Hilfe
Viele Grüße
|
|
|
| |
|
Hallo,
für die Aufgabe I. kann man eine Implikationskette der Form
[mm] A\Rightarrow{B}\Rightarrow{C}\Rightarrow{A}
[/mm]
ansetzen, das vereinfacht die Sache ziemlich.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:14 Fr 24.11.2017 | | Autor: | Tobikall |
Ok, kann mir denn noch jemand bei II) helfen? Die Aufgabe ist so allgemein gehalten, dass ich nicht weiß, wie ich das nachweisen oder zeigen soll.
|
|
|
| |
|
Hallo,
zur Aufgabe II):
Bei Teilaufgabe i) geht es darum, eine recht einfache Formel herauszufinden, mit der man die Anzahl der Fehlstände einer Transposition direkt berechnen kann. Wenn du die Formel nicht kennst, dann führe einmal für eine überschaubare Menge natürlicher Zahlen Transpostionen mit unterschiedlichen Abständen durch und finde die Fehlstände jeweils durch Abzählen. Vielleicht kennst du aber auch die Formel (bzw. hast sie in deinen Unterlagen).
Bei der ii) beachte zunächst, dass es sich um einen sog. Rechtsshift handelt (also um eine zyklische Permutation).
Aufgabe iii) fehlt, die iv) dürfte kein Problem sein, oder?
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:25 Fr 24.11.2017 | | Autor: | Tobikall |
ok, zur II) i):
ein Fehlstand liegt dann vor, wenn l<m ist und sigma(m)<sigma(l) ist. Wenn ein Tau vorliegt, wobei l und m getauscht werden, liegt ein genau Fehlstand vor und das Vorzeichen berechnent sich durch [mm] (-1)^m.
[/mm]
Nur wie berechnet man das m jetzt hier???
iii)Hier lässt sich das Vorzeichen leicht durch [mm] (-1)^m [/mm] berechnen, nur weiß ich wirklich nicht wie ich auf m kommen soll, da die vertauschte Reihenfolge wirklich sehr durcheinander ist
iv) ist eine mögliche Lösung:???
[mm] (T(1)\circ [/mm] T(2) [mm] \circ [/mm] ... [mm] \circ [/mm] T(n-1)) [mm] \circ [/mm] ((T(2)) [mm] \circ... \circ T(n-1))\circ... \circ [/mm] T(n-1)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:05 Fr 24.11.2017 | | Autor: | Diophant |
Hallo,
ganz ehrlich: lies dir den Stoff und die zugehörigen Definitionen durch und bearbeite dann die Aufgabe. Dir sind die Begriffe überhaupt nicht klar!
Gruß, Diophant
|
|
|
| |
|
Hallo,
konntest du dich mittlerweile ein wenig in die Materie einarbeiten? Als Anschubhilfe hier einmal die erwähnte Formel für die Fehlstände einer Transposition. Sei [mm] 1\le{a}
[mm]2*(b-a)-1[/mm]
Fehlständen. Den Rest recherchiere bitte einmal selbst, außerdem scheint es da einen Aufgabenteil iii) zu geben, den du in deinem Startbeitrag unterschlagen hast. Den solltest du also noch nachreichen.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:22 Sa 25.11.2017 | | Autor: | Tobikall |
Hallo,
also es ist nicht so, dass ich mich nicht mit dem Stoff auseinandersetze, nur war mir die Formel für die Anzahl der Fehlstände schon einmal unbekannt und ich wüsste sehr wohl, wie die Aufgabe zu lösen wäre, wären feste Zahlenwerrte angegeben.
Nur ist Teil i) so allgemein gestellt, dass ich einfach nicht weiß was ich notieren soll und bei der ii) weiß ich z.B. nicht, ob bei den ... auch Werte vertauscht wurden, oder ob sie dort gleich geblieben sind.
Es wäre vll einfach schön gewesen, wenn mir jemand meine Fehler aufzeigen würde und evtl. ein paar nützliche Ratschläge geben könnte, danke.
|
|
|
|
