1

Fundamentele algebrice ale informaticiipentru anul I Informatic ( zi + ID) ncepnd cu anul universitar 2005/2006CURSUL nr. 1 1. Mulimi. Operaii cu mulimi n cadrul acestei lucrri vom privi mulimile n sensul n care ele au fost privite de ctre GEORG CANTOR - primul matematician care a iniiat studiul lor sistematic (punct de vedere cunoscut n matematic sub numele de teoria naiv a mulimilor). Definiia1.1.. Dac A i B sunt dou mulimi, vom spune c A este inclus n B (sau c A este submulime a lui B) dac elementele lui A sunt i elemente ale lui B; n acest caz vom scrie AB iar n caz contrar AB. Avem deci : AB pentru orice xA xB AB exist xA a.. xB. Vom spune despre mulimile A i B c sunt egale dac oricare ar fi x, xA xB. Deci, A=BAB i BA. Vom spune c A este inclus strict n B i vom scrie AB dac AB i AB. poart numele de mulimea vid. Se observ c pentru orice mulime A, A (deoarece n caz contrar ar trebui s existe x a.. xA absurd.!). O mulime diferit de mulimea vid se zice nevid. Pentru o mulime T, vom nota prin P(T) mulimea submulimilor sale (evident , TP(T) ). Urmtorul rezultat este imediat : Dac T este o mulime oarecare iar A, B, CP(T), atunci : (i) AA (ii) Dac AB i BA, atunci A=B (iii) Dac AB i BC, atunci AC. n cadrul acestei lucrri vom utiliza deseori noiunea de familie de elemente a unei mulimi indexat de o mulime nevid de indici I (prin aceasta nelegnd o funcie definit pe mulimea I cu valori n mulimea respectiv). Astfel, vom scrie de exemplu (xi)iI pentru a desemna o familie de elemente ale unei mulimi sau (Ai) iI pentru a desemna o familie de mulimi indexat de mulimea I. Pentru o mulime T i A, BP(T) definim : AB={xT | xA i xB} AB={xT | xA sau xB} A\B={xT | xA i xB} AB=(A\B)(B\A). Dac AB=, mulimile A i B se zic disjuncte. Operaiile , , \ i poart numele de intersecie, reuniune, diferen i diferen simetric. n particular, T\A se noteaz prin T (A) (sau (A) dac nu este pericol de confuzie) i poart numele de complementara lui A n T.1

Se accept existena unei mulimi ce nu conine nici un element care se noteaz prin i

2

n mod evident, pentru A, BP(T) avem: A\B=AT (B) AB=(AB)\(AB)=(AT (B))(T (A)B) T ()=T, T(T)= AT (A)=T, AT (A)= iar T (T (A))=A.

De asemenea, pentru xT avem: xAB xA sau xB xA\B xA sau xB xT (A) xA. xAB xA i xB

xAB (xA i xB) sau (xA i xB) Din cele de mai nainte deducem imediat c dac A, BP(T), atunci: T (AB)=T(A)T (B) i T (AB)=T (A)T (B). Aceste ultime dou egaliti sunt cunoscute sub numele de relaiile lui De Morgan. Pentru o familie nevid (Ai )iI de submulimi ale lui T definim: I Ai ={xT | xAi pentru orice iI} iiI iI

U Ai ={xT | exist iI

a.. xAi }.

Astfel, relaiile lui De Morgan sunt adevrate ntr-un context mai general: Dac (Ai) iI este o familie de submulimi ale mulimii T, atunci:

CT I Ai = U CT ( Ai ) i CT U Ai = I CT ( Ai ) . iI iI iI iIUrmtorul rezultat este imediat: Propoziia 1.2. Dac T o mulime iar A, B, CP(T), atunci: (i) A(BC)=(AB)C i A(BC)=(AB)C (ii) AB=BA i AB=BA (iii) AT=A i A=A (iv) AA=A i AA=A. Observaia 1.3. 1. Din (i) deducem c operaiile i sunt asociative, din (ii) deducem c

pentru , iar din (iv) deducem c i sunt operaii idempotente pe P(T). A(BC)=(AB)(AC) i

