Capitolul I

Notiuni preliminare

§1.1. Multimi

Notiunea de multime nu se defineste, este una primara.Prin multime vom ıntelege o colectie de obiecte ce poseda anu-

mite proprietati caracteristice. Aceste obiecte se numesc elementelemultimii.

Vom nota, de regula, multimile cu litere mari, iar elementele lor culitere mici ale alfabetului latin. Daca A este o multime si x un elemental sau, atunci vom scrie x ∈ A, iar daca y nu este un element al multimiiA, vom scrie y 6∈ A.

Se considera ca o multime este cunoscuta atunci cand ıi cunoastemelementele. A indica o multime ınseamna a preciza care sunt elementeleei. Acest lucru poate fi realizat enumerand elementele multimii sauindicand o proprietate caracteristica doar elementelor multimii date.

In primul caz multimea se indica scriind ıntre acolade elementelesale {a, b, c, ...}. De exemplu, A = {1, 2, ..., 9}.

In cazul al doilea notam A = {x|P (x)}, adica A este multimeaacelor obiecte x pentru care are loc P (x). De exemplu,

B = {x | x ∈ R, 2x2 + x− 1 = 0}.O multime care are un numar finit de elemente se numeste multime

finita. In caz contrar multimea se numeste infinita. Multimea care nuare nici un element se numeste multime vida si se noteaza ∅.

Daca fiecare element al unei multimi A apartine multimii B, atunciA se numeste submultime (sau parte) a multimii B si se noteazaA ⊆ B. Multimea vida este o submultime a oricarei multimi. Spunemca multimile A si B coincid daca A ⊆ B si B ⊆ A. Daca A ⊆ B siA 6= B, atunci vom mai nota A ⊂ B.

Multimea tuturor submultimilor unei multimi A se noteaza cu B(A)si se numeste booleanul multimii A.

Daca A si B sunt doua multimi, atunci intersectia lor A ∩ B si

6

reuniunea lor A ∪B se definesc ın felul urmator:

A ∩B = {x|x ∈ A si x ∈ B},

A ∪B = {x|x ∈ A sau x ∈ B}.In cazul A ∩ B = ∅ spunem ca multimile A si B sunt disjuncte.

Multimea B \ A = {x ∈ B|x 6∈ A} se numeste diferenta multimilor Bsi A. Daca A ⊆ B, atunci diferenta B \ A se numeste complementaramultimii A ın B si se noteaza cu CBA sau AC . In particular, CB∅ = B,iar CBB = ∅.

Pentru orice trei multimi A,B si C au loc urmatoarele egalitati:

A ∩A = A,A ∪A = A,A ∩B = B ∩A, A ∪B = B ∪A,

(A ∩B) ∩ C = A ∩ (B ∩ C), (A ∪B) ∪ C = A ∪ (B ∪ C),

A ∩ (A ∪B) = A,A ∪ (A ∩B) = A, A ∩∅ = ∅, A ∪∅ = A,

A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C),

A \B = A \ (A ∩B), A = (A ∩B) ∪ (A \B),

(A \B) ∩ C = (A ∩ C) \ (B ∩ C).

Daca A1 si A2 sunt doua submultimi ale multimii B, atunci au locegalitatile:

CB(A1 ∪A2) = CBA1 ∩ CBA2,

CB(A1 ∩A2) = CBA1 ∪ CBA2,

numite formulele lui de Morgan.Operatiile de reuniune ”∪” si intersectie ”∩” a multimilor pot fi

definte pentru orice totalitate de multimi {Ai|i ∈ I}. In acest cazintersectia ∩{Ai|i ∈ I} si reuniunea ∪{Ai|i ∈ I} se definesc ın felulurmator:

∩{Ai|i ∈ I} = {x|x ∈ Ai pentru orice i ∈ I},

∪{Ai|i ∈ I} = {x|∃i ∈ I astfel ıncat x ∈ Ai}.

7

In loc de ∩{Ai|i ∈ I} mai notam⋂i∈I

Ai, iar ın loc de ∪{Ai|i ∈ I} mai

notam⋃i∈I

Ai. Daca I = {1, 2, ..., n}, atunci notam⋂i∈I

Ai = A1 ∩ A2 ∩

... ∩ An si⋃i∈I

Ai = A1 ∪ A2 ∪ ... ∪ An sau⋂i∈I

Ai =n⋂

i=1Ai si, respectiv,

⋃i∈I

Ai =n⋃

i=1Ai.

Daca I = ∪{Ik|k ∈ J}, unde Is ∩ It = ∅, pentru orice s 6= t, atunciau loc egalitatile:

⋂k∈J

( ⋂i∈Ik

Ai

)=

⋂i∈I

Ai si⋃

k∈J

( ⋃i∈Ik

Ai

)=

⋃i∈I

Ai.

Aceste egalitati pot fi interpretate ca o generalizare a legii asociative.Daca A este o multime si {Bi|i ∈ I} este o totalitate de multimi,

atunci au loc egalitatile:

A⋂( ⋃

i∈I

Bi

)=

⋃i∈I

