Algebraische Grundstrukturen

Gruppen

Definition: Tupel

Sei \(M\) eine Menge. Unter einem \(n\)-Tupel (oder kurz Tupel) verstehen wir eine Aufzählung von \(n\) Objekten \(m_1, \dots, m_n \in M\) in einer Liste. Wir schreiben ein solches Tupel als \((m_1, \dots, m_n)\).

Im Gegensatz zu Mengen müssen die Elemente eines Tupels nicht notwendigerweise voneinander verschieden sein, d.h., das gleiche Element kann in einem Tupel mehrmals vorkommen. Überdies ist die Reihenfolge der Elemente in einem Tupel von Bedeutung. Ein 2-Tupel bezeichnet man auch als geordnetes Paar, ein 3-Tupel als Tripel und ein 4-Tupel als Quadrupel.

Definition: Verknüpfung

Sei \(M\) eine nichtleere Menge. Eine Abbildung * von \(M \times M\) nach \(M\), also \(* : M \times M \rightarrow M\), nennen wir eine Verknüpfung auf \(M\).

Beispiel: Verknüpfungen

1. Die Abbildung \(+ : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\), definiert durch \(+(a, b) := a + b\) für alle \((a, b) \in \mathbb{N} \times \mathbb{N}\), ist eine Verknüpfung auf \(\mathbb{N}\).


2. Die Abbildung \(\cdot : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}\), definiert durch \(\cdot(a, b) := a \cdot b\) für alle \((a, b) \in \mathbb{Z} \times \mathbb{Z}\), ist eine Verknüpfung auf \(\mathbb{Z}\).


3. Sei \(M\) eine nichtleere Menge und sei \(\mathcal{M} := \{f : M \rightarrow M | f \text{ ist eine Abbildung}\}\) die Menge aller Abbildungen von \(M\) nach \(M\). Weiterhin sei \(\circ\) die Komposition von Abbildungen, also \(g \circ f : M \rightarrow M, (g \circ f)(m) = g(f(m))\) mit \(f, g \in \mathcal{M}\) und \(m \in M\). Dann ist \(\circ : \mathcal{M} \times \mathcal{M} \rightarrow \mathcal{M}\) eine Verknüpfung auf \(\mathcal{M}\).

Definition: Halbgruppe

Sei \(M\) eine nichtleere Menge und sei * eine Verknüpfung auf \(M\), für die das Assoziativgesetz gilt, d.h. \((m_1 * m_2) * m_3 = m_1 * (m_2 * m_3)\) für alle \(m_1, m_2, m_3 \in M\). Dann nennen wir das Tupel \((M, *)\) eine Halbgruppe.

Beispiel: Halbgruppe

1. Seien die Abbildungen \(+ : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) und \(\cdot : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}\) wie im vorherigen Beispiel definiert. Dann sind \((\mathbb{N}, +)\) und \((\mathbb{Z}, \cdot)\) Halbgruppen.


2. Sei \(\circ : \mathcal{M} \times \mathcal{M} \rightarrow \mathcal{M}\) wie im vorherigen Beispiel definiert. Wir haben bereits gezeigt, dass die Komposition von Abbildungen assoziativ ist. Somit ist \((\mathcal{M}, \circ)\) eine Halbgruppe.

Definition: Neutrales Element

Sei \((M, *)\) eine Halbgruppe. Ein Element \(e \in M\) heißt neutrales Element in \(M\), falls für alle \(m \in M\) gilt, dass \(m * e = e * m = m\) ist.

Beispiel: Neutrales Element

1. Sei die Halbgruppe \((\mathbb{N}, +)\), wie im vorherigen Beispiel definiert, gegeben. Dann gibt es in dieser Halbgruppe kein neutrales Element, denn für alle \(a, b \in \mathbb{N}\) ist \(a + b \not = a\).


2. Die Halbgruppe \((\mathbb{N}_0, +)\) hingegen hat ein neutrales Element, und zwar 0. Es ist \(a + 0 = 0 + a = a\) für alle \(a \in \mathbb{N}_0\).


3. Die Halbgruppe \((\mathbb{Z}, \cdot)\) besitzt die 1 als neutrales Element. Es ist \(a \cdot 1 = 1 \cdot a = a\) für alle \(a \in \mathbb{Z}\).


