ELEMENTE DE TEORIA GRUPURILOR

§1. OPERATIE ALGEBRICA INTERNA

Definitie. Fiind data o multime nevida M, se numeste operatie algebrica interna sau lege de compozitie interna definita pe M orice functie

φ: M x M M,

(x, y) φ(x, y).

In acest capitol, fiind vorba numai de operatii algebrice interne, vom spune pe scurt operatie algebrica in loc de operatie algebrica interna.

Exemple. 1) Adunarea si inmultirea in multimea N a numerelor naturale, in multimea Z a numerelor intregi, in multimea Q a numerelor rationale, in multimea R a numerelor reale si in multimea C a numerelor complexe sunt operatii algebrice. 

2) Pe multimea Z a numerelor intregi, scaderea este o operatie algebrica. Ea este definita astfel:

s : Z x Z Z,

s(x, y) = x + (-y) = x - y.

De asemenea, scaderea este operatie algebrica si pe multimile: Q, R, C. Insa pe multimea N a numerelor naturale scaderea nu este operatie algebrica, deoarece rezultatul acesteia nu este intotdeauna un numar natural.

3) Daca M este o multime, pe multimea

F(M) =

a functiilor de la M la M putem defini operatia algebrica de compunere. Reamintim ca daca f, g I F(M), atunci se defineste compunerea g o f ca fiind functia

g o f : M M, (g o f) (x) = g(f(x)).

4) Daca M este o multime nevida, iar

P(M) =

este multimea partilor lui M, atunci reuniunea

(X, Y) X Y, X, Y I P(M)

si intersectia

(X, Y) X Y, X, Y I P(M)

sunt operatii algebrice pe P(M).

5) Fie n 1 un numar natural. Pe multimea Z_n = a claselor de resturi modulo n, definim urmatoarele operatii algebrice:

([a], [b] ) [a] + [b] (numita adunare),

([a], [b]) [a] [b] (numita inmultire).

Sa aratam mai intai ca adunarea este o operatie algebrica pe Z_n, adica nu depinde de alegerea reprezentantilor. Intr-adevar, fie [a] = [a₁] si [b] = [b₁]; atunci a s a₁ (mod n) si b s b₁ (mod n), adica n | a - a₁ si n | b - b₁, de unde n | (a + b) - (a₁ + b­₁), adica a + b s a₁ + b₁ (mod n) si deci [a + b] = [a₁ + b₁].

La fel se arata ca daca a s a₁ (mod n) si b s b₁ (mod n), atunci [ab] = [a₁b₁] si deci operatia de inmultire este bine definita

Deseori, daca φ : M x M M este o operatie algebrica pe multimea M, in loc de φ(x, y) se foloseste ca si in exemplele de mai inainte, o alta notatie, ca de exemplu: x * y, x o y, x y, x T y, x + y, x y, etc.

Daca notam elementul φ(x, y) prin x + y, pentru orice x, y I M, operatia algebrica se numeste adunare (fara a fi vorba de adunarea numerelor), iar x + y se numeste suma lui x cu y; in acest caz, se spune ca am folosit scrierea aditiva a operatiei algebrice. Daca notam elementul φ(x, y) prin xy pentru orice x, y I M, operatia algebrica se numeste inmultire (de asemenea, fara a avea vreo legatura cu inmultirea numerelor), iar xy se numeste produsul lui x cu y; in acest caz, se spune ca am folosit scrierea multiplicativa a operatiei algebrice.

Dam cateva proprietati ale operatiilor algebrice, cu ajutorul carora se definesc structurile de baza ale algebrei.

Asociativitatea. Fie M o multime si φ : M x M M o operatie algebrica pe multimea M. Se spune ca φ este o operatie algebrica asociativa daca oricare ar fi x, y, z I M, are loc egalitatea

φ(x, φ(y, z)) = φ(φ(x, y), z).

In scrierea aditiva conditia de asociativitate se scrie

x + (y + z) = (x + y) + z, oricare ar fi x, y, z I M,

iar in scrierea multiplicativa, aceasta se scrie

x (y z) = (x y) z, oricare ar fi x, y, z I M.

Daca φ nu este asociativa, se spune ca φ este o operatie algebrica neasociativa.