(A

⋂Bi

), A

⋃( ⋂i∈I

Bi

)=

⋂i∈I

(A⋃

Bi

)

Daca m,n ∈ N∗ si {Aij |i = 1,m, j = 1, n} este o totalitate demultimi, atunci

m⋂i=1

(n⋃

j=1Aij

)=

n⋃j=1

(m⋂

i=1Aij

).

Observam ca ultima egalitate nu admite o generalizare simpla ıncaz infinit.

Fie A si B doua multimi arbitrare. Prin produs cartezian almultimilor A si B ıntelegem multimea

A×B = {(a, b)|a ∈ A, b ∈ B}.

In perechea (a, b) primul element este din A, iar al doilea din B. Acesteperechi se numesc ordonate sau cupluri. Doua perechi ordonate (a1, b1)

8

si (a2, b2) din A×B sunt considerate egale daca si numai daca a1 = a2

si b1 = b2.Daca B = A, atunci notam A2 = A × A. Observam ca daca una

dintre multimile A si B este vida atunci A×B = ∅.In mod analog se defineste produsul cartezian al oricarui numar

finit de multimi A1, A2, ..., An. Multimea

A1 ×A2 × ...×An = {(a1, a2, ..., an)|ai ∈ Ai, i = 1, n}

se numeste produs cartezian al multimilor A1, A2, ..., An.

In acest caz mai notamn∏

i=1Ai = A1 × A2 × ... × An. Elementele

multimii A1 × A2 × ... × An se numesc uple sau consecutivitati delungime n.

Observam ca doua uple (a1, a2, ..., an), (b1, b2, ..., bn) ∈n∏

i=1Ai se con-

sidera egale daca si numai daca a1 = b1, a2 = b2, ..., an = bn.Daca A1 = A2 = ... = An = A, atunci notam An = A×A× ...×A

si numim puterea a n-a carteziana a multimii A.In teoria multimilor este admisa urmatoarea axioma, numita axi-

oma alegerii:daca S = {Ai|i ∈ I} este o familie nevida de multimi nevide, dis-

juncte doua cate doua, atunci exista o multime A (numita multimeselectiva) astfel ıncat A∩X este formata dintr-un singur element, ori-care ar fi X ∈ S.

Exercitii

1. Fie A,B si C trei multimi. Sa se demonstreze urmatoarele egalitati:a) A ∪ (A ∩B) = A = A ∩ (A ∪B);b) (A ∪B) \ C = (A \ C) ∪ (B \ C);c) A \ (B \ C) = (A \B) ∪ (A ∩ C);d) A \ (B ∪ C) = (A \B) \ C.

2. Fie M multime nevida, B(M) booleanul multimii M si A,B ∈B(M). Multimea A4B

def= (A \ B) ∪ (B \ A) se numeste diferenta

simetrica a multimilor A si B. Sa se demonstreze egalitatile urmatoare:

9

a) A4(B4C) = (A4B)4C (asociativitate);b) A ∩ (B4C) = (A ∩B)4(A ∩ C) (distributivitate);c) (A ∪B) = A4B4(A ∩B);d) A \B = A4(A ∩B).

3. Fie M o multime nevida si A, B ⊆ M. Multimea A : Bdef=

A ∪ BC , unde BC este complementara multimii B ın M , se numestecatul multimilor A si B. Sa se arate ca:

a) A : (B ∩ C) = (A : B) ∪ (A : C);b) A : (B ∪ C) = (A : B) ∩ (A : C);c) A ∩ (B : A) = A ∩B.

4. Fie A1, A2, . . . , An submultimi ale unei multimi E. Punem prindefinitie A1

i = E/Ai si A0i = Ai, ∀i = 1, n. Orice intersectie de forma

Ai11 ∩Ai2

2 ∩ ... ∩Ainn ,

unde ij ∈ {0, 1}, pentru orice j = 1, n, se numeste componenta amultimii E (ın raport cu multimile A1, A2, . . . , An). Sa se arate ca oricedoua componente ale multimii E (ın raport cu A1, A2, . . . , An) suntdisjuncte si ca reuniunea tuturor componentelor lui E este egala cu E.5. Fie A,B si C submultimi ale unei multimi E. Sa se reprezintemultimea A \ (B \ C) ca reuniune a componentelor multimii E (ınraport cu A,B si C).

§1.2. Relatii pe multimi. Functii. Numere cardinale

Prin functie (sau aplicatie) definita pe multimea nevida A cu valoriın multimea nevida B se ıntelege o corespondenta (regula) f ıntre Asi B care asociaza fiecarui element a ∈ A un element unic, notat f(a),din B. Multimea A se numeste domeniul de definitie al functiei f, iarmultimea B se numeste domeniul valorilor functiei f (sau codomeniulfunctiei f). Daca f este o functie definita pe multimea A cu valori ın

B, atunci notam f : A → B sau Af→ B.

Fie f : A → B o functie, H ⊆ A si K ⊆ B. Punem prin definitie:

f(H) = {f(x)|x ∈ H},

10

