monoid

A monoid is an algebraic structure consisting of a set M equipped with an associative binary operation and an identity element. Formally, it is a pair (M, ⋅) where ⋅: M × M → M is closed and associative, and there exists an element e ∈ M such that e ⋅ a = a ⋅ e = a for all a ∈ M. If every element has an inverse, the monoid is a group; if inverses are not required, it remains a monoid.

Common examples include the natural numbers under addition with 0 as the identity, the natural numbers under multiplication with 1 as the identity, and the set of strings over a fixed alphabet under concatenation with the empty string as the identity. The set of all functions from a set to itself forms a monoid under composition, with the identity function as the identity element.

Submonoids are nonempty subsets that are closed under the operation and contain the identity. A monoid homomorphism preserves the operation, i.e., f(a ⋅ b) = f(a) ⋅ f(b). Isomorphisms identify monoids that are structurally the same. The free monoid on a set A consists of all finite strings over A with concatenation as the operation and the empty string as the identity.

Monoids are foundational in algebra and computer science, where they model concatenation, endomorphisms, and program semantics. In category theory, a monoid is a simple example of a monoid object in the category of sets, and many constructions in algebra reduce to monoid-theoretic notions.