Exemple. Operatiile algebrice de adunare si inmultire pe multimile de numere: N, Z, Q, R, C sunt asociative; operatia algebrica de compunere a functiilor pe F(M) data in exemplul 3) este asociativa; de asemenea, reuniunea si intersectia pe P(M) (vezi exemplul 4) sunt operatii algebrice asociative. Adunarea si inmultirea pe Z_n (vezi exemplul 5) sunt operatii algebrice asociative. Intr-adevar, daca [a], [b], [c]I Z_n, atunci

[a] + ([b] + [c]) = [a] + [b + c] = [a + (b + c)] = [(a + b) + c] = [a + b] + [c] = ([a] + [b]) + [c]

si

[a] ([b] [c]) = [a][bc] = [a(bc)] = [(ab)c] = [ab][c] = ([a][b])[ c].

Insa scaderea numerelor nu este asociativa; de exemplu

Comutativitatea. Fie M o multime si φ : M x M M o operatie algebrica pe multimea M. Se spune ca φ este e operatie algebrica comutativa, daca oricare ar fi x, y I M are loc egalitatea

φ(x, y) = φ(y, x).

Daca folosim scrierea aditiva, respectiv scrierea multiplicativa, conditia de comutativitate se scrie:

x + y = y + x, oricare ar fi x, y I M,

respectiv

x y = y x, oricare ar fi x, y I M.

Daca φ nu este comutativa, se spune ca φ este o operatie algebrica necomutativa.

Exemple. Operatiile algebrice definite in exemplul 1) sunt comutative. Scaderea numerelor este necomutativa; de exemplu

De asemenea, operatia algebrica de compunere pe F(M) nu este comutativa decat daca M are un singur element (lasam ca exercitiu demonstratia acestei afirmatii). De asemenea, reuniunea si intersectia pe P(M) sunt operatii algebrice comutative. Adunarea si inmultirea pe Z_n sunt operatii algebrice comutative.

Element neutru. Fie φ : M x M M o operatie algebrica definita pe multimea M . Se spune ca elementul e I M este element neutru pentru operatia φ, daca oricare ar fi x I M avem   

φ(x, e) = φ(x, e) = x.

Daca consideram o operatie algebrica oarecare, notata prin * : M x M M, (x, y) x * y, atunci conditia de mai inainte a elementului neutru se scrie

x * e = e * x = x, oricare ar fi x I M.

Sa presupunem ca e si e' sunt elemente neutre pentru aceasta operatie algebrica. Atunci avem

e = e * e' = e'.

Deci elementul neutru, daca exista, este unic determinat.

Daca folosim scrierea aditiva, elementul neutru se numeste element nul sau element zero sau chiar zero si se noteaza de obicei cu 0. Cu aceasta notatie, conditia elementului zero devine

x + 0 = 0 + x = x, oricare ar fi x I M.

In scrierea multiplicativa, elementul neutru se numeste element unitate si se noteaza de obicei cu e sau chiar cu 1 (a nu se confunda cu numarul 1!).

Cu aceste notatii, conditia elementului unitate devine

x . 1 = 1 . x = x, oricare ar fi x I M.

Exemple. Pentru operatia de adunare in N, Z, Q, R, C, numarul 0 este element neutru, iar pentru operatia de inmultire a numerelor, numarul 1 este element neutru. Pentru operatia de compunere a functiilor definita pe F(M), functia identica 1_M este element neutru. Pentru operatia de reuniune (respectiv intersectie) pe multimea P(M) a partilor unei multimi M, multimea vida (respectiv multimea totala M) este element neutru. Pentru adunare pe multimea Z_n elementul neutru este [0], iar pentru inmultire elementul neutru este [1].

Daca consideram multimea 2Z = a numerelor intregi pare, inmultirea (obisnuita) a numerelor intregi este o operatie algebrica interna care, in mod evident, nu are element neutru.

Elemente simetrizabile. Fie M o multime si φ o operatie algebrica pe M care are un element neutru e. Fie x I M. Se spune ca x este simetrizabil fata de operatia data daca exista un element x' I M astfel incat

φ(x, x') = φ(x', x) = e.

Elementul x' este un simetric al lui x.