f−1(K) = {x ∈ A|f(x) ∈ K}.Multimea f(H) ⊆ B se numeste imaginea submultimii H prin functiaf , iar f−1(K) ⊆ A se numeste imaginea inversa a submultimii K prinfunctia f.

In particular, f(A) = {f(a)|a ∈ A} ⊆ B se numeste imagineafunctiei f si se noteaza cu Imf.

O functie f : A → B se numeste injectiva daca pentru orice a1, a2 ∈A, a1 6= a2, avem f(a1) 6= f(a2).

Prin urmare, o functie f : A → B este injectiva daca si numai dacaare loc implicatia

f(a1) = f(a2) ⇒ a1 = a2.

O functie f : A → B se numeste surjectiva daca pentru orice b ∈ Bexista a ∈ A astfel ıncat f(a) = b.

Prin urmare, o functie f : A → B este surjectva daca si numai dacaImf = B.

O functie se numeste bijectiva daca ea este injectiva si surjectiva.Fie date functiile f : A → B si g : B → C. Functia g ◦ f : A → C,

unde (g ◦ f)(x) = g(f(x)),∀x ∈ A, se numeste compusul functiilor f sig.

Functia 1A : A → A, 1A(x) = x, pentru ∀x ∈ A, se numeste functiaidentica a multimii A.

Este clar ca daca este data functia f : A → B, atunci 1B ◦ f =f ◦ 1A = f.

Propozitia 1. Fiind date functiile f : A → B, g : B → C sih : C → D, are loc egalitatea:

h ◦ (g ◦ f) = (h ◦ g) ◦ f.

Demonstratie. Functiile h ◦ (g ◦ f) si (h ◦ g) ◦ f au domeniul dedefinitie A si domeniul de valori D. Mai mult, pentru orice a ∈ Aavem:

(h ◦ (g ◦ f))(a) = h((g ◦ f)(a)) = h(g(f(a))),

((h ◦ g) ◦ f)(a) = (h ◦ g)(f(a)) = h(g(f(a))).

11

Prin urmare, h ◦ (g ◦ f) = (h ◦ g) ◦ f.O functie f : A → B se numeste inversabila daca exista o functie

g : B → A astfel ıncat g ◦ f = 1A si f ◦ g = 1B.¤Propozitia 2. O functie este inversabila daca si numai daca ea

este bijectiva.Demonstratie. Fie f : A → B o functie inversabila. Atunci exista

functia g : B → A astfel ıncat g ◦ f = 1A si f ◦ g = 1B. Fie a1, a2 ∈ Aastfel ıncat f(a1) = f(a2). Atunci g(f(a1)) = g(f(a2)) ⇒ 1A(a1) =1A(a2) ⇒ a1 = a2, deci f este o functie injectiva.

Daca b ∈ B, atunci notand g(b) = a ∈ A, avem: f(a) = f(g(b)) =(f ◦ g)(b) = 1B(b) = b, deci f este si surjectiva. Prin urmare, f estebijectiva.

Reciproc. Fie f : A → B o functie bijectiva. Daca b ∈ A, atunciexista un element unic a ∈ A astfel ıncat f(a) = b, deoarece f estesurjectiva si injectiva. Definim functia g : B → A astfel ıncat g(b) = adaca si numai daca f(a) = b.

Deoarece g ◦ f = 1A si f ◦ g = 1B, functia g va fi inversa functiei f,deci f este inversabila. ¤

Nota. Daca o functie f : A → B etse inversabila, atunci inversaei este unic determinata. Intr-adevar, daca g si g′ ar fi doua inverseale functiei f , atunci g ◦ f = g′ ◦ f = 1A si f ◦ g = f ◦ g′ = 1B, decig = 1A ◦ g = (g′ ◦ f) ◦ g = g′ ◦ (f ◦ g) = g′ ◦ 1B = g′ ⇒ g = g′.

Functia g (inversa functiei f) se noteaza cu f−1.Propozitia 3. Fie f : A → B si g : B → C doua functii

inversabile. Atunci functiile f−1 si g ◦ f sunt inversabile si au locegalitatile

1) (f−1)−1 = f,2) (g ◦ f)−1 = f−1 ◦ g−1.Demonstratie. 1) Din egalitatile adevarate f ◦f−1 = 1B si f−1◦f =

1A rezulta ca f−1 este inversabila si inversa ei este f, deci (f−1)−1 = f.2) Au loc egalitatile:

(g ◦ f) ◦ (f−1 ◦ g−1) = g ◦ (f ◦ (f−1 ◦ g−1)) = g ◦ ((f ◦ f−1) ◦ g−1) =

= g ◦ (1A ◦ g−1) = g ◦ g−1 = 1C si (f−1 ◦ g−1) ◦ (g ◦ f) =

12

= f−1◦(g−1◦(g◦f) = f−1◦((g−1◦g)◦f) = f−1◦(1B◦f) = f−1◦f = 1A.

Prin urmare, functia g ◦ f : A → C este inversabila si inversa ei estef−1 ◦ g−1. ¤

Propozitia 4. Fie A o multime finita si f : A → A o functie.Urmatoarele afirmatii sunt echivalente:

1) f este bijectiva;2) f este injectiva;3) f este surjectiva.Demonstratie. Implicatiile 1) ⇒ 2) si 1) ⇒ 3) sunt evidente.

