Monoïde

Différentes structures algébriques obtenues à partir de la structure de magma en combinant les axiomes d'associativité, identité ou de divisibilité.

En mathématiques, un monoïde est une structure algébrique utilisée en algèbre générale, définie comme un ensemble muni d'une loi de composition interne associative et d'un élément neutre. Autrement dit, c'est un magma associatif et unifère, c'est-à-dire un demi-groupe unifère.

Préambule

Il arrive parfois qu'une structure composée d'un ensemble et d'une unique opération soit relativement pauvre en éléments inversibles, par exemple un anneau où l'on considère uniquement la multiplication. Une telle structure est appelée monoïde. L'apparente pauvreté de l'opération donne naissance à une théorie spécifique, comme les relations de Green pour les monoïdes ou les idéaux dans les anneaux même non commutatifs. Une autre technique, lorsque l'on est en présence d'une opération simplifiable, consiste à « enrichir » le monoïde pour en faire un groupe.

Parfois au contraire, la structure de monoïde est parfaitement adéquate. Tel est le cas pour l'algèbre des polynômes en plusieurs indéterminées : on la construit comme l'algèbre d'un monoïde particulier, engendré par un ensemble d'indices.

Définition

Un monoïde est un magma unifère associatif.

Formellement, (E,∗,e) est un monoïde lorsque, pour tous éléments x, y et z de E :

Un monoïde E est dit simplifiable à gauche, ou encore régulier à gauche, (respectivement à droite) si

∀(a,b,c)∈E3a∗b=a∗c (respectivement b∗a=c∗a) ⇒b=c

Un monoïde E est dit commutatif si ses éléments sont permutables, c'est-à-dire si :

∀(x,y)∈E2x∗y=y∗x

Composé d'une séquence (finie) d'éléments

Soit E un monoïde. Notons sa loi de composition sous forme multiplicative, c'est-à-dire que nous écrirons xy pour désigner le composé noté x∗y plus haut. L'élément neutre est alors désigné par 1.

On peut définir par récurrence sur n le produit x1⋯xn d'un n-uplet d'éléments de E par :

En étendant cette définition au composé (« produit » dans notre notation) ∏i∈Ixi d'une séquence d'éléments de E — c'est-à-dire d'une famille (xi)i∈I indexée par un ensemble fini totalement ordonné —, on démontre :

Un corollaire est que pour tout (n + 1)-uplet (x1,…,xn+1) d'éléments de E,

x1⋯xn+1=x1(x2⋯xn+1)(2).

Cette formule (2), jointe à la condition (0) ci-dessus, est l'autre définition courante de x1⋯xn par récurrence sur n. Le corollaire permet de prouver l'équivalence de ces deux définitions, par récurrence sur le nombre de facteurs.

Sous-monoïde

Un sous-monoïde d'un monoïde (E,∗,e) est un sous-ensemble F de E vérifiant :

Toute intersection de sous-monoïdes est un sous-monoïde.

Un sous-demi-groupe d'un monoïde M peut être un monoïde sans être un sous-monoïde de M. Par exemple, si M est le monoïde formé par l'ensemble ℤ/6ℤ muni de sa multiplication, les classes résiduelles des nombres pairs forment un sous-demi-groupe D de M et l'on vérifie facilement que la classe résiduelle de 4 est élément neutre de ce sous-demi-groupe. Pourtant, D n'est pas un sous-monoïde de M, car l'élément neutre de M (la classe résiduelle de 1) n'appartient pas à D.

Famille génératrice d'un sous-monoïde

Soit P une partie d'un monoïde (E,∗,e). On appelle sous-monoïde engendré par P (noté P∗) l'intersection des sous-monoïdes de E contenant P. C'est donc le plus petit sous-monoïde de E contenant P. Il peut être décrit par :

P∗={x∈E∣∃n∈ℕ,∃(a1,⋯,an)∈Pn,x=a1∗⋯∗an}

(l'élément e fait bien partie de cet ensemble : c'est le produit vide, correspondant à n = 0,,).

On dit alors que P est une famille génératrice de P∗.

On peut toujours trouver une famille génératrice à tout monoïde, la plus triviale étant lui-même.

