Demi-groupe de transformations
# 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

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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): 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.
