Monoid

In der abstrakten Algebra ist ein Monoid eine algebraische Struktur bestehend aus einer Menge mit einer klammerfrei notierbaren (assoziativen) Verknüpfung und einem neutralen Element. Ein Beispiel sind die natürlichen Zahlen mit der Multiplikation und der Zahl 1 als neutralem Element. Ein Monoid, in dem jedes Element invertierbar ist, heißt Gruppe.

Ein Monoid ist ein Tripel ( M , ∗ , e ) {\displaystyle \left(M,*,e\right)} bestehend aus einer Menge M {\displaystyle M} , einer inneren zweistelligen Verknüpfung

∗ : M × M → M , ( a , b ) ↦ a ∗ b {\displaystyle *\colon M\times M\to M,\quad (a,b)\mapsto a*b}

und einem ausgezeichneten Element e ∈ M {\displaystyle e\in M} mit den folgenden Eigenschaften bezüglich der angegebenen Verknüpfung:

1. Assoziativität der Verknüpfung:

   ∀ a , b , c ∈ M :   ( a ∗ b ) ∗ c = a ∗ ( b ∗ c ) {\displaystyle \forall a,b,c\in M\colon \ (a*b)*c=a*(b*c)}

2. e {\displaystyle e} ist ein neutrales Element:

   ∀ a ∈ M :   e ∗ a = a ∗ e = a {\displaystyle \forall a\in M\colon \ e*a=a*e=a}

Ein Monoid ist also eine Halbgruppe mit neutralem Element. Jede Gruppe ist ein Monoid, aber ein Monoid hat im Gegensatz zur Gruppe nicht notwendigerweise inverse Elemente.

In einem Monoid ist das neutrale Element eindeutig bestimmt. Wenn aus dem Kontext ersichtlich ist, welches das neutrale Element ist, wird ein Monoid oft auch verkürzt als Paar ( M , ∗ ) {\displaystyle \left(M,*\right)} geschrieben. Dies entspricht allerdings nicht der Normalform für (heterogene und) universelle Algebren, da das Axiom für das Neutralelement dann einen – zu vermeidenden – Existenzquantor erfordert.

Häufig wird für die Verknüpfung ∗ {\displaystyle *} das Symbol ⋅ {\displaystyle \,\!\cdot } benutzt, man spricht dann von einem multiplikativ geschriebenen Monoid. Das neutrale Element heißt dann Einselement und wird durch 1 {\displaystyle 1} symbolisiert. Wie auch bei der gewöhnlichen Multiplikation üblich, kann in vielen Situationen der Malpunkt weggelassen werden.

Ein Monoid lässt sich auch additiv notieren, indem für die Verknüpfung ∗ {\displaystyle *} das Symbol + {\displaystyle +} benutzt wird. Das neutrale Element heißt dann Nullelement und wird durch 0 {\displaystyle 0} symbolisiert. Additiv geschriebene Monoide sind üblicherweise kommutativ.

