2.2 Monoide
Definition (Monoid, neutrales Element)
Eine Halbgruppe (M, ∘) heißt Monoid, falls gilt:
Es gibt ein e ∈ M, sodass für alle a ∈ M gilt: a ∘ e = e ∘ a = a. (Existenz eines neutralen Elements)
Ein derartiges e heißt ein neutrales Element des Monoids.
∘ | e | a | b | c | … |
e | e | a | b | c | … |
a | a | a ∘ a | a ∘ b | a ∘ c | … |
b | b | b ∘ a | b ∘ b | b ∘ c | … |
c | c | c ∘ a | c ∘ b | c ∘ c | … |
… | … | … | … | … | … |
Ein neutrales Element e in der Verknüpfungstafel der Operation
Monoide sind also Halbgruppen, die ein zusätzliches Axiom erfüllen: Die Tafel von ∘ enthält eine triviale Zeile und Spalte. So unscheinbar die Eigenschaft
a ∘ e = e ∘ a = a für alle a ∈ A
sein mag, so wichtig ist die Existenz eines „nichts verändernden“ oder „neutralen“ Elements für alles Weitere. Eine wichtige Beobachtung ist:
Eindeutigkeit des neutralen Elements
Sind e und e′ neutrale Elemente eines Monoids (M, ∘), so gilt e = e′.
Sind nämlich e und e′ neutral, so gilt e = e ∘ e′ = e′, wobei wir beim ersten Gleichheitszeichen die Neutralität von e′ verwenden und beim zweiten die Neutralität von e. Wir können also fortan schreiben:
„Sei e das neutrale Element des Monoids (M, ∘).“
Zeichenwahl für das neutrale Element
Das Zeichen für das neutrale Element eines Monoids ist prinzipiell beliebig. Für die Operationszeichen ∘, ∗, ·, … wird neben e oft 1 und für das Operationszeichen + zumeist 0 verwendet.
In Monoiden können wir die für Halbgruppen erklärte Potenzierung erweitern:
Der Exponent Null und das leere Produkt
Ist M ein Monoid mit neutralem Element e, so setzen wir für alle a ∈ M:
a0 = e, ∏1 ≤ k ≤ 0 ak = e.
Die Regeln (an)m = am n und an am = an + m gelten nun für alle a ∈ M und n, m ∈ ℕ. Es gilt ∏1 ≤ k ≤ n a = an. Da das leere Produkt e ist, ist hier auch n = 0 zulässig.
Für Monoide wie (ℕ, ·) und (ℝ, ·) mit neutralem Element 1 gilt nach Definition wie gewohnt a0 = 1 für alle a, einschließlich 00 = 1.
Beispiele
(1) | ℕ, ℤ, ℚ, ℝ, ℂ mit der Addition + sind Monoide mit neutralem Element 0. Gleiches gilt für die Multiplikation, wobei dann 1 neutral ist. |
(2) | ℕ* = ℕ − { 0 } ist mit der Multiplikation ein Monoid mit neutralem Element 1. |
(3) | ℕ* ist mit der Addition eine Halbgruppe, aber kein Monoid. |
(4) | Ist e beliebig, so ist { e } ein Monoid, wenn wir e ∘ e = e definieren. |
(5) | Ist H eine Halbgruppe und e ∉ H, so können wir die Operation auf H zu einer Operation auf M = H ∪ { e } fortsetzen, indem wir definieren: a ∘ e = e ∘ a = a für alle a ∈ M. Dann ist M ein Monoid mit neutralem Element e. |
(6) | Ist A eine Menge und M = { f | f : A → A }, so ist (M, ∘) ein Monoid. Das neutrale Element ist die Identität idA : A → A. |
(7) | Seien M1, M2 Monoide mit den neutralen Elementen e1 bzw. e2. Dann ist das Produkt M = M1 × M2 der Halbgruppen M1 und M2 ein Monoid mit neutralem Element (e1, e2) (vgl. 2. 1). |
(8) | Sei (M, ·) ein Monoid mit neutralem Element e. Dann definieren wir eine Operation ∘ auf der Potenzmenge ℘(M) = { A | A ⊆ M } von M durch A ∘ B = { a · b | a ∈ A und b ∈ B } für alle A, B ⊆ M. Dann ist (℘(M), ∘) ein Monoid mit neutralem Element { e }. |
(9) | Für jede Menge M ist (℘(M), ∪) ein Monoid mit neutralem Element ∅ und (℘(M), ∩) ein Monoid mit neutralem Element M. |
Das folgende Beispiel zeigt, dass es nicht genügt, lediglich die Existenz eines einseitig neutralen Elements e mit
„a ∘ e = a für alle a ∈ M“ oder „e ∘ a = a für alle a ∈ M“
in der Definition eines Monoids zu fordern.
Beispiel
Auf der Menge H = { 0, 1 } definieren wir:
0 ∘ 0 = 1 ∘ 0 = 0, 0 ∘ 1 = 1 ∘ 1 = 1
nach der Devise „der zweite Faktor setzt sich durch“. Dann ist (H, ∘) eine Halbgruppe, aber kein Monoid, denn weder 0 noch 1 sind neutral. Für alle a ∈ H gilt 0 ∘ a = a und 1 ∘ a = a, sodass 0 und 1 sog. linksneutrale Elemente sind. Analoges gilt für die Operation „der erste Faktor setzt sich durch“.
∘ | 0 | 1 |
0 | 0 | 1 |
1 | 0 | 1 |