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 toa semigroup of transformations of some set.This is an extension of Cayley’s theorem on groups,which states that every group is isomorphic toa 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\ot\\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 validif $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$ .