algebra pentru 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 443.3. Aplicatii liniare si matrici 45Matricea unei liste de vectori 45Matricea unei aplicatii liniare 46Exercitii la Aplicatii liniare si matrici 473.4. Diagonalizarea unui endomorfism de spatii vectoriale 47Ideea algoritmului Page Ranking 49Exercitii la Diagonalizare 49

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.


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:


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:

A×B = {(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}}.


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

A1 ×A2 × . . . An−1 ×An = (A1 ×A2 × . . . An−1)×An.Pentru o multime A avem A1 = A si An = An−1 ×A, pentru orice n > 1.

Exercitii la Multimi.

Exercitiu 1.2.16. Sa se determine A ∪B, A ∩B, A \B, CN(A), A×B, unde

A = {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 Af→ B. Pentru a ∈ A se noteazaa f(a) unicul

element 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 (pentru

aceeasi functie): Printr-un tabel:x 1 2 3

f(x) a a bsau 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.


(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

f−1(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→ Ch→ 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 f−1 aceastafunctie si o numim inversa functiei f . De asemenea avem (f−1)−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 asaeste si g ◦ f ; mai mult avem (g ◦ f)−1 = f−1 ◦ g−1.

Demonstratie. �


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 atuncif ◦ 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 atuncik1 ◦ 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. �


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∗ asaıncat 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. �


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:∏

i∈IAi =

{f : I →

⋃i∈I

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 =∏i∈I

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 →

⋃i∈I Ai asa

ıncat 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∗ : A×A→ A. Adesea se scrie a ∗ b ın loc de ∗(a, b).

Definitie 1.3.30. O operattie ∗ : A×A→ 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 ∗ : A×A→ A are un element neutru, atunciel este unic.

Demonstratie. �

Propozitie 1.3.32. Se considera o operatie asociativa ∗ : A×A→ A care are unelement neutru e.

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

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

Demonstratie. �

Definitie 1.3.33. Un monoid este o pereche (structura) (M, ∗) care consista dintr-omultime M ımpreuna cu o operatie asociativa ∗ : M×M →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 .


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 ≤ 0−x+ 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 prinf−1(Y ) putem ıntelege fie contraimaginea lui Y prin f sau imaginea Y prin f−1.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 asaıncat 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 : A→B, 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.


(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 ⊆ f−1(f(X)).(2) f(X1 ∪X2) = f(X1) ∪ f(X2).(3) f(X1 ∩X2) ⊆ f(X1) ∩ f(X2).(4) f(f−1(Y ) ⊆ Y .(5) f−1(Y1 ∪ Y2) = f−1(Y1) ∪ f−1(Y2).(6) f−1(Y1 ∩ Y2) = f−1(Y1) ∩ f−1(Y2).

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

(i) f este injectiva.(ii) X = f−1(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(f−1(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!

(m−n)! .

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!(m−n)! .

Exercitiu 1.3.52. Sa se arate ca∑ni=0

(mi

)= 2m.


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

|A1 ∪A2 ∪ . . . ∪An| =∑

1≤i≤n

|Ai| −∑

1≤i<j≤n

|Ai ∩Aj |+∑

1≤i<j<k≤n

|Ai ∩Aj ∩Ak|

− . . .+ (−1)n−1|A1 ∩A2 ∩ . . . ∩An|.

|A1 ∩A2 ∩ . . . ∩An| =∑

1≤i≤n

|Ai| −∑

1≤i<j≤n

|Ai ∪Aj |+∑

1≤i<j<k≤n

|Ai ∪Aj ∪Ak|

− . . .+ (−1)n−1|A1 ∪A2 ∪ . . . ∪An|.

Exercitiu 1.3.54. Fie A si B multimi, cu |A| = n si |B| = m. Sa se gaseascanumarul tuturor functiilor surjective f : A→ B.

Exercitiu 1.3.55. Sa se arate ca multimile N, Z, Q au acelasi cardinal.

Exercitiu 1.3.56. Sa se arate ca multimile N si R nu au acelasi cardinal. Indicatie:Se arata ca |R| = |P(N)|.

Exercitiu 1.3.57. Fie A o multime finita cu |A| = n.

(1) Cate operatii se pot defini pe A?(2) Cate dintre ele sunt comutative?(3) Cate dintre ele au un element neutru?

Exercitiu 1.3.58. Se considera operatia ∗ : R × R → R, data prin x ∗ y = xy +2ax+by, pentru orice x, y ∈ R. Sa se determine a, b ∈ R, asa ıncat ∗ sa fie asociativasi comutativa.

Exercitiu 1.3.59. Fie A o multime (numita alfabet), si fie W = W (A) =⋃n∈NA

n

(multimea tuturor cuvintelor peste A). Aici A0 = {λ}, unde λ este cuvantul vid siAn = {x1x2 . . . xn | x1, x2, . . . , xn ∈ A}. Ca o exceptie de la regula generala vomnota ın acest context x1x2 . . . xn si nu (x1, x2, . . . , xn) un element din An, asadarAn este multimea tuturor cuvintelor de lungime n. Sa se arate ca (W, ·) este unmonoid, unde

(x1x2 . . . xn) · (y1y2 . . . ym) = x1x2 . . . xny1y2 . . . ym ∈ An+m

este concatenarea (juxtapunerea) cuvintelor. Cum A1 = A, putem privi A ca osubmultime a lui W . Sa se arate ca (W, ·) este monoidul liber peste A, ceea ceınseamna ca pentru orice monoid (M, ∗) si pentru orice functie f : A→ M , existaun unic homomorfism de monoizi f : W →M , asa ıncat f |A = f .

1.4. Relatii.

Definitie 1.4.1. O relatie este un triplet (A,B,R), unde A si B sunt doua multimioarecare, iar R ⊆ A × B. Uneori notam r = (A,B,R) si scriem arb ın loc de(a, b) ∈ R, alteori scriem numai R ⊆ A × B pentru a desemna o relatie. Ca siın cazul functiilor A si B se numesc domeniu respectiv codomeniu. Daca A = Batunci relatia R ⊆ A×A se zice omogena (pe A).

Observatie 1.4.2. Funtiile pot fi privite ca fiind cazuri speciale de relatii, si anumeo functie f : A → B este o relatie f = (A,B, F ) cu prprietatea suplimentara ca

pentru orice x ∈ A exista un singur element y ∈ B asa ıncat xfy. In acest cazF = {(a, f(a)) | a ∈ A este graficul functiei f .


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|(x−y).(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) ∈ Mm×n({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 Mm×n({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 aflaın 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,R−1), unde (b, a) ∈ R−1 ddaca (a, b) ∈ R pentru orice pereche (a, b) ∈ A×B.

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.


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 r−1(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(r−1)(Y ) = r−1(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 caıntr-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= ∅.


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

⋃x∈A[x] = A.

Demonstratie. �

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

(a) ∅ /∈ π.(b) Pentru X,Y ∈ π daca X ∩ Y 6= ∅ atunci X = Y .(c)

⋃X∈πX = 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 π ⊆ P(A) este o partitie a lui A, atunci (A,A,≡π) este o relatie deechivalenta, unde pentru orice a, b ∈ A avem

a ≡π b ddaca exista X ∈ π 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 multime

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


mai mic element ın (A,≤) ddaca a este maximal, respectiv cel mai mare elementın (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 ≥ a2

ldots 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 x∨y = sup{x, y}si x∧y = inf{x, y}. Laticea L se zice completa daca exista inf(X) si sup(X) pentruorice submultime X ∈ L.


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 asaıncat 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 r◦δA = r = δB ◦r, adica relatia de egalitate actioneaza ca elemetneutru pentru compunerea relatiilor.

(2) Sa se arate ca relatia inversa r−1 = (B,A,R−1) nu este ın mod necesar inversaır aport cu compunerea relatiilor, adica sa se construiasca un exemplu de relatiar asa ıncat r−1 ◦ 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) ∈ Mm×n({0, 1}) si M(s) ∈ Mn×p({0, 1}).Sa se determine M(r−1) 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(r−1), 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 = cb

este o echivalenta pe Z× Z∗ si sa se determine multimea factor

(Z× Z∗)/∼.


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) =x

2pentru orice x ∈ Z,

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

xpentru orice x ∈ Z?

Exercitiu 1.4.41. Consideram multimea Q = (Z× Z∗)/∼ ca ın Exercitiul 1.4.39.Sa se arate ca +, · : Q×Q→ 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 ∩ r−1 unde x(r ∩ r−1)y ddaca xry si yrx este o relatie de echivalenta pe Asi pe multimea factor A/(r∩r−1) 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?


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 Gımpreuna cu o operatie · : G×G→ 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) (Mm×n(Z),+), (Mm×n(Q),+), (Mm×n(R),+), (Mm×n(C),+)

Exemplu 2.1.3. Urmatoarele perechi sunt monoizi dar nu grupuri:

(a) (N,+), (N, ·).(b) (Z, ·), (Q, ·), (R, ·), (C, ·).(c) (Mn×n(Z), ·), (Mn×n(Q), ·), (Mn×n(R), ·), (Mn×n(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 x−1 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 | ∃x−1 ∈M astfel ıncat xx−1 = 1 = x−1x}.

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.


(2) Fie K ∈ {Q,R,C} si n ∈ N∗. Multimea GLn(K) = {A ∈ Mn×n(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 ⇒ x−1 ∈ H.

(iii) (a) 1 ∈ H.(b) x, y ∈ H ⇒ xy−1 ∈ H.

Demonstratie. �

Propozitie 2.1.10. Fie (G, ·) un grup. Daca Hi ≤ G, cu i ∈ I, atunci⋂i∈I 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

.

(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 ∪X−1},unde X−1 = {x−1 | x ∈ X}. Aceasta ınseamna ca grupul generat de X continetoate elementele erzedin G care se pot scrie ca un produs finit de elemente dinX ∪X−1.

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

x−1x−1 . . . x−1 (−n ori) daca n < 0

Daca 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 < 0

Corolar 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 care

este 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(x−1) = 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}.

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 finit

daca 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 2π

3 + i sin 2π3

)= 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 α : G×A→ 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 G×A→ 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.

(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) = i

pentru i /∈ {i1, i2, . . . , ik}. In acest caz {i1, i2, . . . , ik} este singura orbitanetriviala a lui σ si notam σ = (i1i2, . . . , ik).


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), . . . , σk−1(i)}.

Demonstratie. �

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

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 cazulın 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(∏

i∈I G, ·)

esteun grup, unde

(xi)i∈I · (yi)i∈I = (xiyi)i∈I pentru orice (xi)i∈I , (yi)i∈I ∈∏i∈I

Gi.

Sa se arate de asemenea ca pj :∏i∈I → Gj , pj(xi)i∈I = xj este un homomorfism

surjectiv pentru orice j ∈ I.


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 si

f(A1A2 . . . An) = A1A2 . . . An}.

Notam cu s rotatia ın jurul centrului O cu 2πn radiani, (de la A1 catre A2) si cu t

simetria 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 = sn−1t.(3) Dn = {1, s, . . . , sn−1, t, st, . . . , sn−1t}(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 ca

Un = {x ∈ C∗ | exista n ∈ N astfel ıncat xn = 1}

este un subgrup a grupului (C∗, ·) si ca Un este ciclic. Sa se gaseasca un izomorfismıntre (Zn,+) si (Un, ·).


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(x−1) = 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 (Z4×Z2,+) (pentru grupul

produs 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 =

⋂x∈A 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:


(a) Sa se defineasca o actiune netriviala a lui H pe N , (adica · : H ×N → N) asaıncat 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) ε(σ) =∏

1≤i<j≤nσ(j)−σ(i)

j−i pentru orice σ ∈ Sn.

(b) ε : Sn → {1,−1} = U2 (vezi Exertiul 2.1.56) este un homomorfism.(c) Kerε = An, unde An = {σ ∈ Sn | σ este para}.

Exercitiu 2.1.77. Un ciclu de lungime k este exact atunci o permutare para cand keste un numar impar. Orice permutare (im)para se scrie ca un produs al unui numar(im)par de transpozitii, dar aceasta descompunere nu mai este unica. Reamintiimca o transpozitie este un ciclu de lungime 2.

Exercitiu 2.1.78. Fie σ ∈ Sn un ciclu de lungime l. Sa se arate:

(a) Daca l = 2k + 1 este impar, atunci σ2 este un ciclu de lungime l.(b) Daca l = 2k este par, atunci σ2 este un produs de doua cicluri disjuncte

amandoua de lungime k.(c) ord(σ) = l.

Exercitiu 2.1.79. Sa se arate ca (12)(3456) ∈ S6 este o permutare para care nueste patratul nici unei alte permutari din S6.

2.2. Inele si corpuri.

Definitie 2.2.1. Un inel este un triplet (R,+, ·), care constaa dintr-o multime Rımpreuna cu doua operatii +, · : R×R→ R, astfel ıncat

(a) (R,+) este un grup abelian.(b) · este asociativa.


(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 (Mn×n(R),+, ·) este de asemenea inel;totusi (Mn×n(R),+, ·) nu este ın mod necesar comutativ. Daca R este unitaraunci to asa este si (Mn×n(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


(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 avem⋂i∈I 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∗ ⇒ x−1 ∈ L

(iii) (a) 0, 1 ∈ L.(b) x, y ∈ L⇒ x− y ∈ L.(c) x, y ∈ L∗ ⇒ xy−1 ∈ 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).


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 astfelıncat 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 trivialal 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.


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 → RA

prin 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 Exercitiul

Ubung 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′+ b′i+ c′j + d′k) = (a+ a′) + (b+ b′)i+ (c+ c′)j + (d+ d′)k

(a+ bi+ cj + dk)(a′ + b′i+ c′j + d′k) = (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].


Exercitiu 2.2.37. Sa se determine toate subinelele lui (Z,+, ·).

Exercitiu 2.2.38. Fie n ∈ N, n ≥ 2. Sa se arate ca Z×n = {[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 b−b a

]| a, b ∈ Z

}este un subiel al lui (M2×2(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 ineleleMn×n(R) si Mn×n(R)o sunt izomorfe. De aici sa se deduca echivalenta urmatoarelorafirmatii, pentru orice A ∈Mn×n(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 M2×2(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.


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 · : K×V → 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) Mm×n(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) siınmultirea 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. �


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

⋂i∈I 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〉 = 〈X〉K =⋂

X⊆U≤KV

U.

Daca X = {x1, x2, . . . , xn} este o multime finita, scriem 〈x1, x2, . . . , xn〉K ı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) 〈X〉K ≤K V .(b) X ⊆ 〈X〉K si X = 〈X〉K ddaca X ≤K V .(c) 〈X〉K este cel mai mic subspatiu a lui V care contine X i. e.

U = 〈X〉K ddaca

U ≤K V

X ⊆ Udaca W ≤K V astfel ıncat X ⊆W atunci U ≤K W

.

(d) Daca X ⊆ Y ⊆ G atunci 〈X〉K ≤ 〈Y 〉K ≤ V .

Demonstratie. �

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

〈X〉K = {α1x1+α2x2+. . .+αnxn | n ∈ N, x1, x2, . . . , xn ∈ X si α1, α2, . . . , αn ∈ K}.


In particular, pentru X = {x1, x2, . . . , xn} avem:

〈x1, x2, . . . , xn〉K = {α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 〈x〉K = {αx | α ∈ K}.(b) Pentru x, y ∈ V avem 〈x, y〉K = {α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 interesatiındeosebi 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 .


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


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 = 5√x5 + y5, pentru orice x, y ∈ R,

� : R× R→ R, α� x = α 5√αx pentru orice α, x ∈ R

definesc 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 | x2

1 + 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 | x1−x2−x3 = 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 ∈ M2×2(R) | α ∈ R} si T = {A ∈M2×2(R) | Tr(A) = 0}, unde Tr(A) este suma intrarilor de pe diagonala principalaa matricii A. Sa se arate ca S, T ≤R M2×2(R) si S ⊕ T = M2×2(R).


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] = x2

1 − 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 n×1, 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 scalariiα1, α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 n×1 ın loc de[v1, v2, . . . , vn] ∈ V n.

(2) Lista vida de vectori este admisa (pentru n = 0). In particular lista vidaeste 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 n×1 contine vectorul nul vi = 0, atunci eaeste liniar dependenta, deoarece

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


(5) Daca lista [v1, v2, . . . , vn]t ∈ V n×1 contine doi vectori egali vi = vj cu i 6= jatunci 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] siv3 = 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 m×1 este o sublista a listei[v1, v2, . . . , vn]t ∈ V n×1 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 m×1 o sublista a listeiv = [v1, v2, . . . , vn]t ∈ V n×1. 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 n×1 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 n×1 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 n×1 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 n×1 o lista de vectori, astfel ıncatexista 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 n×1 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 n×1 astfel ıncat b este liniar independenta si 〈b〉 = Vgilt (i. e. vactorii din aceasta lista genereaza V ).


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

{b1, b2, . . . , bn} ⊆ V

astfel ı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 ]1≤j≤n ∈ Kn, unde δi,j =

{1 daca i = j

0 daca i 6= jpentru orice i ∈ {1, . . . , n}.

Propozitie 3.2.12. Fie V un K-spatiu vectorial si b = [b1, b2, . . . , bn]t ∈ V n×1.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 n×1.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 n×1.Numim coordonatele unui vector x ∈ V ın raport cu b scalari unic determinati[α1, . . . , αn] cu proprietatea x = α1b1 + . . .+ αnbn.


Dimensiune unui spatiu vectorial.

Lema 3.2.18. (Lema lui Steinitz) Se considera doua liste de vectori v = [v1, v2, . . . , vn]t ∈V n×1 si w = [w1, w2, . . . , wm]t ∈ V m×1 ı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 n×1 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 n×1 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 n×1 o baza a lui V .

(a) Daca f, g : V →W sunt aplicatii liniare astfel ıncat f(vi) = g(vi) pentru orice1 ≤ i ≤ n, atunci f = g.

(b) Daca dimKW = n atunci V ∼= W .(c) V ∼= Kn.


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-spatiuluivectorial 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

[x′1, x′2 . . . , x

′n] ın raport cu v′ atunci:{

x′i = α−1i xi

x′j = α−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 = dim〈v〉.

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.


Exercitii la Baze.

Exercitiu 3.2.33. Sa se arate ca o lista cu doi vectori [x, y]t ∈ V 2×1 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)3×1 liniar dependenta?

Exercitiu 3.2.34. Fie V unK-spatiu vectorial cu dimV = n. Sa se arate ca pentruorice numar natural m ≤ n exista un subspatiu S ≤K V astfel ıncat dimS = m.

Exercitiu 3.2.35. Fie f : V → W o aplicatie liniara si X ⊆ V . Sa se arate caf(〈X〉) = 〈f(X)〉.

Exercitiu 3.2.36. Sa se arate ca Q+Q√

2 = {a+b√

2 | a, b ∈ Q} este un Q-spatiuvectorial si sa se determine o baza si demensiunea.

Exercitiu 3.2.37. Fie p un numar prim. Sa se arate ca

Q + Q 3√p+ Q 3

√p2 = {a+ b 3

√p+ 3

√p2 | a, b, c ∈ Q}

este un Q-spatiu vectorial si sa se determine o baza si demensiunea.

Exercitiu 3.2.38. Fie f : V →W o aplicatie liniara si v = [v1, . . . , vn]t ∈ V n×1 olista de vectori. Notam f(v) = [f(v1), . . . , f(vn)]t ∈Wn×1. Atunci:

(a) daca f este injectiv si v este liniar independentaatunci f(v) are aceeasi propri-etate.

(b) Daca f este surjectiv si 〈v〉 = V , atunci 〈f(v)〉 = W .(c) Daca f este bijectiv si v este o baza a lui V atunci f(v) este de asemenea o

baza (a lui W ).

Exercitiu 3.2.39. Pentru un K-spatiu vectorial V cu dimV = n si S ≤K V , sase arate ca exista T ≤K V astfel ıncat S ⊕ T = V .

Exercitiu 3.2.40. Se considera ın R3 lista de vectori v = [v1, v2, v3]t. Folosinddoua metode (definitia bazei respectiv lema substitutiei) sa se gaseasca a ∈ R astfelıncat v este o baza a lui R3, unde:

(1) v1 = [1,−2, 0], v2 = [2, 1, 1], v3 = [0, a, 1].(2) v1 = [2, 1,−1], v2 = [0, 3,−1], v3 = [1, a, 1].

Exercitiu 3.2.41. Sa se arate ca b = [b1, b2, b3, b4]t unde

b1 = [1, 2,−1, 2], b2 = [1, 2, 1, 4], b3 = [2, 3, 0,−1], b4 = [1, 3,−1, 0]

este o baza a lui R4 si sa se determine coordonatele lui x = [2, 3, 2, 10] ın raport cuacea baza.

Exercitiu 3.2.42. Sa se determine a ∈ R astfel ıncat lista v = [v1, v2, v3]t este obaza a lui R3, unde:

v1 = (a, 1, 1), v2 = (1, a, 1), v3 = (1, 1, a).

Exercitiu 3.2.43. Sa se determine rangul listelor de vectori din R4:

(1) [[0, 1, 3, 2], [1, 0, 5, 1], [−1, 0, 1, 1], [3,−1,−3,−4], [2, 0, 1,−1]]t;(2) [1, 2, 3, 0], [0, 1,−1, 1], [3, 7, 8, 1], [1, 3, 2, 1]]t;(3) [[1, 2,−1, 2], [2, 3, 0,−1], [2, 4, 0, 6], [1, 2, 1, 4], [3, 6,−1,−1], [1, 3,−1, 0]]t.


Exercitiu 3.2.44. Se considera subspatiile

S = 〈[2, 0, 1,−1], [0, 1, 2, 3], [−1, 0, 1, 1], [1, 1, 5, 2]〉

T = 〈[1, 0, 2, 0], [2, 1,−1, 2], [−1,−1, 3,−2]〉ale spatiului vectorial real R4. Sa se foloseasca lema substitutiei pentru a determinadimensiunea si cate o baza ın subspatiile S, T , S + T si S ∩ T .

Exercitiu 3.2.45. Folosind lema substitutiei sa se calculeze dimensiunea si cate obaza a subspatiilor Kerf si Imf , ın cazurile:

(1) f : R3 → R3 f [x1, x2, x3] = [x1 + 2x2, x2 + x3, x1 − 2x3].(2) f : R4 → R3 f [x1, x2, x3, x4] = [x1 − x2 − x3, 3x2 + x4, 3x1 − 3x3 + x4](3) f : R3 → R2 f [x1, x2, x3] = [−x1 + 2x2, x1 − x2 + x3, x2 + 2x3].(4) f : R2 → R3 f [x1, x2] = [x1 − 3x2, 2x1,−x1 + x2].(5) f : R4 → R4

f [x1, x2, x3, x4] = [x1 + 2x2 +x3−x4, x1 + 2x2−x3 +x4, x1 + 2x2, x3−x4].

3.3. Aplicatii liniare si matrici.

Matricea unei liste de vectori. In cele ce urmeaza se considera un K-spatiuvectorial V cu dimK V = n. Reamintim ca daca b = [b1, b2, . . . , bn]t o baza a luiV si x ∈ V , atunci coordonatele lui x ın baza b sunt scalarii unic determinati[x1, x2, . . . , xn] ∈ Kn cu proprietatea

x = x1b1 + x2b2 + . . .+ xnbn = [x1, x2, . . . , xn][b1, b2, . . . , bn]t.

Notam [x]b = [x1, x2, . . . , xn] si egalitatea de mai sus se scrie x = [x]bb.

Definitie 3.3.1. Fie V unK-spatiu vectorial cu dimK V = n. Fie b = [b1, b2, . . . , bn]t

o baza a lui V si x ∈ V . Coordonatele lui x ın baza b sunt scalarii v = [v1, v2, . . . , vm]t

un sistem de vectori. Prin matricea listei v ın baza b se ıntelege:

[v]b = [[v1]b, [v2]b, . . . , [vm]b]t ∈Mm×n(K).

Cu alte cuvinte

[v]b =

[v1]b[v2]b

...[vm]b

=

a11 a12 . . . a1n

a21 a22 . . . a2n

......

......

am1 am2 . . . amn

unde vi = ai1b1 + ai2b2 + . . .+ ainbn pentru 1 ≤ i ≤ m.

Propozitie 3.3.2. Fie V un K-spatiu vectorial cu dimK V = n. Fie e = [e1, e2, . . . , en]t

o baza si fie b = [b1, b2, . . . , bn] un sistem de vectori ın V . Atunci b este baza ddaca[b]e ∈ GLn(K) (adica [b]e este inversabila), si ın acest caz pentru x ∈ V avem

[x]b = [x]e[b]−1e .

In particular avem [e]b = [b]−1e .

Demonstratie. �

Observatie 3.3.3. Daca e = [e1, e2, . . . , en]t si b = [b1, b2, . . . , bn] sunt baze, iarv = [v1, v2, . . . , vm] este un sistem de vectori ın V atunci

[v]b = [v]e[b]−1e .


Observatie 3.3.4. Daca v = [v1, v2, . . . , vm]t este un sistem de vectori iar b =[b1, b2, . . . , bm]t este o baza a K-spatiului vectorial V atunci:

rank v = rank[v]b.

Matricea unei aplicatii liniare.

Definitie 3.3.5. Se considera K-spatiile vectoriale V si W cu dimK V = m sidimKW = n. Prin matricea unei aplicatii liniare f ∈ HomK(V,M) ın raportcu perechea de baze v = [v1, v2, . . . , vm] a lui V si w = [w1, w2, . . . , wn] a lui Wıntelegem

[f ]v,w = [f(v)]w ∈Mm×n(K),

unde prin f(v) am notat sistemul de vectori [f(v1), f(v2), . . . , f(vm)]t ın W . Cualte cuvinte

[f ]v,w =

[f(v1)]w[f(v2)]w

...[f(vm)]w

=

a11 a12 . . . a1n

a21 a22 . . . a2n

......

......

am1 am2 . . . amn

unde f(vi) = ai1w1 + ai2w2 + . . .+ ainwn pentru 1 ≤ i ≤ m.

Propozitie 3.3.6. Se considera K-spatiile vectoriale V , W si U cu dimK V =m, dimKW = n si dimK U = p, ımpreuna cu bazele v = [v1, v2, . . . , vm], w =[w1, w2, . . . , wn] si u = [u1, u2, . . . , up] ın V , W , respectiv U . Daca α ∈ K, f, f ∈HomK(V,W ) si g ∈ HomK(W,U) atunci avem:

(a) [f + f ′]v,w = [f ]v,w + [f ′]v,w.(b) [αf ]v,w = α[f ]v,w.(c) [g ◦ f ]v,u = [f ]v,w · [g]w,u.

Demonstratie. �

Teorema 3.3.7. Se considera K-spatiile vectoriale V si W cu dimK V = m,dimKW = n, ımpreuna cu bazele v = [v1, v2, . . . , vm] si w = [w1, w2, . . . , wn].Atunci

(a) Aplicatia ϕ : HomK(V,W )→ Mm×n(K), ϕ(f) = [f ]v,w este un izomorfism despatii vectoriale.

(b) Aplicatia ϕ : EndK(V ) → Mm×n(K)o, ϕ(f) = [f ]v,v este un izomorfism deinele.

Demonstratie. �

Observatie 3.3.8. Pentru f ∈ EndK(V ) vom nota uneori [f ]v = [f ]v,v (ca siMn(K) ın loc de Mn×n(K)).

Teorema 3.3.9 (Formula schimbarii de baza). Se considera K-spatiile vectorialeV si W cu dimK V = m, dimKW = n, ımpreuna cu bazele v = [v1, v2, . . . , vm],v′ = [v′1, v

′2, . . . , v

′m] ın V si w = [w1, w2, . . . , wn], w′ = [w′1, w

′2, . . . , w

′n] ın W .

Daca f ∈ HomK(V,W ) atunci avem

[f ]v′w′ = [v′]v · [f ]v,w · [w′]−1w .

Demonstratie. �


Exercitii la Aplicatii liniare si matrici.

Exercitiu 3.3.10. Fie f : R3 → R2, f [x1, x2, x3] = [x2,−x1] si v = [[1, 1, 0], [0, 1, 1], [1, 0, 1]]t

si w = [[1, 1], [1,−2]]t.

(a) Sa se arate ca f ∈ HomR(R3,R2).(b) Sa se arate ca v si w sunt baze ın R3, respectiv R2 si sa se determine matricile

[f ]v,e si [f ]v,w, unde e este baza canonica din R2.(c) Sa se determine dimensiunea si cate o baza ın Ker(f) si Im(f).

Exercitiu 3.3.11. Fie f : R4 → R4, f [x1, x2, x3, x4] = [x1 + 2x2 + x3 + x4, 3x1 +7x2 + 5x3 + 2x4, x1 + 3x2 + 3x3, 4x1 + 9x2 + x3 + 8x4] si e = [e1, e2, e3, e4]t bazacanonica ın R4.

(a) Sa se arate ca f ∈ EndR(R4).(b) sa se determine matricea [f ]e.(c) Sa se arate ca b = [b1, b2, b3, b4]t, unde b1 = e1, b2 = e1 + e2, b3 = e1 + e2 +

e3, b4 = e1 + e2 + e3 + e4 este o baza ın R4, si sa se determine [f ]b si [v]b undev = [1, 2,−1, 0].

(d) Sa se determine dimensiunea si cate o baza ın Ker(f) si Im(f).

3.4. Diagonalizarea unui endomorfism de spatii vectoriale. In cele ce urmeazafixam un K-spatiu vectorial V , cu dimK V = n ≥ 1, si un endomorfism f ∈EndK(V ).

Propozitie 3.4.1. Pentru orice λ ∈ K, multimea V (λ) = {x ∈ V | f(x) = λx}este un subspatiu vectorial al lui V .

Demonstratie. �

Observatie 3.4.2. Avem V (λ) = Ker(λ1V − f).

Spunem ca λ ∈ K este o valoare proprie pentru f daca ecuatia f(x) = λx are

solutii nenule in V , cu alte cuvinte daca V (λ) 6= 0. In acest caz, o solutie nenulaa acestei ecuatii, adica un vector 0 6= x ∈ V (λ) se numeste vector propriu asociatvalorii proprii λ. O matrice se zice diagonala daca este de forma

diag(λ1, λ2, . . . , λn) =

λ1 0 . . . 00 λ2 . . . 0...

......

...0 0 . . . λn

Spunem ca f este diagonalizabil daca exista o baza b a lui V astfel ıncat [f ]b estediagonala.

Teorema 3.4.3. Fie b = [b1, b2, . . . , bn]t o baza a lui V . Atunci

[f ]b = diag(λ1, λ2, . . . .λn)

ddaca λ1, λ2, . . . .λn sunt valori proprii ale lui f (nu neaparat distincte) iar bi,1 ≤ i ≤ n sunt vectori proprii corespunzatori acestor valori proprii. Asadar f ∈EndK(V ) este diagonalizabil ddaca exista o baza a lui V constituita din vectoriproprii, caz ın care matricea lui f in acesta baza are pe diagonala valorile propriirespective.

Demonstratie. �


Polinomul caracteristic al lui f este definit prin pf (t) = det(tIn − A) undeA = [f ]e este matricea lui f ıntr-o baza e a lui V .

Propozitie 3.4.4. Polinomul caracteristic al lui f nu depinde de baza ın carecalculam matricea lui f , mai precis daca e si e′ sunt baze pentryu V si A = [f ]e,A′ = [f ]e′ , atunci det(tIn −A) = det(tIn −A′).Demonstratie. �

Exemplu 3.4.5. Pentru n = 2 si [f ]e = A =

[a bc d

]avem

pf (t) =

∣∣∣∣ t− a −b−c t− d

∣∣∣∣ = t2 − (a+ d)t+ (ad− bc) = t2 − trace(A)t+ det(A).

Printr-un usor abuz de limbaj vorbim uneori de polinomul caracteristic al matriciiA = [f ]e ın loc de polinomul catacteristic al endomorfismului f si scriem pA(t) ınloc de pf (t). Acelasi lucru este valabil si pentru vectori si valori proprii.

Observatie 3.4.6. Avem:

(a) deg pf = n.(b) Daca pf (t) = p0 +p1t+ · · ·+pn−1t

n−1 +pntn atunci pn = 1, pn−1 = −trace(A),

p0 = (−1)n det(A).

Propozitie 3.4.7. λ ∈ K este valoare proprie a lui f ddaca λ este radacina apolinomului caracteristic al lui f adica pf (λ) = 0.

Demonstratie. �

Corolar 3.4.8. Endomorfismul f are cel mult n valori proprii distincte.

Numim multiplicitate algebrica a valorii proprii λ ∈ K a lui f , multiplicitatealui λ ca radacina a polinomului pf (t) si o notam cu m(λ). Numim multiplicitategeometrica a valorii proprii λ ∈ K a lui f dimensiunea d(λ) = dimV (λ).

Observatie 3.4.9. Pentru orice valoare proprie λ ∈ K a lui f avem 1 ≤ m(λ) sim(λ) este cel mai mare exponent m ∈ N cu proprietatea (t − λ)m | pf (t), adica

(t− λ)m(λ) | pf (t), iar (t− λ)m(λ)+1 - pf (t).

Propozitie 3.4.10. Pentru orice valoare proprie λ ∈ K a lui f avem

1 ≤ d(λ) ≤ m(λ).

Demonstratie. �

Lema 3.4.11. Daca λ1, λ2, . . . , λr sunt valori proprii distincte pentru f si 0 6= bi ∈V (λi), cu 1 ≤ i ≤ r, sunt vectori proprii corespunzatori, atunci b1, b2, . . . , bn suntliniar independenti.

Demonstratie. �

Teorema 3.4.12. Urmatoarele afirmatii sunt echivalente:

(i) f este diagonalizabil.(ii) f are toate valorile proprii ın K si pentru orice valoare proprie λ a lui f este

valabila egalitatea d(λ) = m(λ).

n cazul ın care f este diagonalizabil, matricea diagonala care ıl reprezinta pe f arepe diagonala valorile proprii ale lui f , fiecare valoare proprie aparand de atatea oricat ordinul ei de multiplicitate.


Demonstratie. �

Corolar 3.4.13. Daca f are n valori proprii distincte ın K atunci f este diago-nalizabil.

Ideea algoritmului Page Ranking. (Larry Page - cofondator Google).

I: Cum se masoara importanta unei pagini de internet? R: Importanta uneipagini de internet depinde de numarul de linkuri care trimit la aceea pagina, dar side importanta paginilor care trimit linkuri catre acea pagina. Intr-un anume fel opagina “mosteneste” din importanta paginilor care trimit la ea.

Consideram o retea fromata din paginile p1, p2 . . . , pn. Cautam o masura aimportantei de forma I : {p1, p2 . . . , pn} → R, care creste direct proportional cuimportanta respectivei pagini. Daca de la o pagina pi pleaca li linkuri catre paginilepj1 , pj2 , . . . , pjli atunci fiecareia dintre aceste pagini i se transfera a li-a parte dinimportanta paginii pi. Avem asadar

I(pj) =∑ I(pi)

liunde suma se face dupa toate paginile care trimit catre pj . Cu ajutorul numaruluide linkuri (care se poate determina) se construiete matricea L ∈ Mn×n(R) careare pe linia i exact li elemente egale cu 1

licorespunzatoare celor li pagini catre

care trimite pagina pi, restul elementelor de pe linie fiind 0. Se observa ca sumaelementelor de pe linia i este 1. Egalitatea de mai sus se scrie matricial

[I(p1), I(p2), . . . , I(pn)] = [I(p1), I(p2), . . . , I(pn)]L,

adica [I(p1), I(p2), . . . , I(pn)] este un vector propriu al lui L corespunzator valoriiproprii 1.

Este asdar util sa avem metode care sa determine vectorii si valorile proprii aleunei matrici!

Exercitii la Diagonalizare.

Exercitiu 3.4.14. Sa se diagonalizeze endomorfismul f (adica sa se spuna dacaf este diagonalizabil si ın caz afirmativ sa se gaseasca matricea diagonala care ılreprezinta pe f precum si baza ın care f are aceasta matrice) ın urmatoarele cazuri:

(a) f ∈ EndR(R3), f(x1, x2, x3) = (3x1 + x2,−4x1 − x2,−4x1 − 8x2 − 2x3).

(b) f ∈ EndR(R4) cu matricea (ın baza canonica) [f ]e =

0 0 0 10 0 1 00 1 0 01 0 0 0

.

(c) f ∈ EndR(R3), f(x1, x2, x3) = (x1 + 3x3, x2, 3x1 − x3). In acest caz sa secalculeze fn cu n ∈ N.

(d) f ∈ EndR(R4) cu matricea (ın baza canonica) [f ]e =

1 0 0 00 0 0 01 0 0 00 0 0 1

.

Exercitiu 3.4.15. Sa se arate ca o matrice cu proprietatea ca suma elementelorde pe fiecare linie este 1 admite valoarea proprie 1.

Exercitiu 3.4.16. Fie A ∈Mn×n(C), cu valorile proprii λ1, λ2, . . . , λn ∈ C.

(a) Sa se arate ca det(A) = 0 ddaca A are valoarea proprie λ = 0.


(b) Sa se determine valorile proprii ale matricilor Am, unde m ∈ N si A−1 (dacaaceasta matrice exista).

Exercitiu 3.4.17. Pentru o matrice A ∈ Mn×n(C), sa se arate ca urmatoareleafirmatii sunt echivalente:

(i) A este nilpotenta.(ii) pA(t) = tn.

(iii) A are o singura valoare proprie λ = 0 cu ordinul de multiplicitate m(0) = n.

Universitatea Babes-Bolyai, Facultatea de Matematica si Informatica, Str. Mihail

Kogalniceanu 1, 400084 Cluj-Napoca, RomaniaE-mail address: [email protected]

algebra pentru informatica

Documents