Monoid

A monoid is a pair (M,*), where M is a set and * is a binary operation on M, obeying the following rules:

1. closure: for all a, b in M, a*b is in M (this is implied by the notion of binary operation, and does not need to be required separately)
2. identity: there exists an element e in M, such that for all a in M, a*e = e*a = a.
3. associativity: * is an associative operation; that is, for all a, b, c in M, (a*b)*c = a*(b*c)

In other words, a monoid is a semigroup with an identity element.

Some examples of monoids:

• The natural numbers with addition as the operation (identity element zero), or with multiplication as operation (identity element one).
• The elements of any unitary ring, with addition or multiplication as the operation.
  • The integers, rational numbers, real numbers or complex numbers, with addition or multiplication as operation
  • The set of all n by n matrices over a given (unitary) ring, with matrix addition or matrix multiplication as the operation.
• Any group.
• The set of all finite strings (including the empty string) over some fixed alphabet Σ, with string concatenation as the operation. The empty string serves as the identity element. This monoid is denoted by Σ^* by theoretical computer scientists and called the "free monoid over Σ" by mathematicians.
• Pick an object of a category and consider the set of all morphisms from this object to itself, with composition as the operation. Some examples from well-known categories include:
  • The set of all functions from a set to itself, with composition as the operation (identity is the identity map.
  • The set of all continuous selfmaps of a topological space, with composition as the operation.
  • The set of all endomorphisms of a fixed group, with composition as the operation.
• Fix a monoid M, and consider its power set P(M) consisting of all subsets of M. A binary operation for such subsets can be defined by S * T = {s * t : s in S and t in T}. This turns P(M) into a monoid with identity element {e}.

Directly from the definition, one can show that the identity element e is unique. Then it is possible to define invertible elements: an element x is called invertible if there exists an element y such x*y = e and y*x = e. It turns out that the set of all invertible elements, together with the operation *, forms a group. In that sense, every monoid contains a group.

However, not every monoid sits inside a group. For instance, it is perfectly possible to have a monoid in which exist two elements a and b and such that a*b = a holds even though b is not the identity element. Such a monoid cannot be embedded in a group, because in the group we could multiply both sides with the inverse of a and would get that b = e, which isn't true. A monoid (M,*) has the cancellation property (or is cancellative) if for all a, b and c in M, a*b = a*c always implies b = c and b*a = c*a always implies b = c. A commutative monoid with the cancellation property can always be embedded in a group. That's how the integers (a group with operation +) are constructed from the natural numbers (a commutative monoid with operation + and cancellation property). However, a non-commutative cancellative monoid need not be embeddable in a group.

If a monoid has the cancellation property and is finite, then it is in fact a group.

An inverse monoid, is a monoid where for every a in M, there exists a unique a^-1 in M such that a=aa^-1a and a^-1=a^-1aa^-1.

It is possible to view categories as generalizations of monoids: the composition of morphism in a category shares all properties of a monoid operation except that not all pairs of morphisms may be composed. Many definitions and theorems about monoids may also be given for categories.