# Monoïde

En matematicas, e pus particularament en algèbra, un monoïde es una estructura algebrica que consistís en un ensemble provesit d'una lèi de composicion intèrna associativa e d'un element neutre. Autrament dich, es un magma associatiu e unitari.

## Definicion

Pus explicitament, un monoïde es un pareu $(E,\,*)$ , onte E es un ensemble, e " $\ *$ " es una lèi (de composicion intèrna) dins E, associativa e admetent un element neutre :
* $\forall (x,\,y)\in E^{2},\;x*y\in E$ (lèi de composicion intèrna)
* $\forall (x,\ y,\ z)\in E^{3},\;(x*y)*z=x*(y*z)$ (associativitat)
* $\exists \ e\in E,\;\forall x\in E,\,x*e=e*x=x$ (existéncia d'un element neutre e ; se saup qu'es necessariament unic)
Lo monoïde es dich commutatiu (o abelian) se, de mai, la lèi dins E es commutativa, valent a dire se :
* $\forall (x,\,y)\in E^{2},\;x*y=y*x$ (commutativitat)

### Notacions

La notacion multiplicativa e la notacion additiva son particularament frequentas.

#### Monoïde multiplicatiu

Quand la lèi dins E se nòta multiplicativament, lo monoïde es dich multiplicatiu :
    s'escriu : x · y o x y en plaça de : $\ x*y$
L'element neutre se nòta "1$_E$" o simplament "1" (element unitat de E).

#### Monoïde additiu

Quand la lèi dins E se nòta additivament, lo monoïde es dich additiu :
    s'escriu : x + y en plaça de : $\ x*y$
L'element neutre se nòta "0$_E$" o simplament "0" (element nul, o zèro de E).
Se convèn qu'un monoïde additiu es totjorn commutatiu (s'emplega jamai la notacion additiva per un monoïde non commutatiu).

### Exemples

