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.

Demi-groupes et monoïdes de transformations modifier

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 modifier

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 modifier

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 modifier

(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 modifier

(en) « Semigroup of transformations », sur PlanetMath

Articles connexes modifier

Portail de l’algèbre