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

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

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

  • (en) Alfred H. Clifford et Gordon B. Preston, The algebraic theory of semigroups, vol. I, Providence, R.I., American Mathematical Society, coll. « Mathematical Surveys » (no 7-Part I),‎ 1961, xv+224 p. (ISBN 978-0-8218-0271-2[à vérifier : ISBN invalide])
  • (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),‎ 2000, xviii+529 p. (ISBN 3-11-015248-7)
  • (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)

Lien externe[modifier | modifier le code]

Articles connexes[modifier | modifier le code]