Daca folosim scrierea aditiva, 0 fiind elementul neutru, atunci un element simetric al lui x se numeste element opus al lui x, iar conditia de mai inainte devine

x + x' = x' + x = 0.

In acest caz se spune ca x este opozabil fata de operatia data.

Daca folosim scrierea multiplicativa, fiind elementul neutru, atunci un element simetric al lui x se mai numeste element invers sau un invers al lui x, iar conditia de mai inainte devine

x . x' = x' . x = 1.

In acest caz se spune ca x este inversabil fata de operatia data.

Notam cu U((M, *)) multimea elementelor simetrizabile ale lui M in raport cu o lege

Observatie. Daca M este o multime iar * : M x M M, x, y) x * y este o operatie algebrica pe M care admite element neutru e, atunci e este simetrizabil, simetricul sau fiind e. Intr-adevar, avem e * e = e.

Exemple. In multimea N a numerelor naturale, numai 0 (elementul neutru) are un opus fata de operatia de adunare si numai 1 are invers fata de operatia de inmultire. In multimea Z a numerelor intregi, fata de adunare orice element are un opus, iar fata de inmultire 1 si -1 au invers. In Q, R si C fata de adunare, orice element are un opus iar fata de inmultire orice element nenul are un invers. In multimea F(M), cu operatia algebrica de compunere a functiilor, elementele inversabile sunt functiile bijective. In multimea P(M), fata de reuniune numai multimea vida are un simetric, iar fata de intersectie numai multimea totala M are un simetric.

In multimea Z_n = cu operatia algebrica de adunare, oricare ar fi [a] I Z_n are un opus si anume [-a] I Z_n. Daca consideram Z_n cu operatia algebrica de inmultire avem ca

[a] I Z_n este inversabil daca si numai daca a este prim cu n (scriem (a, n) = 1).

Intr-adevar, daca a este inversabil, atunci exista [b] I Z_n astfel incat [a] [b] = [1] sau [a b] = [1] si deci n | ab - 1. Atunci exista k I Z astfel incat ab - 1 = kn  sau ab + n (- k) = 1 si deci (a, n) = 1. Reciproc, daca (a, n) = 1, atunci exista u, v I Z astfel incat a u + n v = 1, de unde [a u + n v] = [1] sau [a] [u] + [n] [v] = [1]. Dar [n] = [0] si deci [a][u] = [1], adica a este inversabil in Z_n. In concluzie, U(Z_n) = .

Propozitie. Se considera M o multime inzestrata cu o operatie algebrica asociativa * : M x M M, (x, y) x * y si cu element neutru e. Daca elementul x I M este simetrizabil, atunci simetricul sau este unic.

