Multimi, relatii, functii

Multimi, relatii, functii

In cele ce urmeaza, nu vom insista asupra teoriei axiomatice a multimilor, ea nefiind scopul acestei lucrari.

Prin multime, vom intelege, simplu, o colectie de obiecte de un acelasi tip, obiectele fiind numite elementele multimii. Se presupune ca, in momentul abordarii acestui text, cititorul are cunostintele necesare parcurgerii acestui paragraf, scopul sau fiind, in principal, sa fixeze o serie de notatii si sa reaminteasca o serie de rezultate care nu pot fi gasite cu usurinta in alta parte.

Multimile vor fi notate, in general, cu litere mari din alfabetul latin, A, B, C, . , iar elementele lor cu a, b, c, . . Cardinalul lui A (numarul de elemente ale lui A), il notam |A|.

Fie doua multimi, A si B.

Spunem ca A este submultime a lui B si scriem AB (sau BA) daca orice element a lui A este si element a lui B.

Spunem ca A si B sunt egale si scriem A = B daca AB si BA.

Daca A si B nu sunt egale, scriem A ≠ B.

Spunem ca A este o submultime proprie a lui B daca AB, cu A ≠ B.

Multimea care nu contine nici un element se numeste multimea vida si este notata cu Ø.

Multimea vida poate fi caracterizata astfel : Ø = .

Vom numi intersectia multimilor A si B, multimea de elemente care apartine atat lui A, cat si lui B si o notam cu AB.

Daca AB = Ø, se spune ca A si B sunt disjuncte.

Se numeste reuniuna lui A si B multimea notata cu AB, ale carei elemente apartin cel putin uneia dintre multimile A si B.

Se numeste diferenta multimilor A si B si se noteaza cu A - B multimea

Atunci cand toate multimile considerate sunt submultimi ale unei aceleiasi multimi X, vom nota diferenta X - A cu C(A) si o vom numi o complementara a lui A.

Produsul cartezian al multimilor A si B, notat cu A B este multimea perechilor ordonate (a, b), unde aA si bB, A B = .

Daca AB, a ≠ b, atunci perechile (a, b) si (b, a) sunt elemente distincte ale lui A B

Acest lucru se exprima spunand ca A B este multimea perechilor ordonate.

Definitia produsului cartezian se poate extinde la n multimi A₁, A₂, . , A_n,

A₁ A₂ . A_n = ,

unde =

In cazul in care A₁ = A₂ = . = A_n = A vom nota produsul cartezian cu Aⁿ.

In cazul in care A si B sunt intervale din R, A B se poate vizualiza usor:

O multime distinsa asociata oricarei multimi A este multimea partilor lui A, notata P(A) si se defineste ca fiind multimea tuturor submultimilor lui A. Asadar, P(A) = . Vom nota prin P*(A) multimea P(A) din care s-a extras multimea vida, Ø. Merita sa mentionam aici ca |P(A)| = 2^|A|

Definitie 1.1. Date doua multimi A si B, se numeste relatie de la A la B, orice submultime a produsului cartezian A B.

Daca R este o relatie de la A la B, vom nota (x, y)R si in felul urmator xRy.

Daca o relatie are proprietatea (a, b), (a, c) R, atunci b = c.

Se numeste domeniu lui R urmatoarea submultime a lui A :

D(R) = .

Se numeste codomeniu lui R urmatoarea submultime a lui B :

C(R) = .

Definitie 1.2. Se numeste functie multivoca de la multimea A la multimea B, o relatie a carei domeniu coincide cu A.

Pentru orice multime A vom numi relatie pe A o relatie de la A la A.

O relatie particulara pe A este relatia identitate a lui A (sau diagonala):

I_A = .

Se observa ca I_A este o functie multivoca.

Definitie 1.3. Fie RA A.

• R se numeste reflexiva daca xA, (x, x)R;
• R se numeste simetrica daca pentru orice (x, y)R, avem si (y, x)R;
• R se numeste tranzitiva daca pentru orice (x, y)R si (y, z)R, avem ca (x, z)R;
• R se numeste antisimetrica daca pentru orice (x, y)R si (y, x)R, avem x = y.

O relatie R pe A, care este reflexiva, simetrica si tranzitiva se numeste relatie de echivalenta pe A.

O relatie R pe A, care este reflexiva si tranzitiva se numeste relatie de preordine pe A.

O relatie R pe A, care este reflexiva, antisimetrica si tranzitiva se numeste relatie de ordine partiala pe A.

Cuplul (A, R) = multime partial ordonata.

Daca RA B, notam cu R^-1 relatia de la B la A,numita inversa relatiei R, definita astfel:

R^-1 = .

Daca RA × B si S B × C, notam cu S ◦ R relatia de la A la C definita astfel :

S◦R = ,

pe care o numim compunerea (produsul) relatiilor R si S.

Observatii 1.4.

• R este reflexiva daca RI_A
• R este simetrica daca RR^-1 (chiar R = R^-1);
• R este tranzitiva daca R◦RR;
• R este antisimetrica daca RR^-1I_A

Definitie 1.5. Fie o relatie de echivalenta. Se numeste clasa de echivalenta a elementului multimea . Clasa de echivalenta a lui a se noteaza sau sau a.

Exemple 1.6.

este congruenta modulo n, . Clasa de echivalenta a lui cuprinde toate numerele intregi care dau acelasi rest ca si a la impartirea prin n.

Fie relatia din exemplul 1.1, 1⁰. Sa observam ca doua numere reale sunt echivalente daca si numai daca au aceeasi parte fractionara. (se stie ca orice , y numindu-se partea fractionara a lui x). Asadar, intr-o clasa de echivalenta se regasesc toate numerele reale avand aceeasi parte fractionara.