ambele sunt comutative, din (iii) deducem c T i sunt elementele neutre pentru i respectiv 2. Prin dubl incluziune se probeaz imdiat c pentru oricare A, B, CP(T) avem: A(BC)=(AB)(AC) , adic operaiile de intersecie i reuniune sunt distributive una fa de cealalt. Propoziia1.4. Dac A, B, CP(T), atunci: (i) A(BC)=(AB)C (ii) AB=BA (iii) A=A iar A A= (iv) A(BC)=(AB)(AC).

2

3

Demonstraie. (i). Prin dubl incluziune se arat imediat c: A(BC)=(AB)C=[AT(B)T(C)][T(A)BT(C)] [T(A)T(B)C](ABC). (ii), (iii) sunt evidente. (iv). Se probeaz fie prin dubl incluziune, fie innd cont de distributivitatea interseciei fa Din cele de mai inainte deducem ca dac T este o mulime oarecare , atunci (P(T), ,) este inel Boolean . Definiia1.5. Fiind date dou obiecte x i y se numete pereche ordonat a obiectelor x i y mulimea notat (x, y) i definit astfel: (x, y)={ {x}, {x, y} }. Se verific acum imediat c dac x i y sunt dou obiecte a.. xy, atunci (x, y)(y, x) iar (x, y)=(y, x) x=y. dac (x, y) i (u, v) sunt dou perechi ordonate, atunci (x, y)=(u, v) x=u i y=v ; n particular, de reuniune.

Definiia1.6. Dac A i B sunt dou mulimi, mulimea notat AB={ (a, b) | aA i bB } se va numi produsul cartezian al mulimilor A i B. n mod evident: AB A i B AB=BA A=B AB= A= sau B=

AA i BB ABAB. Dac A, B, C sunt trei mulimi vom defini produsul lor cartezian prin egalitatea : ABC=(AB)C. Elementul ((a, b), c) din ABC l vom nota mai simplu prin (a, b, c). Mai general, dac A1, A2, ..., An (n3) sunt mulimi punem A1 A2 ...An =(( ...((A1A2)A3) ...)An) . Dac A este o mulime finit, vom nota prin |A| numrul de elemente ale lui A. n mod evident, dac A i B sunt submulimi finite ale unei mulimi M atunci i AB este submulime finit a lui M iar |AB|=|A|+|B|-|AB|. Vom prezenta n continuare un rezultat mai general cunoscut sub numele de principiul includerii i excluderii: Propoziia1.7. Fie M o mulime finit iar M1, M2, ..., Mn submulimi ale lui M. Atunci :

UMii =1

n

=

1 i n n -1

Mi

-

1 i < j n

Mi M j

+

1 i < j < k n

Mi M j Mk

-

.

- .... + (- 1)

M 1 ... M n

3

4

2.Relaii binare pe o mulime. Relaii de echivalen Definiia 2.1. Dac A este o mulime, numim relaie binar pe A orice submulime a produsului cartezian AA. Dac a, bA i (a, b) vom spune c elementul a este n relaia cu b. De asemenea, vom scrie ab pentru a desemna faptul c (a, b). Pentru mulimea A vom nota prin Rel (A) mulimea relaiilor binare de pe A (evident, Rel (A)=P(AA) ). Relaia A={ (a, a) | aA} poart numele de diagonala produsului cartezian AA. Pentru Rel (A) definim -1={(a, b)AA | (b, a)}. n mod evident, (-1)-1= iar dac mai avem Rel (A) a.. -1.1- Definiia2.2. Pentru , Rel (A) definim compunerea lor prin ({=a, b)AA | exist cA a.. (a, c) i (c, b)}. Rezultatul urmtor este imediat: Propoziia 2.3. Fie , ,Rel (A). Atunci: (i) A=A= (ii) ()=() (iii) i (iv) (=1-)1--1 atunci (v) (=1-)-1 ; 1-mai general, dac (i) iI este o familie de relaii binare pe A, U ri iI -1

= U r i-1 .iI

