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

A Generalization of Cayley's Theorem
Which Includes Monoids and Semigroups
and All Other Algebraic Structures

Cayley's Theorem: Any group is isomorphic to a subgroup of a permutations group.

Arthur Cayley was an Irish mathematician. The name Cayley is the Irish name more commonly spelled Kelly.

A semigroup is a binary associative function and a monoid is a binary associative function with an identity element. They are nothing more than these. It is strange that they were given names that give no clues as to their nature when those two terms which tell exactly what they are would be perfectly suitable names. This is an example of the mathematics community focusing on the elements of an algebraic structure when those elements are just irrelevant names and the mathematical structure is contained in their functions.

Let H be an algebraic structure whose operation is a binary associative function.
Then H is homomorphic to a subset of the permutations of its elements.


Let S be the set of elements of the algebraic structure H and let * be its operation.

Now let F be the set of one-to-one functions from the set S to the set S. Such functions are called permutations of the set. The set F with function composition (·) is a group.

Proof of this proposition concerning permutations

Function composition is closed and associative. There is an identity element e(x)=x for all x belonging to S. There is an inverse for any function: if f(x)=y then f-1(y)=x. Thus (F, ·) is a group.

Proof of the thorem

For any element h of S consider the function fh(x)=h*x for all x in S. This function is an element of F.

Consider fg*h(x). Since H is an algebraic structure g*h is an element of S and hence fg*h is an element of F. Furthermore, since * is associative in H, for any x in S

(g*h)*x = g*(h*x) = g*(fh(x)) = fg(fh(x)) = fg·fh(x)
(g*h)*x is fg*h(x)
fg*h = fg·fh

Thus all products g*h in H correspond to a composition fg·fh in F. Therefore the set {fh for all h in H} is a subset of F which is closed under composition. Furthermore the composition of the correspondences of two elements is equal to the correspondence of their product. Thus H is homomorphic to a subset of F with the operation function composition, (·).

The intent was to generalize Cayley's Theorem to include monoids and semigroups. What was found was far more general because any algebraic structure includes an associative operation. However the existence of a homomorphism is less significant than the existence of an isomorphism as in Cayley's Theorem. Nevertheless the general theorem ties all algebraic structures in some fashion to the permutations of a set.

HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins