MULTIMI, FUNCTII, PRODUS CARTEZIAN

NOTIUNI PRELIMINARE

1. MULTlMI

Prin multime intelegem o colectie de obiecte care se numesc elementele multimii. Vom nota cu litere mari multimile, cu litere mici elementele lor. Daca A este o multime si x un element al sau, vom scrie x I A si vom citi ,,x apartine lui A'. Daca x nu se gaseste in A, atunci vom scrie x A si vom citi ,,x nu apartine lui A'.

Exista doua moduri de definire (de determinare) a unei multimi:   

i) Numind individual elementele sale. In acest caz, multimea se specifica scriind intre acolade elementele sale . De exemplu, A = , adica multimea formata din primele patru numere naturale; B = adica multimea formata din primele cinci litere ale alfabetului latin.

ii) Specificand o proprietate pe care o au elementele sale si nu le au alte elemente. Mai precis, data o proprietate se poate vorbi de multimea acelor obiecte pentru care proprietatea respectiva are loc. Multimile definite in acest mod se vor nota prin A = adica multimea acelor obiecte x pentru care are loc P(x).

De exemplu, sa consideram proprietatea a fi numar natural par'; in acest caz multimea A va fi multimea numerelor naturale pare.

O multime care are un numar finit de elemente se zice finita. In caz contrar se numeste infinita.

Pentru cateva multimi care vor fi des utilizate avem notatii speciale: cu N vom nota multimea numerelor naturale, adica N = . Cu N* vom nota multimea    numerelor naturale nenule, adica N = . Cu Z vom nota multimea numerelor intregi, cu Q multimea numerelor rationale, cu R multimea numerelor reale, iar cu C multimea numerelor complexe.

In teoria multimilor se admite existenta unei multimi care nu are nici un element, aceasta se numeste multimea vida si se noteaza cu simbolul

Daca A si B sunt doua multimi, vom spune ca A este o submultime a lui B (sau A este continuta, respectiv inclusa in B) si vom scrie A B daca orice element al multimii A este si element al multimii B. Simbolic scriem astfel: x, x I A T x I B.

Multimea vida este o submultime a oricarei multimi. Intre multimile considerate mai inainte avem incluziunile: N* N Z Q R C.

Doua multimi A si B se zice ca sunt egale daca au aceleasi elemente, adica A = B A B si B A (" " inseamna 'daca si numai daca').

Relatia de incluziune (resp. relatia de egalitate) intre multimi are proprietatile urmatoare:

a) este reflexiva, adica A A (resp. A = A);

b) este antisimetrica, adica din A B si B A rezulta A = B (resp. este simetrica adica A = B T B = A);

c) este tranzitiva, adica A B si B C T A C (resp. A = B si B = C T A = C).

Relatia de incluziune ne permite sa definim multimea partilor unei multimi T, notata cu P(T), adica P(T) are ca elemente toate submultimile multimii T.

Cu multimi se fac urmatoarele operatii:

. intersectia a doua multimi A si B inseamna multimea

A B = ;

. reuniunea multimilor A si B inseamna multimea

A B = .

In cazul cand A B = , atunci spunem ca multimile A si B sunt disjuncte

Operatiile de intersectie si reuniune satisfac egalitatile

A (B C) = (A B) (A C),

A (B C) = (A B) (A C).

Prin diferenta multimilor B si A intelegem multimea

B A = .

Daca A este o submultime a lui B, atunci diferenta B A se numeste complementa-ra multimii A in B si se noteaza cu C_BA. De exemplu C_B = B, iar C_BB =

Daca A si A' sunt doua submultimi ale multimii B au loc egalitatile:

C_B (A A') = (C_BA) (C_B A')

C_B (A A') = (C_BA) (C_BA')

numite formulele lui de Morgan.

Fie A si B doua multimi arbitrare. Daca a I A si b I B, atunci putem forma perechea ordonata (cuplul) (a, b), adica perechea formata din elementele a si b unde este stabilita o anumita ordine in sensul ca a este primul element iar b este al doilea element in aceasta pereche. Rezulta ca doua perechi (a₁, b₁) si (a₂ , b₂) sunt egale daca si numai daca a₁ = a₂ si b₁ = b₂. Prin produsul cartezian al multimilor A si B intelegem multimea

A x B=.

Cand A = B, atunci notam A² = A x A.

Se observa ca daca una dintre multimile A sau B este multimea vida, atunci A x B = . In plus, daca A are m elemente iar B are n elemente, atunci multimea A x B are m n elemente.

FUNCTII

Fiind date multimile A si B, prin functie (sau aplicatie) definita pe multimea A cu valori in multimea B se intelege o lege f, in baza careia oricarui element a I A i se asociaza un unic element, notat f(a), din B.

