Transformation semigroup

A transformation semigroup is a pair (X,S), where X is a set and S is a semigroup of transformations of X. Here a transformation of X is just a function from a subset of X to X, not necessarily invertible, and therefore S is simply a set of transformations of X which is closed under composition of functions. The set of all partial functions on a given base set, X, forms a regular semigroup called the semigroup of all partial transformations (or the partial transformation semigroup on X), typically denoted by ${\displaystyle {\mathcal {PT}}_{X}}$.[2]

If S includes the identity transformation of X, then it is called a transformation monoid. Obviously any transformation semigroup S determines a transformation monoid M by taking the union of S with the identity transformation. A transformation monoid whose elements are invertible is a permutation group.

The set of all transformations of X is a transformation monoid called the full transformation monoid (or semigroup) of X. It is also called the symmetric semigroup of X and is denoted by T_X. Thus a transformation semigroup (or monoid) is just a subsemigroup (or submonoid) of the full transformation monoid of X.

If (X,S) is a transformation semigroup then X can be made into a semigroup action of S by evaluation:

${\displaystyle s\cdot x=s(x){\text{ for }}s\in S,x\in X.}$

This is a monoid action if S is a transformation monoid.

The characteristic feature of transformation semigroups, as actions, is that they are faithful, i.e., if

${\displaystyle s\cdot x=t\cdot x{\text{ for all }}x\in X,}$

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 T_s of X by

${\displaystyle T_{s}(x)=T(s,x).\,}$

The map sending s to T_s 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 theorem generalizes straightforwardly to monoids: any monoid M is a transformation monoid of its underlying set, via the action given by left (or right) multiplication. 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.

For a semigroup S without a (left or right) identity element, we take X to be the underlying set of the monoid corresponding to S to realise S as a transformation semigroup of X. In particular any finite semigroup can be represented as a subsemigroup of transformations of a set X with |X| ≤ |S| + 1, and if S is a monoid, we have the sharper bound |X| ≤ |S|, as in the case of finite groups.[3]^: 21

Let M be a deterministic automaton with state space S and alphabet A. The words in the free monoid A^∗ induce transformations of S giving rise to a monoid morphism from A^∗ to the full transformation monoid T_S. 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.[3]^: 81

• Semiautomaton
• Krohn–Rhodes theory
• Symmetric inverse semigroup
• Biordered set
• Special classes of semigroups
• Composition ring

• Clifford, A.H.; Preston, G.B. (1961). The algebraic theory of semigroups. Vol. I. Mathematical Surveys. Vol. 7. Providence, R.I.: American Mathematical Society. ISBN 978-0-8218-0272-4. Zbl 0111.03403.
• Howie, John M. (1995). Fundamentals of Semigroup Theory. London Mathematical Society Monographs. New Series. Vol. 12. Oxford: Clarendon Press. ISBN 978-0-19-851194-6. Zbl 0835.20077.
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoids, Acts and Categories: with Applications to Wreath Products and Graphs, Expositions in Mathematics 29, Walter de Gruyter, Berlin, ISBN 978-3-11-015248-7.