Monoid

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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

  • Any group.
  • The integers or natural numbers or complex numbers, with multiplication as the operation.
  • The natural numbers, with addition as the operation.
  • The set of all finite strings (including the empty string) over some fixed alphabet Σ, with string concatenation as the operation. This is denoted by Σ* by theoretical computer scientists and called the "free monoid over Σ" by mathematicians.
  • The elements of every unitary ring, with multiplication as the operation. An example of this is the set of all n by n matrices with matrix multiplication.
  • Pick an object of a category and consider the set of all morphisms from this object to itself, with composition as the operation. (See category theory.) Some examples from well-known categories include:
    • 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.
    • The set of all functions from a set to itself, with composition as the operation.

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.

It it 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 proved for categories.