Monoïde

Pus explicitament, un monoïde es un pareu ${\displaystyle (E,\,*)}$  , onte E es un ensemble, e " ${\displaystyle \ *}$  " es una lèi (de composicion intèrna) dins E, associativa e admetent un element neutre :

• ${\displaystyle \forall (x,\,y)\in E^{2},\;x*y\in E}$  (lèi de composicion intèrna)

• ${\displaystyle \forall (x,\ y,\ z)\in E^{3},\;(x*y)*z=x*(y*z)}$  (associativitat)

• ${\displaystyle \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 :

• ${\displaystyle \forall (x,\,y)\in E^{2},\;x*y=y*x}$  (commutativitat)

La notacion multiplicativa e la notacion additiva son particularament frequentas.

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 : ${\displaystyle \ x*y}$ 

L'element neutre se nòta "1_E" o simplament "1" (element unitat de E).

Quand la lèi dins E se nòta additivament, lo monoïde es dich additiu :

s'escriu : x + y en plaça de : ${\displaystyle \ 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).

• Lo magma ${\displaystyle (\mathbb {N} ,\,+)}$  es un monoïde commutatiu que son element neutre es 0.

• Lo magma ${\displaystyle (\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 :

${\displaystyle {\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 ${\displaystyle {\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, ${\displaystyle {\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á ${\displaystyle {\mathcal {E}}={\mathcal {P}}(\Omega )}$  l'ensemble dei partidas d'un ensemble ${\displaystyle \ \Omega }$  .
  • Lo magma ${\displaystyle \ ({\mathcal {E}},\cup \,)}$  es un monoïde commutatiu qu'a per element neutre l'ensemble vuege ${\displaystyle \varnothing }$  .
  • Lo magma ${\displaystyle \ ({\mathcal {E}},\cap \,)}$  es un monoïde commutatiu qu'a per element neutre l'ensemble ${\displaystyle \ \Omega }$  .

• Sián A un ensemble non vuege, e ${\displaystyle \ {\mathcal {E}}=A^{A}}$  l'ensemble deis aplicacions ${\displaystyle \ A\to A}$  . La composicion deis aplicacions es una lèi dins ${\displaystyle {\mathcal {E}}}$  . Lo magma ${\displaystyle \ ({\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).

Sián ${\displaystyle (E,\,*)}$  un monoïde d'element neutre e, e A una partida de E tala que :

1. ${\displaystyle \ e\in A}$ 
2. ${\displaystyle \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 " ${\displaystyle \ *'}$  " inducha sus A es associativa, e lo pareu ${\displaystyle (A,\,*')}$  es un monoïde, qu'es sonat sosmonoïde de ${\displaystyle (E,\,*)}$  .

• L'ensemble ${\displaystyle \ \{e\}}$  , provesit de la lèi inducha, es un sosmonoïde de ${\displaystyle (E,\,*)}$  .

• L'ensemble A deis entiers naturaus pars, provesit de l'addicion, es un sosmonoïde dau monoïde ${\displaystyle (\mathbb {N} ,\,+)}$  .

• L'ensemble ${\displaystyle {\mathcal {A}}}$  dei foncions afinas es un sosmonoïde dau monoïde ${\displaystyle \ ({\mathcal {E}},\,\circ )}$  , onte ${\displaystyle {\mathcal {E}}}$  es l'ensemble dei foncions ${\displaystyle \mathbb {R} \to \mathbb {R} }$  : se saup que ${\displaystyle {\mathcal {A}}}$  es estable per composicion, e de mai l'element neutre, çò es la foncion identica de ${\displaystyle \mathbb {R} }$  , es una foncion afina.

Un element x de E es dich simetrizable s'existís un element x' de E tau que :

${\displaystyle \ 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 ${\displaystyle x^{-1}}$  ; per tot element invertible x de E :

x x' = ${\displaystyle 1_{E}}$  , e x' x = ${\displaystyle 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' = ${\displaystyle 0_{E}}$  , e x' + x = ${\displaystyle 0_{E}}$ 

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

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 :

${\displaystyle x*x'=e\quad \mathrm {e} \quad x'*x=e}$ 

${\displaystyle x*x''=e\quad \mathrm {e} \quad x''*x=e\;}$ 

Se considèra alora l'element ${\displaystyle \ y=x'*x*x''}$  de E ; per associativitat : ${\displaystyle \ y=(x'*x)*x''=x'*(x*x'')}$ 

• coma ${\displaystyle \ x'*x=e}$  , ${\displaystyle \ y=(x'*x)*x''=e*x''=x''}$ 

• coma ${\displaystyle \ x*x''=e}$  , ${\displaystyle \ 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.

Siá G l'ensemble deis elements simetrizables d'un monoïde ${\displaystyle (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 ${\displaystyle \ x*y}$  apartèn a G e son simetric es : ${\displaystyle \ (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 ${\displaystyle (E,\,*)}$  .

Siá un monoïde ${\displaystyle (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 ${\displaystyle x_{1}*x_{2}*\cdots *x_{n}}$  , onte ${\displaystyle x_{1}}$  , ${\displaystyle x_{2}}$  , ... , ${\displaystyle 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 ${\displaystyle x_{1}}$  , ... , ${\displaystyle x_{n+1}}$  de E, se definís ansin l'element ${\displaystyle x_{1}*\cdots *x_{n}*x_{n+1}}$  :

${\displaystyle 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 : ${\displaystyle 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 : ${\displaystyle 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.

Siá x un element de E. Per tot entier naturau n diferent de 0, se definís :

${\displaystyle x^{[n]}=x_{1}*\cdots *x_{n}}$  , onte ${\displaystyle x_{1}=x_{2}=\dots =x_{n}=x}$ 

Autrament dich :

${\displaystyle x^{[n]}=x*\cdots *x}$  (onte lo nombre d'operands, toteis egaus, es n )

Se completa la definicion en pausant :

${\displaystyle \ x^{[0]}=e}$  (l'element neutre)

Per exemple :

${\displaystyle \ x^{[1]}=x}$  , ${\displaystyle \ x^{[2]}=x*x}$  , ${\displaystyle \ x^{[3]}=x*x*x=(x*x)*x=x*(x*x)=x^{[2]}*x=x*x^{[2]}}$  .

L'aplicacion ${\displaystyle \ \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 :

${\displaystyle \ x^{[n]}*x^{[p]}=x^{[n+p]}}$ 

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 :

${\displaystyle x^{[m]}}$  apartèn tanben a G e :

${\displaystyle \left(x^{[m]}\right)'=(x'\,)^{[m]}}$ 

Se definís alora ${\displaystyle x^{[-m]}}$  en pausant :

${\displaystyle x^{[-m]}=\left(x^{[m]}\right)'=(x'\,)^{[m]}}$ 

En particular, ${\displaystyle x'=x^{[-1]}}$  .

L'aplicacion ${\displaystyle \ \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 :

${\displaystyle \ x^{[n]}*x^{[p]}=x^{[n+p]}}$ 

Per exemple :

${\displaystyle \ x^{[-3]}*x^{[2]}=x^{[-1]}=x'}$ 

Dins lo cas d'un monoïde multiplicatiu :

• l'element ${\displaystyle x_{1}*x_{2}*\cdots *x_{n}}$  es sonat produch de ${\displaystyle x_{1},x_{2},\dots x_{n}}$  e se nòta :

${\displaystyle x_{1}\;x_{2}\cdots x_{n}}$  o ben ${\displaystyle \prod _{i=1}^{n}x_{i}}$ 

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

Dins lo cas d'un monoïde additiu :

• l'element ${\displaystyle x_{1}*x_{2}*\cdots *x_{n}}$  es sonat soma de ${\displaystyle x_{1},x_{2},\dots x_{n}}$  e se nòta :

${\displaystyle x_{1}+x_{2}+\cdots +x_{n}}$  o ben ${\displaystyle \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 ${\displaystyle x^{[n]}}$  ; se ditz qu'es lo multiple de coefficient n de x.
  • 0 x = ${\displaystyle 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 ${\displaystyle 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

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

• Sián dos monoïdes ${\displaystyle (E,\,\ast )}$  (d'element neutre e) e ${\displaystyle (F,\,\star )}$  (d'element neutre f) . Un morfisme de ${\displaystyle (E,\,*)}$  vèrs ${\displaystyle (F,\,\star )}$  es per definicion una aplicacion ${\displaystyle \varphi :E\to F}$  tala que

1. ${\displaystyle \ \forall (x,\,y)\in E^{2},\;\varphi (x*y)=\varphi (x)\star \varphi (y)}$ 
2. ${\displaystyle \varphi (e)=f}$  (leis elements neutres se correspòndon per ${\displaystyle \varphi }$  )

• Lo nuclèu dau morfisme ${\displaystyle \varphi }$  , notat ${\displaystyle \ker(\varphi )}$  , es lo sosensemble de E ansin definit :

${\displaystyle \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.

• Siá un morfisme ${\displaystyle \varphi }$  de ${\displaystyle (E,\,*)}$  vèrs ${\displaystyle (F,\,\star )}$ . Alora :
  • Per tot pareu (x, n) onte x es dins E e n es un entier naturau : ${\displaystyle \varphi \left(x^{[n]}\right)=(\varphi (x))^{\,[n]}\quad \scriptstyle {(\clubsuit )}}$ 
  • Se x es un element simetrizable de E, ${\displaystyle \varphi (x)}$  es un element simetrizable de F, e ${\displaystyle \varphi \left(x'\right)=\varphi (x)'}$ 
  • La relacion (${\displaystyle \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 ${\displaystyle (E,\,*)}$  vèrs ${\displaystyle (E,\,*)}$ .

• La compausada de dos morfismes de monoïdes es un morfisme de monoïdes :
  estent tres monoïdes ${\displaystyle (E,\,*)}$  , ${\displaystyle (F,\,\star )}$  , ${\displaystyle (G,\,\diamond )}$  e dos morfismes ${\displaystyle \varphi }$  de ${\displaystyle (E,\,*)}$  vèrs ${\displaystyle (F,\,\star )}$  , ${\displaystyle \ \psi }$  de ${\displaystyle (F,\,\star )}$  vèrs ${\displaystyle (G,\,\diamond )}$ , l'aplicacion compausada ${\displaystyle \psi \circ \varphi }$  es un morfisme de ${\displaystyle (E,\,*)}$  vèrs ${\displaystyle (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 ${\displaystyle (E,\,*)}$  vèrs ${\displaystyle (F,\,\star )}$  es un isomorfisme de ${\displaystyle (F,\,\star )}$  vèrs ${\displaystyle (E,\,*)}$ .

• L'aplicacion ${\displaystyle \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á ${\displaystyle {\mathcal {E}}={\mathcal {P}}(\Omega )}$  (cf. supra). Lei monoïdes ${\displaystyle \ ({\mathcal {E}},\cup \,)}$  , ${\displaystyle \ ({\mathcal {E}},\cap \,)}$  son isomòrfs. D'efècte, per tot sosensemble A de ${\displaystyle \Omega }$  , notem ${\displaystyle {\overline {A}}}$  lo complementari de A (dins ${\displaystyle \Omega }$  ) : ${\displaystyle {\overline {A}}=\Omega \setminus A}$  . L'aplicacion ${\displaystyle \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 ${\displaystyle {\mathcal {E}}}$  , ${\displaystyle {\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}}$  (formula de De Morgan), çò es : ${\displaystyle \varphi (A\cup B)=\varphi (A)\cap \varphi (B)}$ .
  • ${\displaystyle {\overline {\varnothing }}=\Omega }$  , autrament dich : ${\displaystyle \varphi (\varnothing )=\Omega }$  (lei dos elements neutres se correspòndon).

• Lei dos monoïdes ${\displaystyle (\mathbb {N} ,\,+)}$  e ${\displaystyle (\mathbb {N} ^{\ast },\,\times )}$  (onte ${\displaystyle \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 ${\displaystyle \varphi }$  :
  • Es una bijeccion ${\displaystyle \varphi :\mathbb {N} \to \mathbb {N} ^{\ast }}$ .
  • Per tot pareu (n, p) d'entiers naturaus, ${\displaystyle \varphi (n+p)=\varphi (n)\,\varphi (p)}$ .
  • ${\displaystyle \varphi (0)=1}$  (leis elements neutres se correspòndon)

Pausem ${\displaystyle g=\varphi (1)}$  ;${\displaystyle g\in \mathbb {N} ^{\ast }}$  e (per injectivitat de ${\displaystyle \varphi }$  ), ${\displaystyle g\neq \varphi (0)}$  , donc ${\displaystyle g\geq 2}$  .

Per tot entier naturau n, ${\displaystyle \varphi (n)=g^{n}}$  (demostracion dirècta per recurréncia subre n, o utilizacion de proprietats enonciadas supra). Coma ${\displaystyle \varphi }$  es bijectiva, per tot element m de ${\displaystyle \mathbb {N} ^{\ast }}$  existís un entier naturau (unic) n tau que

${\displaystyle m=\varphi (n)=g^{n}}$ .

En particular (en chausissent l'element m = g +1), existís un entier naturau n tau que ${\displaystyle \ g^{n}=g+1}$  ;

necessariament, n ≠ 0, donc g es un divisor de ${\displaystyle g^{n}}$  , a fortiori de ${\displaystyle g^{n}-g=1}$  ; es absurde, car g es estrictament superior a 1.

Una congruéncia dins un monoïde ${\displaystyle (E,\,*)}$  (d'element neutre e) es una relacion d'equivaléncia "${\displaystyle \ \sim }$ " compatibla amb l'estructura algebrica.

Aiçò significa que :

1. La relacion binària "${\displaystyle \ \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 : ${\displaystyle \ x\sim x'}$  implica ${\displaystyle \ x*y\sim x'*y}$  e ${\displaystyle \ y*x\sim y*x'}$ 

Se'n dedutz que per tota lista (x, x' , y, y' ) d'elements de E :

${\displaystyle \ x\sim x'}$  e ${\displaystyle \ y\sim y'}$  implican : ${\displaystyle \ x*y\sim x'*y'}$  ;

Autrament dich, la classa de l'element ${\displaystyle \ 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 ${\displaystyle E\,/\sim }$  , en pausant :

${\displaystyle [x]\;{\overline {*}}\;[y]=[x*y]}$ 

Es de bòn verificar que lo magma ${\displaystyle (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 ${\displaystyle (E,\,*)}$  per la congruéncia "${\displaystyle \ \sim }$ " .

L'aplicacion canonica : ${\displaystyle \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).

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