Transformation semigroup

Transformation semigroup

In algebra, a transformation semigroup (or composition semigroup) is a collection of functions from a set to itself which is closed under function composition. If it includes the identity function, it is a transformation (or composition) monoid. This is the semigroup anologue of a permutation group.

A transformation semigroup of a set has a tautological semigroup action on that set. Such actions are characterized by being effective, i.e., if two elements of the semigroup have the same action, then they are equal.

An analogue of Cayley's theorem shows that any semigroup can be realized as a transformation semigroup of some set.

Contents

Transformation semigroups and monoids

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 X to itself, not necessarily invertible, and therefore S is simply a set of transformations of X which is closed under composition of functions. 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 TX. Thus a transformation semigroup (or monoid) is just a subsemigroup (or submonoid) of the full transformation monoid of X. The full transformation monoid is a regular semigroup.

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

 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 effective, i.e., if

 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) = sx then we can define, for sS, a transformation Ts of X by

 T_s (x) = T(s,x).\,

The map sending s to Ts is injective if and only if (XT) is effective, in which case the image of this map is a transformation semigroup isomorphic to S.

Cayley representation

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

See also

References

  • A. H. Clifford and G. B. Preston (1961), The Algebraic Theory of Semigroups, volume 1. American Mathematical Society, ISBN 978-0821802724.
  • Howie, John M. (1995). Fundamentals of Semigroup Theory. Clarendon Press. ISBN 0-19-851194-9. 
  • 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-3110152487.
  • Semigroup of transformations on PlanetMath

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Semigroup action — In algebra and theoretical computer science, an action or act of a semigroup on a set is a rule which associates to each element of the semigroup a transformation of the set in such a way that the product of two elements of the semigroup (using… …   Wikipedia

  • Semigroup — This article is about the algebraic structure. For applications to differential equations, see C0 semigroup. In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup… …   Wikipedia

  • Semigroup with involution — In mathematics, in semigroup theory, an involution in a semigroup is a transformation of the semigroup which is its own inverse and which is an anti automorphism of the semigroup. A semigroup in which an involution is defined is called a… …   Wikipedia

  • Regular semigroup — A regular semigroup is a semigroup S in which every element is regular, i.e., for each element a , there exists an element x such that axa = a . [Howie 1995 : 54.] Regular semigroups are one of the most studied classes of semigroups, and their… …   Wikipedia

  • Bicyclic semigroup — In mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. Although it is in fact a monoid, it is usually referred to as simply a semigroup. The first published description of this object was… …   Wikipedia

  • Inverse semigroup — In mathematics, an inverse semigroup S is a semigroup in which every element x in S has a unique inverse y in S in the sense that x = xyx and y = yxy. Inverse semigroups appear in a range of contexts; for example, they can be employed in the… …   Wikipedia

  • Semiautomaton — In mathematics and theoretical computer science, a semiautomaton is an automaton having only an input, and no output. It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function …   Wikipedia

  • Green's relations — In mathematics, Green s relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of… …   Wikipedia

  • Krohn–Rhodes theory — In mathematics and computer science, Krohn Rhodes theory is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These turn out to correspond to finite aperiodic semigroups and …   Wikipedia

  • Special classes of semigroups — In mathematics, a semigroup is a nonempty set together with an associative binary operation. A special class of semigroups is a class of semigroups satisfying additional properties or conditions. Thus the class of commutative semigroups consists… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”