Inabstract algebra, amonoid is a set equipped with anassociativebinary operation and anidentity element. For example, the nonnegativeintegers with addition form a monoid, the identity element being0.

Monoids aresemigroups with identity. Suchalgebraic structures occur in several branches of mathematics.

The functions from a set into itself form a monoid with respect to function composition. More generally, incategory theory, the morphisms of anobject to itself form a monoid, and, conversely, a monoid may be viewed as a category with a single object.

Incomputer science andcomputer programming, the set ofstrings built from a given set ofcharacters is afree monoid.Transition monoids andsyntactic monoids are used in describingfinite-state machines.Trace monoids andhistory monoids provide a foundation forprocess calculi andconcurrent computing.

Intheoretical computer science, the study of monoids is fundamental forautomata theory (Krohn–Rhodes theory), andformal language theory (star height problem).

Seesemigroup for the history of the subject, and some other general properties of monoids.

AsetS equipped with abinary operationS ×S →S, which we will denote•, is amonoid if it satisfies the following two axioms:

Associativity

For alla,b andc inS, the equation(a •b) •c =a • (b •c) holds.

Identity element

There exists an elemente inS such that for every elementa inS, the equalitiese •a =a anda •e =a hold.

In other words, a monoid is asemigroup with anidentity element. It can also be thought of as amagma with associativity and identity. The identity element of a monoid is unique.^[a] For this reason the identity is regarded as aconstant, i. e.0-ary (or nullary) operation. The monoid therefore is characterized by specification of thetriple(S, • ,e).

Depending on the context, the symbol for the binary operation may be omitted, so that the operation is denoted byjuxtaposition; for example, the monoid axioms may be written(ab)c =a(bc) andea =ae =a. This notation does not imply that it is numbers being multiplied.

A monoid in which each element has aninverse is agroup.

Asubmonoid of a monoid(M, •) is asubsetN ofM that is closed under the monoid operation and contains the identity elemente ofM.^[1][b] Symbolically,N is a submonoid ofM ife ∈N ⊆M, andx •y ∈N wheneverx,y ∈N. In this case,N is a monoid under the binary operation inherited fromM.

On the other hand, ifN is a subset of a monoid that isclosed under the monoid operation, and is a monoid for this inherited operation, thenN is not always a submonoid, since the identity elements may differ. For example, thesingleton set{0} is closed under multiplication, and is not a submonoid of the (multiplicative) monoid of thenonnegative integers.

A subsetS ofM is said togenerateM if the smallest submonoid ofM containingS isM. If there is a finite set that generatesM, thenM is said to be afinitely generated monoid.

A monoid whose operation iscommutative is called acommutative monoid (or, less commonly, anabelian monoid). Commutative monoids are often written additively. Any commutative monoid is endowed with itsalgebraicpreordering≤, defined byx ≤y if there existsz such thatx +z =y.^[2] Anorder-unit of a commutative monoidM is an elementu ofM such that for any elementx ofM, there existsv in the set generated byu such thatx ≤v. This is often used in caseM is thepositive cone of apartially orderedabelian groupG, in which case we say thatu is an order-unit ofG.

A monoid for which the operation is commutative for some, but not all elements is atrace monoid; trace monoids commonly occur in the theory ofconcurrent computation.

• Out of the 16 possiblebinary Boolean operators, four have a two-sided identity that is also commutative and associative. These four each make the set{False, True} a commutative monoid. Under the standard definitions,AND andXNOR have the identityTrue whileXOR andOR have the identityFalse. The monoids from AND and OR are alsoidempotent while those from XOR and XNOR are not.
• The set ofnatural numbersN = {0, 1, 2, ...} is a commutative monoid under addition (identity element0) or multiplication (identity element1). A submonoid ofN under addition is called anumerical monoid.
• The set ofpositive integersN ∖ {0} is a commutative monoid under multiplication (identity element1).
• Given a setA, the set of subsets ofA is a commutative monoid under intersection (identity element isA itself).
• Given a setA, the set of subsets ofA is a commutative monoid under union (identity element is theempty set).
• Generalizing the previous example, every boundedsemilattice is anidempotent commutative monoid.
  • In particular, any boundedlattice can be endowed with both ameet- and ajoin- monoid structure. The identity elements are the lattice's top and its bottom, respectively. Being lattices,Heyting algebras andBoolean algebras are endowed with these monoid structures.