Aratam ca 2) ⇒ 1) si 3) ⇒ 1).Fie A = {a1, a2, ..., an} si fie f : A → A o functie injectiva.

Atunci f(A) = {f(a1), f(a2), ..., f(an)} consta din n elemente, deoarecef(ai) 6= f(aj) pentru orice i 6= j. Cum f(A) ⊆ A, rezulta f(A) = A,deci f este si surjectiva. Astfel, am obtinut ca 2) ⇒ 1),, deci 1) ⇔ 2).

Fie acum f : A → A o functie surjectiva si b ∈ A. Atunci f−1(b) ={a ∈ A|f(a) = b} 6= ∅. Deoarece A =

⋃b∈A

f−1(b) si multimile f−1(b)

sunt disjuncte doua cate doua, rezulta ca f−1(b) are un singur element.Prin urmare, f este si injectiva, deci bijectiva. Astfel am aratat ca3) ⇒ 1), deci 1) ⇔ 3). ¤

Nota. Daca A este o multime infinita, atunci ultima propozitienu este adevarata. De exemplu, functia f : Z → Z, f(k) = 2k esteinjectiva ınsa nu este surjectiva, deoarece numerele ıntregi impare nuapartin lui Imf.

Fie date multimile A1, A2, ..., An. Orice submultime α ⊆ A1×A2×...×An se numeste relatie n-ara ıntre multimile A1, A2, ..., An.

Daca n ∈ N si A este o multime, atunci relatia α ⊆ An se numesterelatie n-ara pe multimea A.

In particular, daca A si B sunt doua multimi, atunci orice submul-time α ⊆ A×B se numeste relatie binara ıntre A si B. Daca (a, b) ∈ α,unde a ∈ A si b ∈ B, atunci spunem ca ”a este ın relatia α cu b” si mainotam aαb. Daca (a, b) 6∈ α, atunci mai notam a α b.

Cand A = B si α ⊆ A2, atunci α se numeste relatie binara pemultimea A.

13

Vom nota relatiile binare cu litere mici ale alfabetului grec sau cualte simboluri: ∼,≈,=, <, >,≤,≥ s. a.

Exemple1. Fie A = {1, 2, 3}, B = {3, 4}, α ⊂ A×B, α = {(1, 3), (1, 4), (3, 4)}.

Multimea α este o relatie binara ıntre A si B. Observam ca 1α3, 1α4, 3α4ınsa, de exemplu, 2α4.

2. Daca A este o multime nevida, atunci δA = {(a, a)|a ∈ A} esteo relatie binara pe A si se numeste diagonala multimii A.

3. Multimea{(m,n)|m,n ∈ Z,m < n}

este o relatie binara pe Z si se noteaza cu < .4. Fie f : A → B o functie. Atunci multimea G(f) = {(a, f(a))|a ∈

A} este o relatie binara ıntre A si B. Multimea G(f) se numeste graficulfunctiei f.

Observam ca daca G ⊆ A×B este o relatie ıntre A si B cu propri-etatea: oricare ar fi a ∈ A exista un singur b ∈ B, astfel ıncat (a, b) ∈ G,atunci poate fi definita o functie f : A → B astfel ıncat f(a) = b.

Este clar ca ın acest caz G = g(f) este graficul functiei f.Fie A si B doua multimi si α, β ⊆ A×B. Reuniunea α∪β, intersectia

α ∩ β, diferenta α \ β, complementara α′

si conjugata α∗ se definescın felul urmator:

α ∪ β = {(x, y) ∈ A×B|(x, y) ∈ α sau (x, y) ∈ β},

α ∩ β = {(x, y) ∈ A×B|(x, y) ∈ α si (x, y) ∈ β},α \ β = {(x, y) ∈ A×B|(x, y) ∈ α si (x, y) 6∈ β},

α′= {(x, y) ∈ A×B|(x, y) 6∈ α},

α∗ = {(y, x) ∈ B ×A|(x, y) ∈ α}.Definitie. Fie A o multime nevida si α ⊆ A2. Relatia binara α se

numeste:reflexiva daca aαa, ∀a ∈ A;simetrica daca a α b ⇒ b α a;tranzitiva daca a α b si b α c ⇒ a α c;

14

antisimetrica daca aαb si bαa ⇒ a = b;antireflexiva daca aαa, ∀a ∈ A;liniara daca pentru orice a, b ∈ A ⇒ aαb sau bαa.O relatie binara α ⊂ A2 se numeste relatie de echivalenta daca ea

este reflexiva, simetrica si tranzitiva.O relatie binara α ⊂ A2 se numeste relatie de ordine daca ea este

reflexiva, antisimetrica si tranzitiva. Daca pe multimea A este definitao relatie de ordine, atunci spunem ca multimea A este ordonata (saupartial ordonata).

