Algebra Pt Informatica

download Algebra Pt Informatica

of 45

description

Curs algebra info anul 1

Transcript of Algebra Pt Informatica

  • ALGEBRA PENTRU INFORMATICA

    GEORGE CIPRIAN MODOI

    Cuprins

    Bibliografie 21. Multimi, Functii, Relatii 31.1. Preliminarii logice 3Exercitii la Preliminarii logice 31.2. Multimi 3Operatii cu multimi 4Exercitii la Multimi 61.3. Functii 6Injectivitate, surjectivitate, bijectivitate 8Cardinalul unei multimi 9Produsul cartezian 9Operatii 10Exercitii la functii 111.4. Relatii 13Relatii de echivalenta 15Relatii de ordine 16Exercitii la Relatii 182. Grupuri, inele, corpuri 202.1. Grupuri 20Subgrupuri 21Homomorfisme de grupuri 22Grupuri ciclice si ordinul unui element 23Actiuni ale grupurilor pe multimi 23Grupul simetric 24Exercitii la grupuri 252.2. Inele si corpuri 28Subinele si subcorpuri 29Homomorfisme 30Elemente speciale ntr-un inel 31Exercitii la inele si corpuri 323. Algebra liniara 333.1. Spatii vectoriale si aplicatii liniare 34Subspatii vectoriale 35Suma si suma directa a subspatiilor 36Aplicatii liniare 37Exercitii la spatii vectoriale 383.2. Baza unui spatiu vectorial 39Independenta liniara 39

    1

  • 2 GEORGE CIPRIAN MODOI

    Baze si coordonate 40Dimensiune unui spatiu vectorial 42Proprietatea de universalitate a bazei unui spatiu vectorial 42Formule legate de dimensiune 43Lema substitutiei 43Exercitii la Baze 44

    Bibliografie

    [1] M. Artin, Algebra, Prentice Hall, 1991.

    [2] N. Both, S. Crivei, Culegere de probleme de algebra, Lito UBB, 1996.[3] S. Breaz, T. Coconet, C. Contiu, Lectii de Algebra, Editura Eikon, Cluj, 2010.

    [4] P. M. Cohn, Elements of Linear Algebra, Springer Verlag, N.Y.-Berlin-Heidelberg, 1994.

    [5] I. D. Ion, N. Radu, Algbera, Editura Did. Ped. Bucuresti, 1970.[6] I. D. Ion, N. Radu, C. Nita, D. Popescu, Probleme de algebra, Ed. Did. Ped., Bucuresti, 1970.

    [7] B. Kulshammer, Lineare Algebra und Analytische Geometrie, Vorlesungsskripte,

    https://www.minet.uni-jena.de//algebra//skripten/skripten.html.[8] C. Nastasescu, C. Nita, C. Vraciu, Bazele algebrei, Ed. Academiei, 1986.

    [9] C. Nastasescu, C. Nita, M. Brandiburu, D. Joita, Exercitii si probleme de algebra, Ed. Did.

    Ped. Bucuresti, 1983.[10] I. Purdea, I. Pop, Algebra, Ed. Gill, Zalau, 2007.

    [11] C. Pelea, I. Purdea, Probleme de algebra, Editura EFES, Cluj, 2005.

    [12] G. Pic, I. Purdea, Tratat de algebra moderna, Editura Academiei, Bucuresti, 1977.[13] A. E. Schroth, Algebra fur die Studierende der Informatik, Vorlesungsskripte,

    http://www.carsten-buschmann.de/skripte/Algera fuer Informatiker.pdf.

  • ALGEBRA PENTRU INFORMATICA 3

    1. Multimi, Functii, Relatii

    1.1. Preliminarii logice. Propozitiile logice sunt numai acele propozitii care pot fiadevarate sau false; celelalte propozitii gramaticale precum ntrebarile, exclamatiileetc., care nu pot fi adevarate sau false, nu sunt incluse printre propozitiile logice.Propozitiile sunt conectate de operatori, dintre care noi vom folosi urmatorii:

    Negare si logic sau logic (neexclusiv) sau exclusiv implicatia logica echivalenta logica

    Acestri operatori sunt definiti prin urmatoarele tabele de avedar: (aici p si q suntpropozitii, iar 0 si 1 nseamna fals, respectiv adevarat):

    p q p p q p q p q p q p q0 0 1 0 0 0 1 10 1 1 0 1 1 1 01 0 0 0 1 1 0 01 1 0 1 1 0 1 1

    Exercitii la Preliminarii logice.

    Exercitiu 1.1.1. Sa se arate ca urmatoarele formule propozitionale sunt tau-tologii, adica ele sunt ntotdeauna adevarate, indiferent de valoarea de adevar apropozitiilor p, q r:

    (a) ((p q) r) (p (q r))(b) ((p q) r) (p (q r))(c) (p q) (q p)(d) (p q) (q p)(e) (p (q r)) ((p q) (p r))(f) (p (q r)) ((p q) (p r))(g) (p (p q)) p(h) (p (p q)) p(i) (p q) ((q r) (p r))(j) p p(k) (p q) (q p).1.2. Multimi. Multimea este o colectie de obiecte distincte si bine determinate(care obiecte sunt numite elemente). Multimile pot fi date n mod direct prinenumerarea explicita a elementelor lor (altfel spus sintetic) sau prin precizarea uneiconditii (proprietati) pe care trebuie sa o ndeplineasca (adica analitic). Vom scriex A (si vom spune ca x apartine multimii A) pentru a exprima faptul ca x esteun element al multimii A. De notat ca notiunile multime si apartenenta suntprimare, adica ele nu se definesc.

    Exemplu 1.2.1. a)A = {1, 2, 3}, B = {a, b, c, d}, C = {?, 7, ,}, N = {0, 1, 2, 3, . . .}.b) Z = {x | x N si 0 x < 10}, [3, 8) = {x | x R si 3 x < 8}.c) Alte exemple ...

    Definitie 1.2.2. Doua multimi sunt egale exact atunci cand ele contin aceleasielemente.

  • 4 GEORGE CIPRIAN MODOI

    Exemplu 1.2.3. {1, 2, 3} = {x N | 1 x 3} = {x Z | 0 < x < 4},N = {x Z | x 0}.

    Observatie 1.2.4. a) Elementele unei multimi nu sunt ordonate n nici un fel:{1, 2} = {2, 1} sau {a, b, c} = {b, c, a} = {a, c, b} = {b, a, c} = {c, a, b} = {c, b, a}.

    b) Intr-o multime un element apare numai o data: {1, 2} si NU {1, 2, 2, 1}.c) Definirea analitica a unei multimi necesita precautii suplimentare. De exam-

    plu constructia: R = {x | x / x} conduce la un paradox. Mai precis, amandouapropozitiile R R si R / R conduc la o contradictie (paradoxul lui das Rus-sell). Aici x / A este negatia propozitiei x A. Nu ne vom ocupa prea multde problemem de acest tip, si vom evita paradoxurile lucrand local, anume,cand consideram o proprietate P (Predicat) definim A = {x U | P (x)} si nuA = {x | P (x)}, sie U este o multime suficient de cuprinzatoare (Universul discur-sului).

    Exemplu 1.2.5. Multimi de numere:Numere naturale: N = {0, 1, 2, 3, . . .}, N = {1, 2, 3 . . .}.Numere ntregi: Z = {. . . ,2,1, 0, 1, 2, . . .}.Numere rationale: Q = {mn | n,m Z, n 6= 0}.Numere reale: R (R =?).Numere complexe: C = {a+ ib | a, b R} sie i2 = 1.

    Definitie 1.2.6. Consideram doua multimiA siB . Spunem caA este o submultimea lui B, daca x A implica x B. Scriem A B.

    Definitie 1.2.7. Multimea vida notata cu este multimea care nu contine nici unelement.

    Propozitie 1.2.8. Urmatoarele afirmatii sunt valabile pentru orice multimi A, Bsi C:

    (a) A A (reflexivitate).(b) Daca A B si B C atunci A C (tranzitivitate).(c) A=B ddaca A B si B A (antisimetrie).(d) A.(e) Multimea vida este unic determinata.

    Demonstratie.

    Operatii cu multimi.

    Definitie 1.2.9. Fie A si B mulimi. Se defineste:

    (a) Reuniunea dintre A si B prin A B = {x | x A x B}.(b) Intersectia dintre A si B prin A B = {x | x A x B}.(c) Diferenta dintre A si B prin A \B = {x | x A x / B}.In cazul A U se numeste complementara lui A n U multimea CUA = U \A.

    Observatie 1.2.10. Multimile pot fi reprezentate prin asa numitele diagrameEuler-Venn. De exemplu:

  • ALGEBRA PENTRU INFORMATICA 5

    A

    B

    A B

    U

    Teorema 1.2.11. Fie A, B, C, U multimi, asa ncat A,B,C U .(a) (A B) C = A (B C) si (A B) C = A (B C) (asociativitate).(b) A B = B A si A B = B A (comutativitate).(c) A (B C) = (A B) (A C) si A (B C) = (A B) (A C) (dubla

    distributivitate).(d) A A = A = A A (idempotenta).(e) A (A B) = A = A (A B) (absorbtie).(f) CU (A B) = CUA CUB si CU (A B) = CUA CUB (regulile lui de

    Morgan).

    Demonstratie.

    Definitie 1.2.12. Fie A o multime. Multimea putere a multimii A este multimeatuturor submultimilor lui A, adica:

    P(A) = {X | X A}.Observatie 1.2.13. Definitia multimii tuturor submultimior necesita precautiisuplimentare: care univers trebuie folosit? De notat: paradoxul lui Cantor esteconstruit cu ajutorul multimii tuturor submultimilor.

    Definitie 1.2.14. Pentru doua multimi A si B, se defineste produsul cartezian cafiind:

    AB = {(a, b) | a A si b B}.Aici (a, b) este o pereche (ceea ce nseamna o multime ordonata), care din perspec-tiva teoriei multimilor poate fi definita prin

    (a, b) = {a, {a, b}}.

  • 6 GEORGE CIPRIAN MODOI

    Observatie 1.2.15. Inductiv se poate defini produsul cartezian a unui numar finitde multimi:

    A1 A2 . . . An1 An = (A1 A2 . . . An1)An.Pentru o multime A avem A1 = A si An = An1 A, pentru orice n > 1.Exercitii la Multimi.

    Exercitiu 1.2.16. Sa se determine A B, A B, A \B, CN(A), AB, undeA = {n N | 3n+ 5

    n+ 1 N} si B = {x Z | x este par si 2 x < 3}.

    Exercitiu 1.2.17. Sa se determine P(), P({}), P({, {}}).1.3. Functii.

    Definitie 1.3.1. O functie (sau aplicatie) este un triplet (A,B, f) care este formatdin doua multimi A si B si o lege de corespondenta f , asa ncat fiecarui elementdin A i corespunde un singur element din B. Multimile A si B se numesc domeniulde definitie (sau simplu domeniul), respectiv domeniul de valori (sau codomeniul)

    functiei. Se scrie f : A B sau A f B. Pentru a A se noteazaa f(a) uniculelement din B care i corespunde lui a prin f (numit si imaginea lui a prin f). Senoteaza cu BA multimea tuturor functiilor de la A la B, adica

    BA = {f : A B | f este o functie}.Observatie 1.3.2. Doua func tii f : A B si f : A B sunt egale ddacaA = A, B = B si f(x) = f(x) pentru orice x A.Observatie 1.3.3. Functiile pot fi definite n mai multe moduri:

    (a) Prin indicarea directa a imaginii fiecarui element din domeniu, de exempluf : {1, 2, 3} {a, b, c, d}, f(1) = f(2) = a si f(3) = b. Variante (pentruaceeasi functie): Printr-un tabel:

    x 1 2 3f(x) a a b

    sau printr-o diagrama:

    1

    2

    3

    a

    b

    c

    (b) Printr-o formula de calcul a imaginii fiecarui element, de exemplu f : N N,f(x) = x+ 1 pentru orice x N. Intrebare: Orice formula conduce la o functiebine definita?

    Exemplu 1.3.4. (a) Pentru orice multime A se defineste functia identitate prin1A : A A, 1A(x) = x pentru orice x A. Se noteaza uneoriidA = 1A.

    (b) Daca A si B sunt multimi, asa ncat A B, se defineste functia incluziuneprin i = iA,B : A B, i(x) = x, pentru orice x A. De notat ca iA,B = 1A ddacaA = B, altfel iA,B 6= 1A.

  • ALGEBRA PENTRU INFORMATICA 7

    (c) Daca A, B, C sunt multimi, asa ncat C A si f : A B este o functie seconstruieste functia restrictie a lui f la C, prin f |C : C B, f |C(x) = f(x) pentruorice x C.

    (d) Urmatoarele corespondente nu sunt functii:

    1

    2

    3

    a

    b

    c

    1

    2

    3

    a

    b

    c

    4

    Definitie 1.3.5. Fie f : A B o functie si fie X A, Y B doua submultimi(a lui A respectiv B). Se defineste:

    (a) Imaginea lui X prin f , ca fiind

    f(X) = {f(x) | x X} = {y B | x X astfel ncat f(x) = y}.In cazul X = A vom vorbi despre imaginea functiei f , si anume f(A) = Imf .

    (b) Contraimaginea (imaginea inversa) lui Y prin f , ca fiind

    f1(Y ) = {x A | f(x) Y }.Definitie 1.3.6. Daca f : A B si g : B C sunt functii, atunci compunerealor este definita astfel: g f : A C, (g f)(x) = g(f(x)) pentru orice x A.Teorema 1.3.7. Atunci cand este definita compunerea functiilor este asociativa,

    adica pentru Af B g C h D avem (h g) f = h (g f). Functia identitate

    actioneaza ca element neutru pentru compunerea functiilor, adica pentru Af B

    avem f = f 1A = 1B f .Demonstratie.

    Definitie 1.3.8. O functie f : A B se numeste inversabila daca exista o altafunctie f : B A astfel ncat f f = 1A si f f = 1B .Propozitie 1.3.9. Daca f : A B este inversabila, atunci exista o singura functief : B A cu proprietatea f f = 1A si f f = 1B. Notam cu f1 aceastafunctie si o numim inversa functiei f . De asemenea avem (f1)1 = f .

    Demonstratie.

    Exemplu 1.3.10. exp : R (0,), exp(x) = ex este inversabila si are inversaln : (0,) R. A se observa legatura dintre inversabilitatea funtiilor si solutia(eventual unica) a ecuatiilor!

    Propozitie 1.3.11. Daca Af B g C sunt doa functii inversabile, atunci tot asa

    este si g f ; mai mult avem (g f)1 = f1 g1.Demonstratie.

  • 8 GEORGE CIPRIAN MODOI

    Injectivitate, surjectivitate, bijectivitate.

    Definitie 1.3.12. O functie f : A B se numeste:(a) injectiva daca pentru x1, x2 A, x1 6= x2 implica f(x1) 6= f(x2).(b) surjectiva daca pentru orice y B exista x A asa ncat f(x) = y.(c) bijectiva daca f atat injectiva cat si surjectiva.

    Observatie 1.3.13. In mod echivalent o functie f : A B este(a) injectiva daca x1, x2 A, f(x1) = f(x2) implica x1 = x2.(b) surjectiva daca f(A) = B.

    Observatie 1.3.14. O functie f : A B este injectiva, surjectiva sau bijecktivaddaca pentru orice y B ecuatia f(x) = y are cel mult, cel putin, respectiv exacto solutie x A.

    Propozitie 1.3.15. Urmatoarele propozitii sunt adevarate pentru doua functii Af

    Bg C:

    (a) Daca f si g sunt injective, atunci asa este si g f .(b) Daca f si g sunt surjective, atunci asa este si g f .(c) Daca f si g sunt bijective, atunci asa este si g f .(d) Daca g f este injectiva, atunci asa este si f .(e) Daca g f este surjectiva, atunci asa este si g.(f) Daca g f este bijectiva, atunci f este injectiva si g este surjectiva.Demonstratie.

    Propozitie 1.3.16. Fie f : A B o functie cu A 6= . Urmatoarele afirmatiisunt echivalente:

    (i) f ist injectiva.(ii) f are o inversa la stanga, adica exista g : B A, astfel ncat g f = 1A.

    (iii) f este simplificabila la stanga, adica daca h1, h2 : A A sunt functii atunci

    f h1 = f h2 implica h1 = h2.Demonstratie.

    Propozitie 1.3.17. Fie g : B A o functie. Urmatoarele afirmatii sunt echiva-lente:

    (i) g ist surjectiva.(ii) g are o inversa la dreapta, adica exista f : A B astfel ncat g f = 1A.

    (iii) g este simplificabila la dreapta, adica daca k1, k2 : A A sunt functii atunci

    k1 g = k2 g implica k1 = k2.Demonstratie.

    Teorema 1.3.18. Fie f : A B o functie. Urmatoarele afirmatii sunt echivalente:(i) f este bijectiva.(ii) f este inversabila.

    (iii) f este inversabila la stanga si inversabila la dreapta.

    Demonstratie.

  • ALGEBRA PENTRU INFORMATICA 9

    Cardinalul unei multimi.

    Definitie 1.3.19. Spunem ca doua multimi A si B au acelasi cardinal daca existao bijectie f : A B. O multime A este finita daca A = sau exista n N asancat A si {1, 2, . . . , n} au acelasi cardinal. In ultimul caz, numarul natural n esteunic determinat, deoarece nu exista o bijectie {1, 2 . . . , n} {1, 2, . . . ,m} pentrun 6= m; spunem ca A are cardinalul n, si scriem |A| = n sau ]A = n. Multimeavida nu are elemente, deci cardinalul ei este zero; scriem || = 0.Observatie 1.3.20. Pentru multimile finite cardinalul este simplu numarul deelemente. Dar cardinalul se defineste si pentru multimile infinite, asadar exista omasura cu ajutorul careia putem compara marimea acestor multimi.

    Propozitie 1.3.21. Fie A o multime finita. Urmatoarele afirmatii sunt echivalentepentru o functie f : A A:

    (i) f ist injectiva.(ii) f ist surjectiva.(iii) f ist bijctiva.

    Demonstratie.

    Observatie 1.3.22. O multime infinita A poate fi caracterizata prin proprietateaca exista o functie injectiva (sau surjectiva) f : A A care nu este bijectiva.Definitie 1.3.23. Pentru o submultime X a unei multimi A se defineste functiacaracteristica X : A {0, 1} a lui X (n rapurt cu A) prin

    X(x) =

    {1 daca x X0 daca x / X

    Lema 1.3.24. Pentru orice multime A functia : P(A) {0, 1}A, (X) = Xeste bijectiva.

    Demonstratie.

    Corolar 1.3.25. Pentru orice multime A avem |P(A)| = |{0, 1}A| si multimile Asi P(A) nu au acelasi cardinal.Demonstratie.

    Produsul cartezian.

    Propozitie 1.3.26. Consideram multimile A1, A2, . . . , An, unde n N. Sa searate ca

    : A1 A2 . . .An (A1 A2 . . . An){1,2,...,n} unde(a1, a2, . . . , an)(i) = ai, pentru orice i I

    este o functie injectiva, a carei imagine este:

    Im = {f (A1 A2 . . . An){1,2,...,n} | f(i) Ai pentru orice i I}.Asadar induce o bijectie

    A1 A2 . . .An Im, (a1, a2, . . . , an) 7 (a1, a2, . . . , an).Demonstratie.

  • 10 GEORGE CIPRIAN MODOI

    Propozitia anterioara ne ofera posibilitatea de a extinde definitia produsuluicartezian din cazul familiilor finite de multimi (a se vedea Observatia 1.2.15) pentruo familie oarecare (posibil infinita).

    Definitie 1.3.27. Se considera familia de multimi Ai cu i I. Prin definitieprodusul cartezian a acestei familii este:

    iIAi =

    {f : I

    iI

    Ai | f(i) Ai pentru orice i I}.

    Observatie 1.3.28. (1) Daca n definitia anterioara avem Ai = A pentru oricei I gilt, atunci:

    AI =iI

    Ai = {f : I A | f este o functie}

    ( a se compara cu notatia BA din definitia 1.3.1).(2) Existenta produsului cartezian necesita o axioma speciala a teoriei multimilor,

    si anume Axioma Alegerii. Desi intuitiv este clar, din punct de vedere formal nueste posibil ca n lipsa acestei axiome sa construim o functie f : I iI Ai asancat f(i) Ai pentru orice i I (adica sa alegem elementele f(i) Ai, i I).Operatii.

    Definitie 1.3.29. Fie A o multime. O operatie (binara) pe A este o func tie : AA A. Adesea se scrie a b n loc de (a, b).Definitie 1.3.30. O operattie : AA A pe A se numeste:(a) asociativa daca a (b c) = (a b) c pentru orice a, b, c A.(b) comutativa daca a b = b a pentru orice a, b A.Un element e A cu proprietatea e a = a e = a pentru orice a A se numesteelement neutru pentru . Daca operatia are un element neutru e, atunci unelement x A se numete inversabil daca exsita x A asa ncat x x = e = x x.Propozitie 1.3.31. Daca o operatie : AA A are un element neutru, atunciel este unic.

    Demonstratie.

    Propozitie 1.3.32. Se considera o operatie asociativa : AA A care are unelement neutru e.

    (a) Daca x A este inversabil, atunci elementul x A cu proprietatea xx = e =x x este unic. El se noteaza cu x1 si se numeste inversul (sau simetricul)lui x. Mai mult, avem (x1)1 = x.

    (b) Daca x, y A sunt inversabile, atunci xy este de asemenea inversabil si avem(xy)1 = y1x1.

    Demonstratie.

    Definitie 1.3.33. Un monoid este o pereche (structura) (M, ) care consista dintr-omultime M mpreuna cu o operatie asociativa : MM M , care are un elementneutru. Pentru doi monoizi (M, ) si (N8) se numeste homomorfism de monoizi ofunctie f : M N cu proprietatea f(x y) = f(x) f(y) pentru orice x, y M .

  • ALGEBRA PENTRU INFORMATICA 11

    Exemplu 1.3.34. (1). Urmatoarele perechi sunt monoizi: (N,+), (Z,+), (N, ),(Z, ), (Q,+), (Q, ), (R,+), (R, ), (C,+), (C, ).

    (2) Daca (M, ) si (N, ) sunt monoizi, atunci 1M : M M si e : M N ,e(x) = e pentru orice x M sunt homomorfisme de monoizi.Exercitii la functii.

    Exercitiu 1.3.35. Se considera functiile:

    (1) f1 : R R, f1(x) = x2(2) f2 : [0,) R, f2(x) = x2(3) f3 : R [0,), f3(x) = x2(4) f4 : [0,) [0,), f4(x) = x2.Sa se studieze pentru fircare dintre ele injectivitatea, surjectivitatea si bijectivitatea.In cazul existentei inversei sa se determine aceasta.

    Exercitiu 1.3.36. Acelasi exercitiu ca si 1.3.35 pentru funtiile:

    (1) f : R R, f(x) ={

    2x+ 1 daca x 1x+ 2 daca 1 < x

    (2) f : R R, f(x) ={

    x2 + 1 daca x 0x+ 2 daca 0 < x

    (3) f : R R, f(x) ={

    2x+ 1 daca x 0x+ 2 daca 0 < x

    Exercitiu 1.3.37. Sa se precizeze dau a urmatoarele compuneri f g si g f suntdefinite, si n caz afirmativ sa se determine functia compusa:

    (1) f, g : R R f(x) ={x2 1 daca x 1x 1 daca 1 < x si g(x) =

    { x+ 1 daca x < 3x 2 daca 3 x

    (2) f : R [0,), f(x) = |x| si g : N R, g(x) = 1/x.(3) f : R [0,), f(x) = x2 + 1 si g : [0,) R, g(x) = x.Exercitiu 1.3.38. Fie A, B, C trei multimi asa ncat C A si fie f : A B ofunctie. Sa se arate ca f |C : f i, unde i : A C este functia de incluziune.Exercitiu 1.3.39. Fie f : A B o functie inversabila si fie Y B. Atunci prinf1(Y ) putem ntelege fie contraimaginea lui Y prin f sau imaginea Y prin f1.Sa se arate ca cele dua interpretari nu intra n conflict (conduc la aceeasi multime.

    Exercitiu 1.3.40. Sa se gaseasca un exemplu de doua functii f, g : N N asancat g f 6= f g. (Desi compunerea este definita bilateral, ea nu este comutativa).Exercitiu 1.3.41. Sa se arate ca orice functie f : A B poate fi scrisa ca ocompunere f = i p unde i = if este injectiva iar p = pf este surjectiva.Exercitiu 1.3.42. Sa se gaseasca un exemplu care consta dintr-o functie f : AB, asa ncat:

    (1) f este injectiva dar nu are o inversa la stanga.(2) f are exact o inversa la stanga, dar nu este bijectiva.(3) f are exact doua inverse la stanga.(4) f are o infinitate de inverse la stanga.

    Exercitiu 1.3.43. Sa se gaseasca un exemplu care consta dintr-o functie g : B A, asa ncat:

    (1) g are exact doua inverse la dreapta.

  • 12 GEORGE CIPRIAN MODOI

    (2) g are o infinitate de inverse la dreapta.

    Sa se arate ca g are exact o inversa la dreapta ddaca g este bijectiva.

    Exercitiu 1.3.44. Sa se gaseasca un exemplu care consta din doua functii Af

    Bg C, asa ncat:

    (1) g f este injectiva, dar g nu este injectiva.(2) g f este surjectiva, dar f nu este surjectiva.(3) g f este bijectiva, dar g nu este injectiva si f nu este surjectiva.Exercitiu 1.3.45. Fie f : A B o functie, si fie X,X1, X2 A si Y, Y1, Y2 Bsubmultimi. Sa se arate:

    (1) X f1(f(X)).(2) f(X1 X2) = f(X1) f(X2).(3) f(X1 X2) f(X1) f(X2).(4) f(f1(Y ) Y .(5) f1(Y1 Y2) = f1(Y1) f1(Y2).(6) f1(Y1 Y2) = f1(Y1) f1(Y2).Exercitiu 1.3.46. Urmatoarele afirmatii sunt echivalente, pentru o functie f :A B:

    (i) f este injectiva.(ii) X = f1(f(X)) pentru orice submultime X A.

    (iii) f(X1 X2) = f(X1) f(X2) pentru orice doua submultimi X1, X2 A.Sa se gaseasca un exemplu care sa arate ca injectivitatea lui f este necesara pentruamandoua egalitatile (2) si (3).

    Exercitiu 1.3.47. Urmatoarele afirmatii sunt echivalente, pentru o functie f :A B:

    (i) f ist surjectiva.(ii) f(f1(Y ) = Y pentru orice submultime Y B.

    Sa se gaseasca un exemplu care sa arate ca surjectivitatea lui f este necesara pentruegalitatea (2).

    Exercitiu 1.3.48. Fie A si B doua multimi finite cu |A| = n si |B| = m. Sa sedetermine |BA|. Indicatie: Se arata prin inductie dupa n ca |BA| = mn.Exercitiu 1.3.49. Fie A si B multimi finite cu |A| = n si |B| = m. Sa se determinenumarul tuturor functiilor injective de la A la B. Indicatie: Numarul cautat esteAnm =

    m!(mn)! .

    Exercitiu 1.3.50. Fie A o multime finita cu |A| = n. Sa se determine numarultuturor functiilor bijective f : A A (adica numarul tuturor permutarilor lui A).Exercitiu 1.3.51. Fie B o multime finita cu |B| = m. Sa se determine numarultuturor submultimilor lui B cu n elemente. Indicatie: Numarul cautat este

    (mn

    )=

    m!n!(mn)! .

    Exercitiu 1.3.52. Sa se arate cani=0

    (mi

    )= 2m.

  • ALGEBRA PENTRU INFORMATICA 13

    Exercitiu 1.3.53. (Principiul includerii si al excluderii) FieA1, A2, . . . , An multimifinite, unde n N. Atunci:|A1 A2 . . . An| =

    1in

    |Ai|

    1i

  • 14 GEORGE CIPRIAN MODOI

    Exemplu 1.4.3. Uratoarele exemple sunt relatii care nu sunt func tii:

    (1) Relatia uzuala mai mic sau egal este o relatie omogena pe N, Z, Q sau R.(2) Divizibilitatea a|b ddaca exista c asa ncat b = ac este o relatie omogena pe N

    sau Z.(3) Fie n N, n > 1. Congruenta modulo n este o relatie omogena pe Z. Ream-

    intim: Congruenta modulo n este definita prin x y( mod n) ddaca n|(xy).(4) Pentru orice multime A apartenenta este o relatie ntre A si P(A).Exemplu 1.4.4. Pentru orice multime A, egalitatea este o relatie omogena pe A.Se observa ca aceasta relatie este si o funtie, mai precis functia identitate a lui A.

    Observatie 1.4.5. Ca si n cazul functiilor, exista mai multe moduri n care poatefi data o relatie:

    (1) Prin indicarea directa a perechilor care sunt n relatie, de ex. daca A ={0, 1, 2, 3, 4}, B = {a, b, c, d} siR = {(0, a), (0, b), (1, a), (1, b), (1, c), (2, d), (3, d), (4, c)},atunci (A,B,R) este o relatie. Diagramele vin si aici n ajutor:

    0

    1

    2

    3

    4

    a

    b

    c

    d

    (2) Printr-o matrice cu intrari n multimea {0, 1}: Se considera doua multimi finiteA = {a1, a2, . . . , am} si B = {b1, b2, . . . , bn} si o relatie R A B. Aceastarelatie poate fi reprezentata printr-o matrice M(R) = (mi,j) Mmn({0, 1}),unde

    mi,j =

    {1 daca (ai, bj) R0 daca (ai, bj) / R

    De exemplu matrice relatiei anterioare este:1 1 0 01 1 1 00 0 0 10 0 0 10 0 1 0

    Aici prin Mmn({0, 1}) se noteaza multimea tuturor matricilor (adica tabeledreptunghice) cu m linii si n coloane si cu intrari din {0, 1}.

    (3) Printr-o proprietate pe care trebuie sa o satisfaca toate elementele care se aflan relatie, ca n Exemplul 1.4.3 (2), (3).

    Definitie 1.4.6. Pentru orice relatie (A,B,R) se defineste relatia inversa ca fiind(B,A,R1), unde (b, a) R1 ddaca (a, b) R pentru orice pereche (a, b) AB.Observatie 1.4.7. Relatia inversa se poate defini pentru orice relatie, n particularpentru orice functie privita ca relatie. Dar relatia inversa a unei functii este exactatunci o functie cand functia de la care pornim este bijectiva.

  • ALGEBRA PENTRU INFORMATICA 15

    Definitie 1.4.8. Fie r = (A,B,R) o relatie si X A, Y B submultimi. Sedefinesc: r(X) = {y B | exista x A asa ncat xry} si r1(Y ) = {x A |exista y B asa ncat xry}.Observatie 1.4.9. Pentru o relatie r = (A,B,R) si o submultime Y B avem(r1)(Y ) = r1(Y ).

    Definitie 1.4.10. Fie (A,B,R) si (C,D, S) doua relatii. Compunerea celor douarelatii este definita prin: (A,D, S R) unde

    S R = {(a, d) | exista x B C asa ncat (a, x) B si (x, d) S}.Observatie 1.4.11. Spre deosebire de cazul functiilor, compunerea este definitaoricand fara a fi necesara coincidenta dintre codomeniul primei relatii cu domeniulcelei de-a doua.

    Definitie 1.4.12. O relatie omogena r = (A,A,R) se numeste:

    (a) reflexiva daca ara pentru orice a A.(b) tranzitiva daca pentru orice a, b, c A din arb si brc rezulta arc.(c) simetrica daca pentru orice a, b A din arb rezulta bra.(d) antisimetrica daca pentru orice a, b A din arb si bra rezulta a = b.Se numeste preordine o relatie omogena care este reflexiva si tranzitiva.

    Relatii de echivalenta.

    Definitie 1.4.13. FieA o multime. O relatie de echivalenta (sau pe scurt echivalenta)pe A este o preordine care este de asemene simetrica, adica o relatie omogena pe Acare este reflexiva, tranztiva si simetrica.

    Exemplu 1.4.14. Urmatoarele relatii sunt echivalente:

    (1) Relatia de egalitate pe o multime arbitrara.(2) Congruenta triunghiurilor (pe multimea tuturor triunghiurilor din plan).(3) Asemanarea triunghiurilor (pe multimea tuturor triunghiurilor din plan).

    Definitie 1.4.15. Fie o relatie de echivalenta pe o multime A. Pentru un elementa A se noteaza

    [a] = [a] = {x A | a x}clasa de echivalenta a lui a. Se numeste multimea factor a lui A modulo multimeatuturoe claselor de echivaleta, adica

    A/ = {[a] | a A}.Funtia p = p : A A/ data prin p(x) = [x] se numete proiectia canonica atasatarelatiei de echivalenta .Observatie 1.4.16. In definitia formala a multimii factor este posibil, si chiarfoarte probabil, ca anumite elemente sa apara de mai multe ori. Noi stim cantr-o multime un element apare o singura data, si presupunem automat ca seeleimina repetitiile. Totusi aceasta presupunere necesita precautii suplimentare,caci o folosire gresita poate conduce la functii care nu sunt bine definite si, prinurmare, la contradictii.

    Propozitie 1.4.17. Fie (A,A,) o relatie de echivalenta pe omultime A, si a, b A. Avem:

    (a) a [a], asadar [a] 6= .

  • 16 GEORGE CIPRIAN MODOI

    (b) [a] = [b] ddaca a b.(c) [a] [b] 6= ddaca [a] = [b].(d)

    xA[x] = A.

    Demonstratie. Definitie 1.4.18. Fie A o multime. O partitie a multimii A este o submultime pi P(A) a multimii putere a lui A (adica o multime a carei elemente sunt submultimiale lui A), asa ncat:

    (a) / pi.(b) Pentru X,Y pi daca X Y 6= atunci X = Y .(c)

    XpiX = A.

    Teorema 1.4.19. Fie A o multime.

    (1) Daca (A,A,) este o relatie de echivalenta pe A, atunci A/ este o partitie amultimii A.

    (2) Daca pi P(A) este o partitie a lui A, atunci (A,A,pi) este o relatie deechivalenta, unde pentru orice a, b A avem

    a pi b ddaca exista X pi asa ncat a, b X.(3) Procedeele de la (1) si (2) descriu doua functii inverse una celeilalte ntre

    Multimea tuturor echivalentelor pe A si multimea tuturor partitiilor pe A.

    Demonstratie. Relatii de ordine.

    Definitie 1.4.20. Fie A o multime. O relatie de ordine (sau pe scurt ordine) pe Aeste o preordine care este si antisimetrica, adica o relatie omogena pe A care estereflexiva, tranzitiva si antisimetrica.

    Adesea se noteaza o relatie de ordine cu si se spune ca (A,) este o multimeordonata. In acest caz notam x < y relatia x y si x 6= y.Exemplu 1.4.21. Urmatoarele relatii sunt de ordine:

    (1) Relatia de egalitate pe o multime arbitara.(2) Relata obisnuita de mai mic sau egal pe N, Z, Q sau R.(3) Incluziunea pe o multime a caror elemente sunt multimi, de exemplu (P(A),

    ) este o multime ordonata, unde A este o multime oarecare.

    De notat ca n (R,) avem x y sau y x pentru orice x, y R (aceasta nseamna(R,) este un lant sau sir). In general acest lucru nu este adevarat pentru o multimeordonata oarecare, de exemplu (P(A),) nu este un lant cand A are cel putin douaelemente, pentru ca exista X,Y P(A) astfel ncat X * Y si Y * X.Definitie 1.4.22. Fie (A,) o multime ordonata. Un element a A se numeste:(a) minimal daca pentru orice x A din x a rezulta x = a.(b) maximal daca pentru orice x A din a x rezulta x = a.(c) cel mai mic element a lui A daca a x pentru orice x A.(d) cel mai mare element a lui A daca x a pentru orice x A.Observatie 1.4.23. Fie (A,) o multime ordonata. Se noteaza =1, adicax y ddaca y x. Este usor de a verifica ca este de asemenea o relatie deordine (vezi Exercitiu 1.4.48). Se poate observa ca a A este minimal sau cel

  • ALGEBRA PENTRU INFORMATICA 17

    mai mic element n (A,) ddaca a este maximal, respectiv cel mai mare elementn (A,) si invers. Aceasta observatie se poate extinde pentru toate notiunile siafirmatiile referitoare la multimi ordonate si este asa numitul principiu al dualitatii.

    Lema 1.4.24. Fie (A,) o multime ordonata. Daca A are un cel mai mic (mare)element, atunci acest element este unicul element minimal (respectiv maximal).

    Corolar 1.4.25. Cel mai mic (mare) element al unei multimi ordonate, daca ex-ista, este unic.

    Demonstratie. Teorema 1.4.26. Urmatoarele afirmatii sunt echivalente pentru o multime ordo-nata (A,):

    (i) Orice submultime nevida a lui A are un element minimal (conditia mini-malitatii).

    (ii) Orice lant descrescator de elemente din A este finit, adica daca a0 a1 a2ldots cu a0, a1, a2, . . . A, atunci exista n N asa ncat an = an+1 = . . .(conditia lanturilor descrescatoare).

    (iii) Daca B A are proprietatile(a) B contine toate elementele minimale ale lui A;(b) pentru a A daca {x A | x < a} B atunci a B;

    atunci B = A (conditia inductivitatii).

    Demonstratie. Definitie 1.4.27. Fie (A,) o multime ordonata si X A. O margine inferioara(superioara) pentru X este un element a A asa ncat, a x (respectiv x a)pentru orice x X. Se numeste infimum (supremum) a lui X n A cea mai mare(mica) margine inferioara (respectiv superioara) a lui X, adica

    inf X A ddaca{a x pentru orice x Xdaca a A asa ncat a x pentru orice x X atunci a a.

    supX = a A ddaca{x a pentru orice x Xdaca a A asa ncat x a pentru orice x X atunci a a.

    Observatie 1.4.28. Fie (A,) o multime ordonata si X A.(1) Daca exista inf X si supX sunt unice.(2) Daca exista cel mai mic (mare) element a a lui X atunci a = inf X (a =

    supX).

    Exemplu 1.4.29. (1) In (R,) avem inf(0, 1) = inf[0, 1] = 1, sup{x R |x2 < 2} = 2, nu exista inf Z si nu exsita sup(0,).

    (2) In (Q,) nu exista sup{x Q | x2 < 2}.(3) Intr-o multime ordonata (A,) exista inf (sup ) exact atunci cand A

    are cel mai mare (respectiv mic) element a, si avem inf = a = supA(sup = a = inf A).

    Definitie 1.4.30. O latice este o multime ordonata (L,) cu proprietatea ca exsitainf{x, y} si sup{x, y} pentru orice doua elemente x, y L. Notam xy = sup{x, y}si xy = inf{x, y}. Laticea L se zice completa daca exista inf(X) si sup(X) pentruorice submultime X L.

  • 18 GEORGE CIPRIAN MODOI

    Teorema 1.4.31. Intr-o latice (L,) sunt valabile proprietatile:(a) x (y z) = (x y) z si x (y z) = (x y) z (asociativitate).(b) x y = y x si x y = y x (comutativitate).(c) x (x y) = x = x (x y) (absorbtie).

    Invers, daca L este o multime mpreuna cu doua operatii , : L L L asancat sunt valabile proprietatile (a), (b), (c) de mai sus, atunci L este o multimeordonata n raport cu relatia x y ddaca x y = x; mai mult (L,) este chiar olatice n care inf{x, y} = x y si sup{x, y} = x y, pentru orice x, y L.Demonstratie.

    Propozitie 1.4.32. O multime ordonata (L,) este o latice completa ddaca exsitainf X pentru orice X L.Demonstratie.

    Exercitii la Relatii.

    Exercitiu 1.4.33. Fie f : A B si g : B C doua functii. Sa se arate ca functiacompusa g f este acelasi lucru ca si relatia compusa g f .Exercitiu 1.4.34. Fie r = (A,B,R) o relatie si notam cu A si B relatiile deegalitate pe A respectiv B.

    (1) Sa se arate ca rA = r = B r, adica relatia de egalitate actioneaza ca elemetneutru pentru compunerea relatiilor.

    (2) Sa se arate ca relatia inversa r1 = (B,A,R1) nu este n mod necesar inversar aport cu compunerea relatiilor, adica sa se construiasca un exemplu de relatiar asa ncat r1 r 6= A.

    Exercitiu 1.4.35. Fie r = (A,B,R) si s = (B,C, S) doua relatii, unde A, B si Csunt multimi finite cu |A| = m, |B| = n si |C| = p. Se ordoneaza elementele dinA, B si C si se considera matricile M(r) Mmn({0, 1}) si M(s) Mnp({0, 1}).Sa se determine M(r1) si M(s r) n functie de M(r) si M(s). Sa se scrie unalgoritm care citeste M(r) si M(s) si calculeaza M(r1), M(s r).Exercitiu 1.4.36. Sa se arate ca divizibilitatea pe Z este o preordine care nu estenici simetrica si nici antisimetrica.

    Exercitiu 1.4.37. Sa se determine toate relatiile de echivalenta care se pot definipe A = {a, b, c}.Exercitiu 1.4.38. Sa se arate ca urmatoarele relatii sunt echivalente si sa se cal-culeze respectivele multimi factor:

    (1) (C,C,) data prin x y ddaca |x| = |y|.(2) (C,C,) data prin x y ddaca arg(x) = arg(y).

    Exercitiu 1.4.39. Sa se arate ca relatia data prin

    (a, b) (c, d) ddaca ad = cbeste o echivalenta pe Z Z si sa se determine multimea factor

    (Z Z)/.

  • ALGEBRA PENTRU INFORMATICA 19

    Exercitiu 1.4.40. Sunt bine definite urmatoarele functii

    f : Q Q, f(ab

    )=a+ 1

    b2pentru orice a, b Z, b 6= 0,

    g : Q Q, g(ab

    )=

    2a+ 3b

    bpentru orice a, b Z, b 6= 0,

    h : Z Z, h(x) = x2

    pentru orice x Z,

    k : Z Q, k(x) = 1x

    pentru orice x Z?Exercitiu 1.4.41. Consideram multimea Q = (Z Z)/ ca n Exercitiul 1.4.39.Sa se arate ca +, : QQ Q sunt bine definite, unde:

    a

    b+c

    d=ad+ bc

    bdsia

    b cd

    =ac

    bd

    pentru orice a, b, c, d Z, b 6= 0, d 6= 0.Exercitiu 1.4.42. Fie n N, n 2. Sa se arata ca:

    (1) Congruenta modulo n, si anume (Z,Z,n) data de x n y (sau x y(mod n)) ddaca n|(x y) este o relatie de echivalenta.

    (2) Multimea factor corespunzatoare este multimea tuturor claselor de resturimodulo n: Zn = Z/n = {[0]n, [1]n, . . . , [n 1]n}.

    (3) Operatiile urmatoare sunt bine definite:

    + : Zn Zn Zn unde [x]n + [y]n = [x+ y]n pentru orice x, y Z si : Zn Zn Zn unde [x]n[y]n = [xy]n pentru orice x, y Z.

    Exercitiu 1.4.43. Fie A o multime si r = (A,A,R) o preordine pe A. Sa se arateca r r1 unde x(r r1)y ddaca xry si yrx este o relatie de echivalenta pe Asi pe multimea factor A/(rr1) relatia r induce o ordine: [x] r [y] ddaca xry.Sa se studieze cazul particular cand A = Z si preordinea este divizibilitatea (veziExercitiu 1.4.36).

    Exercitiu 1.4.44. Fie f : A B o funtie. Nucleul funtiei f este o relatie omogenape A notata cu ker f si definita prin a(ker f)b ddaca f(a) = f(b). Sa se arate caker f este o relatie de echivalenta pe A. Invers, pentru orice relatie de echivalenta(A,A,) sa se gasesca o functie f : A B, astfel ncat este nucleul lui f .Exercitiu 1.4.45. Sa se gaseasca numarul tuturor relatiilor de echivalenta care sepot defini pe o multime A cu n elemente.

    Exercitiu 1.4.46. Sa se determine toate relatiile de ordine care se pot defini peA = {a, b, c}. In fiecare caz sa se precizeze elemente;e minimale, maximale, cel maimic si/sau cel mai mare element.

    Exercitiu 1.4.47. Sa se construiasca un exemplu de multime ordonata cu unsingur element minimal, dar care nu are un cel mai mic element.

    Exercitiu 1.4.48. Daca (A,) este o multime ordonata, atunci tot asa este si(A,).Exercitiu 1.4.49. Orice latice finita este completa.

    Exercitiu 1.4.50. Orice lant este o latice. Este orice lant o latice completa?

  • 20 GEORGE CIPRIAN MODOI

    Exercitiu 1.4.51. Orice latice completa are cel mai mic si un cel mai mare element.

    Exercitiu 1.4.52. (N, |) este o latice (aici cu | se noteaza divizibilitatea). Este(N, |) completa?Exercitiu 1.4.53. Aratati ca (N,) este o latice care nu este completa. Explicatide ce acest exemplu nu contrazice Propozitia 1.4.32.

    Exercitiu 1.4.54. (P(A),) este o latice completa pentru orice multime A.Exercitiu 1.4.55. Pe multimea L a tuturor propozitiilor logice se defineste relatiap q ddaca p q este o tautologie. Sa se arate ca este o preordine. Sa sedetermine relatia de echivalenta asociata = ( 1) (vezi Exercitiul 1.4.35)si multimea factor L/ (aceasta multime este numita algebra Lindenbaum-Tarski).Sa se arate ca L/ este o latice completa.

    2. Grupuri, inele, corpuri

    2.1. Grupuri.

    Definitie 2.1.1. Un grup este o pereche (G, ) care consta dintr-o multime Gmpreuna cu o operatie : GG G, astfel ncat este asociativa, are un elementneutru si fiecare element din G este inversabil n raport cu . In cazul n care estesi comutativa atunci G se numeste abelian sau comutativ.

    Exemplu 2.1.2. Urmatoarele perechi sunt grupuri (abeliene):

    (a) (Z,+), (Q,+), (R,+), (C,+).(b) (Q, ), (R, ), (C, ).(c) (Mmn(Z),+), (Mmn(Q),+), (Mmn(R),+), (Mmn(C),+)

    Exemplu 2.1.3. Urmatoarele perechi sunt monoizi dar nu grupuri:

    (a) (N,+), (N, ).(b) (Z, ), (Q, ), (R, ), (C, ).(c) (Mnn(Z), ), (Mnn(Q), ), (Mnn(R), ), (Mnn(C), )Observatie 2.1.4. Cel mai adesea operatia unui grup oarecare este notata multi-plicativ, adica (G, ). In acest caz elementul neutru este notat 1 si pentru x Gnotam cu x1 elementul invers. Pentru un grup abelian nsa operatia este adeseanotata aditiv, adica (G,+). In acest caz, elementul neutru se noteaza 0, iar pentrux G notam x elementul opus.Propozitie 2.1.5. Fie (M, ) un monoid si consideram

    M = {x M | x este inversabil n M}= {x M | x1 M astfel ncat xx1 = 1 = x1x}.

    Sa se arate ca operatia induce pe M, iar M mpreuna cu operatia indusaformeaza un grup.

    Demonstratie.

    Corolar 2.1.6. Urmatoarele constructii conduc la grupuri neabeliene:

    (1) Daca A este o multime, atunci S(A) = { : A A | este bijectiva}este un grup mpreuna cu compunerea functiilor; acest grup nu este abelianpentru |A| 3. Grupul S(A) se numeste grupul simetric al multimii A.

  • ALGEBRA PENTRU INFORMATICA 21

    (2) Fie K {Q,R,C} si n N. Multimea GLn(K) = {A Mnn(K) |det(A) 6= 0} mpreuna cu nmultirea matricilor formeaza un grup, care nueste comutativ pentru n 2. Grupul GLn(K) se numeste grupul lineargeneral de rang n peste K.

    Demonstratie.

    Subgrupuri.

    Definitie 2.1.7. Fie (G, ) un grup. Un subgrup a lui G este o submultime H G,astfel ncat operatia pe G induce o oprttie bine definita pe H (i. e. x, y H xy H; se spune de asemenea ca H este o parte stabila a lui G), si H mpreuna cuoprtati a indusa fofrmeaza un grup. Se scrie H G.Exemplu 2.1.8. (1) Z Q R C (cu adunarea).

    (2) Q R C (cu nmultirea).(3) R+ R, unde R+ = (0,).(4) Orice grup G are asa numitele subgrupuri triviale i. e. {1} si G.

    Propozitie 2.1.9 (Teorema de caracterizare a subgrupurilor). Fie (G, ) un grupsi fie H G o submultime. Urmatoarele afirmatii sunt echivalente:

    (i) H G.(ii) (a) 1 H.

    (b) x, y H xy H.(c) x H x1 H.

    (iii) (a) 1 H.(b) x, y H xy1 H.

    Demonstratie.

    Propozitie 2.1.10. Fie (G, ) un grup. Daca Hi G, cu i I, atunciiI Hi

    G.

    Demonstratie.

    Observatie 2.1.11. Reuniunea a doua sau mai multe subgrupuri nu este cu nece-sitate subgrup (Ubung 2.1.58).

    Definitie 2.1.12. Fie (G, ) un grup si X G o submultime a lui G. Subgrupulgenerat de X este definit prin

    X ={H G | X H}.

    Daca X = {x1, x2, . . . , xn} este o multime finita atunci scriem x1, x2, , xn n locde {x1, x2, , xn}.Lema 2.1.13. Fie (G, ) un grup si X G o submultime a lui G. Atunci:(a) X G.(b) X X si X = X ddaca X G.(c) X este cel mai mic subgrup a lui G care contine submultimea X, adica

    H = X ddaca

    H GX Hdaca K G astfel ncat X K atunci H K

    .

  • 22 GEORGE CIPRIAN MODOI

    (d) Gilt X Y G so gilt auch X Y G.Demonstratie.

    Propozitie 2.1.14. Fie (G, ) un grup si X G o submultime a lui G. Atunci:X = {x1x2 . . . xn | n N, x1, x2, . . . , xn X X1},

    unde X1 = {x1 | x X}. Aceasta nseamna ca grupul generat de X continetoate elementele erzedin G care se pot scrie ca un produs finit de elemente dinX X1.Demonstratie.

    Observatie 2.1.15. Fie (G, ) un grup si x G. Pentru orice n Z se defineste:

    xn =

    xx . . . x (n ori) daca n > 0

    1 daca n = 0

    x1x1 . . . x1 (n ori) daca n < 0Daca operatia este scrisa aditiv, adica (G,+) atunci scriem

    nx =

    x+ x+ . . .+ x (n ori) daca n > 0

    0 daca n = 0

    (x) + (x) + . . .+ (x) (n ori) daca n < 0Corolar 2.1.16. Fie (G, ) un grup.(a) Pentru x G avem x = {xn | n Z}.(b) Pentru x, y G cu xy = yx avem x, y = {xnym | n,m Z}.Homomorfisme de grupuri.

    Definitie 2.1.17. Fie (G, ) si (H, ) doua grupuri. Se numeste homomorfism (degrupuri) ntre G si H o functie f : G H cu proprietatea f(xy) = f(x)f(y)pentru orice x, y G. Se numeste izomorfism (de grupuri) un homomorfism careeste bijectiv. In acest caz grupurile se zic izomorfe si notam G = H.Exemplu 2.1.18. Pentru orice doua grupuri G si H functiile 1G si e : G H,e(x) = 1 sunt un izomorfism respectv un homomorfism de grupuri. Daca G Hatunci functia de incluziune i : G H este un homomorfism.Lema 2.1.19. Daca f : G H este un homomorfism de grupuri atunci:(a) f(1) = 1.(b) f(x1) = f(x)1.

    Demonstratie.

    Lema 2.1.20. Compunerea a doua homomorfisme este de asemenea un homomor-fism. Functia inversa a unui izomorfism de grupuri este de asemenea un izomor-fism.

    Demonstratie.

    Definitie 2.1.21. Fie f : G H un homomorfism. Numim nucleul respectivimaginea lui f multimile

    Kerf = {x G | f(x) = 1} si Imf = {f(x) | x G}.

  • ALGEBRA PENTRU INFORMATICA 23

    Propozitie 2.1.22. Daca f : G H este un homomorfism, atunci:(a) Kerf G.(b) Imf H.(c) f este injectiv ddaca Kerf = {1}.(d) f este surjectiv ddaca Imf = H.

    Demonstratie. Grupuri ciclice si ordinul unui element.

    Definitie 2.1.23. Un grup ciclic este un grup care este generat de un singur elemental sau.

    Definitie 2.1.24. Fie (G, ) un grup si x G. Se spune ca x este de ordin finitdaca exista n N astfel ncat xn = 1. In acest caz se numeste ordinul lui x cel maimic numar natural n N cu aceasta proprietate; scriem n = ord(x). Elementul xeste de ordin infinit daca el nu este de ordin finit, caz n care scriem ord(x) =.Exemplu 2.1.25. (1) In orice grup (G, ) exista un singur elemet de ordin 1,

    anume elementul neutru ord(1) = 1.

    (2) In (Z,+) avem ord(2) = ord(3) = si chiar ord(x) = pentru oricex 6= 0.

    (3) In (R, ) avem ord(1) = 2 si ord(2) = ord(2) = ord(3) =; mai mult,ord(x) = pentru orice x R \ {1,1}.

    (4) In (C, ) avem ord(i) = ord(i) = 4, ord (cos 2pi3 + i sin 2pi3 ) = 3, ord(2) =ord(2) =; mai mult ord(x) = pentru orice x C cu |x| 6= 1.

    Propozitie 2.1.26. Fie (G, ) un grup, x G si n N. Avem:

    ord(x) = n ddaca

    {xn = 1

    daca m Z are proprietatea xm = 1 atunci n|m .

    Demonstratie. Propozitie 2.1.27. Fie (G, ) un grup. Pentru orice x G avem ord(x) = |x|.Demonstratie. Actiuni ale grupurilor pe multimi.

    Definitie 2.1.28. Fie A o multime si (G, ) un grup. Se numeste actiune (la stanga)a lui G pe A o functie : GA A cu proprietatile:

    (1) (g, (h, x)) = (gh, x) pentru orice g, h G si orice x A.(2) (1, x) = x pentru orice x A.

    Observatie 2.1.29. Adesea functia : G A A este vazuta ca o operatie(nmultire) externa, n sensul ca operanzii nu sunt luati din aceeassi multime, si

    este notata prin gx = (g, x). In acest caz, egalitatile (1) si (2) din definitia 2.1.28devin:

    g(hx) = (gh)x, respectiv 1x = x, pentru orice g, h G si orice x A.Teorema 2.1.30. Fie A o multime si (G, ) un grup.(a) Daca GA A, (g, x) 7 gx este o actiune a lui G pe A, atunci : G S(A),

    (g) : A A, (g) : x 7 gx este un homomorfism de grupuri.

  • 24 GEORGE CIPRIAN MODOI

    (b) Daca : G S(A) este un homomorfism de grupuri, atunci G A A,(g, x) 7 (g)(x) este o actiune a lui G pe A.

    (c) Procedeele de la (a) si (b) descriu func ctii mutual inverese ntre multimeatuturor actiunilor lui G pe A si multimea tuturor homomorfismeleor de grupuriG S(A).

    Demonstratie. Definitie 2.1.31. Fie G A A, (g, x) 7 gx o actiune a grupului (G, ) pemultimea A. Se numeste reprezentare prin permutari a acestei actiuni homomorfis-mul de grupuri : G S(A) concstruit n Teorema 2.1.30. Actiunea se zice fidela,daca reprezentarea ei prin permutari este un homomorfism injectiv.

    Propozitie 2.1.32. Fie G A A, (g, x) 7 gx o actiune a grupului (G, ) pemultimea A. Relatia (A,A,) data prin x y ddaca exista g G astfel ncat gx =y, pentru orice x, y A este o relatie de echivalenta, a carei clase de echivalenta(numite orbite) se determina ca fiind Gx = {gx | g G}, mit x A.Demonstratie. Corolar 2.1.33. Notam cu [A/] un sistem de reprezentanti pentru multimea tu-turor orbitelor unei actiuni G A A a grupului (G, ) pe multimea A. Atuncieste valabila egalitatea:

    |A| =

    Gx[A/]|Gx|.

    Demonstratie. Corolar 2.1.34. (Teorema lui Lagrange) Fie G un grup finit.

    (a) Daca H este un subgrup al lui G atunci |H| divide |G|.(b) Daca x G atunci ord(x) divide |G|.Demonstratie. Definitie 2.1.35. Ordinul unui grup (G, ) este cardinalul |G|.Grupul simetric.

    Definitie 2.1.36. Fie n un numar natural si G un subgrup al grupului simetricSn = S({1, 2, . . . , n}). Actiunea lui G pe {1, 2, . . . , n} a carei reprezentare prinpermutari este functia de incluziune i : G Sn este numita actiunea canonica.Pentru Sn se numesc -orbite orbitele actinii canonica a grupului G = .O -orbita se zice triviala daca ea contine un singur element. Un ciclu este opermutare care are o singura orbita netriviala. In acest caz, cardinalul acesteiorbite (netriviale) este numita lungimea ciclului. Doa cicluri se zic disjuncte ncazul n care orbitelel lor netriviale sunt disjuncte (ca multimi).

    Observatie 2.1.37. Fie Sn.(1) = e (e este permutatarea identica) ddaca toate -orbitele sunt triviale;

    Altfel spus e este un ciclu de lungime 1.(2) este un ciclu de lungime 1 < k n ddaca exsita o submultime {i1, i2, . . . , ik} {1, 2, . . . , n}, astfel ncat (i1) = i2, (i2) = i3, . . . , (in) = i1 si (i) = ipentru i / {i1, i2, . . . , ik}. In acest caz {i1, i2, . . . , ik} este singura orbitanetriviala a lui si notam = (i1i2, . . . , ik).

  • ALGEBRA PENTRU INFORMATICA 25

    Lema 2.1.38. Pentru Sn si i {1, 2, . . . , n} exista un cel mai mic numarnatural k 1, astfel ncat k(i) = i. Acest numar k este lungimea orbitelor i siavem:

    i = {i, (i), . . . , k1(i)}.Demonstratie.

    Lema 2.1.39. Daca 1 si 2 sunt cicluri disjuncte, atunci 12 = 21.

    Demonstratie.

    Teorema 2.1.40. Orice permutare se scrie ca un produs de cicluri netriviale sidoua cate doua disjuncte. Mai mult, aceasta descompunere este unica (abstractiefacand e ordinea factorilor).

    Demonstratie.

    Observatie 2.1.41. Se numeste decompunerea lui ca produs de cicluri duoa catedoua disjuncte data n Teorema 2.1.40. Uneori aceasta descompunere contine deasemenea si cicluri triviale (i) = e, unde i {1, 2, . . . , n} cu proprietatea (i) = i,incluzand cazul = e din Teorema precedenta.

    Definitie 2.1.42. O inversiune pentru Sn este o pereche (i, j) {1, 2, . . . , n}2,astfel ncat i < j si (i) > (j). e noteaza cu m() numarul de inversiuni si sedefineste semnul lui prin () = (1)m(). Permutarea se zice (im)para n cazuln care m() este (im)par.

    Teorema 2.1.43. (Cayley) Orice grup este izomorf cu un subgrup al unui grup depermutari.

    Demonstratie.

    Exercitii la grupuri.

    Exercitiu 2.1.44. Se considera multimea

    Z+ iZ = {a+ ib | a, b Z} C (aici i2 = 1).Sa se arate ca Z+ iZ este un monoid n raport cu nmultirea numerelor complexe.Sa se determine (Z+ iZ).

    Exercitiu 2.1.45. Se considera operatia : R R R gegeben durch x y =xy 5x 5y + 30. Ist (R, ) eine Gruppe? Aber (R \ {5}, ), ((5,), ) oder((, 5), )?Exercitiu 2.1.46. Man ziege, dass (Zn,+) (n N, n 2) eine abelsche Gruppeist, si pn : Z Zn, pn(x) = [x]n ein surjektiver Gruppenhomomorphismus ist(siehe also Ubung 1.4.42).

    Exercitiu 2.1.47. Fie (Gi, ) o familie de grupuri. Sa se arate ca(

    iI G, )

    esteun grup, unde

    (xi)iI (yi)iI = (xiyi)iI pentru orice (xi)iI , (yi)iI iI

    Gi.

    Sa se arate de asemenea ca pj :iI Gj , pj(xi)iI = xj este un homomorfism

    surjectiv pentru orice j I.

  • 26 GEORGE CIPRIAN MODOI

    Exercitiu 2.1.48. Fie G un grup. Sa se arete ca daca pentru orice doua elementex, y G, exsita k Z astfel ncat (xy)i = xiyi pentru i = k 1, k, k + 1 atunci Geste abelian.

    Exercitiu 2.1.49. Sa se arate ca o parte stabila finita a unui grup este ntotdeaunaun subgrup. Dar o parte stabila infinita?

    Exercitiu 2.1.50. Se considera un grup (G, ), si se noteaza Sub(G) = {H G |H G} multimea tuturor subgrupurilor. Sa se arata ca (Sub(G),) este o latice.Exercitiu 2.1.51. Fie A1A2 . . . An un poligon regulat (cu n varfuri si n laturi) cucentrul O ntr-un plan . (considerat ca o multime de puncte). O izometrie este ofunctie f : cu proprietatea ca |f(X)f(Y )| = |XY | pentru orice X,Y ,unde prin |XY | notam distanta dintre X si Y . Se considera multimea tuturorizometriilor care invariaza poligonul A1A2 . . . An mai precis

    Dn = {f : |f este o izometrie sif(A1A2 . . . An) = A1A2 . . . An}.

    Notam cu s rotatia n jurul centrului O cu 2pin radiani, (de la A1 catre A2) si cu tsimetria axiala fata de axa A1O. Sa observam ca s, t : sunt izometrii. Sa searate ca

    (1) sn = 1 = t2 (aici 1 = 1 este functia identitate a planului ).(2) ts = sn1t.(3) Dn = {1, s, . . . , sn1, t, st, . . . , sn1t}(4) Dn este un grup n raport cu compunerea functiilor (care este numit grupul

    diedral)(5) Sa se determine s, t, s, t

    Sa se construiasca tablele operatiilor D3 si D4.

    Exercitiu 2.1.52. Pe multimea H = {1,1, i,i, j,j, k,k} se defineste n felulurmator o nmultire:

    1 este elementul neutru. Inmultirea respecta regula semnelor: (x)y = x(y) = xy (altfel semnele

    + si nu au nca vreun sens). i2 = j2 = k2 = 1. ij = k = ji, jk = i = kj, ki = j = ik.

    Sa se arate ca (H, ) este un grup (numit grupul quaternionilor).Exercitiu 2.1.53. Sa se arete ca grupurile (R,+) si (R+, ) sunt izomorfe.Exercitiu 2.1.54. Sa se arate ca f : C R, f(x) = arg x este un homomorfismde grupuri ntre (C, ) si (R,+), si sa se determine Kerf si Imf .Exercitiu 2.1.55. Sa se arate ca grupurile (Z,+) si (Zn,+) (n N, n 2) suntciclice.

    Exercitiu 2.1.56. Fie n N, n 2. Sa se arate caUn = {x C | exista n N astfel ncat xn = 1}

    este un subgrup a grupului (C, ) si ca Un este ciclic. Sa se gaseasca un izomorfismntre (Zn,+) si (Un, ).

  • ALGEBRA PENTRU INFORMATICA 27

    Exercitiu 2.1.57. Sa se gaseasca toate subgrupurile lui (Z,+). Indicatie: Sa searate ca

    Sub(Z,+) = {nZ | n N}, unde nZ = {nx | x Z}.Exercitiu 2.1.58. Sa se gaseasca un exemplu de doua subrupuri ale unui grup acaror reuniune nu este subgrup.

    Exercitiu 2.1.59. Fie (G,+) un grup abelian si H,K G dua subgrupuri. Sa searate ca H K = H +K, unde H +K = {x+ y | x H, y K}.Exercitiu 2.1.60. Fie (G, ) un grup si H,K G. Sa se arate ca H K Gddaca H K sau K H.Exercitiu 2.1.61. Fie n,m Z. Sa se arate ca(a) nZ mZ m|n.(b) nZ mZ = kZ, unde k = lcm(n,m).(c) nZ+mZ = dZ, unde d = gcd(n,m).

    Exercitiu 2.1.62. Sa se arate ca pentru n,m N cu d = gcd(n,m), exista douanumere ntregi s, t Z, astfel ncat d = sn+tm. Folositi acest rezultat ca sa aratatica 1 = gcd(n,m) ddaca exista s, t Z astfel ncat 1 = sn+ tm.Exercitiu 2.1.63. Sa se foloseasca algoritmul lui Euclid pentru ca plecand dela m,n N sa determinam numerele ntregi s, t cu proprietatea ca gcd(n,m) =sn+ tm zu bestimmen.

    Exercitiu 2.1.64. Sa se gaseasca toate grupurile (pana la un izomorfism) care sepot defini pe o multime cu 4 elemente.

    Exercitiu 2.1.65. Fie (G, ) un grup si x, y G astfel ncat xy = yx. Avem:(a) ord(x1) = ord(x)(b) ord(xy) = ord(yx).

    Exercitiu 2.1.66. Fie f : G H un homomorfism de grupuri. Daca x G estede ordin finit, atunci tot asa este si f(x), si avem ord(f(x))| ord(x).Exercitiu 2.1.67. Doua grupuri ciclice infinite sunt izomorfe. Doua grupuri ciclicefinite sunt izomorfe ddaca au acelasi numar de elemente.

    Exercitiu 2.1.68. Daca G este un grup ciclic, atunci exista un homomorfismsurjectiv Z G.Exercitiu 2.1.69. Sa se arata ca urmatoarele perechi de grupuri nu sunt izomorfe:(Zn,+) si (Zm,+) si n 6= m; (Z,+) si (Q,+); (Z8,+) si (Z4Z2,+) (pentru grupulprodus vezi Ubung 2.1.47).

    Exercitiu 2.1.70. Fie G A A, (g, x) 7 gx o actiune a grupului (G, ) pemultimea A. Sa se arate ca:

    (a) Pentru orice x A submultimea StabG(x) = {g G | gx = x} formeaza unsubgrup a lui G.

    (b) Multimea K = {g G | gx = x fur alle x A} este un subgrup a lui G ( acestsubgrup este numit nucleul actiunii. Mai mult avem: K =

    xA StabG(x).

    (c) Actiunea este fidela ddaca nucleul este trivial, adica K = {1}.Exercitiu 2.1.71. Fie N = {1, x, x2} si H = {1, y, y2, y3} doua grupuri ciclicegenerate de elementele x si y cu ord(x) = 3, ord(y) = 4. Atunci:

  • 28 GEORGE CIPRIAN MODOI

    (a) Sa se defineasca o actiune netriviala a lui H pe N , (adica : H N N) asancat h 1 = h pentru orice h H.

    (b) Care este nucleul acestei actiuni?(c) Pentru h H se considera h : N N , h(n) = h n. Sa se arate ca h este

    un izomorfism.(d) Consideram G = N H ca multimi. Se defineste o operatie pe G prin

    (n1, h1)(n2, h2) = (n1(h1 n2), h1h2).Sa se arate ca G mpreuna cu aceasta operatie este un grup neabelian cu 12elemente.

    Exercitiu 2.1.72. Un grup de ordin prim este ciclic. Indicatie: Se arata ca ungrup de ordin prim nu are subgrupuri netriviale (un astfel de grup se zice simplu).

    Exercitiu 2.1.73. Daca multimile A si B au acelasi cardinal, atunci grupurileS(A) si S(B) sunt izomorfe.

    Exercitiu 2.1.74. Sa se descompuna =

    (1 2 3 4 5 6 7 83 2 1 5 6 4 8 7

    ) S8 ca

    produs de cicluri doua cate doua disjuncte.

    Exercitiu 2.1.75. Fie =

    (1 2 3 4 53 4 1 5 2

    ), ==

    (1 2 3 4 52 3 4 5 1

    ) S5.

    (a) Sa se descompuna si ca produs de cicluri doua cate doua disjuncte.(b) Sa se calculeze , , 1, 2.(c) Sa se calculeze ord() si .(d) Sa se calculeze () si ().

    Exercitiu 2.1.76. Sa se arate ca

    (a) () =

    1i

  • ALGEBRA PENTRU INFORMATICA 29

    (c) este distributiva bilateral n raport cu +, adica pentru orice x, y, x R avem:x(y + z) = xy + xz si (y + z)x = yx+ zx.

    Inelul R se zice comutativ sau unitar, dupa cum operatia este si comutativa,respectiv are unitate.

    Observatie 2.2.2. Intr-un inel R se noteaza cu 0 elementul neutru pentru + si cu1 elementul neutru pentru (daca acesta din urma exista). Ordinea operatiilor estecea obisnuita, mai precis mai ntai actioneaza nmultirea si pe urma adunarea.

    Exemplu 2.2.3. (a) (Z,+, ), (Q,+, ), (R,+, ), (C,+, ) sunt inele comutative siunitare.

    (b) Daca R este un inel comutativ, atunci (Mnn(R),+, ) este de asemenea inel;totusi (Mnn(R),+, ) nu este n mod necesar comutativ. Daca R este unitaraunci to asa este si (Mnn(R),+, ), iar elementul neutru pentru nmultireamatricilor este asa numita matrice unitate de rank n:

    In =

    1 0 . . . 00 1 . . . 0 0 0 . . . 1

    (c) Daca (R,+) este un grup abelian, atunci (R,+, ) este un inel unde xy = 0

    pentru orice x, y R (un astfel de inel se numeste de patrat nul. In particularR = {0} este un inel (unitar!), unde 0 + 0 = 0 0 = 0 (acest inel se numesteinelul nul si este notat R = 0).

    (d) Daca (R,+, ) este un inel, atunci tot asa este si Ro,+., unde Ro = R six y = yx pentru orice x, y R; Ro se numeste inelul opus lui R.

    Propozitie 2.2.4. (Reguli de calcul in inele) Fie R un inel si x, y, x R. Avem:(a) x0 = 0x = 0.(b) x(y) = (x)y = xy.(c) x(y z) = xy xz si (y z)x = yx zx.(d) Daca R 6= 0 este un inel unitar, atunci 1 6= 0.Demonstratie. Definitie 2.2.5. Un corp este un inel unitar (K,+, ) cu proprietatea ca oricarex K este inversabil (n raport cu ). (Aici si n continuare notam K = K \ {0})Observatie 2.2.6. In conformitate cu Propozitia 2.1.5, un inel unitar K este exactatunci un corp cand (K, ) este un grup.Exemplu 2.2.7. (a) (Q,+, ), (R,+, ), (C,+, ) sunt corpuri comutative.(b) (Z,+, ) nu este un corp.Subinele si subcorpuri.

    Definitie 2.2.8. Fie (R,+, ) un inel. Un subinel a lui R este o submultime S R,cu proprietatea ca operatiile + si din R induc operatii bine definite pe S (adicax, y S x+ y, xy S; se mai spune ca S este o parte stabila n raport cu + si), iar cu operatiile induse S formeaza un inel. Se scrie S R. Daca 1 R atuncise zice unitar un subinel S R cu proprietatea 1 S.Exemplu 2.2.9. (1) Z Q R C

  • 30 GEORGE CIPRIAN MODOI

    (2) 2Z Z aber 1 / 2Z.(3) Orice inel R are asa numitele subinele triviale, adica {0} si R.

    Propozitie 2.2.10 (Teorema de caractcterizare a subinelelor). Fie (R,+, ) un inelsi fie S R o submultime. Urmatoarele afirmatii sunt echivalente :

    (i) S R.(ii) (a) 0 S.

    (b) x, y S x+ y S.(c) x S x S.(d) x, y S xy S.

    (iii) (a) 0 S.(b) x, y H x y H.(c) x, y S xy S.

    Demonstratie. Propozitie 2.2.11. Fie (R,+, ) un inel. Daca Si R, cu i I, atunci avemiI Si R.

    Observatie 2.2.12. Reuniunea a doua sau mai multe subinele, nu este cu necesi-tate subinel ( a se vedea si Observatia 2.1.11). 2.1.11).

    Definitie 2.2.13. Fie (K,+, ) un corp. Un subcorp a lui K este o submutimeL K cu proprietatea ca operatiile + si din R induc operatii bine definite pe S,iar cu operatiile induse L formeaza un corp. Se scrie L K.Observatie 2.2.14. Un subcorp este un subinel unitar

    Propozitie 2.2.15 (Teorema de caractcterizare a subcorpurilor). Fie (K,+, ) uncorp si fie L K o submultime. Urmatoarele afirmatii sunt echivalente:

    (i) L K.(ii) (a) 0, 1 L.

    (b) x, y L x+ y L.(c) x L x L.(d) x, y L xy L.(e) x L x1 L

    (iii) (a) 0, 1 L.(b) x, y L x y L.(c) x, y L xy1 S.

    Demonstratie. Observatie 2.2.16. Ca si n cazul grupurilor putem defini subinelul sau subcorpulgenerat.

    Homomorfisme.

    Definitie 2.2.17. Un homomorfism de inele (respectiv corpuri) este o functie f :R S (f : K L), unde R si S (K si L) sunt doua inele (corpuri), astfel ncatf(x+ y) = f(x) + f(y) si f(xy) = f(x)f(y) pentru orice x, y R (x, y K). Dacainelele R si S sunt unitare, atunci un homomorfism f : R S se zice unitar dacaf(1) = 1. Un homomorfism de inele (corpuri) se numeste izomorfism daca el estesi bijectiv; n acest caz, inelele (corpurile) se zic izomorfe si scriem R = S (sauK = L).

  • ALGEBRA PENTRU INFORMATICA 31

    Exemplu 2.2.18. Pentru doua inele (corpuri) R si S funtiile 1R si 0 : G H,0(x) = 0 sunt un izomorfism, respectiv un homomorfism. Daca S R atunciaplicatia de incluziune i : S R este un homomorfism.Lema 2.2.19. Un homomorfim de corpuri este sau unitar sau nul.

    Demonstratie. Lema 2.2.20. Compunerea a doua homomorfisme de inele (corpuri) este de aseme-nea un homomorfism. Funtia inversa a unui izomorfism de inele (corpuri) este deasemenea un izomorfism.

    Demonstratie.

    Elemente speciale ntr-un inel

    Ca si n cazul monoizilor, pentru un inel unitar R notam

    R = {x R | x este inversabil (n raport cu nmultirea)}.Definitie 2.2.21. Fie R un inel. Un element x R se numeste:

    (1) divizor al lui zero la stanga sau dreapta daca exista y R, y 6= 0 astfelncat xy = 0 respectiv yx = 0. Elementul x este numit simplu divizor allui zero daca este un divizor al lui zero atat la stanga cat si la dreapta.

    (2) idempotent daca este adevarata egalitatea x2 = x.(3) nilpotent daca exista n N, astfel ncat xn = 0.

    Observatie 2.2.22. Fie R 6= 0 un inel si fie x R.(a) In mod evident 0 este un divizor al lui zero. Se spune ca 0 este divizorul trivial

    al lui zero. Un inel R se zice fara divizori ai lui zero, daca R nu contine divizorinetriviali ai lui zero.

    (b) 0 si 1 (daca exista 1 R, ceea ce nseamna R este unitar) sunt elementeidempotente; acesti idempotenti sunt numiti triviali.

    (c) Daca x este idempotent, atunci este valabila egalitatea xn = x, pentru oricen N.

    (d) Daca x este nilpotent si xn = 0 pentru un n N, atunci avem xn+k = 0 pentruorice k N.

    Exemplu 2.2.23. Se considera inelul (Z12,+, ).(1) [3]12 este un divizor al lui zero, pentru ca [3]12[4]12 = [4]12[3]12 = [0]12.(2) [4]12 este idempotent, pentru ca [4]

    212 = [4]12.

    (3) [6]12 este nilpotent, pentru ca [6]212 = [0]12.

    Propozitie 2.2.24. Fie R un inel unitar.

    (1) Daca x R atunci x nu este un divizor al lui zero.(2) x R nu este un divizor al lui zero la stanga (dreapta) ddaca cu x se poate

    simplifica la stanga (dreapta).(3) Daca e R este un idempotent netrivial, atunci e este un divizor al lui

    zero.(4) Daca x R este nilpotent, atunci x este un divizor al lui zero.

    Demonstratie. Definitie 2.2.25. Un domeniu de integritate este un inel comutativ, unitar si faradivizori ai lui zero.

  • 32 GEORGE CIPRIAN MODOI

    Propozitie 2.2.26. Un subinel unitar al unui corp comutativ este un domeniu deintegritate.

    Demonstratie. Corolar 2.2.27. Un corp comutativ este un domeniu de integritate.

    Examples 2.2.28. Q, R, C sunt corpuri comutative, deci sunt si domenii dein-tegritate. Z este un domeniu de integritate care nu este corp.Propozitie 2.2.29. Un doemeniu de interitate finit este un corp (comutativ).

    Demonstratie. Corolar 2.2.30. Daca p este un numar prim, atunci (Zp,+, ) este un corp comu-tativ.

    Exercitii la inele si corpuri.

    Exercitiu 2.2.31. Sa se verifice ca (Zn,+, ) (n 2) este un inel comutativ siunitar, unde + si sunt definite ca n Exerctiul 1.4.42.Exercitiu 2.2.32. Pentru un grup abelian (G,+) se considera

    End(G) = {f : G G | f este un homomorfism de grupuri}.Sa se arate ca (End(g),+, ) este un inel unitar, unde pentru f, g End(G) sedefineste adunarea prin:

    f + g : G G, (f + g)(x) = f(x) + g(x), pentru orice x G.(End(g),+, ) este numit inelul endomorfismelor lui G.Exercitiu 2.2.33. Se considera o multime oarecare A si un inel R. Pe multimeaRA = {f : A R | f este o funtie} se definesc operatiile +, : RA RA RAprin f + g, fg : A R, (f + g)(x) = f(x) + g(x) si (fg)(x) = f(x)g(x) pentru oricef, g RA si orice x A. Sa se arate ca RA este un inel, iar RA exact atunci estecomutativ sau unitar, cand R are aceesi proprietate.

    Exercitiu 2.2.34. Sa se verifice ca (Q,+, ) este un corp, unde + si sunt definiteca n Exerctiul 1.4.41.

    Exercitiu 2.2.35. Se considera grupul quaternionilor H = {} (vezi ExercitiulUbung 2.1.52). Sa se verifice ca

    H = {a+ bi+ cj + dk | a, b, c, d R}este un corp necomutativ, unde

    (a+ bi+ cj + dk) + (a+ bi+ cj + dk) = (a+ a) + (b+ b)i+ (c+ c)j + (d+ d)k

    (a+ bi+ cj + dk)(a + bi+ cj + dk) = (aa bb cc dd) + (ab + ba + cd dc)i+ (ac bd + ca + db)j + (ad + bc cb + da)k

    (adica nmultirea n H este indusa de n multirea n H).Exercitiu 2.2.36. Fie R un inel comutativ si unitar. Sa se verifice ca multimeatuturor polinoamelor

    R[X] = {a0 + a1X + . . .+ anXn | n N, ai R pentru orice 1 i n}.formeaza un inel comutativ si unitar mpreuna cu adunarea si nmultirea bisnuitaa polinoamelor. Sa se arate de asemenea ca R este un subinel al lui R[X].

  • ALGEBRA PENTRU INFORMATICA 33

    Exercitiu 2.2.37. Sa se determine toate subinelele lui (Z,+, ).Exercitiu 2.2.38. Fie n N, n 2. Sa se arate ca Zn = {[k]n | gcd(n, k) = 1}.Sa se foloseasca acest rezultat pentru a arata din nou ca Zn este un corp ddaca neste un numar prim.

    Exercitiu 2.2.39. Sa se rezolve urmatoarele ecuatii n Z6: [4]6x + [5]6 = [1]6 si[5]6x+ [3]6 = [1]6

    Exercitiu 2.2.40. Sa se arate ca Z+ iZ = {a+ ib | a, b Z} este un subiel al luiC. Sa se arate ca

    R =

    {[a bb a

    ]| a, b Z

    }este un subiel al lui (M22(Z),+, ), si R = Z+ iZ. Sunt Z+ iZ si/sau R domeniide integritate? Dar corpuri?

    Exercitiu 2.2.41. Sa se determine (Z+ iZ).

    Exercitiu 2.2.42. Sa se arate ca R[X] = R, pentru orice inel comutativ siunitar R.

    Exercitiu 2.2.43. Fie R un inel comutativ si unitar. Sa se arate ca ineleleMnn(R) siMnn(R)o sunt izomorfe. De aici sa se deduca echivalenta urmatoarelorafirmatii, pentru orice A Mnn(R):

    (i) A este inversabila la stanga.(ii) A este inversabila la dreapta.

    (iii) A este inversabila.

    Exercitiu 2.2.44. Sa se arate ca urmatoarele perechi de inele nu sunt izomorfe:Z si Q; Z si M22(Z).

    Exercitiu 2.2.45. Sa se arate ca urmatoarele corpuri nu sunt izomorfe: R si C.

    Exercitiu 2.2.46. Sa se arate ca Q+ iQ = {a+ ib | a, b Q} este un subcorp allui C.

    Exercitiu 2.2.47. Daca R este un domeniu de integritate, atunci aceeasi propri-etate este valabila pentru R[X] .

    Exercitiu 2.2.48. Sa se determine toate elementele idempotente din inelul Zn,unde n N, n 2.Exercitiu 2.2.49. Sa se determine toate elementele nilpotente din inelul Zn, unden N, n 2.

    3. Algebra liniara

    In acest capitol fixam un corp comutativ (K,+, ). Exemple de corpuri comuta-tive sunt n special K = R sau K = C dar cazurile K = Q sau K = Zp, sie p Neste un numar prim sunt de asemenea posibile.

  • 34 GEORGE CIPRIAN MODOI

    3.1. Spatii vectoriale si aplicatii liniare.

    Definitie 3.1.1. Un spatiu vectorial peste K sau mai scurt K-spatiu vectorial esteformat dintr-un grup abelian (V,+) mpreuna cu o operatie externa : KV Vcare satisface urmatoarele axiome:

    (SV1) (x+ y) = x+ y;(SV2) (+ )x = x+ x;(SV3) (x) = ()x;(SV4) 1x = x

    pentru orice x, y V si orice si orice , K. Se scrie KV . Elementele din Vsi K sunt numite vectori respectiv scalari. Adunarea n V si operatia externa senumesc adunarea vectorilor respectiv nmultirea cu scalari. Spatiile vectoriale suntnumite uneori spatii liniare.

    Exemplu 3.1.2. (1) V = {0} este un spatiu vectorial, unde 0+0 = 0 si 0 = 0pentru orice K. Se noteaza cu 0 acest spatiu vectorial.

    (2) Kn este un K-spatiu vectorial n raport cu adunarea vectorilor:

    [x1, x2, . . . , xn] + [y1, y2, . . . , yn] = [x1 + y1, x2 + y2, . . . , xn + yn]

    si cu nmultirea cu scalari:

    [x1, x2, . . . , xn] = [x1, x2, . . . , xn].

    (3) Mmn(K) este unK-spatiu vectorial cu adunarea matricilor si cu nmultireaunei matrici cu un scalar, adica pentru A = [ai,j ] si B = [bi,j ] si K,avem A+B = [ai,j + bi,j ] si A = [ai,j ]. ce obtinem cand punem m = 1?Dar pentru n = 1?

    (4) Daca K este un corp si L este un subcorp, atunci L este un k-spatiu vecto-rial, unde adunarea vectorilor este adunarea n L, iar nmultirea cu scalarieste:

    K L L, (, x) 7 x, pentru orice x L, K.(5) Multimea tuturor polinoamelor

    K[X] = {a0 + a1X + . . .+ anXn | n N, a0, a1, . . . , an K}este un K-spatiu vectorial n raport cu adunarea polinoamelor (vectori) sinmultirea polimoamelor cu scalari din K.

    (6) Multimea tuturor vectorilor liberi din plan (sau din spatiu) n raport cuadunarea vectorilor liberi si die obisnuita nmultire cu scalari este un R-spatiu vectorial.

    Propozitie 3.1.3. (Reguli de calcul n spatii vectoriale) Fie V un K-spatiu vecto-rial, x, y V si , K. Avem:(a) 0 = 0 = 0x.(b) (x) = ()x = x.(c) (x y) = x y si ( )x = x x.(d) x = 0 ddaca = 0 sau x = 0.

    Demonstratie.

  • ALGEBRA PENTRU INFORMATICA 35

    Subspatii vectoriale.

    Definitie 3.1.4. Fie V un K-spatiu vectorial. Un subspatiu (vectorial) a lui Veste o submultime U V , cu proprietatea ca adunarea vactorilor si nmultirea cuscalari induc operatii bine definite pe U (adica x, y U, K x + y, x U),si U mpreuna cu operatiile restrictionate fromeaza un spatiu vectorial. Se scrieU K V sau simplu U V .Exemplu 3.1.5. Orice spatiu vectorial KV are doua subspatii as a zise triviale,anume 0 K V si V K V .Propozitie 3.1.6 (de caracterizare a subspatiilor). Fie V un K-spatiu vectorial sifie U V o submultime. Urmatoarele afirmatii sunt echivalente:

    (i) U K V .(ii) (a) 0 U .

    (b) x, y U x+ y U .(c) x U, K x U .

    (iii) (a) 0 S.(b) x, y U x+ y U .

    Demonstratie.

    Propozitie 3.1.7. Fie V un K-spatiu vectorial. Daca Ui K V sunt subspatii, cui I, atunci avem iI Ui K V .Demonstratie.

    Observatie 3.1.8. Reuniunea a doua sau mai multe subspatii nu este cu necesitatesubspatiu (vezi de asemenea Observatia 2.1.11).

    Definitie 3.1.9. Fie V un K-spatiu vectorial si X V o submultime a lui V .Subspatiul generat de X este definit prin

    X = XK =

    XUKVU.

    Daca X = {x1, x2, . . . , xn} este o multime finita, scriem x1, x2, . . . , xnK n loc de{x1, x2, . . . , xn}K .Lema 3.1.10. Fie V un K-spatiu vectorial si X V o submultime a lui V . Avem:(a) XK K V .(b) X XK si X = XK ddaca X K V .(c) XK este cel mai mic subspatiu a lui V care contine X i. e.

    U = XK ddaca

    U K VX Udaca W K V astfel ncat X W atunci U K W

    .

    (d) Daca X Y G atunci XK Y K V .Demonstratie.

    Propozitie 3.1.11. Fie V un K-spatiu vectorial si X V o submultime a lui V .Avem:

    XK = {1x1+2x2+. . .+nxn | n N, x1, x2, . . . , xn X si 1, 2, . . . , n K}.

  • 36 GEORGE CIPRIAN MODOI

    In particular, pentru X = {x1, x2, . . . , xn} avem:x1, x2, . . . , xnK = {1x1 + 2x2 + . . .+ nxn | 1, 2, . . . , n K}.

    Demonstratie. Definitie 3.1.12. Fie V un K-spatiu vectorial si X V . Se numeste combinatieliniara a vectorilor din X o expresie de forma 1x1 + 2x2 + . . .+ nxn cu n N,x1, x2, . . . , xn X si 1, 2, . . . , n K. In particular o combinatie liniara avectorilor x1.x2, . . . , xn V este o expresie de forma 1x1 + 2x2 + . . . + nxn,1, 2, . . . , n K, si o combinatie liniara a vectorilor x, y V este x + y, cu, K.Observatie 3.1.13. Propozitia 3.1.11 spune ca subspatiul generat de X continetoti vectorii care se pot scrie ca V care se pot scrie n forma de combinatii liniarede elemente ale lui X.

    Corolar 3.1.14. Fie V un K-spatiu vectorial.

    (a) Pentru x V avem xK = {x | K}.(b) Pentru x, y V avem x, yK = {x+ y | , K}.Suma si suma directa a subspatiilor.

    Definitie 3.1.15. Fie V un K-spatiu vectorial si fie S, T K V doua subspatii.Suma acestor subspatii este definita ca fiind S + T = {x+ y | x S, y T}.Propozitie 3.1.16. Fie V un K-spatiu vectorial si fie S, T K V doua subspatii.Atunci avem S T K = S + T . In particular suma a doua subspatii este unsubspatiu.

    Demonstratie. Corolar 3.1.17. Intr-un K-spatiu vectorial V notam cu SubK(V ) = {S | S KV } multimea tuturor subspatiilor. Atunci (SubK(V ),K) este o latice n careinf{S, T} = S T si sup{S, T} = S + T .Demonstratie.

    Elementele unei sume S + T a doua subspatii S, T K V sunt vectorii care sepot scrie ca o suma ntre un vector din S si un vector din T . Suntem interesatindeosebi de cazul n care aceasta scriere este unica.

    Propozitie 3.1.18. Fie V un K-spatiu vectorial si fie S, T K V doua subspatii.Urmatoarele afirmatii sunt echivalente:

    (i) S T = 0;(ii) Scrierea oricariu vector din S + T ca o suma dintre un vector din S si unul

    din T este unica, i. e. pentru v S + T avem v = x+ y = s+ t cu x, s Ssi y, t T implica x = s si y = t.

    Demonstratie. Definitie 3.1.19. Se numeste directa o suma S + T a doua subspatii S si T caresatisface conditiile echivalente din Propozitia 3.1.18. In acest caz se scrie S T =S + T .

    Observatie 3.1.20. Fie V K-spatiu vectorial si fie S, T K V doua subspatii.Atunci V = S T ddaca S T = 0 si S + T = V .

  • ALGEBRA PENTRU INFORMATICA 37

    Aplicatii liniare.

    Definitie 3.1.21. Fie V si W doua K-spatii vectoriale. Se numeste aplicatieliniara sau homomorfism de spatii vectoriale ntre V si W o functie f : V W cuproprietatile f(x+ y) = f(x) + f(y) si f(x) = f(x) pentru orice x, y V si orice K. Se numeste isomorfism o aplicatie liniara care este si bijectiva. In acestcaz spatiile vectoriale V si W ise zic izomorfe si scriem V = W .Exemplu 3.1.22. Pentru orice doua K-spatii vectoriale V si W aplicatiile 1V si0 : V W , 0(x) = 0 sunt liniare; mai mult 1V este chiar un isomorfism. DacaV K W atunci aplicatia de incluziune i : V W este liniara.Notatie 3.1.23. Fie V si W doua K-spatii vectoriale. Vom nota

    HomK(V,W ) = {f : V W | f este liniara} si EndK(V ) = HomK(V, V )(o aplicatie liniara f : V V mai este numita si endomorfism a lui V ).Observatie 3.1.24. Orice aplicatie liniara f : V W este si un morfism degrupuri, asadar avem:

    (a) f(0) = 0.(b) f(x) = f(x).Propozitie 3.1.25. Fie V si W doua K-spatii vectoriale. O aplicatie f : V Weste liniara ddaca f(x + y) = f(x) + f(y), pentru orice x, y V si orice, K.Demonstratie. Observatie 3.1.26. Prin inductie se poate arata ca o aplicatie liniara pastreazacombinatiileliniare, i. e. daca f : V W este liniara, 1, . . . , n K six1, . . . , xn V atunci avem:

    f(1x1 + . . .+ nxn) = 1f(x1) + . . .+ 2f(xn).

    Lema 3.1.27. Compunerea si adunarea a doua aplicatii liniare (daca exista) sunt

    de asemenea aplicatii liniare. Inmultirea unei aplicatii liniare cu un scalar este oaplicatie liniara. Functia inversa a unui izomorfism este de asemenea un izomor-fism.

    Demonstratie. Teorema 3.1.28. Fie V si W doua K-spatii vectoriale. Atunci HomK(V,W ) estede asemenea un K-spatiu vectorial n raport cu adunarea vectorilor (a functiilor):

    + : HomK(V,W )HomK(V,W ) HomK(V,W ),(f + g)(x) = f(x) + g(x) pentru orice x V,

    si cu nmultirea cu scalari

    : K HomK(V,W ) HomK(V,W ), (f)(x) = f(x), pentru orice x V.In particular (EndK(V ),+, ) este un inel unitar.Demonstratie. Definitie 3.1.29. Fie f : V W o aplicatie liniara. Numim nucleul respectivimaginea lui f multimile

    Kerf = {x V | f(x) = 0} si Imf = {f(x) | x V }.

  • 38 GEORGE CIPRIAN MODOI

    Propozitie 3.1.30. Daca f : V W este o aplicatie liniaraatunci avem:(a) Kerf K V .(b) Imf K W .(c) f este injectiva ddaca Kerf = 0.(d) f este surjectiva ddaca Imf = W .

    Demonstratie.

    Exercitii la spatii vectoriale.

    Exercitiu 3.1.31. Sa se arate ca R+ = (0,) este un R-spatiu vectorial n raportcu adunarea vectorilor:

    : R+ R+ R+, x y = xy, pentru orice x, y R+,si cu nmultirea cu scalari

    : R R+ R+, x = x pentru orice x R+, R.Exercitiu 3.1.32. Sa se verifice ca operatiile:

    : R R R, x y = 5x5 + y5, pentru orice x, y R,

    : R R R, x = 5x pentru orice , x Rdefinesc o structura de R-spatiu vectorial pe R.

    Exercitiu 3.1.33. Care dintre urmatoarele submultimi ale multimii R3 sunt R-subspatii:

    A = {[x1, x2, x3] R3 | 2x1 + x2 x3 = 0}. B = {[x1, x2, x3] R3 | 2x1 + x2 x3 = 1}. C = {[x1, x2, x3] R3 | x1 = x2 = x3}. D = {[x1, x2, x3] R3 | x21 + x2 = 0}. E = R3 \A. F = (R3 \A) {0}.

    Exercitiu 3.1.34. Fie n N fixat. Sa se arate ca Kn[X] = {f K[X] | grad(f) n} este un K-subspatiu a lui K[X].Exercitiu 3.1.35. Sa se gaseasca ecuatiile care determina vectorii din urmatoarelesubspatii: S = [1, 2,1] si T = [1, 2, 1], [2, 1,3] ale lui R3 (ecuatiile acestorsubspatii).

    Exercitiu 3.1.36. Sa se scrie subspatiile S = {[x1, x2, x3] R3 | x1x2x3 = 0}si T = {[x1, x2, x3] R3 | x1 x 2 = x2 x3 = x3 x1} ale lui R3 ca subspatiigenerate (cu numar minimal de generatori).

    Exercitiu 3.1.37. Se considera submultimile S, T R3 date prin S = {[x1, x2, x3] R3 | x1 + x2 + x3 = 0} si T = {[x1, x2, x3] R3 | x1 = x2 = x3}. Sa se arate caS, T R3 si S T = R3.Exercitiu 3.1.38. Se considera S = {I2 M22(R) | R} si T = {A M22(R) | Tr(A) = 0}, unde Tr(A) este suma intrarilor de pe diagonala principalaa matricii A. Sa se arate ca S, T R M22(R) si S T = M22(R).

  • ALGEBRA PENTRU INFORMATICA 39

    Exercitiu 3.1.39. Se considera o multime oarecare A si RA = {f : A R |f este o functie}. Sa se arate ca RA este un R-spatiu vectorial n raport cu adunareavectorilor (a functiilor):

    + : RA RA RA, (f + g)(x) = f(x) + g(x), pentru orice x A,si cu nmultirea cu scalari

    : R RA RA, (f)(x) = f(x), pentru orice x A.Exercitiu 3.1.40. Se considera submultimile S = {f RR | f este para} si T ={f RR | f este impara} n RR. Sa se arate ca S, T RR si S T = RR.Exercitiu 3.1.41. Se considera un mumar prim p N . Sa se arate ca n orice Zp-spatiu vectorial este valabila efgalitatea 0 = x+x+ . . .+x(p mal), pentru orice x V. Exista o structura de Zp-spatiu vectorial pe grupul abelian (Z,+)?

    Exercitiu 3.1.42. Care dintre urmatoarele aplicatii sunt liniare:

    (1) f : R3 R3, f [x1, x2, x3] = [x1 x2, x2 x3, x3 x1].(2) f : R3 R3, f [x1, x2, x3] = [x1 1, x2 + 2, x3 + 1].(3) f : R3 R2, f [x1, x2, x3] = [2x1 3x2 + x3,x1 + x2 + 3x3, x1 + x2 + x3].(4) f : R2 R3, f [x1, x2] = [x1 + x2, x1 x2, 2x1 + x2].(5) f : R2 R, f [x1, x2] = x21 x22.(6) f : R2 R2, f [x1, x2] = [a1,1x1+a2,1x2, a1,2x1+a2,2x2], unde a1,1, a1,2, a2,1, a2,2

    R sunt fixate.Pentru aplicatiile care sunt liniare sa se determine ecuatiile subspatiilor Kerf siImf .

    3.2. Baza unui spatiu vectorial.

    Independenta liniara.

    Definitie 3.2.1. Fie V unK-spatiu vectorial. Se numete lista de vectori un elementv = [v1, v2, . . . , vn]

    t din V n1, unde n N este arbitrar. O lista de vectori v =[v1, v2, . . . , vn]

    t se zice liniar independenta daca pentru 1, 2, . . . , n K scalariavem 1v1 + 2v2 + . . . + nvn = 0 1 = 2 = . . . = n = 0. O lista sezice liniar dependenta daca nu este liniar independenta. In acest caz o relatie dedependenta liniara este o egalitate de forma 1v1 +2v2 + . . .+nvn = 0 cu scalarii1, 2, . . . , n K nu toti nuli.Observatie 3.2.2. (1) Definitia liniar independentei unei liste v = [v1, v2, . . . , vn]

    t

    se poate scrie astfel:

    [1, 2, . . . , n][v1, v2, . . . , vn]t = 0 1 = 2 = . . . = n = 0.

    Acesta este motivul pentru care luam [v1, v2, . . . , vn]t V n1 n loc de

    [v1, v2, . . . , vn] V n.(2) Lista vida de vectori este admisa (pentru n = 0). In particular lista vida

    este liniar independenta.(3) O lista cu un singur element [v1]

    t este exact atunci liniar independenta candv1 6= 0.

    (4) Daca lista [v1, v2, . . . , vn]t V n1 contine vectorul nul vi = 0, atunci ea

    este liniar dependenta, deoarece

    0v1 + . . .+ 1vi + . . .+ 0vn = 0.

  • 40 GEORGE CIPRIAN MODOI

    (5) Daca lista [v1, v2, . . . , vn]t V n1 contine doi vectori egali vi = vj cu i 6= j

    atunci ea este liniar dependenta, deoarece

    0v1 + . . .+ 1vi + . . .+ (1)vj + . . . 0vn = 0.(6) Uneori nu suntem interesati de ordinea vectorilor dintr-o lista v = [v1, v2, . . . , vn]

    t

    si spunem ca vectorii v1, v2, . . . , vn sunt liniar (in)dependenti n loc saspunem ca lista de vectori are respectiva proprietate.

    Exemplu 3.2.3. (1) Lista [v1, v2, v3]t cu vectorii v1 = [1, 0, 1], v2 = [1, 2, 3] si

    v3 = v1 + v2 = [2, 2, 4] este liniar dependenta n R3 deoarece

    1v1 + 1v2 + (1)v3 = v1 + v2 v3 = 0.(2) Lista [e1, e2, e3]

    t cu vectorii e1 = [1, 0, 0], e2 = [0, 1, 0], e3 = [0, 0, 1] esteliniar independenta n R3.

    Se spune ca lista de vectori [w1, w2, . . . , wm]t V m1 este o sublista a listei

    [v1, v2, . . . , vn]t V n1 daca {w1, w2, . . . , wm} {v1, v2, . . . , vn}. Cu alte cu-

    vinte [w1, w2, . . . , wm]t = [vi1 , vi2 , . . . , vim ]

    t, pentru anumiti indici i1, i2, . . . , in {1, . . . , n}.Propozitie 3.2.4. Se considera w = [vi1 , vi2 , . . . , vim ]

    t V m1 o sublista a listeiv = [v1, v2, . . . , vn]

    t V n1. Daca w este liniar dependenta, atunci tot asa este siv. Echivalent, daca v este liniar independenta, atunci tot asa este si w.

    Demonstratie.

    Notatie 3.2.5. Fie v = [v1, v2, . . . , vn]t V n1 o lista de vectori. Pentru i1, i2, . . . , ik

    {1, 2, . . . , n} notam v\i1,i2,...,ik sublista care este obtinuta din v prin eliminarea vec-torilor vi1 , vi2 , . . . , vin .

    Pentru o lista de vectori v = [v1, v2, . . . , vn]t V n1 scriem simplu b =

    b1, b2, . . . , bn si vom vorbi despre supspatiul generat de respectiva lista.Propozitie 3.2.6. Fie v = [v1, v2, . . . , vn]

    t V n1 o lista de vectori. Lista v esteexact atunci liniar dependenta cand exista i {1, 2, . . . , n}, astfel ncat vi este ocombinatie liniara a vectorilor din lista v\i.

    Demonstratie.

    Corolar 3.2.7. Fie v = [v1, v2, . . . , vn]t V n1 o lista de vectori, astfel ncat

    exista i {1, 2, . . . , n}, cu proprietatea ca vi este o combinatie liniara a vectorilordin lista v\i ist. Atunci v = v\i.Demonstratie.

    Definitie 3.2.8. O submultime finita {v1, v2, . . . , vn} V se numeste liberai dacalista [v1, v2, . . . , vn]

    t V n1 este liniar independenta. O submultime oarecare (posi-bil infinita) B V se numeste libera daca fiecare submultime finita a lui B estelibera.

    Baze si coordonate.

    Definitie 3.2.9. O baza (ordonata) a unui K-spatiu vectorial V este o lista devectori b = [b1, b2, . . . , bn]

    t V n1 astfel ncat b este liniar independenta si b = Vgilt (i. e. vactorii din aceasta lista genereaza V ).

  • ALGEBRA PENTRU INFORMATICA 41

    Observatie 3.2.10. (a) Adesea suntem interesati de baze care nu sunt ordonate,ceea ce nseamna submultimi

    {b1, b2, . . . , bn} Vastfel ncat [b1, b2, . . . , bn]

    t este o baza (ordonata) n sensul Definitiei 3.2.9.(b) Cazul unei baze cu (posibil) o infinitate de elemente este de asemenea ad-

    mis, chiar daca noi nu l vom studi. O baza a unui spatiu vectorial V este osumbultime B V astfel ncat B este libera si B = V .

    Exemplu 3.2.11. Lista e = [e1, e2, . . . , en]t unde e1 = [1, 0, . . . , 0] Kn, e2 =

    [0, 1, . . . , 0] Kn, . . ., en = [0, 0, . . . , 1] Kn este o baza pentru Kn. Aceasta bazase numeste baza canonica a lui Kn. Baza canonica se poate scrie cu ajutorul asanumitelor simboluri lui Kronecker:

    ei = [i,j ]1jn Kn, unde i,j ={

    1 daca i = j

    0 daca i 6= j pentru orice i {1, . . . , n}.

    Propozitie 3.2.12. Fie V un K-spatiu vectorial si b = [b1, b2, . . . , bn]t V n1.

    Urmatoarele afirmatii sunt echivalente:

    (i) b este o lista de vectori maximal liniar independenta, i. e. b este liniarindependenta si pentru orice x V lista b = [b1, b2, . . . , bn, x] nu mai areaceeasi proprietate.

    (ii) b este o lista minimala cu proprietatea ca genereaza V , i. e. b = V sipentru oricare i {1, . . . , n}, avem b\i 6= V .

    (iii) b este o baza a lui V .

    Demonstratie.

    Definitie 3.2.13. Un K-spatiu vectorial V se numeste finit generat daca exsita osubmultime finita {b1, b2, . . . , bn} V astfel ncat b1, b2, . . . , bn = V .Corolar 3.2.14. Orice spatiu vectorial finit generat are o baza.

    Demonstratie.

    Observatie 3.2.15. Aici si n ce urmeaza, vom considera numai spatii vectorialefinit generate. Totusi multe rezultate (de ex. Corolarul 3.2.14, Teorema 3.2.24,Corolarul 3.2.19 etc.) sunt valabile sau au un analog si n cazul spatiilor vectorialecare nu sunt finit generate.

    Propozitie 3.2.16. Fie V un K-spatiu vectorial si b = [b1, b2, . . . , bn]t V n1.

    Urmatoarele afirmatii sunt echivalente:

    (i) b este o baza a lui V .(ii) Pentru orice vector x V exista un unic sistem de scalari

    = [1, . . . , n] Kn astfel ncat x = b = 1b1 + 2b2 + . . .+ nbn.Demonstratie.

    Definitie 3.2.17. Fie V un K-spatiu vectorial si b = [b1, b2, . . . , bn]t V n1.

    Numim coordonatele unui vector x V n raport cu b scalari unic determinati[1, . . . , n] cu proprietatea x = 1b1 + . . .+ nbn.

  • 42 GEORGE CIPRIAN MODOI

    Dimensiune unui spatiu vectorial.

    Lema 3.2.18. (Lema lui Steinitz) Se considera doua liste de vectori v = [v1, v2, . . . , vn]t

    V n1 si w = [w1, w2, . . . , wm]t V m1 ntr-un K-spatiu vectorial V , unde n,m N. Daca v este liniar independenta si w = V , atunci avem n m si, dupa oeventuala renumerotare, v1, . . . , vn, wn+1, . . . , wm = V.Demonstratie. Corolar 3.2.19. Oricare doua baze ale unui K-spatiu vectoriales (finit generat) auacelasi numar de elemente.

    Demonstratie. Definitie 3.2.20. Prin definitie dimensiunea unui K-spatiu vectorial (finit gen-erat) V este numarul elementelor unei baze a (prin urmare a tuturor bazelor) luiV . Se scrie dimK V sau simplu dimV . De acum nu vom mai vorbi despre spatiifinit generate, si vom folosi notiunea echivlenta (dar mai eleganta) de spatii finitdimensionale.

    Exemplu 3.2.21. (1) dim 0 = 0.(2) dimK K

    n = n; n particular dimR R = 1, dimR R2 = 2, dimR R3 = 3

    Observatie 3.2.22. Urmatoarele afirmatii sunt adevu arate ntr-un spatiu finitdimensional:

    (a) Orice lista liniar independenta se poate completa pana la o baza.(b) Din orice lista care generaza pe V se poate extrage o baza.(c) dimV ieste cel mai mare numare de vectori liniar independenti care exista n

    V .(d) dimV este cel mai mic numar de lemente a unel liste care genereaza V .

    Propozitie 3.2.23. Fie V un K-spatiu vectorial cu dimK V = n si b = [b1, b2, . . . , bn] V n1 o lista de vectori. Urmatoarele afirmatii sunt echivalente:

    (i) b este liniear independenta.(ii) b = V .

    (iii) b este o baza.

    Demonstratie. Proprietatea de universalitate a bazei unui spatiu vectorial.

    Teorema 3.2.24. [Proprietatea de universalitate a bazei] Fie V si W doua K-spatii vectoriale si v = [v1, v2, . . . , vn]

    t V n1 o baza a lui V . Pentru orice functief : {v1, v2, . . . , vn} W exista o aplicatie liniara unica f : V W astfel ncatf(vi) = f(vi) pentru orice 1 i n (i. e. f prelungeste pe f sau f este o restrictiea lui f).

    Demonstratie. Corolar 3.2.25. Fie V si W doua K-spatii vectoriale si v = [v1, v2, . . . , vn]

    t V n1 o baza a lui V .(a) Daca f, g : V W sunt aplicatii liniare astfel ncat f(vi) = g(vi) pentru orice

    1 i n, atunci f = g.(b) Daca dimKW = n atunci V = W .(c) V = Kn.

  • ALGEBRA PENTRU INFORMATICA 43

    Formule legate de dimensiune.

    Propozitie 3.2.26. Se considera un K-spatiu vectorial V si S, T K doua subspatii.Avem:

    dimS + dimT = dim(S + T ) dim(S T ).Demonstratie.

    Corolar 3.2.27. Daca V este un K-spatiu vectorial finit dimensional si S K V ,atunci dimS dimV . Mai mult, dimS = dimV ddaca S = V .Demonstratie.

    Propozitie 3.2.28. Fie f : V W o aplicatie liniara ntre doua K-spatii vecto-riale V si W . Atunci:

    dimV = dim Kerf + dim Imf.

    Demonstratie.

    Corolar 3.2.29. Fie V si W doua K-spatii vectoriale cu dimV = dimW si f :V W o aplicatie liniara. eine lineare Abbildung. Urmatoarele afirmatii suntechivalente:

    (i) f ist injectiva.(ii) f ist surjectiva.

    (iii) f ist bijectiva.

    Demonstratie.

    Lema substitutiei.

    Teorema 3.2.30. (Lema substitutiei) Fie b = [b1, b2, . . . , bn]t o baza a K-spatiului

    vectorial V si v V cu coordonatele [1, 2 . . . , n] n raport cu baza b (i. e.v = 1b1 + 2b2 + . . .+ nbn). Consideram lista de vectori v

    = [b1, . . . , v, . . . , bn]care rezulta din v prin nlocuirea (substitutia) vectorului bi cu v. Atunci:

    (a) b este o bazddaca i 6= 0.(b) Daca b este o bazasi x V are coordonatele [x1, x2 . . . , xn] n raport cu v si

    [x1, x2 . . . , x

    n] n raport cu v

    atunci:{xi =

    1i xi

    xj = 1i (ixj jxi) pentru j 6= i

    .

    Demonstratie.

    Definitie 3.2.31. Se numeste rangul unei liste de vectori n v = [v1, . . . , vn]t di-

    mensiunea spatiului generat de v, i. e. rank v = dimv.Observatie 3.2.32. Deoarece orice lista liniar independenta se poate completapana la o baza, se poate folosi lema substitutiei pentru a calcula rangul unei listede vectori.

  • 44 GEORGE CIPRIAN MODOI

    Exercitii la Baze.

    Exercitiu 3.2.33. Sa se arate ca o lista cu doi vectori [x, y]t V 21 este exactatunci liniar dependenta cand exista K astfel ncat x = y sau y = x. Sa segaseasca interpretarea geometrica n cazul K = R, si V = R3. Cand este o lista devectori [x, y, z]t (R3)31 liniar dependenta?Exercitiu 3.2.34. Fie V unK-spatiu vectorial cu dimV = n. Sa se arate ca