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ⁿ (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⁰ = {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 :

1. $\ e\in A$
2. $\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

1. $\ \forall (x,\,y)\in E^{2},\;\varphi (x*y)=\varphi (x)\star \varphi (y)$
2. $\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 :

1. 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].
2. 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