Monoid
19652
215943259
2008-05-30T11:26:18Z
62.65.193.5
/* Properties */
{{For|the alien creatures in the Doctor Who adventure|The Ark (Doctor Who)}}
In [[abstract algebra]], a branch of [[mathematics]], a '''monoid''' is an [[algebraic structure]] with a single, [[associative]] [[binary operation]] and an [[identity element]]. Monoids occur in a number of branches of mathematics. In [[geometry]], a monoid captures the idea of [[function composition]]; indeed, this notion is abstracted in [[category theory]], where the monoid is a [[category (mathematics)|category]] with one [[object (category theory)|object]]. Monoids are also commonly used to lay a firm algebraic foundation for [[computer science]]; in this case, the [[transition monoid]] and [[syntactic monoid]] are used in describing a [[finite state machine]], whereas [[trace monoid]]s and [[history monoid]]s provide a foundation for [[process calculi]] and [[concurrent computing]]. Some of the more important results in the study of monoids are the [[Krohn-Rhodes theorem]] and the [[star height problem]]. The history of monoids, as well as a discussion of additional general properties, are found in the article on [[semigroup]]s.
== Definition ==
A '''monoid''' is a [[set]] ''M'' with [[binary operation]] * : ''M'' × ''M'' → ''M'', obeying the following axioms:
*[[Associativity]]: for all ''a'', ''b'', ''c'' in M, (''a''*''b'')*''c'' = ''a''*(''b''*''c'')
*[[Identity element]]: there exists an element ''e'' in M, such that for all ''a'' in M, ''a''*''e'' = ''e''*''a'' = ''a''.
One often sees the additional axiom
*[[Closure (binary operation)|Closure]]: for all ''a'', ''b'' in M, ''a''*''b'' is in M
though, strictly speaking, this axiom is implied by the notion of a [[binary operation]].
Alternatively, a monoid is a [[semigroup]] with an [[identity element]].
A monoid satisfies all the axioms of a [[group (mathematics)|group]] with the exception of having [[inverse element|inverses]]. A monoid with inverses is a group.
By [[abuse of notation]] we sometimes refer to ''M'' itself as a monoid, implying the presence of identity and operation. A monoid can be denoted by the tuple (''M'', *) if the operation needs to be made explicit.
===Generators and submonoids===
A '''submonoid''' of a monoid ''M'' is a subset ''N'' of ''M'' containing the unit element, and such that, if ''x'',''y''∈''N'' then ''x''*''y''∈''N''. It is then clear that ''N'' is itself a monoid, under the binary operation induced by that of ''M''. Equivalently, a submonoid is a subset ''N'' such that ''N''=''N''<sup>*</sup>, where the superscript * is the [[Kleene star]]. For any subset ''N'' of ''M'', the monoid ''N''<sup>*</sup> is the smallest monoid that contains ''N''.
A subset ''N'' is said to be a '''generator''' of ''M'' if and only if ''M''=''N''<sup>*</sup>. If ''N'' is finite, then ''M'' is said to be '''finitely generated'''.
===Commutative monoid===
A monoid whose operation is [[commutative]] is called a '''commutative monoid''' (or, less commonly, an '''abelian monoid'''). Commutative monoids are often written additively. Any commutative monoid is endowed with its '''algebraic''' [[Preorder|preordering]] ≤, defined by ''x ≤ y'' if and only if there exists ''z'' such that ''x + z = y''. An '''order-unit''' of a commutative monoid ''M'' is an element ''u'' of ''M'' such that for any element ''x'' of ''M'', there exists a positive integer ''n'' such that ''x ≤ nu''. This is often used in case ''M'' is the [[Ordered group|positive cone]] of a [[Ordered group|partially ordered abelian group]] ''G'', in which case we say that ''u'' is an order-unit of ''G''. There is an algebraic construction that will take any commutative monoid, and turn it into a full-fledged [[abelian group]]; this construction is known as the [[Grothendieck group]].
===Partially commutative monoid===
A monoid for which the operation is commutative for some, but not all elements is a [[trace monoid]]; trace monoids commonly occur in the theory of [[concurrent computation]].
===Acts, transition systems===
An [[operator monoid]] is a monoid ''M'' which acts upon a set ''X''.
That is, there is an operation • : ''M'' × ''X'' → ''X'' which is compatible with the monoid operation.
* For all ''x'' in ''X'': ''e • x = x''.
* For all ''a'', ''b'' in ''M'' and ''x'' in ''X'': ''a • (b • x) = (a * b) • x''.
Operator monoids are also known as '''acts''' (since they resemble a [[group action]]), [[transition system]]s, [[semiautomata]] or [[transformation semigroup]]s.
== Examples ==
* Every [[singleton set]] {''x''} gives rise to a one-element (trivial) monoid. For fixed ''x'' this monoid is unique, since the monoid axioms require that ''x''*''x'' = ''x'' in this case.
* Every [[group (mathematics)|group]] is a monoid and every [[abelian group]] a commutative monoid.
* Every bounded [[semilattice]] is an [[idempotent]] commutative monoid.
* Any [[semigroup]] ''S'' may be turned into a monoid simply by adjoining an element ''e'' not in ''S'' and defining ''e''*''e'' = ''e'' and ''e''*''s'' = ''s'' = ''s''*''e'' for all ''s'' ∈ ''S''.
* The [[natural number]]s, '''N''', form a commutative monoid under addition (identity element [[0 (number)|zero]]), or multiplication (identity element [[1 (number)|one]]). A submonoid of '''N''' under addition is called a [[numerical monoid]].
* The elements of any [[unital]] [[ring (algebra)|ring]], with addition or multiplication as the operation.
** The [[integer]]s, [[rational number]]s, [[real number]]s or [[complex number]]s, with addition or multiplication as operation.
** The set of all ''n'' by ''n'' [[matrix_(mathematics)|matrices]] over a given ring, with [[matrix addition]] or [[matrix multiplication]] as the operation.
* The set of all finite [[string (computer science)|strings]] over some fixed alphabet Σ forms a monoid with [[string concatenation]] as the operation. The [[empty string]] serves as the identity element. This monoid is denoted Σ<sup>*</sup> and is called the '''[[free monoid]]''' over Σ.
* Fix a monoid ''M'', and consider its [[power set]] ''P''(''M'') consisting of all [[subset]]s of ''M''. A binary operation for such subsets can be defined by ''S'' * ''T'' = {''s'' * ''t'' : ''s'' in ''S'' and ''t'' in ''T''}. This turns ''P''(''M'') into a monoid with identity element {''e''}. In the same way the power set of a group ''G'' is a monoid under the [[product of group subsets]].
* Let ''S'' be a [[set]]. The set of all functions ''S'' → ''S'' forms a monoid under [[function composition]]. The identity is just the [[identity function]]. If ''S'' is finite with ''n'' elements, the monoid of functions on ''S'' is finite with ''n''<sup>''n''</sup> elements.
* Generalizing the previous example, let ''C'' be a [[category (mathematics)|category]] and ''X'' an object in ''C''. The set of all [[endomorphism]]s of ''X'', denoted End<sub>''C''</sub>(''X''), forms a monoid under composition of [[morphism]]s. For more on the relationship between category theory and monoids see below.
* The set of [[homeomorphism]] [[Class (set theory)|classes]] of [[compact surface]]s with the [[connected sum]]. Its unit element is the class of the ordinary 2-sphere. Furthermore, if ''a'' denotes the class of the torus, and ''b'' denotes the class of the projective plane, then every element ''c'' of the monoid has a unique expression the form ''c=na+mb'' where ''n'' is the integer ''≥ 0'' and ''m=0,1,'' or ''2''. We have ''3b=a+b''.
* Let <math><f></math> be a cyclic monoid of order ''n'', that is, <math><f> = \{f^0,f^1,..,f^{n-1}\}</math>. Then <math>f^n = f^k</math> for some <math>0 \le k \le n</math>. In fact, each such ''k'' gives a distinct monoid of order ''n'', and every cyclic monoid is isomorphic to one of these.
Moreover, ''f'' can be considered as a function on the points <math>{0,1,2,..,n-1}</math> given by
: <math>\begin{bmatrix}
0 & 1 & 2 & ... & n-2 & n-1 \\
1 & 2 & 3 & ... & n-1 & k\end{bmatrix}</math>
or, equivalently
:<math>f(i) := \begin{cases} i+1, & \mbox{if } 0 \le i < n-1 \\ k, & \mbox{if } i = n-1. \end{cases} </math>
Multiplication of elements in <math><f></math> is then given by function composition.
Note also that when <math>k = 0</math> then the function ''f'' is a permutation of <math>\{0,1,2,..,n-1\}</math>
and gives the unique [[cyclic group]] of order ''n''.
== Properties ==
In a monoid, one can define positive integer powers of an element ''x'' : ''x''<sup>1</sup>=''x'', and ''x''<sup>n</sup>=''x''*...*''x'' (''n'' times) for ''n''>1 . The rule of powers ''x''<sup>n+p</sup>=''x''<sup>n</sup> * ''x''<sup>p</sup> is obvious.
Directly from the definition, one can show that the identity element ''e'' is unique. Then, for any ''x'' , one can set ''x''<sup>0</sup>=''e'' and the rule of powers is still true with nonnegative exponents.
It is possible to define ''[[inverse element|invertible elements]]'': an element ''x'' is called invertible if there exists an element ''y'' such ''x''*''y'' = ''e'' and ''y''*''x'' = ''e''. The element ''y'' is called the inverse of ''x'' . Associativity guarantees that inverses, if they exist, are unique.
If ''y'' is the inverse of ''x'' , one can define negative powers of ''x'' by setting ''x''<sup>−1</sup>=''y'' and ''x''<sup>−n</sup>=''y''*...*''y'' (''n'' times) for ''n''>1 . And the rule of exponents is still verified for all ''n'',''p'' rational integers. This is why the inverse of ''x'' is usually written ''x''<sup>−1</sup>. The set of all invertible elements in a monoid ''M'', together with the operation *, forms a [[group (mathematics)|group]]. In that sense, every monoid contains a group (if only the trivial one consisting of the identity alone).
However, not every monoid sits inside a group. For instance, it is perfectly possible to have a monoid in which two elements ''a'' and ''b'' exist such that
''a''*''b'' = ''a'' holds even though ''b'' is not the identity element. Such a monoid cannot be embedded in a group,
because in the group we could multiply both sides with the inverse of ''a'' and would get that ''b'' = ''e'', which isn't true. A monoid (M,*) has the ''[[cancellation property]]'' (or is ''[[cancellative]]'') if for all ''a'', ''b'' and ''c'' in ''M'', ''a''*''b'' = ''a''*''c'' always implies ''b'' = ''c'' and ''b''*''a'' = ''c''*''a'' always implies ''b'' = ''c''. A commutative monoid with the cancellation property can always be embedded in a group. That's how the [[additive group]] of the integers (a group with operation +) is constructed from the additive monoid of natural numbers (a commutative monoid with operation + and cancellation property). However, a non-commutative cancellative monoid need not be embeddable in a group.
If a monoid has the cancellation property and is ''finite'', then it is in fact a group.
The right- and left-cancellative elements of a monoid each in turn form a submonoid (i.e. obviously include the identity and not so obviously are closed under the operation). This means that the cancellative elements of any commutative monoid can be extended to a group.
An '''inverse monoid''', is a monoid where for every ''a'' in ''M'', there exists a unique ''a''<sup>-1</sup> in ''M'' such that ''a''=''a''*''a''<sup>-1</sup>*''a'' and ''a''<sup>-1</sup>=''a''<sup>-1</sup>*''a''*''a''<sup>-1</sup>. If an inverse monoid is cancellative, then it is a group.
== Monoid homomorphisms ==
A [[homomorphism]] between two monoids (''M'',*) and (''M''′,•) is a function ''f'' : ''M'' → ''M''′ such that
* ''f''(''x''*''y'') = ''f''(''x'')•''f''(''y'') for all ''x'', ''y'' in ''M''
* ''f''(''e'') = ''e''′
where ''e'' and ''e''′ are the identities on ''M'' and ''M''′ respectively. Monoid homomorphisms are sometimes simply called '''monoid morphisms'''.
Not every [[Magma_(algebra)|magma (groupoid)]] homomorphism is a monoid homomorphism since it may not preserve the identity. Contrast this with the case of [[group homomorphism]]s: the axioms of [[group theory]] ensure that every [[Magma_(algebra)|magma (groupoid)]] homomorphism between groups preserves the identity. For monoids this isn't always true and it is necessary to state it as a separate requirement.
A [[bijective]] monoid homomorphism is called a monoid [[isomorphism]]. Two monoids are said to be isomorphic if there is an isomorphism between them.
== Monoid congruence and the quotient monoid==
A '''monoid congruence''' is an [[equivalence relation]] that is compatible with the monoid product. That is, it is a subset
:<math>\sim\;\subseteq M\times M</math>
such that it is reflexive, symmetric and transitive (just as every equivalence relation must be), and also has the property that if <math>x\sim y\,</math> and <math>u\sim v\,</math> for every <math>x,y,u</math> and <math>v</math> in ''M'', then one has that <math>x*u\sim y*v\,</math>.
A monoid congruence induces [[congruence class]]es
:<math>[m] = \{x\in M\vert\; x\sim m\}</math>
and the monoid operation * induces a binary operation <math>\circ</math> on the congruence classes:
:<math>[u]\circ [v] = [u*v]</math>
which is a monoid homomorphism. It is also clearly associative, and so the set of all congruence classes are a monoid as well. This monoid is called the '''quotient monoid''', and may be written as
:<math>M/\sim\; = \{[m]\,\vert\; m\in M\}.</math>
Several additional notations are common. Give a subset <math>L\subseteq M</math>, one writes
:<math>[L] = \{[m] \,\vert\; m\in L\}</math>
for the set of congruence classes induced by ''L''. In this notation, clearly <math>[M]=M/\sim</math>. In general, however, <math>[L]</math> is not a monoid. Going in the opposite direction, if <math>X\subseteq [M]</math> is a subset of the quotient monoid, one writes
:<math>\bigcup X = \{m \,\vert\; [m]\in X\}.</math>
This is, of course, just the [[set-theoretic union]] of the members of ''X''. In general, <math>\bigcup X</math> is not a monoid.
Clearly, one has <math>L\subseteq \bigcup[L]</math> and <math>\left[\bigcup X\right]=X</math>.
==Equational presentation==
Monoids may be given a '''presentation''', much in the same way that groups can be specified by means of a [[group presentation]]. One does this by specifying a set of generators <math>\Sigma</math>, and a set of relations on the [[free monoid]] <math>\Sigma^*</math>. One does this by extending (finite) [[binary relation]]s on <math>\Sigma^*</math> to monoid congruences, and then constructing the quotient monoid, as above.
Given a binary relation <math>R\subseteq \Sigma^*\times\Sigma^*</math>, one defines its symmetric closure as <math>R\cup R^{-1}</math>. This can be extended to a symmetric relation <math>E\subseteq \Sigma^*\times\Sigma^*</math> by defining <math>x\sim_E y\,</math> if and only if <math>x=sut</math> and <math>y=svt</math> for some strings <math>s,t\in \Sigma^*</math> and <math>(u,v)\in R\cup R^{-1}</math>. Finally, one takes the reflexive and transitive closure of <math>E</math>, which is then a monoid congruence.
In the typical situation, the relation <math>R</math> is simply given as a set of equations, so that <math>R=\{u_1=v_1,\cdots,u_n=v_n\}</math>. Thus, for example,
:<math>\langle p,q\,\vert\; pq=1\rangle</math>
is the equational presentation for the [[bicyclic monoid]], and
:<math>\langle a,b \,\vert\; aba=baa, bba=bab\rangle</math>
is the [[plactic monoid]] of degree 2 (it has infinite order). Elements of this plactic monoid may be written as <math>a^ib^j(ba)^k</math> for integers <math>i,j,k</math>, as the relations show that <math>ba</math> commutes with both <math>a</math> and <math>b</math>.
== Relation to category theory ==
{{Template:Group-like structures}}
Monoids can be viewed as a special class of [[category theory|categories]]. Indeed, the axioms required of a monoid operation are exactly those required of [[morphism]] composition when restricted to the set of all morphisms whose source and target is a given object. That is,
:''A monoid is, essentially, the same thing as a category with a single object.''
More precisely, given a monoid (''M'',*), one can construct a small category with only one object and whose morphisms are the elements of ''M''. The composition of morphisms is given by the monoid operation *.
Likewise, monoid homomorphisms are just [[functor]]s between single object categories. In this sense, category theory can be thought of as an extension of the concept of a monoid. Many definitions and theorems about monoids can be generalised to small categories with more than one object.
Monoids, just like other algebraic structures, also form their own category, '''Mon''', whose objects are monoids and whose morphisms are monoid homomorphisms.
There is also a notion of [[monoid (category theory)|monoid object]] which is an abstract definition of what is a monoid in a category.
== See also ==
* [[Star height problem]]
== References ==
* John M. Howie, ''Fundamentals of Semigroup Theory'' (1995), Clarendon Press, Oxford ISBN 0-19-851194-9
* {{MathWorld | urlname=Monoid | title=Monoid}}
* {{PlanetMath| urlname=Monoid | title=Monoid | id=389}}
[[Category:Abstract algebra]]
[[Category:Category theory]]
[[Category:Semigroup theory]]
[[Category:Category-theoretic categories]]
[[ca:Monoide]]
[[cs:Monoid]]
[[de:Monoid]]
[[et:Monoid]]
[[es:Monoide]]
[[fr:Monoïde]]
[[hr:Monoid]]
[[it:Monoide]]
[[he:מונואיד (מבנה אלגברי)]]
[[hu:Monoid]]
[[nl:Monoïde]]
[[ja:モノイド]]
[[oc:Monoïde]]
[[pl:Monoid]]
[[pt:Monóide]]
[[ro:Monoid]]
[[ru:Моноид]]
[[sl:Monoid]]
[[sr:Моноид]]
[[fi:Monoidi]]
[[sv:Monoid (matematik)]]
[[tr:Birlik]]
[[uk:Моноїд]]
[[zh:幺半群]]