In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations (functions from a set to itself) that is closed under function composition.
A transformation monoid whose elements are invertible is a permutation group.
The characteristic feature of transformation semigroups, as actions, is that they are faithful, i.e., if then s = t. Conversely if a semigroup S acts on a set X by T(s,x) = s • x then we can define, for s ∈ S, a transformation Ts of X by The map sending s to Ts is injective if and only if (X, T) is faithful, in which case the image of this map is a transformation semigroup isomorphic to S. In group theory, Cayley's theorem asserts that any group G is isomorphic to a subgroup of the symmetric group of G (regarded as a set), so that G is a permutation group.
This action is faithful because if ax = bx for all x in M, then by taking x equal to the identity element, we have a = b.
Two examples of useful transformation monoids given by an action of left multiplication are the functional variation of the difference list data structure, and the monadic Codensity transformation (a Cayley representation of a monad, which is a monoid in a particular monoidal functor category).
The image of this morphism is the transformation semigroup of M.[3]: 78 For a regular language, the syntactic monoid is isomorphic to the transformation monoid of the minimal automaton of the language.