Monoid

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.

Topics in mathematics related to structure	Edit
Abstract algebra | Number theory | Algebraic geometry | Group theory | Monoids | Analysis | Topology | Linear algebra | Graph theory | Universal algebra | Category theory | Order theory