( N 0 , + , 0 ) {\displaystyle \left(\mathbb {N} _{0},+,0\right)}	ist ein Monoid.
( N , ⋅ , 1 ) {\displaystyle (\mathbb {N} ,\cdot ,1)}	ist ein Monoid. Damit ist ( N 0 , + , 0 , ⋅ , 1 ) {\displaystyle (\mathbb {N} _{0},+,0,\cdot ,1)} ein (Bewertungs-)Halbring.
( Z , + , 0 ) {\displaystyle (\mathbb {Z} ,+,0)}	(die Menge der ganzen Zahlen mit der Addition) ist ein Monoid.
( Z , − , 0 ) {\displaystyle (\mathbb {Z} ,-,0)}	ist kein Monoid, da die Subtraktion nicht assoziativ ist.
( R n × n , ⋅ , I n ) {\displaystyle \left(\mathbb {R} ^{n\times n},\cdot ,I_{n}\right)}	(die Menge der reellen n × n   {\displaystyle n\!\times \!n\!\ } -Matrizen mit der üblichen Matrizenmultiplikation und der Einheitsmatrix I n {\displaystyle I_{n}} ) ist ein Monoid und für n ≥ 2 {\displaystyle n\geq 2} nichtkommutativ.
( R 3 , × , 0 → ) {\displaystyle \left(\mathbb {R} ^{3},\times ,{\vec {0}}\right)}	(der dreidimensionale reelle Raum mit dem Vektorprodukt) ist kein Monoid, da das Assoziativgesetz verletzt ist: Bezeichnen wir mit e i {\displaystyle e_{i}} den i-ten Einheitsvektor, so ist ( e 1 × e 1 ) × e 2 = 0 {\displaystyle (e_{1}\times e_{1})\times e_{2}=0} , aber e 1 × ( e 1 × e 2 ) = − e 2 {\displaystyle e_{1}\times (e_{1}\times e_{2})=-e_{2}} .
( n Z , + , 0 ) {\displaystyle (n\mathbb {Z} ,+,0)}	(die Menge der Vielfachen der ganzen Zahl n mit der Addition) ist ein Monoid (sogar eine Gruppe).
( Q + , + , 0 ) {\displaystyle \left(\mathbb {Q} _{+},+,0\right)}	(die Menge der nichtnegativen rationalen Zahlen mit der Addition) ist ein Monoid.
( Q + ∗ , ⋅ , 1 ) {\displaystyle (\mathbb {Q} _{+}^{*},\cdot ,1)}	(die Menge der positiven rationalen Zahlen mit der Multiplikation) ist ein Monoid. Damit ist ( Q + , + , 0 , ⋅ , 1 ) {\displaystyle (\mathbb {Q} _{+},+,0,\cdot ,1)} ein Halbring (sogar ein Halbkörper).
( Q + ∗ , ÷ , 1 ) {\displaystyle (\mathbb {Q} _{+}^{*},\div ,1)}	(die Menge der positiven rationalen Zahlen mit der Division) ist kein Monoid, da die Division nicht assoziativ ist.
( P ( X ) , ∩ , X ) {\displaystyle \left({\mathcal {P}}(X),\cap ,X\right)}	(die Potenzmenge einer Menge X mit dem Schnittmengenoperator) ist ein kommutatives Monoid.
( Σ ∗ , ⋅ , ε ) {\displaystyle (\Sigma ^{*},\cdot ,\varepsilon )}	die Wörter über dem Alphabet Σ {\displaystyle \Sigma } bilden mit der Konkatenation ⋅ {\displaystyle \,\!\cdot } und dem leeren Wort ε {\displaystyle \varepsilon } , das sogenannte Wortmonoid.
( End C ⁡ ( A ) , ∘ , id A ) {\displaystyle (\operatorname {End} _{\mathtt {C}}(A),\circ ,\operatorname {id} _{A})}	die Endomorphismen eines Objekts A {\displaystyle A} in einer beliebigen Kategorie C {\displaystyle {\mathtt {C}}} , d. h. die Morphismen A ⟶ C A {\displaystyle A{\underset {\mathtt {C}}{\longrightarrow }}A} . Jedes Monoid lässt sich so als Kategorie mit genau einem (beliebigen) Objekt auffassen.

In einem Monoid ( M , ∗ , e ) {\displaystyle (M,*,e)} heißt ein Element a ∈ M {\displaystyle a\in M} invertierbar, wenn es ein x ∈ M {\displaystyle x\in M} gibt mit

a ∗ x = e = x ∗ a . {\displaystyle a*x=e=x*a.}

Dieses Element x {\displaystyle x} ist dann durch a {\displaystyle a} eindeutig bestimmt und wird inverses Element von a {\displaystyle a} genannt. Es wird mit a − 1 {\displaystyle \textstyle a^{-1}} bzw. − a {\displaystyle -a} bezeichnet, falls die Verknüpfung ∗ {\displaystyle *} als Multiplikation bzw. Addition geschrieben wird.

Die Menge aller invertierbaren Elemente von M {\displaystyle M} ist eine Gruppe bezüglich der Verknüpfung ∗ . {\displaystyle *.}

• Im kommutativen Monoid ( Z , ⋅ , 1 ) {\displaystyle (\mathbb {Z} ,\,\cdot \,,1)} sind nur 1 {\displaystyle 1} und − 1 {\displaystyle -1} invertierbar.
• Im Monoid ( R n × n , ⋅ , I n ) , {\displaystyle {\big (}\mathbb {R} ^{n\times n},\,\cdot \,,I_{n}{\big )},} bestehend aus den reellen n × n   {\displaystyle n\!\times \!n\!\ } -Matrizen ( n ≥ 0 ) , {\displaystyle (n\geq 0),} ist eine Matrix genau dann invertierbar (regulär), wenn ihre Determinante ≠ 0 {\displaystyle \neq 0} ist.
• Im kommutativen Monoid ( Z / m Z , ⋅ , 1 ¯ ) , {\displaystyle {\big (}\mathbb {Z} /m\mathbb {Z} ,\,\cdot \,,{\overline {1}}{\big )},} das aus den Restklassen modulo m ≥ 1 {\displaystyle m\geq 1} besteht, ist die Restklasse α ¯ {\displaystyle {\overline {\alpha }}} einer ganzen Zahl α {\displaystyle \alpha } genau dann invertierbar, wenn g g T ( α , m ) = 1 {\displaystyle \mathrm {ggT} (\alpha ,m)=1} ist. Dieser größte gemeinsame Teiler und gegebenenfalls die inverse Restklasse α ¯   − 1 {\displaystyle {\overline {\alpha }}\!\ ^{-1}} lassen sich mit dem erweiterten euklidischen Algorithmus berechnen.

Eine Teilmenge U ⊆ M {\displaystyle U\subseteq M} eines Monoids ( M , ∗ , e ) {\displaystyle (M,*,e)} , die das neutrale Element e {\displaystyle e} enthält und bezüglich der Verknüpfung ∗ {\displaystyle *} von M {\displaystyle M} abgeschlossen ist (d. h., für alle u , v ∈ U {\displaystyle u,v\in U} ist auch u ∗ v ∈ U {\displaystyle u*v\in U} ), heißt Untermonoid von M {\displaystyle M} .

Ein Monoid-Homomorphismus ist definiert als eine Abbildung f : A → B {\displaystyle f\colon A\to B} zwischen zwei Monoiden ( A , ∗ A , e A ) {\displaystyle \left(A,*_{A},e_{A}\right)} , ( B , ∗ B , e B ) {\displaystyle \left(B,*_{B},e_{B}\right)} , für die gilt:

• ∀ x , y ∈ A : f ( x ∗ A y ) = f ( x ) ∗ B f ( y ) {\displaystyle \forall x,y\in A\colon f(x*_{A}y)=f(x)*_{B}f(y)} ,
• f ( e A ) = e B {\displaystyle f\left(e_{A}\right)=e_{B}} .

Es handelt sich hier also um eine Abbildung, die mit den Verknüpfungen in A {\displaystyle A} und B {\displaystyle B} verträglich ist und das neutrale Element von A {\displaystyle A} auf das neutrale Element von B {\displaystyle B} abbildet. Ein Monoid-Homomorphismus ist im Sinne der abstrakten Algebra ein Homomorphismus zwischen Monoiden.

Das Bild f ( A ) {\displaystyle f\left(A\right)} eines Monoid-Homomorphismus f : A → B {\displaystyle f\colon A\to B} ist ein Untermonoid des Zielmonoids B {\displaystyle B} .

Ist der Monoid-Homomorphismus f : A → B {\displaystyle f\colon A\to B} bijektiv, dann nennt man ihn einen Monoid-Isomorphismus und die Monoide A {\displaystyle A} und B {\displaystyle B} isomorph.

Ein Monoid ( M , ∗ , e ) {\displaystyle (M,*,e)} heißt frei, wenn es eine Teilmenge A ⊂ M {\displaystyle A\subset M} gibt, so dass sich jedes Element von M {\displaystyle M} eindeutig als endliches Produkt von Elementen aus A {\displaystyle A} darstellen lässt. A {\displaystyle A} heißt dann Basis (Erzeuger) des Monoids.

