# 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