Monoïde
13838
30004586
2008-05-26T11:00:40Z
82.123.60.238
ajout indice i pour le produit *_i dans E_i dans la formule
En [[mathématiques]], un '''monoïde''' est une [[structure (mathématiques)|structure]] [[structure algébrique|algébrique]] consistant en un [[ensemble]] muni d'une [[loi de composition interne]] [[associativité|associative]] et d'un [[élément neutre]]. Un '''monoïde''' est donc un [[magma (mathématiques)|magma]] associatif, c.à.d. un [[demigroupe]], et [[élément neutre|unifère]].
En d'autres termes, <math>(E, *, e)\,</math> est un '''monoïde''' si :
# <math>\forall (x,y)\in E^2, x*y \in E</math> (stabilité)
# <math>\forall (x,y,z)\in E^3, x*(y*z) = (x*y)*z</math> (associativité)
# <math>\exists\ e\in E, \forall x\in E, x*e=e*x=x</math> (élément neutre)
Un monoïde E est dit ''[[loi de composition interne#Éléments particuliers|simplifiable]] à gauche'', ou encore ''régulier à gauche'', (resp. ''à droite'') si
:<math>\forall (a,b,c)\in E^3, a*b=a*c\,</math> (resp. <math>b*a=c*a\,</math>) <math>\Rightarrow b=c.</math>
On dit que deux éléments x, y d'un monoïde ''commutent'' (l'un avec l'autre) ou ''sont permutables'' (l'un avec l'autre) si :
:<math>x*y = y*x</math>.
Un monoïde est dit commutatif si sa loi de composition est commutative, c'est-à-dire si :
:<math>\forall (x,y)\in E^2, x*y = y*x</math>,
ce qui revient à dire que tous les éléments de E commutent l'un avec l'autre.
== 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é <math>x \star y</math> plus haut. L'élément neutre est alors désigné par 1.<br>
Nous nous proposons de définir le composé (« produit » dans notre notation) d'un n-uplet <math>(x_{i})_{1 \leq i \leq n}</math> d'éléments de E, quel que soit le nombre naturel <math>n \geq 0</math>.<br>
Étant donné un tel n-uplet, nous pouvons construire par récurrence sur i un (n+1)-uplet <math>(p_{i})_{0 \leq i \leq n}</math> d'éléments de E en posant :
:<math>p_{0} = 1</math>
et
:<math>p_{i + 1} = p_{i}x_{i + 1} \quad pour \quad 0 \leq i \leq n - 1</math>.
Nous définissons alors le composé du n-uplet <math>(x_{i})_{1 \leq i \leq n}</math> comme étant <math>p_{n}</math>. On note ce composé
:<math>x_{1} \ldots x_{n}</math>
ou encore
:<math>\prod _{i=1}^{n}x_{i}</math>.
On montre facilement par récurrence sur i que si <math>(x_{1}, \ldots ,x_{n+1})</math> est un (n+1)-uplet d'éléments de E, les n+1 « produits partiels » <math>p_{i}</math> associés comme ci-dessus au n-uplet (plus petit) <math>(x_{1}, \ldots ,x_{n})</math> sont les n+1 premiers des n+2 produits partiels associés au (n+1)-uplet <math>(x_{1}, \ldots ,x_{n+1})</math>, d'où la formule
:<math>\prod _{i=1}^{n+1}x_{i} = (\prod _{i=1}^{n}x_{i})x_{n+1}</math>
qu'on peut encore écrire
:<math>x_{1} \ldots x_{n+1} = (x_{1}...x_{n}) x_{n+1}</math>.
Cette formule, ou la formule
:<math>x_{1} \ldots x_{n+1} = x_{1}(x_{2}...x_{n+1})</math>,
est couramment présentée comme définition de <math>x_{1} \ldots x_{n}</math> par récurrence sur n.
Du fait de l'associativité, ces deux formules fournissent la même définition. En effet, avec la définition que nous avons choisie, on prouve par récurrence sur s que, pour tous nombres naturels r et s, pour tout r-uplet <math>(x_{1}, \ldots , x_{r})</math> et tout s-uplet <math>(y_{1}, \ldots , y_{s})</math> d'éléments de E,
:<math>(x_{1} \ldots x_{r}) \ (y_{1} \ldots y_{s}) = x_{1} \ldots x_{r} \ y_{1} \ldots y_{s}</math>,
ce qui permet de prouver l'équivalence des deux définitions par récurrence sur le nombre de facteurs.
On notera que, d'après nos définitions, le produit de la famille vide (ou 0-uplet) est égal à 1.
On appelle séquence d'éléments de E une famille d'éléments de E indexée par un ensemble fini totalement ordonné. On associe de façon évidente à une telle séquence un n-uplet <math>(x_{i})_{1 \leq i \leq n}</math> d'éléments de E, ce qui permet d'étendre de façon évidente la définition du composé d'un n-uplet d'éléments de E à toute séquence d'éléments de E. Deux séquences
:<math>(x_{i})_{i \in I} \quad et \quad (y_{j})_{j \in J}</math>
sont dites équivalentes s'il existe un isomorphisme <math>\sigma</math> d'ensembles ordonnés de I sur J tel que, pour tout élément i de I,
:<math>y_{\sigma(i)} = x_{i}</math>.
Cela équivaut à ce que les n-uplets correspondant à ces deux séquences soient identiques, donc deux séquences équivalentes ont le même composé.
La considération des séquences permet de formuler comme suit le théorème d'associativité<ref>N. Bourbaki, Algèbre, Paris, Hermann, 1970, ch. I, § 1, n° 3, p. 4, et § 2, n° 1, p. 13.</ref> :
Soit E un monoïde, noté multiplicativement, soit A un ensemble fini totalement ordonné, soit <math>(A_{i})_{i \in I})</math> une famille finie de parties deux à deux disjointes de A dont la réunion est A tout entier. (On n'exclut pas que certains des ensembles considérés soient vides.) On suppose que si i et j sont deux éléments de I tels que i < j, alors a < b pour tout élément a de <math>A_{i}</math> et tout élément b de <math>A_{j}</math>. Pour toute séquence <math>(x_{a})_{a \in A}</math> d'éléments de E indexée par A, on a
:<math>\prod _{a \in A}x_{a} = \prod _{i \in I} \prod _{a \in A_{i}}x_{a}</math>
Si le monoïde E est commutatif, on peut définir le composé d'une famille finie d'éléments de E sans préciser un ordre sur l'index de cette famille, car on prouve que le composé, tel que défini ci-dessus, est alors indépendant de l'ordre choisi. Plus généralement, si E est un monoïde non forcément commutatif, si
:<math>(x_i)_i \in I</math>
est une famille d'éléments de E dont tous les éléments commutent l'un avec l'autre, le produit des éléments de cette famille ne dépend pas de l'ordre choisi. C'est le « théorème de commutativité »<ref>N. Bourbaki, Algèbre, ch. I, § 1, théor. 2, Paris, 1970, p. 8.</ref>.
== Monoïdes libres ==
Si ''A'' est un [[alphabet]] fini, l'ensemble des [[Théorie des langages|mots]] sur ''A'' est noté ''A*''. Muni de la [[concaténation]], c'est un monoïde que l'on appelle '''monoïde libre''' sur ''A''. Son élément neutre est le mot vide. De manière générale, un monoïde est dit '''libre''' s'il est isomorphe à l'ensemble des mots sur un [[alphabet]] fini, muni de la [[concaténation]]. On appelle alors '''ensemble des générateurs libres''' du monoïde l'image de l'alphabet par l'isomorphisme. Cet ensemble est unique, et deux monoïdes libres sont isomorphes si et seulement s'ils ont le même nombre de générateurs libres. Notons l'existence de monoïdes non libres. Il suffit par exemple de considérer le monoïde multiplicatif des entiers naturels.
==Sous-monoïde==
Un sous-monoïde d'un monoïde de <math>(E,*,e)\,</math> est un sous ensemble <math>E'\,</math> de <math>E\,</math> verifiant:
# <math>\forall (x,y)\in E^2\, (x \in E'\, et\, y \in E') \Rightarrow (x*y \in E')</math> (stable)
# <math>e \in E'\,</math>
==Exemples==
* L'ensemble des entiers naturels, muni de l'addition, est un monoïde, dont 0 est l'élément neutre ;
* L'ensemble des entiers naturels, muni de la multiplication, est un monoïde d'élément neutre 1. 0 n'est pas simplifiable <math>(\forall (n,m)\, 0.n=0.m\,)</math> ;
* 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 entiers naturels muni de la loi ''Max'' qui a deux entiers associe le plus grand des deux est un monoïde de neutre 0.
* La deuxième loi d'un anneau possède une structure de monoïde. Beaucoup de propriétés des anneaux en découlent, notamment l'étude des [[Anneau factoriel|Anneaux factoriels]].
== Morphisme de monoïde ==
* Soit <math>(E,*,e)</math> et <math>(F,T,f)</math> deux monoïdes. on appelle [[morphisme]] de <math>(E,*,e)</math> vers <math>(F,T,f)</math> toute application <math>\varphi</math> de <math>E</math> vers <math>F</math> telle que
# <math> \forall (x,y)\in E^2,\ \varphi(x*y) =\varphi(x)T\varphi(y)</math>
# <math> \varphi(e) =f</math>
La première propriété est celle de morphisme de [[loi de composition interne|loi]] ou morphisme de magma.
* La composée de deux morphismes de monoïde est un morphisme de monoïde.
* La réciproque de tout morphisme [[Bijection|bijectif]] de monoïde est un morphisme de monoïde. En conséquence, un morphisme bijectif est qualifié d'isomorphisme.
* L'image d'un élément [[idempotent]] par un morphisme de monoïde est un élément idempotent.
* Si on munit l'ensemble des entiers naturels de la loi ''Max'', l'application <math> n \mapsto n+1</math> est un morphisme de loi mais n'est pas un morphisme de monoïde.
* Tout morphisme de loi d'un monoïde vers un [[Groupe (mathématiques)|groupe]] est un morphisme de monoïde.
* L'image d'un sous-monoïde par un morphisme de monoïde est un sous-monoïde. En particulier l'image d'un morphisme de monoïde est un sous-monoïde.
* On appelle noyau d'un morphisme de monoïde l'ensemble des antécédents de l'élément neutre.
Attention, il n'y a pas de lien clair entre noyau et injectivité lorsque le monoïde n'est pas un groupe. Par exemple, l'application <math> n \mapsto 2n</math> est un endomorphisme du monoïde des entiers naturels muni de la loi ''Max''.
* L'image réciproque d'un sous-monoïde par un sous-monoïde est un sous-monoïde. En particulier le noyau d'un morphisme de monoïde est un sous-monoïde.
== Produit direct de monoïdes ==
* Soit <math>(E,*,e)\,</math> et <math>(F,T,f)\,</math> 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\, T\, y')</math>.
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ïde. 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>.
== Symétrique d'un élément==
{{Article détaillé|élément symétrique}}
* Soit <math>(E,*,e)</math> un monoïde et soit <math>x</math> un élément de <math>E</math>. On dira que
# <math>x</math> est symétrisable à droite si et seulement s'il existe un élément <math>y</math> dans <math>E</math> tel que <math>x*y = e</math>. On dit alors que <math>y</math> est un symétrique à droite de <math>x</math>.
# <math>x</math> est symétrisable à gauche si et seulement s'il existe un élément <math>z</math> dans <math>E</math> tel que <math>y*x = e</math>. On dit alors que <math>y</math> est un symétrique à gauche de <math>x</math>.
# <math>x</math> est symétrisable si et seulement si <math>x</math> est symétrisable à droite et à gauche.
* Lorsque <math>x</math> est symétrisable il admet un unique symétrique à droite et un unique symétrique à gauche et ceux-ci sont égaux. Cet unique élément est appelé symétrique de <math>x</math>.
En effet, c'est une conséquence de l'associativité, avec les notations ci-dessus <math> y= e*y= (z*x)*y = z*(x*y) = z*e = z</math>
* Le symétrique de <math>x</math> est généralement noté <math>x^{-1}</math>. On le note parfois <math>\frac1x</math> lorsque la loi est commutative, c'est notamment le cas avec la multiplication des nombres réels. On le note <math>-x</math> lorsque la loi du monoïde est noté <math>+</math>.
Le symétrique est souvent appelé inverse, c'est notamment le cas pour les multiplications. Le symétrique pour les additions est appelé opposé.
* Si <math>x</math> et <math>y</math> sont symétrisables, il en est de même de <math>x*y</math> et on a <math>(x*y)^{-1}=y^{-1}*x^{-1}</math>.
On vérifie <math>(x*y)*(y^{-1}*x^{-1})=x*(y*y^{-1})*x^{-1}=x*e*x^{-1}=x*x^{-1}=e</math> grâce à l'associativité et on fait de même à gauche.
* L'ensemble des éléments symétrisables d'un monoïde forme un groupe.
== Itération ==
{{Article détaillé|itération}}
Le monoïde est un cadre propice pour définir les itérations d'un élément.
==Applications==
En [[mathématiques]], il est rare d'utiliser les monoïdes ; car souvent, lorsqu'une structure est trop pauvre en termes de propriétés pour pouvoir continuer son étude, elle se trouve plongée dans une structure plus riche, comme les [[groupe (mathématiques)|groupes]], ou les [[anneau (mathématiques)|anneaux]]... Les entiers naturels en sont un exemple frappant : pour les étudier, on étudie les entiers relatifs, qui eux forment un [[groupe (mathématiques)|groupe]], et mieux, un [[anneau (mathématiques)|anneau]] [[anneau factoriel|factoriel]] !
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]].
== Bibliographie ==
A.H. Clifford et G.B. Preston, ''The algebraic theory of semigroups'', American Mathematical Society, vol. 1 (2{{e}} éd. 1964) et vol. 2 (réimpr. 1988).
== Notes et références ==
<references/>
{{Portail mathématiques}}
[[Catégorie:Structure algébrique]]
[[ca:Monoide]]
[[cs:Monoid]]
[[de:Monoid]]
[[en:Monoid]]
[[es:Monoide]]
[[et:Monoid]]
[[fi:Monoidi]]
[[he:מונואיד (מבנה אלגברי)]]
[[hr:Monoid]]
[[hu:Monoid]]
[[it:Monoide]]
[[ja:モノイド]]
[[nl:Monoïde]]
[[oc:Monoïde]]
[[pl:Monoid]]
[[pt:Monóide]]
[[ro:Monoid]]
[[ru:Моноид]]
[[sl:Monoid]]
[[sr:Моноид]]
[[sv:Monoid (matematik)]]
[[tr:Birlik]]
[[uk:Моноїд]]
[[zh:幺半群]]