O relatie de ordine α ⊆ A2 se numeste relatie de ordine stricta(nestricta) daca α este antireflexiva (reflexiva).

O relatie de ordine α ⊆ A2 se numeste relatie de ordine liniara, iarmultimea A total ordonata, daca α este o relatie liniara.

Exemple1. δR = {(x, y) ∈ R2|x = y} este o relatie de echivalenta pe

multimea numerelor reale R.2. α = {(x, y) ∈ R2|x > y} este o relatie de ordine liniara pe

multimea numerelor reale R.Definitie. Fie A o multime nevida. O familie de submultimi S =

{Ai|Ai ⊆ A, i ∈ I} se numeste partitie (sau sectiune) a multimii Adaca sunt verificate conditiile:

1) Ai 6= ∅, ∀i ∈ I;2) Ai ∩Aj 6= ∅⇒ Ai = Aj ;3)

⋃i∈I

Ai = A.

Propozitia 5. Orice relatie de echivalenta definita pe o multimenevida A determina o partitie pe A si, reciproc, orice partitie pe Adetermina o relatie de echivalenta pe A.

Demonstratie. Fie α ⊆ A2 o relatie de echivalenta pe A si a ∈ A.Consideram submultimea Ka = {x ∈ A|xαa} si multimea S =

{Ka|a ∈ A}. Aratam ca S este o partitie pe A.Deoarece α este reflexiva, avem aαa pentru orice a ∈ A, deci

a ∈ Ka, ∀a ∈ A, ceea ce implica Ka 6= ∅, ∀a ∈ A si⋃

a∈A

Ka = A.

Fie ca a, b ∈ A si c ∈ Ka ∩ Kb. Atunci cαa si cαb ⇒ aαc si cαb⇒ aαb. Avem: x ∈ Ka ⇒ xαa ⇒ xαa si aαb ⇒ xαb ⇒ x ∈ Kb, deci

15

Ka ⊆ Kb. Analog, y ∈ Kb ⇒ yαb ⇒ yαb si bαa ⇒ yαa ⇒ y ∈ Ka, deciKb ⊆ Ka. Prin urmare, daca Ka ∩Kb 6= ∅, atunci Ka = Kb.

Reciproc. Fie S = {Ai|Ai ⊆ A, i ∈ I} o partitie a multimii A.Definim pe A relatia binara α ın felul urmator:

aαb ⇔ ∃i ∈ I : a, b ∈ Ai.

Deoarece⋃i∈I

Ai = A, obtinem aαa,∀a ∈ A, deci α este reflexiva. Daca

aαb,, atunci exista i ∈ I astfel ıncat a, b ∈ Ai, deci bαa, de underezulta ca α este simetrica. Daca aαb si bαc atunci ∃i, j ∈ I astfelıncat a, b ∈ Ai si b, c ∈ Aj . Deoarece b ∈ Ai ∩Aj , rezulta Ai = Aj , decia, c ∈ Ai = Aj si atunci aαc. Prin urmare, α este si tranzitiva. Astfel,am aratat ca α este o relatie de echivalenta. ¤

Daca α este o relatie de echivalenta pe multimea A, atunci multimea(partitia) {Ka|a ∈ A}, determinata de α pe A, se noteaza cu A/α si senumeste multime factor (sau multime cat) a multimii A prin α. ClasaKa se numeste clasa de echivalenta cu reprezentantul a.

O familie de elemente {ai|ai ∈ A, i ∈ I} se numeste sistem dereprezentanti asociat relatiei de echivalenta α daca pentru orice a ∈ Aexista un singur i ∈ I astfel ıncat aαai.

Daca {ai|i ∈ I} este un sistem de reprezentanti asociat relatieide echivalenta α, definite pe A, atunci A/α = {Kai |i ∈ I}. Sistemulde reprezentanti asociat unei relatii de echivalenta nu este unic. Maimult, fiind data o relatie de echivalenta α pe multimea nevida A existaıntotdeauna un sistem de reprezentanti asociat relatiei α. Intr-adevar,daca A/α = {Ai|i ∈ I}, atunci Ai 6= ∅, ∀i ∈ I deci, conform axiomeialegerii, exista o familie de elemente {ai|i ∈ I} astfel ıncat ai ∈ Ai,oricare ar fi i ∈ I. Evident, {ai|i ∈ I} este un sistem de reprezentantipentru relatia de echivalenta α.

Exemplu. Consideram pe multimea numerelor ıntregi Z relatiabinara ” ∼ ” definita ın felul urmator:

a ∼ b ⇔ |a| = |b|

Se verifica usor ca ” ∼ ” este o relatie de echivalenta pe Z. Mai

16

mult, daca a ∈ Z, atunci

