semi-groupe - structure algébrique -

Prenons les entiers strictement positifs et additionnons-en deux : le résultat reste un entier strictement positif. Avec 2, 3 et 4, on peut d'abord calculer 2 + 3, ou commencer par 3 + 4. Dans les deux cas, le total vaut 9.

Un semi-groupe retient précisément ces deux idées : combiner deux éléments donne encore un élément du même ensemble, et changer le placement des parenthèses ne change pas le résultat. Il n'exige ni élément neutre ni opération permettant de revenir en arrière.

Un semi-groupe est formé d'un ensemble non vide, appelé ensemble sous-jacent, et d'une loi de composition interne. Cette loi associe à chaque couple d'éléments de l'ensemble un résultat qui appartient encore au même ensemble.

La loi doit être associative. Si les lettres a, b et c désignent trois éléments quelconques et si le symbole $\star \backslash star$ désigne la loi, la condition s'écrit : $(a\star b)\star c=a\star (b\star c)(a\; \backslash star\; b)\; \backslash star\; c\; =\; a\; \backslash star\; (b\; \backslash star\; c)$. Les parenthèses peuvent donc être déplacées sans modifier le résultat, mais l'ordre des éléments n'est pas supposé interchangeable.

Aucune autre propriété n'est requise. Un semi-groupe peut posséder un élément neutre, auquel cas il est aussi un monoïde, mais ce neutre n'entre pas dans sa définition. Ses éléments ne sont pas davantage tenus d'avoir des inverses. Lorsqu'un neutre et des inverses existent avec les conditions correspondantes, on obtient la structure plus riche de groupe.

Un semi-groupe réunit quatre données ou exigences. L'ensemble sous-jacent fournit les objets à combiner et doit contenir au moins un élément. La loi binaire indique comment combiner deux de ces objets. La stabilité interne impose que le résultat appartienne encore à l'ensemble. L'associativité garantit enfin que plusieurs combinaisons successives ne dépendent pas du placement des parenthèses.

La loi dépend de l'ensemble choisi : une même opération peut être interne sur un ensemble et ne pas l'être sur un autre. L'associativité porte ensuite sur cette loi précise, pour tous les triplets d'éléments. Ces données suffisent à calculer sans ambiguïté tout produit fini non vide en conservant l'ordre des facteurs. Un symbole, un dessin ou le nom des éléments ne définit pas la structure à lui seul.

Considérons l'ensemble E des entiers strictement positifs 1, 2, 3, …, muni de l'addition. Les données sont l'ensemble E, l'opération + et les trois éléments 2, 3 et 4. Un schéma de regroupement rend visible le contrôle effectué sur ce triplet.

1. Additionnons deux éléments de E. Leur somme est encore strictement positive : l'addition est donc interne sur E.

2. Calculons en regroupant les deux premiers nombres : (2 + 3) + 4 = 5 + 4 = 9.

3. Calculons en regroupant les deux derniers : 2 + (3 + 4) = 2 + 7 = 9.

L'égalité des deux résultats illustre l'associativité, qui vaut pour tous les entiers de E. Le nombre 0, neutre de l'addition, n'appartient pas à E : cet exemple est un semi-groupe sans élément neutre. Le contrôle est refaisable en remplaçant 2, 3 et 4 par n'importe quel triplet d'entiers strictement positifs.

En théorie des automates, on compose des transformations ou des actions successives. Le semi-groupe convient lorsque l'enchaînement est associatif et que l'on étudie surtout les compositions possibles. Si une action vide doit faire partie du modèle, on privilégie un monoïde doté d'un neutre.

En théorie des langages formels, on étudie des opérations de concaténation : l'ordre des symboles compte, tandis que le regroupement des concaténations ne change pas le mot obtenu. Une famille non vide de mots stable par concaténation forme un semi-groupe ; si elle contient le mot vide, elle forme un monoïde.

Dans certains systèmes combinatoires, on repère une opération de composition fermée et associative. Si chaque étape doit pouvoir être annulée, la structure de groupe devient plus adaptée ; sans cette exigence de réversibilité, le semi-groupe conserve seulement l'information nécessaire.

Semi-groupe et monoïde. Le critère qui les sépare est l'existence exigée d'un élément neutre. Les entiers strictement positifs avec l'addition forment un semi-groupe sans être un monoïde, car le neutre 0 est absent de l'ensemble.

Semi-groupe et groupe. Un groupe exige en plus un élément neutre et un inverse pour chaque élément. Dans l'exemple des entiers strictement positifs, ni 0 ni les opposés négatifs n'appartiennent à l'ensemble : l'addition y donne un semi-groupe, pas un groupe.

« Sans neutre » ne signifie pas « neutre interdit ». La définition ne l'exige simplement pas. Si un neutre existe, la structure reste un semi-groupe et possède aussi le statut de monoïde.

L'ensemble vide est exclu. Même si une condition portant sur tous ses triplets semblerait automatiquement satisfaite, le support d'un semi-groupe doit contenir au moins un élément. À l'autre extrême, un ensemble réduit à un élément, muni de son unique loi interne, fournit bien un semi-groupe.

Fermeture et associativité sont deux contrôles distincts. Une opération associative dans un cadre plus large ne définit rien sur un sous-ensemble si elle peut en sortir. Il faut d'abord vérifier que chaque résultat reste dans le support choisi.

Associatif ne veut pas dire commutatif. Déplacer les parenthèses conserve l'ordre des éléments ; les permuter est une autre propriété. Il faut donc garder l'ordre initial lorsqu'on calcule un produit dans un semi-groupe général.

Le monoïde - structure algébrique - montre ce que l'ajout d'un élément neutre apporte à une loi associative.

Le groupe - structure algébrique - prolonge cette construction en imposant aussi l'existence d'inverses.

L'article Langages formels et automates replace les compositions associatives dans un domaine d'application cité par la définition.