Monoïde

Un article de Wikipèdia, l'enciclopèdia liura.
Anar a : navigacion, Recercar

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[modificar | modificar la font]

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[modificar | modificar la font]

La notacion multiplicativa e la notacion additiva son particularament frequentas.

Monoïde multiplicatiu[modificar | modificar la font]

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 "1E" o simplament "1" (element unitat de E).

Monoïde additiu[modificar | modificar la font]

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 "0E" 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[modificar | modificar la font]

  • 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 An (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 A0 = {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[modificar | modificar la font]

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[modificar | modificar la font]

  • 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[modificar | modificar la font]

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[modificar | modificar la font]

  • 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[modificar | modificar la font]

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[modificar | modificar la font]

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[modificar | modificar la font]

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[modificar | modificar la font]

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[modificar | modificar la font]

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[modificar | modificar la font]

Monoïde multiplicatiu[modificar | modificar la font]

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[modificar | modificar la font]

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[modificar | modificar la font]

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

Definicions[modificar | modificar la font]

  • 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[modificar | modificar la font]

  • 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.
  • 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[modificar | modificar la font]

  • 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[modificar | modificar la font]

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[modificar | modificar la font]