* Lo magma $(\mathbb {N} ,\,+)$ es un monoïde commutatiu que son element neutre es 0.
* Lo magma $(\mathbb {N} ,\times )$ es un monoïde commutatiu que son element neutre es 1.
* Siá A un ensemble finit (e qu'a aumens dos elements) : serà convencionalament sonat alfabet e seis elements letras de l'alfabet A. Per tot entier naturau non nul n, se sòna mot de longor n subre l'alfabet A un n-uplet d'elements de A, element de A$^n$ (poténcia cartesiana) : es constituit de n letras ; de mai, se definís lo mot vuege, notat "1", que sa longor es 0, e l'ensemble A$^0$ = {1} . Ansin, l'ensemble :
    ${\mathcal {L}}(A)=A^{0}\cup A^{1}\cup A^{2}\cdots \cup A^{n}\cdots$ es l'ensemble de totei lei mots subre l'alfabet A. La juxtaposicion (o concatenacion) es una lèi dins ${\mathcal {L}}(A)$ : estent dos mots x, y, se s'escriu x seguit de y, se definís un tresen mot que se pòt notar x y. Ansin, provesit d'aquela lèi manifestament associativa, ${\mathcal {L}}(A)$ es un monoïde, non commutatiu, qu'a 1 (lo mot vuege) per element neutre : se ditz qu'es lo monoïde libre engendrat per l'alfabet A.
* Siá ${\mathcal {E}}={\mathcal {P}}(\Omega )$ l'ensemble dei partidas d'un ensemble $\ \Omega$ .
** Lo magma $\ ({\mathcal {E}},\cup \,)$ es un monoïde commutatiu qu'a per element neutre l'ensemble vuege $\varnothing$ .
** Lo magma $\ ({\mathcal {E}},\cap \,)$ es un monoïde commutatiu qu'a per element neutre l'ensemble $\ \Omega$ .
* Sián A un ensemble non vuege, e $\ {\mathcal {E}}=A^{A}$ l'ensemble deis aplicacions $\ A\to A$ . La composicion deis aplicacions es una lèi dins ${\mathcal {E}}$ . Lo magma $\ ({\mathcal {E}},\,\circ )$ es un monoïde qu'a per element neutre l'aplicacion identica de A. Es pas commutatiu, levat lo cas que A a ren qu'un element (valent a dire qu'es un singleton).

## Sosmonoïde

Sián $(E,\,*)$ un monoïde d'element neutre e, e A una partida de E tala que :
   * $\ e\in A$
   * $\forall \,(x,\,y)\in A^{2},\;x*y\in A$ , valent a dire que A es establa per la lèi de E
Alora, la lèi " $\ *'$ " inducha sus A es associativa, e lo pareu $(A,\,*')$ es un monoïde, qu'es sonat sosmonoïde de $(E,\,*)$ .

### Exemples

* L'ensemble $\ \{e\}$ , provesit de la lèi inducha, es un sosmonoïde de $(E,\,*)$ .
* L'ensemble A deis entiers naturaus pars, provesit de l'addicion, es un sosmonoïde dau monoïde $(\mathbb {N} ,\,+)$ .
* L'ensemble ${\mathcal {A}}$ dei foncions afinas es un sosmonoïde dau monoïde $\ ({\mathcal {E}},\,\circ )$ , onte ${\mathcal {E}}$ es l'ensemble dei foncions $\mathbb {R} \to \mathbb {R}$ : se saup que ${\mathcal {A}}$ es estable per composicion, e de mai l'element neutre, çò es la foncion identica de $\mathbb {R}$ , es una foncion afina.

## Elements simetrizables d'un monoïde

Un element x de E es dich simetrizable s'existís un element x' de E tau que :
    $\ x*x'=e\quad \mathrm {e} \quad x'*x=e$
Dins aqueu cas, l'element x' (que son unicitat serà provada infra) es sonat element simetric de x, o simetric de x.
Notacions
* dins lo cas d'una lèi notada multiplicativament, se ditz generalament invertible per simetrizable ; lo simetric d'un element invertible x es sonat invèrs de x e es generalament notat $x^{-1}$ ; per tot element invertible x de E :
    x x' = $1_{E}$ , e x' x = $1_{E}$
* dins lo cas d'una lèi notada additivament, lo simetric d'un element simetrizable x es sonat opausat de x e x' es generalament notat −x ;
    per tot element simetrizable x de E :
    x + x' = $0_{E}$ , e x' + x = $0_{E}$

### Exemples

* dins lo monoïde $(\mathbb {N} ,\,+)$, lo solet element simetrizable es 0, qu'es son pròpri opausat
* dins lo monoïde $(\mathbb {N} ,\,\times )$, lo solet element invertible es 1, qu'es son pròpri invèrs
* dins lo monoïde $(A^{A},\circ )$, leis elements simetrizables son leis aplicacions bijectivas $f:A\to A$ ; lo simetric d'una bijeccion f es la bijeccion recipròca $f^{-1}$ .

### Unicitat de l'element simetric

Per tot element simetrizable d'un monoïde, l'element simetric es unic.
D'efècte, sián x un element simetrizable de E, e x' , x" de simetrics de x :
    $x*x'=e\quad \mathrm {e} \quad x'*x=e$
    $x*x''=e\quad \mathrm {e} \quad x''*x=e\;$
Se considèra alora l'element $\ y=x'*x*x''$ de E ; per associativitat : $\ y=(x'*x)*x''=x'*(x*x'')$
* coma $\ x'*x=e$ , $\ y=(x'*x)*x''=e*x''=x''$
* coma $\ x*x''=e$ , $\ y=x'*(x*x'')=x'*e=x'$
* en conclusion, y = x' e y = x" . Se'n dedutz l'egalitat x' = x ", valent a dire l'unicitat de l'element simetric de x.

### Ensemble deis elements simetrizables d'un monoïde

Siá G l'ensemble deis elements simetrizables d'un monoïde $(E,\,*)$ .
* l'element neutre e apartèn a G e coïncidís amb son simetric : e' = e ; ansin G es non vuege
* se x, y apartènon a G, alora $\ x*y$ apartèn a G e son simetric es : $\ (x*y)'=y'*x'$
* se x apartèn a G, x' apartèn tanben a G e cadun d'elei es lo simetric de l'autre.
Aquelei proprietats fan de G, provesit de la lèi inducha, un grop qu'es un sosmonoïde de $(E,\,*)$ .

## Iteracion de la lèi de composicion intèrna d'un monoïde

Siá un monoïde $(E,\,*)$ d'element neutre e. Còmpte tengut de l'associativitat de la lèi de E, se pòt definir sens ambigüitat un element de E notat $x_{1}*x_{2}*\cdots *x_{n}$ , onte $x_{1}$ , $x_{2}$ , ... , $x_{n}$ son d'elements de E, quin que siá lo nombre n :
* se n = 1 o n = 2, la definicion pausa ges de problèma
* se generaliza per recurréncia subre n :
    estent n + 1 elements $x_{1}$ , ... , $x_{n+1}$ de E, se definís ansin l'element $x_{1}*\cdots *x_{n}*x_{n+1}$ :
    $x_{1}*\cdots *x_{n}*x_{n+1}=(x_{1}*\cdots *x_{n})*x_{n+1}$
L'associativitat permete de plaçar lei parentèsis coma se vòu. Per exemple, se n = 4,
    per definicion : $x_{1}*x_{2}*x_{3}*x_{4}=(x_{1}*x_{2}*x_{3})*x_{4}=((x_{1}*x_{2})*x_{3})*x_{4}$
    mai tanben : $x_{1}*x_{2}*x_{3}*x_{4}=(x_{1}*x_{2})*(x_{3}*x_{4})=x_{1}*(x_{2}*x_{3})*x_{4}$ , etc.

### Iterats d'un element per la lèi dau monoïde

Siá x un element de E. Per tot entier naturau n diferent de 0, se definís :
    $x^{[n]}=x_{1}*\cdots *x_{n}$ , onte $x_{1}=x_{2}=\dots =x_{n}=x$
Autrament dich :
    $x^{[n]}=x*\cdots *x$ (onte lo nombre d'operands, toteis egaus, es n )
Se completa la definicion en pausant :
    $\ x^{[0]}=e$ (l'element neutre)
Per exemple :
    $\ x^{[1]}=x$ , $\ x^{[2]}=x*x$ , $\ x^{[3]}=x*x*x=(x*x)*x=x*(x*x)=x^{[2]}*x=x*x^{[2]}$ .
L'aplicacion $\ \mathbb {N} \times E\to E,\,(n,\,x)\mapsto x^{[n]}$ es un exemple de lèi de composicion extèrna dins E.
Per tot pareu (n, p ) d'entiers naturaus :
    $\ x^{[n]}*x^{[p]}=x^{[n+p]}$

#### Cas deis elements simetrizables

Coma supra, se nòta G l'ensemble deis elements simetrizables dau monoïde, e x' lo simetric d'un element x de G.
Se x apartèn a G, alora per tot entier naturau m :
    $x^{[m]}$ apartèn tanben a G e :
    $\left(x^{[m]}\right)'=(x'\,)^{[m]}$
Se definís alora $x^{[-m]}$ en pausant :
    $x^{[-m]}=\left(x^{[m]}\right)'=(x'\,)^{[m]}$
En particular, $x'=x^{[-1]}$ .
L'aplicacion $\ \mathbb {Z} \times G\to G,\,(n,\,x)\mapsto x^{[n]}$ es un exemple de lèi de composicion extèrna dins G.
Se x es simetrizable, alora per tot pareu (n, p ) d'entiers :
    $\ x^{[n]}*x^{[p]}=x^{[n+p]}$
Per exemple :
    $\ x^{[-3]}*x^{[2]}=x^{[-1]}=x'$

### Notacions
#### Monoïde multiplicatiu

Dins lo cas d'un monoïde multiplicatiu :
* l'element $x_{1}*x_{2}*\cdots *x_{n}$ es sonat produch de $x_{1},x_{2},\dots x_{n}$ e se nòta :
    $x_{1}\;x_{2}\cdots x_{n}$ o ben $\prod _{i=1}^{n}x_{i}$
* per tot pareu (x, n), ont x es dins E e n es un entier naturau, s'escriu $x^{n}$ en luòga de $x^{[n]}$ ; se ditz qu'es la poténcia d'exponent n de x.
** $x^{0}=1_{E}$ (l'element neutre), $x^{1}=x$ ; $x^{2}$ = $x$ $x$ es lo carrat de x ...
** $x^{n}$ $x^{p}$ = $x^{n+p}$ per tot pareu (n, p ) d'entiers naturaus
* per tot pareu (x, n), ont x es un element invertible de E e n es un entier, s'escriu tanben $x^{n}$ en luòga de $x^{[n]}$
** per exemple, l'invèrs de x es $x'=x^{-1}$ , çò que justifica aquesta notacion usuala de l'invèrs
** se m es un entier naturau : $x^{-m}=(x^{-1})^{m}=\left(x^{m}\right)^{-1}$
** $x^{n}$ $x^{p}$ = $x^{n+p}$ per tot pareu (n, p ) d'entiers

#### Monoïde additiu

Dins lo cas d'un monoïde additiu :
* l'element $x_{1}*x_{2}*\cdots *x_{n}$ es sonat soma de $x_{1},x_{2},\dots x_{n}$ e se nòta :
    $x_{1}+x_{2}+\cdots +x_{n}$ o ben $\sum _{i=1}^{n}x_{i}$
* per tot pareu (x, n), ont x es dins E e n es un entier naturau, s'escriu n x en luòga de $x^{[n]}$ ; se ditz qu'es lo multiple de coefficient n de x.
** 0 x = $0_{E}$ (l'element neutre), 1 x = x ; 2 x = x + x es lo doble de x ...
** n x + p x = (n + p) x per tot pareu (n, p ) d'entiers naturaus
* per tot pareu (x, n), ont x es un element simetrizable de E e n es un entier, s'escriu tanben n x en luòga de $x^{[n]}$
** per exemple, l'opausat de x es x' = (−1) x, notat : −x
** se m es un entier naturau : (−m) x = m (−x) = − (m x)
** n x + p x = (n + p) x per tot pareu (n, p ) d'entiers

## Morfisme de monoïdes

Un morfisme de monoïdes es una aplicacion compatibla amb l'estructura algebrica.

### Definicions

* Sián dos monoïdes $(E,\,\ast )$ (d'element neutre e) e $(F,\,\star )$ (d'element neutre f) . Un morfisme de $(E,\,*)$ vèrs $(F,\,\star )$ es per definicion una aplicacion $\varphi :E\to F$ tala que
* $\ \forall (x,\,y)\in E^{2},\;\varphi (x*y)=\varphi (x)\star \varphi (y)$
* $\varphi (e)=f$ (leis elements neutres se correspòndon per $\varphi$ )
* Lo nuclèu dau morfisme $\varphi$ , notat $\ker(\varphi )$ , es lo sosensemble de E ansin definit :
    $\ker(\varphi )=\{x\in E\mid \varphi (x)=f\}$
* Un isomorfisme de monoïdes es un morfisme bijectiu.
* Se ditz que dos monoïdes son isomòrfs s'existís un isomorfisme d'un vèrs l'autre (aiçò significa qu'an exactament lei meteissei proprietats algebricas : per exemple, s'un dei dos es commutatiu, ansin es de l'autre) ; dau ponch de vista de l'algèbra, dos monoïdes isomòrfs son indestriables.

### Proprietats

* Siá un morfisme $\varphi$ de $(E,\,*)$ vèrs $(F,\,\star )$. Alora :
** Per tot pareu (x, n) onte x es dins E e n es un entier naturau : $\varphi \left(x^{[n]}\right)=(\varphi (x))^{\,[n]}\quad \scriptstyle {(\clubsuit )}$
** Se x es un element simetrizable de E, $\varphi (x)$ es un element simetrizable de F, e $\varphi \left(x'\right)=\varphi (x)'$
** La relacion ($\quad \scriptstyle {\clubsuit }$) supra se generaliza au cas que x es un element simetrizable de E e n es un entier.
* L'aplicacion identica de E es un morfisme de $(E,\,*)$ vèrs $(E,\,*)$.
* La compausada de dos morfismes de monoïdes es un morfisme de monoïdes : estent tres monoïdes $(E,\,*)$ , $(F,\,\star )$ , $(G,\,\diamond )$ e dos morfismes $\varphi$ de $(E,\,*)$ vèrs $(F,\,\star )$ , $\ \psi$ de $(F,\,\star )$ vèrs $(G,\,\diamond )$, l'aplicacion compausada $\psi \circ \varphi$ es un morfisme de $(E,\,*)$ vèrs $(G,\,\diamond )$. En particular, la compausada de dos isomorfismes de monoïdes es un isomorfisme de monoïdes.
* L'imatge d'un morfisme de monoïdes es un sosmonoïde. Pus generalament, l'imatge d'un sosmonoïde per un morfisme de monoïdes es un sosmonoïde.
* L'imatge invèrs d'un sosmonoïde per un morfisme de monoïdes es un sosmonoïde. En particular, lo nuclèu es un sosmonoïde.
* La bijeccion recipròca d'un isomorfisme de $(E,\,*)$ vèrs $(F,\,\star )$ es un isomorfisme de $(F,\,\star )$ vèrs $(E,\,*)$.

### Exemples e còntraexemple

* L'aplicacion $\varphi :\mathbb {N} \to A,\,n\mapsto 2\,n$ es un isomorfisme dau monoïde (N, +) vèrs lo monoïde (A, +) deis entiers naturaus pars.
* Siá ${\mathcal {E}}={\mathcal {P}}(\Omega )$ (cf. supra). Lei monoïdes $\ ({\mathcal {E}},\cup \,)$ , $\ ({\mathcal {E}},\cap \,)$ son isomòrfs. D'efècte, per tot sosensemble A de $\Omega$ , notem ${\overline {A}}$ lo complementari de A (dins $\Omega$ ) : ${\overline {A}}=\Omega \setminus A$ . L'aplicacion $\varphi :{\mathcal {E}}\to {\mathcal {E}},\;A\mapsto {\overline {A}}$ es un isomorfisme de monoïdes :
** Es bijectiva.
** Per tot pareu (A, B) d'elements de ${\mathcal {E}}$ , ${\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}$ (formula de De Morgan), çò es : $\varphi (A\cup B)=\varphi (A)\cap \varphi (B)$.
** ${\overline {\varnothing }}=\Omega$ , autrament dich : $\varphi (\varnothing )=\Omega$ (lei dos elements neutres se correspòndon).
* Lei dos monoïdes $(\mathbb {N} ,\,+)$ e $(\mathbb {N} ^{\ast },\,\times )$ (onte $\mathbb {N} ^{\ast }=\mathbb {N} \setminus \{0\}$ ) son pas isomòrfs. Se demòstra per reduccion a l'absurde, en supausant l'existéncia d'un isomorfisme $\varphi$ :
** Es una bijeccion $\varphi :\mathbb {N} \to \mathbb {N} ^{\ast }$.
** Per tot pareu (n, p) d'entiers naturaus, $\varphi (n+p)=\varphi (n)\,\varphi (p)$.
** $\varphi (0)=1$ (leis elements neutres se correspòndon)
    Pausem $g=\varphi (1)$ ;$g\in \mathbb {N} ^{\ast }$ e (per injectivitat de $\varphi$ ), $g\neq \varphi (0)$ , donc $g\geq 2$ .
    Per tot entier naturau n, $\varphi (n)=g^{n}$ (demostracion dirècta per recurréncia subre n, o utilizacion de proprietats enonciadas supra). Coma $\varphi$ es bijectiva, per tot element m de $\mathbb {N} ^{\ast }$ existís un entier naturau (unic) n tau que
       $m=\varphi (n)=g^{n}$.
    En particular (en chausissent l'element m = g +1), existís un entier naturau n tau que $\ g^{n}=g+1$ ;
    necessariament, n ≠ 0, donc g es un divisor de $g^{n}$ , a fortiori de $g^{n}-g=1$ ; es absurde, car g es estrictament superior a 1.

## Monoïde quocient per una congruéncia

Una congruéncia dins un monoïde $(E,\,*)$ (d'element neutre e) es una relacion d'equivaléncia "$\ \sim$" compatibla amb l'estructura algebrica.
Aiçò significa que :
* La relacion binària "$\ \sim$" es una relacion d'equivaléncia dins E ; la classa (d'equivaléncia) de tot element x de E se notarà : [x].
* Per tot triplet (x, x' , y) d'elements de E : $\ x\sim x'$ implica $\ x*y\sim x'*y$ e $\ y*x\sim y*x'$
Se'n dedutz que per tota lista (x, x' , y, y' ) d'elements de E :
    $\ x\sim x'$ e $\ y\sim y'$ implican : $\ x*y\sim x'*y'$ ;
Autrament dich, la classa de l'element $\ x*y$ depende unicament de la classa de x e de la classa de y : ansin, se pòt definir sens ambigüitat una lèi de composicion intèrna dins l'ensemble dei classas, çò es l'ensemble quocient $E\,/\sim$ , en pausant :
    $[x]\;{\overline {*}}\;[y]=[x*y]$
Es de bòn verificar que lo magma $(E\,/\sim \,,\,{\overline {*}})$ es un monoïde qu'a per element neutre la classa [e] de l'element neutre de E. Se sòna monoïde quocient de $(E,\,*)$ per la congruéncia "$\ \sim$" .
L'aplicacion canonica : $\pi :E\to E\,/\sim \,,\,x\mapsto [x]$ es un morfisme subrejectiu de monoïdes ; son nuclèu es la classa de l'element neutre de E, considerada aicí coma un sosensemble de E (e en fach n'es un sosmonoïde).

## Vejatz tanben

* Lèi de composicion intèrna
* Relacion d'equivaléncia