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.

Definition 
Ein Monoid ist ein Tripel  bestehend aus einer Menge , einer inneren zweistelligen Verknüpfung
 
und einem ausgezeichneten Element  mit den folgenden Eigenschaften bezüglich der angegebenen Verknüpfung:
 Assoziativität der Verknüpfung:
 
  ist ein neutrales Element:
 

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.

Bemerkungen zur Notation 
Die Assoziativität (Teil 1. der Definition) rechtfertigt das Weglassen von Klammern: Für den binären Operator  ist der Term  zunächst mehrdeutig. Weil aber das Ergebnis bezüglich der durch Klammerung festgelegten Auswertungsreihenfolge invariant ist, kann man hier auf die Klammern verzichten.

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  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  das Symbol  benutzt, man spricht dann von einem multiplikativ geschriebenen Monoid. Das neutrale Element heißt dann Einselement und wird durch  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  das Symbol  benutzt wird. Das neutrale Element heißt dann Nullelement und wird durch  symbolisiert. Additiv geschriebene Monoide sind üblicherweise kommutativ.

Beispiele und Gegenbeispiele

Untermonoid 
Eine Teilmenge  eines Monoids , die das neutrale Element  enthält und bezüglich der Verknüpfung  von  abgeschlossen ist (d. h., für alle  ist auch ), heißt Untermonoid von .

Monoid-Homomorphismus 
Ein Monoid-Homomorphismus ist definiert als eine Abbildung  zwischen zwei Monoiden , , für die gilt:
 ,
 .

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

Das Bild  eines Monoid-Homomorphismus  ist ein Untermonoid des Zielmonoids .

Ist der Monoid-Homomorphismus  bijektiv, dann nennt man ihn einen Monoid-Isomorphismus und die Monoide  und  isomorph.

Freies Monoid 
Ein Monoid  heißt frei, wenn es eine Teilmenge  gibt, so dass sich jedes Element von  eindeutig als endliches Produkt von Elementen aus  darstellen lässt.  heißt dann Basis (Erzeuger) des Monoids.

Ist  irgendeine Menge, dann bildet die Menge  aller endlichen Folgen in  mit dem Hintereinanderschreiben der Folgen als multiplikative Verknüpfung  und der leeren Folge als neutralem Element  das Monoid . Dieses Monoid nennt man das von  erzeugte freie Monoid. Ist die Menge  endlich, dann spricht man meist vom Alphabet  und von Worten oder Wörtern über diesem Alphabet; man erhält das bereits erwähnte Wortmonoid.

Das freie Monoid  über einer Menge  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  über  erfüllt folgende universelle Eigenschaft:
Ist  ein Monoid und  eine beliebige Funktion, dann gibt es genau einen Monoid-Homomorphismus  mit  für alle . Solche Homomorphismen werden in der theoretischen Informatik zur Definition formaler Sprachen (als Teilmengen von ) genutzt.

Hat ein Monoid  eine Teilmenge , so dass sich jedes Element von  eindeutig bis auf die Reihenfolge der Faktoren als Produkt von Elementen aus  darstellen lässt, dann nennt man  frei kommutativ mit dem Erzeuger . Ein solches Monoid ist notwendig kommutativ.  ist in diesem Fall die Menge der Multimengen die Elemente von  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.

Beispiele 
 Das Monoid  ist sowohl frei als auch frei kommutativ mit dem Erzeuger .
 Für eine Menge  ist die Menge  aller Abbildungen von  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  als Erzeuger (dabei ist  ein Kronecker-Delta).
 Das Nullmonoid  ist sowohl frei als auch frei kommutativ mit der leeren Menge als Erzeuger.
 Das Monoid  ist frei kommutativ über der Menge der Primzahlen, es ist aber kein freies Monoid.
 Die Kleenesche Hülle  ist das von dem Alphabet  bezüglich der 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 

Algebraische Struktur
Algebra
Theorie formaler Sprachen