Demonstratie. Fie x I M, iar x', x'I M simetrice ale lui x, adica x * x' = x' * x = e si x * x' = x' * x = e. Atunci x' *(x * x') = x' * e = x', iar (x' * x) * x' = e * x' = x'. Operatia fiind asociativa, avem x' * (x * x') = (x' * x) * x' si deci x' = x'.

Observatie. Faptul ca operatia este asociativa este esential pentru unicitatea elementului simetric, nu numai in demonstratia data mai inainte. Mai precis, daca operatia nu este asociativa, nu rezulta unicitatea elementului simetric. Sa luam multimea M = si sa definim pe M, o operatie algebrica ' * ', in modul urmator:

e * x = x * e = x, pentru orice x I M ,

a * a = a * b = e, b * a = e, b * b = a.

Aceasta operatie nu este asociativa; de exemplu,

(b * b) * a = a * a = e, iar b * (b * a) = b * e = b.

Elementul a are ca simetrice pe a si pe b.   

In conditiile de mai inainte, daca x este un element simetrizabil pentru o operatie asociativa, simetricul sau, unic determinat, se noteaza cu x^-1 daca folosim scrierea multiplicativa si se citeste inversul lui x, si se noteaza - x, daca folosim scrierea aditiva si se citeste opusul lui x.

O multime nevida M inzestrata cu o operatie algebrica ' * ' o notam, uneori, prin perechea (M, *), punand in evidenta multimea si operatia algebrica.

§ 2. MONOIZI

Definitie. O multime nevida M inzestrata cu o operatie algebrica asociativa si cu element neutru se numeste monoid.

Daca, in plus, operatia algebrica este comutativa, monoidul se numeste comutativ.

Exemple. Multimea N a numerelor naturale fata de adunarea obisnuita formeaza un monoid comutativ. De asemenea, multimea N cu inmultirea obisnuita este monoid comutativ. Multimile Z, Q, R, C fata de adunarea obisnuita, cat si separat, fata de inmultirea obisnuita formeaza monoizi comutativi. Multimea F(M) a functiilor definite pe multimea M cu valori in M, cu operatia de compunere, formeaza un monoid, in general, necomutativ. Multimea P(M) a partilor unei multimi M cu operatia de reuniune (intersectie) formeaza monoid comutativ. Multimea Z_n, a claselor de resturi modulo n cu operatia de adunare, ca si separat, cu cea de inmultire este monoid comutativ.

Reguli de calcul intr-un monoid

Fiind dat un monoid M cu operatia algebrica notata multiplicativ, se poate defini, prin recurenta, produsul unui numar finit de elemente x₁, x₂, , x_n (n 1) ale lui M, astfel: daca notam cu x₁ x_n produsul acestor elemente, atunci

x₁x₂ x_n = (x₁x₂ x_{n - 1}) x_n.

Observatie. Se poate arata cu usurinta, prin inductie, ca pentru k, 0 < k < n, are loc relatia

a₁a₂ a_n = (a₁a ₂ a_k) (a_{k + 1}a_{k + 2} a_n).

Lasam demonstratia ca exercitiu.

In cazul particular in care a₁ = a₂ = . = a_n = a, in loc de a₁a­₂ . a_n se mai scrie aⁿ. Avem a¹ = a, iar daca n = 0 convenim sa punem a⁰ = e, e fiind elementul unitate al monoidului.

Din relatia (1), deducem

a^m . aⁿ = a^{m + n}

pentru m, n I N.

Prin inductie, se demonstreaza usor ca

(a^m)ⁿ = a^mn.

Daca in locul scrierii multiplicative folosim scrierea aditiva, atunci in loc de a₁a₂ a_n, se scrie a₁ + a₂ + . + a_n iar relatia (1) devine a₁ + a₂ + + a_n = (a₁ + + a_k) + (a_{k + 1} + . + a_n). De asemenea, in loc de aⁿ se scrie na si deci 1 . a = a, iar daca n = 0, conventia devine 0 . a = 0. Celelalte relatii devin respectiv

ma + na = (m + n)a si n(ma) = (nm)a.

Morfisme de monoizi

Daca M si N sunt doi monoizi notati multiplicativ, se numeste morfism de monoizi o functie f : M N astfel incat

1) f(x y) = f(x) f(y), oricare ar fi x, y I M;  

2) f(e) = e', unde e si e' sunt respectiv, elementele unitate ale lui M si N.

Exemple. Daca (N, +) este monoidul aditiv al numerelor naturale, iar n I N este un numar natural oarecare, functia

φ_n : N N, φ_n(x) = nx,

este un morfism de monoizi. 

Lasam ca exercitiu demonstratia faptului ca orice morfism de monoizi de la monoidul (N, +) in el insusi este de acest tip. Mai precis, daca f : N N este un morfism de monoizi, atunci exista nIN, astfel incat f = φ_n (adica f(x) = φ_n(x) = nx, oricare ar fi x I N).

Daca (P(M), ) si (P(M), ) sunt monoidul partilor multimii M cu intersectia si respectiv cu reuniunea, functia

g : (P(M), ) (P(M), ), g(X) = C_MX

(C_MX este complementara lui X fata de M) este un morfism de monoizi.

Intr-adevar,

g(X Y) = C_M(X Y) = C_MX C_MY = g(X) g(Y}

si

g(M) = C_MM =

Observatie. Se poate demonstra prin inductie ca daca x₁, x₂, . , x_n I M, atunci pentru orice morfism de monoizi f : M N avem

f(x₁x₂ x­_n) = f(x₁)f(x₂) f(x_n).

In particular,

f(xⁿ) = (f(x))ⁿ.

Compunerea morfismelor de monoizi

