5/24/2018 Lectii de Algebra
1/253
1
DUMITRU BUNEAG DANA PICIU
LEC#IIde
ALGEBR$
Editura UNIVERSITARIACRAIOVA
2002
5/24/2018 Lectii de Algebra
2/253
2
5/24/2018 Lectii de Algebra
3/253
3
Referen'i (tiin'ifici:Prof.univ.dr.Constantin N*st*sescu,Universitatea Bucuresti
Membru corespondent al Academiei Romne
Prof.univ.dr. Constantin Ni'*,Universitatea Bucure(ti
2002 EUC CRAIOVA
All rights reserved. No part of this publication may be reproduce, storedin a retrieval system, or transmitted, in any forms or by any means,electronic, mechanical, photocopying, recording, or other wise, withoutthe prior written permission of the publisher.
Tehnoredactare computerizat*: Dana Piciu, Livia PopescuCopert*: Ctlin Bu#neag
Bun de tipar: 20.02.2002
Tipografia Universit&ii din Craiova, Strada, Al. Cuza, nr.13
Craiova, Romnia
Published in Romania by:
EDITURA UNIVERSITARIA CRAIOVA
Descrierea CIP a Bibliotecii Naionale
Dumitru Bu#neag (coordonator),
Lecii de Algebra527 p.; 21 cm.
Craiova Editura Universitaria 2002Bibliogr.512.54,55,56,58,553,516.62,64
ISBN 973 8043 109 8
5/24/2018 Lectii de Algebra
4/253
4
ISBN: 973 8043 109 8
5/24/2018 Lectii de Algebra
5/253
5
CUPRINS
pag.
CAPITOLUL 1: NO!IUNI PRELIMINARII. . . . . . . . . .
. . . . 1
1. Mulimi. Operaii cu mulimi. . . . . . . . . . . . . . . . . . . . . . . 1
2. Relaii binare pe o mulime. Relaii de echivalen!. . . . . . . . . . 7
3. Relaii funcionale. Noiunea de funcie. Clase de funcii. . . . . 14
4. Nucleul $i conucleul unei perechi de funcii. . . . . . . . . . . . . 32
5. Mulimi ordonate. Semilatici. Latici.. . . . . . . . . . . . . . .
. . . 35
6. Latici.distributive . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 457. Complement $i pseudocomplement ntr-o latice. Algebre
Boole. Algebre Boole generalizate. . . . . . . . . . . . . . . . . . . . . .
. . . . 508. Produsul direct (suma direct!) a unei familii de mulimi . .
. . . 569. Numere cardinale. Operaii cu numere cardinale.
Ordonarea numerelor cardinale.. . . . . . . .. . . . . . . . . . . . .
. . . 60
10. Mulimi num!rabile. Mulimi finite $i mulimi infinite. . .
. . . 66
CAPITOLUL 2: GRUPURI. . . . . . . . . . . . . . . . . . . . .
. . . .711. Operaii algebrice. Monoizi. Morfisme de monoizi. Produse directe
finite de monoizi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2. Grup. Calcule ntr-un grup. Subgrup. Subgrup generat de omulime. Grup ciclic. Ordinul unui element ntr-un grup. . . . . . . . .83
5/24/2018 Lectii de Algebra
6/253
6
3. Centralizatorul unui element ntr-un grup. Centrulunui grup. Teorema lui Lagrange. Indicele unui subgrup
ntr-un grup. Ecuaia claselor. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . 864. Subgrupuri normale. Factorizarea unui grup printr-un subgrup
normal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .90
5. Morfisme de grupuri. Compunerea morfismelor degrupuri. Monomorfisme, epimorfisme, izomorfisme de
grupuri. Nucleul $i conucleul unei perechi de morfismede grupuri. . . . . . . . . . . . . . .94
6. Teorema lui Malev. Grupul (, +). Subgrupurile lui (, +). Clasele
de resturi modulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7. Teoremele de izomorfism pentru grupuri. . . . . . . . . . . . . . . 1088.Produse finite de grupuri. Teorema chinezeasc!a resturilor. Num!rul
tipurilor de grupuri abeliene finite. . . . . . . . . . . . . . . . . . . . . 1129. Teorema lui Cauchy pentru grupuri finite. Grupul diedral Dnde grad
n. Structura grupurilor finite cu 2p elemente (p prim , p!3) . . . . 118
10.Grupuri de permut!ri. Teorema lui Cayley. Grupurile Sn$i An. .12211. Teoremele lui Sylow. Aplicaii: caracterizarea grupurilor cu pq
elemente ( p $i q numere prime distincte ) $i 12 elemente. . . . . . . 132
CAPITOLUL 3: INELE "I CORPURI. . . . . . . . . . . . . .
. . 139
1. Inel. Exemple. Reguli de calcul ntr-un inel. Divizori ai lui zero.
Domenii de integritate. Caracteristica unui inel. . . . . . . . . . . . . 139
2. Subinele $i ideale. . . . . . . . . . . . . . . . . . . . . . . . . . . . .144
3. Morfisme de inele. Izomorfisme de inele. Transportul subinelelor $iidealelor prin morfisme de inele. Produse directe de inele. . . . . . . 152
5/24/2018 Lectii de Algebra
7/253
7
4. Factorizarea unui inel printr-un ideal bilateral. Teoremele de
izomorfism pentru inele. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1575. Corp. Subcorp. Subcorp prim . Morfisme de corpuri. Caracteristica
unui corp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1606. Inele de fracii. Construcia corpului "al numerelor raionale. .165
7. Construcia corpului #al numerelor reale . . . . . . . . . . . . . .169
8. Construcia corpului $al numerelor complexe . . . . . . . . . . .186
9. Construcia corpului Hal cuternionilor. . . . . . . . . . . . . . . 189
10. Ideale prime . Ideale maximale. . . . . . . . . . . . . . . . . . . . 191
11. Divizibilitatea n inele. . . . . . . . . . . . . . . . . . . . . . . . . 199
CAPITOLUL 4: INELE DE POLINOAME. . . . . . . . . . . . . 206
1. Inelul polinoamelor ntr-o nedeterminat!. . . . . . . . . . . . . . .206
2. Inelul polinoamelor n mai multe nedeterminate. . . . . . . . . 213
3. Polinoame simetrice. .. . . . . . . . . . . . . . . . . . . . . . . . . . 2194. R!d!cini ale polinoamelor cu coeficieni ntr-un corp. Teorema
fundamental! a algebrei. Polinoame ireductibile. Rezolvarea ecuaiiloralgebrice de grad 3 $i 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
CAPITOLUL 5: ELEMENTE DE
TEORIA CATEGORIILOR. . . . . . . . . . . . . . . . . . . . . . . 2401. Definiia unei categorii. Exemple. Subcategorie. Duala unei
categorii. Produs de categorii. Principiul dualiz!rii. . . . . . . . . . .240
2.Morfisme $i obiecte remarcabile ntr-o categorie. Nucleul $iconucleul unui cuplu de morfisme. . . . . . . . . . . . . . . . . . . . 2443. Functori. Exemple. Functori remarcabili. Morfisme functoriale.
Categorii echivalente. Duala lui Ens.. . . . . . . . . . . . . . . . . . . 253
4. Functori reprezentabili . Functori adjunci. . . . . . . . . . . . . .264
5. Reflefunctori .Subcategorii reflexive. . . . . . . . . . . . . . . . . 277
6. Produse $i sume directe ale unei familii de obiecte. . . . . . . . 2797.Limita inductiv!(proiectiv!) a unui sistem inductiv (proiectiv)..287
5/24/2018 Lectii de Algebra
8/253
8
8. Sume $i produse fibrate. . . . . . . . . . . . . . . . . . . . . . . . . 294
9. Obiecte injective (proiective). Anvelope injective (proiective) ..297
10. Categorii abeliene. . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
CAPITOLUL 6: MODULE "I SPA!II VECTORIALE. . . . . . 3141. Modul. Submodul. Calcule ntr-un modul. Operaii cu submodule.Submodul generat de o mulime. Laticea submodulelor unui modul.Sistem de generatori. Elemente liniar independente (dependente).Module libere. Spaii vectoriale. Submodul maximal. Modul simplu.
Factorizarea unui modul printr-un submodul. Modul factor.. . . . . 314
2. Morfisme de module. Endomorfisme. Operaii cu morfisme demodule. Imaginea, nucleul, coimaginea $i conucleul unui morfism demodule. Categoriile Mods(A) $i Modd(A). Monomorfisme,epimorfisme, izomorfisme de module. Nucleul $i conucleul unei perechide morfisme. Teorema fundamental! de izomorfism pentru module.Consecine. 'iruri exacte de A-module. Functorii hM $i hM de la
Mods(A)la Ab. Bimodule. Dualul $i bidualul unui modul. . . . . . .3273. Produse $i sume directe n Mods(A). Sume directe de submodule.Produse $i sume directe de morfisme de A-module. Sume $i produse
fibrate n Mods(A). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3474. Limite inductive $i proiective n Mods(A). Limite inductive $i
proiective de morfisme de A-module. . . . . . . . . . . . . . . . . . . 3605. Submodule eseniale $i superflue. Submodule complement.
Submodule nchise. Module injective. Grupuri divizibile. Anvelopeinjective. Module proiective. Anvelope proiective. Generatori,
cogeneratori pentru Mods(A). . . . . . . . . . . . . . . . . . . . . . . . . 3736. Produs tensorial de module. Produs tensorial de morfisme. FunctoriiSM $i TN; transportul $irurilor exacte scurte prin ace$ti functori.Comutativitatea produsului tensorial. Permutarea produsului tensorial cusumele directe. Produs tensorial de module libere. Asociativitatea
produsului tensorial. Proprietatea de adjuncie. Module plate. . . . . 3967. Module libere de rang finit. Matricea de trecere de la o baz!la alta.Formula de schimbare a coordonatelor unui element la schimbarea
5/24/2018 Lectii de Algebra
9/253
9
bazelor. Lema substituiei. Matricea ata$at! unei aplicaii liniare ntremodule libere de rang finit; formula de schimbare a acesteia la
schimbarea bazelor.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
CAPITOLUL 7: DETERMINAN!I. SISTEME DE
ECUA!II LINIARE. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . .426
1. Definiia unui determinant de ordin n. Propriet%iledeterminanilor. Dezvoltarea unui determinant dup% elementele
unei linii. Regula lui Laplace. Formula Binet-Cauchy. . . . . . . . . . .. . . . . . . . . . . . . . 426
2. Matrice inversabil%. Inversa unei matrice. Rangul unui sistemde vectori. Rangul unei matrice. Rangul unei aplicaii liniare ntre
spaii vectoriale de dimensiuni finite.. . . . . . . . . . . . . . . . . . . . . . .
. .4453. Sisteme de ecuaii liniare cu coeficieni ntr-un corp comutativ.Sisteme omogene. Vectori $i valori proprii ai unui operator liniar.Teorema Cayley-Hamilton. . . . . . . . . . . . . . . . . . . . . . . . . . . . .455
CAPITOLUL 8: ELEMENTE DE PROGRAMARE LINIAR)..4701. Punerea unei probleme de programare liniar!. Soluii posibile.
Soluii de baz!.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4702. Tabelul simplex asociat unei soluii de baz!. Algoritmul simplex.
Regula lexicografic!de evitare a ciclajului.. . . . . . . . . . . . . . . .
.4733. Metode de determinare a soluiilor de baz!. Metoda matriceal!.Metoda celor dou! faze. Exemple de aplicare a algoritmului simplex.Exemple de probleme deprogramare liniar!. Exemplu de evitare aciclajului.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 479
5/24/2018 Lectii de Algebra
10/253
10
CAPITOLUL 9: FORME BILINIARE 'I P)TRATICE . . . . . .495
1.Forme biliniare. Definiii. Exemple. Matricea ata$at! unei forme
biliniare. Rangul unei forme biliniare.. . . . . . . . . . . . . . . . . . . . 495
2. Forme p!tratice.Polara unei forme p!tratice.Matricea ata$at! uneiforme p!tratice.Forma canonic!a unei forme p!tratice ;metodele Gauss-
Lagrange $i Jacobi .Legea ineriei a lui Sylvester. . . . .. . . . . . . . 497
BIBLIOGRAFIE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .507
INDEX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
5/24/2018 Lectii de Algebra
11/253
11
CONTENTSpag
Chapter1: PRELIMINARIES. . . . . . . . . . . . . . . . . .
. . . .15 1. Sets. Operations on sets. . . . . . . . . . . . . . . . . . . . . . . . 152. Binary operations on a set.
Equivalence relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3. Functional relations. Notion of function.Classes of functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4. The kernel (equalizer) and cokernel (coequalizer)
for a couple of functions. . . . . . . . . . . . . . . . . . . . . . . . . . 46
5. Ordered sets. Semilattices. Lattices. . . . . . . . . . . . . . . . . 49
6. Distributive lattices. . . . . . . . . . . . . . . . . . . . . . . . . . 59 7. Complement and pseudocomplement in a lattice.
Boolean algebras. Generalized Boolean algebras. . . . . . . . . . . . . 64 8. Direct products (coproducts) for a family of sets. . . . . . . . . .71
9. Cardinal numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . 75
10.Countable sets. Finite and infinite sets. . . . . . . . . . . . . . . .81
Chapter 2: GROUPS. . . . . . . . . . .. . . . . . . . . . . . . . . . 86 1. Algebraic operations. Monoids. Morphisms of monoids.
Direct product of monoids. . . . . . . . . . . . . . . . . . . . . . . . .86 2. Group. Calculus in a group. Subgroup.Subgroup generated by a set. Cyclic groups.
The Order of an element. . . . . . . . . . . . . . . . . . . . . . . . . .98 3. The centralizer of an element in a group.The center of a group. The theorem of Lagrange.The index of a subgroup in a group.
The class equation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4. Normal subgroups.
5/24/2018 Lectii de Algebra
12/253
12
Factorization of a group by a normal subgroup. . . . . . . . . . . . .105 5. Morphisms of groups. Composition of morphisms.Monomorphisms, epimorphisms, isomorphisms of groups.
The kernel (equalizer) and cokernel (coequalizer)for a couple of morphisms. . .. . . . . . . . . . . . . . . . . . . . . .109
6. The theorem of Mal`cev. The group of integers (,+).
The subgroups of (,+).
Complete set of residues modulo n . . . . . . . . . . . . . . . . . . 114
7. The isomorphism theorems for groups. . . . . . . . . . . . . . 123 8. Finite direct products of groups.
The Chinese remainder theorem.The number of abelian finite groups. . . . . . . . . . . . . . . . . . 127 9. The Cauchy theorem for finite groups.The Dihedral group D n of degree n.
The structure for finite groups of 2p order (p prime, p 3). . . . . 13310. The groups of permutations. The theorem of Cayley.The groups S n and A n . . . . . . . . . . . . . . . . . . . . . . . . . .137
11. The Sylow theorems. Applications: the groups of pq order(p,q primers, p q) and of order 12. . . . . . . . . . . . . . . . . . . 147
Chapter 3: RINGS AND FIELDS. . . . . . . . . . . . . . . . . . 154 1. Rings. Examples. Calculus in a ring.
Zero divisors. Integral domains. The characteristic of a ring. . . . 154
2. Subrings and ideals. . . . . . . . . . . . . . . . . . . . . . . . . .159 3. Morphisms of rings. Isomorphisms of rings.The transport of subrings and ideals by a morphism of rings.
Direct products of rings. . . . . . . . . . . . . . . . . . . . . . . . . . . .167 4. The factorization of a ring by a bilateral ideal.
The isomorphism theorems for rings. . . . . . . . . . . . . . . . . . 172 5. Field Subfield. Prime Subfield. Morphisms of fields.
The characteristic of a field. . . . . . . . . . . . . . . . . . . . . . . 175 6. Rings of fractions. Construction of the rationals field ". . . . 179
5/24/2018 Lectii de Algebra
13/253
13
7. Construction of the reals field #. . . . . . . . . . . . . . . . . . 184
8. Construction of the complex numbers field $. . . . . . . . . . .200
9. Construction of the quaternions field H. . . . . . . . . . . . . . 203
10.Prime and maximal ideals. . . . . . . . . . . . . . . . . . . . . . . 205
11.Divisibility in rings . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
Chapter 4: POLYNOMIAL RINGS. . . . . . . . . . . . . . .
220
1. Polynominals ring in one indeterminate. . . . . . . . . . . . . . .
220
2. Polynominals ring in several indeterminates. . . . . . . . . . . .
227
3. Symetrical polynominals. . . . . . . . . . . . . . . . . . . . . . . .
.232 4. Roots of polynominals with coefficients in a field.The fundamental theorem of algebra. Irreducible polynominals.
The solving of the algebraic equations of a 3 and 4 degree. . . . . .
.240
Chapter 5: ELEMENTS OF CATEGORIES THEORY. . . . . .
253 1. Category. Exampels. Subcategory. Dual category.
Duality principle. Product of categories. . . . . . . . . . . . . . . . . . 253 2. Special morphisms and objects in a category.The kernel (equalizer) and cokernel (coequalizer)
for a couple of morphisms . . . . . . . . . . . . . . . . . . . . . . . . . .
257 3. Functors. Examples. Remarkable functors.Morphism functors. Equivalence of Categories.
The dual category of Ens. . . . . . . . . . . . . . . . . . . . . . . . . . . 266
5/24/2018 Lectii de Algebra
14/253
14
4. Representable functors. Adjoint functors. . . . . . . . . . . . . . .277
5. Reflectors. Reflective subcategories. . . . . . . . . . . . . . . . .
.290
6. Products and coproducts of a fammily of objects. . . . . . . . . .292
7. Limits and colimits for a partially ordered system. . . . . . . . .
300
8. Fibred sum (poshout) and fibred product (pullback)
of two objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
9. Injective (projective) objects.
Injective (projective) envelopes. . . . . . . . . . . . . . . . . . . . . . . 310
10.Abelian Categories. . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
5/24/2018 Lectii de Algebra
15/253
15
CAPITOLUL 1: NO!IUNI PRELIMINARII
1 Mulimi. Operaii cu mulimi
n cadrul acestei lucr!ri vom privi mulimile n sensul n careele au fost privite de c!tre GEORG CANTOR - primul matematiciancare a iniiat studiul lor sistematic (punct de vedere cunoscut nmatematic!sub numele de teoria naiva mul#imilor).
Despre paradoxurile ce le implic!acest punct de vedere $i feluln care ele pot fi eliminate, rug!m cititorul s!consulte lucr!rile [16] $i[30].
Definiia 1.1. Dac%A (i B sunt dou%mulimi, vom spune c%A este inclusn B (sau c% A este submul#ime a lui B) dac%elementele lui A sunt (i elemente ale lui B; n acest caz vom scrie
A%B iar n caz contrar A&B.
Avem deci : A%B'pentru orice x(A )x(BA&B'exist!x(A a.. x*B.
Vom spune despre mulimile A $i B c! sunt egale dac!
oricare ar fi x, x(A'x(B. Deci, A=B'A%B $i B%A.
Vom spune c!A este inclusstrictn B $i vom scrie A+B dac!
A%B $i A,B.Se accept!existena unei mulimi ce nu conine nici un element
care se noteaz!prin -$i poart!numele de mul#imea vid. Se observ!
c!pentru orice mulime A, -%A (deoarece n caz contrar ar trebui s!
existe x(-a.. x*A absurd.!).O mulime diferit!de mulimea vid!se zice nevid.Pentru o mulime T, vom nota prin P(T) mulimea
submulimilor sale (evident -, T(P(T) ).
Urm!torul rezultat este imediat :
5/24/2018 Lectii de Algebra
16/253
16
Dac%T este o mulime oarecare iar A, B, C(P(T), atunci :
(i) A%A
(ii) Dac%A%B (i B%A, atunci A=B
(iii) Dac%A%B (i B%C, atunci A%C.
n cadrul acestei lucr!ri vom utiliza deseori noiunea defamiliede elemente a unei mulimi indexat! de o mulime nevid! de indici I(prin aceasta nelegnd o funcie definit! pe mulimea I cu valori nmulimea respectiv!).
Astfel, vom scrie de exemplu (x i)i(Ipentru a desemna o familie
de elemente ale unei mulimi sau (Ai) i(Ipentru a desemna o familie demulimi indexat! de mulimea I. Pentru o mulime T $i A, B(P(T)definim :
A.B={x(T | x(A $i x(B}
A/B={x(T | x(A sau x(B}
A\B={x(T | x(A $i x*B}
A0B=(A\B)/(B\A).
Dac!A.B=-, mulimile A $i B se zic disjuncte.
Operaiile ., /, \ $i 0poart!numele de intersec#ie, reuniune,diferen#$i diferen#simetric.
n particular, T\A se noteaz!prin 1T (A) (sau 1(A) dac!nu estepericol de confuzie) $i poart!numele de complementara lui A n T.
n mod evident, pentru A, B(P(T) avem:
A\B=A.1T (B)A0B=(A/B)\(A+B)=(A.1T (B))/(1T (A).B)
1T (-)=T, 1T(T)=-
A/1T (A)=T, A.1T (A)=- iar 1T (1T (A))=A.
De asemenea, pentru x(T avem:
x*A.B 'x*A sau x*B
x*A/B 'x*A $i x*Bx*A\B 'x*A sau x(B
5/24/2018 Lectii de Algebra
17/253
17
x*A0B'(x*A $i x*B) sau (x(A $i x(B)
x*1T(A)'x(A.
Din cele de mai nainte deducem imediat c!dac!A, B(P(T),
atunci:1T (A.B)=1T(A)/1T (B) $i 1T (A/B)=1T (A).1T (B).
Aceste ultime dou! egalit!i sunt cunoscute sub numele derela#iile lui De Morgan.
Pentru o familie nevid!(Ai )i(Ide submulimi ale lui T definim:
IIi
iA
={x(T | x(Aipentru orice i(I} $i
UIi iA ={x(T | exist!i(I a.. x(Ai }.Astfel, relaiile lui De Morgan sunt adev!rate ntr-un context
mai general:
Dac! (Ai) i(I este o familie de submulimi ale mulimii T,atunci:
( )iIi
TIi
iT ACAC UI
=
$i ( )iIi
TIi
iT ACAC IU
=
.
Urm!torul rezultat este imediat:
Propoziia 1.2. Dac%T o mulime iar A, B, C(P(T), atunci:
(i) A.(B.C)=(A.B).C (i A/(B/C)=(A/B)/C
(ii) A.B=B.A (i A/B=B/A
(iii) A.T=A (i A/-=A
(iv) A.A=A (i A/A=A.
Observaia 1.3. 1. Din (i) deducem c!operaiile /$i .suntasociative, din (ii) deducem c! ambele sunt comutative, din (iii)
deducem c!T $i -sunt elementele neutre pentru .$i respectiv pentru
/,iar din (iv) deducem c!.$i /sunt operaii idempotentepe P(T).
2. Prin dubl!incluziune se probeaz!imdiat c!pentru oricare A,B, C(P(T) avem:
5/24/2018 Lectii de Algebra
18/253
18
A.(B/C)=(A.B)/(A.C) $i
A/(B.C)=(A/B).(A/C) ,adic! operaiile de intersecie $i reuniune sunt distributive una fa! de
cealalt!.
Propoziia 1.4. Dac%A, B, C(P(T), atunci:
(i) A0(B0C)=(A0B)0C
(ii) A0B=B0A
(iii) A0-=A iar A 0A=-
(iv) A.(B0C)=(A.B)0(A.C).
Demonstra#ie. (i). Prin dubl!incluziune se arat!imediat c!:
A0(B0C)=(A0B)0C=[A.1T(B).1T(C)]/[1T(A).B.1T(C)]/
/[1T(A).1T(B).C]/(A.B.C).(ii), (iii) sunt evidente.(iv). Se probeaz! fie prin dubl! incluziune, fie innd cont de
distributivitatea interseciei fa!de reuniune. 2
Definiia 1.5. Fiind date dou% obiecte x (i y se nume(tepereche ordonata obiectelor x (i y mulimea notat%(x, y) (i definit%astfel:
(x, y)={ {x}, {x, y} }.
Se verific! acum imediat c! dac! x $i y sunt dou! obiecte a..
x,y, atunci (x, y),(y, x) iar dac! (x, y) $i (u, v) sunt dou! perechi
ordonate, atunci (x, y)=(u, v) 'x=u $i y=v ; n particular, (x, y)=
=(y, x) )x=y.
Definiia 1.6. Dac% A (i B sunt dou% mulimi, mulimea
notat%AB={ (a, b) | a(A (i b(B } se va numi produsul cartezianal mulimilor A (i B.
n mod evident:AB,-'A,-$i B,-
5/24/2018 Lectii de Algebra
19/253
19
AB=-'A=-sau B=-
AB=BA 'A=B
A3%A $i B3%B )A3B3%AB.
Dac! A, B, C sunt trei mulimi vom defini produsul lorcartezian prin egalitatea : ABC=(AB)C.
Elementul ((a, b), c) din ABC l vom nota mai simplu prin(a, b, c).
Mai general, dac!A1, A2, ..., An (n!3) sunt mulimi punem
A1A2...An =((...((A1A2)A3)...)An).Dac! A este o mulime finit!, vom nota prin |A| num!rul de
elemente ale lui A. n mod evident, dac!A $i B sunt submulimi finiteale unei mulimi M atunci $i A/B este submulime finit!a lui M iar
|A/B|=|A|+|B|-|A.B|.
Vom prezenta n continuare un rezultat mai general cunoscutsub numele deprincipiul includerii $i excluderii:
Propoziia 1.7. Fie M o mulime finit% iar M1, M2, ..., Mnsubmulimi ale lui M. Atunci :
( ) nn
nkji
kji
nji
ji
ni
i
n
i
i
MM
MMMMMMM
-+-
-+-=
-
5/24/2018 Lectii de Algebra
20/253
20
Dac!not!m U1
1
-
==
n
iiMN , atunci conform relaiei (1) putem scrie:
(2) ==U
n
i i
M1
|N/Mn|=|N|+|Mn|-|N.Mn|.
ns! N.Mn=
-
=U
1
1
n
i
iM .Mn= U1
1
)(-
=
n
ini MM , deci aplicnd
ipoteza de inducie pentru ( )U I1
1
-
=
n
ini MM $i innd seama de faptul c!
( ) ( ) ( ) III II njinjni MMMMMMM = ,
( ) ( ) ( ) ( )IIII I III nkjinknjni MMMMMMMMMM = , etc,obinem:
(3)
( )
( ) II I I
I IIU I
n
i
in
nkjinkji
njinji
n
ini
n
inin
MMMMM
MMMMMMMMN
1
2
11
11
1
1
1
1
1....=
-
-
5/24/2018 Lectii de Algebra
21/253
21
( )
( )
( )
( ) .1...
1
....1
1
...
1
1
1
111
2
1...1
3
1
1
2
11 11
11
1
1
1
1
1
221
221
II I
II
I I I I
I
I II I
II
U
n
ii
n
nkjikji
njiji
n
ii
n
ii
n
niii
niiin
n
ii
n
nkji njinjikji
nji
n
iniji
n
ini
nn
n
ii
MMMM
MMMM
MMMM
M
MMMMMM
MMMMMM
MNMNM
n
n
=
-
5/24/2018 Lectii de Algebra
22/253
22
n mod evident, (,-1)-1=, iar dac! mai avem ,3(Rel (A) a..
,%,3),-1%,3-1.
Definiia 2.2. Pentru *, *3(Rel (A) definim compunerea lor*5*3 prin *5*3={(a, b)(AA | exist% c(A a.. (a, c)(*3 (i
(c, b)(*}.
Rezultatul urm!tor este imediat:
Propoziia 2.3. Fie *, *3, *33(Rel (A). Atunci:
(i) *50A=0A5*=*
(ii) (*5*3)5*33=*5(*35*33)
(iii) *%*3)*5*33%*35*33 (i *335*%*335*3
(iv) (*5*3)-1=*3-15*-1
(v) (*/*3)-1=*-1/*3-1 ; mai general, dac% (*i) i(I este ofamilie de relaii binare pe A, atunci
UUIi
i
Ii
i
--
=
11
rr .
Pentru n(6$i ,(Rel(A) definim :
>
=D= 1....
0
npentru
npentru
orin
A
n
4434421 ooo rrrr .
Se probeaz! imediat c! dac! m, n (6 atunci
,m5,n=,m+n.
Definiia 2.4. Vom spune despre o relaie *(Rel (A) c% este:
i) reflexivdac%0A%*
ii) simetricdac%*%*-1
iii) antisimetricdac%*.*-1%0A
iv) tranzitivdac%*2%*.Rezultatul urm!tor este imediat:
5/24/2018 Lectii de Algebra
23/253
23
Propoziia 2.5. O relaie *(Rel(A) este reflexiv% ( simetric%,antisimetric%, tranzitiv% ) dac% (i numai dac% *-1 este reflexiv%
( simetric%, antisimetric%, tranzitiv%) .
Definiia 2.6. Vom spune despre o relaie *(Rel(A) c%este oechivalen#pe A dac%este reflexiv%, simetric%(i tranzitiv%.
Vom nota prin Echiv(A) mulimea relaiilor de echivalen!de
pe A. Evident, 0A, AA(Echiv(A).
Propoziia 2.7. Dac%*(Echiv (A) , atunci *-1=* (i *2=*.
Demonstra#ie. Cum , este simetric! ,%,-1. Dac! (a, b)(,-1,
atunci (b, a)(,%,-1)(b, a)(,-1)(a, b)(,, adic!,-1%,, deci ,-1=,.
Cum ,este tranzitiv!avem ,2%,. Fie acum (x, y)(,. Din (x, x)(,$i
(x, y)(,)(x, y)(,5,=,2, adic!,%,2, deci ,2=,. 2
Propoziia 2.8. Fie *1, *2 (Echiv (A). Atunci*15*2(Echiv (A) dac% (i numai dac%*15*2=*25*1 . n acest caz*15*2= I
rrrr
r
21 ,)(AEchiv
.
Demonstra#ie. Dac!,1 , ,2(Echiv (A), atunci (,15,2)-1=,15,2
conform Propoziiei 2.7. ns! conform Propoziiei 2.3. avem c!
(,15,2)-1= ,2
-15,1-1=,25,1, astfel c!,15,2=,25,1.
Invers, s!presupunem c!,15,2=,25,1.
Cum 7A%,1 , ,2)7A=7A57A%,15,2, adic! ,15,2 este
reflexiv!. Cum (,15,2)-1= ,2
-15,1-1 =,25,1= ,15,2, deducem c! ,15,2
este $i simetric!. Din (,15,2)2=(,15,2)5(,15,2)=,15(,25,1)5,2=
=,15(,15,2)5,2=,125,2
2= ,15,2 deducem c! ,15,2 este $i tranzitiv!,adic!este o echivalen!pe A.
S! presupunem acum c!,15,2=,25,1 $i fie ,3(Echiv (A) a..,1, ,2%,3.
5/24/2018 Lectii de Algebra
24/253
24
Atunci ,15,2%,35,3=,3, adic!
( )Io
rrrr
rrr
21,
21AEchiv
8-
Cum ,1, ,2(Echiv(A) $i ,15,2(Echiv(A) ),1,,2%,15,2)-%,15,2
adic!-=,15,2.2
Pentru ,(Rel (A), definim rela#ia de ehivalen# de pe Ageneratde'ca fiind relaia de echivalen!
( )I
rrr
rr
=AEchiv
.
n mod evident, relaia de echivalen! este caracterizat!decondiiile ,% iar dac!,3(Echiv (A) a.. ,%,3)%,3(altfel zis, este cea mai mic!relaie de echivalen!ce include pe ,).
Lema 2.9. Fie *(Rel(A) (i r=7A/*/*-1. Atunci relaia r
are urm%toarele propriet%i:(i) *%r
(ii) r este reflexiv%
(i simetric
%
(iii) dac%*3este o alt%relaie binar%de pe A reflexiv%(i simetric%a.. *%*3, atunci r%*3.
Demonstra#ie. (i ). este evident!.(ii). Cum 7A%r deducem c!r este reflexiv!iar cum
1-r = (7A/,/,
-1) 1=7A-1/,-1/ (,-1)-1=7A/,/,
-1=r deducem c!
r este $i simetric!.
(iii). Dac! ,3 este reflexiv! $i simetric! a.. ,%,3, atunci
,-1%,3-1=,3$i cum 7A%,3deducem c! r=7A/,/,-1%,3.2
Lema 2.10. Fie *(Rel(A) reflexiv%(i simetric%iar U1
=n
nrr .
Atunci r are urm%toarele propriet%i :
(i) *%r
5/24/2018 Lectii de Algebra
25/253
25
(ii) r este o echivalen%pe A
(iii) Dac%*3(Echiv(A) a.. *%*3,atunci r%*3.
Demonstra#ie. (i). este evident!.(ii). Cum 7A%,%r deducem c! 7A%r , adic! r este
reflexiv!. Deoarece , este simetric! $i pentru orice n(6* avem(,n)-1=(,-1)n=,n, deducem c!
( ) rrrrr ===
=
--
-
UUU11
11
1
1
n
n
n
n
n
n ,
adic! r este $i simetric!. Fie acum (x, y)( rro ; atunci exist! z(Aa.. (x, z), (z, y)(r , adic!exist!m, n(6*a.. (x, z)(,m$i (z, y)(,n.
Deducem imediat c! (x, y)(,n5,m=,n+m%r , adic! rr 2
, deci r
este tranzitiv!, adic!r(Echiv (A).
(iii). Fie acum ,3(Echiv (A) a.. ,%,3. Cum , n%,3 n =,3pentru orice n(6*deducem c! U
1=
n
nrr %,3. 2
Din Lemele 2.9. $i 2.10. deducem imediat:
Teorema 2.11. Dac%*(Rel(A), atunci
( )U U U1
1
-D=n
n
A rrr .
Propoziia 2.12. Fie *, *3(Rel (A ). Atunci:
(i) (*/*3)2=*2/*32/(*5*3)/(*35*)
(ii) Dac% *, *3(Echiv (A) atunci */*3(Echiv (A) dac% (i
numai dac%*5*3, *35*%*/*3.
Demonstra#ie.
(i). Avem: (x, y)((,/,3)2=(,/,3)5(,/,3) 'exist!z(A a..
(x, z)(,/p3 $i (z, y)(,/,3'[ (x, z)(,$i (z, y)(,] sau [ (x, z)(,3$i (z, y)(,3] sau [(x, z)(,3 $i (z, y)(,] sau [(x, z)(, $i (z, y)(,3]
5/24/2018 Lectii de Algebra
26/253
26
' (x, y)(,2 sau (x, y)(,32 sau (x, y)(,5,3 sau (x, y)(,35, '
'(x, y)(,2/,32/(,5,3)/(,35,), de unde egalitatea cerut!.
(ii).,,). Avem c! ,2=,, ,32=,3 $i (,/,3)2=,/,3. Astfel,
relaia de la (i) devine: ,/,3=,/,3/(,5,3)/(,35,), deci ,5,3%,/,3$i
,35,%,/,3.
,,9. Utiliz!m ipoteza din nou $i relaia de la (i):
(,/,3)2=,2/,32/(,5,3)/(,35,)=,/,3/(,5,3)/(,35,)%,/,3, deci
,/,3este tranzitiv!. Cum 7A%, $i 7A%,3)7A%,/,3 , adic! ,/,3
este reflexiv!. Dac! (x, y)(,/,3)(x, y)(,sau (x, y)(,3)(y, x)(,
sau (y, x)(,3) (y, x)(,/,3, adic! ,/,3 este $i simetric!, deci o
echivalen!pe A. 2
Propoziia 2.13. Fie A o mulime (i *(Rel(A) avndpropriet%ile:
(i) Pentru oricex(A, exist%y(A a.. (x, y)(*
(ii) *5*-15*= *
Atunci *5*-1, *-15*(Echiv (A).
Demonstra#ie.
Avem c!,5,-1={(x, y) 4exist!z(A a.. (x, z)(,-1 $i (z, y)(,}.
Deci, pentru a demonstra c!7A%,5,-1ar trebui ca pentru orice
x(A, (x, x)(,5,-1 adic!s!existe z(A a.. (z, x)(,, lucru asigurat de
(i). Deducem c!,5,-1este reflexiv!(analog pentru ,-15,).
Dac!(x, y)(,5,-1)exist!z(A a.. (x, z)(,-1 $i (z, y)(,'
exist!z(A a.. (y, z)(,-1$i (z, x)(,'(y, x)(,5,-1, adic! ,5,-1
este simetric! (analog pentru ,-15,). Cum (,5,-1)5(,5,-1) =
= (,5,-15,)5,-1= ,5,-1 deducem c!,5,-1 este $i tranzitiv!, deci este o
echivalen!. Analog pentru ,-15,.2
5/24/2018 Lectii de Algebra
27/253
27
Definiia 2.14. Dac% *(Echiv (A) (i a(A, prin clasa deechivalen#a lui a relativ%la *nelegem mulimea
[a]*={x(A 4(x, a)(*} (cum *este n particular
reflexiv%deducem c%a([a]*, adic%[a]*,-pentru orice a(A).
Mulimea A / *={ [a] *4a(A } poart%numele de mul#imeafactor( sau ct ) a lui A prin relaia *.
Propoziia 2.15. Dac%*(Echiv (A), atunci:
(i) [ ]UAa
a
*=A
(ii) Dac%a, b(A atunci [a]*=[b]*'(a, b)(*
(iii) Dac%a, b(A, atunci [a]*=[b]*sau [a]*.[b]*=-.
Demonstra#ie.
(i). Deoarece pentru orice a(A, a([a],deducem incluziunea dela dreapta la stnga; cum cealalt! incluziune este evident! deducem
egalitatea solicitat!.(ii). Dac! [a],=[b], , cum a([a], deducem c! a([b], adic!
(a, b)(,.
Fie acum (a, b)(, $i x([a],, adic! (x, a)(,. Datorit!
tranzitivit!ii lui ,deducem c!(x, b)(,, adic!x([b],, deci [a],%[b],.
Analog deducem c!$i [b],%[a],, adic![a],=[b],.
(iii). Presupunem c! [a],.[b],,-. Atunci exist! x(A a.. (x,a), (x, b)(,$i astfel (a, b)(,, deci [a],=[b], (conform cu (ii)). 2
Definiia 2.16. Numim parti#ie a unei mulimi M o familie
(Mi)i(I de submulimi ale lui M ce verific%condiiile :
(i) Pentru i, j(I, i,j )Mi.Mj=-
(ii)UIi i
MM
= .
5/24/2018 Lectii de Algebra
28/253
28
Observaia 2.17. Din cele de mai nainte deducem c! dac! ,este o relaie de echivalen!pe mulimea A, atunci mulimea claselor deechivalen!ale lui ,pe A determin!o partiie a lui A.
3 Relaii funcionale. Noiunea de funcie.Clase de funcii.
Definiia 3.1. Fie A (i B dou% mulimi. O submulime
R%AB se nume(te rela#ie func#ionaldac%:
(i) Pentru oricea(A exist%b(B a.. (a, b)(R(ii) (a, b), (a, b3)(R )b=b3.
Numimfunc#ie( sau aplicaie ) un triplet f=(A, B, R) unde A
(i B sunt dou%mulimi nevide iar R%AB este o relaie funcional%.
n acest caz, pentru fiecare element a(A exist!un unic element
b(B a.. (a, b)(R. Convenim s!not!m b=f(a) ; elementul b se va numi
imaginea lui aprin f. Mulimea A se nume$te domeniul (sau domeniulde defini#ie al lui f) iar B se nume$te codomeniul lui f $i spunem deobicei c! f este o funcie definit! pe A cu valori n B scriind lucrul
acesta prin f:A.B sau A f B.Relaia funcional! R se mai nume$te $i graficul lui f
(convenim s!not!m pe R prin Gf, astfel c!Gf={(a, f(a)) | a(A}.
Dac! f :A.B $i f3:A3.B3 sunt dou! funcii, vom spune c! ele sunt
egale ($i vom scrie f=f3) dac!A=A3, B=B3$i f(a)=f3(a)pentru orice
a(A. Pentru o mulime A, funcia 1A:A.A, 1A(a)=a pentru orice a(Apoart!numele defunc#ia identica lui A(n particular, putem vorbi de
funcia identic!a mulimii vide 1-). Dac!A=-atunci exist!o unic!
funcie f:-:B ( este de fapt incluziunea lui - n B). Dac!A,- $i
B=-atunci n mod evident nu exist!nici o funcie de la A la B.
Dac!f :A.B este o funcie iar A3%A $i B3%B atunci not!m:f(A3)={f (a) | a(A3} $i f-1 (B)={a(A | f (a)(B3}
5/24/2018 Lectii de Algebra
29/253
29
(f (A3)se va numi imaginealui A3prin f iar f-1(B3)contraimaginealui
B3prin f ).
n particular, not!m Im(f)=f (A). Evident, f(-)=-
$i f-1(-)=-.
Definiia 3.2. Fiind date dou% funcii f:A+B (i g:B+C
numim compunerea lor funcia notat% g5f:A+C (i definit% prin
(g5f)(a)=g(f(a)) pentru orice a(A.
Propoziia 3.3. Dac% avem trei funciiDCBA hgf atunci:
(i) h5(g5f)=(h5g)5f
(ii) f51A=1B5f=f.
Demonstra#ie.(i). ntr-adev!r, avem c!h5(g5f) $i (h5g)5f au peA drept domeniu de definiie, pe D drept codomeniu $i pentru orice
a(A(h5(g5f))(a)=((h5g)5f)(a)=h(g(f(a))).
(ii). este evident!. 2
Propoziia 3.4. Fie f:A+B, A3, A33%A, B3, B33%B, (Ai)i(I,
(Bj)j(J dou%familii de submulimi ale lui A (i respectiv B. Atunci:
(i) A3%A33)f(A3)%f(A33)(ii) B3%B33)f-1(B3)%f-1(B33)
(iii) ( )IIIi
iIi
i AfAf
(iv) ( )UUIi
iIi
i AfAf
=
(v) ( )IIJj
jJj
j BfBf
-
- =
11
5/24/2018 Lectii de Algebra
30/253
30
(vi) ( )UUJj
jJj
j BfBf
-
- =
11 .
Demonstra#ie (i). Dac!b(f(A3), atunci b=f(a) cu a(A3$i cum
A3%A33deducem c!b(f(A33), adic!f(A3)%f(A33).(ii). Analog cu (i).(iii). Deoarece pentru orice k(I, I
IiiA
%Ak, conform cu (i)
deducem c! ( )kIi
i AfAf
I $i cum k este oarecare deducem c!
( )IIIi
iIi
i AfAf
.
(iv). Egalitatea cerut!rezult!imediat din echivalenele :
b(
U
IiiAf 'exist!a( U
IiiA
a.. b=f(a) 'exist! i0(I a.. a( 0iA $i
b=f(a)'exist!i0(I a.. b(f(0i
A )'b( ( )UIi
iAf
.
(v). Totul rezult! din echivalenele a(
- IJj
jBf1 '
f(a)(IJj
JB
'pentru orice j(J, f(a)(Bj'pentru orice j(J, a(f-1(Bj)
'a( ( )jJj
BfI
-1 .
(vi). Analog cu (iv). 2
Definiia 3.5. Despre o funcie f:A+B vom spune c%este:
i) injectiv, dac% pentru orice a, a3(A, a,a3)f(a),f(a3)
(echivalent cu f(a)=f(a3))a=a3)
ii) surjectiv, dac%pentru orice b(B, exist%a(A a.. b=f(a)iii) bijectiv,dac%este simultan injectiv%(i surjectiv%.Dac! f :A.B este bijectiv!, funcia f-1:B.A definit! prin
echivalena f-1(b)=a 'b=f(a) (b(B $i a(A) poart!numele de inversalui f.
5/24/2018 Lectii de Algebra
31/253
31
Se verific!imediat c!f-15f=1A $i f5f-1=1B.
Propoziia 3.6. Fie f :A+B (i g :B+C dou%funcii
(i) Dac%f (i g sunt injective (surjective; bijective) atunci g5feste injectiv% (surjectiv%, bijectiv% ; n acest ultim caz
(g5f)-1=f-15g-1)
(ii) Dac% g5f este injectiv% (surjectiv%, bijectiv%) atunci feste injectiv%, (g este surjectiv%; f este injectiv% (i g estesurjectiv%).
Demonstra#ie.(i). Fie a, a3(A a.. (g5f)(a)=(g5f)(a3). Atuncig(f(a))=g(f(a3)) $i cum g este injectiv!deducem c!f(a)=f(a3)iar cum $i f
este injectiv!deducem c!a=a3, adic!g5f este injectiv!.
S!presupunem acum c!f $i g sunt surjective $i fie c(C; cum g
este surjectiv!, c=g(b) cu b(B $i cum $i f este surjectiv!b=f(a) cu a(A
astfel c!c=g(b)=g(f(a))=(g5f)(a), adic!g5f este surjectiv!.
Dac! f $i g sunt bijective atunci faptul c! g5f este bijectiv!rezult! imediat din cele expuse mai sus. Pentru a proba n acest caz
egalitatea (g5f)-1= f-15g-1, fie c(C. Avem c!c=g(b) cu b(B $i b=f(a)
cu a(A. Deoarece (g5f)(a)=g(f(a))=g(b)=c deducem c!(g5f)-1(c)=a=
=f-1(b)=f-1(g-1(c))=(f-15g-1)(c), adic!(g5f)-1=f-15g-1.
(ii). S! presupunem c! g5f este injectiv! $i fie a, a3(A a..
f(a)=f(a3). Atunci g(f(a))=g(f(a3))'(g5f)(a)=(g5f)(a3))a=a3, adic! f
este injectiv!.Dac! g5f este surjectiv!, pentru c(C, exist! a(A a..
(g5f)(a)=c 'g(f(a))=c, adic!g este surjecie.
Dac! g5f este bijecie atunci n particular g5f este injecie $isurjecie, deci conform celor de mai sus cu necesitate f este injecie iar
g surjecie. 2
Propoziia 3.7. Fie M (i N dou% mulimi iar f :M:N ofuncie. ntre mulimile P(M) (i P(N) se definesc funciile
5/24/2018 Lectii de Algebra
32/253
32
f* : P(M):P(N), f* : P(N):P(M) prin f*(A)=f(A), ; A (P(M) (i
f*(B)=f-1(B), ;B(P(N).Urm%toarele afirmaii sunt echivalente:
(i) f este injectiv%(ii) f*este injectiv%
(iii) f*5f*=1P(M)(iv) f*este surjectiv%
(v) f (A.B)=f(A).f(B), ;A, B(P(M)
(vi) f(1MA)%1N f (A), ;A(P(M)
(vii) Dac%g, h:L :M sunt dou%funcii a.. f5g=f5h, atuncig=h
(viii) Exist%o funcie g :N :M a.. g5f=1M.
Demonstra#ie.Vom demonstra echivalena afirmaiilor astfel
(i))(ii))(iii))(iv))(v))(vi))(vii))(i) iar apoi (i)'(viii) .
(i))(ii). Fie A, A3(P(M) a.. f*(A)=f*(A3)'f(A)=f(A3).
Dac! x(A, atunci f(x)(f(A))f(x)(f(A3)) exist! x3(A3 a..
f(x)=f(x3).Cum f este injectiv!, rezult!x=x3(A3,adic!A%A3; analog
A3%A, deci A=A3, adic!f*este injectiv!.
(ii))(iii). Pentru A(P(M) trebuie demonstrat c!
(f*5f*)(A)=A' f-1 (f (A))=A. Incluziunea A%f -1(f (A)) este valabil!
pentru orice funcie f. Pentru cealalt!incluziune, dac!
x(f -1(f(A)))f(x)(f(A))exist!x3(A a.. f(x)=f(x3))f*({x})=f*({x3})
){x}={x3})x = x3(A, adic! f -1(f ( A))%A.
(iii))(iv). Deoarece f*5f*=1P(M) , pentru orice A(P(M),
f*(f*(A))=A, deci notnd B=f*(A)(P(N) avem c!f*(B)=A, adic!f*este
surjectiv!.
(iv))(v). Fie A, B(P(M) $i A3, B3(P(N) a.. A=f 1(A3) $i
B=f1
(B3). Atunci f(A.B)=f(f-1
(A).f-1
(B3))=f(f-1
(
A3.B3)).S!ar!t!m c!f(f-1(A3)).f(f-1(B3))%f(f-1(A3.B3).
5/24/2018 Lectii de Algebra
33/253
33
Dac!y(f(f -1(A3)).f(f -1 (B3)))y(f(f -1(A3)) $i y(f(f -1(B3)))
exist! x3(f -1(A3)$i x33(f -1(B3)a.. y=f(x3)=f(x33).
Cum x3(f -1(A3) $i x33(f -1(B3))f(x3)(A3$i f(x33)(B3, deci
y(A3.B3. Deoarece y=f(x3))x3(f -1(A3.B3), adic!y(f(f -1(A3.B3)).
Astfel, f(A.B)
5/24/2018 Lectii de Algebra
34/253
34
(vi) Dac% g, h:N:P sunt dou% funcii a.. g5f=h5f, atuncig=h
(vii) Exist%o funcie g:N:M a.. f5g=1N.
Demonstra#ie.Vom demonstra echivalena afirmaiilor astfel:
(i))(ii))(iii))(iv))(v))(vi))(i) iar apoi (i)'(vii).
(i))(ii). Fie B(P(N) $i y(B ; atunci exist!xy(M a.. f(xy)=y.
Notnd A={xy4y(B}%M avem c!f (A)=B 'f*(A)=B.
(ii))(iii). Avem de demonstrat c! pentru orice B(P(N),
f (f-1(B))=B . Incluziunea f (f-1(B))%B este valabil!pentru orice funcie
f. Fie acum y(B; cum f* este surjectiv!, exist! A%M a..
f*(A)={y}'f(A)={y}, deci exist! x(A a.. y=f(x) $i deoarece y(B)
x(f-1 (B))y=f(x)(f(f 1(B)), de unde $i incluziunea B%f(f 1 (B)).
(iii))(iv). Dac! B1, B2(P(N) $i f
*
(B1)=f
*
(B2), atuncif*(f
*(B1))=f*(f*(B2)) '1P(N) (B1)=1P(N) (B2)'B1=B2, adic! f
* esteinjectiv!.
(iv))(v). Fie A%M ; a ar!ta c! f(1MA)
5/24/2018 Lectii de Algebra
35/253
35
(vi))(i). Presupunem prin absurd c!exist!y0(N a.. f(x),y0,
pentru orice x(M. Definim g, h : N:{0, 1} astfel : g(y)=0, pentru orice
y(N $i ( )
{ }
=
-
= 0
0
1
0
yypentru
yNypentru
yh
Evident g,h $i totu$i g5f=h5f, ceea ce este absurd, deci f estesurjectiv!.
(i))(vii). Pentru fiecare y(N alegnd cte un singur
xy(f-1 ({y}), obinem astfel o funcie g : N:M, g(y)=xy , pentru orice
y(N , ce verific!n mod evident relaia f5g=1N.
(vii))(i). Pentru y(N, scriind c! f(g(y))=y, rezult! y=f(x), cux=g(y)(M, adic!f este surjectiv!.2
Din propoziiile precedente obinem imediat:
Corolarul 3.9. Cu notaiile de la Propoziia 3.7., urm%toareleafirmaii sunt echivalente:
(i) f este bijectiv%(ii) f(1MA)=1N f(A), ;A(P(M)(iii) f*(i f
*sunt bijective
(iv) Exist%o funcie g:N:M a.. f5g=1N (i g5f=1M.
Propoziia 3.10. Fie M o mulime finit%(i f:M:M o funcie.Urm%toarele afirmaii sunt echivalente:
(i) f este injectiv%(ii) f este surjectiv%(iii) f este bijectiv%.
Demonstra#ie. Vom demonstra urm!toarele implicaii:
(i))(ii))(iii))(i).
(i))(ii). Dac!f este injectiv!, atunci f(M) $i M au acela$i num!r
de elemente $i cum f (M)%M rezult! c! f (M)=M , adic! f este $isurjectiv!.
5/24/2018 Lectii de Algebra
36/253
36
(ii))(iii). Dac! f este surjectiv!, atunci pentru orice element
y(M va exista un unic element xy(M a.. f(xy)=y (c!ci n caz contrar arrezulta contradicia c!M ar avea mai multe elemente dect M), adic!f
este $i injectiv!.(iii))(i). Evident. 2
Propoziia 3.11. Fie M (i N dou%mulimi avnd m, respectivn elemente. Atunci:
(i) Num%rul funciilor definite pe M cu valori n N este egalcu nm
(ii) Dac%m=n, atunci num%rul funciilor bijective de la M laN este egal cu m!
(iii) Dac%m,n, atunci num%rul funciilor injective de la M
la N este egal cu mnA
(iv) Dac%m-n, atunci num%rul funciilor surjective de la M
la N este egal cu mn ( ) ( ) ( ) 1121 1...21 ---+--+-- nnnm
n
m
n CnCnC .
Demonstra#ie.(i). Facem inducie matematic! dup! m; dac!
m=1, mulimea M va avea un singur element $i este clar c!vom avean=n1 funcii de la M la N. Presupunem afirmaia adev!rat! pentrumulimile M ce au cel mult m-1 elemente.
Dac!M este o mulime cu n elemente, putem scrie M=M3/{x0},
cu x0(M iar M3submulime a lui M cu m-1 elemente.
Pentru orice y(N $i g : M3:N funcie, considernd
f g, y : M:N, f g, y (x)=g(x) dac! x(M3 $i y dac! x=x0 , deducem c!
oric!rei funcii g: M3:N i putem asocia n funcii distincte de la M la N
ale c!ror restricii la M3sunt egale cu g. Aplicnd ipoteza de inducie
pentru funciile de la M3 la N, deducem c!de la M la N se pot defininnm-1=nm funcii.
(ii). Facem inducie matematic!dup!m; dac!m =1, mulimileM $i N vor avea cte un singur element $i vom avea o singur!funcie
bijectiv!de la M la N.
Presupunem afirmaia adev!rat!pentru toate mulimile M3$i N3ambele avnd cel mult m-1 elemente $i fie M $i N mulimi avnd fiecare
5/24/2018 Lectii de Algebra
37/253
37
cte m elemente. Scriind M=M3/{x0}, cu x0(M iar M3submulime a lui
M cu m-1 elemente, atunci orice funcie bijectiv! f:M:N este perfect
determinat! de valoarea f(x0)(N precum $i de o funcie bijectiv!
g:M3:N3,unde N3=N \ {f (x0)}. Deoarece pe f (x0) l putem alege nm moduri iar pe g n (m-1)! moduri (conform ipotezei de inducie)
deducem c!de la M la N putem defini (m-1)!.m =m! funcii bijective.
(iii). Dac!f:M:N este injectiv!, atunci lund drept codomeniu
pe f(M)%N, deducem c!f determin!o funcie bijectiv! f :M:f(M),
f (x)=f(x), pentru orice x(M, iar f(M) are m elemente. Reciproc, dac!
vom alege n N o parte N3a sa cu m elemente, atunci putem stabili m!funcii bijective de la M la N3 (conform cu (ii)). Cum num!rul
submulimilor N3ale lui N care au m elemente este egal cu mnC , rezult!
c!putem construi m! . mnmn AC = funcii injective de la M la N.
(iv). S!consider!m M={x1, x2, ...,xm}, N={y1, y2, ...,yn} iar Mimulimea funciilor de la M la N a.. yi nu este imaginea nici unuielement din Mi, i=1,2,...,n.
Astfel, dac!not!m prin nmF mulimea funciilor de la M la N,
mulimea funciilor surjective nmS de la M la N va fi complementara
mulimii M1/ M2/.. .../ Mn dinn
mF , deci conform Propoziiei 1.7.avem egalit!ile (1):
( ) I I II I
UU
n
n
nkjikji
nji
ji
n
i
i
mn
i
i
mn
i
i
n
m
n
m
MMMMMM
MMMnMnMFS
....1.... 211
1111
-++-
-+-=-=-=
5/24/2018 Lectii de Algebra
38/253
38
Deoarece sumele ce apar n (1) au, respectiv, 1nC ,2nC , ...,
nnC
temeni egali, innd cont de acest lucru $i de (2), relaia (1) devine:
n
mS =m
n ( ) ( ) ( )1121
1...21 --
-+--+--n
n
nm
n
m
n CnCnC . 2
Pentru o mulime nevid!M $i A(P(M) definim 0A: M:{0,1},
0A(x)=
Axdaca
Axdaca
1
0
pentru orice x(M. Funcia 0Apoart!numele defunc#ia caracteristicamulimii A.
Propoziia 3.12. Dac%A, B(P(M), atunci:
(i) A=B'.A=.B
(ii) .-=0, .M=1
(iii) .A=B=.A.B , .A2=.A
(iv) .A>B=.A+.B - .A.B
(v) .A \ B=.A - .A .B , ACMj =1-.A
(vi) .A /B=.A+.B - 2.A.B.
Demonstra#ie.
(i).,,).Evident!.
,,9. Presupunem c!0A=0B $i fie x(A; atunci 0A (x)=
=0B(x)=1, deci x(B, adic!A%B. Analog B%A, de unde A=B.
(ii). Evident.
(iii). Pentru x(M putem avea urm!toarele situaii: (x*A, x*B)
sau (x(A, x*B) sau (x*A, x(B) sau (x(A, x(B). n fiecare situaie
n parte se verific!imediat relaia 0A=B (x)=0A (x)0B(x).
Cum A=A=A )0A =0A0A=0A2.
(iv), (v). Asem!n!tor cu (iii).
(vi). Avem0A 1B =0( A \ B )>( B \ A )=0A \ B + 0B \ A-0A \ B 0B \ A =
5/24/2018 Lectii de Algebra
39/253
39
=0A- 0A0B+0B - 0B0A 0(A \ B ) =( B \ A )=0A +0B -20A0B
deoarece (A \ B )=(B \ A )=-. 2
Fie M o mulime oarecare iar ,(Echiv (M). Funciap,,M : M:M / , definit! prin p,,M (x)=[x], pentru orice x(M estesurjectiv!$i poart!numele desurjec#ia canonic.
Propoziia 3.13. Fie M (i N dou% mulimi pe care s-au
definit relaiile de echivalen%*, respectiv *? (i f : M:N o funcieavnd proprietatea:
(x, y)(*)( f(x), f(y))(*?, ;x, y(M.Atunci exist%o singur%funcie f : M/*:N/*a. . diagrama:
fM N
p M,* pN,*?
f
M/* N/*
este comutativ% (adic% pN, *?5f= f 5pM, * , unde pM, * , pN, *, suntsurjeciile canonice).
Demonstra#ie. Pentru x(M, vom nota prin [x], clasa deechivalen!a lui x modulo relaia ,.
Pentru x(M, definim: f ([x],)=[f(x)],.
Dac!x, y(M a.. [x],=[y],'(x, y)(,)[f (x), f (y)](,?(dinenun) )[f (x)],?=[f (y)],?, adic! f este corect definit!.
Dac!x(M, atunci ( f 5pM, ,)(x)= f (pM, ,(x)) =
= f ([x],)=[f[x]],?=pN, ,?(f (x))=(pN, ,?5f)(x), adic!pN, ,?5f= f 5pM, ,.
Pentru a demonstra unicitatea lui f , s! presupunem c! ar mai
exista o funcie f ?: M / ,:N / ,a..pN, ,?5f= f ?5pM, ,, $i fie x(M.
Atunci f ?([x],)= f ?(pM, ,(x))=( f ?5pM, ,)(x)=(pN, ,? 5f)(x) ==pN, ,?(f(x)) =[f (x)]@?= f ?([x],), de unde deducem c! ff= ?. 2
5/24/2018 Lectii de Algebra
40/253
40
Propoziia 3.14. Fie M (i N dou% mulimi iar f :M:N ofuncie ; not%m prin *f relaia binar%de pe M definit%astfel:
( x, y )(*f 'f(x)=f(y) (x, y(M).Atunci:(i) *feste relaie de echivalen%pe M(ii) Exist%o unic%funcie bijectiv% f : M / *f:Im ( f ) a..
i5 f 5FM
p r, =f, i:Im ( f ) :N fiind incluziunea.
Demonstra#ie. (i). Evident! (relaia de egalitate fiind o
echivalen! pe M). (ii). P!strnd notaia claselor de echivalen! de laPropoziia 3.13., pentru x(M definim )]([
fxf r =f(x). Funcia f este
corect definit! c!ci dac! x, y(M $i [ ] [ ]ff
yx rr = ' (x, y)(, f '
f(x)=f(y) (de aici rezult!imediat $i injectivitatea lui f ) . Cum f este
n mod evident $i surjectiv!, deducem c! f este bijectiv!. Pentru a
proba unicitatea lui f , fie f1: M /,f:Im (f ) o alt!funcie bijectiv!a..
i5f15 FMp r, =f $i x(M. Atunci, (i5f15 FMp r, )(x)=f(x) '
' )]([1 fxf r =f(x)' )]([1 fxf r =f(x)= )]([ fxf r , adic! f1= f . 2
Propoziia 3.15. Fie M o mulime finit% cu m elemente.Atunci num%rul Nm, kal relaiilor de echivalen%ce pot fi definite pe
M a.. mulimea ct s% aib% k elemente ( kAm ) este dat de
formula:
( ) ( ) ( ) ( )[ ]1121, 1...21!1 ---+--+--= kkkmkmkmkm CkCkCkkN .
Deci num%rul relaiilor de echivalen% ce pot fi definite pe
mulimea M este dat de formula N=Nm, 1+Nm, 2+...+Nm, m.
Demonstra#ie. Dac! , este o relaie de echivalen!,
,(Echiv (M), atunci avem surjecia canonic!p M, ,: M:M / ,.
5/24/2018 Lectii de Algebra
41/253
41
Dac!n general, f : M:N este o funcie surjectiv!, atunci cumam stabilit n cazul Propoziiei 3.14., aceasta d! na$tere la urm!toarea
relaie de echivalen!de pe M : (x, y)(,f'f(x)=f(y). Mai mult, dac!
g : N:N? este o funcie bijectiv!atunci relaiile ,f$i ,g5f coincid c!ci(x,y)(,g5f'(g5f)(x)=(g5f)(y)'g(f(x))=g(f(y))'f(x)=f(y)'
'(x, y)(,f.Deci, dac! N are k elemente, atunci k! funcii surjective de la
M la N vor determina aceia$i relaie de echivalen! pe M. Lund n
particular N=M/,$i innd cont de Propoziia 3.11. deducem c!
( ) ( ) ( ) ( )[ ]1121, 1...21!1 ---+--+--= k
k
km
k
m
k
m
kmCkCkCkkN . 2
Propoziia 3.16. Fie M o mulime nevid%. Atunci funciacare asociaz%unei relaii de echivalen%definite pe M partiia lui Mdat%de relaia de echivalen%este bijectiv%.
Demonstra#ie.Fie Part(M) mulimea partiiilor lui M.
Vom nota prin f : Echiv (M):Part (M) funcia ce asociaz!fiec!rei relaii de echivalen!,de pe M, partiia lui M dat!de clasele de
echivalen!modulo ,: f(,)={[x]@|x(M } .
Definim g : Part (M):Echiv(M) astfel : dac!P=(Mi)i(I esteo partiie a lui M, definim relaia g(P) pe M astfel :
(x, y )(g(P)'exist!i(I a.. x, y(Mi.Reflexivitatea $i simetria lui g(P) sunt imediate. Fie acum (x, y),
(y, z)(g(P). Exist!deci i1, i2(I a. . x, y( 1iM $i y, z( 2iM ; dac!i1,i2ar rezulta c! I
21 iiMM ,- (c!ci ar conine pe y), ceea ce este absurd .
Deci i1=i2=i $i astfel x, z(Mi , adic! (x, z) g(P) de undeconcluzia c! g (P) este $i tranzitiv!, deci g(P)(Echiv(M), funcia gfiind astfel corect definit!.
S! ar!t!m c! dac! x(Mi , atunci clasa de echivalen! x
modulo g (P) este egal! cu Mi. ntr-adev!r, y(Mi ' (x, y)(g(P) 'y(x 'Mi=x .
5/24/2018 Lectii de Algebra
42/253
42
Deducem astfel c! g este de fapt inversa lui f, adic! f este
bijectiv!. 2
Suntem acum n m!sur! s! facem anumite preciz!ri legate demul#imea numerelor naturale.
Definiia 3.17. Numim triplet Peano un triplet ( N, 0, s )
unde N este o mulime nevid%, 0(N iar s:N+N este o funcie astfelnct sunt verificate axiomele :
P1: 0*s( N )P2: s este o funcie injectiv%
P3 : dac% P%N este o submulime astfel nct 0(P (i(n(P)s(n)(P ), atunci P=N .
n cele ce urmeaz!, accept!m ca axiom! existena unui tripletPeano (cititorului dornic de aprofundarea acestei chestiuni irecomand!m lucrarea [16] ) .
Lema 3.18. Dac% ( N, 0, s ) este un triplet Peano, atunci
N={0}/s(N).
Demonstra#ie Dac!not!m P={0}/s(N), atunci P%N $i cum P
verific!P3, deducem c!P=N .2
Teorema 3.19. Fie ( N, 0, s ) un triplet Peano iar ( NB, 0B, s B)
un alt triplet format dintr-o mulime nevid%NB, un element 0B(NB(i o funcie sB:NB+NB. Atunci :
(i) Exist%o unic% funcie f:N+NBastfel nct f(0) = 0B, iardiagrama
5/24/2018 Lectii de Algebra
43/253
43
N f NB
s sB
N f
NB
este comutativ%(adic% f 5s = sB5f )
(ii) Dac% ( NB, 0B, sB) este un triplet Peano, atunci f estebijecie.
Demonstra#ie (i). Pentru a proba existena lui f, vom considera
toate relaiile R%NNBa.. :
r1: (0, 0B)(R
r2 : Dac! (n, nB)(R, atunci (s(n), sB(nB))(R iar prin R0 vomnota intersecia acestor relaii .
Vom demonstra c!R0 este o relaie funcional!$i astfel f va fi
funcia ce va avea drept grafic pe R0(astfel, din (0, 0B)(R0vom deduce
c! f (0)=0B iar dac! n(N $i f (n)=nB(NB, (n , nB)(R0, deci (s(n),
sB(nB))(R0, adic!, f(s(n))=sB(nB)=sB(f (n)).Pentru a demonstra c! R0 este o relaie funcional!, vom
demonstra c!pentru orice n(N, exist!nB(NBa. . (n, nB)(R 0iar dac!
pentru n(N $i nB, nBB(NB avem (n, nB)(R0 $i (n, nBB)(R0 , atuncinB=nBB.
Pentru prima parte, fie
P={n(N | exist!nB(NBa. . (n, nB)(R0 }%N.
Cum (0, 0B)(R0 deducem c! 0(P. Fie acum n(P $i nB(NB a..
(n, nB)(R0. Din definiia lui R0 deducem c!(s(n), sB(nB))(R0; obinem
c!s(n)(P $i cum (N, 0, s) este triplet Peano, deducem c!P=N.
Pentru a doua parte, fie
5/24/2018 Lectii de Algebra
44/253
44
Q={n(N : dac!nB, nBB(N B$i (n, nB), (n, nBB)(R0 )nB=nBB}%N
$i s!demonstr!m la nceput c!0(Q.
n acest sens, vom demonstra c!dac!(0, nB)(R0atunci nB=0B.Dac! prin absurd, nB/0B, atunci vom considera relaia
R1=R0 C{(0, nB)}%NNB. Din nB/0B deducem c! (0, 0B)(R1 iar dac!
pentru m(NBavem (n, m)(R1 , atunci (n, m)(R0$i (n , m) /(0, nB).
Astfel (s(n), sB(m))(R0 $i cum (s(n), sB(m))/(0, nB) (c!ci s(n) / 0
conform cu P1), deducem c!(s(n), sB(m))(R1 . Cum R1verific!r1$i r2ar
trebui ca R0%R
1 absurd (c!ci R
1este inclus!strict n R
0).
Pentru a proba c!0(Q, fie nB, nBB(NBa. . (0, nB), (0 , nBB)(R0.
Atunci, innd cont de cele stabilite mai sus, deducem c! nB=nBB=0B,
deci 0(Q.
Fie acum n(Q $i n B(N Ba. . (n, nB)(R0 ; vom demonstra c!
dac! (s(n), nBB)(R0, atunci nBB=sB(nB). S!presupunem prin absurd c!
nBB/ sB(nB) $i s! consider!m relaia R2 =R0 C{(s (n), nBB)} . Vomdemonstra c!R2verific!r1$i r2.
ntradev!r, (0, 0B)(R2 ( c!ci 0 / s(n) ) iar dac! (p, pB)(R2 ,
atunci (p, pB)(R0$i (p, pB)/( s(n), nBB).
Deducem c!(s(p), sB(pB))(R0$i dac!presupunem (s(p), sB(pB))=
=(s(n), nBB), atunci s(p) =s(n), deci p=n. De asemenea, sB(pB)=nBB.
Atunci (n, nB)(R0 $i (n, pB)(R0 iar cum n(Q ) nB=pB, decinBB=sB(pB)=sB(nB), ceea ce contrazice faptul c! nBB/s(nB). Prin urmare,
(s(p), sB(pB))/(s(n), nBB),ceea ce ne arat!c!(s(p), sB(pB))(R2 , adic!R2
satisface r1$i r2 . Din nou ar trebui ca R0+R2 absurd !.
Deci (s (n), nBB)(R0 ) nBB=sB(nB) astfel c! dac! r, s (N B $i
(s(n), r), (s(n), s )(R0, atunci r = s = sB(n), adic!s(n)(Q, deci Q=N.
Pentru a proba unicitatea lui f, s! presupunem c! mai exist!fB:N.NBa.. fB(0)=0B$i sB(fB(n))=fB(s(n)) pentru orice n(N.
5/24/2018 Lectii de Algebra
45/253
45
Considernd P={n(N | f(n)=fB(n)}%N, atunci 0(P iar dac!
n(P (adic! f(n)=fB(n)), atunci sB(f(n))=sB(fB(n)))f(s(n))=
=fB(s(n)))s(n)(P $i atunci P=N, adic!f=fB.
(ii). S!ar!t!m la nceput c!f este injectiv!. Pentru aceasta vom
considera P={n(N | dac! m(N $i f(m)=f(n))m=n}%N $i s!
demonstr!m la nceput c!0(P. Pentru aceasta fie m(N a. . f(0)=f(m)$i s! demonstr!m c! m=0. Dac! prin absurd m/0, atunci m=s(n) cu
n(N iar egalitatea f(m)=f(0) devine f(s(n))=f(0)=0B, de unde
sB(f(n))=0B,ceea ce este absurd deoarece prin ipotez! (NB, 0B, sB)esteun triplet Peano.
Fie acum n(P; pentru a demonstra c! s(n)(P, fie m(N a..f(m)=f(s(n)).
Atunci m/0 (c!ci n caz contrar ar rezulta c!
0B=f(0)=f(s(n))=sB(f(n)), absurd !), deci conform Lemei 3.18., m=s(p)
cu p(N iar egalitatea f(m)=f(s(n)) devine
f(s(p))=f(s(n))'sB(f(p))=sB(f(n)), adic! f(p)=f(n) $i cum n(P, atunci
n=p $i astfel m=s(p)=s(n).Pentru a demonstra surjectivitatea lui f s!consider!m
PB={nB(NB| exist!n(N a. . nB=f (n)}%NB.
Cum f(0)=0Bdeducem c!0B(PB. Fie acum nB(PB; atunci exist!
n(N a.. nB=f (n). Deoarece sB(nB)=sB(f(n))=f(s(n)), deducem c!
sB(nB)(PB$i cum tripletul (NB, 0B, sB)este un triplet Peano, deducem c!
PB=NB, adic!f este $i surjectiv!, deci bijectiv!. 2Observaia 3.20. Conform Teoremei 3.19. (cunoscut! $i sub
numele de teorema de recuren#) un triplet Peano este unic pn! la obijecie.
n cele ce urmeaz!vom alege un triplet Peano oarecare (6, 0, s)
pe care l vom fixa ; elementele lui 6le vom numi numere naturale.Elementul 0 va purta numele dezero.
Vom nota 1=s(0), 2=s(1), 3=s(2), e.t.c., astfel c! 6={0, 1, 2, }.Funcia s poart! numele de func#ia succesor . Axiomele P1 P3 sunt
5/24/2018 Lectii de Algebra
46/253
46
cunoscute sub numele de axiomele lui Peano(axioma P3poart!numelede axioma induc#iei matematice).
Pe parcursul acestei lucr!ri vom construi pornind de la o
mulime 6 a numerelor naturale mulimile numerelor ntregi ,ra#ionale ", reale #$i complexe$, rezultnd astfel rolul fundamental
pe care l joac!n matematic!mulimea numerelor naturale.
4.Nucleul (i conucleul unei perechi de funcii
Definiia 4.1. Fie f, g : A:B o pereche de funcii. O pereche(K, i) format%dintr-o mulime K (i o funcie i : K:A se nume(tenucleul perechii (f, g) dac% sunt verificate urm%toarele dou%condiii:
(i) f5i=g5i
(ii) Pentru oricare alt dublet (K3, i3) cu K3 mulime (i
i3:K3:A a.. f5i3= g5i3 exist%o unic%funcie u : K3:K a. . i5u=i3.
Teorema 4.2. Pentru orice pereche de funcii f, g : A:Bexist%un nucleu al perechii (f, g) unic pn%la o bijecie (unicitatea
nseamn%c%dac%(K, i) (i (K3, i3)sunt dou%nuclee pentru perchea
(f, g) atunci exist%o bijecie u : K:K3a.. i35u=i ).
Demonstra#ie. S! prob!m la nceput existena nucleului $i
pentru aceasta fie K={x(A4f(x)=g(x)} iar i : K:A incluziunea (Kput`nd fi chiar -).
n mod evident f5i=g5i. Fie acum (K3, i3) cu i3 : K3:A a. .
f5i3=g5i3. Pentru a(K3, cum f (i3(a))=g (i3(a)) deducem c! i3(a)(K.
Definim atunci u:K3:K prin u(a)=i3(a), pentru orice a(K3$i este clar
c!i5u=i3.
Dac! u3:K3:K este o alt! funcie a.. i5u3=i3, atunci pentrua(K3avem i(u3(a))=u(a), de unde u3(a)=i3(a)=u(a), adic!u=u3.
5/24/2018 Lectii de Algebra
47/253
47
S!prob!m acum unicitatea nucleului iar pentru aceasta fie (K, i)
$i (K3, i3)dou!nuclee pentru perchea (f, g).
Cum (K3, i3)este nucleul perechii (f, g) deducem existena unei
funcii u:K:K3 a.. i35u=i.Cum $i (K, i ) este nucleul perechii (f, g) deducem existena
unei funcii u3:K3:K a.. i5u3=i3.
Deducem imediat c! i35(u5u3)=i3 $i i5(u35u)=i. Cum $ii35 K1 =i3 $i i51K=i, innd cont de unicitatea din Definiia 4.1.,
deducem c!u5u3= K1 $i u35u=1K, adic!u este bijecie $i i35u=i . 2
Observaia 4.3. Vom nota ( K, i ) = Ker (f, g) (iar dac%nueste pericol de confuzie doar K=Ker (f, g)).
Definiia 4.4. Fiind dat% o pereche de funcii f, g :A:Bnumim conucleu al perchii (f, g) pereche (P, p) format% dintr-o
mulime P (i o funcie p:B:P ce verific% urm%toarele dou%
condiii :(i) p5f=p5g
(ii) Pentru oricare alt dublet (P 3, p3)cu P 3mulime (i
p3: B:P 3 a. . p35f= p35g , exist%o unic% funcie v :P:P 3a..
v5p=p3.
Teorema 4.5. Pentru orice pereche de funcii f, g : A:B
exist% un conucleu al perechii ( f, g ) unic pn% la o bijecie(unicitateanseamn%c%dac%(P, p) (i (P 3, p3) sunt dou%conuclee
pentru perchea (f, g), atunci exist%o bijecie v:P:P 3a.. v5p=p3).Demonstra#ie.Vom proba doar existena conucleului perechii
(f, g) deoarece unicitatea sa se probeaz!analog cu unicitatea nucleului.
Pentru aceasta fie ,={(f(x), g(x)) | x(A} (care este o relaie
binar! pe B) iar relaia de echivalen! de pe B generat! de , (ac!rei construcie este descris!n Teorema 2.11.). S!ar!t!m c!perechea( B / , p, B ) este un conucleu al perechii (f, g). Deoarece pentru
5/24/2018 Lectii de Algebra
48/253
48
orice x(A avem (f(x), g(x))( ,% deducem c! (f(x), g(x))(
adic!, p, B (f (x))=p, B(g(x)), deci p, B5f=p, B5g.
Fie acum (B3, p3) cu B3 mulime $i p3:B:B3 a.. p35f=p35g.
Atunci pentru orice x(A, p3(f(x))=p3(g(x)), adic!(f(x), g(x))(,p(vezi
Propoziia 3.14.), deci ,%,p. Cum ,peste relaie de echivalen!pe Biar este cea mai mic!relaie de echivalen!de pe B ce conine pe ,
deducem c!%,p.
Conform Propoziiei 3.13. exist!o funcie 2: B/:B/,Pa..25p, B= Bpp ,r .Fie 3:B/,P:Im(p) bijecia a c!rei existen!ne este
asigurat! de Propoziia 3.14.. Avem c! p?=i?535 Bpp ,r , unde
i?:Im (p?):B?este incluziunea.
Dac!not!m v=i?5352, atunciv5
Bp ,r =(i5352)5 Bp ,r =(i353)5(25 Bp ,r )=(i353)5 Bpp ,r =
=i?5(35 Bpp ,r )=p?.
Dac! mai avem v?:B/:B? a.. v?5B
p ,r =p?, atunci
v?5B
p ,r = v5 Bp ,r $i cum Bp ,r este surjecie deducem c! v?=v
(conform Propoziiei 3.8.). 2
Observaia 4.6. Vom nota (B,B
p ,r )=Coker (f, g) sau
(B=Coker (f, g) dac%nu este pericol de confuzie).
5. Mulimi ordonate. Semilatici. Latici.
Definiia 5.1. Printr-o mul#ime ordonat nelegem undublet (A, ) format dintr-o mulime nevid% A (i o relaie binar%pe A notat%tradiional prin "" care este reflexiv%, antisimetric%(i tranzitiv%. Vom spune c% "" este o ordine pe A.
Pentru x, y A vom scrie x < y dac% x y , x y.Dac% relaia "" este doar reflexiv% (i tranzitiv%, vom spunedespre ea c% este o ordine par#ial sau c% (A, ) este o mulimepar#ial ordonat.
5/24/2018 Lectii de Algebra
49/253
49
Dac%pentru x, yA definim x y dac%(i numai dac%y x obinem o nou%relaie de ordine pe A. Dubletul (A, ) lvom nota prin A (i spunem c%mulimea ordonat% A este dualamulimii A.
Fie ( ),A o mulime parial ordonat! iar r o relaie deechivalen! pe A. Vom spune despre r c! este compatibil! cu
preordinea de pe A dac!pentru oricare elemente x , y , z, t din Aavem implicaia ( ) ( ) rr tzyx ,,, $i .tyz
Dac! r este o relaie de echivalen! pe A compatibil! cu
preordinea , atunci pe mulimea ct A/r se poate defini o ordineparial!astfel :
rr][][ yx 'exist!
r][xz $i
r][yt a.. tz ; vom
numi aceast!ordine parial!preordinea ct.
n cele ce urmeaz! prin (A,A) vom desemna o mulimeordonat!.
Cnd nu este pericol de confuzie prin mulime ordonat!vom specifica numai mulimea subiacent! A (f!r! a mai pune n
eviden!relaia A, aceasta subnelegndu-se ).
Definiia 5.2. Fie m, M A (i S A, S .Vom spune c%:i) m este minorant pentru S dac%pentru orice sS,
m s (n caz c% exist%, prin inf (S) vom desemna cel mai mareminorant al lui S)
ii) M este majorant pentru S dac% M este minorantpentru S n A, adic%pentru orice sS, s M (n caz c%exist%,prin sup (S) vom desemna cel mai mic majorant al lui S).
Dac! S={s1, s2, ..., sn}%A atunci vom notainf (S)= s1Ds2D...Dsn iar sup (S)= s1Es2E..Esn (evident, n cazul ncare acestea exist!).
Ordinea "" de pe A se zice totaldac!pentru orice a,bA, a b sau b a; o submulime total ordonat!a lui A poart!numele de lan#.
Pentru a, bA vom spune c! b urmeaz pe a (sau c! a
este urmatde b) dac! a < b iar pentru a c b avem a=c sau c=b;vom utiliza n acest caz notaia a b.
5/24/2018 Lectii de Algebra
50/253
50
Pentru a, b A vom nota:
(a, b)={x(A4a
5/24/2018 Lectii de Algebra
51/253
51
y iIiA
prin x y dac! $i numai dac! xAi, yAj $i i< j sau
{x, y}Ak iar x y n Ak. Mulimea ordonat! iIiA
definit!mai
sus poart!numele desuma ordinala familiei (Ai) Ai(I.Dac!I={1, 2,..., n}convenim s!not!m
iIiA
= A1A2...An.
Dac!(Pi , )1AiAn este o familie finit!de mulimi ordonate,atunci P=
ni
1Pi devine n mod canonic mulime ordonat!, definind
pentru x=(xi)1AiAn, y=(yi)1AiAn(P, x y exist! 1AsAn a..x1=y1, , xs-1=ys-1$i xs
5/24/2018 Lectii de Algebra
52/253
52
ix) mrginit dac% este simultan inf (i sup - m%rginit%(adic% 0 a 1 pentru orice a A); n acest caz 0 se zice elementini#ial (sauprim) al lui A iar 1 elementfinal (sau ultim) al lui A
x) condi#ional complet dac% pentru orice submulimenevid%(i m%rginit%S a sa exist% inf (S) (i sup (S).
Observaia 5.4.1.Orice mulime ordonat! A care este inf-complet! este latice
complet!.ntr-adev!r, fie M A, M mulimea majoranilor lui M iar
m=inf (M). Cum pentru xM $i y M avem x y deducem c!
x m, adic! mM, astfel m = sup (M).2. Dac! A este o latice complet!, atunci inf () = 1 iar
sup () = 0.3. Pentru ca o latice L s!fie condiional complet!, este suficient
ca pentru orice submulime nevid!$i m!rginit! S a sa, s!existe doarinf (S) (sau sup (S)).
Definiia 5.5. Un element mA se zice:i) minimaldac% avnd aA a.. a m deducem c% m = aii) maximaldac%avnd aA a.. m a deducem c% m = aDac% A are 0, un element aA se zice atom dac% a 0
(i avnd xA a.. x a, atunci x = 0 sau x = a (deci 0 a).Definiia 5.6. Dac% A este inf-semilatice (respectiv sup-
semilatice) vom spune despre o submulime A3%A c% este inf-sub-semilatice (respectiv sup-sub-semilatice), dac% pentru oricare dou%elemente a, b(A3avem aDb(A3(respectiv aEb(A3).
Dac% A este latice, A3%A se va zice sublatice,dac%pentru
oricare dou%elemente a, b(A3 avem aDb, aEb(A3.Exemple.
1. Fie 6 mulimea numerelor naturale iar "" relaia de
divizibilitate pe 6. Atunci "" este o relaie de ordine pe 6. Fa!deaceast!ordine 6 devine latice n care pentru m, n 6, m n = cel
5/24/2018 Lectii de Algebra
53/253
53
mai mare divizor comun al lui m $i n iar m n = cel mai mic multiplucomun al lui m $i n.
Evident, pentru relaia de divizibilitate, elementul 16 este
element iniial iar 06 este element final. Aceast! ordonare nu estetotal!deoarece dac!avem dou!numere naturale m, n prime ntre ele(cum ar fi de exemplu 2 $i 3) nu avem m 4n $i nici n m.
2. Dac! K este una din mulimile de numere 6, , " sau #,atunci Kcu ordonarea natural!este o latice, iar ordonarea natural!estetotal!.
3. Fie M o mulime iar P(M) mulimea submulimilor lui M.
Atunci (P (M), ) este o latice complet! cu prim $i ultim element(respectiv $i M).
Fie acum A, A3dou!mulimi ordonate (cnd nu este pericol deconfuzie convenim s!not!m prin "" ambele relaii de ordine de pe A$i A3) $i f:A:A3o funcie.
Definiia 5.7. Vom spune despre f c% este morfism demul#imi ordonate (sau aplicaie izoton) dac% pentru orice a, bAcu a b avem f (a) f (b) (n anumite lucr%ri f se zice monotoncresctoare).
Dac% A, A3sunt inf (sup) - semilatici vom spune despre f c%este morfism de inf (sup) - semilatici dac% pentru oricare dou%
elemente a, b(A, f (a b) = f (a) f (b) (respectiv f (a b) ==f (a) f (b)).
Dac% A, A3 sunt latici, vom spune c% f este morfism delaticidac% f este simultan morfism de inf (i sup-semilatici (adic%pentru oricare dou% elemente a, b A avem f (a b) ==f (a) f (b) (i f (a b) = f (a) f (b)).
n mod evident, morfismele de inf (sup) - semilatici sunt aplica iiizotone iar dac!compunem dou!morfisme de acela$i tip obinem tot unmorfism de acela$i tip.
Dac! A, A3 sunt mulimi ordonate iar f:A:A3 este morfism demul#imi ordonate, atunci f se zice izomorfismde mul#imi ordonatedac!
5/24/2018 Lectii de Algebra
54/253
54
exist! g:A3:A morfism de mulimi ordonate a.. f5g=1A3 $i g5f=1A.Acest lucru revine la a spune de fapt c! f este o bijecie. n acest caz
vom scrie AFA3.
Analog se define$te noiunea de izomorfism de inf (sup) -semilatici ca $i cea de izomorfism de latici.n continuare vom stabili felul n care mulimile preordonate induc
mulimi ordonate, iar pentru aceasta fie (A, ) o mulime parialordonat!.
Se verific! imediat c! relaia r definit! pe A prin:
( ) yxyx r, $i xy este o echivalen! pe A compatibil! cu
preordinea . Vom considera = A/r mpreun! cu preordinea ct(definit! la nceputul paragrafului) $i s!ar!t!m c!acest!preordine estede fapt o ordine pe (adic!reste $i simetric!).
ntr-adev!r, fie [ ] [ ]rr yx , a.. [ ] [ ]rr yx $i [ ] [ ]rr xy $i s!demonstr!m c! [ ] [ ]rr yx = . Atunci exist! [ ] ,, rxxx [ ]ryyy , a..
yx $i .xy
Avem ( ) ( ) ( ) ( ) r yyyyxxxx ,,,,,,, adic!
yyyyyyxxxxxxxx ,,,,,, $i yy .Din yxxx , $i yy deducem c! yx iar din
xyyy , $i xx deducem c! xy , adic! ( ) ryx, , astfel c![ ] [ ]rr yx = .
Astfel, surjecia canonic! AApA : este funcie izoton!.4innd cont de Propoziia 3.13. se verific! imediat faptul c!
mulimea ordonat! ct ( ),A mpreun! cu surjecia canonic!AApA : verific!urm!toarea proprietate de universalitate:
Pentru orice mul#ime ordonat ( ),B $i func#ie izotonBAf : existo unicaplica#ie izoton BAf : a.. .fpf A=o
Definiia 5.8. Fie A o inf-semilatice (i F %A o submulimenevid%a sa. Vom spune c%F este filtru al lui A dac% F este o inf-
sub-semi- latice (i pentru a, b A, dac% a b (i aF atunci bF.Vom nota prin F(A) mulimea filtrelor lui A.
5/24/2018 Lectii de Algebra
55/253
55
Noiunea dual! celei de filtru este aceea de ideal pentru o sup-semilatice. Mai precis avem:
Definiia 5.9. Fie A o sup-semilatice iar I A o submulimenevid%a sa. Vom spune c% I este un ideal al lui A dac% I este sup-sub-semilatice a lui A (i pentru orice a, bA cu a b, dac%bIatunci (i aI.
Vom nota prin I(A) mulimea idealelor lui A.
Observaia 5.10. Dac! A este latice, atunci noiunile de filtru$i ideal au definiii precise n A (innd cont de definiiile de mai sus,
c!ci A este simultan inf $i sup-semilatice); evident n acest cazA F(A)I(A).
Cum intersecia oric!rei familii de filtre (ideale) este de asemeneafiltru (ideal), putem vorbi de filtrul (idealul) generat de o mul#imenevid.
Dac! A este o inf(sup)-semilatice, pentru SA vom notaprin [S) ( (S]) filtrul(idealul) generat de S (adic! intersecia tuturorfiltrelor (idealelor) lui A ce conin pe S).
Propoziia 5.11. Dac% A este o inf-semilatice (i S A osubmulime nevid%a sa, atunci:
[S)={a(A4exist%s1, s2,.., sn(S a.. s1Ds2D..DsnAa}.
Demonstra#ie.Fie FS={a(A4exist! s1, s2 ,.., sn(S a..
s1Ds2D..DsnAa}. Se probeaz!imediat c! FS F(A) $i S FS, deci[S) FS.
Dac! F3(F(A) a.. S F3 atunci FS%F3 deci FS%.F3=[S),de unde[S)=FS.n
Dual se demonstreaz!:
Propoziia 5.12.Dac% A este o sup-semilatice (i SA este osubmulime nevid%a sa, atunci:
(S]={a(A4exist%s1, s2,.., sn(S a.. a s1s2..sn}.
5/24/2018 Lectii de Algebra
56/253
56
Astfel, (F(A),%) $i (I(A),%) sunt latici n care pentru F1, F2(F(A)
(respectiv I1, I2(I(A)) avem F1DF2=F1=F2 iar F1EF2=[F1>F2)
(respectiv I1DI2=I1=I2iar I1EI2=(I1>I2] ).
Dac! A este o inf (sup)-semilatice $i aA, vom nota prin [a)( (a]) filtrul (idealul) generat de {a}.
Conform celor de mai sus avem c!: [a)={x(A4aAx} $i
(a]={x(A4xAa} ([a), (a] poart! numele de filtrul (idealul) principalgenerat de a).
Teorema 5.13. Fie (A, ) o mulime ordonat%. Atunci Aeste izomorf% cu o mulime de submulimi ale lui A (ordonat% cuincluziunea).
Demonstra#ie. Pentru fiecare aA consider!mMa={x(A4xAa}%A. Deoarece pentru a, bA, a b avemMa Mb deducem c! asocierea a Ma pentru aA descrie
izomorfismul de mulimi ordonate dorit.n
Definiia 5.14.i) O mulime ordonat%n care orice submulime nevid%a sa
are un element iniial se zice bine ordonat(evident o mulime bineordonat%este inf-complet%(i total ordonat%)
ii) O mulime ordonat% n care orice submulime totalordonat% a sa are un majorant (minorant) se zice inductiv
(coinductiv) ordonat%.Dup!cum vom vedea n 9 (6, ) este un exemplu de mulime
bine ordonat!.n cele ce urmeaz!, accept!m c!pentru orice mulime M este
verificat!axioma alegerii:Exist o func#ie s : P(M) M a.. s(S)S pentru orice
submul#ime nevid S a lui M.n continuare, reamintim un rezultat datorat lui Bourbaki $i cteva
corolare importante ale acestuia (pentru demonstraii recomand!mcititorului lucrarea [23]).
5/24/2018 Lectii de Algebra
57/253
57
Lema 5.15. (Bourbaki). Dac% (A, ) este o mulime nevid%,inductiv ordonat%(i f : A A este o aplicaie a.. f (a) a pentruorice aA, atunci exist% uA a.. f (u) =u.
Corolar 1 (Principiul lui Hansdorf de maximalitate). Oricemulime ordonat%conine o submulime total ordonat%maximal%.
Corolar 2 (Lema lui Zorn). Orice mulime nevid% inductiv(coinductiv) ordonat%are cel puin un element maximal (minimal).
Corolar 3 (Principiul elementului maximal (minimal)). Fie
(A, ) o mulime inductiv (coinductiv) ordonat%(i aA. Exist%unelement maximal (minimal) ma A a.. a ma (maa).
Corolar 4 (Lema lui Kuratowski). Orice submulime totalordonat%a unei mulimi ordonate este cuprins% ntr-o submulimetotal ordonat%maximal%.
Corolar 5 (Teorema lui Zermelo). Pe orice mulime nevid%
A se poate introduce o ordine fa%de care A este bine ordonat%.
Corolar 6 (Principiul induc#iei transfinite). Fie (A, ) omulime bine ordonat% infinit% (i P o proprietate dat%. Pentru ademonstra c%toate elementele mulimii A au proprietatea P estesuficient s%demonstr%m c%:
(i) Elementul iniial 0 al lui A are proprietatea P(ii) Dac% pentru aA, toate elementele xA a.. x
5/24/2018 Lectii de Algebra
58/253
58
S!not!m c!exist!latici ce nu sunt modulare.ntr-adev!r, dac!vom considera laticea notat!tradiional prin N5:
1
c
b
a
0
observ!m c! a c, pe cnd a (b c) = a 0= a iar (a b) c=
=1c a, astfel c! c (b a) (c b) a, deci N5 nu este modular!.
Teorema 5.17. (Dedekind). Pentru o latice L urm%toareleafirmaii sunt echivalente:
(i) L este modular%(ii) Pentru orice a, b, cL, dac% c a, atunci a (b c) (a b)c(iii) Pentru orice a, b, cL avem ((ac) b) c = (ac) (bc)(iv) Pentru orice a, b, cL, dac%a c, atunci din a b =c b
(i ab= c b deducem c% a = c(v) L nu are sublatici izomorfe cu N5.
Demonstra#ie. Cum n orice latice, dac! c a, atunci(a b) c a (b c), echivalena (i) (ii) este imediat!.(i) (iii). Rezult!din aceea c! a c c.(iii) (i). Fie a, b, c L a.. a c. Atunci a = a c, deci(a b) c = ((a c) b) c = (a c) (b c) = a (b c).
5/24/2018 Lectii de Algebra
59/253
59
(i) (iv). Avem a = a (a b) = a (c b) = a (b c) ==(a b) c = (c b) c = c.(iv) (v) Evident (innd cont de observaia de mai nainte).
(v) (i) S!presupunem c! L nu este modular!. Exist!atunci a, b, cn L a.. a c, iar a (b c) (a b) c. S!observ!m c!bc x,adic!
x=x+r cu r(6*). Obinem atunci egalitatea:
( )( ) ( )( )
2
1
2
1 yxyxr
yrxyrx +++=+
+++++
de unde deducem c!
( )( ) ( )( )yxyxyrxyrx +++r+y. Alegnd y=r+y+s cu s(6* obinem c!( ) ( )( )
2
1
2
1 +++=+
- szszr
zz, unde z=x+r+y+1, lucru absurd
deoarece ( ) ( ) ( ) +=+-
5/24/2018 Lectii de Algebra
82/253
82
Corolar 10.5. 000 ccc = .
Propoziia 10.6. , * (i " sunt mulimi num%rabile.
Demonstra#ie.Se probeaz!imediat c!f::6
( )
5/24/2018 Lectii de Algebra
83/253
83
unde pentru orice k(6* bk*{0, 9, a k k }, atunci b*Im(f), adic! f nu
este surjectiv!. 2
Definiia 10.8. Vom spune despre o mulime M c% esteinfinit:
(i) n sens Dedekind, dac%exist%M3+M a.. M3GM(ii) n sens Cantor,dac%conine o submulime num%rabil%
(iii) n sens obi$nuit, dac% M HSn pentru orice n(6* (unde
Sn={1, 2, ..., n}) .
Teorema 10.9. Cele trei definiii ale mulimilor infinite dincadrul Definiiei 10.8. sunt echivalente dou!cte dou!.
Demonstra#ie. (i))(ii). Fie M o mulime infinit! n sens
Dedekind ; atunci exist!M3+M $i o bijecie f:M:M3. Cum M3+M,
exist! x0(M a.. x0*M3. Construim prin recuren! $irul de elemente
x1=f (x0), x2=f (x1 ), ..., xn=f (xn-1), ... $i s!ar!t!m c!funcia 0:6:M
0(n)=xnpentru orice n(6este injectiv!. Pentru aceasta vom demonstra
c!dac!n, n3(6, n,n3 , atunci 0 (n),0 (n3). Vom face lucrul acestaprin inducie matematic!dup!n.
Dac!n=0, atunci n3,0, de unde 0(0)=x0$i 0(n3)= ( )1-nxf (
(M3$i cum 0(0)= x0 *M3deducem c! 0(n3),0(0). S!presupunem
acum c!pentru orice n,m3 0(n),0(m3)$i s!alegem acum n3,n+1.
Dac!n3=0, atunci 0(n3)=0(0)= x0 *M3$i xn+1=f (xn ) (M3,deci
0(n+1),0(n3). Dac!n3,0, atunci 0(n3)= ( )1-nxf $i 0(n+1)=f (xn) .Cum n3-1,n, atunci 1-nx , xn $i cum f este injectiv! deducem c!
( )1-nxf ,f (xn), adic!0(n3),0(n+1). Rezult!deci c!0este injectiv!
$i deci 0(6) %M este o submulime num!rabil!.
(ii))(i). Fie M o mulime infinit! n sensul Cantor, adic!
exist!M3%M a.. M3G6(fie f :6:M3o funcie bijectiv!). Se observ!
imediat c! 0: M:M \ {f (0)} definit!prin
5/24/2018 Lectii de Algebra
84/253
84
( )( ) ( )
=+
=
Nncunfxdacanf
Mxdacaxx
1j
este bine definit!$i s!ar!t!m c!0este chiar bijecie.
Fie deci x, x3(M a.. 0(x) = 0(x3).
Deoarece M=M3/ (M \ M3) $i 0 (x) = 0 (x3), atunci x, x3(
(M3sau x, x3*M3. Dac!x, x3*M3,atunci n mod evident din 0(x) =
=0(x3) deducem c! x=x3. Dac! x, x3( M3, atunci dac! x=f(k),
x3=f(t) deducem c!f (k+1)=f (t+1), de unde k+1=t+1 'k=t )x=x3.S! ar!t!m acum c! 0 este surjectiv!. Pentru aceasta fie
y (M \ {f (0)} . Dac!y*M3atunci y=0 (y), iar dac!y(M3 , atunciy=f (n) cu n(6. Cum y,f (0), atunci n,0) n!1 deci putem scrie
y=f (n-1+1)=0(n-1).
(ii))(iii). Aceast! implicaie este evident! deoarece 6HSn
pentru orice n(6* .
(iii))(ii). Vom utiliza urm!torul fapt: dac! M este o mulime
infinit! n sens obi$nuit, atunci pentru orice n(6* exist! o funcie
injectiv!0:Sn:M.Vom proba lucrul acesta prin inducie matematic!referitor la n.
Pentru n=1 exist! o funcie injectiv! 0:S1:M (deoarece
M,). S!presupunem acum c!pentru n(6* exist!0:Sn:M injectiv!.
Cum am presupus c!M este infinit!n sens obi$nuit, atunci 0(Sn) ,M,
deci exist!x0(M a.. x0 *0(Sn).
Atunci y :Sn+1:M, ( )( )
+=
=10 nxpentrux
Sxpentruxx
njy este n mod
evident funcie injectiv!.
S!trecem acum la a demonstra efectiv implicaia (iii))(ii). Dinrezultatul expus anterior deducem c!:
Mk={0:Sk:M | 0este injecie},
pentru orice k(6*. Cum pentru k,k3 , Sk.Sk =, deducem c!Mk.Mk =. Conform axiomei alegerii aplicat! mulimii
5/24/2018 Lectii de Algebra
85/253
85
T={ Mk : k(6 }, exist! S%T a.. S.Mk, $i este format! dintr-unsingur element. Atunci M3= ( )U
SjjIm este o submulime num!rabil! a
lui M. 2
CAPITOLUL 2: GRUPURI
1. Operaii algebrice. Monoizi. Morfisme de monoizi.Produse directe finite de monoizi
Definiia 1.1. Fiind dat!o multime nevid!M, numim operatiealgebric(intern!) sau lege de compozi#ie (intern!) pe M orice funciej:MMM.
Pentru u$urina scrierii vom nota pentru x, yM pe j(x, y) (carese mai nume$te $i compusullui x cu y) prin xoy sau pur $i simplu prinxy (convenim s!spunem c!am notat operaia algebric!jmultiplicativ).
n anumite situaii folosim pentru j$i notaia aditiv,,+.
Exemple 1. Dac% T este o mulime nevid% iar M=P(T), ncapitolul precedent am definit pe M operaiile algebrice deintersecie, reuniune, diferen%(i diferena simetric%.
2. Dac% A este o mulime nevid% iar Hom(A)={f:AA},atunci pe Hom(A) avem operaia de compunere a funciilor:j : Hom(A) Hom(A) Hom(A), j(f, g) = fog pentru oricef, g Hom(A).
Pe parcursul acestei lucr%ri vom mai pune n eviden%altemulimi (i operaii algebrice pe acestea (inclusiv mulimile
numerelor ntregi , raionale ", reale #(i complexe $precum (ioperaiile de adunare (i nmulire pe acestea).
Definiia 1.2. Dac!M este mulime nevid!, vom spune despre ooperaie algebric!de pe M (notat!multiplicativ) c!este:
(i) comutativ dac!pentru oricare x, yM, xy=yx(ii) asociativ dac!pentru oricare x, y, zM, (xy)z=x(yz).
5/24/2018 Lectii de Algebra
86/253
86
Operaiile de intersecie, reuniune (i diferen% simetric%sunt exemple de operaii ce sunt simultan comutative (i asociative,pe cnd compunerea funciilor nu este operaie comutativ% fiind
ns%asociativ%.
Dac% o operaie algebric% de pe M este asociativ%, atuncipentru a scrie compunerea a trei elemente x, y, z din M (sau maimulte) nu mai este necesar s%folosim parantezele, astfel c%n loc s%scriem (xy)z sau x(yz) vom scrie xyz.
Pentru n elemente x1,,xn (n6) din M utiliz%m de multeori notaiile:
x1x2xn= =n
iix1 (cnd operaia algebric% asociativ% este
notat%multiplicativ) sau
x1+x2++xn = =
n
i
ix1
(cnd aceea(i operaie algebric%
asociativ%este notat%aditiv).
Dac% x1=x2==xn=x (i n6* convenim s% not%mx1x2xn=x
n
dac% operaia algebric% este notat% multiplicativ (ix1+x2++xn = nx dac%ea este notat%aditiv.
Definiia 1.3. Fie M o mulime nevid!pe care avem o operaiealgebric!. Vom spune c!un element eM este element neutru pentruoperaia algebric! respectiv! dac! pentru oricexM, xe = ex = x.
Observaia 1.4.1. Dac! o operaie algebric! de pe M ar avea dou! elemente
neutre e, eM, atunci ee=e (dac!gndim pe e element neutru) $i totee=e(dac!gndim pe e element neutru) astfel c!e=e.Deci, elementulneutru al unei operaii algebrice (dac!exist!!) este unic.
2. n cazul adopt!rii notaiei multiplicative pentru o operaiealgebric!, elementul s!u neutru (dac! exist!) va fi notat prin 1, iar n
cazul adopt!rii notaiei aditive acesta se va nota prin 0.
5/24/2018 Lectii de Algebra
87/253
87
Exemple 1. Dac% T-, atunci pentru operaiile algebrice.,/(i 7de pe M=P(T) elementele neutre sunt T,- (i respectiv
-.
2. Dac% A-, atunci pentru compunerea funciilor de peHom(A), 1A este elementul neutru.
Definiia 1.5. Un dublet (M, ) format dintr-o mulime nevid!M$i o operaie algebric! pe M se zice semigrup dac! operaia algebric!respectiv!este asociativ!. Dac!operaia algebric!are $i element neutru,semigrupul (M, ) se zice monoid. Dac! operaia algebric! estecomutativ!, monoidul se zice comutativ.
De multe ori, n cazul unui semigrup se specific% doarmulimea subiacent%M (far%a se mai specifica operaia algebric%de pe M; dac% este pericol de confuzie atunci (i aceasta trebuieneap%rat menionat%).
Exemple 1.Dac%T(i M=P(T), atunci (M,.), (M, /) (i(M,7) sunt monoizi comutativi.
2.Dac% A, atunci (Hom(A),o) este monoid necomutativ.Reamintim c%n 3 de la Capitolul 1 am introdus mulimea 6
a numerelor naturale. n continuare vom defini dou% operaii
algebrice pe 6: adunarea(notat%,,+) (i nmul#irea(notat%,,) nraport cu care 6devine monoid.
Teorema 1.6. Exist% o unic% operaie algebric% pe 6 pecare o vom nota prin + (i o vom numi adunarea numerelor
naturalea. . pentru orice m, n(6s%avem :A1: 0+m=mA2 : s(n)+m=s(n+m) .
Demonstra#ie. S!prob!m la nceput unicitatea $i pentru aceasta
s! presupunem c! mai exist!o operaie algebric!Jpe 6ce verific!
A1$i A2.Fie P={n(6| n+m=nJm, pentru orice m(6}%6.
5/24/2018 Lectii de Algebra
88/253
88
Din A1 deducem c! 0(P iar din A2 deducem c! dac! n(P,
atunci s(n)+m=s(n)Jm ' s(n+m)=s(nJm), ceea ce este adev!rat
deoarece s este injectiv!$i am presupus c!n(P. Deci P=6, adic!cele
dou!operaii coincid.Consider!m un element m (6 (pe care l fix!m) $i tripletul
(6, m, s); conform Teoremei 3.19 de la Capitolul 1 exist! o unic!
funcie fm:6:6a. . fm(0)=m $i s(fm(n))= fm(s(n)) pentru orice n(6.
Pentru n(6 definim n+m=fm (n). Atunci 0+m=fm(0)=m iar
s(n)+m= fm (s(n))=s (fm (n))=s( n+m ). 2
Observaia 1.7. Axiomele A1A2 poart! numele de axiomeleadunrii numerelor naturale.
Propoziia 1.8. Pentru orice m, n(6avem01A : m+0=m02A : n+s (m)= s(n+m) .
Demonstra#ie.Fie P={m(6:m+0=m }%6. Dac! n A1facem
pe m=0, deducem c! 0+0=0, adic! 0(P. Dac! m(P, (adic!m+0=m),
atunci s(m)+0=s(m+0)=s(m), adic! s(m)(P, deci P=6. Analog se
probeaz!$i a doua relaie.2
Propoziia 1.9. Dubletul (6, +) este monoid comutativ cuproprietatea de simplificare.
Demonstra#ie. Din cele stabilite anterior, deducem c! 0 esteelement neutru pentru adunarea numerelor naturale.
Pentru a proba comutativitatea adun!rii s!consider!m
P={n(6:n+m=m+n pentru orice m(6}%6.
Evident 0(P. Dac! n(P, adic! n+m=m+n pentru orice m(6,atunci s(n)+m=m+s(n) ' s(n+m)=s(m+n) ' n+m=m+n, ceea ce este
5/24/2018 Lectii de Algebra
89/253
89
adev!rat (deoarece s este injecie). Deducem c! P=6, adic! adunareanumerelor naturale este comutativ!.
Pentru a demonstra asociativitatea adun!rii
numerelor naturale, s!consider!mP ={n(6:(n+m)+p=n+(m+p) pentru orice m, p(6}%6.
Evident, 0(P. Fie acum n(P. Atunci(s(n)+m)+p=s(n+m)+p=s((n+m)+p) iar s(n)+(m+p)=s(n+(m+p)) $i cum
(n+m)+p=n+(m+p) deducem c!s(n)(P, adic!P=6.Pentru partea final!fie
P={p(6:dac!m+p=n+p )m=n}%6.Evident 0(P $i s!presupunem c!p(P. Atunci m+s(p)=n+s(p)
's(m+p)=s(n+p) ' m+p=n+p 'm=n (c!ci p(P), adic! s(p)(P $i
astfel din nou P=6. 2
Observaia 1.10. Dac!n(6, atunci s(n)=s(n+0)=n+s(0)=n+1.
Propoziia 1.11. Dac%m, n(6(i m+n=0, atunci m=n=0.
Demonstra#ie. Dac! m / 0 sau n / 0, atunci, conform Lemei
3.18 de la Capitolul 1 exist! p, q(6 a. . m = s(p) sau n = s(q). nprimul caz, obinem c!m+n = s(p)+n = s(p+n) /0 absurd ! $i analog
n al doilea caz. Deci m = n = 0 . 2
Propoziia 1.12. Exist% o unic% operaie algebric% pe 6
notat% (i numit%nmul#irea numerelor naturale a.. pentru orice
m, n(6s%avem :I1 : m0=0I2 : ms(n)=mn+m.
Demonstra#ie. Fie m(6fixat ; considernd tripletul (6, 0, fm ),unde fm:6:6 este definit! prin fm(n)=n+m pentru orice n(6, atunci
5/24/2018 Lectii de Algebra
90/253
90
conform Teoremei 3.19 de la Capitolul 1 exist! o unic! funcie
g m :6:6a.. gm(0)=0 $i fm5gm =gm 5s.Definim mn=gm(n) $i astfel m0=gm(0)=0 iar ms(n)=
=gm(s(n))=fm(gm(n))=fm(mn)=mn+m. Unici