Monoid
In algebra, a monoid is a set equipped with a binary operation satisfying certain properties similar to but less stringent than those of a group. A motivating example of a monoid is the set of positive integers with multiplication as the operation.
Formally, a monoid is set M with a binary operation satisfying the following conditions:
- M is closed under ;
- The operation is associative
- There is an identity element such that
- for all x in M.
A commutative monoid is one which satisfies the further property that for all x and y in M. Commutative monoids are often written additively.
An element x of a monoid is invertible if there exists an element y such that : this is the inverse element for x and may be written as : by associativity an element can have at most one inverse (note that as well). The identity element is self-inverse and the product of invertible elements is invertible,
so the invertible elements form a group, the unit group of M.
A pseudoinverse for x is an element such that . The inverse, if it exists, is a pseudoinverse, but a pseudoinverse may exists for a non-invertible element.
A submonoid of M is a subset S of M which contains the identity element I and is closed under the binary operation.
A monoid homomorphism f from monoid to is a map from M to N satisfying
- ;
Examples
- The non-negative integers under addition form a commutative monoid, with zero as identity element.
- The positive integers under multiplication form a commutative monoid, with one as identity element.
- The set of all maps from a set to itself forms a monoid, with function composition as the operation and the identity map as the identity element.
- Square matrices under matrix multiplication form a monoid, with the identity matrix as the identity element: this monoid is not in general commutative.
- Every group is a monoid, by "forgetting" the inverse operation.
Cancellation property
A monoid satisfies the cancellation property if
- and
A monoid is a submonoid of a group if and only if it satisfies the cancellation property.
Free monoid
The free monoid on a set G of generators is the set of all words on G, the finite sequences of elements of G, with the binary operation being concatenation (juxtaposition). The identity element is the empty (zero-length) word. The free monoid on one generator g may be identified with the monoid of non-negative integers