Ist A {\displaystyle A} irgendeine Menge, dann bildet die Menge A ∗ {\displaystyle A^{*}} aller endlichen Folgen in A {\displaystyle A} mit dem Hintereinanderschreiben der Folgen als multiplikative Verknüpfung ⋅ {\displaystyle \,\!\cdot } und der leeren Folge als neutralem Element ε {\displaystyle \varepsilon } das Monoid ( A ∗ , ⋅ , ε ) {\displaystyle (A^{*},\cdot ,\varepsilon )} . Dieses Monoid nennt man das von A {\displaystyle A} erzeugte freie Monoid. Ist die Menge A {\displaystyle A} endlich, dann spricht man meist vom Alphabet A {\displaystyle A} und von Worten oder Wörtern über diesem Alphabet; man erhält das bereits erwähnte Wortmonoid.

Das freie Monoid A ∗ {\displaystyle A^{*}} über einer Menge A {\displaystyle A} spielt in vielen Bereichen der theoretischen Informatik eine Rolle (zum Beispiel formale Sprache, regulärer Ausdruck, Automatentheorie). Siehe auch den Artikel über die Kleenesche Hülle für einen verwandten Begriff.

Das freie Monoid A ∗ {\displaystyle A^{*}} über A {\displaystyle A} erfüllt folgende universelle Eigenschaft: Ist M {\displaystyle M} ein Monoid und f : A → M {\displaystyle f\colon A\to M} eine beliebige Funktion, dann gibt es genau einen Monoid-Homomorphismus T : A ∗ → M {\displaystyle T\colon A^{*}\to M} mit T ( a ) = f ( a ) {\displaystyle T(a)=f\left(a\right)} für alle a ∈ A {\displaystyle a\in A} . Solche Homomorphismen werden in der theoretischen Informatik zur Definition formaler Sprachen (als Teilmengen von A ∗ {\displaystyle A^{*}} ) genutzt.

Hat ein Monoid ( M , ∗ , e ) {\displaystyle (M,*,e)} eine Teilmenge A {\displaystyle A} , so dass sich jedes Element von M {\displaystyle M} eindeutig bis auf die Reihenfolge der Faktoren als Produkt von Elementen aus A {\displaystyle A} darstellen lässt, dann nennt man M {\displaystyle M} frei kommutativ mit dem Erzeuger A {\displaystyle A} . Ein solches Monoid ist notwendig kommutativ. M {\displaystyle M} ist in diesem Fall die Menge der Multimengen die Elemente von A {\displaystyle A} enthalten. Ein freies Monoid mit einem wenigstens zweielementigen Erzeuger ist nicht kommutativ.

Das freie Monoid ist wie die freie Gruppe ein Beispiel eines freien Objekts in der Kategorientheorie.

• Das Monoid ( N 0 , + , 0 ) {\displaystyle (\mathbb {N} _{0},+,0)} ist sowohl frei als auch frei kommutativ mit dem Erzeuger { 1 } {\displaystyle \{1\}} .
• Für eine Menge A {\displaystyle A} ist die Menge A b b f i n ⁡ ( A , N 0 ) {\displaystyle \operatorname {Abb_{fin}} (A,\mathbb {N} _{0})} aller Abbildungen von A {\displaystyle A} in die nichtnegativen ganzen Zahlen, die nur an endlich vielen Stellen einen Wert ungleich 0 annehmen, mit der komponentenweisen Addition ein kommutatives Monoid. Es ist frei kommutativ mit den Elementarfunktionen χ a ( x ) = δ a , x {\displaystyle \chi _{a}(x)=\delta _{a,x}} als Erzeuger (dabei ist δ a , x {\displaystyle \delta _{a,x}} ein Kronecker-Delta).
• Das Nullmonoid ( { 0 } , + , 0 ) {\displaystyle (\{0\},+,0)} ist sowohl frei als auch frei kommutativ mit der leeren Menge als Erzeuger.
• Das Monoid ( N , ⋅ , 1 ) {\displaystyle (\mathbb {N} ,\cdot ,1)} ist frei kommutativ über der Menge der Primzahlen, es ist aber kein freies Monoid.
• Die Kleenesche Hülle Σ ∗ {\displaystyle \Sigma ^{*}} ist das von dem Alphabet Σ {\displaystyle \Sigma } bezüglich der Konkatenation frei erzeugte Monoid.

• Dirk Hachenberger: Mathematik für Informatiker. 2. Auflage. Pearson Studium, München 2008, ISBN 978-3-8273-7320-5, Abschnitt 6.1.

Wiktionary: Monoid – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen