Monoid: Encyclopedia - Monoid

Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. In other words, it is a unital semigroup.

Monoid - Definition

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

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

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

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

Monoid - Examples

• Every singleton set {x} gives rise to a one-element (trivial) monoid. For fixed x this monoid is unique, since the monoid axioms require that x*x = x in this case.
• Every group is a monoid and every abelian group a commutative monoid.
• Every semilattice is an idempotent 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. 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.
• The set of homeomorphism classes of compact surfaces with the connected sum.

Its unit element is the class of the ordinary 2-sphere. Furthermore, if a denotes the class of the torus, and b denotes the class of the projective plane, then every element c of the monoid has a unique expression the form c=na+mb where n is the integer ≥ 0 and m=0,1, or 2. We have 3b=a+b.

Monoid - 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 two elements a and b exist 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.

A submonoid of a monoid G, is a subset H of G containing the unit element, and such that, if x,y∈H then xy∈H. It is then clear that H is itself a monoid, under the binary operation induced by that of G.

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

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.

Monoid - 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,

More precisely, given a monoid (M,*), one can construct a small category whose class of objects is the set {#} and whose morphisms are Mor(#,#) = M. Composition of morphisms is given by the monoid operation *.

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.

Monoids, just like other algebraic structures, also form their own category, Mon, whose objects are monoids and whose morphisms are monoid homomorphisms. The singleton monoids are the zero objects of this category.

Categories: Abstract algebra | Category theory | Monoid theory

Adapted from the Wikipedia article "Monoid", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki