Monoid

For people who check facts

In abstract algebra, a branch of mathematics, a '\monoid' is a set together with a binary operation satisfying certain axioms, detailed below.

Table of contents

1 Definition
2 Examples
3 Properties
4 Monoid homomorphisms
5 Relation to category theory

Definition

A monoid is a magma (M,*), i.e. a set M with binary operation * : M × M → M, obeying the following rules:

Associativity: for all a, b, c in M, (a*b)*c = a*(b*c)
Identity element: there exists an element e in M, such that for all a in M, a*e = e*a = a.

One often sees the additional axiom

Closure: for all a, b in M, a*b is in M

though, strictly speaking, this isn't necessary as it is implied by the notion of a binary operation.

Alternatively, a monoid is a semigroup with an identity element.

Note that a monoid satisfies all the axioms of a group with the exception of having inverses. A monoid with inverses is the same thing a group.

An monoid whose operation is commutative is called a commutative monoid (or, less commonly, an abelian monoid).

Examples

Every group is a monoid and every abelian group a commutative monoid.
Any semigroup S may be turned into a monoid simply by adjoining an element e not in S and defining ee = e and es = s = se for all s ∈ S. Note that this can be done recursively (i.e. if S is monoid with identity e, one obtains a new monoid S ∪ {e′} with identity e′, and so on).
The natural numbers, N, form a commutative monoid under addition (identity element zero), or multiplication (identity element one).
The elements of any unital 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 ring, with matrix addition or matrix multiplication as the operation.
The set of all finite strings over some fixed alphabet Σ forms a monoid with string concatenation as the operation. The empty string serves as the identity element. This monoid is denoted Σ^* and is called the free monoid over Σ.
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}.
Let S be a set. The set of all functions S → S forms a monoid under function composition. The identity is just the identity function. If S is finite with n elements, the monoid of functions on S is finite with nⁿ elements.
Generalizing the previous example, let C be a category and X an object in C. The set of all endomorphisms of X, denoted End_C(X), forms a monoid under composition of morphisms. For more on the relationship between category theory and monoids see below.

Properties

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.

Monoid homomorphisms

A homomorphism between two monoids (M, *) and (M′, @) is a function f : M → M′ such that

f(x*y) = f(x)@f(y) for all x, y in M
f(e) = e′

where e and e′ are the identities on M and M′ respectively. Note that not every magma homomorphism is a monoid homomorphism since it may not preserve the identity. Contrast this with the case of group homomorphisms: the axioms of group theory ensure that every magma homomorphism between groups preserves the identity. For monoids this isn't always true and it is necessary to state it as a separate requirement.

A bijective monoid homomorphism is called a monoid isomorphism. Two monoids are said to be isomorphic if there is an isomorphism between them.

Relation to category theory

Monoids can be viewed as a special class of categories. The axioms required of a monoid operation are exactly those required of morphism composition when restricted to the set of all morphisms which start and end at a given object (i.e. an endomorphism). That is,

A monoid is, essentially, the same thing as a category with a single object.

Likewise, monoid homomorphisms are just functors between single object categories. In this sense, category theory can be thought of as an extension of the concept of a monoid. Many definitions and theorems about monoids can be generalised to small categories with more than one object.