Symmetriegruppe Sn erzeugen

03.05.2020, 17:23

MaPalui

Symmetriegruppe Sn erzeugen

Hallo ihr Lieben smile

ich habe folgende Aufgabe vor mir:
[attach]51149[/attach]

Leider fehlt mir aktuell anscheinend das richtige Verständnis der Schreibweise.
Ich weiß ja, dass $\begin{eqnarray*} S_n := \left\{ \phi: \left\{ 1,...,n \right\} \rightarrow \left\{ 1,...,n \right\}, \phi \text{ bijektiv} \right\} \end{eqnarray*}$ gilt.
$\begin{eqnarray*} S_2 \end{eqnarray*}$ ist also die Menge der Funktionen $\begin{eqnarray*} \phi_1 = id \end{eqnarray*}$ und $\begin{eqnarray*} \phi_2(1) = 2, \phi_2(2) = 1 \end{eqnarray*}$ .
Wenn ich mir nun den Zykel $\begin{eqnarray*} (12) \end{eqnarray*}$ anschaue, dann erhalte ich ja die Abbildung $\begin{eqnarray*} \phi_2 \end{eqnarray*}$ .
Wenn ich daraus bilde $\begin{eqnarray*} (12)\circ (12) \end{eqnarray*}$ , erhalte ich die identische Abbildung und damit habe ich $\begin{eqnarray*} S_2 \end{eqnarray*}$ erzeugt.
Wenn ich nun aber den Zykel $\begin{eqnarray*} (12) \end{eqnarray*}$ in $\begin{eqnarray*} S_3 \end{eqnarray*}$ betrachte, bedeutet das dann, dass 3 nun ein Fixpunkt ist?

03.05.2020, 18:03

Elvis

Auf diesen Beitrag antworten »

Ja. In einem Zykel $\begin{eqnarray*} (a_1,...,a_m) \end{eqnarray*}$ werden genau die Elemente $\begin{eqnarray*} a_1 \end{eqnarray*}$ bis $\begin{eqnarray*} a_m \end{eqnarray*}$ zyklisch vertauscht, die anderen $\begin{eqnarray*} n-m\ge 0 \end{eqnarray*}$ Elemente sind fixiert.

03.05.2020, 18:06

MaPalui

Auf diesen Beitrag antworten »

Hallo Elvis,
Vielen Dank für die Aufklärung.
Ich habe mir das nun einmal auch am Beispiel der $\begin{eqnarray*} S_3 \end{eqnarray*}$ deutlich gemacht. Das war allerdings sehr umständlich: Ich habe eine Verknüpfungstafel mit id, (12) und (13) gemacht, verglichen und ein "fehlendes" Element über nochmalige Verknüpfung mit (13) bekommen.
Leider hat das meinem Verständnis dieser Aufgabe nicht geholfen unglücklich

Kannst du mir vielleicht einen Tipp geben?

03.05.2020, 18:25

Elvis

Auf diesen Beitrag antworten »

Die $\begin{eqnarray*} S_n \end{eqnarray*}$ hat $\begin{eqnarray*} n! \end{eqnarray*}$ Elemente, die $\begin{eqnarray*} S_3 \end{eqnarray*}$ hat also $\begin{eqnarray*} 6 \end{eqnarray*}$ Permutationen. Diese Permutationen vertauschen irgendwelche Elemente (o.B.d.A.) der Menge $\begin{eqnarray*} \{1,2,3,4,5,6\} \end{eqnarray*}$ .
Mein Gefühl sagt mir, dass man jede Vertauschung dadurch erreichen kann, dass man wiederholt hintereinander je 2 Elemente vertauscht. Das ist Teil a) der Aufgabe.
Idee: Die Vertauschung von $\begin{eqnarray*} i \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ wird erreicht durch $\begin{eqnarray*} (1i)(1k)(1i) \end{eqnarray*}$ . Die Idee ist eigentlich schon der ganze Beweis, um sicher zu sein kannst du die Zykel in Permutationsschreibweise schreiben.
Beachte immer, dass jeder Zykel von links nach rechts arbeitet, die Nacheinanderausführung von Zykeln wie immer bei Abbildungen von rechts nach links.

03.05.2020, 19:33

MaPalui

Auf diesen Beitrag antworten »

Hallo nochmal, vielen Dank für deine Hilfe!

Zitat:

Original von Elvis
Idee: Die Vertauschung von $\begin{eqnarray*} i \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ wird erreicht durch $\begin{eqnarray*} (1i)(1k)(1i) \end{eqnarray*}$ . Die Idee ist eigentlich schon der ganze Beweis, um sicher zu sein kannst du die Zykel in Permutationsschreibweise schreiben.

Das konnte ich nun beweisen, das war leicht.

Zitat:

Mein Gefühl sagt mir, dass man jede Vertauschung dadurch erreichen kann, dass man wiederholt hintereinander je 2 Elemente vertauscht. Das ist Teil a) der Aufgabe.

Soweit ich mich recht erinnere, ist das doch der Bubblesort, oder? Den könnte man ja mit Vollständiger Induktion zeigen.
Dann kann ich argumentieren, man kann mit (12),(13),...,(1n) je zwei Elemente vertauschen und dadurch jede Permutation in n Elementen erreichen.

03.05.2020, 19:55

Elvis

Auf diesen Beitrag antworten »

Bubblesort benutzt auch 2-Zykel, stellt aber nur eine bestimmte Ordnung her und läuft so lange über eine Liste bis die gewünschte Ordnung erreicht ist. Das Grundprinzip ist ähnlich, aber nicht identisch.