1) Daca M, N, P sunt monoizi, iar f : M N, g : N P sunt morfisme de monoizi, atunci compunerea g of : M P este morfism de monoizi.

Intr-adevar, daca x, y I M, atunci

(g o f)(x y) = g(f(x y)) = g(f(x)f(y)) = g(f(x)) g(f(y)) = (g o f)(x) (g o f) (y).

De asemenea,

(g of)(e) = g(f(e)) = g(e') = e'.

Compunerea morfismelor de monoizi este asociativa, deoarece este un caz particular de compunere de functii.

2) Daca M este un monoid, functia identica 1_M a multimii M este un morfism de monoizi.

Intr-adevar, daca x, y I M, atunci 1_M(x y) = x y = 1_M(x) 1_M(y). De asemenea,

1_M(e) = e.

Mai mult, daca f : M N este morfism de monoizi, atunci

f o 1_M = f si 1_N o f = f.

Izomorfisme de monoizi

Un morfism de monoizi f : M N se numeste izomorfism daca exista un morfism de monoizi g: N M astfel incat fog = l_N si g o f = 1_M. Scriem atunci f : M N.

Daca f : M N este un izomorfism de monoizi, atunci g : N M definit mai inainte, este unic determinat. Intr-adevar, daca g' : N M este un alt morfism astfel incat g' o f = 1_M si f o g' = l_N, atunci

g' o (f o g) = g' o 1_N = g' si (g' of) o g = l_M o g = g.

Dar g' o ( f o g) = (g' o f) o g si deci g' = g.

Din definitie rezulta ca g este si el un izomorfism de monoizi, numit izomorfismul invers lui f si se noteaza cu f ^-1.

Daca exista un izomorfism de monoizi f : M N se spune ca monoidul M este izomorf cu monoidul N. Daca monoidul M este izomorf cu monoidul N, se mai spune ca M si N sunt monoizi izomorfi si se scrie M N.

Observatie. Relatia de izomorfism intre monoizi este o relatie de echivalenta:

1) Orice monoid M este izomorf cu el insusi, deoarece 1_M : M M este un izomorfism de monoizi;

2) Daca monoidul M este izomorf cu monoidul N, atunci si monoidul N este izomorf cu monoidul M (prin izomorfismul invers);

3) Daca monoidul M este izomorf cu monoidul N, iar monoidul N este izomorf cu monoidul P, atunci M este izomorf cu P.

Observatie. Notiunea de izomorfism este fundamentala in algebra; din punct de vedere algebric, doua structuri algebrice izomorfe sunt la fel, deosebirile dintre ele tinand doar de natura elementelor si a operatiei. Doua structuri algebrice izomorfe se pot identifica.

Propozitie. Fie f : M N un morfism de monoizi. Atunci f este izomorfism de monoizi daca si numai daca functia f este bijectiva.

Demonstratie. Este cunoscut ca o functie este inversabila daca si numai daca este bijectiva. De aici rezulta in mod evident ca daca f este izomorfism, atunci functia f este bijectiva. Reciproc, daca f este bijectiva, atunci exista o functie g : N M astfel incat    g o f = 1_M si f o g = 1_N. Totul rezulta daca aratam ca g este morfism de monoizi. Fie y,    y' I N; atunci

y y' = l_N(y y') = (f o g) (y y') = f(g(y y')).

Pe de alta parte,

y y' = 1_N(y) 1_N(y') = (f o g) (y) (f o g) (y') = f(g (y)) f(g(y')) = f(g(y) g(y'

Deci f(g(y y')) = f(g(y)) f(g(y')) si cum f este injectiva, rezulta

g(y y') = g(y) g(y').

De asemenea, avem (g o f) (e) = e, adica g(f(e)) = e. Dar f(e) = e' si deci g(e') = e.

Exemplu. Morfismul de monoizi

g : (P(M), ) P(M), ), g(X) = C_MX

este izomorfism.

Monoidul liber generat de o multime

