> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/400-abstract-algebra/algebras/monoid.md). # monoid ## Monoid In abstract algebra, a **monoid** is an algebraic structure M = (S, •, ε) a set endowed with an associative binary operation that has an identity element. A monoid is an algebraic structure M = (S, •, ε) closed under * a single *associative* binary operation and * an *identity* element For example, 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*. 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 CS, the study of monoids is fundamental for automata theory and formal language theory. ### Definition If star is a binary operation on a `S` set: $$\star: S \times S \to S$$, then `S` with `⋆` is a monoid if it satisfies the axioms of associativity and identity. Associativity: $$\forall a,b,c \in S\ .\ (a \star b) \star c = a \star (b \star c)$$ Identity: $$!\exists e, \forall a\in S\ .\ e \star a = a \star e = a$$ * The monoid is specified by the triple: $$(S,\star,e)$$. * Its identity element is unique and thus a constant (nullary) operation. * A monoid is a semigroup with an identity element. * A monoid is a magma with associativity and identity. * A monoid in which each element has an inverse is a group. ## Monoid In abstract algebra, a monoid is an algebraic structure with a single associative binary operation and an identity element. Algebraic structures * Monoid: * one binary operation * associativity * totality (closure) * identity Monoid is a semigroup with an identity. For example, collection of all functions from a set into itself, form a monoid with respect to function composition. Function composition is the associative, total, binary operation: function composition is always associative; it is total as it produces new elements that are (still) functions, i.e. new elements remain of the same type, that is, the composition of two functions gives the new function (element) that is also a function (an element in that same set). 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 CS, 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 CS, the study of monoids is fundamental for automata theory (Krohn–Rhodes theory), and formal language theory (star height problem). ### Ref ### Related )