In der abstrakten Algebra, einem Zweig der Mathematik, ist ein monoid eine algebraische Struktur mit einer einzelnen assoziativen binären Operation und einem Identitätselement. Monoids werden in der Halbgruppentheorie studiert, weil sie natürlich Halbgruppen mit der Identität sind. Monoids kommen in mehreren Zweigen der Mathematik vor; zum Beispiel können sie als Kategorien mit einem einzelnen Gegenstand betrachtet werden. So gewinnen sie die Idee von der Funktionszusammensetzung innerhalb eines Satzes. Monoids werden auch in der Informatik sowohl in seinen foundational Aspekten als auch in der praktischen Programmierung allgemein verwendet. Der Übergang monoid und syntaktischer monoid werden im Beschreiben von Zustandsmaschinen verwendet, wohingegen Spur monoids und Geschichte monoids ein Fundament für Prozess-Rechnungen und gleichzeitige Computerwissenschaft zur Verfügung stellen. Einige der wichtigeren Ergebnisse in der Studie von monoids sind der Lehrsatz von Krohn-Rhodos und das Sternhöhe-Problem. Die Geschichte von monoids, sowie eine Diskussion von zusätzlichen allgemeinen Eigenschaften, wird im Artikel über Halbgruppen gefunden.

Definition

Ein monoid ist ein Satz, S zusammen mit einer binären Operation "·" (ausgesprochener "Punkt" oder "Zeiten"), der die folgenden drei Axiome befriedigt:

Verschluss: Für den ganzen a, b in S, dem Ergebnis der Operation a · b ist auch in S.

Associativity: Für den ganzen a, b und c in S, die Gleichung (a · b) · c = a · (b · c) hält.

Identitätselement: Dort besteht ein Element e in S, solch das für alle Elemente in S, die Gleichung e · = a · e = ein Halten.

Und in der mathematischen Notation können wir diese als schreiben

• Verschluss:
• Associativity: und
• Identitätselement:.

Kompakter ist ein monoid eine Halbgruppe mit einem Identitätselement. Davon kann auch als ein Magma mit associativity und Identität gedacht werden. Ein monoid mit dem invertibility Eigentum ist eine Gruppe.

Das Symbol für die binäre Operation wird allgemein weggelassen; zum Beispiel verlangen die monoid Axiome und. Das bedeutet nicht notwendigerweise, dass die Variablen Zahlen sind, die multiplizieren werden, können jede Operation oder Elemente verwendet werden, wenn sie gut definiert werden.

Strukturen von Monoid

Generatoren und submonoids

Ein submonoid einer monoid M ist eine Teilmenge N von der M, die das Einheitselement, und solch dass, wenn x, y  N dann x enthält · y  N. Es ist dann klar, dass N selbst ein monoid unter der binären durch diese der M veranlassten Operation ist. Gleichwertig ist ein submonoid eine Teilmenge N solch, dass N=N *, wo der Exponent * der Stern von Kleene ist: Der Satz wird unter der Zusammensetzung oder Verkettung seiner Elemente geschlossen. Für jede Teilmenge N der M ist monoid N* der kleinste monoid, der N enthält.

Wie man

sagt, ist eine Teilmenge N ein Generator der M wenn und nur wenn M=N*. Wenn es einen begrenzten Generator der M gibt, dann, wie man sagt, wird M begrenzt erzeugt.

Auswechselbarer monoid

Ein monoid, dessen Operation auswechselbar ist, wird einen auswechselbaren monoid (oder, weniger allgemein, ein abelian monoid) genannt. Auswechselbare monoids werden häufig zusätzlich geschrieben. Jeder auswechselbare monoid ist mit seiner algebraischen Voreinrichtung , definiert durch x  y ausgestattet, wenn, und nur wenn dort solcher z dass x + z = y besteht. Eine Ordnungseinheit einer monoid ErsatzM ist ein Element u der solcher M, dass für jedes Element x der M, dort eine positive ganze Zahl n solch dass x  nu besteht. Das wird häufig verwendet, im Falle dass M der positive Kegel einer teilweise befohlenen abelian Gruppe G ist, in welchem Fall wir sagen, dass u eine Ordnungseinheit von G ist.

Teilweise auswechselbarer monoid

Ein monoid, für den die Operation für einige, aber nicht alle Elemente auswechselbar ist, ist eine Spur monoid; verfolgen Sie monoids allgemein kommen in der Theorie der gleichzeitigen Berechnung vor.

