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*</math> de *E* ; *'per associativitat** : <math>\ y = (x' * x) * x'' = x' * (x * x'')</math>

* coma <math>\ x' * x = e</math> , <math>\ y = (x' * x) * x'' = e * x'' = x''</math>

* coma <math>\ x * x'' = e</math> , <math>\ y = x' * (x * x'') = x' * e = x'</math>

* 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 <math>(E,\, *)</math> .
* 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 <math>\ x * y</math> apartèn a ''G'' e son simetric es : <math>\ (x * y)' = y' * x'</math>

* 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 <math>(E,\, *)</math> .

==Iteracion de la lèi de composicion intèrna d'un monoïde==
Siá un monoïde <math>(E,\, *)</math> 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 <math>x_1 * x_ 2 * \cdots * x_n</math> , onte <math>x_1</math> , <math>x_2</math> , ... , <math>x_n</math> 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 <math>x_1</math> , ... , <math>x_{n + 1}</math> de ''E'', se definís ansin l'element <math>x_1  * \cdots * x_n * x_{n + 1}</math> :
: <math>x_1  * \cdots * x_n * x_{n + 1} = (x_1 * \cdots * x_n)  * x_{n + 1}</math>

L'associativitat permete de plaçar lei parentèsis coma se vòu. Per exemple, se ''n'' = 4,
: per definicion : <math>x_1 * x_2 * x_3 * x_4 = (x_1 * x_2 * x_3) * x_4 = ((x_1 * x_2) * x_3) * x_4</math>
: mai tanben : <math>x_1 * x_2 * x_3 * x_4 = (x_1 * x_2) * (x_3 * x_4) = x_1 * (x_2 * x_3) * x_4</math> , 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 :
: <math>x^{[n]} = x_1  * \cdots * x_n</math> , onte <math>x_1 = x_2 = \dots = x_n = x</math>
Autrament dich :
: <math>x^{[n]} = x  * \cdots * x</math> (onte lo nombre d'operands, toteis egaus, es ''n'' )
Se completa la definicion en pausant :
: <math>\ x^{[0]} = e</math> (l'element neutre)
Per exemple :
: <math>\ x^{[1]} = x</math> , <math>\ x^{[2]} = x * x</math> , <math>\ x^{[3]} = x * x * x = (x * x) * x = x * (x * x) = x^{[2]} * x = x * x^{[2]} </math> .

L'aplicacion <math>\ \mathbb{N} \times E \to E,\, (n,\, x) \mapsto x^{[n]}</math> es un exemple de [[lèi de composicion extèrna]] dins ''E''.


Per tot pareu (''n'', ''p'' ) d'entiers naturaus :
: <math>\ x^{[n]} * x^{[p]} = x^{[n + p]} </math>

====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'' :
: <math>x^{[m]}</math> apartèn tanben a ''G'' e :
: <math>\left(x^{[m]}\right)' = (x'\,)^{[m]}</math>
Se definís alora <math>x^{[-m]}</math> en pausant :
: <math> x^{[-m]} = \left(x^{[m]}\right)' = (x'\,)^{[m]} </math>
En particular, <math>x' = x^{[-1]}</math> .

L'aplicacion <math>\ \mathbb{Z} \times G \to G,\, (n,\, x) \mapsto x^{[n]}</math> es un exemple de [[lèi de composicion extèrna]] dins ''G''.


Se ''x'' es simetrizable, alora per tot pareu (''n'', ''p'' ) d'entiers :
: <math>\ x^{[n]} * x^{[p]} = x^{[n + p]} </math>
Per exemple :
: <math>\ x^{[-3]} * x^{[2]} = x^{[-1]} = x' </math>

===Notacions===
====Monoïde multiplicatiu====
Dins lo cas d'un monoïde multiplicatiu :
* l'element <math>x_1 * x_ 2 * \cdots * x_n</math> es sonat **produch** de <math>x_1, x_2, \dots x_n</math> e se nòta :
: <math>x_1 \; x_2 \cdots x_n</math> o ben <math>\prod_{i = 1}^n x_i</math>

