|
|
|
|
Cayley's theorem for semigroups
|
(Theorem)
|
|
|
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 ![[*]](http://images.planetmath.org:8080/cache/objects/11964/js//usr/share/latex2html/icons/crossref.png "[*]") . 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 \begin{equation} \label{eq:iso} f_s(x)=x\cdot s\;\forall x\in S\,. \end{equation}Then for every $s,t,x\in S$ we have \begin{eqnarray*} 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)\,, \end{eqnarray*}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
Then $(M,\ast)$ is isomorphic to a submonoid of $(M^M,\otimes)$ as by (). For $s\in S$ put $g_s=\restrict{f_s}{S}$ : then $g_s\in S^S$ for every $s$ , $g_{s\cdot t}=\restrict{f_{s\ast t}}{S}$ , and $(S,\cdot)$ is isomorphic to $(\Sigma,\otimes)$ with $\Sigma=\{g_s\mid s\in S\}$ . 
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$ .
|
"Cayley's theorem for semigroups" is owned by Ziosilvio.
|
|
(view preamble | get metadata)
Cross-references: valid, submonoid, unit, elements, similar, argument, transformations, invertible, groups, Cayley's theorem, extension, semigroup of transformations, isomorphic, words, morphism, map, injective, theorem, identity function, identity element, monoid, semigroup, structure, functions
This is version 5 of Cayley's theorem for semigroups, born on 2009-10-21, modified 2009-11-11.
Object id is 11964, canonical name is CayleysTheoremForSemigroups.
Accessed 357 times total.
Classification:
| AMS MSC: | 20M15 (Group theory and generalizations :: Semigroups :: Mappings of semigroups) | | | 20M20 (Group theory and generalizations :: Semigroups :: Semigroups of transformations, etc.) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
