Demi-groupe

Cet article concerne la structure algébrique. Pour les applications aux équations différentielles, voir C₀-semigroupe (en) ou Semi-groupes.

En mathématiques, plus précisément en algèbre générale, un demi-groupe (ou semi-groupe) est une structure algébrique constituée d'un ensemble muni d'une loi de composition interne associative. Il est dit commutatif si sa loi est de plus commutative.

Un demi-groupe est un magma associatif. Autrement dit, c'est un couple ${\displaystyle (S,\star )}$ composé d'un ensemble S et d'une opération ${\displaystyle \star }$ qui vérifie la propriété d'associativité : ${\displaystyle (a\star b)\star c=a\star (b\star c)}$ pour tous a, b et c dans S.

• L'ensemble des entiers naturels non nuls muni de l'addition est un demi-groupe.
• Tout monoïde est un demi-groupe.
• Tout groupe est un demi-groupe.
• Si ${\displaystyle (A,+,*)}$ est un pseudo-anneau, alors ${\displaystyle (A,*)}$ est un demi-groupe.
• L'ensemble vide^[1] muni de la loi de composition interne est un demi-groupe.
• Tout ensemble ordonné dont toute paire d'éléments possède une borne inférieure, muni de la loi qui leur associe cette borne inférieure, constitue un demi-groupe commutatif^[2].
• Pour tout demi-groupe ${\displaystyle (S,*)}$, l'ensemble des parties de S est également un demi-groupe pour l'opération définie par${\displaystyle A\cdot B=\{a*b\mid a\in A,b\in B\}.}$

L'étude des demi-groupes, en tant que structure algébrique, commence avec des travaux russes, notamment ceux d'Anton Kazimirovich Suschkewitsch (en), qui détermina en 1928 la structure des semi-groupes simples finis^[3], puis ceux d'Evgenii Sergeevich Lyapin. Quelques années plus tard, des travaux fondateurs furent menés par David Rees, James Alexander Green, Alfred H. Clifford et Gordon Preston^[4]. Puis la théorie des demi-groupes finis s'est beaucoup développée, en liaison avec la théorie des automates, sous l'impulsion de Marcel-Paul Schützenberger et Samuel Eilenberg notamment. Elle est directement liée aux variétés de langages formels^[5].

Depuis 1970 paraît un périodique, Semigroup Forum, consacré à la théorie des demi-groupes.

Un élément neutre du demi-groupe S est un élément ${\displaystyle 1}$ de S tel que ${\displaystyle 1s=s1=s}$ pour tout ${\displaystyle s}$ dans ${\displaystyle S}$. Lorsque S a un élément neutre, on dit que c'est un monoïde ^[6],[7].

Il est d'usage de noter ${\displaystyle (S^{1},\cdot ')}$ le monoïde obtenu par l'ajout à ${\displaystyle S}$ d'un élément supplémentaire, qui déterminera ${\displaystyle \cdot '}$ comme l'unique prolongement de ${\displaystyle \cdot }$ à ${\displaystyle (S^{1})^{2}}$ qui fait de ce nouvel élément l'élément neutre de ${\displaystyle (S^{1},\cdot ');}$ ce dernier restant ${\displaystyle (S,\cdot )}$ s'il est déjà unifère. Formellement

${\displaystyle S^{1}={\begin{cases}S&{\text{si }}S\mathrm {~contient~un~{\acute {e}}l{\acute {e}}ment~neutre~;} \\S\cup \{1\}&{\text{sinon.}}\end{cases}}}$

Dans le deuxième cas, ${\displaystyle 1}$ est un objet quelconque qui ne figure pas dans ${\displaystyle S}$, et la loi ${\displaystyle \cdot }$ sur ${\displaystyle S}$ est étendue à ${\displaystyle S\cup \{1\}}$ en posant

${\displaystyle a\cdot '1=1\cdot 'a=a}$ pour tout ${\displaystyle a}$ dans ${\displaystyle S\cup \{1\}.}$

Lorsque le demi-groupe ${\displaystyle (S,\cdot )}$ est commutatif, le monoïde ${\displaystyle (S^{1},\cdot ')}$ l'est aussi. On définit alors son groupe symétrisé ou groupe de Grothendieck ${\displaystyle G(S^{1},\cdot ')}$. Si de plus ${\displaystyle (S,\cdot )}$ est simplifiable (c'est-à-dire si tous ses éléments sont réguliers) alors ${\displaystyle (S^{1},\cdot ')}$ l'est aussi, donc le morphisme canonique de ${\displaystyle (S,\cdot )}$ dans ${\displaystyle G(S^{1},\cdot ')}$ (via ${\displaystyle (S^{1},\cdot ')}$) est injectif.

L'élément absorbant, aussi appelé zéro d'un demi-groupe ${\displaystyle S}$ est un élément ${\displaystyle 0}$ tel que ${\displaystyle 0s=s0=0}$ pour tout ${\displaystyle s}$ dans ${\displaystyle S}$. Par exemple, le nombre 0 est un zéro des entiers naturels pour la multiplication. Si un demi-groupe possède un zéro, il est unique.

Soient ${\displaystyle (S,\cdot )}$ et ${\displaystyle (T,\star )}$ deux demi-groupes. Une application ${\displaystyle f:S\to T}$ est un morphisme de demi-groupes si ${\displaystyle f(s\cdot t)=f(s)\star f(t)}$ pour tous ${\displaystyle s,t\in S}$. Par exemple, l'application ${\displaystyle f:n\mapsto 2^{n}}$ est un morphisme du demi-groupe des entiers naturels munis de l’addition dans le demi-groupe des puissances entières de 2 munis de la multiplication.

Un sous-demi-groupe d'un demi-groupe ${\displaystyle S}$ est un sous-ensemble de ${\displaystyle S}$ fermé sous l'opération de ${\displaystyle S}$. Un sous-monoïde d'un monoïde ${\displaystyle M}$ est un sous-demi-groupe de ${\displaystyle M}$ qui contient l'élément neutre de ${\displaystyle M}$.

Ainsi l'ensemble ℕ des nombres naturels, muni de la multiplication, est un demi-groupe commutatif dont l'ensemble 2ℕ des nombres pairs est un sous-demi-groupe . ℕ est alors un monoïde avec élément neutre 1 alors que 2ℕ n'est qu'un demi-groupe.

Un sous-demi-groupe d'un monoïde ${\displaystyle M}$ peut être un monoïde sans être un sous-monoïde de ${\displaystyle M}$. Par exemple dans le monoïde multiplicatif ℕ ci-dessus, le sous-demi-groupe {0} est le monoïde trivial, mais n'est pas un sous-monoïde de ℕ, car il ne contient pas l'élément neutre de ℕ.

Il existe dans les demi-groupes une notion de pseudoinverse et une notion d'inverse, qui généralise celle d'élément symétrique dans les groupes :

${\displaystyle x}$ est un pseudoinverse^[8] de ${\displaystyle a}$ si ${\displaystyle axa=a}$.

${\displaystyle b}$ est un inverse de ${\displaystyle a}$ si ${\displaystyle aba=a}$ et ${\displaystyle bab=b}$.

Tout inverse est évidemment un pseudoinverse. Réciproquement, si ${\displaystyle x}$ est un pseudoinverse de ${\displaystyle a}$ alors^[9] ${\displaystyle b=xax}$ est un inverse de ${\displaystyle a}$, puisque ${\displaystyle aba=a(xax)a=(axa)(xa)=a(xa)=a}$ et ${\displaystyle bab=(xax)ab=x(axa)b=(xa)(xax)=x(axa)x=xax=b}$.

En algèbre linéaire, le pseudo-inverse d'une matrice est un inverse pour le semi-groupe multiplicatif des matrices.

Un demi-groupe régulier est un demi-groupe dans lequel tout élément admet au moins un pseudoinverse ou (ce qui, d'après ce qui précède, est équivalent) au moins un inverse.

Un demi-groupe inversif est un demi-groupe dans lequel tout élément admet un unique inverse^[10].

Une partie^[11] ${\displaystyle I}$ d'un demi-groupe ${\displaystyle S}$ est un idéal à gauche (à droite) si ${\displaystyle SI\subset I}$, ${\displaystyle IS\subset I}$. C'est un idéal (bilatère) s'il est à la fois un idéal à droite et à gauche. Pour tout élément ${\displaystyle a}$ de ${\displaystyle S}$, l'ensemble ${\displaystyle S^{1}a}$, ${\displaystyle aS^{1}}$, ${\displaystyle S^{1}aS^{1}}$ est l'idéal à gauche, à droite, bilatère engendré par ${\displaystyle a}$. Un idéal est propre s'il est non vide et distinct du demi-groupe tout entier.

Le zéro, s'il existe, est un idéal bilatère propre si ${\displaystyle S}$ ne se réduit pas à cet élément.

Le produit ${\displaystyle I_{1}I_{2}\cdots I_{n}}$ d'idéaux ${\displaystyle I_{1},I_{2},\ldots ,I_{n}}$ est un idéal contenu dans leur intersection. Il en résulte que si les idéaux ${\displaystyle I_{1},I_{2},\ldots ,I_{n}}$ ne sont pas vides, leur intersection ne l'est pas non plus.

Un idéal non vide ${\displaystyle I}$ est minimal s'il ne contient pas d'autre idéal non vide. Ainsi, un idéal minimal, vu comme demi-groupe, est un demi-groupe simple. Comme l'intersection de deux idéaux non vides est un idéal non vide, un demi-groupe possède au plus un seul idéal minimal. L'existence d'un idéal minimal est assurée dans le cas d'un demi-groupe fini (on prend simplement l'intersection de tous les idéaux non vides).

Si un demi-groupe ${\displaystyle S}$ possède un zéro ${\displaystyle 0}$, il est à lui tout seul l'idéal minimal de ${\displaystyle S}$. Un idéal ${\displaystyle I}$ de ${\displaystyle S}$ est ${\displaystyle 0}$-minimal s'il est non vide, différent de ${\displaystyle 0}$, et ne contient pas d'autre idéal non vide. Un idéal 0-minimal ${\displaystyle I}$, vu comme demi-groupe, est un demi-groupe 0-simple sauf si ${\displaystyle I^{2}=0}$.

Exemple

Le demi-groupe ${\displaystyle S=\{s,t,0\}}$ défini par ${\displaystyle xy=0}$ pour ${\displaystyle x,y\in S}$ possède deux idéaux 0-minimaux, à savoir ${\displaystyle \{s,0\}}$ et ${\displaystyle \{t,0\}}$.

Soit ${\displaystyle S}$ un demi-groupe et soit ${\displaystyle I}$ un idéal de ${\displaystyle S}$. Le quotient de Rees ${\displaystyle S/I}$ de ${\displaystyle S}$ par ${\displaystyle I}$ est le demi-groupe quotient de ${\displaystyle S}$ par la congruence de Rees ${\displaystyle {\mathcal {J}}}$, définie par

${\displaystyle x{\mathcal {J}}y\iff x=y{\text{ ou }}x,y\in I}$.

Si ${\displaystyle I}$ est vide, ${\displaystyle S/I=S}$. Si ${\displaystyle I=S}$, ${\displaystyle S/I}$ est un singleton. Si ${\displaystyle I\neq \emptyset ,S}$, on emploie la construction suivante^[12] : On dénote la classe de ${\displaystyle I}$ par ${\displaystyle 0}$, et on identifie les autres classes à leur unique élément. Alors ${\displaystyle S/I=(S\setminus I)\cup \{0\}}$, avec la multiplication ${\displaystyle *}$ définie comme suit : ${\displaystyle 0}$ est un zéro, et

${\displaystyle x*y={\begin{cases}0&{\text{si }}xy\in I\\xy&{\text{sinon}}.\end{cases}}}$

Le quotient de Rees est nommé ainsi d'après son concepteur, le mathématicien David Rees.

Exemple

Dans le monoïde libre ${\displaystyle A^{*}}$ engendré par un alphabet ${\displaystyle A}$ à deux lettres au moins, on considère l'idéal des mots contenant un mot carré, c'est-à-dire l'ensemble des mots de la forme ${\displaystyle xyyz}$, où ${\displaystyle x,y,z}$ sont des mots, et ${\displaystyle y}$ n'est pas le mot vide. Le quotient de Rees est composé des mots sans carré de ${\displaystyle A^{*}}$, et d'un zéro. Si ${\displaystyle A}$ est composé de deux lettres ${\displaystyle a}$ et ${\displaystyle b}$, le quotient de Rees est fini et formé de ${\displaystyle a,b,ab,ba,aba,bab}$, du mot vide et du zéro. Si ${\displaystyle A}$ a plus de deux lettres, ce quotient de Rees est infini.

• Un demi-groupe ${\displaystyle S}$ est simple si ses seuls idéaux sont ${\displaystyle \emptyset }$ et S.
• Un demi-groupe ${\displaystyle S}$ est 0-simple s'il possède un zéro noté ${\displaystyle 0}$, si ${\displaystyle S^{2}\neq \{0\}}$ et si ${\displaystyle \emptyset ,0}$ et ${\displaystyle S}$ sont ses seuls idéaux. Comme ${\displaystyle S^{2}}$ est un idéal non vide, la seule possibilité qui reste est ${\displaystyle S^{2}=S}$. Un demi-groupe 0-simple ne se réduit donc pas à son zéro.

Exemples

Le demi-groupe bicyclique est simple. Tout groupe est simple en tant que demi-groupe.

Un 0-groupe est un demi-groupe de la forme ${\displaystyle G\cup \{0\}}$, où ${\displaystyle G}$ est un groupe et où ${\displaystyle 0}$ est un élément qui joue le rôle d'un zéro et qui n'est pas dans ${\displaystyle G}$. La loi de ${\displaystyle G}$ est donc étendue à ${\displaystyle G\cup \{0\}}$ par ${\displaystyle 0s=s0=0}$ pour ${\displaystyle s}$ dans ${\displaystyle G\cup \{0\}}$. On écrit en général ${\displaystyle G^{0}}$ pour ${\displaystyle G\cup \{0\}}$. Plus généralement, si ${\displaystyle S}$ est un demi-groupe non vide, on note ${\displaystyle S^{0}}$ le demi-groupe avec zéro obtenu en ajoutant un zéro à ${\displaystyle S}$. Un 0-groupe est un demi-groupe 0-simple.

• Cet article est partiellement ou en totalité issu de l'article intitulé « Semi-groupe » (voir la liste des auteurs).

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Semigroup » (voir la liste des auteurs).

Histoire des demi-groupes

• Gordon B. Preston, « Personal reminiscences of the early history of semigroups », sur gap-system.org, 1990.
• Paul Dubreil, « Apparition et premiers développements de la théorie des demi-groupes en France », Cahiers du séminaire d'histoire des mathématiques, vol. 2,‎ 1981, p. 59-65 (MR 618658, zbMATH 0465.01005, lire en ligne)
• (en) Christopher Hollings, « The early development of the algebraic theory of semigroups », Arch. Hist. Exact Sci. (2009), vol. 63,‎ 2009, p. 497–536 (DOI 10.1007/s00407-009-0044-3)

Ouvrages historiques

• (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 978-0-8218-0272-4, MR 0132791, lire en ligne)
• (en) Alfred H. Clifford et Gordon B. Preston, The Algebraic Theory of Semigroups, vol. II, Providence, R.I., American Mathematical Society, coll. « Mathematical Surveys » (n^o 7-Part II), 1967, xv+350 (ISBN 978-0-8218-0272-4, MR 0218472, lire en ligne)
• (en) Evgueni S. Lyapine, Semigroups, American Mathematical Society, coll. « Translations of Mathematical Monographs » (n^o 3), 1963
  Deux autres éditions suivent, une première en 1968 avec un chapitre additionnel, et une deuxième, en 1974, avec un autre chapitre en plus.

Ouvrages classiques

• (en) John M. Howie, Fundamentals of Semigroup Theory, Oxford, Oxford University Press, coll. « London Mathematical Society Monographs. New Series » (n^o 12), 1995, x+351 (ISBN 0-19-851194-9, MR 1455373)
• (en) Pierre Antoine Grillet, Semigroups : An Introduction to the Structure Theory, Marcel Dekker, coll. « Monographs and Textbooks in Pure and Applied Mathematics » (n^o 193), 1995, xii+398 (ISBN 0-8247-9662-4, MR 2000g:20001)
• Gérard Lallement, Semigroups and Combinatorial Applications, John Wiley & Sons, coll. « Pure and Applied Mathematics », 1979, xi+376 (ISBN 0-471-04379-6, MR 81j:20082)

• (en) Jean-Éric Pin, Varieties of Formal Languages, Plenum Press, 1986

Ouvrages récents

• (en) Mati Kilp, Ulrich Knauer et Alexander V. Mikhalev, Monoids, Acts and Categories : With Applications to Wreath Products and Graphs, Berlin/New York, Walter de Gruyter, coll. « De Gruyter Expositions in Mathematics » (n^o 29), 2000, xviii+529 (ISBN 3-11-015248-7)
• (en) Attila Nagy, Special Classes of Semigroups, Kluwer Academic Publishers, coll. « Advances in Mathematics (Dordrecht) » (n^o 1), 2001, viii+269 (ISBN 0-7923-6890-8, MR 2002d:20091, présentation en ligne)

• Classes particulières de demi-groupes (en)
• Théorème des variétés d'Eilenberg
• Demi-groupe 3x+1
• Demi-groupe automatique
• Demi-groupe numérique

• Portail de l’algèbre