Demi-groupe de transformations

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Un demi-groupe de transformations est un couple , où est un ensemble, et est un demi-groupe de transformations sur . Par transformation, on entend ici une application de 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 contient l'application identité sur , 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 . Un monoïde de transformations dont les éléments sont inversibles est un groupe de permutations.

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

Un demi-groupe de transformations est un cas particulier d'un demi-groupe 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 | modifier le code]

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

Autres demi-groupes de fonction et relations[modifier | modifier le code]

  • Un demi-groupe de transformations partielles sur un ensemble est un demi-groupe d'applications partielles de dans lui-même; ceci signifie que les applications ne sont pas partout définies.
  • Un demi-groupe de bijections partielles sur un ensemble est un demi-groupe d'applications partielles de 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 est un exemple type de demi-groupe inversif, c'est-à-dire d'un demi-groupe tel que, pour tout élément , il existe un et un seul élément tel que .
  • Un demi-groupe de relations sur un ensemble est un demi-groupe de relations binaires sur , avec comme produit la composition des relations. Ce ne sont pas de applications partielles, car elles ne sont pas univalentes. Lorsque est l'ensemble , un tel demi-groupe s'identifie à un demi-groupe de matrices booléennes.

Références[modifier | modifier le code]

  • (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 » (no 29), , xviii+529 p. (ISBN 3-11-015248-7, Math Reviews 2001b:20113)
  • (en) Jean-Éric Pin, Mathematical foundations of automata theory, Support de cours du Master Parisien de Recherche en Informatique (MPRI), , 310 p. (lire en ligne)

Lien externe[modifier | modifier le code]

Articles connexes[modifier | modifier le code]