Monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element.
For example, the nonnegative integers with addition form a monoid, the identity element being 0.
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 (ab)c = a(bc) and ea = ae = a.
Any commutative monoid is endowed with its algebraic preordering ≤, defined by x ≤ y if there exists z such that x + z = y.
When k = 0 then the function f is a permutation of {0, 1, 2, ..., n−1}, and gives the unique cyclic group of order n. The monoid axioms imply that the identity element e is unique: If e and f are identity elements of a monoid, then e = ef = f. For each nonnegative integer n, one can define the product
[6] If x is invertible, say with inverse y, then one can define negative powers of x by setting x−n = yn for each n ≥ 1; this makes the equation xm+n = xm • xn hold for all m, n ∈ Z.
The set of all invertible elements in a monoid, together with the operation •, forms a group.
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).
[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.
Important examples include transition systems of semiautomata.
A homomorphism between two monoids (M, ∗) and (N, •) is a function f : M → N such that where eM and eN are the identities on M and N respectively.
[d] For example, consider [Z]n, the set of residue classes modulo n equipped with multiplication.
This can be extended to a symmetric relation E ⊂ Σ∗ × Σ∗ by defining x ~E y if and only if x = sut and y = svt for some strings u, v, s, t ∈ Σ∗ with (u,v) ∈ R ∪ R−1.
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 R = {u1 = v1, ..., un = vn}.
for integers i, j, k, as the relations show that ba commutes with both a and b. Monoids can be viewed as a special class of categories.
Likewise, monoid homomorphisms are just functors between single object categories.
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.
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 "folded" or "accumulated" to produce a final value.
Alternatively, the associativity of monoid operations ensures that the operation can be 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 ε and associative operation •, the fold operation is defined as follows: In addition, any data structure can be 'folded' in a similar way, given a serialization of its elements.
For example, if we have a multiset, in a program it is represented as a map from elements to their numbers.
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.
