matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenLineare AbbildungenPermutationsgr./ Transposition
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Lineare Abbildungen" - Permutationsgr./ Transposition
Permutationsgr./ Transposition < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Abbildungen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Permutationsgr./ Transposition: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!!!

        
Bezug
Permutationsgr./ Transposition: Antwort
Status: (Antwort) fertig Status 
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?

Bezug
                
Bezug
Permutationsgr./ Transposition: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                        
Bezug
Permutationsgr./ Transposition: Antwort
Status: (Antwort) fertig Status 
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).

Bezug
                                
Bezug
Permutationsgr./ Transposition: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                        
Bezug
Permutationsgr./ Transposition: Antwort
Status: (Antwort) fertig Status 
Datum: 19:55 Do 23.11.2017
Autor: Diophant

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

Bezug
                                                
Bezug
Permutationsgr./ Transposition: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                                                        
Bezug
Permutationsgr./ Transposition: Antwort
Status: (Antwort) fertig Status 
Datum: 21:16 Do 23.11.2017
Autor: Diophant

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

Bezug
                                                                
Bezug
Permutationsgr./ Transposition: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
        
Bezug
Permutationsgr./ Transposition: Antwort
Status: (Antwort) fertig Status 
Datum: 09:11 Fr 24.11.2017
Autor: Diophant

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
 

Bezug
                
Bezug
Permutationsgr./ Transposition: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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)


Bezug
                        
Bezug
Permutationsgr./ Transposition: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Permutationsgr./ Transposition: Antwort
Status: (Antwort) fertig Status 
Datum: 10:10 Sa 25.11.2017
Autor: 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

Bezug
                                
Bezug
Permutationsgr./ Transposition: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Abbildungen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


Alle Foren
Status vor 8m 1. Filza
UAnaRn/Integral berechnen
Status vor 50m 8. Diophant
MSons/Induktion
Status vor 2h 04m 4. Gonozal_IX
UStoc/Verteilungsfunktion
Status vor 2h 41m 2. Diophant
UAnaR1FolgReih/n-te Partialsumme
Status vor 2h 53m 8. sancho1980
MSons/Zeigen, dass Formel gilt
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]