Einfacher ist, eine Permutation als 1. sortiertes Urbild 2. beliebiges Bild, zu schreiben. Zum Beispiel $\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}=(12)(13) \end{eqnarray*}$ .

Wenn du unbedingt vollständige Induktion brauchst, dann mache zuerst die Transposition, die das Zielelement unter die 1 bringt, hier (13). Der Rest permutiert maximal n-1 Elemente. qed.

03.05.2020, 20:44

MaPalui

Auf diesen Beitrag antworten »

Ich danke dir vielmals für all die Zeit.

Zitat:

Einfacher ist, eine Permutation als 1. sortiertes Urbild 2. beliebiges Bild, zu schreiben. Zum Beispiel $\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}=(12)(13) \end{eqnarray*}$ .

Diese Schreibweise kenne ich. Mir erschließt sich gerade nicht wie das für den Beweis meinst? verwirrt

03.05.2020, 21:43

Elvis

Auf diesen Beitrag antworten »

Wenn in einem Satz die natürliche Zahl n vorkommt, dann muss man an einen Beweis durch vollständige Induktion denken.
Der Induktionsanfang für n=2 ist trivial.
Eine Idee für den Induktionsschritt habe ich oben skizziert. Der Ausnahmefall, dass 1 Fixpunkt der Permutation ist, ist dir sicher schon aufgefallen, und ich vermute, dass du das auch schon gelöst hast.

04.05.2020, 14:04

MaPalui

Auf diesen Beitrag antworten »

Entschuldige bitte vielmals, aber für mich ist nun irgendwie doch das "Induktion oder nicht" durcheinandergegangen.
Also ich bin ja vollkommen unerfahren, deshalb immr noch bei (a), obwohl das bestimmt ein Klacks ist.

Ich habe raus:
(1i)(1k)(1i) = (1)(ik) = (ik).

Ok, mit den (12),(13),...,(1n) kann ich je zwei Elemente vertauschen.

Nun fehlt noch, dass ich durch Vertauschung von je zwei Elementen alle Permutationen erreiche, oder?

04.05.2020, 14:12

Elvis

Auf diesen Beitrag antworten »

Ja, aber ich dachte, das sei klar. Endlich viele Elemente vertauschen kann man in einzelnen Schritten machen. Frei aus dem Gedächtnis zitiert nach Lewis Carroll Alice im Wunderland: Beginne am Anfang, mache weiter, und höre am Ende auf. Augenzwinkern

04.05.2020, 14:14

MaPalui

Auf diesen Beitrag antworten »

Die Behauptung ist also: Durch Vertauschen von je zwei Elementen wird jede Permutation erreicht.

Dies nun über Induktion?

(IA) n=2: Wir haben (12) und (12)(12) = id. Passt.

(IV) Die Behauptung gelte für eine natürliche Zahl n>1.

(IS)

Nach (IV) können wir mit (12),(13),...,(1n) alle Permutationen der Elemente 1 bis n erreichen. Nennen wir diese oBda $\begin{eqnarray*} i_1, i_2, \dots, i_n \end{eqnarray*}$ . Dann können wir also alle Permutationen der Form [latex](i_1, i_2, \dots, i_n, (n+1) mit jedem Element vertauschen. Damit erreichen wir alle (n+1)! Permutationen.

04.05.2020, 15:36

Elvis

Auf diesen Beitrag antworten »

Der Beweis leuchtet nicht ein, um nicht zu sagen, er ist falsch.

04.05.2020, 15:50

MaPalui

Auf diesen Beitrag antworten »

OK danke

04.05.2020, 18:13

Elvis

Auf diesen Beitrag antworten »

Danke wofür ? Du könntest einen Algorithmus entwickeln, der eine beliebige Permutation durch Hintereinanderausführung von Vertauschungen realisiert. $\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 3 & . & . & . & n \\ 4 & 5 & 6 & . & . & . & a_n \end{pmatrix}=...(14)(25)(36) \end{eqnarray*}$ , wobei schon $\begin{eqnarray*} ... (14) \end{eqnarray*}$ genügt, um einen Beweis durch vollständige Induktion zu beginnen, denn was dann folgt, muss nur noch $\begin{eqnarray*} n-1 \end{eqnarray*}$ Elemente permutieren, die nach der ersten Vertauschung weiter rechts stehen. Hier ist Handwerk, Phantasie und Kreativität gefragt, es gibt bestimmt 1000 verschiedene Möglichkeiten.

04.05.2020, 23:05

Elvis

Auf diesen Beitrag antworten »

Gerade eben ist mir eine richtig schöne vollständige Induktion eingefallen, die ich dir nicht vorenthalten möchte.
Behauptung : Jede Permutation von n>1 Elementen ist die Komposition von Vertauschungen.
Beweis :
Induktionsanfang. n=2.
Fall 1. Die Permutation hat einen Fixpunkt. Das ist die Identität (12)(12).
Fall 2. Die Permutation hat keinen Fixpunkt. Das ist die Vertauschung (12).
Induktionsvoraussetzung : Jede Permutation von n>1 Elementen ist die Komposition von Vertauschungen.
Induktionsschluss:
Fall 1. Die Permutation hat einen Fixpunkt. Sie ist als Permutation von n-1 Elementen nach IV Komposition von Vertauschungen.
Fall 2. Die Permutation hat keinen Fixpunkt. Also bildet sie 1 auf x ab. Beginn der Permutation ist (1x). Danach fixieren wir x. Die Permutation der übrigen Elemente permutiert n-1 Elemente, sie ist nach IV Komposition von Vertauschungen.
QED

Neue Frage »

Antworten »

Symmetriegruppe Sn erzeugen

Verwandte Themen