Encyclopedia > Monoid

  Article Content

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

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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Dust bowl

... the North American Great Plains there was a years-long drought, leading to soil erosion and dust storms. Crops failed, forcing many farmers to leave in search of work ...