Unterabschnitte

• Von Gruppen und anderen Strukturen
• Permutation
• Morphismen, Darstellungen, Äquivalenzrelationen

Gruppentheorie

Von Gruppen und anderen Strukturen

Kerstin Bauer, Sophia Börner, Daniel de Jong, Axel Kröner, Christoph Lehmann

Definition 1  

Eine nichtleere Menge $G$ bildet bezüglich einer Verknüpfung $\circ \colon G \times G \rightarrow G$ eine Gruppe, wenn die folgenden drei Axiome erfüllt sind:

1. Assoziativgesetz: Für beliebige Elemente $a,b,c \in G$ gilt:
   $$(a \circ b) \circ c = a \circ (b \circ c).$$

2. Existenz des neutralen Elementes: Es gibt in $G$ ein neutrales Element $e$ mit der Eigenschaft, so dass für alle $a \in G$ gilt:
   $$a \circ e = e \circ a = a.$$

3. Existenz inverser Elemente: Zu jedem $a \in G$ gibt es ein inverses Element $a^{-1}$, für das gilt:
   $$a \circ a^{-1} = a^{-1} \circ a = e.$$

Gilt darüberhinaus für eine Gruppe $G$ das Kommutativgesetz $a \circ b = b\circ a$, für alle $a,b \in G$, so heißt $G$ eine kommutative oder abelsche Gruppe.

Die Abbildung $\circ \colon G \times G \rightarrow G$ mit der Eigenschaft, dass für alle $a,b \in G$ auch $a \circ b \in G$ ist, können wir auch als abgeschlossen bezeichnen.

Beispiel 2  

Wollen wir zeigen, dass die ganzen Zahlen $\mathbb{Z}$ bezüglich der Addition eine Gruppe bilden, so müssen wir überprüfen, ob die Eigenschaften (i) bis (iii) gelten.

Das Addieren von zwei ganzen Zahlen ergibt immer wieder eine ganze Zahl, also ist die Addition eine Abbildung $+ \colon \mathbb{Z}\times \mathbb{Z}\rightarrow \mathbb{Z}$. Die Addition ist bekanntlich assoziativ. Das neutrale Element ist 0, das Inverse zu $a \in \mathbb{Z}$ ist $-a\in \mathbb{Z}$. Da es bei der Addition nicht auf die Reihenfolge ankommt, ist die Gruppe $\mathbb{Z}$ kommutativ.

Der Begriff der Gruppe ist für die verschiedensten mathematischen Modelle von großem Vorteil. Wenn alle drei Axiome für eine Verknüpfung innerhalb eines Modelles erfüllt sind, lassen sich auch alle anderen Eigenschaften von Gruppen auf dieses übertragen.

Wofür brauchen wir diese Theorie eigentlich? Ganz einfach! Verschiedene Geduldsspiele, mit denen wir uns während der Akademie befasst haben, kann man mathematisch durch Gruppen beschreiben und dementsprechend auch die mathematischen Schlussfolgerungen, die wir im Zusammenhang mit Gruppen erarbeitet haben, auf die Geduldsspiele anwenden.

Beispiel 3  

