# 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 $(S,\cdot)$ there exist a set $X$ and an injective map $\phi:S\to X^{X}$ which is a morphism of semigroups from $(S,\cdot)$ to $(X^{X},\otimes)$.

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

 $\displaystyle f_{s\cdot t}(x)$ $\displaystyle=$ $\displaystyle x\cdot(s\cdot t)$ $\displaystyle=$ $\displaystyle(x\cdot s)\cdot t$ $\displaystyle=$ $\displaystyle f_{t}(x\cdot s)$ $\displaystyle=$ $\displaystyle f_{t}(f_{s}(x))$ $\displaystyle=$ $\displaystyle(f_{t}\circ f_{s})(x)$ $\displaystyle=$ $\displaystyle(f_{s}\otimes f_{t})(x)\,,$

so $\phi(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\not\in S$. Construct a monoid $(M,\ast)$ by putting $M=S\cup\{e\}$ and defining

 $s\ast t=\left\{\begin{array}[]{ll}s\cdot t&\mathrm{if}\;s,t\in S,\\ s&\mathrm{if}\;s\in S,t=e,\\ t&\mathrm{if}\;s=e,t\in S,\\ e&\mathrm{if}\;s=t=e.\\ \end{array}\right.$

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

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

Title Cayley’s theorem for semigroups CayleysTheoremForSemigroups 2013-03-22 19:04:37 2013-03-22 19:04:37 Ziosilvio (18733) Ziosilvio (18733) 8 Ziosilvio (18733) Theorem msc 20M20 msc 20M15 CayleysTheorem