lectii de algebra

249
5 CUPRINS pag. CAPITOLUL 1: NOŢIUNI PRELIMINARII . . . . . . . . . . . . . . 1 §1. Mulţimi. Operaţii cu mulţimi . . . . . . . . . . . . . . . . . . . . . . . 1 §2. Relaţii binare pe o mul ţime. Relaţii de echivalenţă . . . . . . . . . . 7 §3. Relaţii funcţionale. Noţiunea de funcţie. Clase de funcţii . . . . . 14 §4. Nucleul şi conucleul unei perechi de func ţii. . . . . . . . . . . . . 32 §5. Mulţimi ordonate. Semilatici. Latici. . . . . . . . . . . . . . . . . . . 35 §6. Latici.distributive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 §7. Complement şi pseudocomplement într-o latice. Algebre Boole. Algebre Boole generalizate. . . . . . . . . . . . . . . . . . . . . . . . . . 50 §8. Produsul direct (suma directă) a unei familii de mul ţimi . . . . . 56 §9. Numere cardinale. Operaţii cu numere cardinale. Ordonarea numerelor cardinale. . . . . . . . .. . . . . . . . . . . . . . . . 60 §10. Mulţimi numărabile. Mulţimi finite şi mulţimi infinite. . . . . . 66 CAPITOLUL 2: GRUPURI . . . . . . . . . . . . . . . . . . . . . . . . .71 §1. Operaţii algebrice. Monoizi. Morfisme de monoizi. Produse directe finite de monoizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 §2. Grup. Calcule într-un grup. Subgrup. Subgrup generat de o mulţime. Grup ciclic. Ordinul unui element într-un grup. . . . . . . . .83

Upload: aliarro

Post on 27-Oct-2015

71 views

Category:

Documents


6 download

DESCRIPTION

Lectii de Algebra

