Monoïde

Monoïde
Proprietat P107 (tipe principal (GND)) de botar dens WIKIDATA
Identificacions d'autoritats
GND	[1]
ISNI	[2]
LCCN	[3]
ULAN
BNF	[4]
SUDOC	[5]
CALIS
CiNii
NDL
ISO standard
	Wikimedia Commons prepausa de documents multimèdia liures sus 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