Multimi, relatii binare si functii

Multimi, relatii binare si functii

Multimi

Prin multime se īntelege o colectie de obiecte care vor fi numite elemente. Notiunea de multime, ca orice notiune primara, nu se defineste ca alte notiuni prin genul proxim si diferenta specifica ci se caracterizeaza numind individual elementele sau specificānd o proprietate pe care o au elementele sale si nu o au alte obiecte.

Vom nota multimile cu majuscule A, B, C, ., X, Y iar elementele multimilor cu litere mici a, b, c, ., x, y.

Pentru unele multimi care vor fi des utilizate se folosesc notatii consacrate. Se noteaza cu N multimea numerelor naturale, cu Z multimea numerelor īntregi, cu Q multimea numerelor rationale, cu R multimea numerelor reale iar cu C multimea numerelor complexe.

Legatura dintre un element si multimea din care face parte este data de relatia " " numita relatia de apartenenta. Daca A este o multime si x un element al sau vom scrie x A si vom citi "x apartine lui A".

Daca A si B sunt doua multmi, vom spune ca A este o submultime a lui B si vom scrie A B (A este inclusa īn B) daca orice element al multimii A este si element al multimii B.

Simbolic scriem A B " x, x A x B

Īn teoria multimilor admitem existenta multimii care nu are nici un element, notata cu si numita multimea vida. Multimea vida este o submultime a oricarei multimi.

Doua multimi sunt egale, A = B, daca si numai daca A B si  B A

Relatia de incluziune " " ne permite sa definim clasa partilor unei multimi X, notata cu P(X) si care are ca obiecte toate submultimile multimii X.

Definim īn clasa partilor P(X), ale unei multimi X, operatiile:

reuniunea a doua multimi A si B reprezinta multimea

A B

intersectia a doua multimi A si B reprezinta multimea

A B

Doua multimi se numesc disjuncte daca A B =

diferenta multimilor B si A īnseamna multimea

B \ A

Daca A B atunci B \ A se numeste complementara lui A īn raport cu B si se noteaza cu C_BA. Īn clasa partilor P(X) ale multimii X, notam cu , complementara lui A īn raport cu X, si o vom numi simplu complementara lui A. Este simplu de dovedit ca daca A, B P(X) atunci .

produsul cartezian al multimilor A si B īnseamna multimea

A B =

Un element (a, b) A B se numeste pereche ordonata. Doua perechi ordonate (a₁, a₂) si (b₁, b₂) sunt egale daca si numai daca a₁ = b₁ si a₂ = b₂.

Īn mod analog se pot defini operatiile de reuniune, intersectie si produs scalar pentru trei sau mai multe multimi.

Prin produsul cartezian al multimilor X₁, X₂, ., X_n, īntelegem multimea sistemelor ordonate (x₁, x₂, ., x_n) cu x_i X_i, , adica

Un element al acestui produs cartezian īl vom numi n - upla. Doua n - uple (x₁, x₂, ., x_n) si (y₁, y₂, ., y_n) sunt egale daca si numai daca x₁ = y₁, x₂ = y₂, ., x_n = y_n.

Daca atunci vom folosi notatia .

Numim partitie pe multimea X o familie de parti ale lui X, disjuncte doua cāte doua si a caror reuniune este egala cu X.

Relatii

Fie A si B doua multimi nevide.O corespondenta īntre elementele celor doua multimi se numeste relatie binara. Daca a A si b B si notam cu R relatia īntre A si B, atunci vom citi "a este īn relatia R cu b" si vom nota cu a R b. Multimea A se numeste multime de plecare iar B multimea de sosire. Cele doua multimi nu au un rol simetric, motiv pentru care vom gāndi elementele ce sunt īn relatia R ca pe niste perechi ordonate. Astfel, o relatie binara o putem defini ca o submultime G a produsului cartezian A B. O relatie R īntre elementele multimilor A si B va fi data prin tripletul R = (G; A, B), unde G A B va fi numit graful relatiei R iar A si B sunt multimea de plecare respectiv multimea de sosire.

Daca B = A,relatia binara R se numeste simplu relatie binara pe multimea A.O relatie binara peA se noteaza de regula cu R r, etc.

Data o relatie de echivalenta "~" pe A, atunci pentru orice a A definim multimea

numita clasa de echivalenta īn raport cu relatia "~" a elementului a. Un element al unei clase de echivalente va fi numit reprezentant al acestei clase.

Multimea claselor de echivalenta determinate de relatia "~" pe A se noteaza cu A si se numeste multimea factor sau multimea cāt a lui A īn raport cu relatia "~".

Īn baza teoremei 1.2 rezulta ca o relatie de echivalenta determina o partitie pe A si reciproc. O partitie pe multimea A este definita de clasele de echivalenta. Reciproc, o partitie a multimii A determina o relatie de echivalenta pe A; doua elemente din A se gasesc īn relatie daca ele apartin la aceeasi submultime a partitiei.

Exemple

