2.1 Halbgruppen
Definition (Halbgruppe, Assoziativgesetz)
Seien H eine Menge und ∘ : H2 → H eine (zweistellige) Operation auf H. Dann heißt das Paar (H, ∘) eine Halbgruppe, falls gilt:
(a ∘ b) ∘ c = a ∘ (b ∘ c) für alle a, b, c ∈ H. (Assoziativgesetz)
Zweistufige „Verarbeitung“ von drei Objekten a, b, c.
Bei einer assoziativen Operation ist (a ∘ b) ∘ c = a ∘ (b ∘ c).
Eine Halbgruppe ist also eine mit einer assoziativen Operation ausgestattete Menge. Wir schreiben a ∘ b statt ∘(a, b). Im Begriff „Operation auf H“ ist enthalten, dass der Wertebereich von ∘ eine Teilmenge von H ist (vgl. 1. 8). Es gilt also
a ∘ b ∈ H für alle a, b ∈ H.
Andere Schreibweisen
Das Zeichen ∘ steht für eine beliebige Operation und hat oft nichts mit der Komposition von Funktionen zu tun. Ist H eine Menge von Funktionen, so ist jedoch ∘ die Komposition von Funktionen, wenn nichts anderes gesagt wird. Statt ∘ können wir ein beliebiges anderes Zeichen verwenden. Typische Operationszeichen sind ∗, ·, +. Das Gleiche gilt für die zugrunde gelegte Menge. Man kann schreiben:
„Sei (M, +) eine Halbgruppe.“
Dies bedeutet, dass + : M2 → M und dass a + (b + c) = (a + b) + c für alle a, b, c ∈ M. Auch hier hat die Operation + in vielen Fällen nichts mit der Addition auf einer Zahlenmenge wie ℕ oder ℝ zu tun. Für das Zeichen + sind bestimmte Notationen reserviert, die wir im Folgenden kennenlernen werden.
Vereinfachung der Notation
Anstelle von (H, ∘) schreibt und sagt man oft auch nur H. Eine Operation ist dann stillschweigend mit dabei. So sagt man zum Beispiel: „Ist H eine Halbgruppe, so gilt a ∘ (b ∘ b) = (a ∘ b) ∘ b für alle a und b in H.“ Diese bewusste Verwechslung einer Struktur (H, ∘) mit ihrer Trägermenge H wird in vielen Fällen durchgeführt. Sie ist in der Regel ungefährlich und erleichtert die Sprechweise.
Weglassen des Operationszeichens
Ist das Operationszeichen von + verschieden, so lässt man es oft weg. So schreibt man zum Beispiel ab statt a · b und a(bc) statt a ∗ (b ∗ c) usw.
Beispiele
(1) | ℕ, ℤ, ℚ, ℝ, ℂ bilden mit der üblichen Addition Halbgruppen. Das Gleiche gilt für die Multiplikation. |
(2) | Ist G = { 2n | n ∈ ℕ } die Menge der geraden und U = ℕ − G die Menge der ungeraden Zahlen, so sind (G, +), (G, ·) und (U, ·) mit der üblichen Addition und Multiplikation Halbgruppen. Dagegen ist (U, +) keine Halbgruppe, da + wegen 1 + 1 ∉ U keine Operation auf U ist. |
(3) | Ist A eine Menge und H = { f | f : A → A }, so ist (H, ∘) eine Halbgruppe. Gleiches gilt für H′ = { f | f : A → A ist injektiv }. |
(4) | Setzen wir a ∘ b = |b − a| für alle a, b ∈ ℤ, so ist (ℤ, ∘) keine Halbgruppe, da zum Beispiel (1 ∘ 2) ∘ 3 = 1 ∘ 3 = 2, aber 1 ∘ (2 ∘ 3) = 1 ∘ 1 = 0. |
(5) | Sind H1 und H2 Halbgruppen und ist H = H1 × H2, so setzen wir (a, b) ∘ (c, d) = (ac, bd) für alle (a, b), (c, d) ∈ H. Dann ist (H, ∘) eine Halbgruppe. Sie heißt das Produkt von H1 und H2. |
Das Assoziativgesetz ist ein unverzichtbarer Begleiter bei den allermeisten algebraischen Unternehmungen. Seine Wirkung können wir so zusammenfassen:
Wir dürfen Klammern weglassen.
Da nämlich a ∘ (b ∘ c) = (a ∘ b) ∘ c für alle Elemente einer Halbgruppe gilt, können wir kurz a ∘ b ∘ c schreiben. Allgemein gilt (s ∘ t) ∘ u = s ∘ (t ∘ u) für alle Terme s, t, u, sodass wir einfach s ∘ t ∘ u oder stu schreiben können. Ein Term ist dabei ein aus Variablen, dem Operationszeichen und Klammern aufgebauter Ausdruck wie (a ∘ a) ∘ (b ∘ (c ∘ a)).
Beispiel
In Halbgruppen ist a ∘ b ∘ c ∘ d unzweideutig, da
((a ∘ b) ∘ c) ∘ d = (a ∘ b) ∘ (c ∘ d) = a ∘ (b ∘ (c ∘ d)) = a ∘ ((b ∘ c) ∘ d) = …
Wir führen ein:
Potenzen und Produkte
Ist H eine Halbgruppe, so definieren wir für alle a, a1, …, an ∈ H und n ≥ 1 rekursiv:
a1 = a, an + 1 = an ∘ a, (Potenzen)
∏1 ≤ k ≤ 1 ak = a1, ∏1 ≤ k ≤ n + 1 ak = (∏1 ≤ k ≤ n ak) ∘ an + 1. (Produkt)
Induktiv zeigt man die folgenden Potenzregeln:
(an)m = am n, an am = an + m für alle a ∈ H und n, m ≥ 1.
Beispiele
a2 ∘ b2 = a ∘ a ∘ b ∘ b, (a ∘ b)2 = a ∘ b ∘ a ∘ b.