* per tot pareu (''x'', ''n''), ont ''x'' es dins ''E'' e ''n'' es un entier naturau, s'escriu <math>x^n</math> en luòga de <math>x^{[n]}</math> ; se ditz qu'es la **poténcia d'exponent** ''n'' de ''x''.
** <math>x^0 = 1_E</math> (l'element neutre), <math>x^1 = x</math> ; <math>x^2</math> = <math>x</math>  <math>x</math> es lo **carrat** de ''x'' ...
** <math>x^n</math> <math>x^p</math> = <math>x^{n + p}</math> 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 <math>x^n</math> en luòga de <math>x^{[n]}</math>
** per exemple, l'invèrs de ''x'' es <math>x' = x^{-1}</math> , çò que justifica aquesta notacion usuala de l'invèrs
** se ''m'' es un entier naturau : <math>x^{-m} = (x^{-1})^m = \left(x^m\right)^{-1}</math>
** <math>x^n</math> <math>x^p</math> = <math>x^{n + p}</math> per tot pareu (''n'', ''p'' ) d'entiers

====Monoïde additiu ====
Dins lo cas d'un monoïde additiu :
* l'element <math>x_1 * x_ 2 * \cdots * x_n</math> es sonat **soma** de <math>x_1, x_2, \dots x_n</math> e se nòta :
: <math>x_1 + x_2 + \cdots + x_n</math> o ben <math>\sum_{i = 1}^n x_i</math>

* per tot pareu (''x'', ''n''), ont ''x'' es dins ''E'' e ''n'' es un entier naturau, s'escriu ''n'' ''x'' en luòga de <math>x^{[n]}</math> ; se ditz qu'es lo **multiple de coefficient** ''n'' de ''x''.
** 0 ''x'' = <math>0_E</math> (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 <math>x^{[n]}</math>
** 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 (matematicas)|aplicacion]] compatibla amb l'estructura algebrica.

===Definicions===
* Sián dos monoïdes <math>(E,\, \ast)</math> (d'element neutre ''e'') e <math>(F,\, \star)</math> (d'element neutre ''f'') . Un **morfisme** de <math>(E,\, *)</math> vèrs <math>(F,\, \star)</math> es per definicion una aplicacion <math>\varphi : E \to F</math> tala que
# <math>\ \forall (x,\, y)\in E^2,\; \varphi(x * y) =\varphi(x) \star \varphi(y)</math>
# <math> \varphi(e) =f</math> (leis elements neutres se correspòndon per <math>\varphi</math> )

* Lo **nuclèu** dau morfisme <math>\varphi</math> , notat <math>\ker(\varphi)</math> , es lo sosensemble de ''E'' ansin definit :
: <math>\ker(\varphi) = \{ x \in E \mid \varphi(x) = f\}</math>

