Gruppen

Wir alle haben mit den ganzen Zahlen gerechnet; Schon in der Schule. Jetzt schauen wir, was die Addition von ganzen Zahlen ausmacht. Das sind zwei Dinge: (1) Ich kann immer Null addieren, ohne das Ergebnis zu aendern. (2) Egal welche Zahl \(x\) ich habe, ich kann immer ein \(-x\) finden, sodass \(x + (-x) = 0\). Solch eine Struktur finden wir aber auch an anderen Orten. Bspw. bei den rationalen Zahlen bez. Multiplikation¹, oder der Menge aller Permutationen auf \(n\) Elementen². Da wir all diese Fälle gleich behandeln und besser verstehen wollen, formulieren wir eine Definition, die auf alle anwendbar ist. Diese Definition nennen wir eine Gruppe. Das schauen wir uns hier genauer an.

Bevor es losgeht, möchte ich versuchen Unklarheiten zu beseitigen. Ein typischer Verständnisfehler liegt darin, nur die ganzen Zahlen als Gruppe zu betrachten. Das Konzept einer Gruppe ist allerdings allgemeiner. Die ganzen Zahlen bezüglich Addition sind eine Gruppe, aber nicht die Einzige. Außerdem ist es wichtig, über welche Verknüpfung man spricht. Bei den ganzen Zahlen könnten wir Addition oder Multiplikation betrachten und sehen, dass eines davon keine Gruppe ist³! Es reicht also nicht aus, einfach zu sagen die ganzen Zahlen seien eine Gruppe. Vielmehr geht es um die Verknüpfung, die wir betrachten. Deshalb: Denkt bei dem Begriff einer Gruppe gerne an die ganzen Zahlen mit Addition, es ist ein konkretes Beispiel dafür. Seid Euch aber bewusst, dass es nur ein Beispiel für eine Gruppe ist, und es viel, viel mehr gibt.

Am Anfang War Die Null

Bei den ganzen Zahlen gibt es die Null. Sie kann zu jeder Zahl addiert werden, ohne den Wert zu ändern; \(5 + 0\) ist das Selbe wie \(5\). Ein Element, welches bezüglich einer Verknüpfung “nichts tut” bezeichnen wir als neutrales Element. Gehen wir einen Schritt weg vom Beispiel der ganzen Zahlen und definieren einmal, was ein neutrales Element ist. Sei \(G\) eine Menge und \(*\) eine Verknüpfung auf \(G\), dann ist \(e\) ein neutrales Element, wenn für alle \(g\) gilt \(g * e = g\). In dieser Definition tauchen weder die ganzen Zahlen, noch die Addition auf!

Was sind weitere Beispiele für neutrale Elemente, neben \(0\) in \((\mathbb{Z}, +)\)⁴? Hier liste ich ein paar auf. Wichtig ist nicht sich an all diese Beispiele zu erinnern, sondern zu verstehen, warum diese Beispiele wirklich neutrale Elemente sind.

1. \(1\) bezüglich \((\mathbb{Q}, \cdot)\)
2. \([0]\) bezüglich \((\mathbb{Z}/ n, +)\)
3. \(Id\)⁵ bezüglich der Menge aller bijektiven Funktionen auf \(n\) Elementen und der Funktionenkomposition.

Genauso gibt es Beispiele für Mengen, die kein neutrales Element besitzen. Nehmen wir die ungeraden Zahlen bezüglich der Addition, so sehen wir relativ schnell, dass es kein neutrales Element gibt. Hier bräuchten wir nämlich die \(0\), welche allerdings gerade ist und damit nicht in der Menge enthalten. Daher hat diese Menge kein neutrales Element.

Auf Jeden Topf Passt ein Deckel

Jetzt wissen wir, was ein neutrales Element ist. Damit haben wir das Pendant zu \(0\) bezüglich \((\mathbb{Z}, +)\) gefunden. Die nächste Eigenschaft, die wir isolieren wollen, besteht aus der Existenz von Inversen. So kann ich für ein \(x \in \mathbb{Z}\) immer ein \(-x \in \mathbb{Z}\) finden, sodass \(x - x = 0\). Man soll also für jedes \(x\) ein Element finden, das wenn man es mit \(x\) verknüpft das neutrale Element erhält. Das ist im Grunde eine Definition von Inversen, wie sie in Gruppen genutzt wird.

Auch für Inverse gibt es Beispiele in anderen Mengen. Beispielsweise ist für \(x \in \mathbb{Q}\) \(\frac{1}{x} \in \mathbb{Q}\) ein Inverses bezüglich der Multiplikation. Bei Restklassen ist es nicht mehr so leicht. Wie wir letzt Woche gesehen haben, gibt es nicht immer ein Inverses modulo \(n\). Beispielsweise hat \(2\) kein Inverses modulo \(6\), \(3\) allerdings. Damit sehen wir einen interessanten Unterschied: Im ersten Beispiel haben wir immer ein Inverses. Im Zweiten Beispiel nicht unbedingt. Dieser Unterschied ist für die Definition von Gruppen wichtig, da wir in ihrerer Definition fordern, dass jedes Element ein Inverses hat. Es reicht nicht aus bloß für einige Elemente ein Inverses zu haben.

