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
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