Demi-groupe de transformations

En algèbre, un demi-groupe de transformations est un ensemble de fonctions d'un ensemble X dans lui-même qui est fermé pour l'opération de composition. S'il contient l'application identité, c'est un monoïde de transformations. C'est l'analogue, pour les demi-groupes, d'un groupe de permutations.

Un analogue du théorème de Cayley vaut pour les demi-groupes : tout demi-groupe est isomorphe à un demi-groupe de transformations sur un ensemble.

Un demi-groupe de transformations est un couple ${\displaystyle (X,S)}$, où ${\displaystyle X}$ est un ensemble, et ${\displaystyle S}$ est un demi-groupe de transformations sur ${\displaystyle X}$. Par transformation, on entend ici une application de ${\displaystyle X}$ dans lui-même, non nécessairement inversible, mais partout définie. L'ensemble est un demi-groupe, c'est-à-dire fermé pour la composition de fonctions. Si ${\displaystyle S}$ contient l'application identité sur ${\displaystyle X}$, alors c'est un monoïde de transformations. On peut étendre un demi-groupe de transformations en un monoïde en lui ajoutant l'application identité sur ${\displaystyle X}$. Un monoïde de transformations dont les éléments sont inversibles, et fermé pour l'opération inverse, est un groupe de permutations.

L'ensemble de toutes les transformations de ${\displaystyle X}$ est appelé le monoïde de transformations plein (« full transformation monoid » en anglais). Il est noté ${\displaystyle T(X)}$ ou ${\displaystyle T_{X}}$. Dans le cas où ${\displaystyle X}$ est l'ensemble des entiers de 1 à ${\displaystyle n}$, on écrit ${\displaystyle T_{n}}$. Le monoïde ${\displaystyle T(X)}$ de toutes les transformations de ${\displaystyle X}$ est un demi-groupe régulier.

Un demi-groupe de transformations est un cas particulier d'un demi-groupe ${\displaystyle S}$ opérant sur un ensemble; il a la propriété d'opérer fidèlement : par définition, ceci signifie que si deux éléments du demi-groupe réalisent la même action, alors ils sont égaux.

En théorie des groupes, le théorème de Cayley affirme que tout groupe ${\displaystyle G}$ est isomorphe à un sous-groupe du groupe symétrique sur ${\displaystyle G}$, considéré comme un ensemble, de sorte que ${\displaystyle G}$ est un groupe de permutations. Ce théorème s'étend directement aux monoïdes : tout monoïde ${\displaystyle M}$ est un monoïde de transformations sur ${\displaystyle M}$ vu comme un ensemble; l'action est simplement la multiplication à droite (ou à gauche), c'est-à-dire la transformation associée à ${\displaystyle a\in M}$ est l'application ${\displaystyle x\mapsto xa}$, pour ${\displaystyle x\in M}$. Cette action est fidèle parce si ${\displaystyle xa=xb}$ pour tout ${\displaystyle x\in M}$, c'est en particulier le cas quand ${\displaystyle x}$ est l'élément neutre, ce qui implique que ${\displaystyle a=b}$. Dans le cas d'un demi-groupe ${\displaystyle S}$ sans élément neutre, on prend comme ensemble sous-jacent l'ensemble ${\displaystyle X=S^{1}}$ obtenu en adjoignant un élément neutre à ${\displaystyle S}$. Alors ${\displaystyle S}$ est réalisé comme demi-groupe de transformations sur ${\displaystyle X}$.

• Un demi-groupe de transformations partielles sur un ensemble ${\displaystyle X}$ est un demi-groupe d'applications partielles de ${\displaystyle X}$ dans lui-même; ceci signifie que les applications ne sont pas partout définies.

• Un demi-groupe de bijections partielles sur un ensemble ${\displaystyle X}$ est un demi-groupe d'applications partielles de ${\displaystyle X}$ dans lui-même qui sont toutes des bijections de leur ensemble de définition sur leur image. Le monoïde de toutes les bijections partielles sur un ensemble ${\displaystyle X}$ est un exemple type de demi-groupe inversif, c'est-à-dire d'un demi-groupe tel que, pour tout élément ${\displaystyle a}$, il existe un et un seul élément ${\displaystyle x}$ tel que ${\displaystyle axa=a}$.

• Un demi-groupe de relations sur un ensemble ${\displaystyle X}$ est un demi-groupe de relations binaires sur ${\displaystyle X}$, avec comme produit la composition des relations. Ce ne sont pas de applications partielles, car elles ne sont pas univalentes. Lorsque ${\displaystyle X}$ est l'ensemble ${\displaystyle \{1,\ldots ,n\}}$, un tel demi-groupe s'identifie à un demi-groupe de matrices booléennes.

• (en) Alfred H. Clifford et Gordon B. Preston, The algebraic theory of semigroups, vol. I, Providence, R.I., American Mathematical Society, coll. « Mathematical Surveys » (n^o 7-Part I), 1961, xv+224 (ISBN 1470412349, OCLC 882503487, MR 0132791)

• (en) Mati Kilp, Ulrich Knauer et Alexander V. Mikhalev, Monoids, acts and categories : With applications to wreath products and graphs. A handbook for students and researchers, Berlin, Walter de Gruyter & Co, coll. « de Gruyter Expositions in Mathematics » (n^o 29), 2000, xviii+529 (ISBN 3-11-015248-7, MR 2001b:20113)

• (en) Jean-Éric Pin, Mathematical foundations of automata theory, Support de cours du Master Parisien de Recherche en Informatique (MPRI), 2012, 310 p. (lire en ligne)

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « transformation semigroup » (voir la liste des auteurs).

• (en) « Semigroup of transformations », sur PlanetMath

• Théorie de Krohn–Rhodes (en)
• Symmetric inverse semigroup (en)
• Liste des classes de demi-groupes (en)

• Portail de l’algèbre