Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Monoïde

Définition

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, unifére.

(E, *) est un monoïde si :

1. pour tout x,y dans E : x*y est dans E (loi de composition interne) ;
2. pour tout x,y,z dans E : x*(y*z) = (x*y)*z (associativité) ;
3. 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 ou 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 appelera 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.