4. Die Halbgruppe \((\mathcal{M}, \circ)\) besitzt die Identitätsabbildung \(id_M : M \rightarrow M\) mit \(id_M(m) = m\) für alle \(m \in M\) als neutrales Element. Es ist \(f \circ id_M = id_M \circ f = f\) für alle \(f \in \mathcal{M}\).

Satz: Eindeutigkeit des neutralen Elements

Sei \((M, *)\) eine Halbgruppe mit neutralem Element. Dann ist dieses neutrale Element eindeutig bestimmt.

Beweis:

Seien \(e_1\) und \(e_2\) neutrale Elemente in \((M, *)\). Dann gilt nach Definition des neutralen Elements \(e_1 = e_1 * e_2\), denn \(e_2\) ist ein neutrales Element. Weiterhin gilt \(e_1 * e_2 = e_2\), denn \(e_1\) ist ein neutrales Element. Daraus folgt insgesamt \(e_1 = e_1 * e_2 = e_2\) und somit die Eindeutigkeit des neutralen Elements. \(\square\)

Definition: Invertierbarkeit

Sei \((M, *)\) eine Halbgruppe mit neutralem Element \(e\). Ein Element \(m \in M\) heißt invertierbar, wenn es ein Element \(m' \in M\) gibt, mit \(m * m' = m' * m = e\). Das Element \(m'\) nennt man dann ein inverses Element zu \(m\). Man sagt \(m'\) ist invers zu \(m\).

Beispiel: Invertierbarkeit

1. In der Halbgruppe \((\mathbb{N}, +)\) gibt es keine invertierbaren Elemente, da es in dieser Halbgruppe insbesondere kein neutrales Element gibt.


2. In der Halbgruppe \((\mathbb{N}_0, +)\) ist 0 das neutrale Element. Die 0 ist darüber hinaus das einzige invertierbare Element. Das inverse Element zu 0 ist 0. Es gilt \(0 + 0 = 0\).


3. In der Halbgruppe \((\mathbb{Z}, \cdot)\) ist 1 das neutrale Element. Die einzigen invertierbaren Elemente sind 1 und -1. Das inverse Element zu 1 ist 1, mit \(1 \cdot 1 = 1\). Das inverse Element zu -1 ist -1, mit \((-1) \cdot (-1) = 1\).


4. Die invertierbaren Elemente in \((\mathcal{M}, \circ)\) haben wir bereits bestimmt. Es handelt sich um die bijektiven Abbildungen.

Satz: Eindeutigkeit des inversen Elements

Sei \((M, *)\) eine Halbgruppe mit neutralem Element \(e\). Sei \(m \in M\) ein invertierbares Element. Dann ist das inverse Element zu \(m\) eindeutig bestimmt.

Beweis:

Seien \(m', m'' \in M\) inverse Elemente zu \(m\), d.h. \(m * m' = m' * m = e\) und \(m * m'' = m'' * m = e\). Dann gilt wegen \(m'' * m = e\), dass \(m' = e * m' = (m'' * m) * m'\) ist. Mit der Assoziativität der Verknüpfung folgt weiter \((m'' * m) * m' = m'' * (m * m') = m'' * e = m''\) und damit insgesamt \(m' = m''\). \(\square\)

In Halbgruppen mit der Verknüpfung \(+\), also \((M, +)\), z.B. \((\mathbb{N}, +)\) und \((\mathbb{N}_0, +)\), bezeichnen wir das neutrale Element mit \(0\). Wenn \(a \in M\) ein invertierbares Element ist, so bezeichnen wir darüber hinaus das zu \(a\) inverse Element mit \(-a\).

In Halbgruppen mit der Verknüpfung \(\cdot\), also \((M, \cdot)\), z.B. \((\mathbb{Z}, \cdot)\), bezeichnen wir das neutrale Element mit \(1\). Wenn \(a \in M\) ein invertierbares Element ist, so bezeichnen wir darüber hinaus das zu \(a\) inverse Element mit \(a^{-1}\).

Die folgende Bezeichnung für kommutative Halbgruppen geht auf den norwegischen Mathematiker Niels Henrik Abel (1802-1829) zurück.

Definition: Abelsche Halbgruppe

Sei \((M, *)\) eine Halbgruppe. \((M, *)\) heißt kommutativ oder abelsch, falls für alle \(m_1, m_2 \in M\) das Kommutativgesetz gilt, d.h. \(m_1 * m_2 = m_2 * m_1\). Man spricht in diesem Fall von einer kommutativen Halbgruppe oder einer abelschen Halbgruppe.

Beispiel: Abelsche Halbgruppe

1. Die Halbgruppen \((\mathbb{N}, +), (\mathbb{N}_0, +)\) und \((\mathbb{Z}, \cdot)\) sind abelsch.


2. Die Halbgruppe \((\mathcal{M}, \circ)\) ist nicht abelsch, wie man sich an folgendem Beispiel überlegt: Sei \(M := \{1, 2, 3\}\). Weiterhin seien Abbildungen \(f : M \rightarrow M\) und \(g : M \rightarrow M\) gegeben durch
   \(f(1) = 1, f(2) = 3\) und \(f(3) = 2\) sowie
   \(g(1) = 3, g(2) = 2\) und \(g(3) = 1\).
   Dann ist \[(g \circ f)(1) = g(f(1)) = g(1) = 3\] \[(g \circ f)(2) = g(f(2)) = g(3) = 1\] \[(g \circ f)(3) = g(f(3)) = g(2) = 2\] und \[(f \circ g)(1) = f(g(1)) = f(3) = 2\] \[(f \circ g)(2) = f(g(2)) = f(2) = 3\] \[(f \circ g)(3) = f(g(3)) = f(1) = 1\] Somit ist \(g \circ f \not = f \circ g\).

Definition: Gruppe

Eine Gruppe ist eine Halbgruppe mit neutralem Element, in der jedes Element invertierbar ist.

Beispiel: Gruppe

1. Die Halbgruppen \((\mathbb{N}, +), (\mathbb{N}_0, +)\) und \((\mathbb{Z}, \cdot)\) sind keine Gruppen, da nicht alle ihre Elemente invertierbar sind.


2. Die Halbgruppe \((\mathcal{M}, \circ)\) ist keine Gruppe, da nicht alle ihre Elemente invertierbar sind (denn sie enthält unter Umständen auch nichtinjektive Abbildungen).


3. Sei \(M\) eine nichtleere Menge und sei \(\mathcal{M}_{inv} := \{f : M \rightarrow M|f \text{ ist eine bijektive Abbildung}\}\) die Menge aller bijektiven Abbildungen von \(M\) nach \(M\).
   Nach vorangehenden Aussagen ist die Komposition von bijektiven Abbildungen wieder bijektiv. Folglich ist \(\circ\) eine Verknüpfung auf \(\mathcal{M}_{inv}\).
   Wir haben ebenfalls gesehen, dass die Komposition von Abbildungen assoziativ ist. Damit ist \((\mathcal{M}_{inv}, \circ)\) bereits eine Halbgruppe.
   Das neutrale Element in \(\mathcal{M}_{inv}\) ist \(id_M\), denn \(id_M\) ist eine bijektive Abbildung von \(M\) nach \(M\) (und somit \(id_M \in \mathcal{M}_{inv}\)) und es ist \(f \circ id_M = id_M \circ f = f\) für alle \(f \in \mathcal{M}_{inv}\).
   Jedes Element aus \(\mathcal{M}_{inv}\) ist eine bijektive Abbildung und damit invertierbar. Darüber hinaus sind die inversen Abbildungen von bijektiven Abbildungen wieder bijektiv, liegen also ebenfalls in \(\mathcal{M}_{inv}\).
   Damit folgt, dass \((\mathcal{M}_{inv}, \circ)\) eine Gruppe ist.

Definition: Ordnung einer Gruppe

Sei \((G, *)\) eine Gruppe. Dann nennt man die Mächtigkeit der Menge \(G\), also \(|G|\), die Ordnung der Gruppe.

Für Gruppen mit endlicher Menge \(G\) entspricht die Ordnung der Gruppe also einfach der Anzahl der Elemente in \(G\).