• Everysingleton set{x} closed under a binary operation• forms the trivial (one-element) monoid, which is also thetrivial group.
• Everygroup is a monoid and everyabelian group a commutative monoid.
• AnysemigroupS may be turned into a monoid simply by adjoining an elemente not inS and defininge •s =s =s •e for alls ∈S. This conversion of any semigroup to the monoid is done by thefree functor between the category of semigroups and the category of monoids.^[3]
  • Thus, an idempotent monoid (sometimes known asfind-first) may be formed by adjoining an identity elemente to theleft zero semigroup over a setS. The opposite monoid (sometimes calledfind-last) is formed from theright zero semigroup overS.
    • Adjoin an identitye to the left-zero semigroup with two elements{lt, gt}. Then the resulting idempotent monoid{lt,e, gt} models thelexicographical order of a sequence given the orders of its elements, withe representing equality.
• The underlying set of anyring, with addition or multiplication as the operation. (By definition, a ring has a multiplicative identity1.)
  • Theintegers,rational numbers,real numbers orcomplex numbers, with addition or multiplication as operation.^[4]
  • The set of alln bynmatrices over a given ring, withmatrix addition ormatrix multiplication as the operation.
• The set of all finitestrings over some fixed alphabetΣ forms a monoid withstring concatenation as the operation. Theempty string serves as the identity element. This monoid is denotedΣ^∗ and is called thefree monoid overΣ. It is not commutative ifΣ has at least two elements.
• Given any monoidM, theopposite monoidM^op has the same carrier set and identity element asM, and its operation is defined byx •^opy =y •x. Any commutative monoid is the opposite monoid of itself.
• Given two setsM andN endowed with monoid structure (or, in general, any finite number of monoids,M₁, ...,M_k), theirCartesian productM ×N, with the binary operation and identity element defined on corresponding coordinates, called thedirect product, is also a monoid (respectively,M₁ × ⋅⋅⋅ ×M_k).^[5]
• Fix a monoidM. The set of all functions from a given set toM is also a monoid. The identity element is aconstant function mapping any value to the identity ofM; the associative operation is definedpointwise.
• Fix a monoidM with the operation• and identity elemente, and consider itspower setP(M) consisting of allsubsets ofM. A binary operation for such subsets can be defined byS •T = {s •t :s ∈S,t ∈T }. This turnsP(M) into a monoid with identity element{e}. In the same way the power set of a groupG is a monoid under theproduct of group subsets.
• LetS be a set. The set of all functionsS →S forms a monoid underfunction composition. The identity is just theidentity function. It is also called thefull transformation monoid ofS. IfS is finite withn elements, the monoid of functions onS is finite withnⁿ elements.
• Generalizing the previous example, letC be acategory andX an object ofC. The set of allendomorphisms ofX, denotedEnd_C(X), forms a monoid under composition ofmorphisms. For more on the relationship between category theory and monoids see below.
• The set ofhomeomorphismclasses ofcompact surfaces with theconnected sum. Its unit element is the class of the ordinary 2-sphere. Furthermore, ifa denotes the class of thetorus, andb denotes the class of the projective plane, then every elementc of the monoid has a unique expression in the formc =na +mb wheren is a positive integer andm = 0, 1, or2. We have3b =a +b.
• Let⟨f⟩ be a cyclic monoid of ordern, that is,⟨f⟩ = {f⁰,f¹, ...,fⁿ⁻¹}. Thenfⁿ =f^k for some0 ≤k <n. Each suchk gives a distinct monoid of ordern, and every cyclic monoid is isomorphic to one of these.
  Moreover,f can be considered as a function on the points{0, 1, 2, ...,n−1} given by

  or, equivalently 

Multiplication of elements in⟨f⟩ is then given by function composition.

Whenk = 0 then the functionf is a permutation of{0, 1, 2, ...,n−1}, and gives the uniquecyclic group of ordern.

The monoid axioms imply that the identity elemente is unique: Ife andf are identity elements of a monoid, thene =ef =f.

