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

Demi-groupes et monoïdes de transformations

Un demi-groupe de transformations est un couple $(X,S)$, où $X$ est un ensemble, et $S$ est un demi-groupe de transformations sur $X$. Par transformation, on entend ici une application de $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 $S$ contient l'application identité sur $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 $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 $X$ est appelé le monoïde de transformations plein (« full transformation monoid » en anglais). Il est noté $T(X)$ ou $T_{X}$. Dans le cas où $X$ est l'ensemble des entiers de 1 à $n$, on écrit $T_{n}$. Le monoïde $T(X)$ de toutes les transformations de $X$ est un demi-groupe régulier.

Un demi-groupe de transformations est un cas particulier d'un demi-groupe $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.

Représentation de Cayley

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

Autres demi-groupes de fonction et relations

• Un demi-groupe de transformations partielles sur un ensemble $X$ est un demi-groupe d'applications partielles de $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 $X$ est un demi-groupe d'applications partielles de $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 $X$ est un exemple type de demi-groupe inversif, c'est-à-dire d'un demi-groupe tel que, pour tout élément $a$, il existe un et un seul élément $x$ tel que $axa=a$.

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

Références

• (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).

Lien externe

• Modèle:Planetmath reference

Articles connexes

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