Beispiele

• Jeder Singleton ist untergegangen {x} verursacht einen besonderen (trivialen) Ein-Element-monoid. Die monoid Axiome verlangen dass x*x = x in diesem Fall.
• Jede Gruppe ist ein monoid und jede abelian Gruppe ein auswechselbarer monoid.
• Jedes begrenzte Halbgitter ist ein idempotent auswechselbarer monoid.
• Insbesondere jedes begrenzte Gitter kann sowohl mit einem Entsprechen - als auch mit einer Verbindungslinie - monoid Struktur ausgestattet sein. Die Identitätselemente sind die Spitze des Gitters und sein Boden beziehungsweise. Gitter seiend, sind Heyting und Algebra von Boolean mit diesen monoid Strukturen ausgestattet.
• Jede Halbgruppe S kann in einen monoid verwandelt werden, indem einfach sie an ein Element e nicht in S angrenzt und e*s = s = s*e für den ganzen s  S definiert. Diese Konvertierung jeder Halbgruppe zum monoid wird durch den freien functor zwischen der Kategorie von Halbgruppen und der Kategorie von monoids getan.
• So kann ein idempotent monoid (manchmal bekannt, wie erst finden) durch das Angrenzen an ein Identitätselement e zur linken Nullhalbgruppe über einen Satz S gebildet werden. Das Gegenteil monoid (manchmal genannt finden - letzt), wird von der richtigen Nullhalbgruppe über S gebildet.
• Grenzen Sie an eine Identität e nach links Nullhalbgruppe mit zwei Elementen {Leutnant an; gt}. Dann der resultierende idempotent monoid {Leutnant; e; gt} modelliert die lexikografische Ordnung einer Folge gegeben die Ordnungen seiner Elemente, mit e das Darstellen der Gleichheit.
• Die natürlichen Zahlen, N, bilden einen auswechselbaren monoid unter der Hinzufügung (Identitätselement-Null), oder Multiplikation (Identitätselement ein). Ein submonoid von N unter der Hinzufügung wird einen numerischen monoid genannt.
• Die positiven ganzen Zahlen, N-{0}, bilden einen auswechselbaren monoid unter der Multiplikation (Identitätselement ein).
• Die Elemente jedes Unital-Rings, mit der Hinzufügung oder Multiplikation als die Operation.
• Die ganzen Zahlen, rationalen Zahlen, reellen Zahlen oder komplexen Zahlen, mit der Hinzufügung oder Multiplikation als Operation.
• Der Satz des ganzen n durch n matrices über einen gegebenen Ring, mit der Matrixhinzufügung oder Matrixmultiplikation als die Operation.
• Der Satz aller begrenzten Schnuren über ein festes Alphabet Σ bildet einen monoid mit der Schnur-Verkettung als die Operation. Die leere Schnur dient als das Identitätselement. Dieser monoid wird Σ angezeigt und wird den freien monoid über Σ genannt.
• In Anbetracht jeder monoid M hat das Gegenteil monoid M dasselbe Transportunternehmen und Identitätselement als M setzen lassen, und seine Operation wird durch x * y = y * x definiert. Jeder auswechselbare monoid ist das Gegenteil monoid sich.
• In Anbetracht zwei Sätze M und N ausgestattet mit der monoid Struktur (oder, im Allgemeinen, jede begrenzte Zahl von monoids, M..., M), ihr kartesianisches Produkt M × N ist auch ein monoid (respectivelly, M ×... × M). Die assoziative Operation und das Identitätselement werden pairwise definiert.
• Befestigen Sie eine monoid M. Der Satz aller Funktionen von einem gegebenen Satz bis M ist auch ein monoid. Das Identitätselement ist eine unveränderliche Funktion, die jeden Wert zur Identität der M kartografisch darstellt; die assoziative Operation wird pointwise definiert.
• Befestigen Sie eine monoid M mit der Operation * und Identitätselement e und denken Sie, dass seine Macht P (M) gesetzt hat, aus allen Teilmengen der M bestehend. Eine binäre Operation wegen solcher Teilmengen kann durch S * T = {s * t definiert werden: s in S und t in T\. Das dreht P (M) in einen monoid mit dem Identitätselement {e}. Ebenso ist der Macht-Satz einer Gruppe G ein monoid unter dem Produkt von Gruppenteilmengen.
• Lassen Sie S ein Satz sein. Der Satz aller Funktionen S  S bildet einen monoid unter der Funktionszusammensetzung. Die Identität ist gerade die Identitätsfunktion. Es wird auch die volle Transformation monoid S genannt. Wenn S mit n Elementen begrenzt ist, ist der monoid von Funktionen auf S mit n Elementen begrenzt.

Wenn Sie

• das vorherige Beispiel verallgemeinern, lassen Sie C eine Kategorie und X ein Gegenstand in C sein. Der Satz aller Endomorphismen X, angezeigtes Ende (X), bildet einen monoid unter der Zusammensetzung von morphisms. Für mehr auf der Beziehung zwischen Kategorie-Theorie und monoids sieh unten.
• Der Satz von homeomorphism Klassen von Kompaktoberflächen mit der verbundenen Summe. Sein Einheitselement ist die Klasse des 2-Bereiche-Üblichen. Außerdem, wenn ein Anzeigen der Klasse des Rings und b die Klasse des projektiven Flugzeugs anzeigt, dann hat jedes Element c des monoid einen einzigartigen Ausdruck die Form c=na+mb, wo n die ganze Zahl  0 und m=0,1, oder 2 ist. Wir haben 3b=a+b.
• Lassen Sie, ein zyklischer monoid des Auftrags n zu sein, d. h. Dann für einige. Tatsächlich gibt jeder solcher k einen verschiedenen monoid des Auftrags n, und jeder zyklische monoid ist zu einem von diesen isomorph.

Außerdem kann f als eine Funktion auf den durch gegebenen Punkten betrachtet werden

:

0 & 1 & 2 & \dots & n-2 & n-1 \\

1 & 2 & 3 & \dots & n-1 & k\end {bmatrix} </Mathematik>

oder, gleichwertig

:

Die Multiplikation von Elementen darin wird dann durch die Funktionszusammensetzung gegeben.

Bemerken Sie auch das, wenn dann die Funktion f eine Versetzung von ist

und gibt die einzigartige zyklische Gruppe des Auftrags n.

Eigenschaften

In einem monoid kann man positive Mächte der ganzen Zahl eines Elements x definieren: x=x und x=x*...*x (n Zeiten) für n> 1. Die Regel von Mächten x=x * x ist offensichtlich.

Direkt aus der Definition kann man zeigen, dass das Identitätselement e einzigartig ist. Dann, für jeden x, kann man x=e setzen, und die Regel von Mächten ist noch mit nichtnegativen Hochzahlen wahr.

Es ist möglich, invertible Elemente zu definieren: Ein Element x wird invertible genannt, wenn dort ein Element y solch dass x*y = e und y*x = e besteht. Das Element y wird das Gegenteil von x genannt. Wenn y und z Gegenteile von x, dann durch associativity y = (zx) y = z (xy) = z sind. So sind Gegenteile, wenn sie bestehen, einzigartig.

Wenn y das Gegenteil von x ist, kann man negative Mächte von x definieren, indem man x=y und x=y*...*y (n Zeiten) für n> 1 untergeht. Und die Regel von Hochzahlen wird noch für den ganzen n, p vernünftige ganze Zahlen nachgeprüft. Das ist, warum das Gegenteil von x gewöhnlich x geschrieben wird. Der Satz aller invertible Elemente in einer monoid M, zusammen mit der Operation *, bildet eine Gruppe. In diesem Sinn enthält jeder monoid eine Gruppe (wenn nur die triviale, die aus der Identität allein besteht).

Jedoch sitzt nicht jeder monoid innerhalb einer Gruppe. Zum Beispiel ist es vollkommen möglich, einen monoid zu haben, in dem zwei Elemente a und b solch bestehen, dass a*b = ein Halten, wenn auch b nicht das Identitätselement ist. Solch ein monoid kann in einer Gruppe nicht eingebettet werden, weil in der Gruppe wir beide Seiten mit dem Gegenteil von a multiplizieren konnten und das b = e bekommen würden, der nicht wahr ist. Ein monoid (M, *) hat das Annullierungseigentum (oder ist cancellative), wenn für den ganzen a, b und c in der M, a*b = a*c immer b = c einbezieht und b*a = c*a immer b = c einbezieht. Ein auswechselbarer monoid mit dem Annullierungseigentum kann immer in einer Gruppe über den Aufbau von Grothendieck eingebettet werden. Es ist, wie die zusätzliche Gruppe der ganzen Zahlen (eine Gruppe mit der Operation +) vom Zusatz monoid natürlicher Zahlen (ein auswechselbarer monoid mit der Operation + und Annullierungseigentum) gebaut wird. Jedoch braucht ein nichtauswechselbarer cancellative monoid nicht embeddable in einer Gruppe zu sein.

Wenn ein monoid das Annullierungseigentum hat und begrenzt ist, dann ist es tatsächlich eine Gruppe. Beweis: Befestigen Sie ein Element x im monoid. Da der monoid, x = x für einen m> n> 0 begrenzt ist. Aber dann durch die Annullierung haben wir das x = e, wo e die Identität ist. Deshalb x * x = e, so hat x ein Gegenteil.

Das Recht - und nach-links-cancellative Elemente eines monoid jeder bildet der Reihe nach einen submonoid (d. h. schließt offensichtlich die Identität ein und wird nicht also offensichtlich unter der Operation geschlossen). Das bedeutet, dass die cancellative Elemente jedes auswechselbaren monoid zu einer Gruppe erweitert werden können.

Ein Gegenteil monoid ist ein monoid, wo für jeden in der M, dort ein einzigartiger in der solcher M dass a=a*a*a und a=a*a*a besteht. Wenn ein Gegenteil monoid cancellative ist, dann ist es eine Gruppe.

Gesetze und Maschinenbediener monoids

Lassen Sie M ein monoid mit der binären Operation sein, die dadurch angezeigt ist "·" und das Identitätselement durch e angezeigt. Dann ist eine (linke) M Tat' (oder verlassene Tat über M) ein Satz X zusammen mit einer Operation : M &times; X  X, der mit der monoid Struktur wie folgt vereinbar ist:

• für den ganzen x in X: e  x = x;
• für den ganzen a, b in der M und x in X: ein  (b  x) = (a · b)  x.

Das ist die Entsprechung in der monoid Theorie einer (linken) Gruppenhandlung. Richtige M Taten wird auf eine ähnliche Weise definiert. Ein monoid mit einer Tat ist auch bekannt als ein Maschinenbediener monoid. Wichtige Beispiele schließen Übergang-Systeme von Halbautomaten ein. Eine Transformationshalbgruppe kann in einen Maschinenbediener monoid gemacht werden, indem sie an die Identitätstransformation angrenzt.

Homomorphismus von Monoid

Ein Homomorphismus zwischen zwei monoids (M, *) und (M&prime;,•) ist eine Funktion f: M  M&prime; solch dass

• f (x*y) = f (x) · f (y) für den ganzen x, y in der M
• f (e) =

e&prime;

wo e und e&prime; sind die Identität auf der M und M&prime; beziehungsweise. Homomorphismus von Monoid wird manchmal einfach monoid morphisms genannt.

Nicht jeder Halbgruppenhomomorphismus ist ein monoid Homomorphismus, da er die Identität nicht bewahren kann. Stellen Sie dem mit dem Fall des Gruppenhomomorphismus gegenüber: Die Axiome der Gruppentheorie stellen sicher, dass jeder Halbgruppenhomomorphismus zwischen Gruppen die Identität bewahrt. Für monoids ist das nicht immer wahr, und es ist notwendig, es als eine getrennte Voraussetzung festzusetzen.

Ein bijektiver monoid Homomorphismus wird einen monoid Isomorphismus genannt. Wie man sagt, sind zwei monoids isomorph, wenn es einen Isomorphismus zwischen ihnen gibt.

Präsentation von Equational

Monoids kann eine Präsentation viel ebenso gegeben werden, dass Gruppen mittels einer Gruppenpräsentation angegeben werden können. Man tut das, indem man eine Reihe von Generatoren Σ und eine Reihe von Beziehungen auf dem freien monoid Σ angibt. Man tut das, indem man (begrenzte) binäre Beziehungen auf Σ zu monoid Kongruenzen erweitert, und dann den Quotienten monoid als oben baut.

In Anbetracht einer binären Beziehung R  Σ × Σ definiert man seinen symmetrischen Verschluss als R  R. Das kann zu einer symmetrischen Beziehung E  Σ × Σ durch das Definieren x ~ y wenn und nur wenn x = sut und y = svt für einige Schnuren u, v, s, t  Σ mit (u, v)  R  R erweitert werden. Schließlich nimmt man den reflexiven und transitiven Verschluss von E, der dann eine monoid Kongruenz ist.

In der typischen Situation wird die Beziehung R einfach als eine Reihe von Gleichungen, so dass gegeben. So, zum Beispiel,

:

ist die equational Präsentation für den bicyclic monoid und

der:

ist der plactic monoid vom Grad 2 (es hat unendliche Ordnung). Elemente dieses plactic monoid können bezüglich ganzer Zahlen i, j, k geschrieben werden, weil die Beziehungen zeigen, dass ba sowohl mit a als auch mit b pendelt.

Beziehung zur Kategorie-Theorie

Monoids kann als eine spezielle Klasse von Kategorien angesehen werden. Tatsächlich sind die einer monoid Operation erforderlichen Axiome genau diejenigen, die der morphism Zusammensetzung, wenn eingeschränkt, auf den Satz des ganzen morphisms erforderlich sind, dessen Quelle und Ziel ein gegebener Gegenstand sind. Das, ist

:A monoid, ist im Wesentlichen, dasselbe Ding wie eine Kategorie mit einem einzelnen Gegenstand.

Genauer, in Anbetracht eines monoid (M, *), kann man eine kleine Kategorie mit nur einem Gegenstand bauen, und dessen morphisms die Elemente der M sind. Die Zusammensetzung von morphisms wird durch die monoid Operation * gegeben.

Ebenfalls, monoid Homomorphismus sind gerade functors zwischen einzelnen Gegenstand-Kategorien. So gibt dieser Aufbau eine Gleichwertigkeit zwischen der Kategorie (des kleinen) monoids Montags und einer vollen Unterkategorie der Kategorie von (kleinen) Kategorien Cat. Ähnlich ist die Kategorie von Gruppen zu einer anderen vollen Unterkategorie von Cat gleichwertig.

In diesem Sinn kann von Kategorie-Theorie als eine Erweiterung des Konzepts eines monoid gedacht werden. Viele Definitionen und Lehrsätze über monoids können zu kleinen Kategorien mit mehr als einem Gegenstand verallgemeinert werden. Zum Beispiel ist ein Quotient einer Kategorie mit einem Gegenstand gerade ein Quotient monoid.

Monoids, gerade wie andere algebraische Strukturen, bilden auch ihre eigene Kategorie, Montag, dessen Gegenstände monoids sind, und dessen morphisms monoid Homomorphismus sind.

Es gibt auch einen Begriff des Monoid-Gegenstands, der eine abstrakte Definition dessen ist, was ein monoid in einer Kategorie ist. Ein Monoid-Gegenstand im Satz ist gerade ein monoid.

Monoids in der Informatik

In der Informatik können viele abstrakte Datentypen mit einer monoid Struktur ausgestattet sein. In einem allgemeinen Muster wird eine Folge von Elementen eines monoid "gefaltet" oder "angesammelt", um einen Endwert zu erzeugen. Zum Beispiel müssen viele wiederholende Algorithmen eine Art "Laufen ganz" bei jeder Wiederholung aktualisieren; dieses Muster kann durch eine monoid Operation elegant ausgedrückt werden. Wechselweise stellt der associativity von monoid Operationen sicher, dass die Operation parallelized durch die Beschäftigung einer Präfix-Summe oder ähnlichen Algorithmus sein kann, um vielfache Kerne oder Verarbeiter effizient zu verwerten.

In Anbetracht einer Folge von Werten des Typs M mit dem Identitätselement und der assoziativen Operation wird die Falte-Operation wie folgt definiert:

:

Außerdem kann jede Datenstruktur auf eine ähnliche Weise in Anbetracht einer Anordnung seiner Elemente 'gefaltet' werden. Zum Beispiel könnte sich das Ergebnis, einen binären Baum "zu falten", abhängig von der Vorordnung gegen das Postordnungsbaumtraversal unterscheiden.

Siehe auch

• Sternhöhe-Problem
• Algebra von Kleene
• Monad (funktionelle Programmierung)
• John M. Howie, Grundlagen der Halbgruppentheorie (1995), Clarendon Press, internationale Standardbuchnummer von Oxford 0-19-851194-9
• M. Kilp, U. Knauer, A.V. Mikhalev, Monoids, Gesetze und Kategorien mit Anwendungen auf Kranz-Produkte und Graphen, De Gruyter Expositions in der Mathematik vol. 29, Walter de Gruyter, 2000, internationale Standardbuchnummer 3110152487.