Monoïde
Un article de Freepedia.
Définition
En mathématiques, un monoïde est une structure algébrique consistant en un ensemble muni d'une loi de composition interne associative et d'un élément neutre. Un monoïde est donc un magma associatif et unifère.
En d'autres termes, (E, *) est un monoïde si :
- pour tout x,y dans E, x*y est dans E (loi de composition interne) ;
- pour tout x,y,z dans E, x*(y*z) = (x*y)*z (associativité) ;
- il existe un élément e dans E vérifiant : pour tout x dans E, x*e=e*x=x.
On trouve aussi parfois une définition d'un monoïde où l'existence d'un élément neutre n'est pas requise.
Un monoïde E est dit simplifiable à gauche, ou encore régulier à gauche, (resp. à droite) si pour tout a,b,c dans E, a*b=a*c (resp. b*a=c*a) entraîne b=c.
Un monoïde est dit libre s'il est isomorphe à l'ensemble des séquences d'éléments d'un ensemble fini (alphabet), muni de la concaténation. À ce moment-là, on appelle 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.
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 qui n'est pas simplifiable (0.n=0.m pour tout n,m) ;
- l'ensemble des mots formé sur un alphabet, muni de la concaténation, est un monoïde que l'on appelle monoïde libre, dont le mot vide est l'élément neutre.
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 groupes, ou les anneaux... Les entiers naturels en sont un exemple frappant : pour les étudier, on étudie les entiers relatifs, qui eux forment un groupe, et mieux, un anneau 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.
