San José State University
Thayer Watkins
Silicon Valley
& Tornado Alley

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.

If f(x, y) is associative then

f(f(x, y), z) = f(x, f(y, z))

Lemma: Function composition is associative.

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

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


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 ga(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 ge(x)=f(e, x). Therefore G is a monoid.

It is isomorphic to M under the two-way mapping

a ↔ ga

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

f(a,f(b,x)) = f(f(a, b), x) = f(c, x) = gc(x)

(To be continued.)

HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins,