Relations de Green

En mathématiques, les relations de Green sont cinq relations d'équivalence qui décrivent les éléments d'un demi-groupe par les idéaux principaux qu’ils engendrent. Les relations sont nommées d'après James Alexander Green, qui les a introduites dans un article paru en 1951. Les relations sont fondamentales pour comprendre la structure d'un demi-groupe : ainsi, pour John M. Howie, un théoricien bien connu des demi-groupes, ces relations sont « si omniprésentes que, lorsque l'on rencontre un nouveau demi-groupe, presque la première question que l'on pose est : « à quoi ressemblent ses relations de Green ? » » (Howie 2002). Les relations existent bien sûr aussi dans un groupe, mais ne nous apprennent pas grand-chose dans ce cas puisque la multiplication est toujours inversible dans un groupe (de manière analogue, les idéaux ont une structure moins riche dans un corps que dans un anneau).

Idéaux d'un demi-groupe

Pour un demi-groupe ${\displaystyle S}$, on définit ${\displaystyle S^{1}}$ comme étant égal à ${\displaystyle S}$ si ${\displaystyle S}$ est un monoïde, sinon égal à ${\displaystyle S\cup \{1\}}$, où ${\displaystyle 1}$ est un élément neutre ajouté, donc vérifiant ${\displaystyle a1=1a=a}$ pour tout ${\displaystyle a}$ de ${\displaystyle S}$. Il est commode d'utiliser la notation ${\displaystyle XY}$ pour dénoter le produit des éléments de ${\displaystyle X}$ par les éléments de ${\displaystyle Y}$, soit ${\displaystyle XY=\{xy\mid x\in X,y\in Y\}}$.

Les idéaux engendrés par un élément ${\displaystyle a}$ de ${\displaystyle S}$ sont les suivants :

• L'idéal à gauche engendré par ${\displaystyle a}$ est : ${\displaystyle S^{1}a=\{sa\mid s\in S^{1}\}=Sa\cup \{a\}}$.
• L'idéal à droite engendré par ${\displaystyle a}$ est : ${\displaystyle aS^{1}=\{as\mid s\in S^{1}\}=aS\cup \{a\}}$
• L'idéal bilatère engendré par ${\displaystyle a}$ est : ${\displaystyle S^{1}aS^{1}=SaS\cup aS\cup Sa\cup \{a\}}$.

Par définition, ce sont des idéaux principaux. Si l'on représente la table de multiplication d'un demi-groupe par une matrice, l'idéal à gauche (respectivement à droite) engendré par un élément ${\displaystyle a}$ est constitué des éléments figurant dans la colonne (respectivement dans la ligne) d'indice ${\displaystyle a}$.

Les relations ℒ, ℛ et 𝒥

Les trois premières relations de Green sont les relations d'équivalence entre éléments d'un demi-groupe définies par le fait que les éléments engendrent les mêmes idéaux. Soient ${\displaystyle a}$ et ${\displaystyle b}$ deux éléments de ${\displaystyle S}$ ; on définit :

• ${\displaystyle a{\mathcal {L}}b}$ si et seulement si ${\displaystyle a}$ et ${\displaystyle b}$ engendrent le même idéal à gauche, c'est-à-dire si et seulement si ${\displaystyle S^{1}a=S^{1}b}$ ;
• ${\displaystyle a{\mathcal {R}}b}$ si et seulement si ${\displaystyle a}$ et ${\displaystyle b}$ engendrent le même idéal à droite, c'est-à-dire si et seulement si ${\displaystyle aS^{1}=bS^{1}}$ ;
• ${\displaystyle a{\mathcal {J}}b}$ si et seulement si ${\displaystyle a}$ et ${\displaystyle b}$ engendrent le même idéal bilatère, c'est-à-dire si et seulement si ${\displaystyle S^{1}aS^{1}=S^{1}bS^{1}}$.

On note ${\displaystyle L(a)}$, ${\displaystyle R(a)}$, et ${\displaystyle J(a)}$ la classe d'équivalence de ${\displaystyle a}$ dans la relation ${\displaystyle {\mathcal {L}}}$, ${\displaystyle {\mathcal {R}}}$, et ${\displaystyle {\mathcal {J}}}$ respectivement. Elles sont appelées la ${\displaystyle {\mathcal {L}}}$-classe, ${\displaystyle {\mathcal {R}}}$-classe, et ${\displaystyle {\mathcal {J}}}$-classe de l'élément ${\displaystyle a}$[1]. Si ${\displaystyle S}$ est commutatif, ces trois relations coïncident.

Les relations ℋ et 𝒟

Les relations ${\displaystyle {\mathcal {H}}}$ et ${\displaystyle {\mathcal {D}}}$ sont définies à partir de ${\displaystyle {\mathcal {L}}}$ et ${\displaystyle {\mathcal {R}}}$, la première comme l'intersection de ${\displaystyle {\mathcal {L}}}$ et ${\displaystyle {\mathcal {R}}}$, la deuxième comme leur borne supérieure. Plus précisément, on a :

• ${\displaystyle {\mathcal {H}}={\mathcal {L}}\cap {\mathcal {R}}}$, donc ${\displaystyle a{\mathcal {H}}b}$ si et seulement si ${\displaystyle a{\mathcal {L}}b}$ et ${\displaystyle a{\mathcal {R}}b}$;
• ${\displaystyle {\mathcal {D}}={\mathcal {L}}\lor {\mathcal {R}}}$, donc ${\displaystyle {\mathcal {D}}}$ est la plus petite relation d'équivalence contenant ${\displaystyle {\mathcal {L}}}$ et ${\displaystyle {\mathcal {R}}}$.

La ${\displaystyle {\mathcal {H}}}$-classe de ${\displaystyle a}$ est notée ${\displaystyle H(a)}$, et la ${\displaystyle {\mathcal {D}}}$-classe de ${\displaystyle a}$ est notée ${\displaystyle D(a)}$. On a donc ${\displaystyle H(a)=L(a)\cap R(a)}$. Plus généralement, l'intersection d'une ${\displaystyle {\mathcal {L}}}$-classe et d'une ${\displaystyle {\mathcal {R}}}$-classe est soit vide, soit une ${\displaystyle {\mathcal {H}}}$-classe.

La relation ${\displaystyle {\mathcal {D}}}$ admet une expression plus simple. On a en fait :

${\displaystyle {\mathcal {D}}={\mathcal {L}}{\mathcal {R}}={\mathcal {R}}{\mathcal {L}}}$

Ceci est une conséquence de la commutation de ${\displaystyle {\mathcal {L}}}$ et ${\displaystyle {\mathcal {R}}}$. En effet, il est clair que ${\displaystyle {\mathcal {L}}}$ et ${\displaystyle {\mathcal {R}}}$ sont contenues dans ${\displaystyle {\mathcal {L}}{\mathcal {R}}}$; il est clair aussi que ${\displaystyle {\mathcal {L}}{\mathcal {R}}}$ est réflexive et symétrique. Pour prouver que la relation est transitive, on calcule simplement :

${\displaystyle ({\mathcal {L}}{\mathcal {R}})({\mathcal {L}}{\mathcal {R}})={\mathcal {L}}({\mathcal {R}}{\mathcal {L}}){\mathcal {R}}={\mathcal {L}}({\mathcal {L}}{\mathcal {R}}){\mathcal {R}}=({\mathcal {L}}{\mathcal {L}})({\mathcal {R}}{\mathcal {R}})={\mathcal {L}}{\mathcal {R}}}$.

Dans un demi-groupe fini, les relations ${\displaystyle {\mathcal {D}}}$ et ${\displaystyle {\mathcal {J}}}$ coïncident[2].

Dans un groupe, les cinq relations coïncident, et le groupe est une seule ${\displaystyle {\mathcal {H}}}$-classe. Le cas opposé est celui où les ${\displaystyle {\mathcal {H}}}$-classes sont réduites à un seul élément. Dans le cas des monoïdes finis, ce sont les monoïdes apériodiques qui, par le théorème de Schützenberger caractérisent les langages rationnels sans étoile. Un exemple infini est le monoïde bicyclique qui est le monoïde syntaxique du langage de Dyck sur une paire de parenthèses. Un demi-groupe qui ne possède qu'une seule ${\displaystyle {\mathcal {D}}}$-classe est appelé bisimple. Le monoïde bicyclique est bisimple.

Un exemple

Le demi-groupe de transformation ${\displaystyle T_{3}}$ (« full transformation semigroup » en anglais) consiste en toutes les applications de l'ensemble ${\displaystyle \{1,2,3\}}$ dans lui-même. Il est composé de 27 éléments. On représente la fonction qui envoie ${\displaystyle 1}$ sur ${\displaystyle a}$, ${\displaystyle 2}$ sur ${\displaystyle b}$, et ${\displaystyle 3}$ sur ${\displaystyle c}$ par ${\displaystyle abc}$. L'élément neutre est ${\displaystyle 123}$. Il y a 3 ${\displaystyle {\mathcal {D}}}$-classes. Le produit est la composition, donnée par ${\displaystyle fg=g\circ f}$. La structure en boîte à œufs (voir ci-dessous l'explication) est la suivante :

123, 231, 312, 132, 321, 213
	122, 211 133, 311 233, 322 212, 121 313, 131 323, 232 221, 112 331, 113 332, 223
		111 222 333

Les éléments en gras sont des idempotents. Deux éléments sont dans la même ${\displaystyle {\mathcal {L}}}$-classe s'ils ont même image, deux éléments sont dans la même ${\displaystyle {\mathcal {R}}}$-classe s'ils ont même équivalence nucléaire (s'ils induisent la même partition sur l'ensemble de départ). Par conséquent, deux éléments sont dans la même ${\displaystyle {\mathcal {D}}}$-classe si et seulement si leurs images ont même taille.

Toute ${\displaystyle {\mathcal {H}}}$-classe qui contient un idempotent est un groupe. La première ${\displaystyle {\mathcal {D}}}$-classe est le groupe symétrique ${\displaystyle {\mathfrak {S}}_{3}}$. Il y a six sous-groupes d'ordre 2. Trois de ${\displaystyle {\mathcal {H}}}$-classes de la ${\displaystyle {\mathcal {D}}}$-classe intermédiaire ne sont pas des groupes.

L'élément neutre d'une ${\displaystyle {\mathcal {H}}}$-classe qui est groupe est un idempotent, mais ce n'est pas l'élément neutre de ${\displaystyle S}$ sauf pour ce que l'on appelle le groupe des unités[3], c'est-à-dire la ${\displaystyle {\mathcal {H}}}$-classe ${\displaystyle H(1)}$ de l'élément neutre de ${\displaystyle S}$. La dénomination groupe des unités du monoïde est en analogie avec le groupe des unités d'un anneau. Par exemple, dans le monoïde des transformations ${\displaystyle T_{n}}$ de ${\displaystyle n}$ éléments (ici ${\displaystyle n=3}$), le groupe des unités est le groupe symétrique ${\displaystyle {\mathfrak {S}}_{n}}$ sur ${\displaystyle n}$ éléments.

Structure en « boîte à œufs »

Bijections entre les classes de Green : Les ${\displaystyle {\mathcal {l}}}$-classes (colonnes) sont en bijection, et les bijections respectent les ${\displaystyle {\mathcal {R}}}$-classes (lignes), de sortent que les ${\displaystyle {\mathcal {H}}}$-classes (œufs) sont en bijection.

La forme d'une ${\displaystyle {\mathcal {D}}}$-classe est décrite globalement par la proposition suivante :

Lemme de Green — Soient ${\displaystyle m}$ et ${\displaystyle m'}$ deux éléments ${\displaystyle {\mathcal {R}}}$-équivalents, et soient ${\displaystyle u}$ et ${\displaystyle u'}$ tels que ${\displaystyle m'=mu}$ et ${\displaystyle m=m'u'}$. Les applications ${\displaystyle q\mapsto qu}$ et ${\displaystyle q'\mapsto q'u'}$ sont des bijections de ${\displaystyle L(m)}$ sur ${\displaystyle L(m')}$, réciproques l'une de l'autre, et qui envoient une ${\displaystyle {\mathcal {R}}}$-classe sur elle-même.

Revenons sur l'exemple de ${\displaystyle T_{3}}$ : en prenant ${\displaystyle u=233}$ et ${\displaystyle u'=212}$, on réalise des bijections entre la ${\displaystyle {\mathcal {H}}}$-classe formée de 122 et 211, et de la ${\displaystyle {\mathcal {H}}}$-classe composée de 233 et 322. Ces bijections échangent également les ${\displaystyle {\mathcal {H}}}$-classes des autres lignes.

On peut donc voir une ${\displaystyle {\mathcal {D}}}$-classe comme une union de ${\displaystyle {\mathcal {L}}}$-classes, ou comme une union de ${\displaystyle {\mathcal {R}}}$-classes ou encore comme une union de ${\displaystyle {\mathcal {H}}}$-classes. (Clifford et Preston 1961) suggèrent de voir une ${\displaystyle {\mathcal {D}}}$-classe comme une boîte à œufs (« the egg-box structure ») : Les œufs sont les ${\displaystyle {\mathcal {H}}}$-classes ; elles sont groupées en un tableau rectangulaire. Chaque ligne représente une ${\displaystyle {\mathcal {R}}}$-classe, chaque colonne une ${\displaystyle {\mathcal {L}}}$-classe. De plus, il est de tradition de structurer l'ensemble des ${\displaystyle {\mathcal {D}}}$-classes en un diagramme, où les produits de deux éléments d'une ${\displaystyle {\mathcal {D}}}$-classe ne peuvent se trouver que dans des ${\displaystyle {\mathcal {D}}}$-classes situées plus bas dans le diagramme.

Par les bijections décrites plus haut, les ${\displaystyle {\mathcal {H}}}$-classes d'une ${\displaystyle {\mathcal {D}}}$-classe ont toute même nombre d'éléments. Dans l'exemple ci-dessus, les ${\displaystyle {\mathcal {H}}}$-classes ont respectivement 6, 2 et 1 éléments. Les ${\displaystyle {\mathcal {H}}}$-classes qui sont des groupes sont isomorphes, et isomorphes au groupe de Schützenberger de la ${\displaystyle {\mathcal {D}}}$-classe.

Localisation du produit de deux éléments d'une même ${\displaystyle {\mathcal {D}}}$-classe.

Le calcul, à l'intérieur d'une ${\displaystyle {\mathcal {D}}}$-classe, est décrit explicitement dans la proposition suivante :

Théorème de localisation — Soient ${\displaystyle s}$ et ${\displaystyle t}$ deux éléments d'une ${\displaystyle {\mathcal {D}}}$-classe. On a ${\displaystyle st\in R(s)\cap L(t)}$ si et seulement si la ${\displaystyle {\mathcal {H}}}$-classe ${\displaystyle L(s)\cap R(t)}$ contient un idempotent.

Ainsi, le produit ${\displaystyle st}$ reste dans la boîte à œufs pourvu que dans le coin opposé du carré se trouve un idempotent. Revenons à l'exemple de ${\displaystyle T_{3}}$. Le produit de 122 et de 223 est égal à 222, donc n'est pas dans la même ${\displaystyle {\mathcal {D}}}$-classe; le théorème de localisation dit que c'est ainsi parce que la ${\displaystyle {\mathcal {H}}}$-classe composée de 221 et 112 ne contient pas d'idempotent.

Les résultats précédents ont de plusieurs conséquences :

Proposition — 

1. Si une ${\displaystyle {\mathcal {D}}}$-classe ${\displaystyle D}$ contient un idempotent, alors chaque ${\displaystyle {\mathcal {R}}}$-classe de ${\displaystyle D}$ et chaque ${\displaystyle {\mathcal {L}}}$-classe de ${\displaystyle D}$ contient un idempotent.
2. Une ${\displaystyle {\mathcal {H}}}$-classe ${\displaystyle H}$ est un groupe si et seulement s'il existe deux éléments ${\displaystyle s,t\in H}$ tels que ${\displaystyle st\in H}$.
3. Deux sous-groupes maximaux d'une même ${\displaystyle {\mathcal {D}}}$-classe sont isomorphes.

Soient ${\displaystyle a}$ et ${\displaystyle b}$ deux éléments d'un demi-groupe ${\displaystyle S}$. Ils sont l'inverse l'un de l'autre si ${\displaystyle aba=a}$ et ${\displaystyle bab=b}$. Un élément ${\displaystyle a}$ est régulier s'il possède au moins un inverse. Un idempotent est toujours régulier, il est l'inverse de lui-même. Une ${\displaystyle {\mathcal {D}}}$-classe ${\displaystyle D}$ est régulière si tous ses éléments sont réguliers. La proposition ci-dessus admet comme conséquence :

Soit ${\displaystyle D}$ une ${\displaystyle {\mathcal {D}}}$-classe. Les conditions suivantes sont équivalentes :

1. ${\displaystyle D}$ contient un idempotent;
2. ${\displaystyle D}$ contient un élément régulier;
3. ${\displaystyle D}$ est une ${\displaystyle {\mathcal {D}}}$-classe régulière.

Extensions et applications

Les relations de Green ont aussi été définies pour les demi-anneaux[4] et pour les anneaux[5]. Certaines des propriétés associées aux relations de Green dans les demi-groupes se transposent dans ces cas, mais pas toutes. Les relations de Green ont aussi été étendues pour couvrir le cas des idéaux relatifs qui sont des idéaux par rapport à un sous-demi-groupe[6].

Les applications les plus nombreuses des relations de Green se rencontrent dans l'étude des monoïdes syntaxiques des langages rationnels. Les propriétés spécifiques de ces monoïdes syntaxiques traduisent les propriétés combinatoires des langages correspondants[7]. Un exemple célèbre est le théorème de Schützenberger qui caractérise les langages rationnels « sans étoile » par la propriété que leur monoïde syntaxique n'a que des « sous-groupes triviaux », en d'autres termes, les ${\displaystyle {\mathcal {H}}}$-classes qui sont des groupes sont des singletons. Un autre résultat de cette nature est dû à Imre Simon[8] : un langage rationnel est testable par morceaux[9] si et seulement si son monoïde syntaxique est ${\displaystyle {\mathcal {J}}}$-trivial, c'est-à-dire sa relation ${\displaystyle {\mathcal {J}}}$ est l'identité. Plus généralement, il y a une correspondance entre variétés de langages rationnels et variétés de monoïdes qui a été exposé de manière systématique pour la première fois par Samuel Eilenberg dans le volume B de son traité[10] : une variété de monoïdes finis est une classe de monoïdes fermée par passage au sous-monoïde, au quotient, et par produit direct fini. C'est le théorème des variétés d'Eilenberg[11]. Une variété de langages rationnels est une classe de langages qui est fermée pour les opérations booléennes, par quotients gauche et droit, et par morphisme inverse. Il y a une bijection entre variétés de monoïdes finis et variétés de langages rationnels. Les langages rationnels correspondent à la variété de tous les monoïdes finis, les langages sans étoiles aux monoïdes apériodiques, les langages testables par morceaux aux monoïdes ${\displaystyle {\mathcal {J}}}$-triviaux, etc.

Notes et références

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

Notes

1. Green utilisait les lettres fraktur ${\displaystyle {\mathfrak {l}}}$, ${\displaystyle {\mathfrak {r}}}$ et ${\displaystyle {\mathfrak {f}}}$ pour ces relations, se rapprochant ainsi de la notation des idéaux dans les anneaux employée par Emmy Noether notamment. Il écrivait ${\displaystyle a\equiv b({\mathfrak {l}})}$ pour ${\displaystyle a{\mathcal {L}}b}$, etc.
2. Voir par exemple Gomes, Pin et Silva 2002, p. 94 sur Google Livres ou Pin 2012.
3. Howie 1995, p. 171.
4. (en) Mireille P. Grillet, « Green's relations in a semiring », Port. Math., vol. 29, n^o 4,‎ 1970, p. 181-195 (lire en ligne).
5. (en) Petraq Petro, « Green's relations and minimal quasi-ideals in rings », Comm. Algebra, vol. 30, n^o 10,‎ 2002, p. 4677-4686 (DOI 10.1081/AGB-120014661).
6. (en) A. D. Wallace (en), « Relative ideals in semigroups. II. The relations of Green », Acta Math. Acad. Sci. Hungar., vol. 14, n^os 1-2,‎ 1963, p. 137-148 (DOI 10.1007/BF01901936).
7. Almeida 1994 et Gomes, Pin et Silva 2002.
8. (en) Imre Simon, « Piecewise testable events », dans H. Brakhage, Proceedings 2nd GI Conference, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 33), 1975 (DOI 10.1007/3-540-07407-4_23), p. 214-222.
9. Un langage est testable par morceaux s'il appartient à la fermeture booléenne de langages de la forme ${\displaystyle A^{*}a_{1}A^{*}a_{2}\cdots a_{n}A^{*}}$, où ${\displaystyle A}$ est un alphabet et les ${\displaystyle a_{i}}$ sont des lettres.
10. (en) Samuel Eilenberg, Automata, Languages and Machines, Vol. B, Academic Press, coll. « Pure and Applied Mathematics » (n^o 59), 1976, xiii+387 (MR 0530383).
11. Ne pas confondre avec les variétés au sens de Garrett Birkhoff où le produit direct est quelconque.

Bibliographie

Textes historiques

• (en) Alfred H. Clifford et Gordon B. Preston, The Algebraic Theory of Semigroups, vol. I, Providence, R.I., AMS, coll. « Mathematical Surveys » (n^o 7), 1961, xv+224 (MR 0132791)
  Les relations de Green sont introduites au chapitre 2.
• (en) Alfred H. Clifford et Gordon B. Preston, The Algebraic Theory of Semigroups, vol. II, Providence, R.I., AMS, coll. « Mathematical Surveys » (n^o 7), 1967, xv+350 (MR 0218472)
• (en) James A. Green, « On the structure of semigroups », Annals of Mathematics, 2^e série, vol. 54,‎ 1951, p. 163-172 (DOI 10.2307/1969317, JSTOR 1969317)

Textes plus récents

• (en) Jorge Almeida (trad. du portugais), Finite Semigroups and Universal Algebra, Singapore/New Jersey/London etc., World Scientific, coll. « Series in Algebra » (n^o 3), 1994, xviii+511 (ISBN 981-02-1895-8, MR 96b:20069, lire en ligne)
• (en) Gracinda M. S. Gomes, Jean-Éric Pin et Pedro V. Silva (éditeurs), Semigroups, Algorithms, Automata, and Languages : Coimbra, Portugal, May-July 2001, World Scientific, 2002 (ISBN 978-981-238-099-9, présentation en ligne)
• (en) John M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, coll. « London Mathematical Society Monographs. New Series » (n^o 12), 1995, x+351 (ISBN 978-0-19-851194-6, MR 1455373)
  Ceci est une version révisée et augmentée de : John M. Howie, An Introduction to Semigroup Theory, Academic Press, coll. « London Mathematical Society Monographs » (n^o 7), 1976, x+272 (ISBN 0-12-356950-8, MR 0466355).
• (en) J. M. Howie, « Semigroups, past, present and future », dans Proceedings of the International Conference on Algebra and its Applications (ICAA 2002), Bangkok, Chulalongkorn University, 2002 (MR 2004i:20123), p. 6-20
• (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), p. 95-124

Voir aussi

Article connexe

Groupe de Schützenberger

Lien externe

Jean-Éric Pin, « Semigroupe 2.01 : a software for computing finite semigroups » — Un logiciel de calcul de demi-groupes, notamment la structure des relations de Green.