Die Symmetrische Gruppe

Jetzt wo wir wissen was eine Gruppe ist, schauen wir uns ein erstmal komisch wirkendes Beispiel an. Statt Zahlen zu betrachten geht es hier um Funktionen und ihre Komposition. Genauer sprechen wir über die Menge aller bijektiven Funktionen über der Menge \(\{1, \dots, n\}\)⁶. Die Verknüpfung ist die Komposition von Abbildungen, also das “hintereinander ausführen” der Abbildungen. Diese Gruppe taucht in unterschiedlichen Bereichen auf. Außerdem gibt es zwei spezielle Arten eine solche Funktion zu beschreiben. Wir schauen uns beide Arten an und vergleichen sie.

Die Symmetrische Gruppe über \(n\) Elementen, geschrieben als \(S_n\) oder \(\mathfrak{S}_n\), ist die Menge aller Permutationen⁷ auf \(n\) Elementen. Diese bildet bezüglich der Komposition von Funktionen eine Gruppe. Von einem Beweis sehe ich ab, gebe stattdessen eine Inuition dafür. In einer Gruppe müssen wir sowohl ein neutrales Element als auch Inverse haben. Die Identitätsabbildung Id ist ein neutrales Element. Habe ich beispielsweise eine Permutation \(f\) und führe danach die Identitätsabbildung aus, so ändert sich nichts; die Identitätsabbildung vertauscht keine Elemente miteinander. Für die Inversen ist wichtig, dass Permutationen bijektiv sind. Denn bijektive Abbildungen besitzen immer eine Umkehrabbildung, die ebenfalls bijektiv ist. Deshalb hat jede Permutation auch ein Inverses.⁸

Wie sehen solche Permutationen aus? Natürlich kann ich eine Funktionsvorschrift geben, wie wir das meistens tun. Permutationen liefern jedoch weitere Möglichkeiten der Darstellung. So kann ich eine Permutation in Form einer Wertetabelle aufschreiben, wo die erste Zeile angibt welches Element ich einsetze und die zweite Zeile sagt, welches Element ich erhalte. Eine beispielhafte Wertetabelle für eine Permutation aus \(S_5\) habe ich unterhalb dargestellt. Diese Tabelle gibt vor, dass wir \(1\) auf \(2\) abbilden, \(2\) auf \(3\), usw. Man muss einfach eine Spalte betrachten. Wir sehen also, dass wir eine “schöne” Art haben Permutationen aufzuschreiben. Allerdings geht es noch kompakter und einleuchtender. Dafür müssen wir aber verstehen woraus sich Permutationen zusammensetzen.

\[\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix}\]

Es ist tatsächlich so, dass die Permutation oben sich aus “kleineren”, “simpleren” Permutationen zusammensetzt.⁹ Um das zu sehen schauen wir, welche Elemente wir von der \(1\) aus durch wiederholtes Anwenden der Permutation erreichen können. Zuerst können wir von \(1\) auf \(2\) abbilden. Erneutes anwenden der Permutation bildet nun die \(2\) auf \(3\) ab. Zuletzt bilden wir dann die \(3\) auf die \(1\) ab. Damit sind wir wieder an unserem Start, der \(1\), angekommen. Wir gehen also von \(1\) zu \(2\) zu \(3\) und dann wieder zur \(1\). Dadurch erhalten wir einen Kreis, oder auch Zykel genannt. Das gleiche Spiel können wir von der \(4\) startend spielen. Dann bildet die \(4\) auf die \(5\), und die \(5\) wieder auf die \(4\) ab. Wir sehen also, dass die gesamte Permutation sich durch solche kleineren Zykel versehen lässt. Interessanterweise ist das kein Zufall. Stattdessen bestehen Permutationen immer aus solchen Zykeln. Weshalb wir eine neue Schreibweise für Permutationen haben, welche wir Zykelschreibweise nennen – ein Beispiel findest du wieder unterhalb des Absatzes. Bei dieser schreiben wir nicht zwei Zeilen übereinander, sondern die einzelnen Zykel hintereinander. In diesem Beispiel haben wir zuerst den Zykel der durch \(1,2,3\) gegeben wird aufgeschrieben und anschließend den durch \(4\) und \(5\).

\[ \begin{pmatrix} 1 & 2 & 3 \end{pmatrix} \begin{pmatrix}4 & 5\end{pmatrix} \]

Beide Schreibweisen haben ihre Vorteile. Ich finde, beispielsweise, dass man die Zykelschreibweise besser potenzieren kann, wohingegen die Wertetabelle ein leichtes invertieren ermöglicht.¹⁰ Am Ende des Tages sind aber beide gleichwertig und es werden auch beide genutzt.