TRANSCRIPT

  • 5

    CUPRINS

    pag.

    CAPITOLUL 1: NOIUNI 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

    7. Complement i pseudocomplement ntr-o latice. Algebre Boole. Algebre Boole generalizate. . . . . . . . . . . . . . . . . . . . . . . . . . 50

    8. Produsul direct (suma direct) a unei familii de mulimi . . . . . 56

    9. Numere cardinale. Operaii cu numere cardinale. Ordonarea numerelor cardinale.. . . . . . . .. . . . . . . . . . . . .

    . . . 60 10. Mulimi numrabile. Mulimi finite i mulimi infinite. . .

    . . . 66 CAPITOLUL 2: GRUPURI . . . . . . . . . . . . . . . . . . . . .

    . . . .71 1. Operaii algebrice. Monoizi. Morfisme de monoizi. Produse directe finite de monoizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2. Grup. Calcule ntr-un grup. Subgrup. Subgrup generat de o mulime. Grup ciclic. Ordinul unui element ntr-un grup. . . . . . . . .83

  • 6

    3. Centralizatorul unui element ntr-un grup. Centrul unui grup. Teorema lui Lagrange. Indicele unui subgrup ntr-un grup. Ecuaia claselor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4. Subgrupuri normale. Factorizarea unui grup printr-un subgrup normal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .90 5. Morfisme de grupuri. Compunerea morfismelor de grupuri. Monomorfisme, epimorfisme, izomorfisme de grupuri. Nucleul i conucleul unei perechi de morfisme de grupuri. . . . . . . . . . . . . . .94 6. Teorema lui Malev. Grupul (, +). Subgrupurile lui (, +). Clasele de resturi modulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 7. Teoremele de izomorfism pentru grupuri. . . . . . . . . . . . . . . 108 8.Produse finite de grupuri. Teorema chinezeasc a resturilor. Numrul tipurilor de grupuri abeliene finite . . . . . . . . . . . . . . . . . . . . . 112 9. Teorema lui Cauchy pentru grupuri finite. Grupul diedral Dn de grad n. Structura grupurilor finite cu 2p elemente (p prim , p3) . . . . 118 10.Grupuri de permutri. Teorema lui Cayley. Grupurile Sn i An. .122 11. 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 i idealelor prin morfisme de inele. Produse directe de inele. . . . . . . 152

  • 7

    4. Factorizarea unui inel printr-un ideal bilateral. Teoremele de izomorfism pentru inele. . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 5. Corp. Subcorp. Subcorp prim . Morfisme de corpuri. Caracteristica unui corp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 6. 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 H al 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. .. . . . . . . . . . . . . . . . . . . . . . . . . . 219 4. Rdcini ale polinoamelor cu coeficieni ntr-un corp. Teorema fundamental a algebrei. Polinoame ireductibile. Rezolvarea ecuaiilor algebrice de grad 3 i 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 CAPITOLUL 5: ELEMENTE DE TEORIA CATEGORIILOR. . . . . . . . . . . . . . . . . . . . . . . 240 1. Definiia unei categorii. Exemple. Subcategorie. Duala unei categorii. Produs de categorii. Principiul dualizrii . . . . . . . . . . .240 2.Morfisme i obiecte remarcabile ntr-o categorie. Nucleul i conucleul unui cuplu de morfisme. . . . . . . . . . . . . . . . . . . . 244 3. 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 . . . . . . . . 279 7.Limita inductiv (proiectiv) a unui sistem inductiv (proiectiv). .287

  • 8

    8. Sume i produse fibrate . . . . . . . . . . . . . . . . . . . . . . . . . 294 9. Obiecte injective (proiective). Anvelope injective (proiective)..297 10. Categorii abeliene . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

    CAPITOLUL 6: MODULE I SPAII VECTORIALE. . . . . . 314 1. 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 de module. Imaginea, nucleul, coimaginea i conucleul unui morfism de module. Categoriile Mods(A) i Modd(A). Monomorfisme, epimorfisme, izomorfisme de module. Nucleul i conucleul unei perechi de 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. . . . . . .327 3. 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) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 4. Limite inductive i proiective n Mods(A). Limite inductive i proiective de morfisme de A-module. . . . . . . . . . . . . . . . . . . 360 5. Submodule eseniale i superflue. Submodule complement. Submodule nchise. Module injective. Grupuri divizibile. Anvelope injective. Module proiective. Anvelope proiective. Generatori, cogeneratori pentru Mods(A). . . . . . . . . . . . . . . . . . . . . . . . . 373 6. Produs tensorial de module. Produs tensorial de morfisme. Functorii SM i TN; transportul irurilor exacte scurte prin aceti functori. Comutativitatea produsului tensorial. Permutarea produsului tensorial cu sumele directe. Produs tensorial de module libere. Asociativitatea produsului tensorial. Proprietatea de adjuncie. Module plate. . . . . 396 7. Module libere de rang finit. Matricea de trecere de la o baz la alta. Formula de schimbare a coordonatelor unui element la schimbarea

  • 9

    bazelor. Lema substituiei. Matricea ataat unei aplicaii liniare ntre module libere de rang finit; formula de schimbare a acesteia la schimbarea bazelor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416

    CAPITOLUL 7: DETERMINANI. SISTEME DE

    ECUAII LINIARE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .426

    1. Definiia unui determinant de ordin n. Proprietile determinanilor. Dezvoltarea unui determinant dup elementele unei linii. Regula lui Laplace. Formula Binet-Cauchy. . . . . . . . . . . . . . . . . . . . . . . . . 426

    2. Matrice inversabil. Inversa unei matrice. Rangul unui sistem de vectori. Rangul unei matrice. Rangul unei aplicaii liniare ntre spaii vectoriale de dimensiuni finite. . . . . . . . . . . . . . . . . . . . . . . . . . 445 3. 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..470 1. Punerea unei probleme de programare liniar. Soluii posibile. Soluii de baz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 2. Tabelul simplex asociat unei soluii de baz. Algoritmul simplex. Regula lexicografic de evitare a ciclajului. . . . . . . . . . . . . . . . . .473 3. Metode de determinare a soluiilor de baz. Metoda matriceal. Metoda celor dou faze. Exemple de aplicare a algoritmului simplex. Exemple de probleme de programare liniar. Exemplu de evitare a ciclajului. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479

  • 10

    CAPITOLUL 9: FORME BILINIARE I PTRATICE . . . . . .495

    1.Forme biliniare. Definiii. Exemple. Matricea ataat unei forme biliniare. Rangul unei forme biliniare. . . . . . . . . . . . . . . . . . . . . 495

    2. Forme ptratice.Polara unei forme ptratice.Matricea ataat unei forme ptratice.Forma canonic a unei forme ptratice ;metodele Gauss-Lagrange i Jacobi .Legea ineriei a lui Sylvester. . . . .. . . . . . . . 497

    BIBLIOGRAFIE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507

    INDEX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509

  • 11

    CONTENTS pag

    Chapter1: PRELIMINARIES. . . . . . . . . . . . . . . . . . . . . .15 1. Sets. Operations on sets. . . . . . . . . . . . . . . . . . . . . . . . 15 2. 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.

  • 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) . . . . . 133 10. 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

  • 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

  • 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

  • 15

    CAPITOLUL 1: NOIUNI PRELIMINARII

    1 Mulimi. Operaii cu mulimi

    n cadrul acestei lucrri vom privi mulimile n sensul n care

    ele au fost privite de ctre GEORG CANTOR - primul matematician care a iniiat studiul lor sistematic (punct de vedere cunoscut n matematic sub numele de teoria naiv a mulimilor).

    Despre paradoxurile ce le implic acest punct de vedere i felul n care ele pot fi eliminate, rugm cititorul s consulte lucrrile [16] i [30].

    Definiia 1.1. Dac A i B sunt dou mulimi, vom spune c A este inclus n B (sau c A este submulime a lui B) dac elementele lui A sunt i elemente ale lui B; n acest caz vom scrie AB iar n caz contrar AB.

    Avem deci : AB pentru orice xA xB AB exist xA a.. xB.

    Vom spune despre mulimile A i B c sunt egale dac oricare ar fi x, xA xB. Deci, A=BAB i BA.

    Vom spune c A este inclus strict n B i vom scrie AB dac AB i AB.

    Se accept existena unei mulimi ce nu conine nici un element care se noteaz prin i poart numele de mulimea vid. Se observ c pentru orice mulime A, A (deoarece n caz contrar ar trebui s existe x a.. xA absurd.!).

    O mulime diferit de mulimea vid se zice nevid. Pentru o mulime T, vom nota prin P(T) mulimea

    submulimilor sale (evident , TP(T) ). Urmtorul rezultat este imediat :

  • 16

    Dac T este o mulime oarecare iar A, B, CP(T), atunci : (i) AA (ii) Dac AB i BA, atunci A=B (iii) Dac AB i BC, atunci AC. n cadrul acestei lucrri vom utiliza deseori noiunea de familie

    de elemente a unei mulimi indexat de o mulime nevid de indici I (prin aceasta nelegnd o funcie definit pe mulimea I cu valori n mulimea respectiv).

    Astfel, vom scrie de exemplu (xi)iI pentru a desemna o familie de elemente ale unei mulimi sau (Ai) iI pentru a desemna o familie de mulimi indexat de mulimea I. Pentru o mulime T i A, BP(T) definim : AB={xT | xA i xB}

    AB={xT | xA sau xB} A\B={xT | xA i xB} AB=(A\B)(B\A).

    Dac AB=, mulimile A i B se zic disjuncte. Operaiile , , \ i poart numele de intersecie, reuniune,

    diferen i diferen simetric. n particular, T\A se noteaz prin T (A) (sau (A) dac nu este

    pericol de confuzie) i poart numele de complementara lui A n T. n mod evident, pentru A, BP(T) avem: A\B=AT (B)

    AB=(AB)\(AB)=(AT (B))(T (A)B) T ()=T, T(T)= AT (A)=T, AT (A)= iar T (T (A))=A.

    De asemenea, pentru xT avem: xAB xA sau xB xAB xA i xB xA\B xA sau xB

  • 17

    xAB (xA i xB) sau (xA i xB) xT (A) xA.

    Din cele de mai nainte deducem imediat c dac A, BP(T), atunci:

    T (AB)=T(A)T (B) i T (AB)=T (A)T (B). Aceste ultime dou egaliti sunt cunoscute sub numele de relaiile lui De Morgan.

    Pentru o familie nevid (Ai )iI de submulimi ale lui T definim: I

    IiiA

    ={xT | xAi pentru orice iI} i

    UIi

    iA

    ={xT | exist iI a.. xAi }.

    Astfel, relaiile lui De Morgan sunt adevrate ntr-un context mai general:

    Dac (Ai) iI este o familie de submulimi ale mulimii T, atunci:

    ( )iIi

    TIi

    iT ACAC UI

    =

    i ( )i

    IiT

    IiiT ACAC IU

    =

    .

    Urmtorul rezultat este imediat:

    Propoziia 1.2. Dac T o mulime iar A, B, CP(T), atunci: (i) A(BC)=(AB)C i A(BC)=(AB)C (ii) AB=BA i AB=BA (iii) AT=A i A=A (iv) AA=A i AA=A. Observaia 1.3. 1. Din (i) deducem c operaiile i sunt

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

    2. Prin dubl incluziune se probeaz imdiat c pentru oricare A, B, CP(T) avem:

  • 18

    A(BC)=(AB)(AC) i A(BC)=(AB)(AC) ,

    adic operaiile de intersecie i reuniune sunt distributive una fa de cealalt.

    Propoziia 1.4. Dac A, B, CP(T), atunci:

    (i) A(BC)=(AB)C (ii) AB=BA (iii) A=A iar A A= (iv) A(BC)=(AB)(AC).

    Demonstraie. (i). Prin dubl incluziune se arat imediat c:

    A(BC)=(AB)C=[AT(B)T(C)][T(A)BT(C)] [T(A)T(B)C](ABC).

    (ii), (iii) sunt evidente. (iv). Se probeaz fie prin dubl incluziune, fie innd cont de

    distributivitatea interseciei fa de reuniune.

    Definiia 1.5. Fiind date dou obiecte x i y se numete pereche ordonat a obiectelor x i y mulimea notat (x, y) i definit astfel:

    (x, y)={ {x}, {x, y} }. Se verific acum imediat c dac x i y sunt dou obiecte a..

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

    Definiia 1.6. Dac A i B sunt dou mulimi, mulimea notat AB={ (a, b) | aA i bB } se va numi produsul cartezian al mulimilor A i B.

    n mod evident: AB A i B

  • 19

    AB= A= sau B= AB=BA A=B AA i BB ABAB.

    Dac A, B, C sunt trei mulimi vom defini produsul lor cartezian prin egalitatea : ABC=(AB)C. Elementul ((a, b), c) din ABC l vom nota mai simplu prin (a, b, c).

    Mai general, dac A1, A2, ..., An (n3) sunt mulimi punem A1 A2 ...An =(( ...((A1A2)A3) ...)An) .

    Dac A este o mulime finit, vom nota prin |A| numrul de elemente ale lui A. n mod evident, dac A i B sunt submulimi finite ale unei mulimi M atunci i AB este submulime finit a lui M iar

    |AB|=|A|+|B|-|AB|.

    Vom prezenta n continuare un rezultat mai general cunoscut sub numele de principiul includerii i excluderii:

    Propoziia 1.7. Fie M o mulime finit iar M1, M2, ..., Mn

    submulimi ale lui M. Atunci :

    ( ) nnnkji

    kjinji

    jini

    i

    n

    ii

    MM

    MMMMMMM

    -+-

    -+-=

    -

  • 20

    Dac notm U1

    1

    -

    ==

    n

    iiMN , atunci conform relaiei (1) putem scrie:

    (2) ==Un

    iiM

    1|NMn|=|N|+|Mn|-|NMn|.

    ns NMn=

    -

    =U

    1

    1

    n

    iiM Mn= U

    1

    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

    ii

    n

    nkjinkji

    njinji

    n

    ini

    n

    inin

    MMMMM

    MMMMMMMMN

    1

    2

    11

    11

    1

    1

    1

    1

    1....=

    -

    -

  • 21

    ( )

    ( )

    ( )

    ( ) .1...

    1

    ....1

    1

    ...

    1

    1

    1

    111

    2

    1...1

    3

    1

    1

    2

    11 11

    11

    1

    1

    1

    1

    1

    221221

    II I

    II

    I I I I

    I

    I II I

    II

    U

    n

    ii

    n

    nkjikji

    njiji

    n

    ii

    n

    ii

    n

    niiiniii

    n

    n

    ii

    n

    nkji njinjikji

    nji

    n

    iniji

    n

    ini

    nn

    n

    ii

    MMMM

    MMMM

    MMMM

    M

    MMMMMM

    MMMMMM

    MNMNM

    nn

    =

    -

  • 22

    n mod evident, (-1)-1= iar dac mai avem Rel (A) a.. -1-1.

    Definiia 2.2. Pentru , Rel (A) definim compunerea lor prin ={(a, b)AA | exist cA a.. (a, c) i (c, b)}.

    Rezultatul urmtor este imediat: Propoziia 2.3. Fie , , Rel (A). Atunci: (i) A=A= (ii) ()=() (iii) i (iv) ()-1=-1-1

    (v) ()-1=-1-1 ; mai general, dac (i) iI este o familie de relaii binare pe A, atunci

    UUIi

    iIi

    i

    --

    =

    11

    rr .

    Pentru n i Rel (A) definim :

    >

    =D= 1....

    0

    npentru

    npentru

    orin

    An

    4434421ooo rrrr .

    Se probeaz imediat c dac m, n atunci

    mn=m+n. Definiia 2.4. Vom spune despre o relaie Rel (A) c este:

    i) reflexiv dac A ii) simetric dac -1

    iii) antisimetric dac -1A iv) tranzitiv dac 2. Rezultatul urmtor este imediat:

  • 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 o

    echivalen pe A dac este reflexiv, simetric i tranzitiv. Vom nota prin Echiv (A) mulimea relaiilor de echivalen de

    pe A. Evident, A, AAEchiv (A). Propoziia 2.7. Dac Echiv (A) , atunci -1= i 2=. Demonstraie. Cum este simetric -1. Dac (a, b)-1,

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

    Propoziia 2.8. Fie 1, 2 Echiv (A). Atunci 12Echiv (A) dac i numai dac 1 2=2 1 . n acest caz 1 2= I

    rrrr

    r

    21 ,)( AEchiv.

    Demonstraie. Dac 1 , 2Echiv (A), atunci (12)-1=12 conform Propoziiei 2.7. ns conform Propoziiei 2.3. avem c (12) -1= 2-11-1= 21, astfel c 12=21.

    Invers, s presupunem c 12=21. Cum A1 , 2A=AA12, adic 12 este

    reflexiv. Cum (12) -1= 2-11-1 =21= 12, deducem c 12 este i simetric. Din (12)2=(12)(12)=1(21)2= =1(12)2=1222= 12 deducem c 12 este i tranzitiv, adic este o echivalen pe A.

    S presupunem acum c 12=21 i fie Echiv (A) a.. 1, 2.

  • 24

    Atunci 12 =, adic

    ( )Io

    rrrr

    rrr

    21,

    21AEchiv

    Cum 1 , 2Echiv (A) i 12Echiv (A) 1 ,212 12 adic =12 .

    Pentru Rel (A), definim relaia de ehivalen de pe A generat de ca fiind relaia de echivalen

    ( )I

    rrr

    rr

    =AEchiv

    .

    n mod evident, relaia de echivalen este caracterizat de condiiile iar dac Echiv (A) a.. (altfel zis, este cea mai mic relaie de echivalen ce include pe ).

    Lema 2.9. Fie Rel(A) i r =A-1. Atunci relaia r

    are urmtoarele proprieti: (i) r (ii) r este reflexiv i simetric

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

    Demonstraie. (i ). este evident .

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

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

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

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

    =n

    nrr .

    Atunci r are urmtoarele proprieti : (i) r

  • 25

    (ii) r este o echivalen pe A (iii) Dac Echiv(A) a.. , atunci r . Demonstraie. (i). este evident. (ii). Cum A r deducem c A r , adic r este

    reflexiv. Deoarece este simetric i pentru orice n* 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) rr o ; atunci exist zA a.. (x, z), (z, y) r , adic exist m, n* a.. (x, z)m i (z, y)n. Deducem imediat c (x, y)nm=n+m r , adic rr 2 , deci r este tranzitiv, adic r Echiv (A).

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

    1=

    n

    nrr .

    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 , Rel (A ). Atunci: (i) ()2=22()() (ii) Dac , Echiv (A) atunci Echiv (A) dac i

    numai dac , . Demonstraie. (i). Avem: (x, y)()2=()() exist zA a..

    (x, z)p i (z, y) [ (x, z) i (z, y)] sau [ (x, z) i (z, y)] sau [(x, z) i (z, y)] sau [(x, z) i (z, y)]

  • 26

    (x, y)2 sau (x, y)2 sau (x, y) sau (x, y) (x, y)22()(), de unde egalitatea cerut.

    (ii).,,. Avem c 2=, 2= i ()2=. Astfel, relaia de la (i) devine: =()(), deci i .

    ,,. Utilizm ipoteza din nou i relaia de la (i): ()2=22()()=()(), deci este tranzitiv. Cum A i AA , adic este reflexiv. Dac (x, y) (x, y) sau (x, y) (y, x) sau (y, x) (y, x), adic este i simetric, deci o echivalen pe A.

    Propoziia 2.13. Fie A o mulime i Rel(A) avnd proprietile:

    (i) Pentru orice xA, exist yA a.. (x, y) (ii) -1 = Atunci -1, -1 Echiv (A). Demonstraie.

    Avem c -1={(x, y) exist zA a.. (x, z)-1 i (z, y)}. Deci, pentru a demonstra c A-1 ar trebui ca pentru orice

    xA, (x, x)-1 adic s existe zA a.. (z, x), lucru asigurat de (i). Deducem c -1 este reflexiv (analog pentru -1).

    Dac (x, y) -1 exist zA a.. (x, z)-1 i (z, y) exist zA a.. (y, z)-1 i (z, x) (y, x)-1, adic -1

    este simetric (analog pentru -1). Cum (-1)(-1) = = (-1)-1 = -1 deducem c -1 este i tranzitiv, deci este o echivalen. Analog pentru -1 .

  • 27

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

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

    Mulimea A / ={ [a] aA } poart numele de mulimea factor ( sau ct ) a lui A prin relaia .

    Propoziia 2.15. Dac Echiv (A), atunci: (i) [ ]U

    Aaa

    =A

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

    (i). Deoarece pentru orice aA, a[a] deducem incluziunea de la dreapta la stnga; cum cealalt incluziune este evident deducem egalitatea solicitat.

    (ii). Dac [a]=[b] , cum a[a] deducem c a[b] adic (a, b).

    Fie acum (a, b) i x[a], adic (x, a). Datorit tranzitivitii lui deducem c (x, b), adic x[b], deci [a] [b]. Analog deducem c i [b][a] , adic [a]=[b].

    (iii). Presupunem c [a][b]. Atunci exist xA a.. (x, a), (x, b) i astfel (a, b), deci [a]=[b] (conform cu (ii)).

    Definiia 2.16. Numim partiie a unei mulimi M o familie

    (Mi)iI de submulimi ale lui M ce verific condiiile :

    (i) Pentru i, jI, ij Mi Mj= (ii) U

    Iii MM

    = .

  • 28

    Observaia 2.17. Din cele de mai nainte deducem c dac este o relaie de echivalen pe mulimea A, atunci mulimea claselor de echivalen ale lui pe A determin o partiie a lui A.

    3 Relaii funcionale. Noiunea de funcie. Clase de funcii.

    Definiia 3.1. Fie A i B dou mulimi. O submulime RAB se numete relaie funcional dac :

    (i) Pentru orice aA exist bB a.. (a, b)R (ii) (a, b), (a, b)R b=b. Numim funcie ( sau aplicaie ) un triplet f=(A, B, R) unde A

    i B sunt dou mulimi nevide iar RAB este o relaie funcional. n acest caz, pentru fiecare element aA exist un unic element

    bB a.. (a, b)R. Convenim s notm b=f(a) ; elementul b se va numi imaginea lui a prin f. Mulimea A se numete domeniul (sau domeniul de definiie al lui f) iar B se numete codomeniul lui f i spunem de obicei c f este o funcie definit pe A cu valori n B scriind lucrul acesta prin f:AB sau A f B.

    Relaia funcional R se mai numete i graficul lui f (convenim s notm pe R prin Gf, astfel c Gf={(a, f(a)) | aA}. Dac f :A B i f:AB sunt dou funcii, vom spune c ele sunt egale (i vom scrie f=f) dac A=A , B=B i f(a)=f(a) pentru orice aA. Pentru o mulime A, funcia 1A:AA, 1A(a)=a pentru orice aA poart numele de funcia identic a 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 :AB este o funcie iar AA i BB atunci notm: f(A)={f (a) | aA} i f-1 (B)={aA | f (a)B}

  • 29

    ( f (A) se va numi imaginea lui A prin f iar f-1(B) contraimaginea lui B prin f ).

    n particular, notm Im(f)=f (A). Evident, f()= i f-1( )=.

    Definiia 3.2. Fiind date dou funcii f:AB i g:BC

    numim compunerea lor funcia notat gf:AC i definit prin (gf)(a)=g(f(a)) pentru orice aA.

    Propoziia 3.3. Dac avem trei funcii

    DCBA hgf atunci: (i) h(gf)=(hg)f (ii) f1A=1Bf=f. Demonstraie. (i). ntr-adevr, avem c h(gf) i (hg)f au pe

    A drept domeniu de definiie, pe D drept codomeniu i pentru orice aA

    (h(gf))(a)=((hg)f)(a)=h(g(f(a))). (ii). este evident. Propoziia 3.4. Fie f:AB, A, AA, B, BB, (Ai)iI,

    (Bj) jJ dou familii de submulimi ale lui A i respectiv B. Atunci: (i) AAf(A)f(A) (ii) BBf-1(B)f-1(B) (iii) ( )II

    Iii

    Iii AfAf

    (iv) ( )UUIi

    iIi

    i AfAf

    =

    (v) ( )IIJj

    jJj

    j BfBf

    -

    - =

    11

  • 30

    (vi) ( )UUJj

    jJj

    j BfBf

    -

    - =

    11 .

    Demonstraie (i). Dac bf(A), atunci b=f(a) cu aA i cum

    AA deducem c bf(A), adic f(A)f(A). (ii). Analog cu (i).

    (iii). Deoarece pentru orice kI, IIi

    iA

    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 aU

    IiiA

    a.. b=f(a) exist i0I a.. a 0iA i

    b=f(a) exist i0I a.. bf(0iA ) b ( )U

    IiiAf

    .

    (v). Totul rezult din echivalenele a

    - IJj

    jBf1

    f(a)IJj

    JB

    pentru orice jJ, f(a)Bj pentru orice jJ, af-1(Bj)

    a ( )jJj

    BfI

    -1 .

    (vi). Analog cu (iv).

    Definiia 3.5. Despre o funcie f:AB vom spune c este: i) injectiv, dac pentru orice a, aA, aaf(a)f(a)

    (echivalent cu f(a)=f(a)a=a) ii) surjectiv, dac pentru orice bB, exist aA a.. b=f(a) iii) bijectiv, dac este simultan injectiv i surjectiv. Dac f :AB este bijectiv, funcia f-1:BA definit prin

    echivalena f-1(b)=a b=f(a) (bB i aA) poart numele de inversa lui f.

  • 31

    Se verific imediat c f-1f=1A i ff-1=1B.

    Propoziia 3.6. Fie f :AB i g :BC dou funcii (i) Dac f i g sunt injective (surjective; bijective) atunci gf

    este injectiv (surjectiv, bijectiv ; n acest ultim caz (gf)-1=f-1g-1 )

    (ii) Dac gf este injectiv (surjectiv, bijectiv) atunci f este injectiv, (g este surjectiv; f este injectiv i g este surjectiv).

    Demonstraie.(i). Fie a, aA a.. (gf)(a)=(gf)(a). Atunci

    g(f(a))=g(f(a)) i cum g este injectiv deducem c f(a)=f(a) iar cum i f este injectiv deducem c a=a, adic gf este injectiv.

    S presupunem acum c f i g sunt surjective i fie cC; cum g este surjectiv, c=g(b) cu bB i cum i f este surjectiv b=f(a) cu aA astfel c c=g(b)=g(f(a))=(gf)(a), adic gf este surjectiv.

    Dac f i g sunt bijective atunci faptul c gf este bijectiv rezult imediat din cele expuse mai sus. Pentru a proba n acest caz egalitatea (gf)-1 = f-1g-1, fie cC. Avem c c=g(b) cu bB i b=f(a) cu aA. Deoarece (gf)(a)=g(f(a))=g(b)=c deducem c (gf)-1(c)=a= =f-1(b)=f-1(g-1(c))=(f-1g-1)(c), adic (gf)-1=f-1g-1.

    (ii). S presupunem c gf este injectiv i fie a, aA a.. f(a)=f(a). Atunci g(f(a))=g(f(a))(gf)(a)=(gf)(a)a=a, adic f este injectiv.

    Dac gf este surjectiv, pentru cC, exist aA a.. (gf)(a)=c g(f(a))=c, adic g este surjecie.

    Dac gf este bijecie atunci n particular gf este injecie i surjecie, deci conform celor de mai sus cu necesitate f este injecie iar g surjecie.

    Propoziia 3.7. Fie M i N dou mulimi iar f :MN o funcie. ntre mulimile P(M) i P(N) se definesc funciile

  • 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), BP(N).

    Urmtoarele afirmaii sunt echivalente: (i) f este injectiv (ii) f* este injectiv (iii) f*f*=1P(M) (iv) f* este surjectiv (v) f (AB)=f(A)f(B), A, BP(M) (vi) f(MA)N f (A), AP(M) (vii) Dac g, h:L M sunt dou funcii a.. fg=fh, atunci

    g=h (viii) Exist o funcie g :N M a.. gf=1M. Demonstraie.Vom demonstra echivalena afirmaiilor astfel

    (i)(ii)(iii)(iv)(v)(vi)(vii)(i) iar apoi (i)(viii) . (i)(ii). Fie A, AP(M) a.. f*(A)=f*(A)f(A)=f(A).

    Dac xA, atunci f(x)f(A)f(x)f(A) exist xA a.. f(x)=f(x). Cum f este injectiv, rezult x=xA, adic AA; analog AA, deci A=A, adic f* este injectiv.

    (ii)(iii). Pentru AP(M) trebuie demonstrat c (f*f*)(A)=A f -1 (f (A))=A. Incluziunea Af -1(f (A)) este valabil pentru orice funcie f. Pentru cealalt incluziune, dac

    xf -1(f(A))f(x)f(A) exist xA a.. f(x)=f(x)f*({x})=f*({x}) {x}={x}x = xA, adic f -1 (f ( A))A.

    (iii)(iv). Deoarece f*f*=1P(M) , pentru orice AP(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, BP(M) i A, BP(N) a.. A=f 1(A) i B=f 1(B). Atunci f(AB)=f(f -1(A)f -1 (B))=f(f -1( AB)).

    S artm c f(f-1(A))f(f-1(B))f(f-1(AB).

  • 33

    Dac yf(f -1(A))f(f -1 (B))yf(f -1(A)) i yf(f -1(B)) exist xf -1(A) i xf -1(B) a.. y=f(x)=f(x).

    Cum xf -1(A) i xf -1(B) f(x)A i f(x)B, deci yAB. Deoarece y=f(x)xf -1(AB), adic yf(f -1(AB)).

    Astfel, f(AB)f(A)f(B) i cum incluziunea f(AB)f(A)f(B) este adevrat pentru orice funcie deducem c f (AB)=f(A)f(B).

    (v)(vi). Pentru AP(M) avem f(A)f(MA)=f(AMA)=f()=, deci f(MA)Nf (A). (vi)(vii). Fie g, h : LM dou funcii a.. fg=fh i s

    presupunem prin absurd c exist xL a.. g(x)h(x), adic g(x)M{h(x)}; atunci f(g(x))f(M{h(x)})Nf(h({x}))=N{f(h(x))} deci f(g(x))f(h(x)) (fg)(x)(fh)(x) fgfh , ceea ce este absurd.

    (vii)(i). Fie x, xM a.. f(x)=f(x) i s presupunem prin absurd c xx. Notnd L={x, x} i definind g, h : LM, g(x)=x, g(x)=x, h(x)=x, h(x)=x, atunci gh i totui fg=fh , ceea ce este absurd.

    (i)(viii). Definind g:NM, g(y)=x dac y=f(x) cu xM i y0 dac yf(M), atunci datorit injectivitii lui f, g este definit corect i evident gf=1M .

    (viii)(i). Dac x, xM i f(x)=f(x), atunci g(f(x))=g(f(x))x=x, adic f este injectiv.

    Propoziia 3.8. Cu notaiile de la propoziia precedent, urmtoarele afirmaii sunt echivalente:

    (i) f este surjectiv (ii) f* este surjectiv (iii) f*f*=1P(N) (iv) f* este injectiv (v) f(MA)N f(A), AP(M)

  • 34

    (vi) Dac g, h:NP sunt dou funcii a.. gf=hf, atunci g=h

    (vii) Exist o funcie g:NM a.. fg=1N.

    Demonstraie.Vom demonstra echivalena afirmaiilor astfel:

    (i)(ii)(iii)(iv)(v)(vi)(i) iar apoi (i)(vii). (i)(ii). Fie BP(N) i yB ; atunci exist xyM a.. f(xy)=y. Notnd A={xyyB}M avem c f (A)=B f*(A)=B. (ii)(iii). Avem de demonstrat c pentru orice BP(N),

    f (f-1(B))=B . Incluziunea f (f-1 (B))B este valabil pentru orice funcie f. Fie acum yB; cum f* este surjectiv, exist AM a.. f*(A)={y}f(A)={y}, deci exist xA a.. y=f(x) i deoarece yB xf-1 (B)y=f(x)f(f 1(B)), de unde i incluziunea Bf(f 1 (B)).

    (iii)(iv). Dac B1, B2P(N) i f*(B1)=f*(B2), atunci f*(f*(B1))=f*(f*(B2)) 1P(N) (B1)=1P(N) (B2)B1=B2, adic f* este injectiv.

    (iv)(v). Fie AM ; a arta c f(MA)Nf (A), revine la f(MA)f(A)=N f(MAA)=Nf(M)=N. S presupunem prin absurd c exist y0N a.. pentru orice xM, f(x)y0 , adic f-1 ({y0})=f*({y0})=. Deoarece i f*()= f*({y0})=f*() iar pentru c f* este presupus injectiv ar rezulta c {y0}=, ceea ce este absurd.

    (v)(vi). n particular, pentru A=M ar trebui s avem f(MM)Nf (M) f()Nf (M) Nf (M)f(M)=N.

    Dac g, h:NP sunt dou funcii a.. gf=hf, atunci pentru orice yN, exist xM a.. f(x)=y (cci f (M)=N) i astfel g(y)=g(f(x))=(gf)(x)=(hf)(x)=h(f(x)) = h(y), adic g=h.

  • 35

    (vi)(i). Presupunem prin absurd c exist y0N a.. f(x)y0, pentru orice xM. Definim g, h : N{0, 1} astfel : g(y)=0, pentru orice

    yN i ( ){ }

    =

    -=

    0

    0

    1

    0

    yypentru

    yNypentruyh

    Evident gh i totui gf=hf, ceea ce este absurd, deci f este surjectiv.

    (i)(vii). Pentru fiecare yN alegnd cte un singur xyf-1 ({y}), obinem astfel o funcie g : NM, g(y)=xy , pentru orice yN , ce verific n mod evident relaia fg=1N.

    (vii)(i). Pentru yN, scriind c f(g(y))=y, rezult y=f(x), cu x=g(y)M, adic f este surjectiv.

    Din propoziiile precedente obinem imediat: Corolarul 3.9. Cu notaiile de la Propoziia 3.7., urmtoarele

    afirmaii sunt echivalente: (i) f este bijectiv (ii) f(MA)=N f(A), AP(M) (iii) f* i f * sunt bijective (iv) Exist o funcie g:NM a.. fg=1N i gf=1M.

    Propoziia 3.10. Fie M o mulime finit i f:MM o funcie. Urmtoarele afirmaii sunt echivalente:

    (i) f este injectiv (ii) f este surjectiv (iii) f este bijectiv . Demonstraie. Vom demonstra urmtoarele implicaii:

    (i)(ii)(iii)(i). (i)(ii). Dac f este injectiv, atunci f(M) i M au acelai numr

    de elemente i cum f (M)M rezult c f (M)=M , adic f este i surjectiv.

  • 36

    (ii)(iii). Dac f este surjectiv, atunci pentru orice element yM va exista un unic element xyM a.. f(xy)=y (cci n caz contrar ar rezulta contradicia c M ar avea mai multe elemente dect M), adic f este i injectiv.

    (iii)(i). Evident.

    Propoziia 3.11. Fie M i N dou mulimi avnd m, respectiv n elemente. Atunci:

    (i) Numrul funciilor definite pe M cu valori n N este egal cu nm

    (ii) Dac m=n, atunci numrul funciilor bijective de la M la N este egal cu m!

    (iii) Dac mn, atunci numrul funciilor injective de la M la N este egal cu mnA

    (iv) Dac mn, atunci numrul funciilor surjective de la M la N este egal cu mn ( ) ( ) ( ) 1121 1...21 ---+--+-- nnnmnmn CnCnC .

    Demonstraie.(i). Facem inducie matematic dup m; dac

    m=1, mulimea M va avea un singur element i este clar c vom avea n=n1 funcii de la M la N. Presupunem afirmaia adevrat pentru mulimile M ce au cel mult m-1 elemente.

    Dac M este o mulime cu n elemente, putem scrie M=M{x0}, cu x0M iar M submulime a lui M cu m-1 elemente.

    Pentru orice yN i g : MN funcie, considernd f g, y : MN, f g, y (x)=g(x) dac xM i y dac x=x0 , deducem c oricrei funcii g: MN i putem asocia n funcii distincte de la M la N ale cror restricii la M sunt egale cu g. Aplicnd ipoteza de inducie pentru funciile de la M la N, deducem c de la M la N se pot defini nnm-1=nm funcii.

    (ii). Facem inducie matematic dup m; dac m =1, mulimile M i N vor avea cte un singur element i vom avea o singur funcie bijectiv de la M la N.

    Presupunem afirmaia adevrat pentru toate mulimile M i N ambele avnd cel mult m-1 elemente i fie M i N mulimi avnd fiecare

  • 37

    cte m elemente. Scriind M=M{x0}, cu x0M iar M submulime a lui M cu m-1 elemente, atunci orice funcie bijectiv f:MN este perfect determinat de valoarea f(x0)N precum i de o funcie bijectiv g:MN, unde N=N \ {f (x0)}. Deoarece pe f (x0) l putem alege n m 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:MN este injectiv, atunci lund drept codomeniu pe f(M)N, deducem c f determin o funcie bijectiv f :Mf(M), f (x)=f(x), pentru orice xM, iar f(M) are m elemente. Reciproc, dac

    vom alege n N o parte N a sa cu m elemente, atunci putem stabili m! funcii bijective de la M la N (conform cu (ii)). Cum numrul submulimilor N ale lui N care au m elemente este egal cu mnC , rezult c putem construi m! . mn

    mn AC = funcii injective de la M la N.

    (iv). S considerm M={x1, x2, ...,xm}, N={y1, y2, ...,yn} iar Mi mulimea funciilor de la M la N a.. yi nu este imaginea nici unui element din Mi, i=1,2,...,n.

    Astfel, dac notm 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 din nmF , deci conform Propoziiei 1.7. avem egalitile (1):

    ( ) I I II I

    UU

    nn

    nkjikji

    njiji

    n

    ii

    mn

    ii

    mn

    ii

    nm

    nm

    MMMMMM

    MMMnMnMFS

    ....1.... 211

    1111

    -++-

    -+-=-=-=

  • 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: nmS = mn ( ) ( ) ( ) 1121 1...21 ---+--+-- nnnmnmn CnCnC .

    Pentru o mulime nevid M i AP(M) definim A : M{0,1},

    A(x)=

    Axdaca

    Axdaca

    1

    0

    pentru orice xM. Funcia A poart numele de funcia caracteristic a mulimii A.

    Propoziia 3.12. Dac A, BP(M), atunci: (i) A=BA=B (ii) =0, M=1 (iii) AB=A B , A2=A (iv) AB=A+B - A B (v) A \ B=A - A B , ACMj =1-A (vi) A B=A+B - 2AB . Demonstraie. (i).,,. Evident. ,,. Presupunem c A=B i fie xA; atunci A (x)=

    =B (x)=1, deci xB, adic AB. Analog BA, de unde A=B. (ii). Evident. (iii). Pentru xM putem avea urmtoarele situaii: (xA, xB)

    sau (xA, xB) sau (xA, xB) sau (xA, xB). n fiecare situaie n parte se verific imediat relaia AB (x)=A (x)B(x).

    Cum AA=A A =AA=A 2. (iv), (v). Asemntor cu (iii). (vi). Avem

    A B =( A \ B )( B \ A )= A \ B + B \ A -A \ B B \ A =

  • 39

    =A- AB+B - BA (A \ B ) ( B \ A )= A +B -2AB deoarece (A \ B ) (B \ A )=.

    Fie M o mulime oarecare iar Echiv (M). Funcia p,M : MM / definit prin p,M (x)=[x] pentru orice xM este surjectiv i poart numele de surjecia canonic.

    Propoziia 3.13. Fie M i N dou mulimi pe care s-au definit relaiile de echivalen , respectiv i f : MN o funcie avnd proprietatea:

    (x, y) ( f(x), f(y)), x, yM. Atunci exist o singur funcie f : M/N/ a. . diagrama: f M N p M, pN, f M/ N/ este comutativ (adic pN, f= f pM, , unde pM, , pN, , sunt surjeciile canonice).

    Demonstraie. Pentru xM, vom nota prin [x] clasa de echivalen a lui x modulo relaia .

    Pentru xM, definim: f ([x])=[f(x)]. Dac x, yM a.. [x]=[y] (x, y) [f (x), f (y)] (din

    enun) [f (x)]=[f (y)] , adic f este corect definit. Dac xM, atunci ( f pM, )(x)= f (pM, (x)) =

    = f ([x])=[f[x]] =pN, (f (x))= (pN, f)(x), adic pN, f= f pM, . Pentru a demonstra unicitatea lui f , s presupunem c ar mai

    exista o funcie f : M / N / a.. pN, f= f pM, , i fie xM. Atunci f ([x])= f (pM, (x))=( f pM, )(x)=(pN, f)(x) =

    =pN, (f(x)) = [f (x)] = f ([x]), de unde deducem c ff = .

  • 40

    Propoziia 3.14. Fie M i N dou mulimi iar f :MN o

    funcie ; notm prin f relaia binar de pe M definit astfel: ( x, y ) f f(x)=f(y) (x, yM). Atunci: (i) f este relaie de echivalen pe M

    (ii) Exist o unic funcie bijectiv f : M / fIm ( f ) a.. i f

    FMp r, =f, i:Im ( f ) N fiind incluziunea. Demonstraie. (i). Evident (relaia de egalitate fiind o

    echivalen pe M). (ii). Pstrnd notaia claselor de echivalen de la Propoziia 3.13., pentru xM definim )]([

    fxf r =f(x). Funcia f este

    corect definit cci dac x, yM 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 /fIm (f ) o alt funcie bijectiv a.. if1 FMp r, =f i xM. Atunci, (if1 FMp r, )(x)=f(x) )]([1 fxf r =f(x) )]([1 fxf r =f(x)= )]([ fxf r , adic f1= f .

    Propoziia 3.15. Fie M o mulime finit cu m elemente.

    Atunci numrul Nm, k al relaiilor de echivalen ce pot fi definite pe M a.. mulimea ct s aib k elemente ( km ) este dat de formula: ( ) ( ) ( ) ( )[ ]1121, 1...21!1 ---+--+--= kkkmkmkmkm CkCkCkkN .

    Deci numrul relaiilor de echivalen ce pot fi definite pe mulimea M este dat de formula N=Nm, 1+Nm, 2+...+Nm, m.

    Demonstraie. Dac este o relaie de echivalen,

    Echiv (M), atunci avem surjecia canonic p M, : MM / .

  • 41

    Dac n general, f : MN este o funcie surjectiv, atunci cum am stabilit n cazul Propoziiei 3.14., aceasta d natere la urmtoarea relaie de echivalen de pe M : (x, y) f f(x)=f(y). Mai mult, dac g : NN este o funcie bijectiv atunci relaiile f i gf coincid cci (x,y)gf(gf)(x)=(gf)(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 aceiai relaie de echivalen pe M. Lund n particular N=M/ i innd cont de Propoziia 3.11. deducem c

    ( ) ( ) ( ) ( )[ ]1121, 1...21!1 ---+--+--= kkkmkmkmkm CkCkCkkN .

    Propoziia 3.16. Fie M o mulime nevid. Atunci funcia care asociaz unei relaii de echivalen definite pe M partiia lui M dat de relaia de echivalen este bijectiv.

    Demonstraie. Fie Part (M) mulimea partiiilor lui M.

    Vom nota prin f : Echiv (M)Part (M) funcia ce asociaz fiecrei relaii de echivalen de pe M, partiia lui M dat de clasele de echivalen modulo : f()={[x] | xM } .

    Definim g : Part (M)Echiv (M) astfel : dac P=(Mi) iI este o partiie a lui M, definim relaia g(P) pe M astfel :

    (x, y )g(P) exist iI a.. x, yMi . Reflexivitatea i simetria lui g(P) sunt imediate. Fie acum (x, y), (y, z)g(P). Exist deci i1 , i2I a. . x, y 1iM i y, z 2iM ; dac i1i2 ar rezulta c I 21 ii MM (cci ar conine pe y), ceea ce este absurd .

    Deci i1=i2=i i astfel x, zMi , adic (x, z) g(P) de unde concluzia c g (P) este i tranzitiv, deci g(P) Echiv (M), funcia g fiind astfel corect definit.

    S artm c dac xMi , atunci clasa de echivalen x modulo g (P) este egal cu Mi. ntr-adevr, yMi (x, y)g(P) y x Mi= x .

  • 42

    Deducem astfel c g este de fapt inversa lui f, adic f este bijectiv.

    Suntem acum n msur s facem anumite precizri legate de mulimea numerelor naturale. Definiia 3.17. Numim triplet Peano un triplet ( N, 0, s ) unde N este o mulime nevid, 0N iar s:NN este o funcie astfel nct sunt verificate axiomele :

    P1 : 0s( N ) P2 : s este o funcie injectiv P3 : dac PN este o submulime astfel nct 0P i

    (nPs(n)P ), atunci P=N . n cele ce urmeaz, acceptm ca axiom existena unui triplet Peano (cititorului dornic de aprofundarea acestei chestiuni i recomandm lucrarea [16] ) . Lema 3.18. Dac ( N, 0, s ) este un triplet Peano, atunci N={0}s(N).

    Demonstraie Dac notm P={0}s(N), atunci PN i cum P

    verific P3 , deducem c P=N .

    Teorema 3.19. Fie ( N, 0, s ) un triplet Peano iar ( N, 0, s ) un alt triplet format dintr-o mulime nevid N, un element 0N i o funcie s:N N. Atunci :

    (i) Exist o unic funcie f:NN astfel nct f(0) = 0, iar diagrama

  • 43

    N f N

    s s

    N f N

    este comutativ (adic f s = sf )

    (ii) Dac ( N, 0, s) este un triplet Peano, atunci f este bijecie.

    Demonstraie (i). Pentru a proba existena lui f, vom considera

    toate relaiile RNN a.. : r1 : (0, 0) R

    r2 : Dac (n, n)R, atunci (s(n), s(n))R iar prin R0 vom nota 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, 0)R0 vom deduce c f (0)=0 iar dac nN i f (n)=nN, (n , n)R0, deci (s(n), s(n))R0, adic, f(s(n))=s(n)=s(f (n)).

    Pentru a demonstra c R0 este o relaie funcional, vom demonstra c pentru orice nN, exist nN a. . (n, n)R 0 iar dac pentru nN i n, nN avem (n, n)R0 i (n, n)R0 , atunci n= n .

    Pentru prima parte, fie P={nN | exist nN a. . (n, n)R0 }N.

    Cum (0, 0)R0 deducem c 0P. Fie acum nP i nN a.. (n, n)R0. Din definiia lui R0 deducem c (s(n), s(n))R0 ; obinem c s(n)P i cum (N, 0, s) este triplet Peano, deducem c P=N.

    Pentru a doua parte, fie

  • 44

    Q={nN : dac n, nN i (n, n), (n, n)R0 n= n}N i s demonstrm la nceput c 0Q.

    n acest sens, vom demonstra c dac (0, n)R0 atunci n=0. Dac prin absurd, n0, atunci vom considera relaia R1=R0 {(0, n)}NN. Din n0 deducem c (0, 0)R1 iar dac pentru mN avem (n, m)R1 , atunci (n, m)R0 i (n , m) (0, n). Astfel (s(n), s(m))R0 i cum (s(n), s(m))(0, n) (cci s(n) 0 conform cu P1), deducem c (s(n), s(m))R1 . Cum R1 verific r1 i r2 ar trebui ca R0R1 absurd (cci R1 este inclus strict n R0 ).

    Pentru a proba c 0Q, fie n, nN a. . (0, n), (0 , n)R0. Atunci, innd cont de cele stabilite mai sus, deducem c n=n=0, deci 0Q.

    Fie acum nQ i n N a. . (n, n)R0 ; vom demonstra c dac (s(n), n)R0, atunci n=s(n). S presupunem prin absurd c n s(n) i s considerm relaia R2 =R0 {(s (n), n)} . Vom demonstra c R2 verific r1 i r2 .

    ntradevr, (0, 0)R2 ( cci 0 s(n) ) iar dac (p, p)R2 , atunci (p, p) R0 i (p, p)( s(n), n) .

    Deducem c (s(p), s(p))R0 i dac presupunem (s(p), s(p))= =(s(n), n), atunci s(p) =s(n), deci p=n. De asemenea, s(p)=n. Atunci (n, n)R0 i (n, p)R0 iar cum nQ n=p, deci n=s(p)=s(n), ceea ce contrazice faptul c ns(n). Prin urmare, (s(p), s(p)) (s(n), n), ceea ce ne arat c (s(p), s(p))R2 , adic R2 satisface r1 i r2 . Din nou ar trebui ca R0R2 absurd !.

    Deci (s (n), n)R0 n=s(n) astfel c dac r, s N i (s(n), r), (s(n), s )R0 , atunci r = s = s(n), adic s(n)Q, deci Q=N.

    Pentru a proba unicitatea lui f, s presupunem c mai exist f:NN a.. f(0)=0 i s(f(n))=f(s(n)) pentru orice nN.

  • 45

    Considernd P={nN | f(n)=f(n)}N, atunci 0P iar dac nP (adic f(n)=f(n)), atunci s(f(n))=s(f(n))f(s(n))= =f(s(n))s(n)P i atunci P=N, adic f=f.

    (ii). S artm la nceput c f este injectiv. Pentru aceasta vom considera P={nN | dac mN i f(m)=f(n)m=n}N i s demonstrm la nceput c 0P. Pentru aceasta fie mN a. . f(0)=f(m) i s demonstrm c m=0. Dac prin absurd m0, atunci m=s(n) cu nN iar egalitatea f(m)=f(0) devine f(s(n))=f(0)=0, de unde s(f(n))=0, ceea ce este absurd deoarece prin ipotez (N, 0, s) este un triplet Peano.

    Fie acum nP; pentru a demonstra c s(n)P, fie mN a.. f(m)=f(s(n)).

    Atunci m0 (cci n caz contrar ar rezulta c 0=f(0)=f(s(n))=s(f(n)), absurd !), deci conform Lemei 3.18., m=s(p) cu pN iar egalitatea f(m)=f(s(n)) devine f(s(p))=f(s(n))s(f(p))=s(f(n)), adic f(p)=f(n) i cum nP, atunci n=p i astfel m=s(p)=s(n).

    Pentru a demonstra surjectivitatea lui f s considerm

    P={nN| exist nN a. . n=f (n)}N . Cum f(0)=0 deducem c 0P. Fie acum nP ; atunci exist nN a.. n=f (n). Deoarece s(n)=s(f(n))=f(s(n)), deducem c s(n)P i cum tripletul (N, 0, s) este un triplet Peano, deducem c P=N, adic f este i surjectiv, deci bijectiv .

    Observaia 3.20. Conform Teoremei 3.19. (cunoscut i sub numele de teorema de recuren ) un triplet Peano este unic pn la o bijecie.

    n cele ce urmeaz vom alege un triplet Peano oarecare (, 0, s) pe care l vom fixa ; elementele lui le vom numi numere naturale .

    Elementul 0 va purta numele de zero .

    Vom nota 1=s(0), 2=s(1), 3=s(2), e.t.c., astfel c ={0, 1, 2, }. Funcia s poart numele de funcia succesor . Axiomele P1 P3 sunt

  • 46

    cunoscute sub numele de axiomele lui Peano (axioma P3 poart numele de axioma induciei matematice). Pe parcursul acestei lucrri vom construi pornind de la o mulime a numerelor naturale mulimile numerelor ntregi , raionale , 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 : AB o pereche de funcii. O pereche (K, i) format dintr-o mulime K i o funcie i : KA se numete nucleul perechii (f, g) dac sunt verificate urmtoarele dou condiii:

    (i) fi=gi (ii) Pentru oricare alt dublet (K, i) cu K mulime i

    i:KA a.. fi= gi exist o unic funcie u : KK a. . iu=i.

    Teorema 4.2. Pentru orice pereche de funcii f, g : AB exist un nucleu al perechii (f, g) unic pn la o bijecie (unicitatea nseamn c dac (K, i) i (K, i) sunt dou nuclee pentru perchea (f, g) atunci exist o bijecie u : KK a.. iu=i ).

    Demonstraie. S probm la nceput existena nucleului i pentru aceasta fie K={xAf(x)=g(x)} iar i : KA incluziunea (K put`nd fi chiar ).

    n mod evident fi=gi. Fie acum (K, i) cu i : KA a. . fi=gi. Pentru aK, cum f (i(a))=g (i(a)) deducem c i(a)K. Definim atunci u:KK prin u(a)=i(a), pentru orice aK i este clar c iu=i.

    Dac u:KK este o alt funcie a.. iu=i, atunci pentru aK avem i(u(a))=u(a), de unde u(a)=i(a)=u(a), adic u=u.

  • 47

    S probm acum unicitatea nucleului iar pentru aceasta fie (K, i) i (K, i) dou nuclee pentru perchea (f, g).

    Cum (K, i) este nucleul perechii (f, g) deducem existena unei funcii u:KK a.. iu=i.

    Cum i (K, i ) este nucleul perechii (f, g) deducem existena unei funcii u:KK a.. iu=i.

    Deducem imediat c i(uu)=i i i(uu)=i. Cum i i K 1 =i i i1K=i, innd cont de unicitatea din Definiia 4.1., deducem c uu= K 1 i uu=1K , adic u este bijecie i iu=i .

    Observaia 4.3. Vom nota ( K, i ) = Ker (f, g) (iar dac nu este pericol de confuzie doar K=Ker (f, g)).

    Definiia 4.4. Fiind dat o pereche de funcii f, g :AB numim conucleu al perchii (f, g) pereche (P, p) format dintr-o mulime P i o funcie p:BP ce verific urmtoarele dou condiii :

    (i) pf=pg (ii) Pentru oricare alt dublet (P , p) cu P mulime i

    p: BP a. . pf= pg , exist o unic funcie v :PP a.. vp=p.

    Teorema 4.5. Pentru orice pereche de funcii f, g : AB exist un conucleu al perechii ( f, g ) unic pn la o bijecie (unicitatea nseamn c dac (P, p) i (P , p) sunt dou conuclee pentru perchea (f, g), atunci exist o bijecie v:PP a.. vp=p ).

    Demonstraie. Vom proba doar existena conucleului perechii (f, g) deoarece unicitatea sa se probeaz analog cu unicitatea nucleului.

    Pentru aceasta fie ={(f(x), g(x)) | xA } (care este o relaie binar pe B) iar relaia de echivalen de pe B generat de (a crei construcie este descris n Teorema 2.11.). S artm c perechea ( B / , p, B ) este un conucleu al perechii (f, g). Deoarece pentru

  • 48

    orice xA avem (f(x), g(x)) deducem c (f(x), g(x)) adic, p, B (f (x))=p, B(g(x)), deci p, Bf=p, Bg.

    Fie acum (B, p) cu B mulime i p:BB a.. pf=pg. Atunci pentru orice xA, p(f(x))=p(g(x)), adic (f(x), g(x)) p (vezi Propoziia 3.14.), deci p . Cum p este relaie de echivalen pe B iar este cea mai mic relaie de echivalen de pe B ce conine pe deducem c p .

    Conform Propoziiei 3.13. exist o funcie : B/B/P a.. p, B= Bpp ,r .Fie :B/PIm(p) bijecia a crei existen ne este asigurat de Propoziia 3.14.. Avem c p=i Bpp ,r , unde

    i: Im (p)B este incluziunea. Dac notm v=i , atunci

    v Bp ,r =(i) Bp ,r =(i)( Bp ,r )=(i) Bpp ,r = =i( Bpp ,r )=p.

    Dac mai avem v:B/B a.. v Bp ,r =p, atunci v Bp ,r = v Bp ,r i cum Bp ,r este surjecie deducem c v=v

    (conform Propoziiei 3.8.). Observaia 4.6. Vom nota (B, Bp ,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 mulime ordonat nelegem un dublet (A, ) format dintr-o mulime nevid A i o relaie binar pe A notat tradiional prin "" care este reflexiv, antisimetric i tranzitiv. Vom spune c "" este o ordine pe A. Pentru x, y A vom scrie x < y dac x y , x y. Dac relaia "" este doar reflexiv i tranzitiv, vom spune despre ea c este o ordine parial sau c (A, ) este o mulime parial ordonat.

  • 49

    Dac pentru x, yA definim x y dac i numai dac y x obinem o nou relaie de ordine pe A. Dubletul (A, ) l vom nota prin A i spunem c mulimea ordonat A este duala mulimii A. Fie ( ),A o mulime parial ordonat iar r o relaie de echivalen pe A. Vom spune despre r c este compatibil cu preordinea de pe A dac pentru oricare elemente x , y , z, t din A avem implicaia ( ) ( ) rr tzyx ,,, i .tyzx Dac r este o relaie de echivalen pe A compatibil cu preordinea , atunci pe mulimea ct A/ r se poate defini o ordine parial astfel : rr ][][ yx exist r][xz i r][yt a.. tz ; vom numi aceast ordine parial preordinea ct. n cele ce urmeaz prin (A,) vom desemna o mulime ordonat. Cnd nu este pericol de confuzie prin mulime ordonat vom specifica numai mulimea subiacent A (fr a mai pune n eviden relaia , aceasta subnelegndu-se ). Definiia 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 mare minorant al lui S) ii) M este majorant pentru S dac M este minorant pentru S n A, adic pentru orice sS, s M (n caz c exist, prin sup (S) vom desemna cel mai mic majorant al lui S). Dac S={s1, s2, ..., sn}A atunci vom nota inf (S)= s1s2 ...sn iar sup (S)= s1s2 ..sn (evident, n cazul n care acestea exist). Ordinea "" de pe A se zice total dac pentru orice a, bA, a b sau b a; o submulime total ordonat a lui A poart numele de lan. Pentru a, bA vom spune c b urmeaz pe a (sau c a este urmat de b) dac a < b iar pentru a c b avem a=c sau c=b; vom utiliza n acest caz notaia a b.

  • 50

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

  • 51

    y iIi

    A prin x y dac i numai dac xAi, yAj i i< j sau

    {x, y} Ak iar x y n Ak. Mulimea ordonat iIi

    A definit mai

    sus poart numele de suma ordinal a familiei (Ai) AiI. Dac I={1, 2,..., n} convenim s notm i

    IiA

    = A1 A2... An.

    Dac (Pi , )1in este o familie finit de mulimi ordonate, atunci P=

    ni

    1Pi devine n mod canonic mulime ordonat, definind

    pentru x=(xi)1in , y=(yi)1in P, x y exist 1sn a.. x1 = y1, , xs-1=ys-1 i xs

  • 52

    ix) mrginit dac este simultan inf i sup - mrginit (adic 0 a 1 pentru orice a A); n acest caz 0 se zice element iniial (sau prim) al lui A iar 1 element final (sau ultim) al lui A x) condiional complet dac pentru orice submulime nevid i mrginit 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-adevr, 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 mrginit S a sa, s existe doar inf (S) (sau sup (S)). Definiia 5.5. Un element mA se zice: i) minimal dac avnd aA a.. a m deducem c m = a ii) maximal dac avnd aA a.. m a deducem c m = a Dac 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 AA c este inf-sub-semilatice (respectiv sup-sub-semilatice), dac pentru oricare dou elemente a, bA avem abA (respectiv abA). Dac A este latice, AA se va zice sublatice, dac pentru oricare dou elemente a, bA avem ab, abA. Exemple. 1. Fie mulimea numerelor naturale iar "" relaia de divizibilitate pe . Atunci "" este o relaie de ordine pe . Fa de aceast ordine devine latice n care pentru m, n , m n = cel

  • 53

    mai mare divizor comun al lui m i n iar m n = cel mai mic multiplu comun al lui m i n.

    Evident, pentru relaia de divizibilitate, elementul 1 este element iniial iar 0 este element final. Aceast ordonare nu este total deoarece dac avem dou numere naturale m, n prime ntre ele (cum ar fi de exemplu 2 i 3) nu avem m n i nici n m.

    2. Dac K este una din mulimile de numere , , sau , atunci K cu ordonarea natural este o latice, iar ordonarea natural este total. 3. Fie M o mulime iar P(M) mulimea submulimilor lui M. Atunci (P (M), ) este o latice complet cu prim i ultim element (respectiv i M).

    Fie acum A, A dou mulimi ordonate (cnd nu este pericol de confuzie convenim s notm prin "" ambele relaii de ordine de pe A i A ) i f:AA o funcie. Definiia 5.7. Vom spune despre f c este morfism de mulimi ordonate (sau aplicaie izoton) dac pentru orice a, bA cu a b avem f (a) f (b) (n anumite lucrri f se zice monoton cresctoare). Dac A, A sunt inf (sup) - semilatici vom spune despre f c este morfism de inf (sup) - semilatici dac pentru oricare dou elemente a, bA, f (a b) = f (a) f (b) (respectiv f (a b) = =f (a) f (b)). Dac A, A sunt latici, vom spune c f este morfism de latici dac f este simultan morfism de inf i sup-semilatici (adic pentru oricare dou elemente a, b A avem f (a b) = =f (a) f (b) i f (a b) = f (a) f (b)). n mod evident, morfismele de inf (sup) - semilatici sunt aplicaii izotone iar dac compunem dou morfisme de acelai tip obinem tot un morfism de acelai tip.

    Dac A, A sunt mulimi ordonate iar f:AA este morfism de mulimi ordonate, atunci f se zice izomorfism de mulimi ordonate dac

  • 54

    exist g:AA morfism de mulimi ordonate a.. fg=1A i gf=1A. Acest lucru revine la a spune de fapt c f este o bijecie. n acest caz vom scrie AA . Analog se definete noiunea de izomorfism de inf (sup) - semilatici ca i cea de izomorfism de latici. n continuare vom stabili felul n care mulimile preordonate induc mulimi ordonate, iar pentru aceasta fie (A, ) o mulime parial ordonat. 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 A/ r mpreun cu preordinea ct (definit la nceputul paragrafului) i s artm c acest preordine este de fapt o ordine pe A (adic r este i simetric).

    ntr-adevr, fie [ ] [ ]rr yx , A a.. [ ] [ ]rr yx i [ ] [ ]rr xy i s demonstrm 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. innd cont de Propoziia 3.13. se verific imediat faptul c mulimea ordonat ct ( ),A mpreun cu surjecia canonic

    AApA : verific urmtoarea proprietate de universalitate: Pentru orice mulime ordonat ( ),B i funcie izoton

    BAf : exist o unic aplicaie izoton BAf : a.. .fpf A =o Definiia 5.8. Fie A o inf-semilatice i F A o submulime nevid a sa. Vom spune c F este filtru al lui A dac F este o inf-sub-semi- latice i pentru a, b A, dac a b i aF atunci bF. Vom nota prin F (A) mulimea filtrelor lui A.

  • 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 submulime nevid a sa. Vom spune c I este un ideal al lui A dac I este sup-sub-semilatice a lui A i pentru orice a, bA cu a b, dac bI atunci i aI. Vom nota prin I (A) mulimea idealelor lui A. 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, cci A este simultan inf i sup-semilatice); evident n acest caz A F (A)I (A). Cum intersecia oricrei familii de filtre (ideale) este de asemenea filtru (ideal), putem vorbi de filtrul (idealul) generat de o mulime nevid. Dac A este o inf(sup)-semilatice, pentru SA vom nota prin [S) ( (S]) filtrul(idealul) generat de S (adic intersecia tuturor filtrelor (idealelor) lui A ce conin pe S). Propoziia 5.11. Dac A este o inf-semilatice i S A o submulime nevid a sa, atunci: [S)={aAexist s1, s2 ,.., snS a.. s1s2 ..sna}.

    Demonstraie.Fie FS={aAexist s1, s2 ,.., snS a.. s1s2 ..sna}. Se probeaz imediat c FS F (A) i S FS, deci [S) FS .

    Dac FF(A) a.. S F atunci FSF deci FSF=[S),de unde [S)=FS .n Dual se demonstreaz: Propoziia 5.12. Dac A este o sup-semilatice i SA este o submulime nevid a sa, atunci: (S]={aAexist s1, s2 ,.., snS a.. a s1 s2 .. sn}.

  • 56

    Astfel, (F(A),) i (I(A),) sunt latici n care pentru F1, F2F(A) (respectiv I1, I2I(A)) avem F1F2=F1F2 iar F1F2=[F1F2) (respectiv I1I2=I1I2 iar I1I2=(I1I2] ).

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

    ( (a]) filtrul (idealul) generat de {a}. Conform celor de mai sus avem c: [a)={xAax} i

    (a]={xAxa} ([a), (a] poart numele de filtrul (idealul) principal generat de a).

    Teorema 5.13. Fie (A, ) o mulime ordonat. Atunci A este izomorf cu o mulime de submulimi ale lui A (ordonat cu incluziunea). Demonstraie. Pentru fiecare aA considerm Ma={xAxa}A. Deoarece pentru a, bA, a b avem Ma 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 bine ordonat este inf-complet i total ordonat) ii) O mulime ordonat n care orice submulime total ordonat a sa are un majorant (minorant) se zice inductiv (coinductiv) ordonat.

    Dup cum vom vedea n 9 (, ) este un exemplu de mulime bine ordonat.

    n cele ce urmeaz, acceptm c pentru orice mulime M este verificat axioma alegerii:

    Exist o funcie s : P(M) M a.. s(S)S pentru orice submulime nevid S a lui M.

    n continuare, reamintim un rezultat datorat lui Bourbaki i cteva corolare importante ale acestuia (pentru demonstraii recomandm cititorului lucrarea [23]).

  • 57

    Lema 5.15. (Bourbaki). Dac (A, ) este o mulime nevid,

    inductiv ordonat i f : A A este o aplicaie a.. f (a) a pentru orice aA, atunci exist uA a.. f (u) =u.

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

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

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

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

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

  • 58

    S notm c exist latici ce nu sunt modulare. ntr-adevr, dac vom considera laticea notat tradiional prin N5 : 1 c b a 0 observm c a c, pe cnd a (b c) = a 0 = a iar (a b) c= =1 c a, astfel c c (b a) (c b) a, deci N5 nu este modular. Teorema 5.17. (Dedekind). Pentru o latice L urmtoarele afirmaii sunt echivalente: (i) L este modular (ii) Pentru orice a, b, cL, dac c a, atunci a (b c) (a b) c (iii) Pentru orice a, b, cL avem ((ac) b) c = (ac) (bc) (iv) Pentru orice a, b, cL, dac a c, atunci din a b =c b i a b= c b deducem c a = c (v) L nu are sublatici izomorfe cu N5. Demonstraie. Cum n orice latice, dac c a, atunci (a b) c a (b c), echivalena (i) (ii) este imediat. (i) (iii). Rezult din aceea c a c c. (iii) (i). Fie a, b, c L a.. a c. Atunci a = a c, deci (a b) c = ((a c) b) c = (a c) (b c) = a (b c).

  • 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, c n L a.. a c, iar a (b c) (a b) c. S observm c bc <

  • 60

    2. (, | ), (P (M), ) Ld (0, 1). Observaia 6.1. Raionnd inductiv dup n*, deducem c dac S1, S2, ..., Sn sunt submulimi nevide ale unei latici distributive

    L, atunci: ( ) ( )

    ===

    n

    n

    ii

    n

    iSSfifS ...111

    .

    Teorema 6.2. Pentru LL urmtoarele afirmaii sunt echivalente: (i) L Ld (ii) a (b c) (a b) (a c) pentru orice a, b, c L (iii) (a b) (b c) (c a) = (a b) (b c) (c a) pentru orice a, b, cL (iv) Pentru orice a, b, cL, dac a c = b c i a c = b c, atunci a = b (v) L nu are sublatici izomorfe cu N5 sau M3, unde M3 are urmtoarea diagram Hasse: 1 b a c 0 Demonstraie. (i) (ii). Rezult din aceea c pentru oricare elemente a, b, c L, (a b) (a c) a (b c). (i) (iii). S presupunem c L Ld i fie a, b, c L. Atunci (a b) (b c) (c a) = (((a b) b) ((a b) c)) (c a) =

  • 61

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

  • 62

    u

    b a c d Cum {d, a, b, c, u}L este sublatice, dac vom verifica faptul c elementele d, a, b, c, u sunt distincte, atunci sublaticea {d, a, b, c, u} va fi izomorf cu M3 ceea ce va fi contradictoriu cu ipoteza pe care o acceptm.

    Deoarece d < u, vom verifica egalitile a b = = b c=c a = u, a b = b c = c a = d i atunci va rezulta i c cele 5 elemente d, a, b, c, u sunt distincte.

    Datorit modularitii lui L avem: a = d (a u), b = =d (b u), c = d (c u) iar datorit simetriei este suficient s demonstrm doar c a c = d.

    ntr-adevr, a c = ((d a) u) ((d c) u) = =(d a) (d c) u = ((a b) (b c) (c a) a) (d c) u = =((b c) a) (d c) u = ((b c) a) ((a b) c) (a b) (b c) (c a) = ((b c) a) ((a b) c) = =(b c) (a ((a b) c)) = (datorit modularitii) = =(b c) (((a b) c) a)= (b c) ((a b) (c a)) = (datorit modularitii) = d. n

  • 63

    Corolar 6.3. O latice L este distributiv dac i numai dac pentru oricare dou ideale I, J I (L), I J = {i j | i I i j J}.

    Demonstraie. S presupun c L este distributiv. innd cont de Propoziia 5.12., pentru tI J exist i I, j J a.. t i j, astfel c t = (t i) (t j) = i j cu i = t i I iar j = t j J. Pentru a proba afirmaia reciproc, s presupun prin absurd c L nu este distributiv i s artm c exist I, JI (L) ce nu verific ipoteza. Conform Teoremei 6.2., L conine elementele a, b, c care mpreun cu 0 i 1 formeaz laticile N5 sau M3. Fie I = (b], J = (c]. Cum a b c deducem c aI J. Dac am avea a=i j cu iI i jJ, atunci j c, deci j a c < b, adic jJ i astfel a = i j I - absurd! n Corolar 6.4. Fie LLd iar I, JI(L). Dac I J i IJ sunt ideale principale, atunci I i J sunt ideale principale.

    Demonstraie. Fie I J = (x] i I J = (y]. Conform Corolarului 6.3., y = i j cu iI i jJ. Dac c = x i i b = x j, atunci cI i bJ. S probm c I = (c] i J = (b]. Dac prin absurd J(b], atunci exist aI, a > b iar {x, a, b, c, y} este izomorf cu N5 - absurd! Analog, dac I (c], gsim o sublatice a lui L izomorf cu M3 ceea ce este din nou absurd! n Corolar 6.5. Fie L o latice oarecare i x, yL. Atunci (x] (y]=(x y] iar (x y](x] (y]; dac LLd, atunci (x] (y] = (x y]. Demonstraie. Egalitatea (x] (y] = (x y] se probeaz imediat prin dubl incluziune iar incluziunea (x y](x] (y] rezult

  • 64

    din Propoziia 5.12. Dac LLd , atunci conform Corolarului 6.3., (x] (y] = {i j | i (x] i j (y]} = {i j | i x i j y}, de unde rezult imediat c (x] (y] (x y], deci (x y]=(x] (y]. n 7. Complement i pseudocomplement ntr-o latice. Algebre Boole. Definiia 7.1. Fie L o latice mrginit. Vom spune c elementul aL are un complement n L dac exist aL a.. a a = 0 i a a = 1 (a se va numi complementul lui a). Vom spune despre laticea L c este complementat dac orice element al su are un complement. Dac L este o latice oarecare i a, b L, a b, prin complementul relativ al unui element x[a, b] din intervalul [a, b], nelegem acel element x[a, b] (dac exist!) pentru care x x = a i x x = b. Vom spune despre o latice L c este relativ complementat dac orice element al su admite un complement relativ n orice interval din L ce-l conine. Lema 7.2. Dac LL(0, 1), atunci un element al lui L poate avea cel mult un complement.

    Demonstraie. Fie aL iar a, a doi complemeni ai lui a. Atunci a a = a a = 0 i a a = a a = 1, de unde a = a (conform Teoremei 6.2, (iv)). n Lema 7.3. Orice latice L modular i complementat este relativ complementat.

  • 65

    Demonstraie. Fie b, c L, b c, a [b, c] i a L com- plementul lui a n L. Dac vom considera a = (a b) c [b, c], atunci a a= a [(a b) c] = [(a a) (a b)] c = (a b) c = =b c= b iar a a= a [(a b) c] = (a a b) (a c) = 1 c = c, adic a este complementul relativ al lui a n [b, c]. n

    Lema 7.4. (De Morgan) Fie LLd(0, 1), a, bL avnd complemenii a, b L. Atunci a b, a b au complemeni n L i anume (a b) = a b iar (a b) = a b.

    Demonstraie. Conform Lemei 7.2 i principiului dualizrii, este suficient s probm c (a b) (a b) = 0 iar (a b) (a b) = 1. ntr-adevr, (a b) (a b) = (a b a) (a b b) = 0 0 = 0 iar (a b) (a b) = (a a b) (b a b) = 1 1 = 1. n Observaia 7.5. Dac LLd (0, 1) i aL are un complement aL, atunci a este cel mai mare element al lui L cu proprietatea c a a=0 (adic a = sup ({x L | a x = 0}). Aceast observaie ne conduce la: Definiia 7.6. Fie L o inf-semilatice cu 0 i aL. Un element a*L se zice pseudocomplementul lui a dac a*= sup ({x L | a x = 0}). Dac orice element al lui L are pseudocomplement, vom spune c inf - semilaticea L este pseudocomplementat O latice L se zice pseudocomplementat, dac privit ca inf-semilatice este pseudocomplementat. Lema 7.7. Dac L este o latice modular mrginit, atunci orice element ce are un complement a l va avea pe a i ca pseudocomplement.

  • 66

    Demonstraie. ntr-adevr, fie aL, a un complement al lui a i bL a.. a b i b a = 0. Atunci b = b 1 = b (a a) = a (b a) = a 0 = a. n Teorema 7.8. Fie LLd (0) pseudocomplementat, R (L) = {a* | a L} iar D (L) = {a L | a* = 0}. Atunci, pentru a, b L avem: 1) a a* = 0 iar a b = 0 a b* 2) a b a* b* 3) a a** 4) a* = a*** 5) (a b)* = a* b* 6) (a b)** = a** b** 7) a b = 0 a** b** = 0 8) a (a b)* = a b* 9) 0* = 1, 1* = 0 10) a R (L) a = a** 11) a, b R (L) a b R (L) 12) sup )(LR {a, b} = (a b)** = (a* b*)*

    13) 0, 1 R (L), 1 D (L) i R (L) D (L) = {1} 14) a, b D (L) a b D (L) 15) a D (L) i a b b D (L) 16) a a* D (L). Demonstraie. 1) Rezult din definiia lui a*. Echivalena rezult din definiia lui b*. 2) Deoarece b b* = 0, atunci pentru a b, deducem c a b*= 0, adic b* a*. 3) Din a a* = 0 deducem c a* a = 0, adic a (a*)* = a**. 4) Din a a** i 2) deducem c a*** a* i cum din 3) deducem c a* (a*)** = a*** rezult c a* = a***.

  • 67

    5) Avem (a b) (a* b*) = (a a* b*) (b a* b*) = =0 0 = 0. Fie acum x L a.. (a b) x = 0. Deducem c (a x) (b x) = 0, adic a x = b x = 0, de unde x a*, x b*, adic x a* b*. Restul afirmaiilor se probeaz analog. n Observaia 7.9. 1. Elementele lui R (L) se zic regulate iar cele ale lui D (L) dense. 2. innd cont de 4) i 10) deducem c R (L) = { a L / a** = a}. 3. Din 14) i 15) deducem c D (L) F (L). Teorema 7.10. Fie LLd i aL. Atunci fa : L (a] [a), fa (x) = (x a, x a) pentru xL este un morfism injectiv n Ld. n cazul n care LLd (0, 1), atunci fa este izomorfism n Ld (0, 1) dac i numai dac a are un complement. Demonstraie. Faptul c fa este morfism de latici este imediat. Fie acum x, y L a.. fa (x) = fa (y) adic x a = y a i x a = =y a. Cum LLd, atunci x = y (conform Teoremei 6.2.), deci fa este ca funcie o injecie, adic fa este morfism injectiv n Ld. S presupunem acum c LLd (0, 1). Dac fa este izomorfism n Ld (0, 1), atunci pentru (0, 1) (a] [a) va exista xL a.. f (x) = (0, 1), adic a x = 0 i a x = 1, de unde x = a. Reciproc, dac a L este complementul lui a, pentru (u, v) (a] [a) alegnd x = (ua) v deducem imediat c fa (x) = =(u, v), adic fa este i surjecie, deci izomorfism n Ld (0, 1). n Definiia 7.11. Numim latice Boole orice latice complementat din Ld (0, 1). Exemple. 1. Lanul trivial 1 = {} ca i 2 = {0, 1} (n care 0 = 1 i 1 = 0). De fapt 1 i 2 sunt singurele lanuri ce sunt latici Boole.

  • 68

    2. Pentru orice mulime M, (P(M), ) este o latice Boole n care pentru orice X M, X = M \ X = CM (X). 3. Fie n, n 2 iar Dn mulimea divizorilor naturali ai lui n. Mulimea ordonat (Dn, ) este latice Boole n este liber de ptrate (n care caz pentru p, q Dn, p q = (p, q), p q =

    = [p, q], 0 = 1, 1 = n iar p = n / p). 4. Fie M o mulime iar 2M = {f : M 2}. Definim pe 2M relaia de ordine f g f (x) g (x) pentru orice xM. Astfel (2M, ) devine latice Boole (n care caz pentru f 2M, f = 1 - f). Definiia 7.12. Din punctul de vedere al Algebrei Universale, prin algebr Boole nelegem o algebr (B, , , , 0, 1) de tipul (2, 2, 1, 0, 0) (cu i operaii binare, o operaie unar iar 0, 1 B operaii nule) a.. B1: (B, , ) Ld B2: Sunt verificate identitile x 0 = 0, x 1 = 1

    x x = 0, x x = 1. n cele ce urmeaz prin B vom desemna clasa algebrelor Boole. Dac B1, B2 B, f : B1 B2 va fi morfism de algebre Boole dac f este morfism n Ld (0, 1) i n plus f (x) = (f (x)) pentru orice x B1.

    Morfismele bijective din B se vor numi izomorfisme. Propoziia 7.13. (Glivenko) Fie (L, , *, 0) o inf-semilatice pseudocomplementat iar R (L) = {a* | a L}. Atunci, cu ordinea indus de pe L, R (L) devine algebr Boole. Demonstraie. innd cont de Teorema 7.8. deducem c L este mrginit (1 = 0*) iar pentru a, b R (L), a b R (L) iar

  • 69

    sup R (L) {a, b} = (a* b*)* astfel c R (L) este latice mrginit i sub-inf-semilatice a lui L. Deoarece pentru aR (L), a a* = (a* a**)* = 0* = 1 i a a* = 0 deducem c a* este complementul lui a n R (L). Mai rmne de probat faptul c R (L) este distributiv. Pentru x, y, z R (L), x z x (y z) i y z x (y z), deci x z [x (y z)]* = 0 i (y z) [x (y z)]* = 0 astfel c z [x (y z)]* x*, y*, adic z [x (y z)]* x* y* i z [x (y z)]* (x* y*)* = 0 ceea ce implic z (x* y*) [x (y z)]**. Cum partea stng a acestei ultime inegaliti este z (x y) iar partea dreapt este x (y z) (n R (L)), deducem c z (x y) x (y z), adic R (L) este i distributiv. n Lema 7.14. Fie B B i a, bB a.. a b = 0 i a b = 1. Atunci b = a.

    Demonstraie. Rezult imediat din Lema 7.2. Lema 7.15. Dac B B i a, b B, atunci (a) = a, (a b)=a b iar (a b) = a b.

    Demonstraie. Rezult imediat din Lema 7.4.. Propoziia 7.16. Dac M este o mulime oarecare, atunci algebrele Boole 2M i P(M) sunt izomorfe. Demonstraie. Fie XP(M) i Xa :M2,

    ( )

    =

    Xxpentru

    XxpentruxX 1

    0a

    Se verific imediat c asocierea X aX definete un

    izomorfism de algebre Boole a : P(M) 2M. n Pentru B B i aB, vom nota I (a) = [0, a].

  • 70

    Propoziia 7.17. Pentru orice a B: (i) (I (a), , , *, 0, a) B, unde pentru x I(a), x* = x a (ii) aa : B I (a), aa (x) = a x pentru xB este un morfism surjectiv din B (iii) B I (a) I (a). Demonstraie. (i). I (a) Ld (0, 1) (ca sublatice a lui B). Pentru xI (a), x x*= x (x a) = (x x) a = 0 a = 0 iar x x* = =x (x a)= (x x) (x a) = 1 (x a) = x a = a. (ii). Dac x, y B, atunci aa (x y) = a (x y) = =(a x) (a y)= aa (x) aa (y), aa (x y) = a (x y) = =(a x) (a y) = aa (x) aa (y), aa (x) = a x = =(a a) (a x) = a (a x) =a (a x) = (aa (x))*, aa (0) = 0 iar aa (1) = a, adic aa este morfism surjectiv n B.

    (iii). Se verific uor c a : B I (a) I (a), a (x) = =(a x, a x) pentru