Eine Anwendung hierfür ist der Zauberwürfel (auch ,,Rubik's Cube`` genannt). Die Drehung einer Scheibe um $90^\circ$ nennen wir einen Elementarzug. Die Hintereinanderausführung von Elementarzügen bezeichnen wir als eine Zugfolge. Dabei kürzen wir aufeinanderfolgende Elemente und ihre Inversen, beispielsweise die Drehung einer Scheibe und die umgekehrte Drehung.

Alle verschiedenen Zugfolgen bilden zusammen die Elemente einer Gruppe. Die Verknüpfung $\circ$ ist die Hintereinanderausführung von Zugfolgen. Die Gruppe $G$ der Zugfolgen ist bzgl. der Verknüpfung $\circ$ abgeschlossen, denn zwei hintereinander ausgeführte Zugfolgen, ergeben wieder eine Zugfolge.

Die Assoziativität ist in natürlicher Weise gegeben, da wir die Züge nur der Reihe nach ausführen können. Das neutrale Element ist das Ausführen keines Zuges. Wir unterscheiden hier zwischen den Zugfolgen und ihrer Wirkung auf den Würfel (mathematisch modelliert durch den Begriff der Permutationsdarstellung, siehe Definition 36). Es gibt also Zugfolgen mit derselben Wirkung auf dem Würel, z. B. $R$, $LRL^{-1}$ und $R^5$. Das Zurückdrehen ist das Inverse zu einem ausgeführten Zug, da man durch Drehen der Scheibe um $90^\circ$ im Uhrzeigersinn und wieder zurück den Würfel wieder im Ausgangszustand erhält.

Ein weiteres Beispiel bildet das oben erwähnte Schiebepuzzle von Samuel Loyd, bei dem man auf einem $4 \times 4$-Feld fünfzehn Zahlenplättchen mit Hilfe von Verschiebungen in die richtige Reihenfolge bringen soll. Analog zum Würfel kann man auch hier zeigen, dass es sich beim Schiebepuzzle um eine Gruppe handelt. Wir können die Zugfolgen, die das freie Feld wieder in die ursprüngliche Lage bringen, mit der Hintereinanderausführung als Verknüpfung als Gruppe auffassen.

Natürlich haben wir im Zusammenhang mit Gruppen, Assoziativität, usw. auch mehrere Sätze bewiesen und Definitionen aufgestellt. Die wichtigsten von ihnen sind folgende:

Lemma 4  

Eine Gruppe $G$ hat höchstens ein neutrales Element.

Beweis:

Seien $e$ und $f$ neutrale Elemente von $G$. Dann gilt: $e = e \circ f = f$. $\Box$

Weil eine Gruppe nach Lemma 4 genau ein neutrales Element besitzt, nennen wir dieses neutrale Element das neutrale Element der Gruppe. Das folgende Lemma wird ähnlich bewiesen:

Lemma 5  

Das Inverse Element $g^{-1}$ zu $g \in G$ ist eindeutig bestimmt.

Satz 6  

Ist eine binäre Operation assoziativ, so führen alle Möglichkeiten der Klammerung zum gleichen Ergebnis, man kann also die Klammern weglassen.

Der Beweis sei hier nur am Beispiel mit vier Elementen angedeutet:

$$a \circ (b \circ (c \circ d))=(a \circ b) \circ (c \circ d)=((a \circ b)\circ c)\circ d.$$

Satz 7  

In einer Gruppe gilt die Kürzungsregel, d.h.:

$$g \circ x = g \circ y \Rightarrow x=y$$   und$$\qquad x \circ g = y \circ g \Rightarrow x=y.$$

Satz 8  

Sei $G$ eine Gruppe. Dann gilt

$$e^{-1} = e, \qquad (g^{-1})^{-1} = g$$   und$$\qquad (g \circ h)^{-1} = h^{-1} \circ g^{-1}$$

für alle $g,h \in G$.

Die dritte Formel des letzten Satzes ist besonders wichtig. Sie besagt, dass wenn man zwei hintereinander ausgeführte Elemente rückgängig machen will, erst das zweite und dann das erste rückgängig machen muss. Auch dies wird am Würfel sofort klar. Dreht man erst eine Scheibe und dann eine andere, muss man, um den Urzustand wieder zu erhalten, erst die zweite und dann die erste Scheibe zurückdrehen. Es gibt ein weiteres Beispiel aus dem Alltag, um sich diesen Satz zu verdeutlichen. Zieht man morgens erst das Unterhemd und dann den Pullover an, muss man abends erst den Pullover und dann das Unterhemd ausziehen.

Eine weitere Definition und ein Satz sind an dieser Stelle wichtig.

Definition 9  

Seien $g$ und $h$ zwei Elemente einer Gruppe $G$. Dann heißt das Element

$$[g,h] := g \circ h \circ g^{-1} \circ h^{-1}$$

Kommutator von $g$ und $h$.

Satz 10  

Es gilt $[g,h]=e$ genau dann, wenn $g \circ h=h \circ g$, d.h. wenn $g$ und $h$ vertauschbar sind.

Die Vertauschbarkeit kann man mit den oben genannten Beispielen verdeutlichen. Da es egal ist, ob man zuerst die Hose oder den Pullover anzieht, ist es auch egal, was man davon zuerst auszieht.

Beim Würfel gilt das nur für bestimmte Züge, zum Beispiel ist es nicht von Bedeutung, ob man erst die obere oder erst die untere Scheibe dreht; also ist es auch nicht von Bedeutung, welche Scheibe zuerst zurückgedreht wird.

Definition 11  

Eine Untermenge $H$ einer Gruppe $G$ wird Untergruppe genannt, wenn $e \in H$, $a \circ b \in H$ und $a^{-1} \in H$ für alle $a,b \in H$.

Da eine Untergruppe alle Eigenschaften der Gruppe erfüllt, ist sie selbst wieder eine Gruppe. Sie ist assoziativ, in sich abgeschlossen, enthält das neutrale Element sowie zu jedem Element das inverse Element.

Satz 12  

Sei $H$ eine nichtleere Teilmenge einer Gruppe $G$. Dann sind folgende Aussagen äquivalent:

1. $H$ ist Untergruppe von $G$.
2. Für $a,b \in H$ gilt $ab^{-1} \in H$.

Beweis:

$(i) \Rightarrow (ii)$: Sei $a,b \in H$, dann ist $b^{-1} \in H$ und $a \circ b^{-1} \in H$.
$(ii) \Rightarrow (i)$: Wähle $a \in H$, dann gilt $a \circ a^{-1}= e \in H$. Sei $a \in H$, dann folgt $e \circ a^{-1}=a^{-1} \in H$. Seien $a,b \in H$, dann ist $b^{-1} \in H$ und folglich $a \circ (b^{-1})^{-1} = a \circ b \in H$. $\Box$

Lemma 13  

Sei $D \subset G$. Dann ist die Menge aller Produkte $g_1 \circ g_2 \circ \dots \circ g_n$ mit $g_i \in D$ oder $g_i^{-1} \in D,\ i=1,\dots,n$ eine Untergruppe von $G$, die wir mit $\langle D \rangle$ bezeichnen.

Gilt $G =\langle D \rangle$, dann sagen wir auch, dass $G$ durch $D$ erzeugt wird. Eine Gruppe heißt endlich erzeugt, wenn sie von einer endlichen Menge erzeugt wird. Eine Gruppe heißt zyklisch, wenn sie von genau einem Element erzeugt werden kann.

Beispiel 14  

Überträgt man diese Definition auf den Zauberwürfel, dann stellen die Elementarzüge (Drehen der rechten, linken, oberen, unteren, vorderen, hinteren oder einer der mittleren Ebenen) die Erzeugermenge dar.

Permutation

Birte Albrecht, Markus Balthasar, Marie Gille, Mareike Heinrich, Tim Offermann

Mit Hilfe von Permutationen schaffen wir einen weitere Grundlage zur Betrachtung des Zauberwürfel. Trotzdem können wir auf eine mathematische Darstellung dieses Themas nicht verzichten!

Definition 15  

Wenn jedem Element aus einer endlichen Menge $X$ genau ein noch nicht vergebenes Element derselben Menge zugeordnet wird, so spricht man von einer Permutation. Mathematisch gesprochen ist eine Permutation eine bijektive Abbildung einer endlichen Menge auf sich selbst.

Betrachtet man die Menge $X=\{1,2,\dots,n\}$ mit $n$ Elementen ( $n \in \mathbb{N}$), so wird die Menge der Permutationen auf $X$ mit $S_n$ bezeichnet. Die Menge $S_n$ hat $n!$ Elemente (Permutationen).

Um sich mühsame Abbildungsschreibweisen zu ersparen, werden Permutationen in Form von Matrix- oder Listenschreibweise angegeben. Für $g \in S_4$ mit $g(1)=2$, $g(2)=3$, $g(3)=1$ und $g(4)=4$ nutzen wir folgende Notation:

Matrixschreibweise:	$\left(\begin{array}{cccc}1&2&3&4\\ 2&3&1&4\end{array}\right)$
Listenschreibweise:	$[\,2,\hspace{1.1ex}3,\hspace{1.1ex}1,\hspace{1.1ex}4\,]$

Definition 16  

Das Produkt zweier Permutationen $g,h \in S_n$ ist definiert als die Verkettung $g \circ h$ bzw. $gh$ von $g$ und $h$, dabei gilt

$$(gh)(x):=g(h(x))$$

für alle $x \in X$.

Es wird also zuerst $h$ und dann $g$ angewandt. Um diese Reihenfolge der Auswertung zu verdeutlichen, schreiben wir $\circ$ als Verknüpfungszeichen.

Um zu klären, ob es sich bei der Menge $S_n$ mit der Verknüpfung von Permutationen um eine Gruppe handelt, müssen folgende Kriterien überprüft werden:

Abgeschlossenheit: Da es sich bei dem Produkt mehrerer Permutationen aus $S_n$ wiederum um eine Permutation aus $S_n$ handelt, ist diese abgeschlossen.

Assoziativität: Permutationen sind assoziativ (der Beweis erfordert nur ausdauerhaftes Aufschreiben und wird daher dem Leser überlassen).

Existenz eines neutralen Elements: Die Permutation, die jedes Element aus $X$ auf sich selbst abbildet, nennt man die Identität. Das neutrale Element in $S_n$ ist die Indentität.

$$e=\left(\begin{array}{cccc}1&2&3\dots n\\ 1&2&3\dots n\end{array}\right)$$

Existenz eines Inversen: Da jede Permutation umkehrbar ist, existiert für jedes Element $g \in S_n$ auch ein Inverses, nämlich die inverse Abbildung $g^{-1}: X\rightarrow X$.

Nur die Gruppen $S_1$ und $S_2$ sind kommutativ, alle anderen Gruppen $S_n$ mit $n>2$ sind nicht kommutativ.
Beweis:

Gegenbeispiel: Wenn wir zum Beispiel $a,b \in S_3$ mit $a= [2,3,1], b= [1,3,2]$ wählen, so gilt $a \circ b = [2,1,3] \ne b \circ a = [3,2,1]$. $\Box$

Fixpunkte und Träger

Definition 17  

$g$ sei eine Permutation in $S_n$. Die Fixpunkte von $g$ sind die Elemente von {1, 2, ..., n}, für die gilt: $g(i) = i$. Die Menge aller Fixpunkte von $g$ nennen wir $\operatorname{fix}(g)$. Der Träger $\operatorname{supp}(g)$ von $g$ ist das Komplement zu $\operatorname{fix}(g)$ in $X$, also

$$\operatorname{fix}(g) = \{ \, x \in X \, \vert \, g(x) = x \, \}$$

$$\operatorname{supp}(g) = \{ \, x \in X \, \vert \, g(x) \neq x \, \}$$

Beispiel 18  

Zur Verdeutlichung betrachten wir zwei Elemente $g,h \in S_4$. Es gilt

$$g = [2, 4, 3, 1] \operatorname{fix}(g) = \{3\} \operatorname{supp}(g) = \{1, 2, 4\}$$

$$h = [1, 3, 2, 4] \operatorname{fix}(h) = \{1, 4\} \operatorname{supp}(h) = \{2, 3\}.$$

Zykel

Zykeln kann man durch einen Kreis veranschaulichen: Wenn man sich $m$ Elemente an $m$ Stellen auf dem Rand eines Kreises vorstellt, dann bewegt $g$ jedes Element zur nächsten Stelle, so dass das letzte Element auf die Stelle des ersten verschoben wird.

Definition 19   Sei $g \in S_n$ mit Träger $\operatorname{supp}(g) = \{a_1, \dots, a_m\}$. Wir nennen $g$ einen $m$-Zykel, wenn $g(a_i) = a_{i+1}$ für alle $1 \le i < m$ und $g(a_m) = a_1$ gilt.

Zykeln schreibt man in der Zykelschreibweise mit runden Klammern:
$g = (a_1, a_2, \dots, a_m)$. Wir nennen $2$-Zykel auch Transpositionen.

Unter einem $m$-Zyklus versteht man also diejenige Permutation, welche $a_1$ auf $a_2$, $a_2$ auf $a_3, \dots, a_{m-1}$ auf $a_m$, und schließlich $a_m$ auf $a_1$ abbildet.
Ein $1$-Zykel ist das neutrale Element $e$.

Beispiel 20  

Wir können die Elemente von $S_3$ in der Zykelschreibweise durch

$$S_3 = \{ e, (1, 2), (1, 3), (2, 3), (1, 2, 3), (1, 3, 2)\}$$

darstellen.

Definition 21  

Zwei Zykeln $c$ und $c^{\star}$ heißen disjunkt, wenn die Schnittmenge ihrer Träger leer ist.
Zwei disjunkte Zykeln sind immer vertauschbar. Ebenso vertauschen ein Zykel ( $a_1, \dots, a_m$) und der zugehörige inverse Zyklus ( $a_m, \dots, a_1$).

Beispiel 22  

Der Zykel $(1, 2)$ ist disjunkt zu $(3, 4)$, es gilt also $(1, 2) \circ (3, 4) = (3, 4) \circ (1, 2)$. Außerdem sind $(1,2,3)$ und der inverse Zykel $(3,2,1)$ kommutativ: $(1, 2, 3) \circ (3, 2, 1) = (3, 2, 1) \circ (1, 2, 3)$.

Gegeben seien zwei Zykel $a = (a_1, \dots, a_m)$ und $b = (b_1, \dots, b_n)$, wobei die ersten $r$ Zahlen übereinstimmen, also $a_1 = b_1, \dots, a_r = b_r$ mit $r < m, n$ sowie $a_i \neq b_i$ für $r+1 \le i \le m, n$. Wir wollen den Kommutator $[a, b] := a \circ b \circ a^{-1} \circ b^{-1}$ berechnen.

Die Elemente von $a_3$ bis $a_r$ werden auf sich selbst abgebildet, da sie zweimal nach ,,unten`` und zweimal nach ,,oben`` verschoben werden. Weiter wird $a_{r+1}$ mit $b_{r+1}$ vertauscht, sowie $a_1$ und $a_2$. Sonst werden keine anderen Element von der Permutation bewegt. Es enstehen also zwei Zykeln, und zwar Transpositionen, welche im Fall $r>1$ disjunkt sind. Es gilt also

$$[a,b]=a \circ b \circ a^{-1} \circ b^{-1} = (a_1, a_2) \circ (a_{r+1}, b_{r+1}).$$

Satz 23  

Jedes Element der Menge $S_n$ ist ein Produkt aus disjunkten Zykeln. Das Produkt ist bis auf die Reihenfolge der Zykeln eindeutig.

Man kann daher jede Permutation durch das Produkt von disjunkten Zykeln darstellen; dies nennt man auch die disjunkte Zykel-Schreibweise. $1$-Zykel werden dabei nicht berücksichtigt.

Beispiel 24  

Die disjunkte Zykel-Schreibweise von $g = [3, 5, 4, 1, 2, 6] \in S_6$ ist $(1, 3, 4) \circ (2, 5)$.

Definition 25  

Die Zykel-Struktur einer Permutation ist die (ungeordnete) Folge von Zykellängen einer Permutation in disjunkter Zykel-Schreibweise. Jede Permutation hat also eine eindeutige Zykel-Struktur.

Beispiel 26  

Die Zykelstruktur vom vorherigen Beispiel ist $3,2$.

Die disjunkte Zykel-Schreibweise ist besonders dann sinnvoll, wenn sehr viele Fixpunkte in $S_n$ enthalten sind. Da die Fixpunkte von der Permutation nicht bewegt werden, können sie in der Zykel-Schreibweise ausgelassen werden. Beispielsweise können wir die Permutation $g = [7, 5, 4, 1, 8, 6, 3, 2, 9, 10, 11, 12] \in S_{12}$ in disjunkter Zykel-Schreibweise auch schreiben als $(1, 7, 3, 4) \circ (2, 5, 8)$.

Konjugation

Eine Konjugation kann man als eine Umbenennung auffassen.

Definition 27   Sei $G$ eine Gruppe mit $g,h \in G$, dann heißt die Abbildung $g\rightarrow hgh^{-1}$ Konjugation mit $h$.

Beispiel 28  

Wir betrachten ein gleichseitiges Dreieck, bei dem wir die Ecken mit $1$, $2$ und $3$ bezeichnen. Bei der Spiegelung dieses Dreiecks an der Höhe durch die Ecke $2$ wird $1\rightarrow 3$, $2\rightarrow 2$ und $3\rightarrow 1$ abgebildet. Dies entspricht dem $2$-Zykel $(1,3)$. Bei der Drehung dieses Dreiecks um $120^\circ$ gegen den Uhrzeigersinn wird $1\rightarrow 3$, $2\rightarrow 1$, und $3\rightarrow 2$ abgebildet. Dies entspricht dem $3$-Zykel $(1,3,2)$.

Wenn wir die Ecken jedoch der Reihe nach mit $1',3'$ und $2'$ bezeichnen (siehe Abb. $2$), so erhalten wir aus der Spiegelung an derselben Achse einen $2$-Zykel $(1',2')$ und aus der Drehung einen $3$-Zykel $(1',2',3')$. So ist mit Hilfe von $h$ eine ,,Umbenennung`` des Zykels $(1,3)$ zum Zykel $(1',2')$ und für die Drehung von $(1,3,2)$ nach $(1,2,3)$ gelungen. Es gilt also $h(1,3)h^{-1}=(1',2')$ und $h(1,3,2)h^{-1}=(1',2',3')$ mit $h(1)=1'$, $h(2)=3'$ und $h(3)=2'$.

Diese Anwendung ist wichtig für das Lösen eines Würfels. Man muss also nur einmal einen Weg finden, um z.B. drei Ecken miteinander zu vertauschen. Mit Hilfe der Konjugation können wir diesen Schritt dann auf andere Ecken übertragen.

Signum einer Permutation

Permutationen können nicht nur als Verknüpfung beliebiger disjunkter Zykeln ausgedrückt werden, sondern auch durch das Produkt von Transpositionen. Es gilt nämlich

$$(a_{1}, a_{2}, \dots, a_{n})=(a_{1}, a_{2}) \circ (a_{2}, a_{3}) \circ \dots \circ(a_{m-1},a_{m}).$$

Beispiel 29  

Dies gilt auch für die folgende Permutation: $(2, 4, 1, 3)=(2, 4)\circ(4, 1)\circ(1, 3)$.

Satz 30  

Wir nehmen an, dass sich eine Permutation auf zwei Arten als Produkt von Transpositionen darstellen lässt. Dann bestehen beide Produkte entweder aus einer geraden Anzahl von Transpositionen oder beide aus einer ungeraden Anzahl von Transpositionen.

Betrachten wir die Produkte

$$(1,2)\circ(3,4)\circ(2,3)$$   und$$\quad (1,2)\circ(2, 4) \circ (1,2) \circ(4, 3) \circ (1,2),$$

so sieht man, dass sie beide die Permutation $[2,4,1,3]$ beschreiben.

Abhängig davon, ob die Permutation aus einer geraden oder ungeraden Anzahl von Transpositionen besteht, definieren wir eine Vorzeichenfunktion, die wir Signum nennen. Satz 30 rechtfertigt folgende Definition:

Definition 31  

Wir nennen eine Permutation gerade (ungerade), wenn sie sich als Produkt einer geraden (ungeraden) Anzahl von Transpositionen darstellen lässt. Das Signum $sgn(g)$ einer geraden Permutation $g$ setzen wir $1$ und das Signum einer ungeraden Permutation setzen wir $-1$.

Zum Beispiel hat die Permutation $[2,1,4,3]=(1,2)(3,4)$ das Signum $1$.

Satz 32  

Das Signum ist multiplikativ, d.h. es gilt

$$\operatorname{sgn}(g \circ h)=\operatorname{sgn}(g) \operatorname{sgn}(h).$$

Beweis:

Der Beweis ist einfach. Für das Produkt zweier ungerader oder gerader Permutationen $g$ und $h$ gilt $\operatorname{sgn}(g \circ h)=1$. Analog gilt für ein gemischtes Produkt mit einer ungeraden Permutation und einer geraden Permutation $\operatorname{sgn}(g \circ h)=-1$. $\Box$

Alternierende Gruppe

Die Menge aller geraden Permutationen in $S_n$ bildet eine Untergruppe, die wir alternierende Gruppe $A_n$ nennen. Da $S_n$ aus der gleichen Anzahl ungerader und gerader Elemente besteht, enthält $A_n$ genau $n!/2$ Elemente.

Jede gerade Permutation kann als ein Produkt von $3$-Zykeln geschrieben werden. Wenn $a,b$ und $c$ paarweise verschieden sind, dann gilt $(a,b)\circ(c,d)=(a,b)\circ(b,c)\circ(b, c)\circ(c,d)=(a,b,c)\circ(b,c,d)$.

Diese Erkenntnisse lassen sich unmittelbar auf das bereits vorgestellte Schiebepuzzle von Samuel Loyd anwenden. Wir betrachten alle Zugfolgen, die das freie Feld wieder auf seinen ursprünglichen Platz zurückführen. Diese können nur aus einer geraden Anzahl von Transpositionen bestehen, da jede Bewegung nach rechts (oben) durch eine Bewegung nach links (unten) kompensiert werden muss. Alle diese geraden Permutationen im Puzzle lassen sich letztendlich auf $3$-Zykeln zurückführen. Der direkte Tausch benachbarter Segmente ist also nicht möglich, denn dies würde eine Transposition und somit eine ungerade Permutation darstellen. Wenn im Ausgangszustand allerdings genau zwei benachbarte Plättchen vertauscht sind, ist das Puzzle folglich nicht lösbar. Listigerweise lies Sam Loyd sein Puzzle in solch einer unlösbaren Startposition verteilen. Da er beim Patentamt so ehrlich war und zugab, dass sein Puzzle unlösbar wäre, bekam er auch kein Patent ...

Morphismen, Darstellungen, Äquivalenzrelationen

Dominik Klein, Anja von Olnhausen, Martin Sallge, Miriam Schneider, Stefan Walter

Definition 33  

Seien $(G,\circ,e)$ und $(G',\star,e')$ zwei Gruppen. Eine Abbildung $f \colon G \to G'$ heißt Morphismus, wenn

$$f(a\circ b) = f(a) \star f(b)$$

für alle $a,b \in G$ gilt. Ein bijektiver Morphismus heißt Isomorphismus.

Ein Morphismus ist also eine strukturerhaltende Abbildung. Bei Gruppen heißt das, dass das neutrale Element übertragen wird, ebenso wie die Verknüpfung und das Inverse wie man leicht aus der Definition folgern kann. Ein Beispiel eines Morphismus ist die Signum-Abbildung, siehe Satz 32.

Definition 34  

Die Abbildung $f \colon G \to G'$ sei ein Morphismus. Die Mengen

$$f(G) = \{ \, f(x) \, \vert \, x \in G \, \} \quad \ker(f) = \{ \, x \in G \, \vert \, f(x) = e' \, \}$$

heißen Bild bzw. Kern des Morphismus $f$.

Satz 35  

Die Abbildung $f \colon G \to G'$ sei ein Morphismus.

1. Das Bild $f(G)$ ist eine Untergruppe von $G'$.
2. Der Kern $ker(f)$ ist eine Untergruppe von $G$.
3. Die Abbildung $f$ ist genau dann injektiv, wenn $ker(f) = \{e\}$.
4. Die Umkehrung eines Isomorphismus ist wieder ein Isomorphismus.

Darstellungen

Zunächst fangen wir wieder mit Definitionen an .... Sei $\operatorname{Sym}(X)$ die Gruppe aller eineindeutigen (bijektiven) Abbildungen von $X$ auf $X$. Speziell ist $S_n=\operatorname{Sym}(\{1,\dots,n\})$.

Definition 36  

Eine Permutationsdarstellung einer Gruppe $G$ auf $X$ ist ein Morphismus von $G$ in $\operatorname{Sym}(X)$, also

$$f \colon G \to \operatorname{Sym}(X).$$

Beim Zauberwürfel betrachten wir die Gruppe $G$ der Zugfolgen und ihre Permutationsdarstellung auf der Menge der Positionen $X$ des Würfels. Dabei besteht die Menge der Positionen $X$ (beim einfachen $3 \times 3$-Würfel) aus der Menge der Ecken und Kanten jeweils mit Orientierung. Dem Elementarzug $R$ werden beispielsweise die beiden $4$-Zykeln der entsprechenden Ecken und Kanten zugeordnet.

Die Permutationsdarstellung ist insofern wichtig, um zwischen physikalisch durchgeführten Zugfolgen und ihrer Wirkung auf dem Würfel zu unterscheiden. Es gibt beispielsweise beim $3 \times 3$-Würfel Züge, die scheinbar nichts verändern, jedoch das Mittelplättchen drehen. Das kann dadurch sichtbar gemacht werden, dass man zuvor einen Strich vom Mittelplättchen zu einem beliebigen benachbarten Kantenkubie macht. Je nachdem, ob man diese ,,unsichtbaren`` Drehungen betrachten will oder nicht, verwendet man verschiedene Permutationsdarstellungen der Gruppe der Zugfolgen.

Äquivalenzrelationen

Oft ist bei der Untersuchung und bei dem Vergleich bestimmter Strukturen lediglich eine bestimmte Eigenschaft von Interesse; alle Objekte, die diese Eigenschaft besitzen, sind als gleichwertig (äquivalent) anzusehen. Ein Beispiel hierfür ist die Auswertung von Wahlen, bei der zwei Wähler gleichwertig sind, wenn sie die gleiche Partei gewählt haben. Eine solche Gleichheit wird mathematisch durch eine Äquivalenzrelation $\sim$ ausgedrückt, die durch folgende Eigenschaften definiert ist:

Definition 37  

Eine Relation $\sim$ auf $X$ heißt Äquivalenzrelation, wenn sie folgende Eigenschaften aufweist (jeweils für alle $x, y, z \in X$):

1. reflexiv ($x \sim x$),
2. symmetrisch ( $x \sim y \Leftrightarrow y \sim x$)
3. transititv ( $x \sim y \wedge y \sim z \Rightarrow x \sim z$).

Die Menge aller Elemente, die zu $x$ äquivalent sind, wird als Äquivalenzklasse von $x$ bezeichntet, man schreibt $[x]$.

Bahnen

Nachdem die Begriffe der Permutationsdarstellung und der Äquivalenzrelation eingeführt wurden, können wir nun die Äquivalenzrelation itso (in the same orbit) auf der Permutationsdarsellung $f \colon G \to \operatorname{Sym}(X)$ untersuchen. Für $x,y \in G$ gelte $X \sim Y$ genau dann, wenn es ein $g \in G$ mit $g(x) = y$ (oder genauer gesagt $(f(g))(x) = y$) gibt. Die Äquivalenzklassen dieser Äquivalenzrelation werden als Bahnen bezeichnet.

Ein Beispiel hierfür bildet die Darstellung der Gruppe der Zugfolgen aus einem Zauberwürfel. Hier besteht eine Bahn aus allen Positionen, die durch Verdrehung aus einer bestimmten Position erreicht werden kann. Alle ,,lösbaren`` Positionen des Würfels liegen also in der Äquivalenzklasse der Ausgangsposition.

Stabilisator

Bei der Lösung des Würfels tritt irgendwann zwangsläufig das Problem auf, bestimmte Vertauschungen durchzuführen, ohne andere Kubies, die schon an ihrem korrekten Ort und in der korrekten Orientierung sind, zu verändern. Wir suchen also solche Zugfolgen $g \in G$, die bestimmte Positionen $x$ eines Kubies nicht verändern. Man sagt, dass ein $g \in G$, das $x$ nicht verändert, das Element $x$ stabilisiert. Die Menge $G_x$ aller $g \in G$, die $x$ stabilisieren, heißt Stabilisator von $x$, also

$$G_x\colon =\{ \, g \in G \, \vert \, g(x)=x \, \}.$$

Man kann zeigen, dass $G_x$ eine Untergruppe von $G$ ist.

Satz von Lagrange

Satz 38  

Sei $H$ eine Untergruppe der endlichen Gruppe $G$. Dann gilt:

$$\vert G\vert = \vert H\vert \cdot k,$$

wobei $k$ eine ganze Zahl ist. Das heißt, dass die Anzahl der Elemente der Untergruppe H multipliziert mit einem Faktor $k$ die Anzahl der Elemente der Gruppe $G$ ergibt. Speziell folgt, dass die Ordnung von $g \in G$ die Anzahl der Elemente von $G$ teilt.

Lemma 39  

Sei $G$ eine endliche Gruppe und $p$ eine Primzahl, die $\vert G\vert$ teilt. Dann existiert ein Element $g \in G$ der Ordnung $p$.

Wir können dieses Lemma auf den Würfel anwenden: Wenn wir wissen, dass $11$ ein Teiler der Anzahl der durch Zugfolgen erreichbaren Durchmischungen ist, dann muss es eine Zugfolge geben, die nach $11$-maligem Anwenden den Würfel wieder in sich selber, also in die Ausgangsstellung, überführt.