For each nonnegative integern, one can define the product${\displaystyle p_n=\prod _{i=1}^n{a}_i}$  of any sequence(a₁, ...,a_n) ofn elements of a monoid recursively: letp₀ =e and letp_m =p_m−1 •a_m for1 ≤m ≤n.

As a special case, one can define nonnegative integer powers of an elementx of a monoid:x⁰ = 1 andxⁿ =xⁿ⁻¹ •x forn ≥ 1. Thenx^m+n =x^m •xⁿ for allm,n ≥ 0.

An elementx is calledinvertible if there exists an elementy such thatx •y =e andy •x =e. The elementy is called the inverse ofx. Inverses, if they exist, are unique: ify andz are inverses ofx, then by associativityy =ey = (zx)y =z(xy) =ze =z.^[6]

Ifx is invertible, say with inversey, then one can define negative powers ofx by settingx⁻ⁿ =yⁿ for eachn ≥ 1; this makes the equationx^m+n =x^m •xⁿ hold for allm,n ∈Z.

The set of all invertible elements in a monoid, together with the operation •, forms agroup.

Not every monoid sits inside a group. For instance, it is perfectly possible to have a monoid in which two elementsa andb exist such thata •b =a holds even thoughb is not the identity element. Such a monoid cannot be embedded in a group, because in the group multiplying both sides with the inverse ofa would get thatb =e, which is not true.

A monoid(M, •) has thecancellation property (or is cancellative) if for alla,b andc inM, the equalitya •b =a •c impliesb =c, and the equalityb •a =c •a impliesb =c.

A commutative monoid with the cancellation property can always be embedded in a group via theGrothendieck group 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 isfinite, then it is in fact a group.^[c]

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, ifa •b =a •c, thenb andc have the same image in the Grothendieck group, even ifb ≠c. In particular, if the monoid has anabsorbing element, then its Grothendieck group is thetrivial group.

Aninverse monoid is a monoid where for everya inM, there exists a uniquea⁻¹ inM such thata =a •a⁻¹ •a anda⁻¹ =a⁻¹ •a •a⁻¹. If an inverse monoid is cancellative, then it is a group.

In the opposite direction, azerosumfree monoid is an additively written monoid in whicha +b = 0 implies thata = 0 andb = 0:^[7] equivalently, that no element other than zero has an additive inverse.

LetM be a monoid, with the binary operation denoted by• and the identity element denoted bye. Then a (left)M-act (or left act overM) is a setX together with an operation⋅ :M ×X →X which is compatible with the monoid structure as follows:

• for allx inX:e ⋅x =x;
• for alla,b inM andx inX:a ⋅ (b ⋅x) = (a •b) ⋅x.

This is the analogue in monoid theory of a (left)group action. RightM-acts are defined in a similar way. A monoid with an act is also known as anoperator monoid. Important examples includetransition systems ofsemiautomata. Atransformation semigroup can be made into an operator monoid by adjoining the identity transformation.

Ahomomorphism between two monoids(M, ∗) and(N, •) is a functionf :M →N such that

• f(x ∗y) =f(x) •f(y) for allx,y inM
• f(e_M) =e_N,

wheree_M ande_N are the identities onM andN respectively. Monoid homomorphisms are sometimes simply calledmonoid morphisms.

Not everysemigroup 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.^[d] For example, consider[Z]_n, the set ofresidue classes modulon equipped with multiplication. In particular,[1]_n is the identity element. Functionf : [Z]₃ → [Z]₆ given by[k]₃ ↦ [3k]₆ is a semigroup homomorphism, since[3k ⋅ 3l]₆ = [9kl]₆ = [3kl]₆. However,f([1]₃) = [3]₆ ≠ [1]₆, 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 agroup homomorphism, as it necessarily preserves the identity (because, in the target group of the homomorphism, the identity element is the only elementx such thatx ⋅x =x).

Abijective monoid homomorphism is called a monoidisomorphism. Two monoids are said to be isomorphic if there is a monoid isomorphism between them.

Monoids may be given apresentation, much in the same way that groups can be specified by means of agroup presentation. One does this by specifying a set of generatorsΣ, and a set of relations on thefree monoidΣ^∗. One does this by extending (finite)binary relations onΣ^∗ to monoid congruences, and then constructing the quotient monoid, as above.

