Cayley’s theorem for semigroups

Let X be a set. We can define on XX, the set of functions from X to itself, a structureMathworldPlanetmath of semigroup by putting fg=gf. Such semigroup is actually a monoid, whose identity elementMathworldPlanetmath is the identity function of X.

Theorem 1 (Cayley’s theorem for semigroups)

For every semigroup (S,) there exist a set X and an injective map ϕ:SXX which is a morphismMathworldPlanetmathPlanetmath of semigroups from (S,) to (XX,).

In other words, every semigroup is isomorphicPlanetmathPlanetmathPlanetmath to a semigroup of transformations of some set. This is an extensionPlanetmathPlanetmathPlanetmath of Cayley’s theorem on groups, which states that every group is isomorphic to a group of invertiblePlanetmathPlanetmathPlanetmath transformationsPlanetmathPlanetmath of some set.

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

First, suppose (S,) is a monoid with unit e. For sS define fs:SS as

fs(x)=xsxS. (1)

Then for every s,t,xS we have

fst(x) = x(st)
= (xs)t
= ft(xs)
= ft(fs(x))
= (ftfs)(x)
= (fsft)(x),

so ϕ(s)=fs is a homomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath of monoids, with fe=idS. This homomorphism is injectivePlanetmathPlanetmath, because if fs=ft, then s=fs(e)=ft(e)=t.

Next, suppose (S,) is a semigroup but not a monoid. Let eS. Construct a monoid (M,) by putting M=S{e} and defining


Then (M,) is isomorphic to a submonoid of (MM,) as by (1). For sS put gs=fs|S: then gsSS for every s, gst=fst|S, and (S,) is isomorphic to (Σ,) with Σ={gssS}.

Observe that the theorem remains valid if fg is defined as fg. In this case, the morphism ϕ is defined by fs(x)=sxxS.

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