View source for Monoid

{{short description|Algebraic structure with an associative operation and an identity element}}
{{for|monoid objects in category theory|Monoid (category theory)}}
{{Distinguish|Monad (disambiguation){{!}}Monad}}
{{Algebraic structures |group}}
[[File:Magma to group3.svg|thumb|right|300px|Algebraic structures between [[Magma (algebra)|magmas]] and [[Group (mathematics)|groups]]. Monoids are [[semigroup]]s with identity.]]
In [[abstract algebra]], a branch of [[mathematics]], a '''monoid''' is an [[algebraic structure]] with a single [[associative]] [[binary operation]] and an [[identity element]].

Monoids are [[semigroup]]s with identity. They occur in several branches of mathematics. 

For example, the functions from a set into itself form a monoid with respect to function composition. More generally, in [[category theory]], the morphisms of an [[object (category theory)|object]] to itself form a monoid, and, conversely, a monoid may be viewed as a category with a single object. 

In [[computer science]] and [[computer programming]], the set of [[string (computer science)|strings]] built from a given set of [[Character (computing)|characters]] is a [[free monoid]]. [[Transition monoid]]s and [[syntactic monoid]]s are used in describing [[finite-state machine]]s. [[Trace monoid]]s and [[history monoid]]s provide a foundation for [[process calculi]] and [[concurrent computing]].

In [[theoretical computer science]], the study of monoids is fundamental for [[automata theory]] ([[Krohn–Rhodes theory]]), and [[formal language theory]] ([[star height problem]]).

See [[Semigroup]] for the history of the subject, and some other general properties of monoids.

== Definition ==

Suppose that ''S'' is a [[set (mathematics)|set]] and • is some [[binary operation]] {{math|1=''S'' × ''S'' → ''S''}}, then ''S'' with • is a '''monoid''' if it satisfies the following two axioms:

; Associativity: For all ''a'', ''b'' and ''c'' in ''S'', the equation {{math|1=(''a'' • ''b'') • ''c'' = ''a'' • (''b'' • ''c'')}} holds.
; Identity element: There exists an element ''e'' in ''S'' such that for every element ''a'' in ''S'', the equations {{math|1=''e'' • ''a'' = ''a'' • ''e'' = ''a''}} hold.

In other words, a monoid is a [[semigroup]] with an [[identity element]]. It can also be thought of as a [[magma (algebra)|magma]] with associativity and identity. The identity element of a monoid is unique.<ref>If both ''e''<sub>1</sub> and ''e''<sub>2</sub> satisfy the above equations, then ''e''<sub>1</sub> = ''e''<sub>1</sub> • ''e''<sub>2</sub> = ''e''<sub>2</sub>.</ref>  For this reason the identity is regarded as a [[Constant (mathematics)|constant]], i. e. 0-ary (or nullary) operation. The monoid therefore is characterized by specification of the [[Tuple|triple]] (''S'', • , ''e'').

Depending on the context, the symbol for the binary operation may be omitted, so that the operation is denoted by juxtaposition; for example, the monoid axioms may be written <math>(ab)c = a(bc)</math> and <math>ea=ae=a</math>. This notation does not imply that it is numbers being multiplied.

A monoid in which each element has an [[inverse element|inverse]] is a [[group (mathematics)|group]].

== Monoid structures ==

===Submonoids===
A '''submonoid''' of a monoid {{math|(''M'', •)}} is a [[subset]] ''N'' of ''M'' that is closed under the monoid operation and contains the identity element ''e'' of ''M''.{{sfn|Jacobson|2009}}<ref>Some authors omit the requirement that a submonoid must contain the identity element from its definition, requiring only that it have ''an'' identity element, which can be distinct from that of ''M''.</ref> Symbolically, ''N'' is a submonoid of ''M'' if {{math|''N'' ⊆ ''M''}}, {{math|''x'' • ''y'' ∈ ''N''}} whenever {{math|''x'', ''y'' ∈ ''N''}}, and {{math|''e'' ∈ ''N''}}. ''N'' is thus a monoid under the binary operation inherited from ''M''.