Definitie 1.7. Fie A o multime si P = _iI o familie de submultimi ale lui A. P se numeste partitie a lui A daca satisface conditiile :

• iI, A_i ≠ Ø;
• i,jI, i ≠ j AiAj = Ø;
• _i = A.

Observatii 1.8.

1⁰ Orice relatie de echivalenta pe A determina o partitie a lui A, submultimile

partitiei fiind clasele de echivalenta.

2⁰ Daca este o partitie a lui A, putem defini relatia asociata partitiei:

Dupa cum se constata usor, este o relatie de echivalenta pe A.

In plus, daca , clasa sa de echivalenta,

Daca , este o echivalenta, multimea claselor de echivalenta ale lui A

relativ la se numeste multimea cat (sau factor) a lui A relativ la si se

noteaza . Aplicatia se numeste aplicatia

canonica sau proiectia canonica.

Fie o relatie oarecare.

In cele ce urmeaza vom incerca sa determinam cea mai mica (in sensul incluziunii de multimi) relatie de echivalenta pe A care contine , adica relatia de echivalenta generata de. Daca o vom nota, pentru moment, prin , este clar ca . Aceasta definitie nu este foarte utila din punct de vedere practic, ea este insa folositoare atunci cand este vorba de minimalitatea ei. Putem insa sa o construim efectiv:

Definitie 1.9. Relatia se numeste inchiderea tranzitiva a relatiei

Sa observam ca este o relatie tranzitiva si, in plus, este inclusa in orice relatie tranzitiva ce contine

Fie . Aceasta relatie este, evident, reflexiva si simetrica, si este cea mai mica relatie (in sensul incluziunii) relatie cu aceste proprietati ce include

Din acest moment este clar ca avem:

Propozitie 1.10. Relatia de echivalenta generata de este (inchiderea tranzitiva a lui ). In plus, sau exista sirul de elemente din astfel incat (sau, echivalent, sau

Definitie 1.11. Fie A o multime, o relatie de echivalenta peste A. O submultime B a lui A se numeste α - saturata daca

Propozitie 1.12. In ipotezele precedente, B este α - saturata daca si numai daca

Demonstratie :

este evidenta.

Deoarece rezulta ca . Din ipoteza, , deci , deci avem egalitatea ceruta.

Definitie 1.13. Un sistem de inchidere este o familie de parti CP(M) cu proprietatile :

- D, DC , C

- MC

Definitie 1.14. Un operator de inchidere pe o multime M este o aplicatie

c : P(M)→P(M) cu proprietatile:

- M₁M₂ c(M₁) c(M₂) M₁, M₂P(M);

-M₁c(M₁) M₁P(M);

-c(c(M₁)) = c(M₁) M₁P(M).

Definitie 1.15. Fie A, B doua multimi. Se numeste functie de la A la B o relatie definita prin urmatoarele conditii:

astfel incat

2⁰ Daca atunci

Sau, o aplicatie sau o functie f de la o multime A la o multime B este o functie multivoca ce satisface conditia : [xfy, yfz]y = z.

In cazul in care se slabesc conditiile din definitie, se pot obtine notiuniunile de functie partiala (care nu este peste tot definita - slabirea conditiei 1⁰) si functie multivaluata sau functie nedeterminista ( dispare conditia 2⁰).

Faptul ca perechea (a,b) apartine functiei f se noteaza . In general, o functie se noteaza prin sau . Oricarei functii i se poate asocia o relatie, graficul functiei

Pentru doua functii , se poate vorbi despre compunerea lor ca relatii:

f : A→B si g : B →C, f ◦ g = .

Dupa cum se poate constata usor, compunerea a doua functii este si ea, la randul ei, o functie.

Avand in vedere ca, in definirea lui f ◦ g, (a, c)f ◦ g daca si numai daca bB astfel incat f(a) = b si g(b) = c, putem scrie ca g(f(a)) = c, ceea ce justifica o conventie de notatie: in loc de 'f ◦ g' vom scrie'g ◦ f', adica in loc sa scriem (f ◦ g)(a) = c, vom scrie

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

Definitie1.16. Fie functia

1⁰ Se numeste domeniul lui f - multimea A

2⁰ Se numeste codomeniul lui f - multimea B

3⁰ Se numeste imaginea lui A' prin f - multimea

4⁰ Se numeste contraimaginea lui B' prin f - multimea

5⁰ Se numeste restrictia lui f la A' - functia

6⁰ Daca este o functie astfel incat se spune ca f ' s-a prelungit la A sau, inca, ca f este o prelungire a lui f ' la A.

Observatie 1.17. Sa remarcam ca, in definitia anterioara, la punctul 4⁰, nu este vorba de functia inversa. Este vorba de relatia inversa, intrucat relatia inversa a unei functii poate sa nu fie functie.

Definitie 1.18. Fie f : A → B o functie.

f se numeste functie injectiva daca din f(a) = f(b) rezulta ca a = b

(sau a, bA cu a ≠ b f(a) ≠ f(b)).

f se numeste functie surjectiva daca f(A) = B (bB, aA astfel incat

f(a) = b).

f se numeste functie bijectiva daca este injectiva si surjectiva (bB, !aA astfel incat f(a) = b).

Observatii 1.19. Fie o functie.

se mai noteaza si se numeste imaginea functiei f.

Se poate demonstra fara dificultate ca f este bijectiva daca si numai daca

relatia inversa, , este si ea functie.

Daca A este o multime, este chiar functie, si se numeste functia identitate

pe A, notata . Daca f este bijectiva atunci si