Fie A o multime. Vom numi cuvant de elemente din A un sistem finit ordonat de elemente din A, a₁a₂ a_k. Vom spune ca doua cuvinte cu elemente din A, a = a₁a₂ a_k,   b = b₁b₂ . b_s, sunt egale daca si numai daca k = s si a_i = b_i pentru i = 1, 2, , k. Pe multimea L(A) a cuvintelor cu elemente din A introducem urmatoarea operatie algebrica (notata multiplicativ): pentru a si b din L(A) de forma de mai sus definim

ab = a₁a₂ . a_kb₁b₂ . b_s.

Este clar ca aceasta operatie este asociativa si are element unitate care este cuvantul ,,vid' (format din submultimea vida a lui A). Asadar L(A) cu operatia introdusa este monoid si se numeste monoidul liber generat de multimea A.

Se vede ca daca multimea A are cel putin doua elemente distincte a si b, atunci operatia algebrica introdusa pe L(A) nu este comutativa, caci ab ba, unde ab este compunerea cuvantului a cu cuvantul b, iar ba compunerea cuvantului b cu cuvantul a. Daca insa multimea A este constituita dintr-un singur element, A = , atunci exista un singur cuvant de lungime n > 0, care poate fi notat sub forma aⁿ, iar pentru n 0, m 0, avem ca aⁿa^m = a^{n + m} si deci este clar ca in acest caz L(A) este monoid comutativ.

In continuare, in afara de cazul in care se mentioneaza altfel, operatia algebrica pe un monoid va fi notata multiplicativ. Insa, fara o mentiune expresa, N va fi considerat ca monoid cu adunarea.

Propozitie. Daca A este o multime formata dintr-un singur element, A = , atunci monoidul liber L(A) generat de A este izomorf cu monoidul aditiv N.

Demonstratie. Am vazut ca, in ipoteza din propozitie, orice element al lui L(A) este de forma aⁿ, cu n I N si este clar ca functia φ : L(A) N definita prin φ(aⁿ) = n este un morfism de monoizi fiindca

φ(aⁿa^m ) = φ(a^{n + m}) = n + m = φ(aⁿ ) + φ(a^m) .

Analog, functia φ': N L(A), definita prin φ'(n) = aⁿ, este un morfism de monoizi si avem φ' o φ = 1_L(A) si φ o φ'=1_N.

Din propozitia de mai sus rezulta ca toti monoizii liberi generati de un element sunt izomorfi, fapt care rezulta de altfel aproape imediat din definitia monoidului liber generat de o multime A, in care se vede ca natura elementelor din A nu intervine. Deci la doua multimi A si A' echipotente se asociaza monoizi liberi izomorfi. Aceasta afirmatie rezulta si din urmatoarea:

Teorema. Fie A o multime, L(A) monoidul liber generat de A, M un monoid oarecare si f:A M o aplicatie. Atunci exista un unic morfism de monoizi f : L(A) M, astfel ca f o i_A = f, unde i_A:A L(A) este incluziunea canonica a lui A in L(A).

Demonstratie. Va trebui sa definim pe f pentru orice cuvant format cu elemente din A. Acest lucru se face astfel: daca a I L(A), a = a₁a₂ . a_n, a_kIA, k = 1, 2, . , n, n 1, atunci f (a) = f(a₁) f(a_n) (compunerea elementelor f(a₁), , f(a_n) in M), iar pentru n = 0, adica cuvantului vid, ii asociem elementul unitate din M. Fie b = b₁ b_m un alt element din L(A). Atunci avem prin definitie:

f (ab) = f(a₁) f(a_n)f(b₁) f(b_m

si

f (a f (b) = (f(a₁) f(a_n))(f(b₁) f(b_m

Deoarece in M operatia este asociativa avem ca f (ab f (a f (b , deci f este morfism de monoizi. Am construit astfel morfismul f cu proprietatea ceruta.

Sa aratam ca este unicul morfism de monoizi cu aceasta proprietate. Fie atunci f ': L(A) M un alt morfism astfel ca f ' o i_A = f. Fie a I L(A) scris sub forma de mai sus. Atunci f a f '(a₁ . a_n) = f '(a₁) f '(a_n) = f(a f(a_n), adica f a f a), pentru orice a I L(A) si deci f f

Proprietatea monoidului liber generat de o multime A demonstrata in teorema pre-cedenta poarta numele de proprietatea de universalitate a monoidului liber generat de A.