Ka ={ {a,−a} daca a 6= 0,

{0} daca a = 0.

Un sistem de reprezentanti asociat lui ” ∼ ” este multimea numerelornaturale N = {0, 1, . . .}. Un alt sistem de reprezentanti asociat lui” ∼ ” este {0,−1,−2,−3, . . .}.

Doua multimi A si B se numesc cardinal echivalente sau echipotentedaca exista o bijectie de la A la B.

In clasa tuturor multimilor relatia binara ” ∼ ”, unde A ∼ B ⇔ Asi B sunt cardinal echivalente, este o relatie de echivalenta. In acest cazclasele de echivalenta se numesc numere cardinale. Cardinalul multimiiA se noteaza cu cardA sau |A|.

Daca A este o multime finita avand n elemente, atunci o multimeB este cardinal echivalenta cu A daca si numai daca B are n elemente.Deci cardinalul multimii A este determinat de numarul de elemente almultimii A. Din aceste motive cardinalul |A| se identifica cu numarulde elemente din A, adica |A| = n. Vom considera |∅| = 0.

Daca A si B sunt doua multimi, atunci vom nota |A| ≤ |B| daca Aeste cardinal echivalenta cu o submultime a lui B. Relatia ” ≤ ” este orelatie de ordine liniara ın clasa tuturor numerelor cardinale.

Se noteaza |N| = ℵ0 (alef zero). Orice multime cardinal echivalentacu multimea numerelor naturale N se numeste numarabila. Cardinalulmultimii tuturor submultimilor multimii N (care coincide cu cardinalulmultimii numerelor reale) se noteaza cu ℵ1 sau cu c.

Se stie ca cardinalul oricarei multimi este mai mic decat cardinalulmultimii tuturor submultimilor sale, ınsa cardinalul multimii tuturorsubmultimilor finite ale unei multimi infinite A este egal cu cardinalulmultimii A.

Pentru orice trei multimi A,B si C au loc relatiile:1) |A| ≤ |B| ⇒ |A× C| ≤ |B × C|;2) daca A este infinita, iar B numarabila, atunci |B| ≤ |A| si

|A ∪B| = |A|;

17

3) daca A este infinita si n ∈ N∗, atunci |An| = |A|;4) orice multime infinita A poate fi reprezentata ca reuniune de

submultimi disjuncte doua cate doua, cardinal echivalente lui A, astfelıncat multimea formata din aceste submultimi este cardinal echivalentacu A;

5) daca A este infinita, atunci |A ∪B| ≤ max{|A|, |B|};6) daca B este infinita, A 6= ∅ si |A| ≤ |B|, atunci |A×B| = |B|.Notiunea de cardinal al multimii a fost introdusa de G.Cantor

(ıntemeietorul teoriei multimilor) ın a. 1878. G.Cantor a aratat, ın par-ticular, ca cardinalul multimii numerelor reale este mai mare decat ℵ0,demonstrand astfel ca multimile pot avea cardinal diferit. Spunem camultimea numerelor reale este de cardinal continuum. G.Cantor a emisipoteza (numita continuum-ipoteza) ca orice submultime a multimii nu-merelor reale este sau finita, sau numarabila, sau este cardinal echiva-lenta cu multimea tuturor numerelor reale. In prezent se cunoaste caaceasta ipoteza nu poate fi nici confirmata, nici infirmata prin mij-loacele teoriei multimilor.

Exercitii

1. Fie A si B doua multimi nevide si f : A → B o functie. Sa se arateca f este injectiva daca si numai daca f(X∩Y ) = f(X)∩f(Y ), pentruorice X,Y ∈ B(A).2. Fie f : A → B o functie. Demonstrati afimatiile:

a) f este injectiva daca si numai daca f(CAX) ⊆ CBf(X) oricarear fi X ∈ B(A);

b) f este surjectiva daca si numai daca CBf(X) ⊆ f(CAX) oricarear fi X ∈ B(A);

c) f este bijectiva daca si numai daca f(CAX) = CBf(X) oricarear fi X ∈ B(A).3. Fie A si B doua multimi, |A| = n si |B| = m, unde n ≤ m. Sa searate ca exista An

m functii injective de la A la B.4. Fie A si B doua multimi, |A| = n si |B| = m, unde n ≥ m. Sa searate ca numarul functiilor surjective de la A la B este egal cu

mn −C1m(m− 1)n + C2

m(m− 2)n −C3m(m− 3)n + ... + (−1)m−1Cm−1

m .

18

5. Fie f : A → B o functie. Pe multimea B(A) (multimea partilor luiA) definim functia

ϕ : B(A) → B(A), ϕ(X) = f−1(f(X)), ∀X ∈ B(A).

Sa se rate ca:a) ϕ ◦ ϕ = ϕ;b) f este injectiva daca si numai daca ϕ = εB(A).

6. Fie f : A → B o functie. Pe multimea B(B) (multimea partilor luiB) definim functia

ψ : B(B) → B(B), ψ(Y ) = f(f−1(Y )), ∀Y ∈ B(B).

Sa se arate ca:a) ψ ◦ ψ = ψ;b) f este surjectiva daca si numai daca ψ = εB(B).

7. Fie date aplicatiile f : A → B, g : B → C. Sa se demonstrezeurmatoarele afirmatii:

a) daca f si g sunt injectvie, atunci g ◦ f este injectiva;b) daca f si g sunt surjective, atunci g ◦ f este surjectiva;c) daca f si g sunt bijective, atunci g ◦ f este bijectiva;d) daca g ◦ f este injectiva, atunci f este injectiva;e) daca g ◦ f este surjectiva, atunci g este surjectiva.

8. Sa se arate ca nu exista functii f : R→ R bijective astfel ıncat:a) (f ◦ f)(x) = x2, ∀x ∈ R;b) (f ◦ f)(x) = x4 + 1, ∀x ∈ R;c) (f ◦ f)(x) = x2 + 3,∀x ∈ R;d) (f ◦ f)(x) = |x|+ 4,∀x ∈ R.

9. Sa se verifice daca relatia α este reflexiva, simetrica, tranzitiva,antisimetrica, antireflexiva, liniara:

a) α = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)(3, 4)} ⊂ {1, 2, 3,4} × {1, 2, 3, 4};

b) α = {(1, 2), (1, 3), (2, 1), (3, 1), (3, 4), (4, 3)} ⊂ {1, 2, 3, 4} ×{1, 2, 3, 4};

c) α = {(x, y) ∈ R2|x > 1 si y > 1};d) α = {(x, y) ∈ R2|x ≥ 0 sau y < 0};

19

e) α = {(x, y) ∈ R2|x2 = y2};f) α = {(x, y) ∈ R2|x2 + x = y2 + y}.

10. Este data multimea A si relatia binara α ⊆ A2. Sa se demonstrezeca α este o relatie de echivalenta si sa se determine multimea factorA/α.

a) A = {1, 2, 3}, α = {(1, 1), (1, 3), (3, 1), (2, 2), (3, 3)};b) A = {1, 2, 3, 4}, α = {(1, 1), (1, 2), (1, 3), (2, 1), (3, 1),

(2, 2), (3, 3), (4, 4), (3, 2), (2, 3)};c) A = {1, 2, 3, 4}, α = {(1, 4), (1, 1), (4, 1), (1, 2), (2, 1),

(3, 3), (2, 2), (2, 4), (4, 2), (4, 4)};d) A = {1, 3, 5, 6}, α = {(1, 6), (6, 1), (1, 1), (6, 6), (3, 3), (5, 5)}.

11. Fie data multimea A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Sa se arate ca sis-temul de submultimi S = {Ai ⊆ A|i = 1, n} este o partitie a multimii Asi sa se defineasca o relatie de echivalenta α pe A astfel ıncat A/α = S.

a) A1 = {1, 2, 3, 8, 9}, A2 = {4}, A3 = {5, 6, 7}.b) A1 = {1, 2}, A2 = {3, 4}, A3 = {5, 6}, A4 = {7, 8}, A5 = {9};c) A1 = {1}, A2 = {2, 3, 4}, A3 = {5, 6}, A4 = {7, 8, 9};d) A1 = {1, 3, 5, 7, 9}, A2 = {2, 4, 6, 8}.

12. Consideram pe R relatia binara α = {(x, y) ∈ R2| sin2 x− 2 sin x =sin2 y − 2 sin y}. Sa se arate ca α este o relatie de echivalenta. Sa sedetermine clasele de echivalenta.

§1.3. Multimi ordonate

Amintim ca o relatie binara definita pe o multime nevida A senumeste relatie de ordine daca ea este reflexiva, antisimetrica si tranz-itiva. De obicei, relatia de ordine se noteaza cu simbolul ≤ si se scriea ≤ b ın loc de (a, b) ∈ ≤ . O multime A pe care s-a definit o relatiede ordine ” ≤ ” se numeste multime ordonata (sau partial ordonata)si se noteaza (A,≤). Daca ” ≤ ” este o relatie de ordine liniara pe A,atunci A se numeste multime total ordonata sau lant.

Exemple1. Multimea numerelor naturale N ımpreuna cu relatia obisnuita

de ordine ” ≤ ” este total ordonata.

20

2. Booleanul B(M) al unei multimi M, ımpreuna cu relatia deincluziune ” ⊆ ”, este o multime total ordonata.

3. Orice multime nevida este o multime partial ordonata cu diago-nala ın calitate de relatie de ordine.

Daca (A,≤) este o multime ordonata si ∅ 6= B ⊆ A, atunci B esteo multime ordonata ın raport cu relatia de ordine B × B ∩ ≤ . Inacest caz spunem ca B este o multime ordonata ın raport cu ” ≤ ”.Astfel, orice submultime nevida a unei multimi, pe care este definita orelatie de ordine, este o multime ordonata ın raport cu aceeasi relatiede ordine.

Fie (A,≤) o multime ordonata. Elementul a ∈ A se numeste max-imal (respectiv, minimal) daca a ≤ x (respectiv x ≤ a) implica a = x.Daca B ⊆ A, atunci un element a ∈ A se numeste majorant (respectivminorant) al submultimii B daca x ≤ a (respectiv a ≤ x) pentru oricex ∈ B. O multime ordonata (A,≤) se numeste inductiva daca oricesubmultime total ordonata a multimii A poseda un majorant.