* Un **isomorfisme** de monoïdes es un morfisme [[bijeccion|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 <math>\varphi</math> de <math>(E,\, *)</math> vèrs <math>(F,\, \star)</math>. Alora :
** Per tot pareu (''x'', ''n'') onte ''x'' es dins ''E'' e ''n'' es un entier naturau : <math>\varphi\left(x^{[n]}\right) = (\varphi(x))^{\,[n]} \quad \scriptstyle{(\clubsuit)}</math>
** Se ''x'' es un element simetrizable de ''E'', <math>\varphi(x)</math> es un element simetrizable de ''F'', e <math>\varphi\left(x'\right) = \varphi(x)'</math>
** La relacion (<math>\quad\scriptstyle{\clubsuit}</math>) ''supra'' se generaliza au cas que ''x'' es un element simetrizable de ''E'' e ''n'' es un entier.

* L'[[aplicacion (matematicas)#Aplicacion identica d'un ensemble X|aplicacion identica]] de ''E'' es un morfisme de <math>(E,\, *)</math> vèrs <math>(E,\, *)</math>.

* La [[aplicacion (matematicas)#Composicion d'aplicacions|compausada]] de dos morfismes de monoïdes es un morfisme de monoïdes :<br> estent tres monoïdes <math>(E,\, *)</math> , <math>(F,\, \star)</math> , <math>(G,\, \diamond)</math> e dos morfismes <math>\varphi</math> de <math>(E,\, *)</math> vèrs <math>(F,\, \star)</math> , <math>\ \psi </math> de <math>(F,\, \star)</math> vèrs <math>(G,\, \diamond)</math>, l'aplicacion compausada <math> \psi \circ \varphi</math> es un morfisme de <math>(E,\, *)</math> vèrs <math>(G,\, \diamond)</math>. <br> En particular, la compausada de dos isomorfismes de monoïdes es un isomorfisme de monoïdes.

* L'[[aplicacion (matematicas)#Imatge d'una aplicacion|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'[[aplicacion (matematicas)#Imatge invèrs|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 <math>(E,\, *)</math> vèrs <math>(F,\, \star)</math> es un isomorfisme de <math>(F,\, \star)</math> vèrs <math>(E,\, *)</math>.

===Exemples e còntraexemple===
* L'aplicacion <math>\varphi : \mathbb{N} \to A,\, n \mapsto 2\, n</math> es un isomorfisme dau monoïde (**N**, +) vèrs lo monoïde (''A'', +) deis entiers naturaus pars.
* Siá <math>\mathcal{E} = \mathcal{P}(\Omega)</math> (cf. ''supra''). Lei monoïdes <math>\ (\mathcal{E}, \cup\,)</math> , <math>\ (\mathcal{E}, \cap\,)</math> son isomòrfs. D'efècte, per tot sosensemble ''A'' de <math>\Omega</math> , notem <math>\overline{A}</math> lo [[ensemble complementari|complementari]] de ''A'' (dins <math>\Omega</math> ) : <math>\overline{A} = \Omega \setminus A</math> . L'aplicacion <math>\varphi : \mathcal{E} \to \mathcal{E},\; A \mapsto \overline{A} </math> es un isomorfisme de monoïdes :
** Es bijectiva.
** Per tot pareu (''A'', ''B'') d'elements de <math>\mathcal{E}</math> , <math>\overline{A \cup B} = \overline{A} \cap \overline{B}</math> (formula de De Morgan), çò es : <math>\varphi(A \cup B) = \varphi(A) \cap \varphi(B)</math>.
** <math>\overline{\varnothing} = \Omega</math> , autrament dich : <math>\varphi(\varnothing) = \Omega</math> (lei dos elements neutres se correspòndon).

* Lei dos monoïdes <math>(\mathbb{N},\, +)</math> e <math>(\mathbb{N}^\ast,\, \times)</math> (onte <math>\mathbb{N}^\ast = \mathbb{N} \setminus \{0\}</math> ) son pas isomòrfs. Se demòstra per [[reduccion a l'absurde]], en supausant l'existéncia d'un isomorfisme <math>\varphi</math> :
** Es una bijeccion <math>\varphi : \mathbb{N} \to \mathbb{N}^\ast </math>.
** Per tot pareu (''n'', ''p'') d'entiers naturaus, <math>\varphi(n + p) = \varphi(n)\, \varphi(p)</math>.
** <math>\varphi(0) = 1</math> (leis elements neutres se correspòndon)
: Pausem <math>g = \varphi(1)</math> ;<math>g \in \mathbb{N}^\ast</math> e (per injectivitat de <math>\varphi</math> ), <math>g \neq \varphi(0)</math> , donc <math>g \geq 2</math> .
: Per tot entier naturau ''n'', <math>\varphi(n) = g^n</math> (demostracion dirècta per recurréncia subre ''n'', o utilizacion de proprietats enonciadas ''supra''). Coma <math>\varphi</math> es bijectiva, per tot element ''m'' de <math>\mathbb{N}^\ast</math> existís un entier naturau (unic) ''n'' tau que
::<math>m = \varphi(n) = g^n</math>.
: En particular (en chausissent l'element ''m'' = ''g'' +1), existís un entier naturau ''n'' tau que <math>\ g^n = g +1</math> ;
: necessariament, ''n''  ≠ 0, donc ''g'' es un [[divisor]] de <math>g^n</math> , ''a fortiori'' de <math>g^n - g = 1</math> ; es absurde, car ''g'' es estrictament superior a 1.

== Monoïde quocient per una congruéncia ==
Una **congruéncia** dins un monoïde <math>(E,\, *)</math> (d'element neutre ''e'') es una relacion d'equivaléncia "<math>\ \sim</math>" compatibla amb l'estructura algebrica.

Aiçò significa que :
# La relacion binària "<math>\ \sim</math>" es una [[relacion d'equivaléncia]] dins ''E'' ; la [[relacion d'equivaléncia#Classas d'equivaléncia|classa (d'equivaléncia)]] de tot element ''x'' de ''E'' se notarà : [''x''].
# Per tot triplet (''x'', ''x' '', ''y'') d'elements de ''E'' : <math>\ x \sim x'</math> implica <math>\ x * y \sim x' * y</math> e <math>\ y * x \sim y * x'</math>
Se'n dedutz que per tota lista (''x'', ''x' '', ''y'', ''y' '') d'elements de ''E'' :
: <math>\ x \sim x'</math> e <math>\ y \sim y'</math> implican : <math>\ x * y \sim x' * y'</math> ;
Autrament dich, la classa de l'element <math>\ x * y</math> 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 <math>E\, / \sim</math> , en pausant :
: <math>[x]\; \overline{*}\; [y] = [x * y]</math>
Es de bòn verificar que lo magma <math>(E\, / \sim\,,\, \overline{*})</math> 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 <math>(E,\, *)</math> per la congruéncia "<math>\ \sim</math>" .

L'aplicacion canonica :
<math>\pi : E \to E\, / \sim\,,\, x \mapsto [x]</math>
es un morfisme [[subrejeccion|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