Relatia de paralelism īn multimea dreptelor din spatiu este o relatie de echivalenta. Doua drepte d₁ si d₂ din spatiu spunem ca sunt paralele daca exista un plan ce le contine si care satisfac una din proprietatile: d₁ d₂ = sau d₁ = d₂. Putem constata usor ca relatia de paralelism astfel definita este o relatie de echivalenta .

Clasa de echivalenta a unei drepte d este formata din multimea tututror dreptelor paralele cu d. Aceasta clasa de echivalenta se numeste directia determinata de dreapta d īn spatiul considerat.

2° Numere cardinale. Doua multimi A si B se zic cardinal echivalente sau echivalente daca exista o bijectie de la A la B. Aceasta relatie este o relatie de echivalenta īn clasa tuturor multimilor. Clasele de echivalenta se numesc numere cardinale. Vom nota cardinalul multimii A cu card A. Daca N este multimea numerelor naturale vom nota cardinalul acesteia cu (alef zero). Orice multime cardinal echivalenta cu N se numeste numarabila.

Daca A si B sunt doua multimi, card A = m si card B = n, atunci card .

O multime A pe care s-a definit o relatie de ordine " " se numeste multime ordonata si o vom nota prin (A,

Daca pentru orice a, b A avem a b sau b a, atunci multimea (A, ) se numeste total ordonata sau lant.

Īntr-o multime ordonata (A, ) un element a A se numeste prim element (respectiv ultim element) al lui A daca a x (respectiv x a) oricare ar fi x A.

Elementul a A se zice maximal (respectiv minimal) daca din a x (respectiv x a) rezulta x = a.

Daca B A, un element a A se zice majorant (respectiv minorant) al lui B daca x a (respectiv a x) oricare ar fi x B.

Un element a A se numeste supremum (respectiv infimum) pentru multimea B, daca pentru " x B si daca , " x B atunci a a (daca pentru " x B si daca , " x B atunci a a). Elementul a A (daca exista) se noteaza cu sup (B) (respectiv inf (B)).

O multime total ordonata (A, ) se zice inductiva daca orice submultime a sa are un majorant.

Īn teoria multimilor se demonstreaza ca urmatoarele afirmatii sunt echivalente:

1° Axioma alegerii. Daca A₁, A₂, ..., A_n este o familie de multimi nevide atunci A₁ A₂ A_n

2° Lema lui Zorn. O multime inductiva nevida are cel putin un majorant.

O multime ordonata (A, ) se zice bine ordonata, daca orice submultime nevida a sa are un prim element.

3° Teorema lui Zermelo. Daca A este o multime nevida, atunci exista o relatie de ordine " " astfel īncāt (A, ) este o multime bine ordonata.

Functii

O relatie binara particulara o reprezinta notiunea de functie.

Fie doua multimi oarecare E si F.

Proprietatea relatiei binare f, ce defineste o functie pe E cu valori īn F, se numeste univocitate, adica .

Prin functie se īntelege deci, ansamblul format din multimea de plecare E numita domeniu de definitie, multimea de sosire F numita multimea īn care functia ia valori si legea de corespondenta f. Elementul y F care corespunde prin f elementului x E se noteaza prin

y = f(x) sau

Elementul x E va fi numit variabila independenta sau argument iar y = f(x) F se numeste imaginea lui x prin f.

Vom folosi notatia , y = f(x).

Notam cu F : (E; F) multimea tuturor functiilor definite pe E cu valori īn F. Daca E = F, vom nota multimea functiilor de la E la F prin F (E)

Doua functii f₁, f₂ F (E, F) sunt egale, f₁ = f₂, daca si numai daca f₁(x) = f₂(x), " x E

Graful corespondentei univoce f se va numi greficul functiei si va fi notat cu .

Doua functii f₁ si f₂ sunt egale daca submultimile produsului cartezian E F, si sunt egale.

O functie se numeste injectiva daca

Functia se numeste surjectiva daca

Multimea f(E) se numeste imaginea functiei f si se noteaza cu

Im f =

Functia este surjectiva daca si numai daca . Oricarei aplicatii i se poate asocia aplicatia surjectiva avānd acelasi grafic.

Functia se numeste bijectiva daca f este injectiva si surjectiva.

Doua multimi sunt īn corespondenta biunivoca daca exista o aplicatie bijectiva .

Sa consideram functiile si . Functia definita prin relatia se numeste compunerea functiilor f si g.

Functia 1_E F (E) definita prin relatia se numeste functia identica a multimii E. Graficul acestei functii reprezinta diagonala produsului cartezian E E

O functie se numeste inversabila daca exista o functie , numita inversa functiei f, care satisface conditiile si .

O functie este inversabila daca si numai daca f este bijectiva.

Daca , atunci x = f^-1(y) E este numit imaginea inversa sau contraimaginea lui y.

O functie punctuala nu admite īntotdeauna inversa, dar gāndita ca o aplicatie de multime are sens sa vorbim de imaginea inversa (reciproca) a unei submultimi īn raport cu f, adica

O functie este injectiva daca si numai daca , multimea contine cel mult un element.