===Generators===
A subset ''S'' of ''M'' is said to be a '''generator''' of ''M'' if ''M'' is the smallest set containing ''S'' that is [[closure (mathematics)|closed]] under the monoid operation, or equivalently ''M'' is the result of applying the [[finitary closure operator]] to ''S''. If there is a generator of ''M'' that has finite cardinality, then ''M'' is said to be '''finitely generated'''. Not every set ''S'' will generate a monoid, as the generated structure may lack an identity element.

===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]]ing ≤, defined by {{math|''x'' ≤ ''y''}} if there exists ''z'' such that {{math|1=''x'' + ''z'' = ''y''}}.<ref>{{cite book|first1=Michel |last1=Gondran |first2=Michel |last2=Minoux |title=Graphs, Dioids and Semirings: New Models and Algorithms |year=2008 |location=Dordrecht |publisher=[[Springer-Verlag]] |isbn=978-0-387-75450-5 |zbl=1201.16038 |series=Operations Research/Computer Science Interfaces Series |volume=41 | page=13}}</ref> 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 {{math|''x'' ≤ ''nu''}}. This is often used in case ''M'' is the [[Ordered group|positive cone]] of a [[Partially ordered set|partially ordered]] [[abelian group]] ''G'', in which case we say that ''u'' is an order-unit of ''G''.

===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]].

== Examples ==
* Out of the 16 possible [[truth table#Truth table for all binary logical operators|binary Boolean operator]]s, each of the four that has a two sided identity is also commutative and associative and thus makes the set {False, True} a commutative monoid. Under the standard definitions, [[Logical conjunction|AND]] and [[Logical biconditional|XNOR]] have the identity True while [[Exclusive disjunction|XOR]] and [[Logical disjunction|OR]] have the identity False. The monoids from AND and OR are also [[idempotent]] while those from XOR and XNOR are not.
* 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 {{math|'''N'''}} under addition is called a [[numerical monoid]].
* The [[positive integer]]s, {{math|'''N''' ∖ {{mset|0}}}}, form a commutative monoid under multiplication (identity element one).
* Given a set {{mvar|A}}, all subsets of {{mvar|A}} form a commutative monoid under intersection operation (identity element is {{mvar|A}} itself).
* Given a set {{mvar|A}}, all subsets of {{mvar|A}} form a commutative monoid under union operation (identity element is the empty set).
* Generalizing the previous example, every bounded [[semilattice]] is an [[idempotent]] commutative monoid.
** In particular, any bounded [[lattice (order)|lattice]] can be endowed with both a [[Join and meet|meet]]- and a [[Join and meet|join]]- monoid structure. The identity elements are the lattice's top and its bottom, respectively. Being lattices, [[Heyting algebra]]s and [[Boolean algebra (structure)|Boolean algebra]]s are endowed with these monoid structures.
* Every [[singleton set]] {{math|{{mset|''x''}}}} closed under a binary operation • forms the trivial (one-element) monoid, which is also the [[trivial group]].
* Every [[group (mathematics)|group]] is a monoid and every [[abelian group]] a commutative monoid.
* Any [[semigroup]] {{math|''S''}} may be turned into a monoid simply by adjoining an element {{math|''e''}} not in {{math|''S''}} and defining {{math|1=''e'' • ''s'' = ''s'' = ''s'' • ''e''}} for all {{math|''s'' ∈ ''S''}}. This conversion of any semigroup to the monoid is done by the [[free functor]] between the category of semigroups and the category of monoids.<ref>{{citation|title=The q-theory of Finite Semigroups: A New Approach|volume=71|series=Springer Monographs in Mathematics|first1=John|last1=Rhodes|first2=Benjamin|last2=Steinberg|publisher=Springer|year=2009|isbn=9780387097817|page=22|url=https://books.google.com/books?id=8L0QIEj0PI4C&pg=PA22}}.</ref>
** Thus, an idempotent monoid (sometimes known as ''find-first'') may be formed by adjoining an identity element {{math|''e''}} to the [[left zero semigroup]] over a set {{math|''S''}}. The opposite monoid (sometimes called ''find-last'') is formed from the [[right zero semigroup]] over {{math|''S''}}.
*** Adjoin an identity {{math|''e''}} to the left-zero semigroup with two elements {{math|{{mset|lt, gt}}}}. Then the resulting idempotent monoid {{math|{{mset|lt, ''e'', gt}}}} models the [[lexicographical order]] of a sequence given the orders of its elements, with ''e'' representing equality.
* The elements of any [[unital algebra|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.{{sfn|Jacobson|2009|p=29, examples 1, 2, 4 & 5}}
** The set of all {{math|''n''}} by {{math|''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 {{math|Σ}} forms a monoid with [[string concatenation]] as the operation. The [[empty string]] serves as the identity element. This monoid is denoted {{math|Σ<sup>∗</sup>}} and is called the '''[[free monoid]]''' over {{math|Σ}}.
* Given any monoid {{math|''M''}}, the ''opposite monoid'' {{math|''M''<sup>op</sup>}} has the same carrier set and identity element as {{math|''M''}}, and its operation is defined by {{math|1=''x'' •<sup>op</sup> ''y'' = ''y'' • ''x''}}. Any [[commutative monoid]] is the opposite monoid of itself.
* Given two sets {{math|''M''}} and {{math|''N''}} endowed with monoid structure (or, in general, any finite number of monoids, {{math|''M''<sub>1</sub>, ..., ''M<sub>k</sub>'')}}, their [[cartesian product]] {{math|''M'' × ''N''}} is also a monoid (respectively, {{math|''M<sub>1</sub>'' × ... × ''M<sub>k</sub>''}}). The associative operation and the identity element are defined pairwise.{{sfn|Jacobson|2009|p=35}}
* Fix a monoid {{math|''M''}}. The set of all functions from a given set to {{math|''M''}} is also a monoid. The identity element is a [[constant function]] mapping any value to the identity of {{math|''M''}}; the associative operation is defined [[pointwise]].
* Fix a monoid {{math|''M''}} with the operation {{math|•}} and identity element {{math|''e''}}, and consider its [[power set]] {{math|''P''(''M'')}} consisting of all [[subset]]s of {{math|''M''}}. A binary operation for such subsets can be defined by {{math|1=''S'' • ''T'' = {{mset| ''s'' • ''t'' : ''s'' ∈ ''S'', ''t'' ∈ ''T'' }}}}. This turns {{math|''P''(''M'')}} into a monoid with identity element {{math|{{mset|''e''}}}}. In the same way the power set of a group {{math|''G''}} is a monoid under the [[product of group subsets]].
* Let {{math|''S''}} be a set. The set of all functions {{math|''S'' → ''S''}} forms a monoid under [[function composition]]. The identity is just the [[identity function]]. It is also called the '''[[full transformation monoid]]''' of {{math|''S''}}. If {{math|''S''}} is finite with {{math|''n''}} elements, the monoid of functions on {{math|''S''}} is finite with {{math|''n''<sup>''n''</sup>}} elements.
* Generalizing the previous example, let {{math|''C''}} be a [[category (mathematics)|category]] and {{math|''X''}} an object of {{math|''C''}}. The set of all [[endomorphism]]s of {{math|''X''}}, denoted {{math|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 {{math|''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 {{math|1=''c'' = ''na'' + ''mb''}} where {{math|''n''}} is a positive integer and {{math|1=''m'' = 0, 1}}, or {{math|2}}. We have {{math|1=3''b'' = ''a'' + ''b''}}.
* Let <math>\langle f\rangle</math> be a cyclic monoid of order {{math|''n''}}, that is, <math>\langle f\rangle = \{f^0,f^1,\dots,f^{n-1}\}</math>. Then <math>f^n = f^k</math> for some <math>0 \le k < n</math>. In fact, each such {{math|''k''}} gives a distinct monoid of order {{math|''n''}}, and every cyclic monoid is isomorphic to one of these.<br/>Moreover, {{math|''f''}} can be considered as a function on the points <math>\{0,1,2,\dots,n-1\}</math> given by
:: <math>\begin{bmatrix}
0 & 1 & 2 & \dots & n-2 & n-1 \\
1 & 2 & 3 & \dots & n-1 & k\end{bmatrix}</math>
:or, equivalently
:: <math>f(i) := \begin{cases} i+1, & \text{if }  0 \le i < n-1  \\ k,  & \text{if } i = n-1. \end{cases} </math>
:Multiplication of elements in <math>\langle f\rangle</math> is then given by function composition.
:When <math>k = 0</math> then the function {{math|''f''}} is a permutation of <math>\{0,1,2,\dots,n-1\},</math> and gives the unique [[cyclic group]] of order {{math|''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.

From the definition of a monoid, 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 that {{math|1=''x'' • ''y'' = ''e''}} and {{math|1=''y'' • ''x'' = ''e''}}. The element ''y'' is called the inverse of ''x''. If ''y'' and ''z'' are inverses of ''x'', then by associativity {{math|1=''y'' = (''zx'')''y'' = ''z''(''xy'') = ''z''}}. Thus inverses, if they exist, are unique.<ref>Jacobson, I.5. p. 22</ref>

If ''y'' is the inverse of ''x'', one can define negative powers of ''x'' by setting {{math|1=''x''<sup>−1</sup> = ''y''}} and  {{math|1=''x''<sup>−''n''</sup> = ''y'' • ... • ''y''}} (''n'' times) for {{math|''n'' > 1}}. And the rule of exponents is still verified for all integers {{math|''n'', ''p''}}. This is why the inverse of ''x'' is usually written {{math|''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 (possibly only the [[trivial group]] consisting of only the identity).

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 {{math|1=''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 {{math|1=''b'' = ''e''}}, which isn't true. A monoid {{math|(''M'', •)}} has the [[cancellation property]] (or is [[cancellative]]) if for all ''a'', ''b'' and ''c'' in ''M'', {{math|1=''a'' • ''b'' = ''a'' • ''c''}} always implies {{math|1=''b'' = ''c''}} and {{math|1=''b'' • ''a'' = ''c'' • ''a''}} always implies {{math|1=''b'' = ''c''}}. A commutative monoid with the cancellation property can always be embedded in a group via the [[Grothendieck group|Grothendieck construction]]. That is 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. Proof: Fix an element ''x'' in the monoid. Since the monoid is finite, {{math|1=''x''<sup>''n''</sup> = ''x''<sup>''m''</sup>}} for some {{math|''m'' > ''n'' > 0}}. But then, by cancellation we have that {{math|1=''x''<sup>''m'' − ''n''</sup> = ''e''}} where ''e'' is the identity. Therefore, {{math|1=''x'' • ''x''<sup>''m'' − ''n'' − 1</sup> = ''e''}}, so ''x'' has an inverse.

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.

It turns out that requiring the cancellative property in a monoid is not required to perform the Grothendieck construction – commutativity is sufficient. However, if the original monoid has an [[absorbing element]] then its Grothendieck group is the trivial group. Hence the homomorphism is, in general, not injective.

An '''inverse monoid''' is a monoid where for every ''a'' in ''M'', there exists a unique ''a''<sup>−1</sup> in ''M'' such that {{math|1=''a'' = ''a'' • ''a''<sup>−1</sup> • ''a''}} and {{math|1=''a''<sup>−1</sup> = ''a''<sup>−1</sup> • ''a'' • ''a''<sup>−1</sup>}}. If an inverse monoid is cancellative, then it is a group.

In the opposite direction, a '''[[zerosumfree monoid]]''' is an additively written monoid in which {{math|1=''a'' + ''b'' = 0}} implies that {{math|1=''a'' = 0}} and {{math|1=''b'' = 0}}:<ref>{{cite journal|title=Tensor products of structures with interpolation |first=Friedrich |last=Wehrung |journal=Pacific Journal of Mathematics |volume=176 |issue=1 |year=1996 |pages=267–285 |zbl=0865.06010 |url= http://projecteuclid.org/euclid.pjm/1102352063 }}</ref> equivalently, that no element other than zero has an additive inverse.

==Acts and operator monoids==
{{main|monoid act}}
Let ''M'' be a monoid, with the binary operation denoted by • and the identity element denoted by ''e''. Then a (left) '''''M''-act''' (or left act over ''M'') is a set ''X'' together with an operation {{math|⋅ : ''M'' × ''X'' → ''X''}} which is compatible with the monoid structure as follows:
* for all ''x'' in ''X'': {{math|1=''e'' ⋅ ''x'' = ''x''}};
* for all ''a'', ''b'' in ''M'' and ''x'' in ''X'': {{math|1=''a'' ⋅ (''b'' ⋅ ''x'') = (''a'' • ''b'') ⋅ ''x''}}.
This is the analogue in monoid theory of a (left) [[Group action (mathematics)|group action]]. Right ''M''-acts are defined in a similar way. A monoid with an act is also known as an '''[[operator monoid]]'''. Important examples include [[transition system]]s of [[semiautomata]]. A [[transformation semigroup]] can be made into an operator monoid by adjoining the identity transformation.

== Monoid homomorphisms ==
[[File:Exponentiation as monoid homomorphism svg.svg|thumb|x150px|Example monoid homomorphism {{math|''x'' ↦ 2<sup>''x''</sup>}} from {{math|{{color|#004000|('''N''', +, 0)}}}} to {{math|{{color|#400000|('''N''', ×, 1)}}}}. It is injective, but not surjective.]]
A [[homomorphism]] between two monoids {{math|(''M'', ∗)}} and {{math|(''N'', •)}} is a function {{math|''f'' : ''M'' → ''N''}} such that
* {{math|1=''f''(''x'' ∗ ''y'') = ''f''(''x'') • ''f''(''y'')}} for all ''x'', ''y'' in ''M''
* {{math|1=''f''(''e''<sub>''M''</sub>) = ''e''<sub>''N''</sub>}},
where ''e''<sub>''M''</sub> and ''e''<sub>''N''</sub> are the identities on ''M'' and ''N'' respectively. Monoid homomorphisms are sometimes simply called '''monoid morphisms'''.

Not every [[semigroup homomorphism]] between monoids is a monoid homomorphism, since it may not map the identity to the identity of the target monoid, even though the identity is the identity of the image of homomorphism.{{example needed|date=October 2019}} So, a monoid homomorphism is  a semigroup homomorphism between monoids that maps the identity of the first monoid to the identity of the second monoid (the latter condition must not be omitted).

In contrast, a semigroup homomorphism between groups is always a [[group homomorphism]], as it necessarily preserves the identity (because, in a group, the identity is the only element such that {{math|1=''x'' ⋅ ''x'' = ''x''}}).

A [[bijective]] monoid homomorphism is called a monoid [[isomorphism]]. Two monoids are said to be isomorphic if there is a monoid isomorphism between them.

==Equational presentation==
{{main|Presentation of a monoid}}

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 Σ, and a set of relations on the [[free monoid]] Σ<sup>∗</sup>. One does this by extending (finite) [[binary relation]]s on Σ<sup>∗</sup> to monoid congruences, and then constructing the quotient monoid, as above.

Given a binary relation {{math|''R'' ⊂ Σ<sup>∗</sup> × Σ<sup>∗</sup>}}, one defines its symmetric closure as {{math|''R'' ∪ ''R''<sup>−1</sup>}}. This can be extended to a symmetric relation {{math|''E'' ⊂ Σ<sup>∗</sup> × Σ<sup>∗</sup>}} by defining {{math|''x'' ~<sub>''E''</sub> ''y''}} if and only if {{math|1=''x'' = ''sut''}} and {{math|1=''y'' = ''svt''}} for some strings {{math|''u'', ''v'', ''s'', ''t'' ∈ Σ<sup>∗</sup>}} with {{math|(''u'',''v'') ∈ ''R'' ∪ ''R''<sup>−1</sup>}}. Finally, one takes the reflexive and transitive closure of ''E'', which is then a monoid congruence.

In the typical situation, the relation ''R'' 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 ''i'', ''j'', ''k'', as the relations show that ''ba'' commutes with both ''a'' and ''b''.

== Relation to category theory ==
{{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.<ref name=Awo10>{{cite book |zbl=1100.18001 |title=Category Theory |volume=49 |series=Oxford Logic Guides |first=Steve |last=Awodey |authorlink=Steve Awodey |publisher=[[Oxford University Press]] |year=2006 |isbn=0-19-856861-4 |page=10}}</ref> That is,
: ''A monoid is, essentially, the same thing as a category with a single object.''
More precisely, given a monoid {{math|(''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.<ref name=Awo10/>  So this construction gives an [[equivalence of categories|equivalence]] between the [[category of monoids|category of (small) monoids]] '''Mon''' and a full subcategory of the category of (small) categories '''Cat'''. Similarly, the [[category of groups]] is equivalent to another full subcategory of '''Cat'''.

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. For example, a quotient of a category with one object is just a quotient monoid.

Monoids, just like other algebraic structures, also form their own category, '''Mon''', whose objects are monoids and whose morphisms are monoid homomorphisms.<ref name=Awo10/>

There is also a notion of [[monoid (category theory)|monoid object]] which is an abstract definition of what is a monoid in a category. A monoid object in '''[[category of sets|Set]]''' is just a monoid.

== Monoids in computer science ==
In computer science, many [[abstract data types]] can be endowed with a monoid structure. In a common pattern, a [[sequence]] of elements of a monoid is "[[fold (higher-order function)|folded]]" or "accumulated" to produce a final value. For instance, many iterative algorithms need to update some kind of "running total" at each iteration; this pattern may be elegantly expressed by a monoid operation. Alternatively, the associativity of monoid operations ensures that the operation can be [[parallelization|parallelized]] by employing a [[prefix sum]] or similar algorithm, in order to utilize multiple cores or processors efficiently.

Given a sequence of values of type ''M'' with identity element <math>\varepsilon</math> and associative operation <math>\bullet</math>, the ''fold'' operation is defined as follows:
: <math>\mathrm{fold}: M^{*} \rarr M = l \mapsto \begin{cases} \varepsilon & \mbox{if } l = \mathrm{nil} \\ m \bullet \mathrm{fold} \, l' & \mbox{if } l = \mathrm{cons} \, m \, l' \end{cases}</math>

In addition, any [[data structure]] can be 'folded' in a similar way, given a serialization of its elements. For instance, the result of "folding" a [[binary tree]] might differ depending on pre-order vs. post-order [[tree traversal]].

== MapReduce ==
An application of monoids in computer science is so-called [[MapReduce]] programming model (see [https://erikerlandson.github.io/blog/2016/09/05/expressing-map-reduce-as-a-left-folding-monoid/ Encoding Map-Reduce As A Monoid With Left Folding]). MapReduce, in computing, consists of two or three operations. Given a dataset, "Map" consists of mapping arbitrary data to elements of a specific monoid. "Reduce" consists of folding those elements, so that in the end we produce just one element.

For example, if we have a [[multiset]], in a program it is represented as a map from elements to their numbers. Elements are called keys in this case. The number of distinct keys may be too big, and in this case the [[multiset]] is being sharded. To finalize reduction properly, the "Shuffling" stage regroups the data among the nodes. If we do not need this step, the whole Map/Reduce consists of mapping and reducing; both operation are parallelizable, the former due to its element-wise nature, the latter due to associativity of the monoid.

==Complete monoids==
A '''complete monoid''' is a commutative monoid equipped with an [[infinitary sum]] operation <math>\Sigma_I</math> for any [[index set]] {{mvar|I}} such that:<ref name="droste">Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. {{doi|10.1007/978-3-642-01492-5_1}}, pp.&nbsp;7–10</ref><ref>{{cite journal |last=Hebisch |first=Udo |title=Eine algebraische Theorie unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe |language=German |zbl=0747.08005 |journal=Bayreuther Mathematische Schriften |volume=40 |pages=21–152 |year=1992}}</ref><ref>{{cite book |last=Kuich |first=Werner |chapter=ω-continuous semirings, algebraic systems and pushdown automata |pages=103–110 |title=Automata, Languages and Programming: 17th International Colloquium, Warwick University, England, July 16-20, 1990, Proceedings |volume=443 |series=Lecture Notes in Computer Science |editor1-first=Michael S. |editor1-last=Paterson |publisher=[[Springer-Verlag]] |year=1990 |isbn=3-540-52826-1 }}</ref><ref name=Kuich11>{{cite book |last=Kuich |first=Werner |chapter=Algebraic systems and pushdown automata |zbl=1251.68135 |editor1-last=Kuich |editor1-first=Werner |title=Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement |location=Berlin |publisher=[[Springer-Verlag]] |isbn=978-3-642-24896-2 |series=Lecture Notes in Computer Science |volume=7020 |pages=228–256 |year=2011}}</ref>

: <math>\sum_{i \in \emptyset}{m_i} =0;\quad \sum_{i \in \{j\}}{m_i} = m_j;\quad \sum_{i \in \{j, k\}}{m_i} = m_j+m_k \quad \text{ for } j\neq k</math>

and

: <math>\sum_{j \in J}{\sum_{i \in I_j}{m_i}} = \sum_{i \in I}(m_i)\quad  \text{ if } \bigcup_{j\in J} I_j=I \text{ and } I_j \cap I_{j'} = \emptyset \quad \text{ for } j\neq j'</math>

A '''continuous monoid''' is an ordered commutative monoid in which every [[directed set]] has a [[least upper bound]] compatible with the monoid operation:

: <math>a + \sup S = \sup(a + S) \ . </math>

These two concepts are closely related: a continuous monoid is a complete monoid in which the infinitary sum may be defined as

: <math> \sum_I a_i = \sup \sum_E a_i </math>

where the supremum on the right runs over all finite subsets {{mvar|E}} of {{mvar|I}} and each sum on the right is a finite sum in the monoid.<ref name=Kuich11/>

== See also ==
* [[Green's relations]]
* [[Monad (functional programming)]]
* [[Semiring]] and [[Kleene algebra]]
* [[Star height problem]]
* [[Vedic square]]

{{Div col end}}
{| style="margin:2em; border-right:1px solid Silver; border-bottom:2px solid Silver"
|
{| style="margin:4px; border:2px solid Silver"
|
{| style="margin:1em"
| [[Group (mathematics)|Group]]
|
{| style="border-left:4px solid SkyBlue"
|
{|
| Monoid
|
{| style="border-left:4px solid SkyBlue"
|
{|
| [[Semigroup]]
|
{| style="border-left:4px solid SkyBlue"
|
{|
| [[Magma (algebra)|Magma]]
|
{| style="border-left:4px solid SkyBlue"
| [[Operation (mathematics)|Operation]]
|-
| [[Closure (mathematics)|Closure]]
|}
|}
|-
| [[Associativity]]
|}
|}
|-
| [[Identity element|Identity]]
|}
|}
|-
| [[Inverse element|Inverses]]
|}
|}
|}
|}

== Notes ==
{{reflist}}

== References ==
* {{citation | first=John M. | last=Howie | authorlink=John Mackintosh Howie | title=Fundamentals of Semigroup Theory | series=London Mathematical Society Monographs. New Series | volume=12 | year=1995 | publisher=Clarendon Press | location=Oxford | isbn=0-19-851194-9 | zbl=0835.20077 }}
* {{citation | last=Jacobson | first=Nathan | author-link=Nathan Jacobson | title=Lectures in Abstract Algebra | volume=I | publisher=D. Van Nostrand Company | year=1951 | isbn=0-387-90122-1}}
* {{Citation|last=Jacobson |first=Nathan |author-link=Nathan Jacobson |year=2009 |title=Basic algebra |edition=2nd |volume=1 |publisher=Dover |isbn=978-0-486-47189-1 |ref=harv}}
* {{citation | zbl=0945.20036 | last1=Kilp | first1=Mati | last2=Knauer | first2=Ulrich | last3=Mikhalev | first3=Alexander V. | title=Monoids, acts and categories. With applications to wreath products and graphs. A handbook for students and researchers| series=de Gruyter Expositions in Mathematics | volume=29 | location=Berlin | publisher=Walter de Gruyter | year=2000 | isbn=3-11-015248-7 }}
* {{citation | last=Lothaire | first=M. | authorlink=M. Lothaire | others=Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon | title=Combinatorics on words | edition=2nd | series=Encyclopedia of Mathematics and Its Applications | volume=17 | publisher=[[Cambridge University Press]] | year=1997 | doi = 10.1017/CBO9780511566097 | isbn=0-521-59924-5 | mr = 1475463  | zbl=0874.20040 }}

== External links ==
* {{springer|title=Monoid|id=p/m064740}}
* {{MathWorld | urlname=Monoid | title=Monoid}}
* {{PlanetMath| urlname=Monoid | title=Monoid | id=389}}

[[Category:Algebraic structures]]
[[Category:Category theory]]
[[Category:Semigroup theory]]