Given a binary relationR ⊂ Σ^∗ × Σ^∗, one defines its symmetric closure asR ∪R⁻¹. This can be extended to a symmetric relationE ⊂ Σ^∗ × Σ^∗ by definingx ~_Ey if and only ifx =sut andy =svt for some stringsu,v,s,t ∈ Σ^∗ with(u,v) ∈R ∪R⁻¹. Finally, one takes the reflexive and transitive closure ofE, which is then a monoid congruence.

In the typical situation, the relationR is simply given as a set of equations, so thatR = {u₁ =v₁, ...,u_n =v_n}. Thus, for example,

${\displaystyle ⟨p,q|pq=1⟩}$ 

is the equational presentation for thebicyclic monoid, and

${\displaystyle ⟨a,b|aba=baa,bba=bab⟩}$ 

is theplactic monoid of degree2 (it has infinite order). Elements of this plactic monoid may be written as${\displaystyle a^i{b}^j(ba{)}^k}$  for integersi,j,k, as the relations show thatba commutes with botha andb.

Monoids can be viewed as a special class ofcategories. Indeed, the axioms required of a monoid operation are exactly those required ofmorphism composition when restricted to the set of all morphisms whose source and target is a given object.^[8] 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 ofM. The composition of morphisms is given by the monoid operation •.

Likewise, monoid homomorphisms are justfunctors between single object categories.^[8] So this construction gives anequivalence between thecategory of (small) monoidsMon and a full subcategory of the category of (small) categoriesCat. Similarly, thecategory of groups is equivalent to another full subcategory ofCat.

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.^[8]

There is also a notion ofmonoid object which is an abstract definition of what is a monoid in a category. A monoid object inSet is just a monoid.

In computer science, manyabstract data types can be endowed with a monoid structure. In a common pattern, asequence of elements of a monoid is "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 beparallelized by employing aprefix sum or similar algorithm, in order to utilize multiple cores or processors efficiently.

Given a sequence of values of typeM with identity elementε and associative operation •, thefold operation is defined as follows:

 

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

An application of monoids in computer science is the so-calledMapReduce programming model (seeEncoding 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 amultiset, 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, themultiset 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.

Acomplete monoid is a commutative monoid equipped with aninfinitary sum operation${\displaystyle {\mathrm{\Sigma }}_I}$  for anyindex setI such that^{[9][10][11][12]}

${\displaystyle \sum _{i\in \mathrm{\varnothing }}{m}_i=0;\sum _{i\in \{j\}}{m}_i=m_j;\sum _{i\in \{j,k\}}{m}_i=m_j+m_k\text{ for }j\ne k}$ 

and

${\displaystyle \sum _{j\in J}\sum _{i\in I_j}{m}_i=\sum _{i\in I}{m}_i\text{ if }\bigcup _{j\in J}{I}_j=I\text{ and }{I}_j\cap I_{j^{\prime }}=\mathrm{\varnothing }\text{ for }j\ne j^{\prime }}$ .

Anordered commutative monoid is a commutative monoidM together with apartial ordering≤ such thata ≥ 0 for everya ∈M, anda ≤b impliesa +c ≤b +c for alla,b,c ∈M.

Acontinuous monoid is an ordered commutative monoid(M, ≤) in which everydirected subset has aleast upper bound, and these least upper bounds are compatible with the monoid operation:

${\displaystyle a+supS=sup(a+S)}$ 

for everya ∈M and directed subsetS ofM.

If(M, ≤) is a continuous monoid, then for any index setI and collection of elements(a_i)_i∈I, one can define

${\displaystyle \sum _I{a}_i=\underset{\text{finite }E\subset I}{sup}\sum _E{a}_i,}$ 

andM together with this infinitary sum operation is a complete monoid.^[12]

• Cartesian monoid
• Green's relations
• Monad (functional programming)
• Semiring andKleene algebra
• Star height problem
• Vedic square
• Frobenioid

• "Monoid",Encyclopedia of Mathematics,EMS Press, 2001 [1994]
• Weisstein, Eric W."Monoid".MathWorld.
• Monoid atPlanetMath.