Monoïde — Wikipédia
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
[modifier | modifier le code]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
[modifier | modifier le code]Un monoïde est un magma unifère associatif.
Formellement, (, ✻, ) est un monoïde lorsque, pour tous éléments , et de :
- (loi interne) ;
- (associativité) ;
- (e est neutre).
Un monoïde E est dit simplifiable à gauche, ou encore régulier à gauche, (respectivement à droite) si
- (respectivement )
Un monoïde est dit commutatif si ses éléments sont permutables, c'est-à-dire si :
Composé d'une séquence (finie) d'éléments
[modifier | modifier le code]Soit un monoïde. Notons sa loi de composition sous forme multiplicative, c'est-à-dire que nous écrirons pour désigner le composé noté plus haut. L'élément neutre est alors désigné par 1.
On peut définir par récurrence sur le produit d'un n-uplet d'éléments de par :
- le produit du 0-uplet est égal à ;
- .
En étendant cette définition au composé (« produit » dans notre notation) d'une séquence d'éléments de [1] — c'est-à-dire d'une famille indexée par un ensemble fini totalement ordonné —, on démontre :
- un théorème d'associativité[2] selon lequel, dans un monoïde, un produit , évalué par cette définition ou en plaçant les parenthèses de n'importe quelle autre façon, donnera le même résultat (par exemple : ).
- un théorème de commutativité[3] selon lequel, dans un monoïde commutatif (ou plus généralement, pour une famille dont les éléments 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 d'éléments de ,
- .
Cette formule (2), jointe à la condition (0) ci-dessus, est l'autre définition courante de 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
[modifier | modifier le code]Un sous-monoïde d'un monoïde (, ✻, ) est un sous-ensemble de vérifiant :
- (stable) ;
Toute intersection de sous-monoïdes est un sous-monoïde.
Un sous-demi-groupe d'un monoïde peut être un monoïde sans être un sous-monoïde de . Par exemple, si 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 de et l'on vérifie facilement que la classe résiduelle de 4 est élément neutre de ce sous-demi-groupe. Pourtant, n'est pas un sous-monoïde de , car l'élément neutre de (la classe résiduelle de 1) n'appartient pas à .
Famille génératrice d'un sous-monoïde
[modifier | modifier le code]Soit une partie d'un monoïde (, ✻, ). On appelle sous-monoïde engendré par (noté ) l'intersection des sous-monoïdes de contenant . C'est donc le plus petit sous-monoïde de contenant . Il peut être décrit par :
(l'élément fait bien partie de cet ensemble : c'est le produit vide, correspondant à n = 0[4],[5],[6]).
On dit alors que est une famille génératrice de .
On peut toujours trouver une famille génératrice à tout monoïde, la plus triviale étant lui-même.
Monoïde libre
[modifier | modifier le code]Un monoïde est dit libre[7] s'il vérifie la propriété universelle suivante :
Définition — Un monoïde est dit libre s'il existe un ensemble et une fonction telle que pour tout monoïde et toute fonction , il existe un unique morphisme de monoïdes tel que . Dans ce cas, on dit que 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 sont exactement les monoïdes isomorphes à , où est le monoïde formé par les suites finies d'éléments de , 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 , et est la fonction qui envoie sur la suite finie composée d'un seul élément, . Dans ce contexte, 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 et , isomorphes respectivement à et , est isomorphe à si et seulement si et sont en bijection.
Monoïde commutatif libre
[modifier | modifier le code]Un monoïde commutatif (c'est-à-dire, un monoïde dont la loi de composition est commutative) est dit libre[8] 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 est dit libre s'il existe un ensemble et une fonction telle que pour tout monoïde commutatif et toute fonction , il existe un unique morphisme de monoïdes tel que . Dans ce cas, on dit que est le monoïde commutatif libre sur A.
Les monoïdes commutatifs libres peuvent être construits de plusieurs façons équivalentes :
- En quotientant l'ensemble des mots sur par la relation d'équivalence s'il existe une permutation de telle que pour tout , muni de la concaténation.
- Comme l'ensemble des combinaisons linéaires formelles sur à coefficients dans , c'est-à-dire comme l'ensemble des avec et des entiers et des éléments de , muni de la somme. On peut voir ces combinaisons linéaires comme une application de vers à support fini, c'est-à-dire comme une application pour laquelle l'ensemble des éléments de qui ont une valeur non nulle soit finie.
- Comme l'ensemble des multiensembles finis à valeurs dans .
Exemples
[modifier | modifier le code]- Un groupe est un monoïde dont tous les éléments sont inversibles[9].
- L'ensemble ℕ des entiers naturels muni de l'addition est le monoïde libre sur l'ensemble à 1 élément , dont 0 est l'élément neutre. C'est également le monoïde commutatif libre sur le même ensemble.
- Les monoïdes numériques sont des sous-monoïdes particuliers de (ℕ, +, 0).
- ℕ muni de la multiplication est un monoïde d'élément neutre 1. L'élément 0 n'est pas simplifiable ().
- est un monoïde, engendré par l'ensemble des nombres premiers.
- ℕ muni de la loi max qui à deux entiers associe le plus grand des deux est un monoïde de neutre 0.
- L'ensemble des parties d'un ensemble , 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 est l'élément neutre.
- L'ensemble des applications d'un ensemble dans lui-même, muni de la composition, est un monoïde dont le neutre est l'application identité, les éléments simplifiables à gauche sont les injections et ceux simplifiables à droite sont les surjections.
- La deuxième loi d'un anneau unitaire possède une structure de monoïde (non commutatif si l'anneau est non commutatif).
- Si est un groupe monogène d'ordre infini, et si n'est pas l'élément neutre, alors est un monoïde, mais pas un groupe.
Morphisme de monoïdes
[modifier | modifier le code]Soient (, , ) et (, , ) deux monoïdes. On appelle morphisme de (, , ) vers (F, , ) toute application de vers telle que
La première propriété est celle de morphisme de magmas.
- La composée de deux morphismes de monoïdes est un morphisme de monoïdes.
- Le réciproque d'un morphisme 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[10].
- Si l'on munit l'ensemble des entiers naturels de la loi 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 monoïde libre sur (au moins) deux éléments vers (ℕ, +), n'est pas injectif.
- L'image réciproque d'un sous-monoïde par un morphisme de monoïdes est un sous-monoïde. En particulier, le noyau d'un morphisme de monoïdes est un sous-monoïde.
- L'image d'un sous-monoïde par un morphisme de monoïdes est un sous-monoïde. En particulier, l'image d'un morphisme de monoïdes est un sous-monoïde.
Produit direct de monoïdes
[modifier | modifier le code]- Soient (, ✻, ) et (, ✮, f) deux monoïdes. On peut munir le produit cartésien et d'une structure de monoïde en introduisant une nouvelle loi de la façon suivante :
- .
C'est un monoïde de neutre .
- Les deux projections de dans et de dans sont des morphismes de monoïde. Et le triplet vérifie la propriété universelle du produit direct.
- Plus généralement, soit un ensemble et une famille de monoïdes. On construit la structure de produit direct sur le produit cartésien par la formule
- .
- 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 symétrique à droite et un unique symétrique à gauche et ceux-ci sont égaux.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.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)[10].
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 celle des groupes (c'est l'adjoint à droite du foncteur d'oubli M : Grp → Mon).
Symétrisation
[modifier | modifier le code]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 :
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 :
Applications
[modifier | modifier le code]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.
Notes et références
[modifier | modifier le code]- Cette section est beaucoup plus détaillée dans le chapitre .
- N. Bourbaki, Algèbre, chapitres 1 à 3, Springer, , ch. I, § 1, no 3, p. 4 et § 2, no 1, p. 13.
- Bourbaki 2007, ch. I, § 1, théor. 2, p. 8.
- Bourbaki 2007, ch. I, § 2, no 1, p. 13.
- (en) Arjeh M. Cohen, Hans Cuypers et Hans Sterk, Algebra Interactive!: Learning Algebra in an Exciting Way, Springer, (lire en ligne), p. 71.
- (en) Henri Bourlès et Bogdan Marinescu, Linear Time-Varying Systems: Algebraic-Analytic Approach, Springer, (lire en ligne), p. 30.
- Lothaire 1997, p. 2-5
- Vikraman Choudhury et Marcelo Fiore, « Free Commutative Monoids in Homotopy Type Theory », Electronic Notes in Theoretical Informatics and Computer Science, proceedings of MFPS XXXVIII, vol. 1, (ISSN 2969-2431, DOI 10.46298/entics.10492, arXiv 2110.05412, lire en ligne
[PDF], consulté le )
- Bourbaki, A I.15, §2 3, Éléments inversibles, Définition 6.
- Pour une démonstration, voir par exemple le corrigé de .
Voir aussi
[modifier | modifier le code]Article connexe
[modifier | modifier le code]Présentation d'un monoïde (en)
Bibliographie
[modifier | modifier le code]- (en) Alfred H. Clifford et Gordon B. Preston, The Algebraic Theory of Semigroups, vol. 1 (2e éd. 1964) et vol. 2 (réimpr. 1988), AMS.
- (en) M. Lothaire, Combinatorics on Words, Cambridge University Press, coll. « Cambridge Mathematical Library », (ISBN 978-0-521-59924-5, lire en ligne
).