Pentru n i Rel (A) definim :r n = r o r o .... o r pentru n > 1 . 4 4 14243n ori

D A pentru n = 0

Se probeaz imediat c dac m, n atunci mn=m+n. Definii 2.3. Vom spune despre o relaie Rel (A) c este: i) reflexiv dac A ii) simetric dac -1 iii) antisimetric dac -1A iv) tranzitiv dac 2. Rezultatul urmtor este imediat:

Propoziia2.4. O relaie Rel(A) este reflexiv ( simetric, antisimetric, tranzitiv ) dac i numai dac -1 este reflexiv ( simetric, antisimetric, tranzitiv ) . Definiia 2.5. Vom spune despre o relaie Rel(A) c este o echivalen pe A dac este reflexiv, simetric i tranzitiv.4

5

Vom nota prin Echiv (A) mulimea relaiilor de echivalen de pe A. Evident, A, AAEchiv (A). Propoziia 2.6. Dac Echiv (A) , atunci -1= i 2=. Demonstraie. Cum este simetric -1. Dac (a, b)-1, atunci (b, a)-1 (b, a)-

1

x) i (x, y) (x, y)=2, adic 2, deci 2=.

(a, b), adic -1, deci -1=. Cum este tranzitiv avem 2. Fie acum (x, y). Din (x,

Lema 2.7. Fie Rel(A) i r =A-1. Atunci relaia r are urmtoarele proprieti: (i) (ii) rr este reflexiv i simetric

(iii) dac este o alt relaie binar de pe A reflexiv i simetric a.. , atunci r . Demonstraie. (i ). este evident . (ii). Cum A r deducem c r este reflexiv iar cumr-1

= (A-1) 1=A-1-1 (-1)-1=A-1= r deducem c r este i simetric.

(iii). Dac este reflexiv i simetric a.. ,atunci -1=1- i cum A deducem c r =A-1. Lema 2.8. Fie Rel(A) reflexiv i simetric iar r = U r n . Atunci r are urmtoarelen 1

proprieti : (i) r ; (ii) r este o echivalen pe A; (iii) Dac Echiv(A) a.. ,atunci r . Demonstraie. (i). este evident. (ii). Cum A r deducem c A r , adic r este reflexiv. Deoarece este simetric i pentru orice n* avemr-1

(n)-1=(-1)n=n , deducem c-1 n1

= Urn n1

= U rn

( )

-1

= Urn = r ,n 1

adic r este i simetric. Fie acum (x, y) r o r ; atunci exist zA a.. (x, z), (z, y) r , adic exist m, n* a.. (x, z)m i (z, y)n. Deducem imediat c (x, y)nm=n+m r , adic r r , decir este tranzitiv, adic r Echiv (A).2

(iii). Fie acum Echiv (A) a.. .Cum n n = pentru orice n* deducem c r = U r n .n 1

Din Lemele de mai sus deducem imediat: Teorema 2.9. Dac Rel(A), atuncir = U D A U r U r -1n 1

(

)

n

.

5

6

Definiia 2.10. Dac Echiv (A) i aA, prin clasa de echivalen a lui a relativ la nelegem mulimea adic [a] pentru orice aA). [a]={xA (x, a)} (cum este n particular reflexiv deducem c a[a],

Mulimea A / ={ [a] aA } poart numele de mulimea factor ( sau ct ) a lui A prin relaia . Propoziia 2.11. Dac Echiv (A), atunci: (i) U [a ] =A;a A

(ii) Dac a, bA atunci [a]=[b] (a, b); Demonstraie.

(iii) Dac a, bA, atunci [a]=[b] sau [a][b]=.

(i). Deoarece pentru orice aA, a[a] deducem incluziunea de la dreapta la stnga; cum cealalt incluziune este evident deducem egalitatea solicitat. (ii). Dac [a]=[b] , cum a[a] deducem c a[b] adic (a, b). Fie acum (a, b) i x[a], adic (x, a). Datorit tranzitivitii lui deducem c (x, b), adic x[b], deci [a] [b]. Analog deducem c i [b][a] , adic [a]=[b]. deci [a]=[b] (conform cu (ii)). (iii). Presupunem c [a][b]. Atunci exist xA a.. (x, a), (x, b) i astfel (a, b),

Definiia 2.12. Numim partiie a unei mulimi M o familie (Mi)iI de submulimi ale lui M ce verific condiiile : (i) Pentru i, jI, ij Mi Mj=; (ii) U M i = M .iI

Observaia 2.13. Din cele de mai nainte deducem c dac este o relaie de echivalen pe mulimea A, atunci mulimea claselor de echivalen ale lui pe A determin o partiie a lui A. Definiia 2.13. Dac A i B sunt dou mulimi vom spune despre ele c sunt cardinal echivalente (sau mai simplu echivalente) dac exist o bijecie f : AB. Dac A i B sunt echivalente vom scrie AB (n caz contrar, vom scrieAB). Propoziia 2.14. Relaia de ,, este o echivalen pe clasa tuturor mulimilor . Demonstraie. Pentru orice mulime A, AA cci funcia 1A:AA este o bijecie. Dac A i B sunt dou mulimi iar AB, atunci exist f : AB o bijecie. Cum i f -1 : BA este bijecie, deducem c BA, adic relaia ,, este i simetric. Pentru a proba i tranzitivitatea relaiei ,, fie A, B, C mulimi a.. AB i BC, adic exist f :AB i g :BC bijecii. Cum gf : A C este bijecie deducem c AC.

Definiia 2.15. Dac A este o mulime, prin numrul cardinal al lui A nelegem clasa de echivalen a lui A (notat |A|) relativ la relaia de echivalen . Deci B|A|AB. (n ); convenim s notm pentru n*, n=|Sn|. Convenim de asemenea s notm 0=cardinalul mulimii vide i prin c 0 (alef zero) cardinalul mulimii numerelor naturale .*

Vom numi seciuni ale lui mulimile de forma Sn={0, 1, ..., n-1} formate din n elemente

6

7

Fie n , n 2 i n definit prin (x,y) n n | x-y. Deoarece pentru orice x , n|x-x=0 deducem c n este reflexiv iar dac n|x-y, atunci n|y-x, adic (y,x)n astfel c n este i simetric. Dac (x,y), (y,z)n, atunci n|x-y, y-z i atunci n|(xy)+(y-z)=x-z, deci (x,z)n, adic n este i tranzitiv, deci o echivalen pe . Dac x, atunci mprind pe x la n avem x = cn+r cu c i r{0,1,,n-1}. Atunci x-r = cn adic (x, r)n i deci [x ]r n = [r ]r n astfel c) Pentru a respecta tradiia notaiilor, vom nota /n=n iar [k ]r n = k pentru orice k{0,1,,nn =

/n ={ [0]r n , [1]r n , , [n - 1]r n }

1} (dac nu este pericol de confuzie); astfel k{0,1,,n-1}.

) { 0, 1,..., n - 1 } iar k ={k+cn|c} pentru orice