Multimea A se numeste domeniul de definitie al functiei f, iar multimea B se numeste domeniul valorilor functiei f (sau codomeniul functiei f).

O functie f este perfect determinata cand se da domeniul de definitie, codomeniul sau si modul cum actioneaza f. O functie f definita pe multimea A cu valori in B se noteaza f: A B.

Daca f: A B este o functie si A' A este o submultime a multimii A, notam

f(A') =

numita imaginea directa a lui A' prin functia f. In cazul particular cand A' = A, notam f(A) = Im f si se numeste imaginea functiei.

Similar, daca B' B este o submultime a lui B, atunci notam

f ^-1(B) = .

Aceasta submultime se numeste imaginea inversa a lui B' prin functia f si este o submultime a lui A.

O functie f: A B se numeste injectiva daca oricare ar fi a, a' I A cu a a' rezulta f(a) f(a') sau echivalent, din egalitatea f(a) = f(a') rezulta a = a'.

Functia f: A B se numeste surjectiva daca oricare ar fi b I B exista a I A astfel incat f(a) = b sau echivalent, Im f = B.

O functie care este injectiva si surjectiva se numeste bijectiva.

Daca A si B sunt doua multimi oarecare, vom nota cu B^A = , adica multimea tuturor functiilor definite pe A cu valori in B.

Daca A este o multime oarecare, functia 1_A: A A, unde 1_A(a) = a oricare ar fi aIA se numeste functia identica a multimii A.

Daca A B este o submultime a lui B, atunci functia i: A B unde i(a) = a oricare ar fi aIA se numeste functia incluziune a submultimii A a lui B.

O functie f: A B se numeste restrictia functiei g: A' B' daca A A', B B' si f(a) = g(a), oricare ar fi aIA. In aceasta situatie g se numeste o extindere a lui f.

Fiind date functiile f: A B si g: B C, functia notata cu g of, unde g o f: A C si (g of)(a) = g(f(a)) oricare ar fi aIA se numeste compunerea functiilor f si g.

Daca f: A B este o functie, atunci sunt evidente egalitatile:

1_B o f = f si f o 1_A = f.

O proprietate importanta a compunerii functiilor este urmatoarea:

Teorema 2.1. Compunerea functiilor este asociativa, adica fiind date functiile

f: A B, g: B C si h: C D are loc egalitatea

h o (g o f) = (h o g) o f.

Demonstratie. Intr-adevar, se vede mai intai ca functiile h o (g o f) si (h o g) o f au

domeniul de definitie A, iar codomeniul D. Fie acum a I A; avem

(h o (g o f))(a) = h((g of)(a)) = h(g(f(a)))

si

((h o g) o f)(a) =(h o g)(f(a)) = h(g(f(a))

de unde rezulta ca

h o (g o f) = (h o g) o f.

O functie f: A B se numeste inversabila daca exista o functie g: B A astfel incat g o f = l_A si f o g = 1_B. Urmatoarea teorema caracterizeaza functiile inversabile:

Teorema 2.2. Daca f: A B este o functie, atunci f este inversabila daca si numai

daca f este bijectiva.

Demonstratie. Presupunem ca f este inversabila. Atunci exista functia g : B A

astfel incat g o f = 1_A si f o g = 1_B. Fie a, a'IA astfel incat f(a) = f(a'). Atunci avem ca g(f(a)) = g(f(a')) adica (g o f)(a) = (g o f)(a'), de unde obtinem ca 1_A(a) = l_A(a') si deci a = a'. Deci f este o functie injectiva.

Fie acum bI B; punem a = g(b) I A. Deci f(a) = f(g(b)) = (f o g)(b) = 1_B(b) = b,

ceea ce ne arata ca f este si surjectiva si deci f este bijectiva.

Invers, presupunem ca f este bijectiva. Fie b I B un element oarecare. Cum f este surjectiva exista elementul a_bIA astfel incat f(a_b) = b. Cum f este injectiva, elementul a_b este unic determinat de b. Atunci definim functia g: B A astfel: g(b) = a_b. Se verifica imediat ca g o f = 1_A si f o g = l_B.

Sa presupunem din nou ca functia f : A B este inversabila. In acest caz functia

g: B A cu proprietatile g o f = 1_A si f o g = 1_B, este unic determinata. Intr-adevar, sa presupunem ca mai exista o functie g': B A astfel incat g' o f = 1_A si f o g' = 1_B. In acest caz avem (g' o f) o g = 1_A o g = g. Cum (g' o f) o g = g' o (f o g) = g' o 1_B = g' rezulta g = g'. Functia g fiind unica se noteaza cu f ^-1 si se numeste inversa functiei f.

Teorema 2.3. i) Daca functia f: A B este inversabila, atunci inversa sa

f ^-1: B A este inversabila si are loc egalitatea (f ^-1) ^-1 = f.

ii) Daca functiile f: A B si g: B C sunt inversabile, atunci si functia

g o f: A C este inversabila si are loc egalitatea

(g o f) ^-1 = f ^-1 o g ^-1 .

Demonstratie. i) Cum avem egalitatile f o f ^-1 = 1_B si f o f ^-1 = l _A rezulta ca si f ^-1

