Monoid

A monoid $$M$$ is a pair $$(X, \diamond)$$ where $$X$$ is a set and $$\diamond$$ is an as­so­ci­a­tive bi­nary op­er­a­tor with an iden­tity.$$\diamond$$ is of­ten in­ter­preted as con­cate­na­tion; data struc­tures that sup­port con­cate­na­tion and have an “empty el­e­ment” (such as lists, strings, and the nat­u­ral num­bers un­der ad­di­tion) are ex­am­ples of monoids.

Monoids are alge­braic struc­tures. We write $$x \diamond y$$ for the ap­pli­ca­tion of $$\diamond$$ to $$x, y \in X$$, which must be defined.$$x \diamond y$$ is com­monly ab­bre­vi­ated $$xy$$ when $$\diamond$$ can be in­ferred from con­text. The monoid ax­ioms (which gov­ern the be­hav­ior of $$\diamond$$) are as fol­lows.

1. (Clo­sure) For all $$x, y$$ in $$X$$, $$xy$$ is also in $$X$$.

2. (As­so­ci­a­tivity) For all $$x, y, z$$ in $$X$$, $$x(yz) = (xy)z$$.

3. (Iden­tity) There is an $$e$$ in $$X$$ such that, for all $$x$$ in $$X$$, $$xe = ex = x.$$

The ax­iom of clo­sure says that $$x \diamond y \in X$$, i.e. that com­bin­ing two el­e­ments of $$X$$ us­ing $$\diamond$$ yields an­other el­e­ment of $$X$$. In other words, $$X$$ is closed un­der $$\diamond$$.

The ax­iom of as­so­ci­a­tivity says that $$\diamond$$ is an as­so­ci­a­tive op­er­a­tion, which jus­tifies omit­ting paren­the­sis when de­scribing the ap­pli­ca­tion of $$\diamond$$ to many el­e­ments in se­quence..

The ax­iom of iden­tity says that there is some el­e­ment $$e$$ in $$X$$ that $$\diamond$$ treats as “empty”: If you ap­ply $$\diamond$$ to $$e$$ and $$x$$, then $$\diamond$$ sim­ply re­turns $$x$$. The iden­tity is unique: Given two el­e­ments $$e$$ and $$z$$ that satisfy the ax­iom of iden­tity, we have $$ze = e = ez = z.$$ Thus, we can speak of “the iden­tity” $$e$$ of $$M$$. $$e$$ is of­ten writ­ten $$1$$ or $$1_M$$.

knows-req­ui­site(Cat­e­gory the­ory): Equiv­a­lently, a monoid is a cat­e­gory with ex­actly one ob­ject.

Monoids are semi­groups equipped with an iden­tity. Groups are monoids with in­verses. For more on how monoids re­late to other alge­braic struc­tures, re­fer to the tree of alge­braic struc­tures.

Notation

Given a monoid $$M = (X, \diamond)$$, we say ”$$X$$ forms a monoid un­der $$\diamond$$.” For ex­am­ple, the set of finite bit­strings forms a monoid un­der con­cate­na­tion: The set of finite bit­strings is closed un­der con­cate­na­tion; con­cate­na­tion is an as­so­ci­a­tive op­er­a­tion; and the empty bit­string is a finite bit­string that acts like an iden­tity un­der con­cate­na­tion.

$$X$$ is called the un­der­ly­ing set of $$M$$, and $$\diamond$$ is called the monoid op­er­a­tion.$$x \diamond y$$ is usu­ally ab­bre­vi­ated $$xy$$. $$M$$ is gen­er­ally al­lowed to sub­sti­tute for $$X$$ when dis­cussing the monoid. For ex­am­ple, we say that the el­e­ments $$x, y \in X$$ are “in $$M$$,” and some­times write “$$x, y \in M$$” or talk about the “el­e­ments of $$M$$.”

Examples

Bit­strings form a monoid un­der con­cate­na­tion, with the empty string as the iden­tity.

The set of finite lists of el­e­ments drawn from $$Y$$ (for any set $$Y$$) form a monoid un­der con­cate­na­tion, with the empty list as the iden­tity.

The nat­u­ral num­bers $$\mathbb N$$ form a monid un­der ad­di­tion, with $$0$$ as the iden­tity.

Monoids have found some use in func­tional pro­gram­ming lan­guages such as Haskell and Scala, where they are used to gen­er­al­ize over data types in which val­ues can be “com­bined” (by some op­er­a­tion $$\diamond$$) and which in­clude an “empty” value (the iden­tity).