Lema lui Zorn. Orice multime ordonata nevida inductiva are celputin un element maximal.

Un element a al unei multimi ordonate (A,≤) se numeste primelement (respectiv, ultim element) al lui A daca a ≤ x (respectiv,x ≤ a) pentru orice x ∈ A. Multimea ordonata (A,≤) se numeste bineordonata daca orice submultime nevida a sa are un prim element.

Din definitie rezulta ca orice multime bine ordonata este total ordo-nata. Un exemplu de multime bine ordonata este multimea numerelornaturale ın raport cu relatia de ordine ” ≤ ”.

Teorema lui Zermelo. Pe orice multime nevida A exista o relatiede ordine ” ≤ ”, astfel ıncat (A,≤) este o multime bine ordonata.

Se stie ca Axioma alegerii, Lema lui Zorn si Teorema lui Zermelosunt afirmatii echivalente. Pana ın prezent a fost demonstrata doarechivalenta acestor afirmatii, nu si ınsesi afirmatiile.

Fie (A,≤) o multime ordonata si B ⊆ A. Elementul a ∈ A senumeste superiorul (respectiv, inferiorul) submultimii B daca x ≤ apentru orice x ∈ B si daca exista un element a

′ ∈ A cu proprietateax ≤ a

′, ∀x ∈ B, atunci a ≤ a

′(respectiv, a ≤ x, ∀x ∈ B si daca

21

a′ ≤ x,∀x ∈ B, atunci a

′ ≤ a). Elementul a (daca exista) se noteazacu supB (respectiv, infB).

O multime ordonata (A,≤) se numeste latice daca pentru oricedoua elemente a, b ∈ A exista superiorul sup{a, b} si inferiorul inf{a, b}.De obicei sup{a, b} se noteaza cu a ∨ b iar inf{a, b} cu a ∧ b.

Orice multime total ordonata este o latice.O latice se numeste completa daca orice submultime nevida a

multimii A are superior si inferior ın A.O latice (A,≤) se numeste modulara daca pentru orice trei elemente

a, b, c ∈ A, unde b ≤ a, are loc egalitatea a ∧ (b ∨ c) = b ∨ (a ∧ c).Daca (A,≤) este o latice, atunci pentru orice x, y, z ∈ A au loc

urmatoarele doua afirmatii:1) sup{x, inf{y, z}} ≤ inf{sup{x, y}, sup{x, z}};2) inf{x, sup{y, z}} ≥ sup{inf{x, y}, inf{x, z}}.Insa ın orice latice (A,≤) sunt echivalente afirmatiile:a) sup{x, inf{y, z}} = inf{sup{x, y}, sup{x, z}},

∀x, y, z ∈ A;b) inf{x, sup{y, z}} = sup{inf{x, y}, inf{x, z}},

∀x, y, z ∈ A.O latice care verifica una din conditiile a) sau b) se numeste dis-

tributiva.De exemplu, orice multime total ordonata este o latice distributiva.Relatia de incluziune ” ⊆ ” determina pe booleanul B(A) al unei

multimi arbitrare A o relatie de ordine (partiala), astfel ıncat (B(A),⊆)este o latice completa.

Notiunea de latice este un concept foarte general, continut im-plicit ın majoritatea ramurilor matematicii, unde se ıntalnesc multimipartial ordonate (logica matematica, algebra, teoria multimilor, topolo-gia, teoria probabilitatilor, analiza functionala, geometria proiectivaetc.). Teoria laticelor contribuie la unificare unor aspecte fundamen-tale comune celor mai multe ramuri ale matematicii.

22

Exercitii

1. Definim pe multimea numerelor complexe C relatia α ın felulurmator:

(a + bi)α(c + di) ⇔ a < c sau (a = c si b ≤ d).

a) Sa se arate ca α este o relatie de ordine pe C.b) Sa se determine superiorul si inferiorul submultimilor

A = {z ∈ C| |z| < 2} si B = {z ∈ C | 1 ≤ Rez ≤ 2, 2 ≤ Imz ≤ 3}.c) Indicati primul element si ultimul element (ın caz ca exista) ın

multimile A si B.d) Indicati multimea M1 a tuturor minorantilor multimii A si

multimea M2 a tuturor majorantilor multimii B.2. Fie A o multime ordonata care poseda prim element si ultim element.Sa se arate ca exista inferiorul oricarei submultimi nevide a lui A dacasi numai daca exista superiorul oricarei submultimi nevide a lui A.3. Fie A o latice si x, y, z ∈ A. Sa se arate ca sunt adevarate urmatoareleafirmatii:

a) sup(x, inf(y, z)) ≤ inf(sup(x, y), sup(x, z));b) inf(x, sup(y, z)) ≥ sup(inf(x, y), inf(x, z)).

4. Daca A este o latice, atunci urmatoarele afirmatii sunt echivalente:a) x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) oricare ar fi x, y, z ∈ A;b) x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) oricare ar fi x, y, z ∈ A.

5. Sa se arate ca multimea numerelor naturale cu relatia de divizibili-tate este o latice distributiva.

23