Elementele lui n se numesc clasele de resturi modulo n.

CURSUL nr. 2 : 1.Mulimi ordonate.Lema Zorn Definiia 1.1. Printr-o mulime ordonat nelegem un dublet (A, ) format dintr-o mulime nevid A i o relaie binar pe A notat tradiional prin "" care este reflexiv, antisimetric i tranzitiv. Vom spune c "" este o ordine pe A. Pentru x, y A vom scrie x < y dac x y , x y. Dac relaia "" este doar reflexiv i tranzitiv, vom spune despre ea c este o ordine parial sau c (A, ) este o mulime parial ordonat. Dac pentru x, yA definim x y dac i numai dac y x obinem o nou relaie de ordine pe A. Dubletul (A, ) l vom nota prin A i spunem c mulimea ordonat A este duala mulimii A. Fie ( A, ) o mulime parial ordonat iar r o relaie de echivalen pe A. Vom spune despre r c este compatibil cu preordinea de pe A dac pentru oricare elemente x , y , z, t din A avem implicaia ( x, y ) r , ( z, t ) r i x z y t. Dac r este o relaie de echivalen pe A compatibil cu preordinea , atunci pe mulimea ct A/ r se poate defini o ordine parial astfel : [ x] r [ y ] r exist z [x] r i t [ y ] r a.. z t ; vom numi aceast ordine parial preordinea ct. n cele ce urmeaz prin (A,) vom desemna o mulime ordonat. Cnd nu este pericol de confuzie prin mulime ordonat vom specifica numai mulimea subiacent A (fr a mai pune n eviden relaia , aceasta subnelegndu-se ). Definiia 1.2. Fie m, M A i S A, S . Vom spune c: i) m este minorant pentru S dac pentru orice sS, m s (n caz c exist, prin inf (S) vom desemna cel mai mare minorant al lui S) ii) M este majorant pentru S dac M este minorant pentru S n A, adic pentru orice sS, s M (n caz c exist, prin sup (S) vom desemna cel mai mic majorant al lui S). Dac S={s1, s2, ..., sn}A atunci vom nota inf (S)= s1s2 ...sn iar sup (S)= s1s2 ..sn (evident, n cazul n care acestea exist). Ordinea "" de pe A se zice total dac pentru orice a, bA, a b sau b a; o submulime total ordonat a lui A poart numele de lan. Pentru a, bA vom spune c b urmeaz pe a (sau c a este urmat de b) dac a < b iar pentru a c b avem a=c sau c=b; vom utiliza n acest caz notaia a b.7

