Voir la source de Monoïde

En [[mathématiques]], un '''monoïde''' est une des [[Structure algébrique|structures algébriques]] utilisées en [[algèbre générale]]. C'est un [[ensemble]] muni d'une [[loi de composition interne]] [[associativité|associative]] et d'un [[élément neutre]]. Autrement dit, c'est un [[Magma (algèbre)|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 unitaire|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éal|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 à [[Symétrisation|« enrichir » le monoïde]] pour en faire un [[groupe (mathématiques)|groupe]].

Parfois au contraire, la structure de monoïde est parfaitement adéquate. Tel est le cas pour l'[[algèbre associative|algèbre]] des [[polynôme en plusieurs indéterminées|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 (algèbre)|magma]] unifère associatif.

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

*<math>x*y \in E</math> (loi interne) ;
*<math>x*(y*z) = (x*y)*z</math> (associativité) ;
*<math>x*e=e*x=x</math> (''e'' est neutre).

Un monoïde ''E'' est dit ''[[loi de composition interne#Éléments particuliers|simplifiable]] à gauche'', ou encore ''régulier à gauche'', (respectivement ''à droite'') si
:<math>\forall (a,b,c)\in E^3, a*b=a*c\,</math> (respectivement <math>b*a=c*a\,</math>) <math>\Rightarrow b=c.</math>

Un monoïde est dit [[commutatif]] si ses éléments sont [[permutable]]s, c'est-à-dire si :

:<math>\forall (x,y)\in E^2\quad x*y = y*x.</math>

== 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 <math>xy</math> pour désigner le composé noté <math>x*y</math> plus haut. L'élément neutre est alors désigné par 1.

On peut [[Définition par récurrence|définir par récurrence]] sur ''n'' le produit <math>x_1\cdots x_n</math> d'un [[n-uplet|''n''-uplet]] d'éléments de ''E'' par :
*le produit du 0-uplet est égal à <math>1\quad(0)</math> ;
*<math>x_1\cdots x_{n+1}=(x_1\cdots x_n)x_{n+1}\quad(1)</math>.
En étendant cette définition au composé (« produit » dans notre notation) <math>\prod _{i\in I}x_i</math> d'une ''séquence'' d'éléments de ''E''<ref>{{Note autre projet|wikiversité|Monoïde/Composé d'une séquence|« Composé d'une séquence » de la leçon sur les monoïdes|début=Cette section est beaucoup plus détaillée dans le chapitre}}</ref> — c'est-à-dire d'une [[Famille (mathématiques)|famille]] <math>(x_i)_{i\in I}</math> indexée par un ensemble fini [[Ordre total|totalement ordonné]] —, on démontre :
*un '''théorème d'associativité<ref>{{Ouvrage|auteur=[[N. Bourbaki]]|titre=[[Éléments de mathématique|Algèbre, chapitres 1 à 3]]|éditeur=[[Springer Verlag|Springer]]|année=2007}}, ch. I, § 1, {{Numéro|3}}, {{p.|4}} et § 2, {{Numéro|1}}, {{p.|13}}.</ref>''' selon lequel, dans un monoïde, un produit <math>x_1\cdots x_n</math>, évalué par cette définition ou en plaçant les parenthèses de [[Nombre de Catalan#Produits non associatifs|n'importe quelle autre façon]], donnera le même résultat (par exemple : <math>((ab)c)d=(a(bc))d=(ab)(cd)=a((bc)d)=a(b(cd))</math>).
*un '''théorème de commutativité<ref>{{harvsp|Bourbaki|2007|loc=ch. I, § 1, théor. 2, p. 8}}.</ref>''' selon lequel, dans un monoïde commutatif (ou plus généralement, pour une famille dont les éléments [[Commuter|commutent]] deux à deux) le composé d'une famille finie ne dépend pas de l'ordre choisi sur l'index de cette famille.

Un [[corollaire]] est que pour tout (''n'' + 1)-uplet <math>(x_1,\ldots,x_{n+1})</math> d'éléments de ''E'',
:<math>x_1\cdots x_{n+1}=x_1(x_2\cdots x_{n+1})\quad(2)</math>.

Cette formule (2), jointe à la condition (0) ci-dessus, est l'autre définition courante de <math>x_1\cdots x_n</math> par récurrence sur ''n''. Le corollaire permet de prouver l'équivalence de ces deux définitions, [[Raisonnement par récurrence|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 :
*<math>\forall x,y\in F\quad x*y \in F</math> (stable) ;
*<math>e \in F.</math>

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

Un [[Demi-groupe#Sous-demi-groupe|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 [[Anneau ℤ/nℤ|ℤ/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 :
<center><math>P^* = \{ x \in E\mid\exists n \in \N, \exists (a_1,\cdots,a_n) \in P^n, x = a_1 *\cdots * a_n \}</math></center>
(l'élément ''e'' fait bien partie de cet ensemble : c'est le [[produit vide]], correspondant à ''n'' = 0<ref>{{harvsp|Bourbaki|2007|loc=ch. I, § 2, {{n°|1}}, p. 13}}.</ref>{{,}}<ref>{{Ouvrage|lang=en|auteur=Arjeh M. Cohen|auteur2=Hans Cuypers|auteur3=Hans Sterk|titre=Algebra Interactive!: Learning Algebra in an Exciting Way|éditeur=Springer|year=1999|url={{Google Livres|vhyGCAyQj3gC|page=71}}|page=71}}.</ref>{{,}}<ref>{{Ouvrage|lang=en|auteur=Henri Bourlès|auteur2=Bogdan Marinescu|titre=Linear Time-Varying Systems: Algebraic-Analytic Approach|éditeur=Springer|year=2011|url={{Google Livres|oFryCAAAQBAJ|page=30}}|page=30}}.</ref>).

''P'' est appelé 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.

== Bases et monoïdes libres ==

Une partie ''P'' d'un monoïde (''E'', ✻, ''e'') est appelée '''base''' de ''E'' si c'est une famille génératrice de ''E'' dans laquelle tout élément se décompose de façon unique, c'est-à-dire si
<center><math>\forall x \in E\quad\exists! n \in \N\quad\exists! (a_1,\ldots,a_n) \in P^n, x = a_1 *\cdots * a_n.</math></center>
Un monoïde est dit [[Objet libre|libre]] s'il admet une base. Dans ce cas, la base est unique.

* ''e'' n'appartient jamais à la base, sans quoi les éléments auraient une infinité de décompositions possibles.
* Si ''A'' est un ensemble (appelé parfois [[alphabet]]), l'ensemble des suites finies d'éléments de ''A'' (appelées [[Théorie des langages|mots]]) muni de l'opération de [[concaténation]] est un monoïde libre noté ''A''* et appelé '''{{Lien|trad=Free monoid|monoïde libre}} sur ''A'''''. Sa base est l'ensemble des mots de longueur un, et donc assimilable naturellement à l'alphabet.
* Deux monoïdes libres sur des alphabets finis sont [[#Morphisme de monoïdes|isomorphes]] si et seulement si leurs bases ont même cardinal.
* Dans un monoïde libre, l'élément neutre est le seul élément [[#Symétrique d'un élément|symétrisable]].

==Exemples==

* L'ensemble <math>\N</math> des [[Entier naturel|entiers naturels]] muni de l'addition est un monoïde libre, dont 0 est l'élément neutre et 1 l'unique élément de la base.
*<math>\N</math> muni de la multiplication est un monoïde d'élément neutre 1. L'élément 0 n'est pas simplifiable <math>(\forall (n,m)\, 0.n=0.m\,)</math>.
*<math>\N</math> muni de la loi {{math|max}} qui à deux entiers associe le plus grand des deux est un monoïde de neutre 0.
* L'[[ensemble des parties d'un ensemble]] ''E'', muni de l'union ensembliste, est un monoïde, dont l'ensemble vide est l'élément neutre. Le même ensemble muni de l'intersection ensembliste est aussi un monoïde dont ''E'' est l'élément neutre.
*L'ensemble des [[application (mathématiques)|applications]] d'un ensemble dans lui-même, muni de la [[Composition de fonctions|composition]], est un monoïde dont le neutre est l'[[application identité]], les éléments simplifiables à gauche sont les [[Injection (mathématiques)|injections]] et ceux simplifiables à droite sont les [[surjection]]s.
* La deuxième loi d'un [[Anneau (mathématiques)|anneau]] possède une structure de monoïde.

== Morphisme de monoïdes ==
Soient (''E'', ✻, ''e'') et (''F'', ✮, ''f'') deux monoïdes. On appelle [[morphisme]] de (''E'', ✻, ''e'') vers (''F'', ✮, ''f'') toute application {{math|''φ''}} de ''E'' vers ''F'' telle que
*<math> \forall x,y\in E\quad\varphi(x*y) =\varphi(x)\star\varphi(y)</math>
*<math> \varphi(e) =f.</math>
La première propriété est celle de morphisme de [[Magma_(algèbre)|magmas]]. 
* La composée de deux morphismes de monoïdes est un morphisme de monoïdes.
* Le réciproque d'un morphisme [[Bijection|bijectif]] de monoïdes est un morphisme de monoïdes. En conséquence, un morphisme bijectif est qualifié d'isomorphisme.
*Tout morphisme de magmas d'un monoïde vers un monoïde simplifiable est un morphisme de monoïdes<ref name=ExosWikiversité>{{Note autre projet|wikiversité|Théorie des groupes/Exercices/Élément neutre|l'exercice correspondant|début=Pour une démonstration, voir par exemple le corrigé de}}</ref>.
* Si l'on munit l'ensemble des entiers naturels de la loi {{math|max}}, l'application ''n'' ↦ ''n'' + 1 est un morphisme de magmas mais n'est pas un morphisme de monoïdes.
* Tout morphisme de magmas [[surjectif]] entre deux monoïdes est un morphisme de monoïdes.
* On appelle noyau d'un morphisme de monoïdes l'ensemble des antécédents de l'élément neutre. Si le morphisme est injectif alors son noyau est réduit à l'élément neutre, mais la réciproque est fausse en général (contrairement au cas d'un [[morphisme de groupes]]) : par exemple le morphisme qui à tout mot associe sa longueur, d'un [[#Bases et monoïdes libres|monoïde libre]] sur (au moins) deux éléments vers [[#Exemples|(ℕ, +)]], n'est pas injectif.
{{énoncé|
* L'[[image réciproque]] d'un sous-monoïde par un morphisme de monoïdes est un [[#Sous-monoïde|sous-monoïde]]. En particulier, le noyau d'un morphisme de monoïdes est un sous-monoïde.
* L'[[Image directe|image d'un sous-monoïde]] par un morphisme de monoïdes est un sous-monoïde. En particulier, l'[[Image d'une application|image d'un morphisme]] de monoïdes est un sous-monoïde.
}}

== Produit direct de monoïdes ==
* Soient (''E'', ✻, ''e'') et (''F'', ✮, ''f'') deux monoïdes. On peut munir le produit cartésien et <math>E\times F\,</math> d'une structure de monoïde en introduisant une nouvelle loi <math>\wedge</math> de la façon suivante :
:<math> \forall (x,y),(x',y') \in (E\times F)^2,\ (x,y)\wedge (x',y')= (x*x',y\star y')</math>.<br />C'est un monoïde de neutre <math>\displaystyle (e,f)</math>.
* Les deux projections <math> p : (x,y) \mapsto x</math> de <math> E\times F</math> dans <math>\displaystyle E</math> et <math> q : (x,y) \mapsto y</math> de <math> E\times F</math> dans <math>\displaystyle F</math> sont des morphismes de monoïde. Et le triplet <math> ((E\times F,\wedge,(e,f)),p,q)</math> vérifie la [[propriété universelle]] du [[produit direct]].
* Plus généralement, soit <math>I</math> un ensemble et <math>((E_i,*_i,e_i))_{i\in I}</math> une famille de monoïdes. On construit la structure de produit direct sur le produit cartésien <math>\prod_{i\in I}(E_i)</math> par la formule
:<math> (x_i)_{i\in I} * (y_i)_{i\in I} = (x_i *_i y_i)_{i\in I}.</math>.

== [[Élément symétrique|Symétrique d'un élément]] ==

* Soient (''E'', ✻, ''e'') un monoïde et ''x'' un élément de ''E''. On dit que :
**''x'' est symétrisable à droite s'il existe un élément ''y'' dans ''E'' tel que ''x'' ✻ ''y = e''. On dit alors que ''y'' est un symétrique à droite de ''x'' ;
**''x'' est symétrisable à gauche s'il existe un élément ''z'' dans ''E'' tel que ''z'' ✻ ''x = e''. On dit alors que ''z'' est un symétrique à gauche de ''x'' ;
**''x'' est symétrisable s'il est symétrisable à droite et à gauche.
* Lorsque ''x'' est symétrisable, il admet un unique [[élément symétrique|symétrique]] à droite et un unique symétrique à gauche et ceux-ci sont égaux.{{Retrait|1=En effet, avec les notations ci-dessus, ''y = e''✻''y'' = (''z''✻''x'')✻''y'' = ''z''✻(''x''✻''y'') = ''z''✻''e = z''.}}Cet unique élément est appelé symétrique de ''x'' et généralement noté ''x''{{-1}}.
* L'ensemble ''I''(''E'') des éléments symétrisables du monoïde forme un groupe, car il est stable :
**par passage au symétrique : pour tout ''x'' ∈ ''I''(''E''), ''x''{{-1}} ∈ ''I''(''E'') et (''x''{{-1}}){{-1}} = ''x'' ;
**par produit : pour tous ''x'', ''y'' ∈ ''I''(''E''), ''x''✻''y'' ∈ ''I''(''E'') et (''x''✻''y''){{-1}} = ''y''{{-1}} ✻ ''x''{{-1}}.{{Retrait|1=En effet, (''y''{{-1}}✻''x''{{-1}})✻(''x''✻''y'') = ''y''{{-1}}✻(''x''{{-1}}✻''x'')✻''y = y''{{-1}}✻''e''✻''y = y''{{-1}}✻''y = e'' donc aussi (en posant ''a = y''{{-1}} et ''b = x''{{-1}}) (''x''✻''y'')✻(''y''{{-1}}✻''x''{{-1}}) = (''b''{{-1}}✻''a''{{-1}})✻(''a''✻''b'') = ''e''.}}
*Par restriction, tout morphisme φ : (''E'', ✻, ''e'') → (''F'', ✮, ''f'') entre deux monoïdes induit un morphisme de groupes de ''I''(''E'') dans ''I''(''F'')<ref name=ExosWikiversité/>.<br />En [[théorie des catégories]], on interprète ce fait en disant que ''I'' est un [[foncteur]] de la [[catégorie des monoïdes]] dans [[Catégorie des groupes|celle des groupes]] (c'est l'[[Foncteur adjoint|adjoint à droite]] du [[foncteur d'oubli]] [[Catégorie des groupes#Groupes, monoïdes et ensembles|''M'' : Grp → Mon]]).

== Symétrisation ==
{{Voir|Symétrisation}}
On généralise la [[construction des entiers relatifs]] à partir des [[Entier naturel|entiers naturels]], en associant [[Canonique (mathématiques)|canoniquement]] à tout monoïde commutatif ''M'' = (''S'', +, 0) un [[groupe abélien]] G(''M''), appelé son [[Symétrisation|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 :
:<math>( m , n ) \sim ( p , q ) \Leftrightarrow \exists k\in S \quad m + q+k= p + n+k.</math>

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 :
:<math>( m , n ) \sim ( p , q ) \Leftrightarrow m + q=p + n.</math>

==Applications==
Le monoïde est un cadre propice pour définir les [[itération|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.

== Notes et références ==
{{Références}}

== Articles liés ==
* [[Demi-groupe]]
* [[Demi-groupe numérique|Monoïde numérique]]

==Bibliographie==
{{Ouvrage|lang=en|nom1=[[Alfred H. Clifford]]|nom2=[[Gordon Preston|Gordon B. Preston]]|titre=The Algebraic Theory of Semigroups|lien éditeur=American Mathematical Society|éditeur=AMS|volume=1 ({{2e}} éd. 1964) et vol. 2 (réimpr. 1988)}}

{{Palette|Structures algébriques}}
{{Portail|algèbre}}

[[Catégorie:Structure algébrique]]
[[Catégorie:Algèbre générale]]