A monoid is a mathematical concept that is used in abstract algebra. It 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.
In more detail, a monoid is a set S equipped with a binary operation S × S → S, which we will denote •, if it satisfies the following two axioms:
- Associativity: For all a, b and c in S, the equation (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 equalities e • a = a and a • e = a hold.
Monoids are semigroups with identity. Such algebraic structures 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 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 strings built from a given set of characters is a free monoid. Transition monoids and syntactic monoids are used in describing finite-state machines. Trace monoids and history monoids 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.
A submonoid of a monoid (M, •) is a subset N of M that is closed under the monoid operation and contains the identity element e of M. Symbolically, N is a submonoid of M if e ∈ N ⊆ M, and x • y ∈ N whenever x, y ∈ N. In this case, N is a monoid under the binary operation inherited from M. On the other hand, if N is subset of a monoid that is closed under the monoid operation, and is a monoid for this inherited operation, then N is not always a submonoid, since the identity elements may differ.
A monoid homomorphism is a function between two monoids that preserves the binary operation and maps the identity element of one to the identity element of the other. Formally, let (M, ∗) and (N, •) be two monoids. A function f : M → N is called a homomorphism if it satisfies two conditions:
- f(x ∗ y) = f(x) • f(y) for all x, y in M
- f(eM) = eN where eM and eN are the identity elements of M and N respectively.
To contact me, send an email anytime or leave a comment below.