8

Pentru a, b A vom nota: (a, b)={xAa2, atunci cum p este prim (deci cu necesitate impar) deducem c (x-y) p = x p y p iar dac p=2, cum 2y 2 = 0 avem (x-y)2=x2+y2=x2-y2. Observaia 1.8. Din propoziia precedent deducem c funcia jp:KK, jp(x)=xp este morfism de corpuri. Morfismul jp poart numele de morfismul lui Frobenius. 2.Construcia corpului al numerelor complexe Scopul acestui paragraf este de a identifica corpul al numerelor reale cu un subcorp al unui Pentru aceasta vom considera = iar pentru (x, y), (x, y)+(z, t)=(x+z, y+t) (x, y)(z, t )=(xz-yt, xt+yz). Teorema 2.1. (, +, ) este corp comutativ n care ecuaia x2=-1 are soluie. Demonstraie. Faptul c (, +) este grup abelian se probeaz imediat (elementul neutru este ( 0, 0 ), iar pentru (x, y), -(x, y)= =(-x, -y )). n mod evident nmulirea este comutativ. Pentru a proba c (*, ) este grup, fie (x, y), (z, t), (r, s). Deoarece (x, y)[(z, t)(r, s)]=[(x, y)(z, t)](r, s)=(xzr-xts-yzs-ytr, xzs+xtr+yzr-yts) deducem c nmulirea este asociativ. Cum (x, y)(1, 0)=(1, 0)(x, y)=(x, y) deducem c elementul neutru fa de nmulire este (1, 0). Fie acum (x, y)* (adic x0 sau y0). Egalitatea (x, y) (x, y)=(1, 0) este echivalent cu xxyy=1 = 2

corp comutativ n care ecuaia x2 =-1 are soluie.

(z, t) definim :

i xy+yx=0,x2

de

unde

x=

x x +y2 2

i

y= -

y x +y2 2

,

adic

(x,

y)

-1

=

x +y

, -

. x +y y2 2

Cum pentru (x, y), (z, t), (r, s), (x, y)[(z, t)+(r, s)]=(x, y)(z, t)+(x, y)(r, s)=(xz+xr-yt-ys, xt+xs+yz+yr) deducem c nmulirea este distributiv fa de adunare, adic (, +, ) este corp comutativ.46

47

n .

S notm i=(0, 1). Cum i2=(0, 1)(0, 1)=(-1, 0)=-(1, 0) deducem c ecuaia x2=-1 are soluie

morfism de corpuri (deci funcie injectiv). n felul acesta poate fi privit ca subcorp al lui . anterioare deducem c z se poate scrie (formal) sub forma z=x+iy (cu i=(0, 1) iar i2=-1). complexe. Elementele din \ se zic pur imaginare.

Observaia 2.2. Se probeaz imediat c i:, i(x)=(x, 0) pentru orice x, este Deoarece pentru z=(x, y) putem scrie z=(x, 0)+(y, 0)(0, 1), innd cont de identificrile

Mulimea poart numele de mulimea numerelor complexe, iar (, +, ) corpul numerelor

Dac z=x+iy cu x, y, atunci x se zice partea real a lui z iar yi partea imaginar a lui z ( y se numete coeficientul prii imaginare ). Pentru z, z=x+iy, definim z = x - iy (ce se va numi conjugatul lui z) i z = x 2 + y 2 ( |z| poart numele de modulul lui z ). Propoziia 2.3. Fie z, z1, z2. Atunci (i) z z = z (ii) z = z , z z = z2

(iii) z1 z 2 = z1 z 2 , z1 z 2 = z1 z 2 , 1 = 1 (cu z20) z 2 z2 (iv) z = z , z1 + z 2 z1 + z 2 , z1 z 2 = z1 z 2 ,z1 z1 (cu z20). = z2 z2

z

z

Demonstraie. (i). Fie z=a+ib. Dac z, atunci b=0, deci z = a = z iar dac z = z atunci b =-b adic b=0, deci z. (ii). i (iii). sunt evidente. (iv). S probm doar inegalitatea |z1+z2||z1|+|z2| (celelalte probndu-se imediat). Alegem z1=x1+iy1 i z2=x2+iy2 cu x1, x2, y1, y2 i astfel |z1+z2||z1|+|z2|

( x1 + x 2 )2 + ( y1 + y 2 )2

2 2 2 2 x1 + y1 + x 2 + y 2

2 2 2 2 2 2 2 2 x1 + x 2 + 2 x1 x 2 + y1 + y 2 + 2 y1 y 2 x1 + y1 + x 2 + y 2 + 2 2 2 2 + 2 x1 + y1 x 2 + y 2

(

)(

2 2 ( x1 x 2 + y1 y 2 )2 x12 + y12 x 2 + y 2 (x1 y 2 - x 2 y1 )2 0 ceea ce este evident.

(

)

)(

)

Egalitate avem dac

x1 x 2 = = l cu l , adic z1 = l z 2 . y1 y 2 a b

Observaia 2.4. Asociind fiecrui numr complex z=a+ib matricea - b a se probeaz imediat c corpul (,+,) este izomorf cu corpul nmulire fiind cele obinuite din M2 (). a b -b a a, b

, operaiile de adunare i

47

48

CURSUL nr. 11 1.Inelul polinoamelor ntr-o nedeterminat n cele ce urmeaz prin A vom desemna un inel unitar i comutativ. Prin A vom nota mulimea funciilor f: A. Pentru uurina scrierii vom reprezenta o f=(a0, a1, ...,an,...) unde pentru orice i, ai=f(i)A ( f se funcie f: A n felul urmtor : mai numete i ir de elemente din A). n mod evident, dac mai avem g: A , g=(b0, b1, ..., bn ,...), atunci f=g dac i numai dac ai=bi , pentru orice i. Pentru f, gA , f=(a0, a1, ..., an, ...) i g=(b0, b1, ..., bn, ...) definim f+g, (f+g)(i)=f(i)+g(i) i (fg)(i)= f (k ) g (i - k ) pentru orice i.k =0 i

fg A prin

Altfel zis, f+g=(a0+b0, a1+b1, ..., an+bn, ...) i fg=(c0, c1, ..., cn, ...) unde ci= a kbi-k pentruk =0

i

orice i. Astfel, c0=a0b0, c1=a0b1+a1b0, ...,

cn=a0bn+a1bn-1+...+an-1b1+anb0,

Propoziia 1.1. (A, +,) este inel unitar comutativ. Demonstraie. Faptul c (A, +) este grup comutativ este imediat: asociativitatea i

comutativitatea adunrii de pe A rezult din asociativitatea i comutativitatea adunrii de pe A, elementul neutru este irul nul 0=(0, 0, ..., 0, ...) (ce are toate componentele egale cu zero), iar pentru f = (a0, a1, ..., an, ...)A opusul su -f este dat de Comutativitatea nmulirii de pe proba asociativitatea nmulirii de pe A, A fie A -f = (-a0, -a1, ..., -an, ...) . f = (a0, a1, ..., an, ...), g = (b0, b1, ..., bn, ...), h i s probm c (fg)h=f(gh). ntr-adevr, pentru n rezult din comutativitatea nmulirii de pe A. Pentru a

= (c0, c1, ..., cn, ...) trei elemente oarecare din avem :n n i i =0 i =0 j =0

((fg)h)(n)= ( fg )(i ) h(n - i ) = ( f ( j ) g (i - j )) h(n - i ) =

j + k +t = n

f ( j ) g (k )h(t )

i analog (f(gh))(n)=

j + k +t = n

f ( j ) g (k )h(t ) ,

de unde ((fg)h)(n)=(f(gh))(n), adic

(fg)h=f(gh). Dac notm 1=(1, 0, ..., 0, ...)A , atunci pentru orice fA avem f1=1f=f , de unde concluzia c 1 este elementul neutru pentru nmulirea de pe A. Deoarece nmulirea de pe A este distributiv fa de adunarea de pe A deducem imediat c dac f, g, h A i n, atunci (f(g+h))(n)=f(n)(g(n)+h(n))=f(n)g(n)+f(n)h(n)=(fg)(n)+(fh)(n)= altfel zis nmulirea de pe demonstrat. Observaia 1.2. 1. Dac vom considera iA : A A, iA(a)=(a, 0, 0,...,0,...) pentru orice aA, atunci iA este morfism injectiv de inele unitare, astfel c putem identifica orice element aA cu elementul (a, 0,..., 0, ...) din A i astfel putem privi pe A ca subinel unitar al inelului A. 2. Dac X = (0, 1, 0, ..., 0, ...) A , atunci pentru orice n avem Xn = ( 0,...,0 ,1, 0, ...), A =(fg+fh)(n), adic f(g+h)=fg+fh, este distributiv fa de adunarea de pe A i cu aceasta propoziia este

13 2nori

astfel c dac f=(a0, a1, ..., an, atunci folosind adunarea i nmulirea definite pe A ca i identificrile stabilite n prima parte a acestei observaii avem:48

...)A,

49

f= (a0, a1, ..., an, ...) = (a0, 0, ...) + (0, a1, 0, ...) + ... = (a0, 0, ...) + +(a1, 0, ...) (0, 1, 0,...) + (a2, 0, ...) (0, 0, 1, 0, ...) +...+ (an, 0, ...) ( 0,0,...,0 , 1, 0, ...) +... =(a0, 0, ...) + (a1, 0, ...) X + (a2, 0, ...) X2+...+

123nori

+(an, 0, ...) Xn+...= a0+a1X+...+anXn+... Obinem astfel scrierea obinuit a unei serii formale. Aceast observaie ne permite s dm urmtoarea definiie : Definiia 1.3. Inelul (A, +, ) se numete inelul seriilor formale n nedeterminata X cu coeficieni din A i se noteaz prin A[[X]]. Un element f din A[[X]] se va scrie condensat sub forma f= ai X i (aceasta fiind doar oi 0

notaie, fr sens de adunare). Definiia 1.4. O serie formal f = ai X i A[[X]] cu proprietatea c { iai 0} estei 0

finit se numete polinom cu coeficieni n A. Vom nota prin A[X] mulimea polinoamelor cu coeficieni n A. Polinoamele de forma aXn cu aA* se zic monoame. Astfel, dac f= ai X i A[X], atunci exist n a.. ai=0 pentru orice i, i n+1; n acesti 0

caz vom scrie f=a0+a1X+...+anXn sau f= ai X i .i =0

n

n cazul polinomului nul, ai=0 pentru orice i; dac nu este pericol de confuzie convenim s notm prin 0 polinomul nul. Observaia 1.5. Fie f= ai X i , g= bi X i dou polinoame din A[X]. Cum n particular f i gi =0 i =0 n m

sunt funcii de la la A deducem c f=g dac i numai dac m=n i ai=bi pentru orice 0 i n. n particular, f=0 dac i numai dac ai=0 pentru orice 0 i n i f 0 dac i numai dac exist 0 i n a.. ai 0. Definiia 1.6. Pentru polinomul nul 0A[X] definim gradul su ca fiind - iar pentru fA[X], f 0 definim gradul lui f ca fiind grad(f)=max{iai 0}. Astfel, dac f 0 i grad(f)=n 1, atunci f se poate scrie sub forma f=a0+a1X+...+anXn i an 0. n acest caz, an se zice coeficientul dominant al lui f; dac an=1, f se mai zice monic. Dac grad(f)=0, atunci f=a cu aA; spunem n acest caz c f este polinom constant. Propoziia 1.7. A[X] este subinel al inelului A[[X]]. Demonstraie. Fie f=a0+a1X+...+anXn i g=b0+b1X+...+bmXm dou polinoame din A[X] de grade n i respectiv m. Dac de exemplu n m, atunci f-g=(a0-b0)+(a1-b1)X+...+(an-bn)Xn+(bn+1)Xn+1+...+(-bm)Xm A[X] iar fg=a0b0+(a0b1+a1b0)X+...+anbmXn+m A[X]. De asemenea, polinomul constant 1A[X]. Definiia 1.8. Inelul A[X] poart numele de inelul polinoamelor n nedeterminata X cu coeficieni n inelul A sau mai pe scurt, inelul polinoamelor ntr-o nedeterminat. Propoziia 1.9.Dac f, gA[X], atunci: (i) grad (f+g) max{grad(f), grad(g)} (ii) grad (fg) grad(f) + grad(g).

49

50

Demonstraie. Dac f=g=0 totul este clar. De asemenea, dac de exemplu f=0 i g 0 (innd cont de conveniile de calcul cu ). Dac f0 i g0 inegalitile de la (i) i (ii) rezult imediat din felul n care se efectueaz f+g i fg Propoziia 1.10. Fie f=a0+a1X+...+anXn A[X]. Atunci: (i) fU(A[X]) a0U(A) iar a1, ..., anN(A) (reamintim c prin N(A) am notat mulimea elementelor nilpotente din A) (ii) f este divizor al lui zero n A[X] exist aA* a.. af=0. Demonstraie. (i). "". Dac fU(A[X]), atunci exist g=b0+b1X+...+bmXm A[X] a.. fg=1

a0b0 = 1 a0b1 + a1b0 = 0 a b + a b + a 2b0 = 0 (*) 0 2 1 1 ............................... a n-1bm + a n bm-1 = 0 a n bm = 0 Din prima egalitate din (*) deducem c a0U(A). nmulind ambii membrii ai penultimei egaliti din (*) cu an i innd cont de ultima egalitate deducem c an2bm-1=0. Inductiv deducem c anm+1b0=0, de unde anm+1=0 (cci b0U(A)), adic anN(A). Atunci anXn N(A[X]) i cum fU(A[X]) deducem c f1=f-anXn U(A[X]). Cum f1=a0+a1X+...+an-1Xn-1 deducem c an-1N(A). Raionnd acum inductiv deducem c an-2, ..., a2, a1 N(A). "". S presupunem c a0U(A) (deci a0U(A[X])) i a1, a2, ..., anN(A). Atunci a1, ..., anN(A[X]) i cum N(A[X]) este ideal n A[X] deducem c a1X, a2X2,,anXn N(A[X]) deci i a1X+a2X2+...+anXnN(A[X]). Cum a0U(A[X]) iar f=a0+(a1X+...+anXn) deducem c fU(A[X]) . (ii). "". Evident. "". S presupunem c f este divizor al lui zero n A[X] i fie g=b0+b1X+...+bmXm A[X] un polinom nenul de grad minim pentru care fg=0. Atunci anbm=0 i cum g1=ang=anb0+anb1+...+anbmm-1 are gradul m-1