imported>Okoska-törp: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-02-15T14:08:24Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

{{Begriffsklärungshinweis|Zur gleichnamigen Schülerzeitschrift siehe [[Monoid (Zeitschrift)]].}}

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

== Definition ==
Ein Monoid ist ein [[Tupel|Tripel]] <math>\left(M,*,e\right)</math> bestehend aus einer Menge <math>M</math>, einer [[zweistellige Verknüpfung#Definition|inneren zweistelligen Verknüpfung]]
: <math>*\colon M\times M\to M,\quad (a,b)\mapsto a*b</math>
und einem ausgezeichneten Element <math>e\in M</math> mit den folgenden Eigenschaften bezüglich der angegebenen Verknüpfung:
# [[Assoziativität]] der Verknüpfung:
#: <math>\forall a,b,c\in M\colon (a*b)*c=a*(b*c)</math>
# <math>e</math> ist ein [[neutrales Element]]:
#: <math>\forall a\in M\colon e*a=a*e=a</math>

Ein Monoid ist also eine [[Halbgruppe]] mit neutralem Element. Jede [[Gruppe (Mathematik)|Gruppe]] ist ein Monoid, aber ein Monoid hat im Gegensatz zur Gruppe nicht notwendigerweise inverse Elemente.

=== Bemerkungen zur Notation ===
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 <math>\left(M,*\right)</math> geschrieben. Dies entspricht allerdings nicht der Normalform für (heterogene und) [[universelle Algebra|universelle Algebren]], da das Axiom für das Neutralelement dann einen – zu vermeidenden – [[Existenzquantor]] erfordert.

Häufig wird für die Verknüpfung <math>*</math> das Symbol <math>\cdot</math> benutzt, man spricht dann von einem multiplikativ geschriebenen Monoid. Das neutrale Element heißt dann ''Einselement'' und wird durch <math>1</math> 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 <math>*</math> das Symbol <math>+</math> benutzt wird. Das neutrale Element heißt dann ''Nullelement'' und wird durch <math>0</math> symbolisiert. Additiv geschriebene Monoide sind üblicherweise kommutativ.

== Beispiele und Gegenbeispiele ==
{| border="0" cellspacing="5"
| <math>\left(\mathbb{N}_0, +, 0\right) </math>
| ist ein Monoid.
|-----
| <math>(\mathbb{N}, \cdot, 1)</math>
| ist ein Monoid. Damit ist <math>(\mathbb{N}_0, +, 0, \cdot, 1)</math> ein [[Halbring (Algebraische Struktur)#Einselement|(Bewertungs-)Halbring]].
|-----
| <math>(\mathbb{Z}, +, 0) </math>
| (die Menge der [[ganze Zahl|ganzen Zahlen]] mit der Addition) ist ein Monoid.
|-----
| <math>(\mathbb{Z}, -, 0) </math>
| ist '''kein''' Monoid, da die Subtraktion nicht assoziativ ist.
|-----
| <math>\left(\mathbb{R}^{n\times n}, \cdot, E\right)</math>
| (die Menge der n×n-[[Matrix (Mathematik)|Matrizen]] mit der üblichen [[Matrizenmultiplikation]] und der [[Einheitsmatrix]] ''E'') ist ein [[Kommutativgesetz|nichtkommutatives]] Monoid.
|-----
| <math>\left(\mathbb{R}^3, \times, \vec{0}\right)</math>
| (der dreidimensionale reelle Raum mit dem [[Vektorprodukt]]) ist '''kein''' Monoid, da das Assoziativgesetz verletzt ist: Bezeichnen wir mit <math>e_i</math> den ''i''-ten [[Einheitsvektor]], so ist <math>(e_1 \times e_1)\times e_2 = 0</math>, aber <math>e_1 \times (e_1 \times e_2) = -e_2</math>.
|-----
| <math>(n\mathbb{Z},+,0)</math>
| (die Menge der [[Vielfaches|Vielfachen]] der ganzen Zahl ''n'' mit der Addition) ist ein Monoid (sogar eine [[Gruppe (Mathematik)|Gruppe]]).
|-----
| <math>\left(\mathbb{Q}_+,+,0\right)</math>
| (die Menge der nichtnegativen rationalen Zahlen mit der Addition) ist ein Monoid.
|-----
| <math>(\mathbb{Q}_+^*,\cdot,1)</math>
| (die Menge der positiven rationalen Zahlen mit der Multiplikation) ist ein Monoid. Damit ist <math>(\mathbb{Q}_+,+,0,\cdot,1)</math> ein [[Halbring (Algebraische Struktur)|Halbring]] (sogar ein [[Halbkörper]]).
|-----
| <math>(\mathbb{Q}^*_+, \div, 1)</math>
| (die Menge der positiven rationalen Zahlen mit der Division) ist '''kein''' Monoid, da die Division nicht assoziativ ist.
|-----
| <math>\left(\mathcal{P}(X),\cap,X\right)</math>
| (die [[Potenzmenge]] einer Menge ''X'' mit dem Schnittmengenoperator) ist ein kommutatives Monoid.
|-----
| <math>(\Sigma^*,\cdot,\varepsilon)</math>
| die [[Wort (Theoretische Informatik)|Wörter]] über dem Alphabet <math>\Sigma</math> bilden mit der Konkatenation <math>\cdot</math> und dem leeren Wort <math>\varepsilon</math>, das sogenannte Wortmonoid.
|-
|<math>(\operatorname{End}_{\mathtt C}(A),\circ,\operatorname{id}_A) </math>
|die Endomorphismen eines Objekts <math>A</math> in einer beliebigen Kategorie <math>\mathtt {C}</math>, d. h. die Morphismen <math>A \underset{\mathtt C}
\longrightarrow A</math>. Jedes Monoid lässt sich so als Kategorie mit genau einem (beliebigen) Objekt auffassen.
|}

== Untermonoid ==
Eine Teilmenge <math>U\subseteq M</math> eines Monoids <math>(M,*,e)</math>, die das neutrale Element <math>e</math> enthält und bezüglich der Verknüpfung <math>*</math> von <math>M</math> abgeschlossen ist (d. h., für alle <math>u,v\in U</math> ist auch <math>u*v\in U</math>), heißt ''Untermonoid'' von <math>M</math>.

== Monoid-Homomorphismus ==
Ein ''Monoid-Homomorphismus'' ist definiert als eine Abbildung <math>f\colon A \to B</math> zwischen zwei Monoiden <math>\left(A,*_A,e_A\right)</math>, <math>\left(B,*_B,e_B\right)</math>, für die gilt:
* <math>\forall x, y \in A\colon f(x *_A y) = f(x) *_B f(y)</math>,
* <math>f\left(e_A\right) = e_B</math>.

Es handelt sich hier also um eine Abbildung, die mit den Verknüpfungen in <math>A</math> und <math>B</math> verträglich ist und das neutrale Element von <math>A</math> auf das neutrale Element von <math>B</math> abbildet. Ein Monoid-Homomorphismus ist im Sinne der [[abstrakte Algebra|abstrakten Algebra]] ein [[Homomorphismus]] zwischen Monoiden.

Das [[Bildmenge|Bild]] <math>f\left(A\right)</math> eines Monoid-Homomorphismus <math>f\colon A \to B</math> ist ein Untermonoid des [[Zielmenge|Ziel]]<nowiki></nowiki>monoids <math>B</math>.

Ist der Monoid-Homomorphismus <math>f\colon A \to B</math> [[Bijektivität|bijektiv]], dann nennt man ihn einen Monoid-[[Isomorphismus]] und die Monoide <math>A</math> und <math>B</math> isomorph.

== Freies Monoid ==
Ein Monoid <math>(M,*,e)</math> heißt ''frei'', wenn es eine Teilmenge <math>A \subset M</math> gibt, so dass sich jedes Element von <math>M</math> eindeutig als endliches Produkt von Elementen aus <math>A</math> darstellen lässt. <math>A</math> heißt dann Basis (Erzeuger) des Monoids.

Ist <math>A</math> irgendeine Menge, dann bildet die Menge <math>A^*</math> aller endlichen [[Folge (Mathematik)|Folgen]] in <math>A</math> mit dem Hintereinanderschreiben der Folgen als multiplikative Verknüpfung <math>\cdot</math> und der leeren Folge als neutralem Element <math>\varepsilon</math> das Monoid <math>(A^*,\cdot,\varepsilon)</math>. Dieses Monoid nennt man ''das von <math>A</math> erzeugte freie Monoid''. Ist die Menge <math>A</math> endlich, dann spricht man meist vom Alphabet <math>A</math> und von [[Wort (Theoretische Informatik)|Worten]] oder Wörtern über diesem Alphabet; man erhält das bereits erwähnte Wortmonoid.

Das freie Monoid <math>A^*</math> über einer Menge <math>A</math> 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 <math>A^*</math> über <math>A</math> erfüllt folgende [[universelle Eigenschaft]]:
Ist <math>M</math> ein Monoid und <math>f\colon A \to M</math> eine beliebige Funktion, dann gibt es genau einen Monoid-[[Homomorphismus]] <math>T\colon A^* \to M</math> mit <math>T(a) = f\left(a\right)</math> für alle <math>a \in A</math>. Solche Homomorphismen werden in der [[Theoretische Informatik|theoretischen Informatik]] zur Definition formaler Sprachen (als Teilmengen von <math>A^*</math>) genutzt.

Hat ein Monoid <math>(M,*,e)</math> eine Teilmenge <math>A</math>, so dass sich jedes Element von <math>M</math> eindeutig ''bis auf die Reihenfolge der Faktoren'' als Produkt von Elementen aus <math>A</math> darstellen lässt, dann nennt man <math>M</math> ''frei kommutativ'' mit dem Erzeuger <math>A</math>. Ein solches Monoid ist notwendig kommutativ. <math>M</math> ist in diesem Fall die Menge der [[Multimenge]]n die Elemente von <math>A</math> enthalten. Ein freies Monoid mit einem wenigstens zweielementigen Erzeuger ist nicht kommutativ.

Das freie Monoid ist wie die [[freie Gruppe]] ein Beispiel eines [[freies Objekt|freien Objekts]] in der [[Kategorientheorie]].

=== Beispiele ===
* Das Monoid <math>(\mathbb N_0,+,0)</math> ist sowohl frei als auch frei kommutativ mit dem Erzeuger <math>\{1\}</math>.
* Für eine Menge <math>A</math> ist die Menge <math>\operatorname{Abb_{fin}}(A,\mathbb{N}_0)</math> aller Abbildungen von <math>A</math> 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 <math>\chi_a(x)=\delta_{a,x}</math> als Erzeuger (dabei ist <math>\delta_{a,x}</math> ein [[Kronecker-Delta]]).
* Das Nullmonoid <math>(\{0\},+,0)</math> ist sowohl frei als auch frei kommutativ mit der [[Leere Menge|leeren Menge]] als Erzeuger.
* Das Monoid <math>(\mathbb N,\cdot,1)</math> ist frei kommutativ über der Menge der [[Primzahl]]en, es ist aber kein freies Monoid.
* Die [[Kleenesche Hülle]] <math>\Sigma^*</math> ist das von dem [[Alphabet (Informatik)|Alphabet]] <math>\Sigma</math> bezüglich der [[Konkatenation (Wort)|Konkatenation]] frei erzeugte Monoid.

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

== Weblinks ==
{{Wiktionary}}

[[Kategorie:Algebraische Struktur]]
[[Kategorie:Algebra]]
[[Kategorie:Theorie formaler Sprachen]]

Monoid - Versionsgeschichte

imported>Okoska-törp: /* growthexperiments-addlink-summary-summary:2|0|0 */