# Cayley’s theorem for semigroups

Let $X$ be a set.
We can define on ${X}^{X}$,
the set of functions from $X$ to itself,
a structure^{} of semigroup by putting
$f\otimes g=g\circ f$.
Such semigroup is actually a monoid,
whose identity element^{} is the identity function of $X$.

###### Theorem 1 (Cayley’s theorem for semigroups)

For every semigroup $\mathrm{(}S\mathrm{,}\mathrm{\cdot}\mathrm{)}$
there exist a set $X$
and an injective map $\varphi \mathrm{:}S\mathrm{\to}{X}^{X}$
which is a morphism^{} of semigroups from $\mathrm{(}S\mathrm{,}\mathrm{\cdot}\mathrm{)}$ to $\mathrm{(}{X}^{X}\mathrm{,}\mathrm{\otimes}\mathrm{)}$.

In other words,
every semigroup is isomorphic^{} to
a semigroup of transformations of some set.
This is an extension^{} of Cayley’s theorem on groups,
which states that every group is isomorphic to
a group of *invertible ^{}* transformations

^{}of some set.

Proof of Theorem 1.
The argument is similar^{} to the one for Cayley’s theorem on groups.
Let $X=S$, the set of elements of the semigroup.

First, suppose $(S,\cdot )$ is a monoid with unit $e$. For $s\in S$ define ${f}_{s}:S\to S$ as

$${f}_{s}(x)=x\cdot s\forall x\in S.$$ | (1) |

Then for every $s,t,x\in S$ we have

${f}_{s\cdot t}(x)$ | $=$ | $x\cdot (s\cdot t)$ | ||

$=$ | $(x\cdot s)\cdot t$ | |||

$=$ | ${f}_{t}(x\cdot s)$ | |||

$=$ | ${f}_{t}({f}_{s}(x))$ | |||

$=$ | $({f}_{t}\circ {f}_{s})(x)$ | |||

$=$ | $({f}_{s}\otimes {f}_{t})(x),$ |

so $\varphi (s)={f}_{s}$ is a homomorphism^{} of monoids,
with ${f}_{e}={\mathrm{id}}_{S}$.
This homomorphism is injective^{},
because if ${f}_{s}={f}_{t}$,
then $s={f}_{s}(e)={f}_{t}(e)=t$.

Next, suppose $(S,\cdot )$ is a semigroup but not a monoid. Let $e\notin S$. Construct a monoid $(M,\ast )$ by putting $M=S\cup \{e\}$ and defining

$$s\ast t=\{\begin{array}{cc}s\cdot t\hfill & \mathrm{if}s,t\in S,\hfill \\ s\hfill & \mathrm{if}s\in S,t=e,\hfill \\ t\hfill & \mathrm{if}s=e,t\in S,\hfill \\ e\hfill & \mathrm{if}s=t=e.\hfill \end{array}$$ |

Then $(M,\ast )$ is isomorphic to a submonoid of $({M}^{M},\otimes )$ as by (1). For $s\in S$ put ${g}_{s}={{f}_{s}|}_{S}$: then ${g}_{s}\in {S}^{S}$ for every $s$, ${g}_{s\cdot t}={{f}_{s\ast t}|}_{S}$, and $(S,\cdot )$ is isomorphic to $(\mathrm{\Sigma},\otimes )$ with $\mathrm{\Sigma}=\{{g}_{s}\mid s\in S\}$. $\mathrm{\square}$

Observe that the theorem remains valid if $f\otimes g$ is defined as $f\circ g$. In this case, the morphism $\varphi $ is defined by ${f}_{s}(x)=s\cdot x\forall x\in S$.

Title | Cayley’s theorem for semigroups |
---|---|

Canonical name | CayleysTheoremForSemigroups |

Date of creation | 2013-03-22 19:04:37 |

Last modified on | 2013-03-22 19:04:37 |

Owner | Ziosilvio (18733) |

Last modified by | Ziosilvio (18733) |

Numerical id | 8 |

Author | Ziosilvio (18733) |

Entry type | Theorem |

Classification | msc 20M20 |

Classification | msc 20M15 |

Related topic | CayleysTheorem |