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}}
{{Dark mode invert|[[File:Magma to group2.svg|thumb|Algebraic structures between [[Magma (algebra)|magmas]] and [[Group (mathematics)|groups]]. For example, monoids are [[semigroup]]s with identity.]]}}

In [[abstract algebra]], a '''monoid''' is a set equipped with an [[associative]] [[binary operation]] and an [[identity element]]. For example, the [[natural numbers]] with addition form a monoid, the identity element being {{math|0}}.

Monoids are [[semigroup]]s with identity.  Such [[algebraic structure]]s occur in several branches of mathematics. 

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

A [[set (mathematics)|set]] {{math|''S''}} equipped with a [[binary operation]] {{math|''S'' × ''S'' → ''S''}}, which we will denote {{math|•}}, is a '''monoid''' if it satisfies the following two axioms:

; Associativity: For all {{math|''a''}}, {{math|''b''}} and {{math|''c''}} in {{math|''S''}}, the equation {{math|1=(''a'' • ''b'') • ''c'' = ''a'' • (''b'' • ''c'')}} holds.
; Identity element: There exists an element {{math|''e''}} in {{math|''S''}} such that for every element {{math|''a''}} in {{math|''S''}}, the equalities {{math|1=''e'' • ''a'' = ''a''}} and {{math|1=''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.{{efn|If both {{math|''e''<sub>1</sub>}} and {{math|''e''<sub>2</sub>}} satisfy the above equations, then {{math|1=''e''<sub>1</sub> = ''e''<sub>1</sub> • ''e''<sub>2</sub> = ''e''<sub>2</sub>}}.}}  For this reason the identity is regarded as a [[Constant (mathematics)|constant]], i. e. {{math|0}}-ary (or nullary) operation. The monoid therefore is characterized by specification of the [[Tuple|triple]] {{math|(''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|1=(''ab'')''c'' = ''a''(''bc'')}} and {{math|1=''ea'' = ''ae'' = ''a''}}. This notation does not imply that it is numbers being multiplied.

A [[Group (mathematics)|group]] is a special case of a monoid where every element has an inverse.

== Monoid structures ==

=== Submonoids ===
A '''submonoid''' of a monoid {{math|(''M'', •)}} is a [[subset]] {{math|''N''}} of {{math|''M''}} that is closed under the monoid operation and contains the identity element {{math|''e''}} of {{math|''M''}}.{{sfn|ps=|Jacobson|2009}}{{efn|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 {{math|''M''}}.}} Symbolically, {{math|''N''}} is a submonoid of {{math|''M''}} if {{math|''e'' ∈ ''N'' ⊆ ''M''}}, and {{math|''x'' • ''y'' ∈ ''N''}} whenever {{math|''x'', ''y'' ∈ ''N''}}.  In this case, {{math|''N''}} is a monoid under the binary operation inherited from {{math|''M''}}.

On the other hand, if {{math|''N''}} is a subset of a monoid that is [[closure (mathematics)|closed]] under the monoid operation, and is a monoid for this inherited operation, then {{math|''N''}} is not always a submonoid, since the identity elements may differ. For example, the [[singleton set]] {{math|{{mset|0}}}} is closed under multiplication, and is not a submonoid of the (multiplicative) monoid of the [[nonnegative integer]]s.

=== Generators ===
A subset {{math|''S''}} of {{math|''M''}} is said to ''generate'' {{math|''M''}} if the smallest submonoid of {{math|''M''}} containing {{math|''S''}} is {{math|''M''}}. If there is a finite set that generates {{math|''M''}}, then {{math|''M''}} is said to be a '''finitely generated monoid'''.

=== 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 {{math|≤}}, defined by {{math|''x'' ≤ ''y''}} if there exists {{math|''z''}} such that {{math|1=''x'' + ''z'' = ''y''}}.{{sfn|ps=|Gondran|Minoux|2008|p=13}} An ''order-unit'' of a commutative monoid {{math|''M''}} is an element {{math|''u''}} of {{math|''M''}} such that for any element {{math|''x''}} of {{math|''M''}}, there exists {{math|''v''}} in the set generated by {{math|''u''}} such that {{math|''x'' ≤ ''v''}}. This is often used in case {{math|''M''}} is the [[Ordered group|positive cone]] of a [[Partially ordered set|partially ordered]] [[abelian group]] {{math|''G''}}, in which case we say that {{math|''u''}} is an order-unit of {{math|''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, four have a two-sided identity that is also commutative and associative. These four each make the set {{math|{{mset|False, True}}}} a commutative monoid. Under the standard definitions, [[Logical conjunction|AND]] and [[Logical biconditional|XNOR]] have the identity {{math|True}} while [[Exclusive disjunction|XOR]] and [[Logical disjunction|OR]] have the identity {{math|False}}. The monoids from AND and OR are also [[idempotent]] while those from XOR and XNOR are not.
* The set of [[natural number]]s {{math|1='''N''' = {{mset|0, 1, 2, ...}}}} is a commutative monoid under addition (identity element [[0 (number)|{{math|0}}]]) or multiplication (identity element [[1 (number)|{{math|1}}]]). A submonoid of {{math|'''N'''}} under addition is called a [[numerical monoid]].
* The set of [[positive integer]]s {{math|'''N''' &setminus; {{mset|0}}}} is a commutative monoid under multiplication (identity element {{math|1}}).
* Given a set {{math|''A''}}, the set of subsets of {{math|''A''}} is a commutative monoid under intersection (identity element is {{math|''A''}} itself).
* Given a set {{math|''A''}}, the set of subsets of {{math|''A''}} is a commutative monoid under union (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 {{math|•}} 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.{{sfn|ps=|Rhodes|Steinberg|2009|p=[https://books.google.com/books?id=8L0QIEj0PI4C&pg=PA22 22]}}
** 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 underlying set of any [[ring (algebra)|ring]], with addition or multiplication as the operation.  (By definition, a ring has a multiplicative identity {{math|1}}.)
** The [[integer]]s, [[rational number]]s, [[real number]]s or [[complex number]]s, with addition or multiplication as operation.{{sfn|ps=|Jacobson|2009|p=29|loc=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|Σ}}. It is not commutative if {{math|Σ}} has at least two elements.
* 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''}}, with the binary operation and identity element defined on corresponding coordinates, called the [[direct product]], is also a monoid (respectively, {{math|''M''<sub>1</sub> × ⋅⋅⋅ × ''M''<sub>''k''</sub>}}).{{sfn|ps=|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 {{math|''b''}} denotes the class of the projective plane, then every element {{math|''c''}} of the monoid has a unique expression in 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|{{angle bracket|{{itco|''f''}}}}}} be a cyclic monoid of order {{math|''n''}}, that is, {{math|1={{angle bracket|{{itco|''f''}}}} = {{mset|{{itco|''f''}}<sup>0</sup>, {{itco|''f''}}<sup>1</sup>, ..., {{itco|''f''}}<sup>''n''−1</sup>}}}}. Then {{math|1={{itco|''f''}}<sup>''n''</sup> = {{itco|''f''}}<sup>''k''</sup>}} for some {{math|0 ≤ ''k'' < ''n''}}. 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|{{mset|0, 1, 2, ..., ''n''−1}}}} given by
<math display="block">\begin{bmatrix}
 0 & 1 & 2 & \cdots & n-2 & n-1 \\
 1 & 2 & 3 & \cdots & n-1 & k\end{bmatrix}</math> or, equivalently <math display="block">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|{{angle bracket|{{itco|''f''}}}}}} is then given by function composition. {{pb}} When {{math|1=''k'' = 0}} then the function {{math|''f''}} is a permutation of {{math|{{mset|0, 1, 2, ..., ''n''−1}}}}, and gives the unique [[cyclic group]] of order {{math|''n''}}.

== Properties ==
By the monoid axioms the identity element {{math|''e''}} is unique, since if {{math|''e''}} and {{math|''f''}} were identity elements of a monoid, then {{math|1=''e'' = ''ef'' = ''f''}}.

=== Products and powers ===
For each nonnegative integer {{math|''n''}}, one can define the product <math>p_n = \textstyle \prod_{i=1}^n a_i</math> of any sequence {{math|(''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>)}} of {{math|''n''}} elements of a monoid recursively: let {{math|1=''p''<sub>0</sub> = ''e''}} and let {{math|1=''p''<sub>''m''</sub> = ''p''<sub>''m''−1</sub> • ''a''<sub>''m''</sub>}} for {{math|1 ≤ ''m'' ≤ ''n''}}.

As a special case, one can define nonnegative integer powers of an element {{math|''x''}} of a monoid: {{math|1=''x''<sup>0</sup> = 1}} and {{math|1=''x''<sup>''n''</sup> = ''x''<sup>''n''−1</sup> • ''x''}} for {{math|''n'' ≥ 1}}.  Then {{math|1=''x''<sup>''m''+''n''</sup> = ''x''<sup>''m''</sup> • ''x''<sup>''n''</sup>}} for all {{math|''m'', ''n'' ≥ 0}}.

=== Invertible elements ===
An element {{math|''x''}} is called [[inverse element|invertible]] if there exists an element {{math|''y''}} such that {{math|1=''x'' • ''y'' = ''e''}} and {{math|1=''y'' • ''x'' = ''e''}}. The element {{math|''y''}} is called the inverse of {{math|''x''}}. Inverses, if they exist, are unique: if {{math|''y''}} and {{math|''z''}} are inverses of {{math|''x''}}, then by associativity {{math|1=''y'' = ''ey'' = (''zx'')''y'' = ''z''(''xy'') = ''ze'' = ''z''}}.{{sfn|ps=|Jacobson|2009|p=31|loc=§1.2}}

If {{math|''x''}} is invertible, say with inverse {{math|''y''}}, then one can define negative powers of {{math|''x''}} by setting {{math|1=''x''<sup>−''n''</sup> = ''y''<sup>''n''</sup>}} for each {{math|''n'' ≥ 1}}; this makes the equation {{math|1=''x''<sup>''m''+''n''</sup> = ''x''<sup>''m''</sup> • ''x''<sup>''n''</sup>}} hold for all {{math|''m'', ''n'' ∈ '''Z'''}}.

The set of all invertible elements in a monoid, together with the operation •, forms a [[group (mathematics)|group]].

=== Grothendieck group ===
{{main|Grothendieck group}}
Not every monoid sits inside a group. For instance, it is perfectly possible to have a monoid in which two elements {{math|''a''}} and {{math|''b''}} exist such that {{math|1=''a'' • ''b'' = ''a''}} holds even though {{math|''b''}} is not the identity element (for example, take ''a'' = 0 and ''b'' = 5 in the multiplicative monoid of nonnegative integers.) Such a monoid cannot be embedded in a group, because in the group multiplying both sides with the inverse of {{math|''a''}} would get that {{math|1=''b'' = ''e''}}, which is not true. 

A monoid {{math|(''M'', •)}} has the [[cancellation property]] (or is cancellative) if for all {{math|''a''}}, {{math|''b''}} and {{math|''c''}} in {{math|''M''}}, the equality {{math|1=''a'' • ''b'' = ''a'' • ''c''}} implies {{math|1=''b'' = ''c''}}, and the equality {{math|1=''b'' • ''a'' = ''c'' • ''a''}} implies {{math|1=''b'' = ''c''}}. 

A commutative monoid with the cancellation property can always be embedded in a group via the ''Grothendieck group construction''. That is how the additive group of the integers (a group with operation {{math|+}}) is constructed from the additive monoid of natural numbers (a commutative monoid with operation {{math|+}} 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.{{efn|Proof: Fix an element {{math|''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 {{math|''e''}} is the identity. Therefore, {{math|1=''x'' • ''x''<sup>''m''−''n''−1</sup> = ''e''}}, so {{math|''x''}} has an inverse.}}

The right- and left-cancellative elements of a monoid each in turn form a submonoid (i.e. are closed under the operation and obviously include the identity). This means that the cancellative elements of any commutative monoid can be extended to a group.

The cancellative property in a monoid is not necessary to perform the Grothendieck construction – commutativity is sufficient. However, if a commutative monoid does not have the cancellation property, the homomorphism of the monoid into its Grothendieck group is not injective. More precisely, if {{math|1=''a'' • ''b'' = ''a'' • ''c''}}, then {{math|''b''}} and {{math|''c''}} have the same image in the Grothendieck group, even if {{math|''b'' ≠ ''c''}}. In particular, if the monoid has an [[absorbing element]], then its Grothendieck group is the [[trivial group]].

=== Types of monoids ===
An '''inverse monoid''' is a monoid where for every {{math|''a''}} in {{math|''M''}}, there exists a unique {{math|''a''<sup>−1</sup>}} in {{math|''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}}:{{sfn|ps=|Wehrung|1996}} equivalently, that no element other than zero has an additive inverse.

== Acts and operator monoids ==
{{main|Monoid act}}
Let {{math|''M''}} be a monoid, with the binary operation denoted by {{math|•}} and the identity element denoted by {{math|''e''}}. Then a (left) '''{{math|''M''}}-act''' (or left act over {{math|''M''}}) is a set {{math|''X''}} together with an operation {{math|⋅ : ''M'' × ''X'' → ''X''}} which is compatible with the monoid structure as follows:
* for all {{math|''x''}} in {{math|''X''}}: {{math|1=''e'' ⋅ ''x'' = ''x''}};
* for all {{math|''a''}}, {{math|''b''}} in {{math|''M''}} and {{math|''x''}} in {{math|''X''}}: {{math|1=''a'' ⋅ (''b'' ⋅ ''x'') = (''a'' • ''b'') ⋅ ''x''}}.
This is the analogue in monoid theory of a (left) [[group action]]. Right {{math|''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 {{math|''x''}}, {{math|''y''}} in {{math|''M''}}
* {{math|1=''f''(''e''<sub>''M''</sub>) = ''e''<sub>''N''</sub>}},
where {{math|''e''<sub>''M''</sub>}} and {{math|''e''<sub>''N''</sub>}} are the identities on {{math|''M''}} and {{math|''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 the homomorphism.{{efn|{{math|1=''f''(''x'') ∗ ''f''(''e''<sub>''M''</sub>) = ''f''(''x'' ∗ ''e''<sub>''M''</sub>) = ''f''(''x'')}} for each {{math|''x''}} in {{math|''M''}}, when {{math|''f''}} is a semigroup homomorphism and {{math|''e''<sub>''M''</sub>}} is the identity of its domain monoid {{math|''M''}}.}} For example, consider {{math|['''Z''']<sub>''n''</sub>}}, the set of [[residue class]]es modulo {{math|''n''}} equipped with multiplication. In particular, {{math|[1]<sub>''n''</sub>}} is the identity element. Function {{math|''f'' : ['''Z''']<sub>3</sub> → ['''Z''']<sub>6</sub>}} given by {{math|[''k'']<sub>3</sub> ↦ [3''k'']<sub>6</sub>}} is a semigroup homomorphism, since {{math|1=[3''k'' ⋅ 3''l'']<sub>6</sub> = [9''kl'']<sub>6</sub> = [3''kl'']<sub>6</sub>}}. However, {{math|1=''f''([1]<sub>3</sub>) = [3]<sub>6</sub> ≠ [1]<sub>6</sub>}}, 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 and the latter condition cannot be omitted.

In contrast, a semigroup homomorphism between groups is always a [[group homomorphism]], as it necessarily preserves the identity (because, in the target group of the homomorphism, the identity element is the only element {{math|''x''}} 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 {{math|Σ}}, and a set of relations on the [[free monoid]] {{math|Σ<sup>∗</sup>}}. One does this by extending (finite) [[binary relation]]s on {{math|Σ<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 {{math|''E''}}, which is then a monoid congruence.

In the typical situation, the relation {{math|''R''}} is simply given as a set of equations, so that {{math|1=''R'' = {{mset|1=''u''<sub>1</sub> = ''v''<sub>1</sub>, ..., ''u''<sub>''n''</sub> = ''v''<sub>''n''</sub>}}}}. 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 {{math|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''}}, {{math|''j''}}, {{math|''k''}}, as the relations show that {{math|''ba''}} commutes with both {{math|''a''}} and {{math|''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.{{sfn|ps=|Awodey|2006|p=10}} 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 {{math|''M''}}. The composition of morphisms is given by the monoid operation&nbsp;{{math|•}}.

Likewise, monoid homomorphisms are just [[functor]]s between single object categories.{{sfn|ps=|Awodey|2006|p=10}}  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.{{sfn|ps=|Awodey|2006|p=10}}

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 {{math|''M''}} with identity element {{math|''ε''}} and associative operation&nbsp;{{math|•}}, the ''fold'' operation is defined as follows:
<math display="block">\mathrm{fold}: M^{*} \rarr M = \ell \mapsto \begin{cases} \varepsilon & \text{if } \ell = \mathrm{nil} \\
m \bullet \mathrm{fold} \, \ell' & \text{if } \ell = \mathrm{cons} \, m \, \ell' \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 the 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 operations 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 [[Finitary|infinitary]] sum operation <math>\Sigma_I</math> for any [[index set]] {{math|''I''}} such that{{sfn|ps=|Droste|Kuich|2009|pp=7–10}}{{sfn|ps=|Hebisch|1992}}{{sfn|ps=|Kuich|1990}}{{sfn|Kuich|2011}}
<math display="block">\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 display="block">\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>.

An '''ordered commutative monoid''' is a commutative monoid {{math|''M''}} together with a [[partial ordering]] {{math|≤}} such that {{math|''a'' ≥ 0}} for every {{math|''a'' ∈ ''M''}}, and {{math|''a'' ≤ ''b''}} implies {{math|''a'' + ''c'' ≤ ''b'' + ''c''}} for all {{math|''a'', ''b'', ''c'' ∈ ''M''}}.

A '''continuous monoid''' is an ordered commutative monoid {{math|(''M'', ≤)}} in which every [[directed set|directed subset]] has a [[least upper bound]], and these least upper bounds are compatible with the monoid operation:
<math display="block">a + \sup S = \sup(a + S)</math>
for every {{math|''a'' ∈ ''M''}} and directed subset {{math|''S''}} of {{math|''M''}}.

If {{math|(''M'', ≤)}} is a continuous monoid, then for any index set {{math|''I''}} and collection of elements {{math|(''a''{{sub|''i''}}){{sub|''i''∈''I''}}}}, one can define  
<math display="block"> \sum_I a_i = \sup_{\text{finite } E \subset I} \; \sum_E a_i, </math>
and {{math|''M''}} together with this infinitary sum operation is a complete monoid.{{sfn|Kuich|2011}}

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

== Notes ==
{{notelist}}

== Citations ==
{{reflist}}

== References ==
{{refbegin}}
* {{cite book | last=Awodey | first=Steve | author-link=Steve Awodey | title=Category Theory | volume=49 | series=Oxford Logic Guides | publisher=[[Oxford University Press]] | year=2006 | isbn=0-19-856861-4 | zbl=1100.18001 }}
* {{citation | last1=Droste | first1=M. | last2=Kuich | first2=W | year=2009 | chapter=Semirings and Formal Power Series | title=Handbook of Weighted Automata | series=Monographs in Theoretical Computer Science. An EATCS Series | pages=3–28 | doi=10.1007/978-3-642-01492-5_1  | isbn=978-3-642-01491-8 | citeseerx=10.1.1.304.6152 }}
* {{cite book | last1=Gondran | first1=Michel | last2=Minoux | first2=Michel | title=Graphs, Dioids and Semirings: New Models and Algorithms | year=2008 | location=Dordrecht | publisher=[[Springer-Verlag]] | series=Operations Research/Computer Science Interfaces Series | volume=41 | isbn=978-0-387-75450-5 | zbl=1201.16038 }}
* {{cite journal | last=Hebisch | first=Udo | title=Eine algebraische Theorie unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe | language=de | journal=Bayreuther Mathematische Schriften | volume=40 | pages=21–152 | year=1992 | zbl=0747.08005 }}
* {{citation | first=John M. | last=Howie | author-link=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 }}
* {{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 }}
* {{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 | chapter-url=https://archive.org/details/automatalanguage0000ical/page/103 }}
* {{cite book | last=Kuich | first=Werner | chapter=Algebraic systems and pushdown automata | 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 | zbl=1251.68135 }}
* {{citation | editor1-last=Lothaire | editor1-first=M. | editor1-link=M. Lothaire | 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 }}
* {{citation | last1=Rhodes | first1=John | last2=Steinberg | first2=Benjamin | title=The q-theory of Finite Semigroups: A New Approach | volume=71 | series=Springer Monographs in Mathematics | publisher=Springer | year=2009 | isbn=9780387097817 }}
* {{cite journal | last=Wehrung | first=Friedrich | title=Tensor products of structures with interpolation | url=http://projecteuclid.org/euclid.pjm/1102352063 | journal=Pacific Journal of Mathematics | volume=176 | issue=1 | year=1996 | pages=267–285 | doi=10.2140/pjm.1996.176.267 | zbl=0865.06010 | s2cid=56410568 | doi-access=free }}
{{refend}}

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