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).