A monoid is a pair $(X, ⋄)$ where $X$ is a set and $⋄$ is an associative binary operator with an identity. $⋄$ is often interpreted as concatenation; data structures that support concatenation and have an "empty element" (such as lists, strings, and the natural numbers under addition) are examples of monoids.

Monoids are algebraic structures. We write $x ⋄ y$ for the application of $⋄$ to $x, y \in X$ , which must be defined. $x ⋄ y$ is commonly abbreviated $x y$ when $⋄$ can be inferred from context. The monoid axioms (which govern the behavior of $⋄$ ) are as follows.

(Closure) For all $x, y$ in $X$ , $x y$ is also in $X$ .

(Associativity) For all $x, y, z$ in $X$ , $x (y z) = (x y) z$ .

(Identity) There is an $e$ in $X$ such that, for all $x$ in $X$ , $x e = e x = x .$

The axiom of closure says that $x ⋄ y \in X$ , i.e. that combining two elements of $X$ using $⋄$ yields another element of $X$ . In other words, $X$ is closed under $⋄$ .

The axiom of associativity says that $⋄$ is an associative operation, which justifies omitting parenthesis when describing the application of $⋄$ to many elements in sequence..

The axiom of identity says that there is some element $e$ in $X$ that $⋄$ treats as "empty": If you apply $⋄$ to $e$ and $x$ , then $⋄$ simply returns $x$ . The identity is unique: Given two elements $e$ and $z$ that satisfy the axiom of identity, we have $z e = e = e z = z .$ Thus, we can speak of "the identity" $e$ of $M$ . $e$ is often written $1$ or $1_{M}$ .

Equivalently, a monoid is a category with exactly one object.

Monoids are semigroups equipped with an identity. Groups are monoids with inverses. For more on how monoids relate to other algebraic structures, refer to the tree of algebraic structures.

Notation

Given a monoid $M = (X, ⋄)$ , we say " $X$ forms a monoid under $⋄$ ." For example, the set of finite bitstrings forms a monoid under concatenation: The set of finite bitstrings is closed under concatenation; concatenation is an associative operation; and the empty bitstring is a finite bitstring that acts like an identity under concatenation.

$X$ is called the underlying set of $M$ , and $⋄$ is called the monoid operation. $x ⋄ y$ is usually abbreviated $x y$ . $M$ is generally allowed to substitute for $X$ when discussing the monoid. For example, we say that the elements $x, y \in X$ are "in $M$ ," and sometimes write " $x, y \in M$ " or talk about the "elements of $M$ ."

Examples

Bitstrings form a monoid under concatenation, with the empty string as the identity.

The set of finite lists of elements drawn from $Y$ (for any set $Y$ ) form a monoid under concatenation, with the empty list as the identity.

The natural numbers $N$ form a monid under addition, with $0$ as the identity.

Monoids have found some use in functional programming languages such as Haskell and Scala, where they are used to generalize over data types in which values can be "combined" (by some operation $⋄$ ) and which include an "empty" value (the identity).