Monoïde
Un article de Wikipèdia, l'enciclopèdia liura.
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.
Somari |
[Modificar] Definicion
Pus explicitament, un monoïde es un pareu , onte E es un ensemble, e "
" es una lèi (de composicion intèrna) dins E, associativa e admetent un element neutre :
(lèi de composicion intèrna)
(associativitat)
(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 :
(commutativitat)
[Modificar] Notacions
La notacion multiplicativa e la notacion additiva son particularament frequentas.
[Modificar] Monoïde multiplicatiu
Quand la lèi dins E es notada multiplicativament, lo monoïde es dich multiplicatiu :
- s'escriu : x · y o x y en plaça de :
L'element neutre es notat "1" o "1E" (element unitat de E).
[Modificar] Monoïde additiu
Quand la lèi dins E es notada additivament, lo monoïde es dich additiu :
- s'escriu : x + y en plaça de :
L'element neutre es notat "0" o "0E" (element nul, o zèro de E).
Es convengut qu'un monoïde additiu es totjorn commutatiu (s'emplega jamai la notacion additiva per un monoïde non commutatiu).
[Modificar] Exemples
- Lo magma
es un monoïde commutatiu que son element neutre es 0.
- Lo magma
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 :
es l'ensemble de totei lei mots subre l'alfabet A. La juxtaposicion (o concatenacion) es una lèi dins: 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,
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á
l'ensemble dei partidas d'un ensemble
.
- Lo magma
es un monoïde commutatiu qu'a per element neutre l'ensemble vuege
.
- Lo magma
es un monoïde commutatiu qu'a per element neutre l'ensemble
.
- Lo magma
- Sián A un ensemble non vuege, e
l'ensemble deis aplicacions
. La composicion deis aplicacions es una lèi dins
. Lo magma
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).
[Modificar] Sosmonoïde
Sián un monoïde d'element neutre e, e A una partida de E tala que :
-
, 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
es un monoïde, qu'es sonat sosmonoïde de
.
[Modificar] Exemples
- L'ensemble
, provesit de la lèi inducha, es un sosmonoïde de
.
- L'ensemble A deis entiers naturaus pars, provesit de l'addicion, es un sosmonoïde dau monoïde
.
- L'ensemble
dei foncions afinas es un sosmonoïde dau monoïde
, onte
es l'ensemble dei foncions
: se saup que
es estable per composicion, e de mai l'element neutre, çò es la foncion identica de
, es una foncion afina.
[Modificar] Elements simetrizables d'un monoïde
Un element x de E es dich simetrizable s'existís un element x' de E tau que :
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' = 1E , e x' x = 1E
- 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' = 0E , e x' + x = 0E
[Modificar] Exemples
- dins lo monoïde
, lo solet element simetrizable es 0, qu'es son pròpri opausat
- dins lo monoïde
, lo solet element invertible es 1, qu'es son pròpri invèrs
- dins lo monoïde
, leis elements simetrizables son leis aplicacions bijectivas
; lo simetric d'una bijeccion f es la bijeccion recipròca f − 1 .
[Modificar] 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 :
Se considèra alora l'element de E ; per associativitat :
- coma
,
- coma
,
- 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.
[Modificar] Ensemble deis elements simetrizables d'un monoïde
Siá G l'ensemble deis elements simetrizables d'un monoïde .
- 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
apartèn a G e son simetric es :
- 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 .
[Modificar] Iteracion de la lèi de composicion intèrna d'un monoïde
Siá un monoïde 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
, onte x1 , x2 , ... , xn 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 x1 , ... , xn + 1 de E, se definís ansin l'element
:
L'associativitat permete de plaçar lei parentèsis coma se vòu. Per exemple, se n = 4,
- per definicion : x1 * x2 * x3 * x4 = (x1 * x2 * x3) * x4 = ((x1 * x2) * x3) * x4
- mai tanben : x1 * x2 * x3 * x4 = (x1 * x2) * (x3 * x4) = x1 * (x2 * x3) * x4 , etc.
[Modificar] 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 :
, onte
Autrament dich :
(onte lo nombre d'operands, toteis egaus, es n )
Se completa la definicion en pausant :
(l'element neutre)
Per exemple :
,
,
.
L'aplicacion es un exemple de lèi de composicion extèrna dins E.
Per tot pareu (n, p ) d'entiers naturaus :
[Modificar] 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 :
Se definís alora x[ − m] en pausant :
En particular, x' = x[ − 1] .
L'aplicacion es un exemple de lèi de composicion extèrna dins G.
Se x es simetrizable, alora per tot pareu (n, p ) d'entiers :
Per exemple :
[Modificar] Notacions
[Modificar] Monoïde multiplicatiu
Dins lo cas d'un monoïde multiplicatiu :
- l'element
es sonat produch de
e es notat :
o ben
- per tot pareu (x, n), ont x es dins E e n es un entier naturau, s'escriu xn en luòga de x[n] ; se ditz qu'es la poténcia d'exponent n de x.
- x0 = 1E (l'element neutre), x1 = x ; x2 = x x es lo carrat de x ...
- xn xp = xn + 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 xn 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 :
- xn xp = xn + p per tot pareu (n, p ) d'entiers
[Modificar] Monoïde additiu
Dins lo cas d'un monoïde additiu :
- l'element
es sonat soma de
e es notat :
o ben
- 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 = 0E (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
[Modificar] Morfisme de monoïdes
Un morfisme de monoïdes es una aplicacion compatibla ambé l'estructura algebrica.
[Modificar] Definicions
- Sián dos monoïdes
(d'element neutre e) e
(d'element neutre f) . Un morfisme de
vèrs
es per definicion una aplicacion
tala que
(leis elements neutres se correspòndon per
)
- Lo nuclèu dau morfisme
, notat
, es lo sosensemble de E ansin definit :
- 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.
[Modificar] Proprietats
- Siá un morfisme
de
vèrs
. Alora :
- Per tot pareu (x, n) onte x es dins E e n es un entier naturau :
- Se x es un element simetrizable de E,
es un element simetrizable de F, e
- La relacion (
) supra se generaliza au cas que x es un element simetrizable de E e n es un entier.
- Per tot pareu (x, n) onte x es dins E e n es un entier naturau :
- L'aplicacion identica de E es un morfisme de
vèrs
.
- La compausada de dos morfismes de monoïdes es un morfisme de monoïdes :
estent tres monoïdes,
,
e dos morfismes
de
vèrs
,
de
vèrs
, l'aplicacion compausada
es un morfisme de
vèrs
.
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
vèrs
es un isomorfisme de
vèrs
.
[Modificar] Exemples e còntra-exemple
- L'aplicacion
es un isomorfisme dau monoïde (N, +) vèrs lo monoïde (A, +) deis entiers naturaus pars.
- Siá
(cf. supra). Lei monoïdes
,
son isomòrfs. D'efècte, per tot sosensemble A de Ω , notem
lo complementari de A (dins Ω ) :
. L'aplicacion
es un isomorfisme de monoïdes :
- Es bijectiva.
- Per tot pareu (A, B) d'elements de
,
(formula de De Morgan), çò es :
.
, autrament dich :
(lei dos elements neutres se correspòndon).
- Lei dos monoïdes
e
(onte
) son pas isomòrfs. Se demòstra per reduccion a l'absurd, en supausant l'existéncia d'un isomorfisme
:
- Es una bijeccion
.
- Per tot pareu (n, p) d'entiers naturaus,
.
(leis elements neutres se correspòndon)
- Es una bijeccion
- Pausem
;
e (per injectivitat de
),
, donc
.
- Per tot entier naturau n,
(demostracion dirècta per recurréncia subre n, o utilizacion de proprietats enonciadas supra). Coma
es bijectiva, per tot element m de
existís un entier naturau (unic) n tau que
.
- En particular (en chausissent l'element m = g +1), existís un entier naturau n tau que
;
- necessariament, n ≠ 0, donc g es un divisor de gn , a fortiori de gn − g = 1 ; es absurd, car g es estrictament superior a 1.
[Modificar] Monoïde quocient per una congruéncia
Una congruéncia dins un monoïde (d'element neutre e) es una relacion d'equivaléncia "
" compatibla ambé l'estructura algebrica.
Aiçò significa que :
- La relacion binària "
" es una relacion d'equivaléncia dins E ; la classa (d'equivaléncia) de tot element x de E serà notada : [x].
- Per tot triplet (x, x' , y) d'elements de E :
implica
e
Se'n dedutz que per tota lista (x, x' , y, y' ) d'elements de E :
e
implican :
;
Autrament dich, la classa de l'element depende unicament de la classa de x e de la classa de y : ansin, es possible de definir sens ambigüitat una lèi de composicion intèrna dins l'ensemble dei classas, çò es l'ensemble quocient
, en pausant :
Es de bòn verificar que lo magma 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
per la congruéncia "
" .
L'aplicacion canonica : 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).