1 fundamentele algebrice ale informaticii -...

90
1 1 Fundamentele algebrice ale informaticii pentru anul I Informatică ( zi + ID) începînd cu anul universitar 2005/2006 CURSUL nr. 1 §1. Mulţimi. Operaţii cu mul ţimi În cadrul acestei lucrări vom privi mulţimile în sensul în care ele au fost privite de către GEORG CANTOR - primul matematician care a ini ţiat studiul lor sistematic (punct de vedere cunoscut în matematică sub numele de teoria naivă a mul ţimilor). Definiţia1.1.. Dacă A şi B sunt două mulţimi, vom spune că A este inclusă în B (sau că A este submulţime 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 : ABpentru orice xA xB ABexistă xA a.î. xB. Vom spune despre mulţimile A şi B că sunt egale dacă oricare ar fi x, xAxB. Deci, A=BAB şi BA. Vom spune că A este inclusă strict în B şi vom scrie AB dacă AB şi AB. Se acceptă existenţa unei mulţimi ce nu conţine nici un element care se notează prin şi poartă numele de mulţimea vidă. Se observă că pentru orice mulţime A, ∅⊆A (deoarece în caz contrar ar trebui să existe x∈∅ a.î. xA – absurd.!). O mulţime diferită de mulţimea vidă se zice nevidă. Pentru o mulţime T, vom nota prin P(T) mulţimea submulţimilor sale (evident , TP(T) ). Următorul rezultat este imediat : Dacă T este o mul ţime 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 lucrări vom utiliza deseori noţiunea de familie de elemente a unei mul ţimi indexat ă de o mulţime nevidă de indici I (prin aceasta înţelegând o funcţie definită pe mulţimea I cu valori în mulţimea respectivă). Astfel, vom scrie de exemplu (x i ) iI pentru a desemna o familie de elemente ale unei mulţimi sau (A i ) iI pentru a desemna o familie de mul ţimi indexată de mulţimea I. Pentru o mulţime 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=, mulţimile A şi B se zic disjuncte. Operaţiile , , \ şi poartă numele de intersecţie, 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.

Upload: others

Post on 29-Aug-2019

42 views

Category:

Documents


3 download

TRANSCRIPT

  • 1

    1

    Fundamentele algebrice ale informaticii

    pentru anul I Informatic ( zi + ID) ncepnd cu anul universitar 2005/2006 CURSUL 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. Se accept existena unei mulimi ce nu conine nici un element care se noteaz prin i

    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.

  • 2

    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 xAB xA i xB xA\B xA sau xB xAB (xA i xB) sau (xA i xB) xT (A) xA.

    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:

    IIi

    iA

    ={xT | xAi pentru orice iI} i

    UIi

    iA

    ={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:

    ( )iIi

    TIi

    iT ACAC UI

    =

    i ( )i

    IiT

    IiiT ACAC IU

    =

    .

    Urmtorul 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

    ambele sunt comutative, din (iii) deducem c T i sunt elementele neutre pentru i respectiv pentru , iar din (iv) deducem c i sunt operaii idempotente pe P(T).

    2. Prin dubl incluziune se probeaz imdiat c pentru oricare A, B, CP(T) avem: A(BC)=(AB)(AC) i 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).

  • 3

    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

    de reuniune. 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

    dac (x, y) i (u, v) sunt dou perechi ordonate, atunci (x, y)=(u, v) x=u i y=v ; n particular, (x, y)=(y, x) x=y.

    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= A= sau B= AB=BA A=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 :

    ( ) nnnkji

    kjinji

    jini

    i

    n

    ii

    MM

    MMMMMMM

    +

    +=

  • 4

    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.. -11-.

    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 (v) (1-(=-11- ; mai general, dac (i) iI este o familie de relaii binare pe A,

    atunci

    UUIi

    iIi

    i

    =

    11

    .

    Pentru n i Rel (A) definim :

    >

    == 1....

    0

    npentrunpentru

    orin

    An

    4434421ooo .

    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.

  • 5

    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 (a, b), adic -1, deci -1=. Cum este tranzitiv avem 2. Fie acum (x, y). Din (x, x) i (x, y) (x, y)=2, adic 2, deci 2=.

    Lema 2.7. Fie Rel(A) i =A-1. Atunci relaia are urmtoarele proprieti:

    (i) (ii) este reflexiv i simetric (iii) dac este o alt relaie binar de pe A reflexiv i simetric a.. , atunci .

    Demonstraie. (i ). este evident .

    (ii). Cum A deducem c este reflexiv iar cum 1

    = (A-1) 1=A-1-1 (-1)-1=A-1= deducem c este i simetric. (iii). Dac este reflexiv i simetric a.. , atunci -11-= i cum A deducem

    c =A-1.

    Lema 2.8. Fie Rel(A) reflexiv i simetric iar U1

    =n

    n . Atunci are urmtoarele

    proprieti : (i) ; (ii) este o echivalen pe A; (iii) Dac Echiv(A) a.. , atunci . Demonstraie. (i). este evident. (ii). Cum A deducem c A , adic este reflexiv. Deoarece este simetric

    i pentru orice n* avem (n)-1=(-1)n=n , deducem c

    ( ) ===

    =

    UUU11

    11

    1

    1

    n

    n

    n

    n

    n

    n ,

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

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

    1=

    n

    n .

    Din Lemele de mai sus deducem imediat: Teorema 2.9. Dac Rel(A), atunci

    ( )U U U1

    1

    =n

    n

    A .

  • 6

    6

    Definiia 2.10. Dac Echiv (A) i aA, prin clasa de echivalen a lui a relativ la nelegem mulimea

    [a]={xA (x, a)} (cum este n particular reflexiv deducem c a[a], adic [a] pentru orice aA).

    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

    Aaa

    =A;

    (ii) Dac a, bA atunci [a]=[b] (a, b); (iii) Dac a, bA, atunci [a]=[b] sau [a][b]=. Demonstraie. (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]. (iii). Presupunem c [a][b]. Atunci exist xA a.. (x, a), (x, b) i astfel (a, b),

    deci [a]=[b] (conform cu (ii)). 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

    Iii MM

    = .

    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. Vom numi seciuni ale lui mulimile de forma Sn={0, 1, ..., n-1} formate din n elemente

    (n*); convenim s notm pentru n*, n=|Sn|. Convenim de asemenea s notm 0=cardinalul mulimii vide i prin 0 (alef zero) cardinalul mulimii numerelor naturale .

  • 7

    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|(x-y)+(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 [ ] [ ] nn rx = astfel c /n ={ [ ] n0 , [ ] n1 , , [ ] nn 1 }

    Pentru a respecta tradiia notaiilor, vom nota /n=n iar [ ] kk n)

    = pentru orice k{0,1,,n-

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

    )={k+cn|c} pentru orice

    k{0,1,,n-1}. 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 o relaie de echivalen pe A. Vom spune despre c este compatibil cu preordinea de pe A dac pentru oricare elemente x , y , z, t din A avem implicaia ( ) ( ) tzyx ,,, i .tyzx Dac este o relaie de echivalen pe A compatibil cu preordinea , atunci pe mulimea ct A/ se poate defini o ordine parial astfel : ][][ yx exist ][xz i ][yt a.. tz ; 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.

  • 8

    8

    Pentru a, b A vom nota: (a, b)={xAa

  • 9

    9

    Corolar 1 (Principiul lui Hansdorf de maximalitate). Orice mulime ordonat conine o submulime total ordonat maximal.

    Corolar 2 (Lema lui Zorn). Orice mulime nevid inductiv (coinductiv) ordonat are cel puin un element maximal (minimal). Corolar 3 (Principiul elementului maximal (minimal)). Fie (A, ) o mulime inductiv (coinductiv) ordonat i aA. Exist un element maximal (minimal) ma A a.. a ma (ma a).

    Corolar 4 (Lema lui Kuratowski). Orice submulime total ordonat a unei mulimi ordonate este cuprins ntr-o submulime total ordonat maximal.

    Corolar 5 (Teorema lui Zermelo). Pe orice mulime nevid A se poate introduce o ordine fa de care A este bine ordonat.

    Corolar 6 (Principiul induciei transfinite). Fie (A, ) o mulime bine ordonat infinit i P o proprietate dat. Pentru a demonstra c toate elementele mulimii A au proprietatea P este suficient s demonstrm c: (i) Elementul iniial 0 al lui A are proprietatea P (ii) Dac pentru aA, toate elementele xA a.. x

  • 10

    10

    2. Dac A este o latice complet, atunci inf () = 1 iar sup () = 0. 3. Pentru ca o latice L s fie condiional complet, este suficient ca pentru orice submulime

    nevid i mrginit S a sa, s existe doar inf (S) (sau sup (S)). Definiia 1.3. Dac A este inf-semilatice (respectiv sup-semilatice) vom spune despre o submulime AA c este inf-sub-semilatice (respectiv sup-sub-semilatice), dac pentru oricare dou elemente a, bA avem abA (respectiv abA). Dac A este latice, AA se va zice sublatice, dac pentru oricare dou elemente a, bA avem ab, abA. Exemple. 1. Fie mulimea numerelor naturale iar "" relaia de divizibilitate pe . Atunci "" este o relaie de ordine pe . Fa de aceast ordine devine latice n care pentru m, n , m n = cel mai mare divizor comun al lui m i n iar m n = cel mai mic multiplu comun al lui m i n. Evident, pentru relaia de divizibilitate, elementul 1 este element iniial iar 0 este element final. Aceast ordonare nu este total deoarece dac avem dou numere naturale m, n prime ntre ele (cum ar fi de exemplu 2 i 3) nu avem m n i nici n m.

    2. Dac K este una din mulimile de numere , , sau , atunci K cu ordonarea natural este o latice, iar ordonarea natural este total. 3. Fie M o mulime iar P(M) mulimea submulimilor lui M. Atunci (P (M), ) este o latice complet cu prim i ultim element (respectiv i M). Fie acum A, A dou mulimi ordonate (cnd nu este pericol de confuzie convenim s notm prin "" ambele relaii de ordine de pe A i A ) i f:AA o funcie. Definiia1.4. Vom spune despre f c este morfism de mulimi ordonate (sau aplicaie izoton) dac pentru orice a, bA cu a b avem f (a) f (b) (n anumite lucrri f se zice monoton cresctoare). Dac A, A sunt inf (sup) - semilatici vom spune despre f c este morfism de inf (sup) - semilatici dac pentru oricare dou elemente a, bA, f (a b) = f (a) f (b) (respectiv f (a b) = f (a) f (b)). Dac A, A sunt latici, vom spune c f este morfism de latici dac f este simultan morfism de inf i sup-semilatici (adic pentru oricare dou elemente a, b A avem f (a b) = f (a) f (b) i f (a b) = f (a) f (b)). n mod evident, morfismele de inf (sup) - semilatici sunt aplicaii izotone iar dac compunem dou morfisme de acelai tip obinem tot un morfism de acelai tip. Dac A, A sunt mulimi ordonate iar f:AA este morfism de mulimi ordonate, atunci f se zice izomorfism de mulimi ordonate dac exist g:AA morfism de mulimi ordonate a.. fg=1A i gf=1A. Acest lucru revine la a spune de fapt c f este o bijecie. n acest caz vom scrie AA . Analog se definete noiunea de izomorfism de inf (sup) - semilatici ca i cea de izomorfism de latici. Definiia 1.5. Fie A o inf-semilatice i F A o submulime nevid a sa. Vom spune c F este filtru al lui A dac F este o inf-sub-semi- latice i pentru a, b A, dac a b i aF atunci bF. Vom nota prin F (A) mulimea filtrelor lui A. Noiunea dual celei de filtru este aceea de ideal pentru o sup-semilatice. Mai precis avem: Definiia1.6. Fie A o sup-semilatice iar I A o submulime nevid a sa. Vom spune c I este un ideal al lui A dac I este sup-sub-semilatice a lui A i pentru orice a, bA cu a b, dac bI atunci i aI. Vom nota prin I (A) mulimea idealelor lui A.

  • 11

    11

    Observaia1.7. Dac A este latice, atunci noiunile de filtru i ideal au definiii precise n A (innd cont de definiiile de mai sus, cci A este simultan inf i sup-semilatice); evident n acest caz A F (A)I (A). Cum intersecia oricrei familii de filtre (ideale) este de asemenea filtru (ideal), putem vorbi de filtrul (idealul) generat de o mulime nevid. Dac A este o inf(sup)-semilatice, pentru SA vom nota prin [S) ( (S]) filtrul(idealul) generat de S (adic intersecia tuturor filtrelor (idealelor) lui A ce conin pe S). Propoziia1.8. Dac A este o inf-semilatice i S A o submulime nevid a sa, atunci: [S)={aAexist s1, s2 ,.., snS a.. s1s2 ..sna}. Demonstraie.Fie FS={aAexist s1, s2 ,.., snS a.. s1s2 ..sna}. Se probeaz imediat c FS F (A) i S FS, deci [S) FS .

    Dac FF(A) a.. S F atunci FSF deci FSF=[S),de unde [S)=FS .n Dual se demonstreaz: Propoziia1.9. Dac A este o sup-semilatice i SA este o submulime nevid a sa, atunci: (S]={aAexist s1, s2 ,.., snS a.. a s1 s2 .. sn}. Astfel, (F(A),) i (I(A),) sunt latici n care pentru F1, F2F(A) (respectiv I1, I2I(A)) avem F1F2=F1F2 iar F1F2=[F1F2) (respectiv I1I2=I1I2 iar I1I2=(I1I2] ).

    Dac A este o inf (sup)-semilatice i aA, vom nota prin [a) ( (a]) filtrul (idealul) generat

    de {a}. Conform celor de mai sus avem c: [a)={xAax} i (a]={xAxa} ([a), (a] poart numele

    de filtrul (idealul) principal generat de a).

    Definiia1.10. Vom spune despre o latice (L,) c este: i) modular dac pentru oricare x, y, z L cu z x avem x (y z) = (x y)

    z ii) distributiv dac verific una din urmtoarele dou condiii echivalente: 1) x (y z) = (x y) (x z) 2) x (y z) = (x y) (x z) pentru orice x, y, z L. S notm c exist latici ce nu sunt modulare. ntr-adevr, dac vom considera laticea notat tradiional prin N5 : 1 c b a 0

  • 12

    12

    observm c a c, pe cnd a (b c) = a 0 = a iar (a b) c= =1 c a, astfel c c (b a) (c b) a, deci N5 nu este modular. Teorema 1.11. (Dedekind). Pentru o latice L urmtoarele afirmaii sunt echivalente: (i) L este modular (ii) Pentru orice a, b, cL, dac c a, atunci a (b c) (a b) c (iii) Pentru orice a, b, cL avem ((ac) b) c = (ac) (bc) (iv) Pentru orice a, b, cL, dac a c, atunci din a b =c b i a b= c b deducem c a = c (v) L nu are sublatici izomorfe cu N5. Demonstraie. Cum n orice latice, dac c a, atunci (a b) c a (b c), echivalena (i) (ii) este imediat. (i) (iii). Rezult din aceea c a c c. (iii) (i). Fie a, b, c L a.. a c. Atunci a = a c, deci (a b) c = ((a c) b) c = (a c) (b c) = a (b c). (i) (iv). Avem a = a (a b) = a (c b) = a (b c) = (a b) c = (c b) c = c. (iv) (v) Evident (innd cont de observaia de mai nainte). (v) (i) S presupunem c L nu este modular. Exist atunci a, b, c n L a.. a c, iar a (b c) (a b) c. S observm c bc < a (b c) < (a b) c < ab, b c < b < a b, a (b c) b i b (a b) c. Obinem n felul acesta diagrama Hasse a unei sublatici a lui L izomorf cu N5: a b (a b) c b a (b c) b c (observnd i c (a (bc)) b = a ((bc) b) = ab i ((ab) c) b = ((a b) b) c = b c, ceea ce este absurd. n Pe parcursul acestei lucrri vom prezenta mai multe exemple de latici modulare. Evident, orice latice distributiv este modular. n cele ce urmeaz, prin Ld vom nota clasa laticilor distributive iar prin Ld (0, 1) clasa laticilor distributive mrginite. Exemple. 1. Dac L este un lan, atunci LLd (0, 1). 2. (, | ), (P (M), ) Ld (0, 1). Teorema 1.12. Pentru LL urmtoarele afirmaii sunt echivalente: (i) L Ld (ii) a (b c) (a b) (a c) pentru orice a, b, c L (iii) (a b) (b c) (c a) = (a b) (b c) (c a) pentru orice a, b, cL (iv) Pentru orice a, b, cL, dac a c = b c i a c = b c, atunci a = b (v) L nu are sublatici izomorfe cu N5 sau M3, unde M3 are urmtoarea diagram Hasse:

  • 13

    13

    1 b a c 0 Demonstraie. (i) (ii). Rezult din aceea c pentru oricare elemente a, b, c L, (a b) (a c) a (b c). (i) (iii). S presupunem c L Ld i fie a, b, c L. Atunci (a b) (b c) (c a) = (((a b) b) ((a b) c)) (c a) = =(b ((a c) (b c))) (c a) = (b (a c)) (c a) = (b (c a)) ((a c) (c a)) = ((b c) (b a)) (a c) = (a b) (b c) (c a). (iii) (i). Deducem imediat c L este modular, deoarece dac a, b, c L i a c, (a b) c = (a b) ((b c) c) = (a b) (b c) (c a) = (a b) (b c) (c a) = (a b) (b c) a = ((a b) a) (b c) = a (b c). Cu aceast observaie, distributivitatea lui L se deduce astfel: a (b c) = (a (a b)) (b c) = ((a (c a)) (a b) (b c) = a (a b) (b c) (c a) = a ((a b) (b c) (c a)) = =(a ((a b) (b c))) (c a) = (datorit modularitii) = a (b c)) (a b) (c a) = (datorit modularitii) = (a b) (a c). (i) (iv). Dac a c = b c i a c = b c, atunci a = a (a c) = a (b c) = (a b) (a c) = (a b) (b c) = b (a c) = b (b c) = b. (iv) (v). S admitem prin absurd c att N5 ct i M3 sunt sublatici ale lui L. n cazul lui N5 observm c b c = b a = 0, b c = =b a = 1 i totui a c iar n cazul lui M3, b a = b c = 0, b a = b c = 1 i totui a c - absurd! (v) (i). Conform Teoremei 1.1, dac L nu are sublatici izomorfe cu N5 atunci ea este modular. Cum pentru oricare a, b, c L avem: (a b) (b c) (c a) (a b) (b c) (c a), s presupunem prin absurd c exist a, b, c L a.. (a b) (b c) (c a) < (a b) (b c) (c a). Notm d = (a b) (b c) (c a), u = (a b) (b c) (c a), a = (d a) u, b = (d b) u i c = (d c) u. Diagrama Hasse a mulimii {d, a, b, c, u} este:

  • 14

    14

    u b a c d Cum {d, a, b, c, u}L este sublatice, dac vom verifica faptul c elementele d, a, b, c, u sunt distincte, atunci sublaticea {d, a, b, c, u} va fi izomorf cu M3 ceea ce va fi contradictoriu cu ipoteza pe care o acceptm. Deoarece d < u, vom verifica egalitile a b = b c=c a = u, a b = b c = c a = d i atunci va rezulta i c cele 5 elemente d, a, b, c, u sunt distincte. Datorit modularitii lui L avem: a = d (a u), b = d (b u), c = d (c u) iar datorit simetriei este suficient s demonstrm doar c a c = d. ntr-adevr, a c = ((d a) u) ((d c) u) = (d a) (d c) u = ((a b) (b c) (c a) a) (d c) u = =((b c) a) (d c) u = ((b c) a) ((a b) c) (a b) (b c) (c a) = ((b c) a) ((a b) c) = (b c) (a ((a b) c)) = (datorit modularitii) =(b c) (((a b) c) a)= (b c) ((a b) (c a)) = (datorit modularitii) = d. Corolar 1.13. Fie L o latice oarecare i x, yL. Atunci (x] (y]=(x y] iar (x y](x] (y]; dac LLd, atunci (x] (y] = (x y]. Demonstraie. Egalitatea (x] (y] = (x y] se probeaz imediat prin dubl incluziune iar incluziunea (x y](x] (y] este imediata. Dac LLd , atunci (x] (y] = {i j | i (x] i j (y]} = {i j | i x i j y}, de unde rezult imediat c (x] (y] (x y], deci (x y]=(x] (y]. n CURSUL nr. 4 1.Algebre Boole. Definiia1. Fie L o latice mrginit. Vom spune c elementul aL are un complement n L dac exist aL a.. a a = 0 i a a = 1 (a se va numi complementul lui a). Vom spune despre laticea L c este complementat dac orice element al su are un complement. Dac L este o latice oarecare i a, b L, a b, prin complementul relativ al unui element x[a, b] din intervalul [a, b], nelegem acel element x[a, b] (dac exist!) pentru care x x = a i x x = b. Vom spune despre o latice L c este relativ complementat dac orice element al su admite un complement relativ n orice interval din L ce-l conine.

  • 15

    15

    Lema 1.2. Dac LL(0, 1), atunci un element al lui L poate avea cel mult un complement. Demonstraie. Fie aL iar a, a doi complemeni ai lui a. Atunci a a = a a = 0 i a a = a a = 1, de unde a = a n Lema 1.3. Orice latice L modular i complementat este relativ complementat. Demonstraie. Fie b, c L, b c, a [b, c] i a L complementul lui a n L. Dac vom considera a = (a b) c [b, c], atunci a a= a [(a b) c] = [(a a) (a b)] c = (a b) c =b c= b iar a a= a [(a b) c] = (a a b) (a c) = 1 c = c, adic a este complementul relativ al lui a n [b, c]. n Lema1.4. (De Morgan) Fie LLd(0, 1), a, bL avnd complemenii a, b L. Atunci a b, a b au complemeni n L i anume (a b) = a b iar (a b) = a b. Demonstraie. Este suficient s probm c (a b) (a b) = 0 iar (a b) (a b) = 1. ntr-adevr, (a b) (a b) = (a b a) (a b b) = 0 0 = 0 iar (a b) (a b) = (a a b) (b a b) = 1 1 = 1. n Observaia 1.5. Dac LLd (0, 1) i aL are un complement aL, atunci a este cel mai mare element al lui L cu proprietatea c a a= 0 (adic a = sup ({x L | a x = 0}). Aceast observaie ne conduce la: Definiia1.6. Fie L o inf-semilatice cu 0 i aL. Un element a*L se zice pseudocomplementul lui a dac a*= sup ({x L | a x = 0}). Dac orice element al lui L are pseudocomplement, vom spune c inf - semilaticea L este pseudocomplementat O latice L se zice pseudocomplementat, dac privit ca inf-semilatice este pseudocomplementat. Lema 1.7.Dac L este o latice modular mrginit, atunci orice element ce are un complement a l va avea pe a i ca pseudocomplement. Demonstraie. ntr-adevr, fie aL, a un complement al lui a i bL a.. a b i b a = 0. Atunci b = b 1 = b (a a) = a (b a) = a 0 = a. n Teorema 1.8. Fie LLd (0) pseudocomplementat, R (L) = {a* | a L} iar D (L) = {a L | a* = 0}. Atunci, pentru a, b L avem: 1) a a* = 0 iar a b = 0 a b* 2) a b a* b* 3) a a** 4) a* = a*** 5) (a b)* = a* b* 6) (a b)** = a** b** 7) a b = 0 a** b** = 0 8) a (a b)* = a b* 9) 0* = 1, 1* = 0

  • 16

    16

    10) a R (L) a = a** 11) a, b R (L) a b R (L) 12) sup )(LR {a, b} = (a b)** = (a* b*)*

    13) 0, 1 R (L), 1 D (L) i R (L) D (L) = {1} 14) a, b D (L) a b D (L) 15) a D (L) i a b b D (L) 16) a a* D (L). Demonstraie. 1) Rezult din definiia lui a*. Echivalena rezult din definiia lui b*. 2) Deoarece b b* = 0, atunci pentru a b, deducem c a b*= 0, adic b* a*. 3) Din a a* = 0 deducem c a* a = 0, adic a (a*)* = a**. 4) Din a a** i 2) deducem c a*** a* i cum din 3) deducem c a* (a*)** = a*** rezult c a* = a***. 5) Avem (a b) (a* b*) = (a a* b*) (b a* b*) = 0 0 = 0. Fie acum x L a.. (a b) x = 0. Deducem c (a x) (b x) = 0, adic a x = b x = 0, de unde x a*, x b*, adic x a* b*. Restul afirmaiilor se probeaz analog. n Observaie 1.9. 1. Elementele lui R (L) se zic regulate iar cele ale lui D (L) dense. 2. innd cont de 4) i 10) deducem c R (L) = { a L : a** = a}. 3. Din 14) i 15) deducem c D (L) F (L). Teorema1.10. Fie LLd i aL. Atunci fa : L (a] [a), fa (x) = (x a, x a) pentru xL este un morfism injectiv n Ld. n cazul n care LLd (0, 1), atunci fa este izomorfism n Ld (0, 1) dac i numai dac a are un complement. Demonstraie. Faptul c fa este morfism de latici este imediat. Fie acum x, y L a.. fa (x) = fa (y) adic x a = y a i x a = y a. Cum LLd, atunci x = y , deci fa este ca funcie o injecie, adic fa este morfism injectiv n Ld. S presupunem acum c LLd (0, 1). Dac fa este izomorfism n Ld (0, 1), atunci pentru (0, 1) (a] [a) va exista xL a.. f (x) = (0, 1), adic a x = 0 i a x = 1, de unde x = a. Reciproc, dac a L este complementul lui a, pentru (u, v) (a] [a) alegnd x = (ua) v deducem imediat c fa (x) = (u, v), adic fa este i surjecie, deci izomorfism n Ld (0, 1). n Definiia1.11. Numim latice Boole orice latice complementat din Ld (0, 1). Exemple. 1. Lanul trivial 1 = {} ca i 2 = {0, 1} (n care 0 = 1 i 1 = 0). De fapt 1 i 2 sunt singurele lanuri ce sunt latici Boole. 2. Pentru orice mulime M, (P(M), ) este o latice Boole n care pentru orice X M, X = M \ X = CM (X). 3. Fie n, n 2 iar Dn mulimea divizorilor naturali ai lui n. Mulimea ordonat (Dn, ) este latice Boole n este liber de ptrate (n care caz pentru p, q Dn, p q = (p, q), p q = [p, q], 0 = 1, 1 = n iar p = n / p).

  • 17

    17

    4. Fie M o mulime iar 2M = {f : M 2}. Definim pe 2M relaia de ordine f g f (x) g (x) pentru orice xM. Astfel (2M, ) devine latice Boole (n care caz pentru f 2M, f = 1 - f). Definiia1.12. Din punctul de vedere al Algebrei Universale, prin algebr Boole nelegem o algebr (B, , , , 0, 1) de tipul (2, 2, 1, 0, 0) (cu i operaii binare, o operaie unar iar 0, 1 B operaii nule) a.. B1: (B, , ) Ld B2: Sunt verificate identitile x 0 = 0, x 1 = 1 x x = 0, x x = 1. n cele ce urmeaz prin B vom desemna clasa algebrelor Boole. Dac B1, B2 B, f : B1 B2 va fi morfism de algebre Boole dac f este morfism n Ld (0, 1) i n plus f (x) = (f (x)) pentru orice x B1. Morfismele bijective din B se vor numi izomorfisme. Propoziia1.13. (Glivenko) Fie (L, , *, 0) o inf-semilatice pseudocomplementat iar R (L) = {a* | a L}. Atunci, cu ordinea indus de pe L, R (L) devine algebr Boole. Demonstraie. Deducem imediat c L este mrginit (1 = 0*) iar pentru a, b R (L), a b R (L) iar sup R (L) {a, b} = (a* b*)* astfel c R (L) este latice mrginit i sub-inf-semilatice a lui L. Deoarece pentru aR (L), a a* = (a* a**)* = 0* = 1 i a a* = 0 deducem c a* este complementul lui a n R (L). Mai rmne de probat faptul c R (L) este distributiv. Pentru x, y, z R (L), x z x (y z) i y z x (y z), deci x z [x (y z)]* = 0 i (y z) [x (y z)]* = 0 astfel c z [x (y z)]* x*, y*, adic z [x (y z)]* x* y* i z [x (y z)]* (x* y*)* = 0 ceea ce implic z (x* y*) [x (y z)]**. Cum partea stng a acestei ultime inegaliti este z (x y) iar partea dreapt este x (y z) (n R (L)), deducem c z (x y) x (y z), adic R (L) este i distributiv. n Propoziia1.14. Fie B B i a, bB a.. a b = 0 i a b = 1. Atunci b = a Dac B B i a, b B, atunci (a) = a, (a b)=a b iar (a b) = a b. Demonstraie. Rezult imediat din cele de mai inainte Propoziia1.15. Dac M este o mulime oarecare, atunci algebrele Boole 2M i P(M) sunt izomorfe. Demonstraie. Fie XP(M) i X :M2,

    ( )

    =

    Xxpentru

    XxpentruxX 1

    0

    Se verific imediat c asocierea X X definete un izomorfism de algebre Boole : P(M)

    2M. n

    2.Legtura dintre inelele Boole i algebrele Boole.

    Definiia 2.1. Un inel (A, +, , -, 0, 1) se zice Boolean dac a2 = a pentru orice a A.

    Exemple 1. 2 este inel Boolean (n care 1 + 1 = 0).

  • 18

    18

    2. (P(X), , , , , X) cu X mulime oarecare iar diferena simetric de mulimi. Lema 2.2. Dac A este inel Boolean, atunci pentru orice a A, a + a = 0 iar A

    este comutativ.

    Demonstraie. Din a + a = (a + a)2 deducem c a + a = a + a + a + a, adic a + a = 0, deci -a = a.

    Pentru a, b A, din a + b = (a + b)2 deducem c a + b = a2 + ab + ba + +b2 adic ab + ba = 0 de unde ab = - (ba) = ba. n

    Legtura dintre algebrele Boole i inelele Boole ne este oferit de:

    Propoziia 2.3. (i) Dac (A, +, , -, 0, 1) este un inel Boole, atunci relaia "" de pe A definit prin a b ab = a confer lui A structur de algebr Boole, unde pentru a, b A, a b= ab, a b = a + b + ab iar a = 1 + a.

    (ii) Reciproc, dac (A, , , , 0, 1) este o algebr Boole, atunci A devine inel Boole fa de operaiile +, definite pentru a, b A prin a + b = (a b) (a b) i ab = a b iar -a = a.

    Demonstraie. (i) Faptul c (A, ) este mulime ordonat se probeaz imediat. Fie acum a, b A. Deoarece a (ab) = a2 b = ab i b (ab) = ab2 = ab deducem c ab a i ab b. Fie acum c A a.. c a i c b, adic ca = c i cb = c. Atunci c2 ab = c2 cab = c c ab, de unde concluzia c ab = a b.

    Analog se probeaz c a b = a + b + ab. Deoarece a (b c) = a (b + c + bc) = ab + ac + abc iar (a b) (a c) = =(ab) (ac) = ab

    + ac + a2 bc = ab + ac + abc deducem c a (b c) = (a b) (a c), adic A Ld. Deoarece pentru a A, a a = a (1 + a) = a (1 +a) = =a + a2 = a + a = 0 i a a = a (1 + a) = a + 1 + a + a (1 + a) = a + 1 + a + a + +a2 = 1 + a+ a + a + a = 1 deducem c (A, , , , 0, 1) este latice Boole.

    (ii) Pentru a, b, c A avem 1. a + (b + c) = [a (b + c)] [a (b + c)] = = {a [(b c) (b c)]} {a [(b c) (b c)]} = = {a [(b c) (b c)]} {(a b c) (a b c)} = = {a [(b c) (c b)]} {(a b c) (a b c)} = = (a b c) (a b c) (a b c) (a b c) = = (a b c) (a b c) (b c a) (c a b)

    Cum forma final este simetric n a, b i c deducem c a + (b + c) = = (a + b) + c. 2. a + b = (a b) (a b) = (b a) (a b) = b + a. 3. a + 0 = (a 0) (a 0) = (a 1) 0 = a. 4. a + a = (a a) (a a) = 0 0 = 0, deci -a = a. 5. a (bc) = a (b c) = (a b) c = (ab) c 6. a 1 = a 1 = a. 7. a (b + c) = a [(b c) (b c)] = (a b c) (a b c) iar (ab) + (ac) = (a b) + (a c) = [(a b) (a c)] [(a b) (a c)] = [a b (a c)] [(a b) (a c)] = [(a b a) (a b c)] [(a c a) (a c b)] = = (a b c) (a c b), de unde deducem c a (b + c) = ab + ac.

    Din 1-7 deducem c (A, +, , -, 0, 1) este inel Boolean unitar. n

    Teorema 2.4. Fie (B1, +, ), (B2, +, ) dou inele Boole iar (B1, , , , 0, 1), (B2, , , , 0, 1) algebrele Boole induse de aceste.

    Atunci f : B1 B2 este morfism de inele (unitare) dac i numai dac f este morfism de algebre Boole.

    Demonstraie. Totul rezult din definiia morfismelor de inele i de latici Boole n

  • 19

    19

    Teorema 2.5. Fie B1 i B2 dou algebre Boole iar f : B1 B2 o funcie. Urmtoarele condiii sunt echivalente:

    (i) f este morfism de algebre Boole; (ii) f este morfism de latici mrginite; (iii) f este morfism de inf-semilatici i f(x) = (f(x)) pentru orice xB1; (iv) f este morfism de sup-semilatici i f(x) = (f(x)) pentru orice xB1.

    Demonstraie. (i) (ii). Evident. (ii) (i). f(x) f(x) = f(x x) = f(0) = 0 i analog f(x) f(x) = f(x x) = f(1) = 1, deci

    f(x) = (f(x)). (iii) (i). f este morfism de sup semilatici deoarece f(x y) = f(x y) = f((x y)) =

    (f(x y)) = (f(x) f(y))= ((f(x)) (f(y))) = f(x) f(y) = f(x) f(y). Atunci f(0) = f(x x) = f(x) (f(x)) = 0 i analog f(1) = 1, deci f este morfism de algebre

    Boole. (i) (iii). Evident. (iv). Este afirmaia dual lui (iii) i deci echivalena (iv) (i) se demonstreaz analog ca i

    echivalena (i) (iii). n Teorema 2.6. Fie f : B1 B2 un morfism de algebre Boole iar Ker(f) = = f -1{0} = {xB1|

    f(x) = 0}. Atunci Ker(f) I(B1) iar f este ca funcie o injecie dac i numai dac Ker(f) = {0}. Demonstraie. Fie xKer (f) i yB1 a.. y x. Atunci, f fiind izoton f(y) f(x) = 0

    f(y) = 0 yKer (f). Dac x, yKer (f) atunci n mod evident i x y Ker (f), adic Ker (f) I(B1). S presupunem c Ker (f) = {0} i fie x, y Ker(f) a.. f(x) = f(y). Atunci f(xy) = f(x)f(y) = f(x)f(y) = f(x) f(x) = 0, deci x y Ker (f), adic x y = 0, deci x y. Analog se arat c y x, de unde x = y. Implicaia reciproc este evident (deoarece f(0) = 0). n

    Teorema 2.7. Fie f : B1 B2 un morfism de algebre Boole. Urmtoarele afirmaii sunt

    echivalente: (i) f este izomorfism de algebre Boole;

    (ii) f este surjectiv i pentru orice x, yB1 avem x y f(x) f(y); (iii) f este inversabil i f-1 este un morfism de algebre Boole. Demonstraie. (i) (ii). f izomorfism f surjecie. Orice morfism de latici este o funcie izoton, deci x y f(x) f(y).

    Fie f(x) f(y). Atunci f(x) = f(x) f(y) = f(x y) i cum f este injectiv x = x y, de unde x y.

    (ii) (iii). Artm c f este injectiv. Fie f(x) = f(y) f(x) f(y) i f(y) f(x) x y i y x x = y. Cum f este i surjecie, rezult c f este bijecie, deci este inversabil. S demonstrm de exemplu c f -1(x y ) = f -1(x) f -1(y), oricare ar fi x, yB2. Din x, yB2 i f surjecie rezult c exist x1 i y1B1 a.. f(x1) = x i f(y1) = y, deci f -1(x y ) = f -1 (f(x1) f(y1)) = f -1(f(x1 y1)) = x1 y1 = f -1(f(x1)) f -1(f(y1)) = f -1(x) f -1(y).

    Analog f -1(x y ) = f -1(x) f -1(y) i f -1 ( x) = (f -1(x)). (iii) (i). Evident. n

    Teorema 2.8. ntr-o algebr Boole (B, , , , 0, 1), pentru x,yB definim: x y = x y i x y = (xy) (yx) =(x y) (y x). Atunci pentru orice x, y, zB avem:

    (i) x y x y = 1; (ii) x 0 = x, 0 x = 1, x 1 = 1, 1 x = x, x x = 1, x x = x, x x

    = x; (iii) x ( y x ) = 1;

  • 20

    20

    (iv) x ( y z ) = ( x y ) ( x z); (v) x (y z) = ( x y) z ;

    (vi) Dac x y, atunci z x z y i y z x z; (vii) (x y) y = y, x ( x y ) = x y; (viii) (x y) (y z) x z; (ix) ((x y) y) y = x y;

    (x) (x y) y = (y x) x = x y; (xi) x y = sup { zB : x z y}; (xii) x (y z) = (x y) (x z); (xiii) (x y) z = (x z) (y z); (xiv) x (y z) = x [ (x y) (x z)] ;

    (xv) x y = 1 x = y.

    Demonstraie. (i). Dac xy =1 atunci x y =1 x y. (iii). x (yx) = x (y x) = 1 y = 1 Analog celelalte relaii . n

    CURSUL nr. 5 1.Filtre ntr-o algebr Boole.

    Aa cum am menionat anterior, prin filtru ntr-o algebr Boole (B,,,,0,1) nelegem un filtru al laticei (B,,,0,1). Ca i n cazul laticilor vom nota prin F(B) mulimea filtrelor lui B. Un filtru maximal propriu al lui B se va numi (ca i n cazul laticilor) ultrafiltru.

    Ca i n cazul laticilor deducem:

    Teorema.1.1. (i) n orice algebr Boole B exist ultrafiltre; (ii) Orice element x 0 este coninut ntr-un ultrafiltru. Corolar 1.2. Fie B o algebr Boole i x,yB, xy. Atunci exist un ultrafiltru U al lui B

    a.. xU i yU. Demonstraie. Dac x y, atunci x y i y x. Considerm c x y. Atunci x y 0 (cci dac x y = 0, atunci x y). Conform Teoremei

    1, (ii), cum x y 0 exist un ultrafiltru U al lui B a.. x yU. Cum x y x , y i U este n particular filtru deducem c x, yU. Cum U B deducem c yU. n

    Teorema 1.3. Fie (B, , , , 0, 1) o algebr Boole iar FF(B). Pe B definim urmtoarele relaii binare:

    x F y exist fF a.. x f = y f, x F y x y F.

    Atunci:

    (i) F = F not= F;

    (ii) F este o congruen pe B; (iii) Dac pentru xB notm prin x/F clasa de echivalen a lui x relativ la F, B/F = {x/F| xB}, atunci definind pentru x,yB, x/F y/F = = (xy)/F, x/F y/F = (xy)/F i (x/F) = x/F, atunci (B/F, , , , 0, 1) devine n mod canonic algebr Boole ( unde 0 = {0}/F = { xB | x F} iar 1= {1}/F = F).

    Demonstraie. (i). Fie x F y exist fF a.. x f = y f.

  • 21

    21

    Atunci x (x f) = x (y f) (x x) (x f) = (x y) (x f) x f = (x y) (x f). Cum fF, F filtru i f x f rezult c x f F xyF. Analog x yF, deci x y F, adic x F y. Invers, dac x F y x yF (x y ) (x y)F x y, x y F exist f1, f2F a .. x y=f1 i x y= f2. Atunci x f1 = x (x y) = (x x) (x y) = x y i analog y f2 = x y, deci dac f = f1 f2F, atunci x f = y f. (ii). Demonstrm c F este o relaie de congruen.

    -reflexivitatea: x F x deoarece x x = 1F. - simetria: x F y (x y ) (x y)F y F x. - tranzitivitatea: x F y i y F z implic x y , x y, y z , y z F. Atunci x z = x

    z ( y y)=( x z y) ( x z y) (x y) ( y z). Deoarece x y, y z F atunci x z F. Analog x z F, deci x F z. Astfel am demonstrat c F este o relaie de echivalen.

    Demonstrm compatibilitatea lui F cu operaiile ,,. Fie x F y i z F t. Atunci x y, z tF (x y) ( z t) F. Avem (x y)( z t)

    (x y t)( z t y) = (x z) ( y t) = (x z) (y t), deci (x z) (y t) F. Analog (y t) (x z), deci (x z) F (y t). Fie x F y. Atunci x yF i xy = (x y)(y x) = (x y) (x y) = x y,

    deci x F y. Fie x F y i z F t. Conform celor de mai sus x F y i z F t i cum F este compatibil cu

    , avem (x z) F (y t) (x z) F (y t) (x z) F (y t). Cu aceasta am stabilit c F este o congruen. (iii). Totul rezult din faptul c F este o congruen pe B . n

    Teorema 1.4. Fie B1, B2 dou algebre Boole iar f : B1 B2 este un morfism de algebre Boole. Notm prin Ff = f-1({1}) = {xB1 : f(x) = 1}. Atunci: (i) Ff F(B1); (ii) f ca funcie este injecie Ff = {1}; (iii) B1/ Ff Im(f) ( unde Im(f) = f(B1)).

    Demonstraie. (i). Se verific imediat prin dualizarea teoremei corespunzatoare de lalatici. (ii). Dac f este injectiv i xFf atunci din f(x) = 1 = f(1) x = 1. Dac Ff = {1} i f(x) =

    f(y), atunci f(x y) = f(x y) = 1, deci x y = x y = 1, adic x y i y x, deci x = y. (iii). Considerm aplicaia : B1/Ff f(B1) definit prin (x/Ff) = f(x), pentru orice x/Ff B1/Ff. Deoarece pentru x,yB1: x/Ff = y/Ff x F f y (xy)(xy)Ff (conform Teoremei 1) f((xy)(xy)) = 1 f(xy)=f(xy)=1 f(x)=f(y) (x/Ff) = (y/Ff), deducem c este corect definit i injectiv. Avem : (x/Ff y/Ff) = ((x y) / Ff) = f( xy ) = f(x) f(y) = (x/Ff) ( x/Ff); analog se arat c (x/Ff y/Ff) = (x/Ff) ( y/Ff) i (x/Ff) = ( (x/Ff)), deci este morfism de latici Boole. Fie y = f(x) f(B1), xB1; atunci x/Ff B1/Ff i ( x/Ff) = f(x) = y, deci este surjectiv, adic izomorfism. n

    Teorema 1.5 . Pentru un filtru propriu F al unei algebre Boole B urmtoarele afirmaii sunt echivalente: (i) F este ultrafiltru; (ii) Pentru orice xB \ F avem c xF .

    Demonstraie. S observm c nu putem avea x, xF deoarece atunci x x = 0F, adic F = B, absurd.

    (i) (ii). Presupunem c F este ultrafiltru i c xF. Atunci [F{x}) = B. Deoarece 0B, exist x1,,xnF a.. x1 xn x = 0, deci x1 xn x, de unde concluzia c xF ( cci x1 xn F i F este un filtru).

  • 22

    22

    (ii) (i). S presupunem c exist un filtru propriu F1 a.. F F1, adic exist xF1 \ F. Atunci xF, deci xF1 i cum xF1 deducem c 0F1, deci F1 = B, absurd. Deci F este ultrafiltru. n Teorema 1.6. Pentru un filtru propriu F al unei algebre Boole B urmtoarele afirmaii sunt echivalente: (i) F este ultrafiltru; (ii) 0 F i pentru orice elemente x, yB dac x yF atunci xF sau yF ( adic F este filtru prim). Demonstraie. (i) (ii). Presupunem c x y F i xF.

    Atunci [F{x}) = B i atunci cum 0B exist zF a.. z x = 0. Deoarece z, x y F rezult c z (x y) = (z x) (z y) = 0 (z y) = z yF. Cum z y y deducem c yF. (ii) (i). Cum pentru orice xB, x x = 1, deducem c xF sau xF i atunci F este un ultrafiltru. n

    Teorema 1.7. Pentru un filtru propriu F al unei algebre Boole B urmtoarele afirmaii sunt echivalente: (i) F este ultrafiltru;

    (ii) B/F 2. Demonstraie. (i) (ii). Reamintim c B/F = {x/F | xB} (vezi Teorema 3). Fie xB a.. x/F

    1. Atunci xF ,deci xF, adic x/F = 1. Dar (x/F) = x/F, deci x/F = (x/F) = 1 = 0, de unde concluzia c B/F = = {0,1} 2.

    (ii) (i). Dac xF atunci x/F 1, deci x/F = 0 iar x/F = (x/F) = 0 = 1, adic xF i deci F este ultrafiltru. n Teorema 1.8. (Stone). Pentru orice algebr Boole B exist o mulime M a.. B este izomorf cu o subalgebr Boole a algebrei Boole (P(M), ).

    Demonstraie. Vom nota prin M = UB mulimea ultrafiltrelor lui B iar despre uB : B P(UB), uB(x) = {F UB : xF} vom arta c este morfism injectiv de algebre Boole ( astfel c B va fi izomorf cu uB(B))

    Dac x,yB i x y atunci exist F UB a.. xF i yF, adic F uB(x) i F uB(y), deci uB(x) uB(y).

    n mod evident u(0) = i u(1) = UB. Fie acum x,yB i F UB. Avem: F uB(xy) x yF xF i yF deci uB(x y) =

    uB(x) uB(y). Deducem c uB(x y) = uB(x) uB(y), iar apoi uB(x) = (uB(x)), adic uB este i morfism de

    algebre Boole. n

    CURSUL nr. 6 1.Operaii algebrice. Monoizi. Morfisme de monoizi.

    Produse directe finite de monoizi

    Definiia 1.1. Fiind dat o multime nevid M, numim operatie algebric (intern) sau lege de compoziie (intern) pe M orice funcie :M MM. Pentru uurina scrierii vom nota pentru x, yM pe (x, y) (care se mai numete i compusul lui x cu y) prin xoy sau pur i simplu prin xy (convenim s spunem c am notat operaia algebric multiplicativ).

    n anumite situaii folosim pentru i notaia aditiv ,,+.

  • 23

    23

    Exemple 1. Dac T este o mulime nevid iar M=P(T), n capitolul precedent am definit pe M operaiile

    algebrice de intersecie, reuniune, diferen i diferena simetric. 2. Dac A este o mulime nevid iar Hom(A)={f:AA}, atunci pe Hom(A) avem operaia de compunere a funciilor: : Hom(A) Hom(A) Hom(A), (f, g) = fog pentru orice f, g Hom(A). Pe parcursul acestei lucrri vom mai pune n eviden alte mulimi i operaii algebrice pe acestea (inclusiv mulimile numerelor ntregi , raionale , reale i complexe precum i operaiile de adunare i nmulire pe acestea).

    Definiia1.2. Dac M este mulime nevid, vom spune despre o operaie algebric de pe M (notat multiplicativ) c este:

    (i) comutativ dac pentru oricare x, yM, xy = yx (ii) asociativ dac pentru oricare x, y, zM, (xy)z = x(yz).

    Operaiile de intersecie, reuniune i diferen simetric sunt exemple de operaii ce sunt

    simultan comutative i asociative, pe cnd compunerea funciilor nu este operaie comutativ fiind ns asociativ.

    Dac o operaie algebric de pe M este asociativ, atunci pentru a scrie compunerea a trei elemente x, y, z din M (sau mai multe) nu mai este necesar s folosim parantezele, astfel c n loc s scriem (xy)z sau x(yz) vom scrie xyz.

    Pentru n elemente x1,,xn (n) din M utilizm de multe ori notaiile: x1x2xn=

    =

    n

    iix

    1 (cnd operaia algebric asociativ este notat multiplicativ) sau

    x1+x2++xn = =

    n

    iix

    1 (cnd aceeai operaie algebric asociativ este notat aditiv).

    Dac x1=x2==xn=x i n* convenim s notm x1x2xn = xn dac operaia algebric este notat multiplicativ i x1+x2++xn = nx dac ea este notat aditiv.

    Definiie Fie M o mulime nevid pe care avem o operaie algebric. Vom spune c un element eM este element neutru pentru operaia algebric respectiv dac pentru orice xM, xe = ex = x.

    Observaie 1.3. (i). Dac o operaie algebric de pe M ar avea dou elemente neutre e, eM, atunci

    ee=e (dac gndim pe e element neutru) i tot ee=e (dac gndim pe e element neutru) astfel c e=e. Deci, elementul neutru al unei operaii algebrice (dac exist !) este unic.

    (ii). n cazul adoptrii notaiei multiplicative pentru o operaie algebric, elementul su neutru (dac exist) va fi notat prin 1, iar n cazul adoptrii notaiei aditive acesta se va nota prin 0.

    Exemple 1. Dac T, atunci pentru operaiile algebrice , i de pe M=P(T) elementele neutre

    sunt T, i respectiv . 2. Dac A, atunci pentru compunerea funciilor de pe Hom(A), 1A este elementul neutru.

    Definiia 1.4. Un dublet (M, ) format dintr-o mulime nevid M i o operaie algebric pe M se zice semigrup dac operaia algebric respectiv este asociativ. Dac operaia algebric are i element neutru, semigrupul (M, ) se zice monoid. Dac operaia algebric este comutativ, monoidul se zice comutativ.

    De multe ori, n cazul unui semigrup se specific doar mulimea subiacent M (far a se mai specifica operaia algebric de pe M; dac este pericol de confuzie atunci i aceasta trebuie neaprat menionat).

  • 24

    24

    Exemple 1. Dac T i M = P(T), atunci (M, ), (M , ) i (M, ) sunt monoizi comutativi.

    2. Dac A , atunci (Hom(A),o) este monoid necomutativ.

    S revenim acum la cazul general al semigrupurilor. Urmtorul rezultat este imediat:

    Propoziia 1.5. Dac M este un semigrup, xM iar m, n*, atunci xmxn=xm+n iar (xm)n=xmn.

    Dac mai avem yM a.. xy=yx, atunci (xy)n=xnyn. Definiia1.6.. Dac M, M sunt monoizi, o funcie f:MM se zice morfism de monoizi

    dac f(1)=1 i f(xy)=f(x)f(y) pentru orice x, yM.

    Vom nota prin Mon clasa monoizilor iar pentru M, MMon vom nota prin HomMon(M, M) (sau mai simplu Hom(M, M) dac nu este pericol de confuzie) toate morfismele de monoizi de la M la M, adic Hom(M, M) = ={f:MM/ f este morfism de monoizi}.

    Propoziia1.7. Dac M, M, M sunt monoizi iar fHom(M, M) i gHom(M, M) , atunci gofHom(M, M).

    Demonstraie. Cum f(1) = g(1), (gof)(1) = g(f(1)) = g(1) = 1 iar pentru x, yM avem

    (gof)(xy) = g(f(xy)) = g(f(x)f(y)) = g(f(x))g(f(y)) = (gof)(x)(gof)(y), adic gof Hom(M, M).

    Definiia1.8. Dac M i M sunt doi monoizi, numim izomorfism de monoizi un morfism fHom(M, M) pentru care exist gHom(M, M) a.. fg = 1M i gf = 1M; n acest caz vom spune despre monoizii M, M c sunt izomorfi i vom scrie MM.

    Se deduce imediat c fHom(M, M) este izomorfism de monoizi dac i numai dac f este bijecie; atunci f -1:MM este morfism de monoizi.

    Definiia1.9. Fie (M, ) un monoid. Vom spune despre un element xM c este inversabil

    (sau simetrizabil ) dac exist xM a.. xx=xx=1. S observm c dac x exist atunci el este unic deoarece dac ar mai exista xM a..

    xx=xx=1, atunci x(xx)=x1=x i x(xx)=(xx)x=1x=x, adic x=x. Elementul x poart numele de inversul (sau simetricul) lui x. n cazul notaiei multiplicative

    vom nota x=x-1 iar n cazul notaiei aditive vom nota x=-x (iar x se va numi opusul lui x). n cele ce urmeaz (pn la specificri suplimentare) vom considera monoizi multiplicativi.

    Pentru monoidul (M, ) prin U(M, ) (sau mai simplu U(M) dac nu se creeaz confuzii prin nespecificarea operaiei algebrice de pe M ) vom nota mulimea elementelor inversabile din M (adic U(M)={xM / exist xM a.. xx=xx=1}).

    Evident, dac xU(M), atunci x -1U(M) iar (x -1) -1=x. Pentru exemplele de monoizi de pn acum avem: U(P(T),)={T}, U(P(T),)={},

    U(P(T),)=P(T), U(,+)={0}, U(,) = {1}, iar pentru o mulime A, U(Hom(A),o)={f:AA / f este bijecie}. Convenim s notm (A)={fHom(A) / f este bijecie} i s numim un element f(A) ca fiind o permutare asupra elementelor lui A.

    Propoziia1.10.Fie (M, ) un monoid i x, yU(M). Atunci 1U(M), xyU(M) iar (xy)-1=y-1x-1.

    Demonstraie. Din 11=11=1 deducem c 1U(M) iar din (xy)(y-1x-1) = =x(yy-1)x-1 = x1x-1 =

    xx-1 = 1 i (y-1x-1)(xy) = y-1(x-1x)y = y-11y=y-1y=1 deducem c xyU(M) iar (xy)-1=y-1x-1.

  • 25

    25

    Observaie. Raionnd inductiv dup n deducem c dac x1,,xnU(M) (n2), atunci x1x2xnU(M) iar (x1x2xn)-1=xn-1x2-1x1-1. Fie acum M1, M2, , Mn monoizi iar M = M1Mn={(x1, , xn) / xiMi , 1 i n}. Pentru x=(x1,,xn), y=(y1,,yn)M definim xy=(x1y1,,xnyn) iar pentru fiecare 1 i n considerm pi :MMi definit prin pi (x)=xi pentru orice x=(x1,,xn)M ( pi se zice a i-a proiecie a lui M pe Mi sau proiecia de indice i ).

    Propoziia 1.11. Dac M1,,Mn sunt monoizi, atunci (M, ) este monoid, U(M)=U (M1)U (Mn), pentru fiecare 1 i n, pi Hom(M,Mi ) i n plus este verificat urmtoarea proprietate de universalitate : Pentru oricare monoid M i familie de morfisme de monoizi (pi)1 i n cu piHom(M, Mi ), 1 i n, exist un unic uHom(M, M) a.. pi ou=pi .

    Demonstraie. Asociativitatea operaiei de nmulire de pe M rezult din asociativitatea

    fiecrei operaii de nmulire de pe Mi iar elementul neutru este 1=(1,,1). Dac xU(M), x=(x1,,xn), atunci exist yM , y=(y1,,yn) a.. xy=yx=1

    (x1y1,,xnyn)=(y1x1,,ynxn)=(1,,1) xiyi = yixi = 1 pentru orice 1 i n xiU(Mi) pentru orice 1 i nxU(M1) U(Mn), de unde egalitatea (de mulimi). U(M)= U(M1) U(Mn).

    Dac x=(x1,,xn), y=(y1,,yn)M i 1 i n, atunci xy=(x1y1,,xnyn), deci pi (xy) =xi yi =pi (x)pi (y), adic pi Hom(M, Mi).

    S verificm acum proprietatea de universalitate, iar pentru aceasta fie M un alt monoid i pentru 1 i n s considerm piHom(M, Mi). Pentru xM, definim u:MM prin u(x)=(p1(x),,pn(x)) i se verific imediat c uHom(M, M) iar piou=pi , pentru orice 1 i n.

    Fie acum uHom(M, M) a.. piou=pi pentru orice 1 i n. Atunci pentru orice xM avem pi(u(x)) = pi(x), adic u(x)=(p1(x),,pn(x))=u(x), de unde u=u.

    Definiia 1.12. Monoidul M=M1 Mn mpreun cu proieciile (pi)1in poart numele de produsul direct al monoizilor M1, M2, , Mn (cnd nu este pericol de confuzie nu vom mai specifica proieciile). CURSUL nr. 7 1. Grup. Calcule ntr-un grup. Subgrup.

    Subgrup generat de o mulime. Grup ciclic. Ordinul unui element ntr-un grup.

    Definiia1.1. Vom spune despre un monoid M c este grup dac U(M)=M. Altfel zis,

    dubletul (M, ) format dintr-o mulime M i o operaie algebric pe M este grup dac operaia algebric este asociativ, admite element neutru i orice element din M este inversabil. Grupul M se va zice comutativ ( sau abelian ) dac operaia algebric este comutativ.

    Exemple. 1. Dac T este o mulime nevid atunci (P(T), ) este grup comutativ. 2. Dac A este o mulime nevid, atunci ((A) , o) este grup ( n general necomutativ). 3. Mai general, dac (M, ) este un monoid atunci (U (M), ) este grup.

  • 26

    26

    n cele ce urmeaz prin (G, ) vom desemna un grup multiplicativ (dac nu este pericol de confuzie nu vom mai specifica operaia algebric). Cardinalul mulimii G se va nota | G | i se va numi ordinul grupului G .

    n consecin, elementul neutru al lui G va fi notat cu 1 iar pentru xG inversul su va fi notat prin x-1 .

    Analog ca n cazul semigrupurilor, dac pentru xG definim x0 = 1, atunci (x-1)-1= x iar dac m, n, atunci xm xn = xm+n i (xm)n = xmn. De asemenea, dac x, y G i xy = yx, atunci pentru orice n (xy)n = xn y n.

    Definiia1.2. O submulime nevid S a lui G se zice subgrup al lui G dac S mpreun cu restricia operaiei algebrice de pe G la S formeaz grup.

    Vom nota prin L(G) mulimea subgrupurilor lui G; pentru a exprima c HL(G) vom indica

    lucrul acesta scriind c HG. Propoziia1.3. Pentru o mulime nevid S a lui G urmtoarele afirmaii sunt echivalente:

    (i) SL(G) ; (ii) 1S i pentru orice x, yS, xyS i x -1S ;

    (iii) pentru orice x, yS , x-1yS.

    Demonstraie. Implicaiile (i)(ii) i (ii)(iii) sunt imediate. (iii)(i). Cum S exist x0S i atunci 1=x0-1x0S. Alegnd un element oarecare xS,

    cum 1S avem c i x-1=x-11S adic (S, ) este grup. n mod evident, {1}L(G) i GL(G). Oricare alt subgrup S al lui G diferit de {1} i G se

    zice propriu. Subgrupul {1} se zice subgrup nul i se noteaz de obicei prin 0.

    Propoziia1.4. Fie (Si)iI o familie nevid de subgrupuri ale lui G . Atunci, IIi

    iS

    L(G).

    Demonstraie. Fie S= I

    IiiS

    i x, y S . Atunci pentru orice iI, x, ySi i cum SiG avem c

    x -1ySi , adic x-1yS, deci SG. Observaia1.5. n ceea ce privete reuniunea a dou subgrupuri ale lui G s demonstrm c

    dac H, KL(G), atunci HKL(G)HK sau KH. Implicaia de la dreapta la stnga fiind evident s presupunem c HKL(G) i totui HK i KH , adic exist xH astfel nct xK i yK astfel nct yH. Considernd elementul z=xy atunci cum am presupus c HKL(G) ar trebui ca zHK. Dac zH, atunci cum y=x-1z am deduce c yH absurd. Dac zK atunci ar rezulta c x = zy -1K absurd !. Din cele expuse mai nainte deducem c n general, dac H, KL(G) nu rezult cu necesitate c i HKL(G). Este una din raiunile pentru care vom introduce noiunea ce urmeaz.

    Definiia1.6. Dac M este o submulime nevid a lui G, prin subgrupul lui G generat de M nelegem cel mai mic subgrup al lui G ( fa de relaia de incluziune ) ce conine pe M i pe care l vom nota prin . Altfel zis

    = ISM

    L(G)Ss .

    Dac ML(G), n mod evident =M.

    Propoziia1.7. Dac MG este o submulime nevid, atunci = {x1 xn | n iar xi M sau xi-1 M pentru orice 1in }.

  • 27

    27

    Demonstraie. Fie H={x1 xn | n iar xi M sau xi-1 M pentru orice 1in } i x, yH, adic x=x1 xn , y=y1 ym cu xi sau xi-1 n M i yj sau yj-1 n M pentru 1in i 1jm. Cum x-1y = xn-1 x1-1 y1 ym deducem c x-1yH, adic HG. Deoarece MH iar este cel mai mic subgrup al lui G ce conine pe M deducem c H .

    Fie acum SG astfel nct MS. Atunci HS, deci H ISM

    GSs =, de unde egalitatea

    =H. Corolar 1.8 . ={xn | n}{(x-1)n | n}.

    Definiie. poart numele de grupul ciclic generat de x. Ordinul unui element xG

    notat o(x) se definete ca fiind o(x)=||. Evident, o(1)=1 iar dac x1 i o(x)=n, atunci n este cel mai mic numr natural pentru care xn=1. Dac o(x)=, atunci xn1, pentru orice n1.

    Observaia 1.9. 1. Dac Gx este de ordin finit i exist n * a.. 1=nx , atunci o(x) n . ntr-adevr, mprind pe n la o(x) gsim c, r a. rxocn += )( i ).(xor < Din 1)( == nxo xx deducem imediat c i 1=rx , adic r = 0 (innd cont de minimalitatea lui

    o(x)), deci o(x) n . 2. Dac Gyx , , a.. o(x) i o(y) sunt finite, xy = yx i (o(x), o(y)) = 1, atunci o(xy) =

    o(x)o(y). ntr-adevr, dac notm m = o(x), n = o(y) i p = o(xy), din 1== nm yx deducem c

    1)( == mnmnmn yxxy , adic p mn . Din o(xy) = p deducem c 1)( =pxy , deci pp yx = iar de aici

    1)( == pnnp yx , adic npm i cum (m,n) = 1 deducem c pm . Analog pn i cum (m,n) = 1 deducem c pmn , adic p = mn.

    3. Din cele de mai nainte deducem recursiv c dac Gxxx n ,...,, 21 ( 2n ) i cele n elemente comut ntre ele iar ordinele a oricare dou (diferite) sunt prime ntre ele, atunci

    ).()...()...( 11 nn xoxoxxo =

    Propoziia1.10. (L(G), ) este latice complet. Demonstraie. n mod evident 0={1}, 1=G iar pentru H, KL(G), HK=HK iar

    HK=. Dac (Si)iI este o familie oarecare de subgrupuri ale lui G, atunci Ii

    Si = IIi

    Si

    L(G) iar Ii

    Si = < UIi

    Si > L(G).

    2.Subgrupuri normale. Factorizarea unui grup printr-un subgrup normal

    Definiia 2.1. Vom spune despre un subgrup H al lui G c este normal n G dac xH = Hx pentru orice xG i vom scrie HG pentru a desemna faptul acesta.

    Vom nota prin L0(G) mulimea subgrupurilor normale ale lui G. Evident, L0(G) L(G), {1}, G L0(G) iar dac G este comutativ, atunci L0(G)= L(G).

    Propoziia 2.2. Pentru HL(G) urmtoarele afirmaii sunt echivalente (i) H L0(G) (ii) Pentru orice xG, xHx-1H (unde xHx-1={xhx-1 : hH}).

    Demonstraie. (i) (ii). Dac HG i xG, atunci xH=Hx, deci pentru hH, xh=kx cu kH astfel c xhx-1 = kH.

  • 28

    28

    (ii)(i). Fie xG. Din xHx-1H deducem imediat c xHHx. nlocuind pe x cu x-1 deducem c x-1H Hx-1, de unde HxxH, adic xH=Hx, deci H L0(G).

    Propoziia 2.3. L0(G) este sublatice modular marginit a lui L(G). Demonstraie. Am vzut c {1} i G fac parte din L0(G). Fie acum H, K L0(G), xG i

    hHK. Atunci xhx-1H, K deci xhx-1HK, adic HK L0(G). S artm acum c HK =HK=KH (unde HK= {hk|hH, kK}). Avem HK= U U

    Hx HxKHKxxK

    == .

    n mod evident H, KHK iar dac alegem SG astfel nct H, KS atunci HKS, adic HK=KH=HK. Pentru a arta c HKG, fie xG, hH i kK.

    Scriind x(hk)x-1=(xhx-1)(xkx-1), cum xhx-1H i xkx-1K, deducem c x(hk)x-1 HK, adic HKG, deci i HKL0(G). Am demonstrat deci c L0(G) este sublatice (mrginit) a lui L(G). Pentru a proba c L0(G) este modular fie H, K, LL0(G) astfel nct HK i s artm c K(HL)=H(KL). innd cont de cele stabilite anterior este suficient s probm incluziunea K(HL)H(KL) (cealalt fiind evident) iar pentru aceasta fie xK(HL). Atunci xK i xHL ceea ce implic x=yz cu yH i zL. Avem z=y-1xK i cum zL deducem c zKL.

    Cum yH rezult x=yzH(KL), adic avem K(LH)H(KL).

    Dac HG, atunci (G/H)s=(G/H)d=G/H. Pentru xH, yHG/H (cu x,yG) definim (xH)(yH)=(xy)H i s artm c fa de aceast

    operaie algebric G/H devine grup. Dac mai avem x, yG astfel nct xH=xH i yH=yH atunci x-1x, y-1yH.

    Pentru a proba c (xy)H=(xy)H scriem (xy)-1(xy)= =y-1x-1xy=[y-1(x-1 x)y](y-1y), de unde deducem c (xy)-1(xy)H, adic (xy)H=(xy)H i astfel nmulirea pe G/H este corect definit. Ea este i asociativ deoarece pentru xH, yH, zHG/H cu x, y, zG avem

    (xH)[(yH)(zH)]=(xH)[(yz)H]=[x(yz)]H=[(xy)z]H=[(xy)H](zH)= =[(xH)(yH)](zH) Elementul neutru va fi 1H=H iar pentru xHG/H avem (x-1H)(xH)=(x-1xH)=H i (xH)(x-1H)=(xx-1)H=H, de unde deducem c (xH)-1=x-1H.

    Definiia 2.4. Grupul (G/H, ) poart numele de grupul factor al lui G prin subgrupul normal H. Aplicaia pH:GG/H, pH(x)=xH pentru orice xG poart numele de surjecia canonic.

    Observaia 2.5. 1. n mod evident |G/H|=|G:H|, astfel c dac G este finit, |G/H|=|G|:|H|. 2. Dac HG i |G:H|=2, atunci HG, (deoarece alegnd xG\H, din HxH = HHx= i

    HxH=HHx=G deducem c xH=Hx).

    n continuare vom prezenta un alt mod de a introduce grupul factor G / H cnd HG. S presupunem la nceput c H este doar subgrup al lui G (fr a fi normal). Pe G definim dou relaii sH i

    dH astfel:

    (x, y) sH x-1yH i (x, y) dH xy-1H. Se verific imediat c sH i

    dH sunt relaii de echivalen pe G iar pentru xG,

    [ ] xHx sH

    = i [ ] Hxx dH = . n cazul n care HG , atunci sH = dH H i s artm c H este o congruen pe G

    (adic compatibil cu structura de grup a lui G). Pentru aceasta fie x, x, y, yG a.. (x, x), (y, y) H i s artm c i (xy, xy) H . Avem (xy)-1(xy)=y-1x-1xy= [y-1(x-1x)y](y-1y) i cum

  • 29

    29

    x-1x, y-1yH iar HG (adic y-1(x-1x)yH) deducem imediat c (xy)-1(xy)H adic, (xy, xy) H . Astfel G / H = HGxHx GxGxH /}{}]{[ == i de aici construcia grupului factor G / H continu ca mai nainte.

    Observaia 2.6. Am vzut c dac HG, atunci H este o congruen pe G (adic o relaie

    de echivalen pe G compatibil cu structura de grup a lui G). Se poate arta imediat c asocierea H H stabilete o bijecie ntre L0(G) i congruenele de

    pe G. ntr-adevr, dac este o congruen pe G, atunci se arat uor c

    [ ] ( ){ } = 1,1 xGx L0(G) i astfel, asocierea [1] este inversa funciei H H (de mai nainte). CURSUL nr. 8

    1.Morfisme de grupuri. Compunerea morfismelor de grupuri. Monomorfisme, epimorfisme, izomorfisme de

    grupuri.

    Definiia 1.1. Dac G i G sunt dou grupuri, vom spune c o funcie f:GG este morfism de grupuri dac pentru orice x, yG, f(xy)=f(x)f(y).

    Vom nota HomGr(G, G)={f:GG|f este morfism de grupuri}. Dac nu este pericol de confuzie n loc de HomGr(G, G) vom scrie Hom(G, G).

    Exemple. 1. Funcia 1G:GG este morfism de grupuri. 2. f : GG, f(x)=1 pentru orice xG este de asemenea morfism de grupuri (numit

    morfismul nul). 3. Dac HG atunci pH :GG/H, pH(x)=xH pentru orice xG este morfism surjectiv de

    grupuri (numit morfismul surjectiv canonic).

    Observaia.1.2. Ca i n cazul monoizilor se demonstreaz imediat c dac G, G, G sunt grupuri i fHom(G,G), gHom(G,G), atunci gofHom(G,G).

    Propoziia 1.3. Dac G, G sunt grupuri i fHom(G, G), atunci f(1)=1 i f(x-1) = (f(x))-1 pentru orice xG.

    Demonstraie. Din 1=11 deducem c f(1)=f(11)=f(1)f(1) iar de aici c f(1) =1. Dac xG, cum xx-1 = 1 deducem 1 = f(1) = f(xx-1) = =f(x) f(x-1), de unde f(x-1)=f(x)-1.

    Propoziia 1.4. Fie G, G grupuri iar fHom(G, G).

    (i) Dac HG atunci f(H)G (ii) Dac HG i f este funcie surjectiv, atunci f(H)G

    (iii) Dac HG, atunci f-1(H)G (iv) Dac HG, atunci f-1(H)G.

    Demonstraie. (i). Dac x, yf(H), atunci x=f(x), y=f(y) cu x, yH i cum x-1y =(f(x))-1

    f(y)=f(x-1y) iar x-1yH deducem c x-1yf(H), adic f(H)G. (ii). Dac xG i hf(H) atunci cum f este surjecie x=f(x) cu xG i h=f(h) cu hH. Deoarece

    xhx-1=f(xhx-1) iar xhx-1H (cci HG) deducem c xhx-1 f(H), adic f(H)G.

  • 30

    30

    (iii). Dac x, yf-1(H), atunci f(x), f(y)H i cum HG deducem c f(x)-1 f(y)=f(x-1y)H, adic

    x-1y f-1(H), deci f-1(H)G. (iv). Fie xG i yf-1(H) (adic f(y)H). Cum HG avem f(x)f(y)f(x)-1H sau f(xyx-1)H, deci xyx-1f-1(H), adic f-1(H)G.

    Observaia 1.5. Dac fHom(G, G), conform propoziiei precedente deducem c f-1({1})G iar f(G)G. Convenim s notm f-1({1})=Ker(f) i s-l numim nucleul lui f iar f(G)=Im(f) i s-l numim imaginea lui f.

    Astfel, pentru orice fHom(G, G), Ker(f)G iar Im(f)G.

    Propoziia 1.6. Dac G, G sunt grupuri iar fHom(G, G), urmtoarele afirmaii sunt echivalente:

    (i) f este funcie injectiv (ii) Ker(f)={1}

    (iii) Pentru orice grup G i , Hom(G, G), dac fo=fo, atunci =. Demonstraie. (i) (ii). Evident {1}Ker(f). Dac xKer(f) atunci f(x)=1=f(1) i cum f

    este injecie deducem c x=1, adic Ker(f)={1}. (ii)(i). Dac x, yG astfel nct f(x)=f(y), cum f(x-1y)=(f(x))-1f(y)=1 deducem c

    x-1yKer(f)={1}, adic x-1y=1 deci x=y, rezultnd astfel c f este injecie. (i)(iii). Evident (iii)(i). S presupunem prin absurd c f nu este injectiv (dei verific (iii)). Cum (i)

    (ii), deducem c Ker(f){1}. Dac notm G=Ker(f) i considerm , :G G, =incluziunea iar = morfismul nul (adic (x)=1 pentru orice xG), atunci i fo=fo (cci ambele dau morfismul nul) absurd !.

    Observaia 1.7. Datorit propoziiei precedente vom numi morfismele injective de grupuri monomorfisme. Monomorfismele se mai zic i scufundri.

    Propoziia 1.8. Dac G, G sunt grupuri iar fHom(G, G), atunci n ipoteza c G este comutativ, urmtoarele afirmaii sunt echivalente:

    (i) f este surjecie (ii) Im(f)=G (iii) Pentru orice grup G i orice morfisme , Hom(G,G), dac of=of, atunci =.

    Demonstraie. Echivalena (i) (ii) este imediat.

    (i)(iii). Dac yG cum f este surjecie exist xG astfel nct f(x)=y. Atunci (of)(x)=( of)(x) (f(x))= (f(x)) (y)=(y), adic =. (iii)(i). S presupunem c f verific (iii) i totui nu este surjectiv, adic Im(f)G. Alegnd G=G/Im(f) (lucru posibil deoarece prin ipotez G este comutativ i deci Im(f)G) avem c G{1} i astfel alegnd =pIm(f):GG i = morfismul nul de la G la G avem c dei of=of (cci ambele compuneri dau morfismul nul) absurd.

    Observaia 1.9. Datorit propoziiei precedente morfismele surjective fHom(G, G) cu G comutativ se mai zic i epimorfisme.

    Definiia 1.10. Dac G, G sunt grupuri, vom spune c fHom(G, G) este izomorfism de grupuri dac exist gHom(G, G) astfel nct gof=1G i fog=1G. n acest caz vom spune despre grupurile G i G c sunt izomorfe i vom scrie G G.

  • 31

    31

    2.Teoremele de izomorfism pentru grupuri

    Vom ncepe cu o teorem cunoscut sub numele de teorema fundamental de izomorfism pentru grupuri:

    Teorema.2.1. Dac G, G sunt grupuri iar fHom(G, G), atunci G/Ker(f)Im(f). Demonstraie. Dac notm H=Ker(f) atunci H={xG | f(x)=1}G iar G/Ker(f)={x Ker f |

    xG}={xH | xG}. Definim :G/Ker(f)Im(f) prin (xH)=f(x) pentru orice xG. Dac x, yG, atunci din

    echivalenele xH=yH x-1yH f(x-1y)=1 f(x)=f(y) deducem c este corect definit i injectiv. Surjectivitatea lui fiind imediat deducem c este bijecie.

    Cum ((xH)(yH)) = ((xy)H) = f(xy) = f(x)f(y) = (xH)(yH) pentru orice xH, yHG/H deducem c este i morfism de grupuri, adic este izomorfism de grupuri.

    Corolar 2.2. Dac G, G sunt grupuri iar fHom(G, G) un morfism surjectiv de grupuri, atunci G/Ker(f)G.

    Corolar 2.3. Fie G un grup, H, K subgrupuri ale lui G a. K G. Atunci HK G, HK H iar HK / K H / HK.

    n plus, dac i H G, atunci HK G (unde reamintim c HK={hk / hH i kK}). Demonstraie. Cum KG, xK=Kx pentru orice xG i prin urmare HK= U

    HxKx

    = U

    HxxK

    =KH

    . Dac x, yHK, x=h1k1 i y=h2k2 cum h1, h2H i k1, k2K atunci scriind:

    xy-1=(h1k1)(h2k2)-1=(h1k1)(h2-1k2-1)=[h1(k1k2-1)h1-1](h1h2-1) deducem c xy-1KH=HK (cci din H, KG i KG deducem pe rnd c h1,h2-1K, h1(k1k2-1)h1-1K ]i h1h2-1H), adic[ HKG.

    n mod evident KHK i s considerm :HHK/K, (x)=xK pentru orice xH (evident este corect definit deoarece pentru xH avem xHK i xKHK/K), care este morfism de grupuri.

    Deoarece orice element din HK/K este de forma (xy)K=x(yK)=xK=(x) (cu xH i yK) deducem c este morfism surjectiv de grupuri. n plus, Ker ={xH / (x)=1}={xH / xK=K}={xH / xK}=HK. Deducem c H/Ker HK/K H/HKHK/K. Dac i HG, atunci pentru orice xG avem x(HK)=(xH)K=(Hx)K=H(xK)=H(Kx)=(HK)x, adic HKG. 3.Grupuri de permutri. Teorema lui Cayley.

    Grupurile Sn i An.

    Fie M o mulime nevid iar (M)={fHom(M) | f este bijectiv}. Dup cum am vzut n 1 al acestui capitol (Hom(M),) este monoid iar (M) apare acum ca grupul unitilor monoidului Hom(M). Convenim s numim grupul (M) ca fiind grupul permutrilor asupra elementelor mulimii M. Dac M este o mulime cu n elemente (exemplul clasic fiind M={1,2,,n} cu n1), atunci grupul (M) se noteaz prin Sn i se va numi grupul permutrilor asupra unei mulimi cu n elemente sau grup simetric de grad n. (vom vedea mai departe c pentru grupul Sn natura elementelor mulimii M joac un rol secundar, numrul elementelor lui M fiind lucrul important). Astfel, un element al lui Sn se va prezenta de multe ori sub forma unui tabel

    ( ) ( )

    n

    n ...1

    ...1 .

  • 32

    32

    Vom nota prin en sau simplu prin e (dac nu este pericol de confuzie) permutarea identic din Sn.

    Avem c | Sn | = n!. Teorema 3.1.(Cayley) Orice grup G este izomorf cu un subgrup al grupului de permutri

    (G). Demonstraie. Pentru xG se probeaz imediat c x:G(G), x(y)=xy pentru orice yG

    este un element din (G). S artm acum c :G(G) , (x)=x pentru orice xG este un morfism injectiv de grupuri. Dac x, yG i (x)=(y), atunci x=y deci n particular x(1)=y(1) x1=y1 x=y, de unde deducem c este ca funcie o injecie.

    De asemenea, (x) (y) = x y iar dac zG avem (x y)(z) = x (y(z)) = x(yz) = (xy)z = xy(z), adic x y = xy = =(xy), deci (x) (y) = (xy), adic Hom (G, (G)). Deducem c G (G) (G).

    n continuare ne vom ocupa de studiul grupului Sn cu n2. Evident, grupul S2 avnd 2

    elemente este comutativ pe cnd ncepnd cu n3, Sn nu mai este comutativ. Definiia 3.2. Numim ciclu de lungime k (2kn) o permutare Sn pentru care exist

    elementele distincte i1,i2,,ik din {1,2,,n} a.. (i1)=i2, (i2)= i3, , (ik)=i1 iar (i)=i pentru orice i{1,2,,n} \ {i1,i2, , ik}. Convenim s notm un astfel de ciclu prin = (i1 i2 ik) sau = (i1,i2, , ik) (dac exist pericol de confuzie). Ciclii de lungime 2 se mai numesc i transpoziii. De exemplu, n S5

    (1 3 5)=

    1 4 5 2 3

    5 4 3 2 1 iar (2 4)=

    5 2 3 4 1

    5 4 3 2 1.

    Dac = (i1 i2 ik) este un ciclu de lungime k, convenim s numim mulimea {i1,i2, , ik} ca

    fiind orbita lui . Dac = (j1 j2 jt) este un alt ciclu de lungime t din Sn , vom spune c i sunt ciclii disjunci dac {i1, i2, , ik}{j1, j2, , jt}=. Propoziia 3.3. Dac , sunt ciclii disjunci din Sn, atunci =. Demonstraie. Dac i {1, 2, , n} \ ({i1, i2, , ik} {j1,j2, , jt}), atunci ()(i) = =()(i) =i. S presupunem c i{i1, i2, , ik}, s zicem de exemplu c i=i1. Atunci ()(i)=((i))=(i)=(i1)=i2, iar ()(i)=((i))=(i2)=i2 de unde concluzia c ()(i)=()(i). Analog se arat c ()(i)=()(i) dac i{j1, j2, , jt}, de unde deducem egalitatea = . n esen am folosit faptul c dac i{i1, i2, , ik} atunci (i)=i iar dac j{j1, j2, , jt}, atunci (j)=j. Observaia 3.4. Deoarece pentru orice 2kn avem (i1 i2 ik) = (i2 i3 ik i1) = =

    (ik i1 ik-1) deducem c n Sn exist knAk

    1 ciclii distinci de lungime k.

    Propoziia 3.5. Ordinul oricrui ciclu de lungime k (2kn) este k . Dac , sunt 2 ciclii disjunci de lungimi k i respectiv t (2k, tn), atunci o()=[k,t]. n particular, dac (k,t)=1, atunci o(t)=o()o(). Demonstraie. Trebuie n prima parte s demonstrm c k(i)=i pentru orice i{1,2, ,n}, unde =(i1, i2, , ik) este un ciclu de lungime k. Dac i {1,2 , , n} \ {i1 , i2 , , ik}, atunci n mod evident k(i)=i. Dac i{i1 , i2 , , ik}, de exemplu i = i1, atunci 2(i) = ((i)) = ((i1)) = (i2) = i3, deci k-1(i) = ik i iar k(i)=i i

  • 33

    33

    analog pentru orice i{i1 , i2 , , ik}, ii1 , de unde concluzia c k=e iar k este cel mai mic numr natural cu aceast proprietate, adic o()=k. Fie = (i1 i2 ik) , =(j1 j2 jt) ciclii disjunci de lungime k i respectiv t (2k, tn), = = , s=[k,t] iar r=o(). Va trebui s demonstrm c r=s. Deoarece k,t | s deducem c s=e, adic r|s. Cum r= e deducem c rr=e adic r=-r . Dac am avea re, atunci exist i{i1, i2, ,ik} a.. r(i)i. Cum r = -r deducem c i r(i)i, adic i{j1, j2, , jt} absurd ! . n concluzie r= r=e, de unde deducem k|r i t|r. Cum s=[k,t] deducem c s|r, adic s=r. Corolar 3.6. Dac 1, k sunt ciclii disjunci doi cte doi din Sn de lungimi t1, ,tk , atunci o(1 k)=[t1, ,tk]. Teorema 3.7.. Orice permutare Sn, e se descompune n mod unic n produs de ciclii disjunci (exceptnd ordinea n care acetia sunt scrii) . Demonstraie. Fie t=|{ i{1,2,,n} | (i)i }| ; cum e deducem c exist i{1,2.,,n} a. . (i)i i astfel i ((i))(i), de unde concluzia c t2. Vom face acum inducie matematic dup t. Dac t=2 totul este clar cci n acest caz se reduce la o transpoziie. S presupunem acum teorema adevrat pentru toate permutrile ce schimb efectiv mai putin de t indici i s artm c dac este o permutare ce schimb efectiv t indici atunci se descompune n produs de ciclii disjunci. Alegem i0{1,2,,n} pentru care (i0)i0 i fie q=o(). Alegnd i1=(i0), i2=(i1), ,ik+1=(ik), se vede c ik=k(i0) pentru orice k1. Cum q= e deducem c q(i0)=i0, deci iq=i0. Putem alege atunci cel mai mic numar natural m cu proprietatea c im=i0. Atunci numerele i0,i1,,im-1 sunt distincte ntre ele. ntr-adevr, dac ir=is cu 0r, ss, notnd p=r-s obinem p(i0)=i0 i deci ip=i0 contrazicnd alegerea lui m (cci p

  • 34

    34

    Propoziia 3.11. Dac ,Sn, atunci sgn()=sgn()sgn().

    Demonstraie. Avem

  • 35

    35

    CURSUL nr. 9 1.Inel. Exemple. Reguli de calcul ntr-un inel. Divizori ai lui zero. Domenii de integritate. Caracteristica unui inel

    Definiia 1.1. O mulime nevid A, mpreun cu dou operaii algebrice notate

    tradiional prin + i se zice inel dac: (i) (A,+) este grup comutativ (ii (A,) este semigrup

    (iii) nmulirea este distributiv la stnga i la dreapta fa de adunare, adic pentru oricare x, y, z A avem: x(y+z)=xy+xz i (x+y)z=xz+yz. n cele ce urmeaz (dac nu este pericol de confuzie) cnd vom vorbi despre un inel A vom pune n eviden doar mulimea A (operaiile de adunare i nmulire subnelegndu-se). Astfel, prin 0 vom nota elementul neutru al operaiei de adunare iar pentru aA, prin a vom desemna opusul lui a. Dac operaia de nmulire de pe A are element neutru (pe care l vom nota prin 1) vom spune despre inelul A c este unitar. Dac A este un inel unitar i 0=1 vom spune despre A c este inelul nul; n caz contrar vom spune c A este inel nenul. Dac nmulirea de pe A este comutativ, vom spune despre inelul A c este comutativ. Convenim s notm A*=A\{0}. Exemple. 1. Din cele stabilite n 6 de la Capitolul 2 deducem c (,+,) este inel comutativ unitar. 2. Dac vom considera A=2={2n : n} atunci (A,+,) este exemplu de inel comutativ neunitar (cci 12). 3. Dac n, n2 atunci (n, +, ) este exemplu de inel unitar comutativ finit cu n elemente (vezi 6 de la Capitolul 2).

    4. Fie A un inel i m, n*. Un tablou de forma

    =

    mnm

    n

    ............

    ...

    1

    111

    cu m limii i n coloane, format din elemente ale lui A se zice matrice cu m linii i n coloane; convenim s notm o astfel de matrice i sub form mai condensat ( )

    njmiij

    =

    11 .

    Dac m=n notm Mm,n(A)=Mn(A); o matrice din Mn(A) se zice ptratic de ordin n. Pentru , Mm,n(A), =(ij)

    njmi

    11 i =(ij)

    njmi

    11 definim:

    +=(ij+ij) njmi

    11 .

    Asociativitatea adunrii matricelor este imediat, elementul neutru este matricea Om,n din Mm,n(A) ce are toate elementele egale cu 0, iar opusa matricei este matricea - =(-ij)

    njmi

    11 , de unde

    concluzia c (Mm,n(A), +) este grup (abelian). Pentru m, n, p* , Mm,n(A), Mn,p(A), =(ij)

    njmi

    11 , =(jk)

    pknj

    11 definim =(ik)

    pkmi

    11 ,

    unde ik= =

    n

    j 1ijjk pentru 1im i 1kp.

    n mod evident, Mm,p(A).

  • 36

    36

    S demonstrm c dac m, n, p, q* i Mm,n(A), Mn,p(A), Mp,q(A), atunci ()=(). ntr-adevr, fie =(ik)

    pkmi

    11 , cu ik=

    =

    n

    j 1ijjk i () =(it)

    qtmi

    11 cu it=

    =

    p

    k 1ikkt

    = =

    p

    k 1(

    =

    n

    j 1ijjk) kt =

    =

    p

    k 1

    =

    n

    j 1ij jk kt.

    Dac =(jt)qtnj

    11 cu jt=

    =

    p

    k 1jkkt iar ()=(it)

    qtmi

    11 , atunci it=

    =

    n

    j 1ijjt

    = =

    n

    j 1ij

    =

    p

    k 1jkkt =

    =

    n

    j 1

    =

    p

    k 1ijjkkt, de unde egalitatea ()=().

    innd cont de distributivitatea nmulirii de pe A fa de adunare, deducem imediat c dac Mm,n(A) i ,Mn,p(A) atunci (+)=+ iar dac , Mm,n(A) i Mn,p(A) atunci (+)=+. Sumnd cele de mai sus, deducem c dac n, n2, atunci (Mn(A),+,) este un inel (numit inelul matricelor ptratice de ordin n cu elemente din A). Dac inelul A este unitar, atunci i inelul (Mn(A),+,) este unitar, elementul neutru fiind matricea In ce are pe diagonala principal 1 i n rest 0. S remarcm faptul c n general, chiar dac A este comutativ, Mn(A) nu este comutativ.

    Observaia 1.2. Dac A este inel unitar, rezult c adunarea de pe A este comutativ.

    ntr-adevr, calculnd pentru a, bA, (a+b)(1+1) n dou moduri (innd cont de distributivitatea la stnga i la dreapta a nmulirii fa de adunare) obinem egalitatea a + a + b + b =a + b + a + +b, de unde a+b=b+a. 2. Notarea generic cu litera A a unui inel oarecare se explic prin aceea c n limba francez noiunea matematic corespunztoare se traduce prin anneaux. n anumite cri un inel oarecare se noteaz prin R (de la faptul c n limba englez noiunea matematic de inel se traduce prin ring).

    Propoziia 1.3. Dac A este un inel, atunci: (i) a0=0a=0, pentru orice aA (ii) a(-b)=(-a)b= -(ab) i (-a)(-b) = ab, pentru orice a, bA

    (iii) a(b-c)= ab-ac i (a-b)c= ac-bc, pentru orice a, b, cA (iv) a(b1++bn)=ab1++abn i (a1++an)b=a1b++anb, pentru orice a, b, ai, biA, 1 i n (v) Dac a, b A, n* i ab=ba avem egalitile: an- bn = (a-b)(an-1 + an-2b ++ abn-2 + bn-1) a2n+1+b2n+1 = (a+b)(a2n a2n-1b +- ab2n-1 + b2n). Demonstraie. (i). Totul rezult din 0+0=0. (ii). Totul rezult din (i) i din aceea c b+(-b)=0. (iii). Rezult din (ii).

    (iv). Se face inducie matematic dup n. (v). Se fac calculele n membrul drept.

    Observaia 1.4. Definind pentru aA i n

    43421

    orin

    aa ++ ... dac 0>n

    na = 0 dac 0=n

    44 344 21orin

    aa

    ++ )(...)( dac 0

  • 37

    37

    (vii). Dac A este un inel unitar, a, bA, ab=ba i n* , avem egalitatea

    =

    =+n

    k

    kknkn

    n baCba0

    )( (prin definiie a0=1).

    Egalitatea de la (vi) rezult din (iv) iar (vii) se demonstreaz prin inducie matematic dup n innd cont de faptul c 11

    1 ++

    + =+ knkn

    kn CCC pentru orice n* i 0 k n.

    Definiia 1.6. Prin unitile U(A) ale inelului unitar A nelegem unitile monoidului (A, ), adic U(A)={aA : exist bA a.. ab=ba=1}.

    n mod evident, (U(A), ) este grup. De exemplu, U()={1} iar dac A este inel unitar i n, n2, atunci U(Mn(A))={MMn(A)| det(M)0}. Grupul (U(Mn(A),) se noteaz prin GLn(A) i se numete grupul liniar general de grad n peste A.

    Definiia 1.7. Un element aA se zice divizor al lui zero la stnga (dreapta) dac exist bA* a.. ab=0 (ba=0).

    Exemple 1. Dac A=M2(), atunci din

    =

    10

    10

    00

    11

    O2 deducem

    c

    00

    11

    este divizor al lui zero la stnga iar

    10

    10

    este divizor al lui zero la dreapta.

    Dac n, n 2 nu este un numr prim iar n=n1n2 cu n1, n2 diferii de 1 i n, atunci n inelul (n, +, ) avem egalitatea 0 21 == nnn , adic 1n i 2n sunt divizori ai lui zero. 2. n orice inel A, elementul 0 este divizor al lui zero la stnga i la dreaptaA.

    Propoziia 1.8. Fie A un inel i a, b, cA. (i) Dac A este unitar i aU(A), atunci a nu este divizor al lui zero ( nici la dreapta nici

    la stnga) (ii) Dac a nu este divizor al lui zero la stnga (dreapta) i ab=ac (ba=ca), atunci b=c. Demonstraie. (i). Dac aU(A), atunci exist bA a.. ab=ba=1. Dac a ar fi divizor al lui

    zero, de exemplu la stnga, atunci exist cA* a.. ac=0. Deducem imediat c b(ac)=b0=0 (ba)c=0 1c=0 c=0 - absurd. Analog dac a este divizor al lui zero la dreapta.

    (ii). Din ab=ac deducem c a(b-c)=0 i cum am presupus c a nu este divizor al lui zero la stnga, cu necesitate b-c=0, adic b=c.

    Definiia 1.10. Numim domeniu de integritate (sau inel integru), un inel comutativ, nenul i fr divizori ai lui zero, diferii de zero. Inelul ntregilor (, +,) este un exemplu de inel integru . Definiia 1.11. Un element aA se zice nilpotent dac exist n* a.. an = 0. Vom nota prin N(A) mulimea elementelor nilpotente din inelul A (evident 0N(A)).

    De exemplu, n inelul A=M2() dac alegem M=

    01

    00

    cum

    M2=O2, deducem c MN(M2()). De asemenea, cum n inelul 8 avem 0823 == deducem c 2 N(8). n mod evident, dac aN(A), atunci a este divizor al lui zero la dreapta i la stnga.

  • 38

    38

    S presupunem c A este un inel unitar nenul. Dac elementul 1 are ordinul infint n grupul (A,+) vom spune c A este un inel de caracteristic 0 (vom scrie car(A)=0). n mod evident, a spune c car(A)=0 revine la aceea c n10 pentru orice n*. Dac ordinul lui 1 n grupul (A,+) este p vom spune c inelul A are caracteristic p i vom scrie car(A)=p (acest lucru revine la a spune c p este cel mai mic numr natural nenul cu proprietatea c p1=0). De exemplu, inelul ntregilor este un inel de caracteristic 0, pe cnd 3 este un inel de caracteristic 3.

    Observaia 1.12. Dac inelul A este domeniu de integritate de caracteristic p, atunci p este un numr prim. ntr-adevr, dac p nu ar fi prim, atunci putem scrie p=p1p2 cu p1, p2 numere naturale mai mici dect p i diferite de 1 i p. Cum p1=0 iar (p1p2)1=(p11)(p21) obinem c (p11)(p21)=0 i cum A este domeniu de integritate deducem c p11=0 sau p21=0, contrazicnd minimalitatea lui p cu proprietatea c p1=0. 2. Subinele i ideale Definiia 2.1. Dac (A,+,) este un inel, vom spune c o submulime nevid A a lui A este subinel al lui A dac restriciile operaiilor de adunare i nmulire