Monoïde libre

Un monoïde est dit libre s'il vérifie la propriété universelle suivante :

Définition — Un monoïde M est dit libre s'il existe un ensemble A et une fonction i:A→M telle que pour tout monoïde N et toute fonction f:A→N, il existe un unique morphisme de monoïdes φ:M→N tel que f=φ∘i. Dans ce cas, on dit que M est le monoïde libre sur A.

Cela correspond à la définition d'un objet libre dans la catégorie des monoïdes et des morphismes de monoïdes.

Les monoïdes libres sur un ensemble A sont exactement les monoïdes isomorphes à A∗, où A∗ est le monoïde formé par les suites finies d'éléments de A, appelées mots, muni de l'opération de concaténation. L'élément neutre est le mot vide, noté ε. Dans ce cas, φ est défini par φ(a1,…an)=f(a1)×⋯×f(an), et i:A→A∗ est la fonction qui envoie a∈A sur la suite finie composée d'un seul élément, a. Dans ce contexte, A est souvent appelé un alphabet.

Dans un monoïde libre, l'élément neutre est le seul élément symétrisable. De plus, étant donné deux monoïdes libres M et N, isomorphes respectivement à A∗ et B∗, M est isomorphe à N si et seulement si A et B sont en bijection.

Monoïde commutatif libre

Un monoïde commutatif (c'est-à-dire, un monoïde dont la loi de composition est commutative) est dit libre s'il est l'objet libre dans la catégorie des monoïdes commutatifs et des morphismes de monoïdes, ou encore s'il vérifie la propriété universelle du monoïde libre, où le mot « monoïde » est remplacé par « monoïde libre », c'est-à-dire :

Définition — Un monoïde commutatif M est dit libre s'il existe un ensemble A et une fonction i:A→M telle que pour tout monoïde commutatif N et toute fonction f:A→N, il existe un unique morphisme de monoïdes φ:M→N tel que f=φ∘i. Dans ce cas, on dit que M est le monoïde commutatif libre sur A.

Les monoïdes commutatifs libres peuvent être construits de plusieurs façons équivalentes :

Exemples

Morphisme de monoïdes

Soient (E,∗,e) et (F,⋆,f) deux monoïdes. On appelle morphisme de (E,∗,e) vers (F,⋆,f) toute application φ de E vers F telle que

La première propriété est celle de morphisme de magmas.

Produit direct de monoïdes

∀(x,y),(x′,y′)∈(E×F)2, (x,y)∧(x′,y′)=(x∗x′,y⋆y′).
C'est un monoïde de neutre (e,f).
(xi)i∈I∗(yi)i∈I=(xi∗iyi)i∈I..

Symétrique d'un élément

Symétrisation

On généralise la construction des entiers relatifs à partir des entiers naturels, en associant canoniquement à tout monoïde commutatif M = (S, +, 0) un groupe abélien G(M), appelé son groupe de Grothendieck, muni d'un morphisme de monoïdes de M dans G(M).

Le procédé de construction est appelé la symétrisation du monoïde. On considère pour cela la relation d'équivalence ∼ sur S × S définie par :

(m,n)∼(p,q)⇔∃k∈Sm+q+k=p+n+k.

Le groupe G(M) a pour éléments les classes d'équivalence de ∼ et le morphisme naturel de M dans G(M) associe à tout élément x de S la classe de (x, 0). Ce morphisme est injectif si et seulement si M est simplifiable ; dans ce cas, la relation ∼ peut être décrite plus simplement :

(m,n)∼(p,q)⇔m+q=p+n.

Applications

Le monoïde est un cadre propice pour définir les itérés d'un élément.

En informatique théorique, les monoïdes et plus particulièrement le monoïde libre sont parmi les structures les plus utilisées, notamment dans la théorie des codes et dans la théorie des langages.

Le terme « monoïde » a fait son entrée dans l'art contemporain dans la décennie 1970 avec le peintre Jean-Claude Bédard qui s'en justifie dans son livre Pour un art schématique : étude d'un monoïde graphique, Éditions de Beaune et Goutal-Darley, 1978.

Voir aussi

Articles connexes

Présentation d'un monoïde (en)