applet-magic.com Thayer Watkins Silicon Valley & Tornado
Alley USA

Some SimpleTheorems
Concerning Monoids

A monoid is an associative binary function defined over a set which has a left identity element.
Semigroups are the only simpler algebraic structure, They have no identity element.

Definition. A function monoid is a set of functions defined over a set which
is closed under function composition and includes the identity function,

Theorem: For any monoid there is a function
monoid to which it is isomorphic.

Proof:

Let M be a monoid over the set S and f:S×S→S its binary associative function with e its
left identity element.

For each element a of S create the function g_{a}(x)=f(a, x). The set G of such functions
is at least a semigroup with respect to function composition. The left identity element of G is the
function g_{e}(x)=f(e, x). Therefore G is a monoid.

It is isomorphic to M under the two-way mapping

a ↔ g_{a}

because if f(a, b)=c then it also holds that g_{a}°g_{b}=g_{c}
and vice versa. The composition g_{a}°g_{b} is, in terms of their definitions,

f(a,f(b,x)) = f(f(a, b), x) = f(c, x) = g_{c}(x)

This theorem can be considered as Cayley's Theorem for monoids.

A Semigroup Completion Lemma

Any semigroup may be converted into a monoid by adjoining a left identity element to its set. Let S be any semigroup
and Z be its set. Let the binary function for S be denoted as f( , ); i.e., f:Z×Z→Z.
Then let e be an element not in Z. Create Z* as Z∪{e} and define f(e, z)=z for all z in Z*.