Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 8/latex
\setcounter{section}{8}
\zwischenueberschrift{Homomorphie- und Isomorphiesatz}
\inputfaktbeweis
{Gruppenhomomorphismus/Homomorphiesatz/Surjektiv und Kern/Fakt}
{Satz}
{}
{
\faktsituation {Es seien
\mathkor {} {G, Q} {und} {H} {}
\definitionsverweis {Gruppen}{}{,}
es sei
\maabb {\varphi} {G} { H
} {}
ein
\definitionsverweis {Gruppenhomomorphismus}{}{}
und
\maabb {\psi} {G} {Q
} {}
ein
\definitionsverweis {surjektiver}{}{}
Gruppenhomomorphismus.}
\faktvoraussetzung {Es sei vorausgesetzt, dass
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{kern} \psi
}
{ \subseteq} { \operatorname{kern} \varphi
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist.}
\faktfolgerung {Dann gibt es einen eindeutig bestimmten Gruppenhomomorphismus
\maabbdisp {\tilde{\varphi}} {Q } {H
} {}
derart, dass
\mavergleichskette
{\vergleichskette
{\varphi
}
{ = }{ \tilde{\varphi} \circ \psi
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist.}
\faktzusatz {Mit anderen Worten: das Diagramm
\mathdisp {\begin{matrix}G & \stackrel{ \varphi }{\longrightarrow} & H & \\ \!\!\! \!\! \psi \downarrow & \nearrow \tilde{\varphi} \!\!\! \!\! & \\ Q & & & & \!\!\!\!\! \!\!\! \\ \end{matrix}} { }
ist kommutativ.}
\faktzusatz {}
}
{
\teilbeweis {Wir zeigen zuerst die Eindeutigkeit.\leerzeichen{}}{}{}
{Für jedes Element
\mavergleichskette
{\vergleichskette
{ u
}
{ \in }{ Q
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es mindestens ein
\mathkor {} {g \in G} {mit} {\psi (g)=u} {.}
Wegen der Kommutativität des Diagramms muss
\mavergleichskettedisp
{\vergleichskette
{ \tilde{\varphi} (u)
}
{ =} {\varphi(g)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gelten. Das bedeutet, dass es maximal ein $\tilde{\varphi}$ geben kann.}
{}
\teilbeweis {Wir haben zu zeigen, dass durch diese Bedingung eine wohldefinierte Abbildung gegeben ist.\leerzeichen{}}{}{}
{Es seien also
\mavergleichskette
{\vergleichskette
{ g,g'
}
{ \in }{ G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zwei Urbilder von $u$. Dann ist
\mavergleichskettedisp
{\vergleichskette
{ \psi { \left( g' g^{-1} \right) }
}
{ =} { u u^{-1}
}
{ =} { e_Q
}
{ } {
}
{ } {
}
}
{}{}{}
und somit ist
\mavergleichskette
{\vergleichskette
{ g'g^{-1}
}
{ \in }{ \operatorname{kern} \psi
}
{ \subseteq }{ \operatorname{kern} \varphi
}
{ }{
}
{ }{
}
}
{}{}{.}
Daher ist
\mavergleichskette
{\vergleichskette
{ \varphi(g)
}
{ = }{ \varphi(g')
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Die Abbildung ist also wohldefiniert. Seien
\mavergleichskette
{\vergleichskette
{ u,v
}
{ \in }{ Q
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und seien
\mavergleichskette
{\vergleichskette
{ g,h
}
{ \in }{ G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Urbilder davon. Dann ist $gh$ ein Urbild von $uv$ und daher ist
\mavergleichskettedisp
{\vergleichskette
{ \tilde{\varphi} (uv)
}
{ =} { \varphi(gh)
}
{ =} { \varphi(g) \varphi (h)
}
{ =} { \tilde{\varphi} (u) \tilde{\varphi} (v)
}
{ } {}
}
{}{}{.}
D.h. $\tilde{\varphi}$ ist ein Gruppenhomomorphismus.}
{}
Die im vorstehenden Satz konstruierte Abbildung heißt
\definitionswortenp{induzierte Abbildung}{} oder
\definitionswortenp{induzierter Homomorphismus}{} und entsprechend heißt der Satz auch
\stichwort{Satz vom induzierten Homomorphismus}{.}
\inputfaktbeweis
{Gruppenhomomorphismus/Surjektiv und Restklassengruppe/Fakt}
{Korollar}
{}
{
\faktsituation {Es seien
\mathkor {} {G} {und} {H} {}
\definitionsverweis {Gruppen}{}{}
und sei
\maabbdisp {\varphi} {G} {H
} {}
ein \definitionsverweis {surjektiver}{}{}
\definitionsverweis {Gruppenhomomorphismus}{}{.}}
\faktfolgerung {Dann gibt es eine kanonische
\definitionsverweis {Isomorphie}{}{}
\maabbdisp {\tilde{\varphi}} {G/ \operatorname{kern} \varphi } {H
} {.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir wenden
Satz 8.1
auf
\mavergleichskette
{\vergleichskette
{Q
}
{ = }{ G/ \operatorname{kern} \varphi
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die
\definitionsverweis {kanonische Projektion}{}{}
\maabb {q} {G} {G/\operatorname{kern} \varphi
} {}
an. Dies induziert einen Gruppenhomomorphismus
\maabbdisp {\tilde{\varphi}} {G/\operatorname{kern} \varphi } {H
} {}
mit
\mavergleichskette
{\vergleichskette
{ \varphi
}
{ = }{ \tilde{\varphi} \circ q
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
der surjektiv ist. Sei
\mathkor {} {[x] \in G/\operatorname{kern} \varphi} {und} {[x] \in \operatorname{kern} \tilde{\varphi}} {.}
Dann ist
\mavergleichskettedisp
{\vergleichskette
{ \tilde{\varphi} ([x])
}
{ =} { \varphi(x)
}
{ =} { e_H
}
{ } {}
{ } {}
}
{}{}{,}
also
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ \operatorname{kern} \varphi
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Damit ist
\mavergleichskette
{\vergleichskette
{ [x]
}
{ = }{ e_Q
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
d.h. der Kern von $\tilde{\varphi}$ ist trivial und nach
Lemma 5.12
ist $\tilde{\varphi}$ auch injektiv.
\inputfaktbeweis
{Gruppenhomomorphismus/Faktorisierung/Fakt}
{Satz}
{}
{
\faktsituation {Es seien
\mathkor {} {G} {und} {H} {}
\definitionsverweis {Gruppen}{}{}
und sei
\maabbdisp {\varphi} {G} {H
} {}
ein
\definitionsverweis {Gruppenhomomorphismus}{}{.}}
\faktfolgerung {Dann gibt es eine kanonische Faktorisierung
\mathdisp {G \stackrel{q}{\longrightarrow} G/ \operatorname{kern} \varphi \stackrel{\theta}{\longrightarrow} \operatorname{bild} \varphi \stackrel{\iota} {\hookrightarrow} H} { , }
wobei $q$ die
\definitionsverweis {kanonische Projektion}{}{,}
$\theta$ ein
\definitionsverweis {Gruppenisomorphismus}{}{}
und $\iota$ die kanonische Inklusion der
\definitionsverweis {Bildgruppe}{}{}
ist.}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt aus
Korollar 8.2,
angewandt auf die Bildgruppe
\mavergleichskette
{\vergleichskette
{ U
}
{ = }{ \operatorname{bild} \varphi
}
{ \subseteq }{ H
}
{ }{
}
{ }{
}
}
{}{}{.}
Diese Aussage wird häufig kurz und prägnant so formuliert:
\einrueckung{
\betonung{Bild $=$ Urbild modulo Kern}{.}}
\inputfaktbeweis
{Gruppentheorie/Isomorphiesatz für Restklassengruppen/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $G$ eine
\definitionsverweis {Gruppe}{}{}
und
\mavergleichskette
{\vergleichskette
{ N
}
{ \subseteq }{ G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Normalteiler}{}{} mit der
\definitionsverweis {Restklassengruppe}{}{}
\mavergleichskette
{\vergleichskette
{Q
}
{ = }{G/N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei
\mavergleichskette
{\vergleichskette
{H
}
{ \subseteq }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein weiterer Normalteiler in $G$, der $N$ umfasst.}
\faktfolgerung {Dann ist das
\definitionsverweis {Bild}{}{}
$\overline{H}$ von $H$ in $Q$ ein Normalteiler und es gilt die kanonische
\definitionsverweis {Isomorphie}{}{}
\mavergleichskettedisp
{\vergleichskette
{ G/H
}
{ \cong} { Q/ \overline{H}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Für die erste Aussage siehe
Aufgabe *****.
Damit ist die Restklassengruppe
\mathl{Q/\overline{H}}{} wohldefiniert. Wir betrachten die Komposition
\mathdisp {p \circ q : G \longrightarrow Q \longrightarrow Q/\overline{H}} { . }
Wegen
\mavergleichskettealign
{\vergleichskettealign
{ \operatorname{kern} \left( p \circ q \right)
}
{ =} { { \left\{ x \in G \mid (p \circ q) (x) = e \right\} }
}
{ =} { { \left\{ x \in G \mid q (x) \in \operatorname{kern} p \right\} }
}
{ =} { { \left\{ x \in G \mid q (x) \in \overline{H} \right\} }
}
{ =} {H
}
}
{}
{}{}
ist
\mavergleichskette
{\vergleichskette
{ \operatorname{kern} \left( p \circ q \right)
}
{ = }{ H
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Daher ergibt
Korollar 8.2
die kanonische Isomorphie
\maabbdisp {} {G/H} {Q/\overline{H}
} {.}
Kurz gesagt ist also
\mavergleichskettedisp
{\vergleichskette
{ G/H
}
{ =} {(G/N)/(H/N)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
\zwischenueberschrift{Permutationsgruppen}
Seien
\mathl{M_1,M_2,M_3,M_4}{} Mengen und es seien Abbildungen
\mathdisp {M_1 \stackrel{\varphi_1}{\longrightarrow} M_2 \stackrel{\varphi_2}{\longrightarrow} M_3 \stackrel{\varphi_3}{\longrightarrow} M_4} { }
gegeben. Dann ist es egal, ob man die Hintereinanderschaltung der drei Abbildungen als
\mathl{\verknuepfung {(\verknuepfung {\varphi_1} {\varphi_2})} {\varphi_3}}{} oder als
\mathl{\verknuepfung {\varphi_1} {(\verknuepfung {\varphi_2} {\varphi_3})}}{}
auffasst. Das ist die natürliche Assoziativität für Abbildungen.
\inputdefinition
{}
{
Es sei $M$ eine beliebige Menge. Dann ist die Menge
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{Abb} \, (M)
}
{ =} { \operatorname{Abb} \, { \left( M , M \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
der
\definitionsverweis {Abbildungen}{}{}
von $M$ in sich mit der
\definitionsverweis {Hintereinanderschaltung}{}{}
von Abbildungen als Verknüpfung und mit der
\definitionsverweis {Identität}{}{}
als neutralem Element ein
\definitionsverweis {Monoid}{}{,}
das man das \definitionswort {Abbildungsmonoid}{} zu $M$ nennt.
}
\inputdefinition
{}
{
Zu einer Menge $M$ nennt man die Menge
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{Aut} \, (M)
}
{ =} { \operatorname{Perm} \,( M)
}
{ =} { { \left\{ \varphi:M \longrightarrow M \mid \varphi \text{ bijektiv} \right\} }
}
{ } {
}
{ } {
}
}
{}{}{}
der bijektiven Selbstabbildungen die \definitionswort {Automorphismengruppe}{} oder die \definitionswort {Permutationsgruppe}{} zu $M$.
}
Eine bijektive Selbstabbildung
\maabb {\varphi} {M} {M
} {}
nennt man auch eine \stichwort {Permutation} {.} Für eine endliche Menge
\mathl{I=\{1 , \ldots , n\}}{} schreibt man
\mathl{S_n=\operatorname{Perm} \,(I)}{.} Wir werden uns hauptsächlich auf endliche Permutationsgruppen beschränken. Eine endliche Permutation kann man beispielsweise mit einer
\zusatzklammer {vollständigen} {} {}
Wertetabelle oder mit einem Pfeildiagramm beschreiben.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Composicion_de_permutaciones.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Composicion de permutaciones.svg } {} {Drini} {Commons} {CC-by-SA 3.0} {}
\inputfaktbeweis
{Endliche Permutationsgruppe/Anzahl/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei $M$ eine endliche Menge mit $n$ Elementen.}
\faktfolgerung {Dann besitzt die
\definitionsverweis {Permutationsgruppe}{}{}
\mavergleichskette
{\vergleichskette
{ \operatorname{Perm} \,( M)
}
{ \cong }{ S_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau $n!$ Elemente.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei
\mavergleichskette
{\vergleichskette
{ M
}
{ = }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Für die $1$ gibt es $n$ mögliche Bilder, für $2$ gibt es noch
\mathl{n-1}{} mögliche Bilder, für $3$ gibt es noch
\mathl{n-2}{} mögliche Bilder, usw. Daher gibt es insgesamt
\mavergleichskettedisp
{\vergleichskette
{ n(n-1)(n-2) \cdots 2 \cdot 1
}
{ =} { n !
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mögliche Permutationen.
\inputfaktbeweis
{Menge und Teilmenge/Permutation/Untergruppe/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei $M$ eine Menge und $N \subseteq M$ eine Teilmenge.}
\faktfolgerung {Dann gibt es eine natürliche injektive Abbildung
\maabbeledisp {} { \operatorname{Perm} \, (N) } { \operatorname{Perm} \, (M) } { \sigma} { \tilde{ \sigma} } {,}
wobei $\tilde{\sigma}$ auf $N$ gleich $\sigma$ und auf
\mathl{M \setminus N}{} die Identität ist.}
\faktzusatz {Mittels dieser Abbildung ist $\operatorname{Perm} \, (N)$ eine
\definitionsverweis {Untergruppe}{}{} von $\operatorname{Perm} \, (M)$.}
\faktzusatz {}
}
{
Offenbar ist die Abbildung wohldefiniert. Sie ist injektiv, da aus
\mavergleichskette
{\vergleichskette
{ \tilde{\sigma}
}
{ = }{ \tilde{\tau}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sofort folgt, dass
\mavergleichskette
{\vergleichskette
{ \sigma
}
{ = }{ \tau
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Die Abbildung liefert eine Bijektion zwischen $\operatorname{Perm} \, (N)$ und der Menge der Permutationen auf $M$, die
\mathl{M \setminus N}{} fest lassen. Diese Permutationen bilden eine Untergruppe.
\inputbemerkung
{}
{
Das vorstehende Lemma besagt bei
\mathl{M=\{1 , \ldots , n \}}{} und
\mathl{N=\{1 , \ldots , n-1 \}}{,} dass
\mathl{S_{n-1} \subseteq S_n}{} eine Untergruppe ist. Diese Untergruppe ist bei
\mathl{n \geq 3}{} kein Normalteiler. Sie hat den Index $n$, woraus sich erneut durch Induktion ergibt, dass die Permutationsgruppe $S_n$ die Ordnung $n!$ besitzt.
}
Permutationsgruppen tauchen in vielen unterschiedlichen Situationen auf, und zwar häufig dann, wenn man sich die Wirkungsweise einer Gruppe auf einem geometrischen Objekt anschaut, wie im folgenden Beispiel
\zusatzklammer {Zykel und Transposition werden sofort definiert} {} {.}
\inputbeispiel{}
{
Wir betrachten die Gruppe der eigentlichen Bewegungen an einem Würfel. Für eine fixierte Raumdiagonale $W$ betrachten wir die Untergruppe $H$ derjenigen Bewegungen, die diese Raumdiagonale in sich überführen. Das sind einerseits die drei Drehungen um diese Achse um $0,120,240$ Grad, andererseits aber auch die drei Halbdrehungen um diejenigen Kantenmittelpunktsachsen, deren Kanten nicht an den Ecken von $W$ anliegen. Diese drei Halbdrehungen führen ebenfalls $W$ in sich über, wobei allerdings die Eckpunkte vertauscht werden.
Es seien $B,G$ und $R$ die drei anderen Raumdiagonalachsen. Dann definiert jede Bewegung aus $H$ eine Permutation der Menge $\{B,G,R\}$. Die beiden Dritteldrehungen definieren dabei die beiden Zykel \mathkor {} {\langle B,G,R \rangle} {und} {\langle B,R,G \rangle} {,} und die drei Halbdrehungen definieren jeweils eine Transposition. Damit ist $H$ isomorph zu $S_3$ und somit ist $S_3$ eine Untergruppe der Würfelgruppe.
}
\zwischenueberschrift{Zykeldarstellung für Permutationen}
Sei $M$ eine endliche Menge,
\mathl{\sigma \in \operatorname{Perm} \,(M)}{} eine Permutation und
\mathl{x \in M}{.} Dann kann man die Folge
\mathdisp {\sigma^0(x)=\operatorname{id} \, (x)=x,\, \sigma^1(x)= \sigma(x),\, \sigma^2(x), \, \sigma^3(x) \ldots ,} { }
betrachten. Da $M$ endlich ist, gibt es eine Wiederholung \mathkon { \sigma^{i} (x) = \sigma^{j} (x) } { mit } { i <j }{ .} Durch Multiplikation mit
\mathl{\sigma^{-i}}{} sieht man, dass es ein minimales
\mathl{k\in \N_+}{} gibt mit
\mathl{\sigma^k (x) = \sigma^0(x)=x}{,} und dass alle
\mathl{\sigma^{j}(x)}{} für
\mathbed {j} {}
{1 \leq j <k} {}
{} {} {} {,} verschieden sind. Ist
\mathl{y= \sigma^j(x)}{,} so durchläuft auch
\mathl{\sigma^{i} (y)}{} dieselbe Teilmenge aus $M$.
\inputdefinition
{}
{
Es sei $M$ eine endliche Menge und $\pi$ eine
\definitionsverweis {Permutation}{}{}
auf $M$. Man nennt $\pi$ einen \definitionswort {Zykel der Ordnung}{} $r$, wenn es eine $r$-elementige Teilmenge
\mavergleichskette
{\vergleichskette
{Z
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart gibt, dass $\pi$ auf
\mathl{M \setminus Z}{} die Identität ist und $\pi$ die Elemente aus $Z$ zyklisch vertauscht. Wenn
\mavergleichskette
{\vergleichskette
{Z
}
{ = }{ \{z, \pi(z),\, \pi^2(z) , \ldots , \pi^{r-1}(z)\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so schreibt man einfach
\mavergleichskettedisp
{\vergleichskette
{ \pi
}
{ =} { \langle z, \pi(z),\, \pi^2(z) , \ldots , \pi^{r-1}(z) \rangle
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
Dabei kann man statt $z$ jedes andere Element aus $Z$ als Anfangsglied nehmen. Die Menge $Z$ heißt auch der \stichwort {Wirkungsbereich} {} des Zykels, und die (geordnete) Auflistung heißt die \stichwort {Wirkungsfolge} {} des Zykels.
\inputdefinition
{}
{
Eine \definitionswort {Transposition}{} auf einer endlichen Menge $M$ ist eine \definitionsverweis {Permutation}{}{} auf $M$, die genau zwei Elemente miteinander vertauscht und alle anderen Elemente unverändert lässt.
}
Eine Transposition ist also ein besonders einfacher Zykel mit der Zyklendarstellung
\mathl{\langle x, y \rangle}{,} wenn die Transposition die Punkte \mathkon { x } { und } { y }{ } vertauscht.
\inputfaktbeweis
{Endliche Permutation/Darstellung mit Transpositionen/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Jede
\definitionsverweis {Permutation}{}{}
auf einer endlichen Menge $M$}
\faktfolgerung {kann man als Produkt von
\definitionsverweis {Transpositionen}{}{}
schreiben.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir beweisen die Aussage durch Induktion über die Anzahl der Menge $M$. Für
\mavergleichskette
{\vergleichskette
{ { \# \left( M \right) }
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist nichts zu zeigen, sei also
\mavergleichskette
{\vergleichskette
{ { \# \left( M \right) }
}
{ \geq }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Die Identität ist das leere Produkt aus Transpositionen. Es sei also $\pi$ nicht die Identität, und sei
\mavergleichskette
{\vergleichskette
{ \pi(x)
}
{ = }{ y
}
{ \neq }{x
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei $\tau$ die Transposition, die $x$ und $y$ vertauscht. Dann ist $y$ ein
\definitionsverweis {Fixpunkt}{}{}
von $\pi \tau$, und man kann $\pi \tau$ auffassen als eine Permutation auf
\mavergleichskette
{\vergleichskette
{ M'
}
{ = }{M \setminus \{y\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Nach Induktionsvoraussetzung gibt es dann Transpositionen $\tau_j$ auf $M'$ mit
\mavergleichskette
{\vergleichskette
{\pi \tau
}
{ = }{ \prod_j \tau_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auf $M'$. Dies gilt dann auch auf $M$, und daher ist
\mavergleichskette
{\vergleichskette
{ \pi
}
{ = }{ { \left( \prod_j \tau_j \right) } \tau
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\inputfaktbeweis
{Permutationen/Zyklendarstellung/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei $M$ eine endliche Menge und $\sigma$ eine Permutation auf $M$.}
\faktfolgerung {Dann gibt es eine Darstellung
\mavergleichskettedisp
{\vergleichskette
{ \sigma
}
{ =} { \sigma_1 \cdots \sigma_k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei die $\sigma_i$
\definitionsverweis {Zykel}{}{}
der Ordnung $\geq 2$ sind mit disjunkten Wirkungsbereichen.}
\faktzusatz {Dabei ist die Darstellung bis auf die Reihenfolge eindeutig.}
\faktzusatz {}
}
{
Es sei $F$ die Fixpunktmenge von $\sigma$ und es seien
\mathl{Z_1 , \ldots , Z_k}{} diejenigen Teilmengen von $M$ mit mindestens zwei Elementen derart, dass $\sigma$ die Elemente aus jedem $Z_i$ zyklisch vertauscht. Dann ist $M$ die disjunkte Vereinigung aus $F$ und den $Z_i$. Zu
\mathbed {i} {}
{1 \leq i \leq k} {}
{} {} {} {,} sei $\sigma_i$ der
\definitionsverweis {Zykel}{}{}
auf $M$, der auf
\mathl{M \setminus Z_i}{} die Identität ist und auf $Z_i$ mit $\sigma$ übereinstimmt. Wir behaupten
\mavergleichskettedisp
{\vergleichskette
{ \sigma
}
{ =} { \sigma_1 \cdots \sigma_k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Um dies einzusehen, sei
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
beliebig. Bei
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist $x$ ein Fixpunkt für alle $\sigma_i$ und daher kommt links und rechts wieder $x$ raus. Es sei also $x$ kein Fixpunkt der Permutation. Dann gehört
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ Z_i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für genau ein $i$. Für alle
\mathl{j \neq i}{} ist $x$ ein Fixpunkt von $\sigma_j$. Da
\mavergleichskettedisp
{\vergleichskette
{ y
}
{ =} { \sigma(x)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ebenfalls zu $Z_i$ gehört, ist auch $y$ ein Fixpunkt von $\sigma_j$ für alle
\mavergleichskette
{\vergleichskette
{ j
}
{ \neq }{ i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wendet man daher die rechte Seite auf $x$ an, so wird $x$ auf $x$ abgebildet bis man zu $\sigma_i$ kommt. Dieses bildet $x$ auf $y$ ab und die folgenden $\sigma_j$ bilden $y$ auf $y$ ab, sodass die rechte Seite insgesamt $x$ auf $y$ schickt und daher mit $\sigma$ übereinstimmt.
Aufgrund von diesem Satz können wir allgemein eine Zyklendarstellung für eine beliebige Permutation definieren.
\inputdefinition
{}
{
Es sei $M$ eine endliche Menge und $\sigma$ eine
\definitionsverweis {Permutation}{}{}
auf $M$. Es seien
\mathl{Z_1 , \ldots , Z_k}{} die Wirkungsbereiche der
\definitionsverweis {Zyklen}{}{}
von $\sigma$ mit
\mavergleichskette
{\vergleichskette
{n_i
}
{ = }{ { \# \left( Z_i \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei
\mavergleichskette
{\vergleichskette
{x_i
}
{ \in }{Z_i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{Z_i
}
{ = }{\{x_i, \sigma(x_i) , \ldots , \sigma^{n_i-1}(x_i)\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann nennt man
\mathdisp {\langle x_1, \sigma(x_1) , \ldots , \sigma^{n_1-1}(x_1) \rangle \langle x_2, \sigma(x_2) , \ldots , \sigma^{n_2-1}(x_2) \rangle \cdots \langle x_k, \sigma(x_k) , \ldots , \sigma^{n_k-1}(x_k) \rangle} { }
die \definitionswort {Zyklendarstellung}{} von $\sigma$.
}
Diese Schreibweise ist wie in Satz 8.14 zu verstehen, dass also $\sigma$ das Produkt der $k$ Zykel ist, die jeweils durch ihre Wirkungsfolge angegeben werden.