este inversabila si inversa sa este f, adica (f ^-1) ^-1= f .

ii) Calculam

(g o f) o (f ^-1 o g ^-1) = g o ((f o f ^-1) o g ^-1) = g o (l _A o g ^-1) = gog ^-1 = l _C

si

(f ^-1o g ^-1 o (g o f) = f ^-1 o (g ^-1 o (g o f)) = f ^-1 o ((g ^-1 o g) o f) = f ^-1 o (1_B o f) = f ^-1 o f = 1_A

Aceste egalitati ne arata ca g o f este inversabila si inversa sa este f ^-1o g^-1,

adica (g o f) ^-1 = f ^-1 o g ^-1.

Un rezultat important, foarte util in cele ce urmeaza este urmatorul:

Teorema 2.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 T 2) si 1) T 3) sunt evidente.

T 1) Deoarece A este o multime finita, atunci putem scrie ca A = . Cum f este injectiva, atunci f(A) = , unde f(a_i) f(a_j), oricare ar fi i j. Deci f(A) are n elemente. Cum f(A ) A rezulta neaparat ca A = f(A) si deci f este si surjectiva, adica bijectiva.

T 1) Fie b I A si notam cu f ^-1(b) = . Evident ca f ^-1(b) este

o submultime a lui A. Cum f este surjectiva, atunci f ^-1(B) oricare ar fi bIA. Deoarece A = _bIA f ^-1(b) si multimile f ^-1(b) sunt disjuncte doua cate doua, rezulta ca f ^-1(b) are un singur element, deoarece in caz contrar ar rezulta ca _bIA f ^-1(b) ar avea un numar mai mare de elemente decat multimea A. Aceasta ne arata ca f este neaparat o functie injectiva.

Observatie. Daca A nu este finita, teorema 2.4 nu mai este adevarata. De exemplu, sa

luam A = N iar f: N N sa fie functia f(n) = n + l. Se vede ca f este injectiva, dar nu este surjectiva deoarece 0 Im f.

3. PRODUS CARTEZIAN AL UNEI FAMILII DE MULTIMI

Fie I si A o multime oarecare; o functie φ: I A se mai numeste si multime indexata de elemente din A dupa multimea de indici I (sau familie de elemente din A indexata dupa I ). Se noteaza

φ = (a_i)_iII = (a_i)_i, unde a_i = φ(i).

Daca I = , atunci folosim notatia (a_i)_iII = (a₁, a₂, . , a_n) si (a₁, a₂, , a_n) se mai numeste n-uplu.

Daca elementele lui A sunt multimi (sau submultimi ale unei multimi T) obtinem

notiunea de familie de multimi (resp. familie de submultimi a lui T).

Fie (A_i)_iII o familie de multimi. Atunci multimile

A_i , resp. A_i =

iII iII

se numesc reuniunea, resp. intersectia familiei (A_i)_iII

Fie (A_i)_iII o familie de multimi. Multimea

A_i =

iII    iII

se numeste produs cartezian sau produs direct al familiei (A_i)_iII

Astfel, putem scrie:

A_i = .

iII

Daca A_i = A oricare ar fi i I I, atunci produsul cartezian nu este altcineva decat multimea A^I = . Daca I = , atunci notam _iII A_i cu A₁ x A₂ x x A_n. Deci A₁ x A₂ x x A_n = . In cazul n = 2 obtinem produsul cartezian a doua multimi introdus in 1. Daca A₁ = A₂ = . = A_n = A vom nota Aⁿ = A₁ x A₂ x x A_n. Fie i I I; functia p_i : _jII A_j A_j, definita prin egalitatea p_i(φ) = φ(i) I A_i, unde φ I _jII A_j (sau p_i((x_j)_jII) = x_i) se numeste i-proiectia canonica a produsului cartezian pe multimea A_i.

In teoria multimilor se admite urmatoarea axioma:

Axioma alegerii. Daca (A_i)_iII este o familie nevida de multimi nevide, atunci

A_i

iII

Echivalenta cu axioma alegerii este urmatoarea afirmatie: daca S este o colectie nevida de multimi nevide disjuncte doua cate doua, atunci exista o multime A, numita multime selectiva, astfel incat A X este formata dintr-un singur element oricare ar fi XI S.