Monoïde

En mathématiques, et plus précisément en algèbre générale, 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. Par définition il s'agit donc d'un magma associatif et unifère, soit un demigroupe 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 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

Un monoïde est un magma unifère associatif.

Formellement, $(E, *, e)$ est un monoïde lorsque :

$\forall (x,y)\in E^2, x*y \in E$ (stabilité) ;
$\forall (x,y,z)\in E^3, x*(y*z) = (x*y)*z$ (associativité) ;
$\exists\ e\in E, \forall x\in E, x*e=e*x=x$ (existence d'un élément neutre).

Un monoïde E est dit simplifiable à gauche, ou encore régulier à gauche, (resp. à droite) si

\forall (a,b,c)\in E^3, a*b=a*c\,

(resp.

b*a=c*a\,

)

\Rightarrow b=c.

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

\forall (x,y)\in E^2\quad x*y = y*x.

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é $x*y$ plus haut. L'élément neutre est alors désigné par 1.

Définissons récursivement le composé (« produit » dans notre notation) $\prod _{i=1}^nx_i=x_1\ldots x_n$ d'un n-uplet $(x_i)_{1\le i\le n}$ d'éléments de E pour tout entier naturel n ou plus généralement, le composé $\prod _{i\in I}x_i$ d'une séquence d'éléments de E, c'est-à-dire d'une famille $(x_i)_{i\in I}$ indexée par un ensemble fini totalement ordonné :

le produit indexé par l'ensemble vide est égal à 1 ;
si $\beta$ est le plus grand élément de $I$ , $\prod _{i\in I}x_i=\left(\prod _{i\in I\setminus\{\beta\}}x_i\right)x_{\beta}.$

Pour les n-uplets, cette condition s'écrit :

\prod _{i=1}^{n+1}x_{i} = \left(\prod _{i=1}^{n}x_{i}\right)x_{n+1}

ou encore :

x_1\ldots x_{n+1}=(x_1\ldots x_n)x_{n+1}\quad(1).

La « généralisation » des n-uplets aux séquences n'est qu'un artifice de notation — si deux séquences $(x_{i})_{i \in I}$ et $(y_{j})_{j \in J}$ sont équivalentes, c'est-à-dire s'il existe un isomorphisme $\sigma$ d'ensembles ordonnés de I sur J tel que, pour tout élément i de I, $y_{\sigma(i)}=x_i$ , leurs composés sont évidemment égaux, or toute séquence est canoniquement équivalente à un uplet — mais aide à formuler le théorème d'associativité^[1] :

Soit E un monoïde, noté multiplicativement, soient A et I deux ensembles finis totalement ordonnés, et $(A_i)_{i \in I}$ une famille de parties 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 $A_i$ et tout élément b de $A_j$ . Pour toute séquence $(x_{a})_{a \in A}$ d'éléments de E indexée par A, on a

$\prod _{a \in A}x_{a} = \prod _{i \in I} \prod _{a \in A_{i}}x_a.$

Un corollaire est que pour tout (n + 1)-uplet $(x_1,\ldots,x_{n+1})$ d'éléments de E,

x_1\ldots x_{n+1}=x_1(x_2\ldots x_{n+1})\quad(2).

Cette formule (2), ou la formule (1) précédente, est couramment présentée — jointe à la définition du produit du 0-uplet comme étant égal à 1 — comme définition de $x_1\ldots x_n$ 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.

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 $(x_i)_{i \in I}$ 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é »^[2].

Sous-monoïde

Un sous-monoïde d'un monoïde $(E,*,e)\,$ est un sous ensemble $E'\,$ de $E\,$ vérifiant :

$\forall (x,y)\in E^2\, (x \in E'\, et\, y \in E') \Rightarrow (x*y \in E')$ (stable)
$e \in E'.$

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

Un 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 Z/6Z muni de sa multiplication, les classes résiduelles des nombres pairs forment un sous-demi-groupe D de M et 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 de E contenant P. Il peut être décrit par :

P^* = \{ x \in E\mid\exists n \in \N, \exists (a_1,\cdots,a_n) \in P^n, x = a_1 *\cdots * a_n \}

(l'élément e fait bien partie de cet ensemble : c'est le produit vide, correspondant à n = 0).

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

\forall x \in E\quad\exists! n \in \N\quad\exists! (a_1,\cdots,a_n) \in P^n, x = a_1 *\cdots * a_n.

Un monoïde est dit 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 mots) muni de l'opération de concaténation est un monoïde libre noté A* et appelé monoïde libre (en) 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 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étrisable.

Exemples

L'ensemble ℕ des 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.
ℕ muni de la multiplication est un monoïde d'élément neutre 1. L'élément 0 n'est pas simplifiable $(\forall (n,m)\, 0.n=0.m\,)$ .
ℕ 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 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 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 possède une structure de monoïde.

Morphisme de monoïdes

Soit et deux monoïdes. on appelle morphisme de vers toute application de vers telle que
- $\forall (x,y)\in E^2,\ \varphi(x*y) =\varphi(x)\star\varphi(y)$
- $\varphi(e) =f.$
  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.
La réciproque de tout morphisme bijectif de monoïdes est un morphisme de monoïdes. En conséquence, un morphisme bijectif est qualifié d'isomorphisme.
L'image d'un élément idempotent par un morphisme de monoïdes (ou même seulement de magmas) est un élément idempotent.
Si 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.
Tout morphisme de magmas d'un monoïde vers un groupe est un morphisme de monoïdes.
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.
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 au 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.

Produit direct de monoïdes

Soit $(E,*,e)\,$ et $(F,\star,f)\,$ deux monoïdes. on peut munir le produit cartésien et $E\times F\,$ d'une structure de monoïde en introduisant une nouvelle loi $\wedge$ de la façon suivante :

\forall (x,y),(x',y') \in (E\times F)^2,\ (x,y)\wedge (x',y')= (x*x',y\star y')

.
C'est un monoïde de neutre

\displaystyle (e,f)

Les deux projections $p : (x,y) \mapsto x$ de $E\times F$ dans $\displaystyle E$ et $q : (x,y) \mapsto y$ de $E\times F$ dans $\displaystyle F$ sont des morphismes de monoïde. Et le triplet $((E\times F,\wedge,(e,f)),p,q)$ vérifie la propriété universelle du produit direct.
Plus généralement, soit $I$ un ensemble et $((E_i,*_i,e_i))_{i\in I}$ une famille de monoïde. On construit la structure de produit direct sur le produit cartésien $\prod_{i\in I}(E_i)$ par la formule

(x_i)_{i\in I} * (y_i)_{i\in I} = (x_i *_i y_i)_{i\in I}.

Symétrique d'un élément

Soit un monoïde et soit 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. Cet unique élément est appelé symétrique de $x$ .
En effet, c'est une conséquence de l'associativité, avec les notations ci-dessus $y= e*y= (z*x)*y = z*(x*y) = z*e = z$ .
Le symétrique de $x$ est généralement noté $x^{-1}$ . Il est symétrisable : $(x^{-1})^{-1}=x.$
Si $x$ et $y$ sont symétrisables, il en est de même de $x*y$ et l'on a $(x*y)^{-1}=y^{-1}*x^{-1}$ .
On vérifie en effet que $(x*y)*(y^{-1}*x^{-1})=x*(y*y^{-1})*x^{-1}=x*e*x^{-1}=x*x^{-1}=e$ (grâce à l'associativité) et donc (en posant $a=y^{-1},b=x^{-1}$ ) $(y^{-1}*x^{-1})*(x*y)=(a*b)*(b^{-1}*a^{-1})=e.$
L'ensemble U(M) des éléments symétrisables d'un monoïde M forme un groupe et par restriction, tout morphisme entre deux monoïdes induit un morphisme de groupes entre leurs groupes d'éléments symétrisables. En théorie des catégories, on interprète ce fait en disant que U est un foncteur de la catégorie des monoïdes dans la catégorie des groupes.

Démonstration

U(M) est stable par produit et passage au symétrique: Si x est symétrisable dans M, il possède un symétrique y ; et y possède alors un symétrique dans M, qui est précisément x. Donc, le symétrique d'un élément symétrisable est symétrisable.; Si x et y sont des éléments symétrisables de M, alors y⁻¹x⁻¹ est un symétrique de xy. En effet, l'associativité donne :; $(y^{-1}x^{-1})\times (xy)=y^{-1}\times (x^{-1}x)\times y=y^{-1}\times 1\times y=y^{-1}y=1$ .; Par conséquent, le produit de deux éléments symétrisables est symétrisable.; L'associativité de la multiplication et l'existence d'un élément neutre sont garanties par les propriétés du monoïde.
L'image d'un élément symétrisable est symétrisable: Soit un élément symétrisable x d'un monoïde M. Notons y le symétrique de x dans M. Soit f un morphisme de monoïdes de M dans N. Comme xy = 1 dans M, il vient : f(x)f(y) = f(xy) = 1. Par conséquent, f(x) est symétrisable dans N (et son symétrique est f(y)).

Symétrisation

Article détaillé : Symétrisation.

On généralise la construction des entiers relatifs à partir des entiers naturels, en associant canoniquement à tout monoïde commutatif (S, +, 0) un groupe abélien G(S), appelé son groupe de Grothendieck, muni d'un morphisme de monoïdes de S dans G(S).

Le procédé de construction est appelé la symétrisation du monoïde. On considère pour cela la relation d'équivalence $\sim$ sur $S\times S$ définie, pour $( m , n ), ( p , q )\in S\times S$ par :

( m , n ) \sim ( p , q ) \Leftrightarrow \exists k\in S \quad m + q+k= p + n+k.

Le groupe G(S) a pour éléments les classes d'équivalence de $\sim$ et le morphisme naturel de S dans G(S) associe à tout élément x de S la classe de (x, 0). Ce morphisme est injectif si et seulement si S est simplifiable ; dans ce cas, la relation $\sim$ peut être décrite plus simplement :

( m , n ) \sim ( p , q ) \Leftrightarrow m + q=p + n.

Applications

Le monoïde est un cadre propice pour définir les itérations 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

↑ N. Bourbaki, Algèbre, Paris, Hermann,‎ 1970, ch. I, § 1, n° 3, p. 4 et § 2, n° 1, p. 13
↑ Bourbaki 1970, ch. I, § 1, théor. 2, p. 8

Voir aussi

(en) Alfred H. Clifford et Gordon B. Preston, The Algebraic Theory of Semigroups, vol. 1 (2^e éd. 1964) et vol. 2 (réimpr. 1988), AMS

Portail de l’algèbre

This article is issued from Wikipédia - version of the Monday, June 08, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.