QReferate - referate pentru educatia ta.
Referatele noastre - sursa ta de inspiratie! Referate oferite gratuit, lucrari si proiecte cu imagini si grafice. Fiecare referat, proiect sau comentariu il poti downloada rapid si il poti folosi pentru temele tale de acasa.



AdministratieAlimentatieArta culturaAsistenta socialaAstronomie
BiologieChimieComunicareConstructiiCosmetica
DesenDiverseDreptEconomieEngleza
FilozofieFizicaFrancezaGeografieGermana
InformaticaIstorieLatinaManagementMarketing
MatematicaMecanicaMedicinaPedagogiePsihologie
RomanaStiinte politiceTransporturiTurism
Esti aici: Qreferat » Referate matematica

Relatii de echivalenta








RELATII DE ECHIVALENTA


Fie A si B doua multimi; o submultime ρ A x B se numeste relatie binara intre A si B. Daca elementul (a, b) I ρ, unde a I A si b I B spunem ca a este in relatia ρ cu b si notam a ρ b. Cand scriem a ρ b inseamna ca elementele a I A si b I B nu sunt in relatia ρ. De exemplu daca f: A B este o functie, atunci multimea G(f) = este relatie binara intre A si B. Multimea G(f) se numeste graficul functiei f.




Invers, daca G A x B este o relatie intre A si B cu proprietatea ca oricare ar fi

a I A exista un unic b I B astfel incat (a, b) I G, atunci putem defini functia f : A B asa incat f(a) = b. Se observa imediat ca G(f) = G.

Cand B = A, o relatie binara ρ intre A si A se numeste simplu relatie binara pe multimea A. O relatie binara pe o multime se noteaza de regula cu unul din simbolurile: ρ, ~, A , etc.


Exemple. 1) Fie A o multime oarecare; multimea DA = se numeste

diagonala multimii A si este o relatie binara pe A.

2) Daca A este o multime de numere naturale, atunci multimea

< =

este o relatie binara pe A. In particular, daca A =, atunci < = .


Definitia 4.1. O relatie binara pe A, notata ,,ρ', se numeste relatie de echivalenta

daca urmatoarele conditii sunt verificate pentru orice a, b, c I A:

i) a ρ a (reflexivitatea);

ii) a ρ b T b ρ a (simetria);

iii) a ρ b si b ρ c T a ρ c (tranzitivitatea).


De exemplu, daca consideram Z si n > 0 un numar natural, atunci relatia binara

notata s' (mod n) (congruenta modulo n):

a s b (mod n) n | a - b

este o relatie de echivalenta pe Z.

Sau daca consideram pe multimea R a numerelor reale relatia ,,~':

a ~ b a b I Z ;

~ este o relatie de echivalenta pe R.

Data o relatie de echivalenta ,,ρ' pe A atunci pentru orice a I A definim multimea:

a =

care se numeste clasa de echivalenta a elementului a.

Clasa de echivalenta a elementului a se mai noteaza, de la caz la caz, si astfel: a, a, a, , Ca, [a], etc.


Teorema 4.2. Fie A o multime nevida si ρ' o relatie de echivalenta pe A. Atunci clasele de echivalenta determinate de ρ' pe A au proprietatile:

1) a I [a] oricare ar fi a I A. In particular [a]

2) [a] = [b] a ρ b.

3) Daca [a] si [b] sunt doua clase de echivalenta, atunci

[a] = [b] sau [a] [b] =

4) Reuniunea tuturor claselor de echivalenta este egala cu A.

Demonstratie. 1) Deoarece a ρ a rezulta ca [a]

Daca [a] = [b], cum a I A, atunci a I [b] si deci a ρ b. Invers, presupunem ca

a ρ b. Fie x I [a]; deci x ρ a si ,,ρ' este tranzitiva; obtinem ca x ρ b adica x I [b]. Deci [a] [b]. Similar, rezulta incluziunea [b] [a] si deci avem egalitatea [a] = [b].

Presupunem ca [a] [b] . Deci exista un x I [a] [b]. Atunci x ρ a si x ρ

b. Cum ρ' este simetrica avem a ρ x si deci a ρ b. Din afirmatia 2) rezulta ca [a] = [b].

4) Rezulta din 1).


Definitia 4.3. Fie A o multime nevida si ,,ρ' o relatie de echivalenta pe A. O familie de elemente din A, (ai)iII, se numeste un sistem complet si independent de reprezentanti (pe scurt, SCIR) relativ la relatia de echivalenta ρ daca are urmatoarele proprietati:

i)        Oricare ar fi i j, ai ρ aj .

ii)      Oricare ar fi a I A, exista i I I astfel incat a ρ ai.


Se observa ca i) si ii) pot fi formulate concentrat astfel: oricare ar fi a I A exista un unic iI I astfel incat a ai .

Fiind data o relatie de echivalenta ,, ' pe multimea nevida A exista intotdeauna un sistem de reprezentanti asociat relatiei Intr-adevar, fie (Ci)iII multimea tuturor claselor de echivalenta asociate relatiei '. Cum Ci oricare ar fi iII, conform axiomei alegerii, exista o familie de elemente (ai)iII astfel incat ai I Ci, oricare ar fi iII. Evident ca (ai)iII este un sistem de reprezentanti pentru relatia ,, '. Trebuie sa observam ca acest sistem de reprezentanti nu este unic.



Daca (ai)iII este un sistem de reprezentanti relativ la relatia ', din teorema 4.2 rezulta ca A = [ai] iar multimile [ai], iII, sunt disjuncte doua cate doua.

iII


Exemplu. Pe multimea Z a numerelor intregi consideram relatia ,,~': a ~ b

|a| = |b|. Se observa imediat ca ~ este o relatie de echivalenta pe Z. Daca aIZ avem

[a] = , daca a 0 si [a] =, daca a = 0. Un sistem de reprezentanti poate fi considerat sistemul de numere: 0, 1, 2, 3, , adica multimea numerelor naturale N. Un alt sistem de reprezentanti poate fi considerat si sistemul de numere 0, -1, -2, -3 , , adica multimea numerelor intregi negative.


Definitia 4.4. Data relatia de echivalenta ρ' pe A, multimea claselor de echivalenta determinate de ,,ρ' pe A se noteaza cu A/ρ si se numeste multimea factor (sau multimea cat) a lui A prin relatia ,,ρ'. Functia p: A A/ρ, p(a) = [a], este o functie surjectiva si se numeste proiectia (surjectia) canonica a lui A pe multimea factor A/ρ.


Definitia 4.5. Fie f: A B o functie. Definim pe A o relatie ρf astfel:

a ρf a f(a) = f(a

ρf se numeste relatia asociata functiei f.


Se observa ca ρf este o relatie de echivalenta pe A, iar multimea factor A/ρf

se descrie astfel:

A/ρf = .


Teorema 4.3. (Proprietatea de universalitate a multimilor factor) Fie A o multime nevida si ρ' o relatie de echivalenta pe A. Fie f : A B o functie si ρf' relatia de echivalenta pe A asociata functiei f. Daca ρ ρf, atunci exista o unica functie f : A/ρ B cu proprietatea ca f o p = f. Mai mult:

f este injectiva ρ = ρf.

f este surjectiva f este surjectiva.


5. MULTIMI ORDONATE. LATICE


Definitia 5.1. Fie A o multime nevida; o relatie binara pe A se numeste relatie de ordine daca urmatoarele conditii sunt verificate pentru orice a, b, c I A:

i) a a (reflexivitatea)

ii) a b si b a T a = b (antisimetria)

iii) a b si c a T a c (tranzitivitatea).


O multime A pe care s-a definit o relatie de ordine ' se numeste multime ordonata si se noteaza (A, ). Fiind data o relatie de ordine ' pe multimea A, i se asociaza relatia <' definita prin a < b a b si a b, care este o relatie tranzitiva.

Daca pentru orice a, b I A avem a b sau b a, multimea (A, se numeste total ordonata sau lant. Daca A' A este o submultime a multimii ordonate (A, ), atunci A' cu relatia de ordine indusa de pe A' este o multime ordonata.


Exemplu. Daca T este o multime, pe multimea P(T) a partilor lui T, relatia de incluziune ' este o relatie de ordine. Daca T are cel putin doua elemente, atunci (P(T), ) nu este o multime total ordonata.


Fie (A, ) o multime ordonata. Un element a I A se numeste prim element (resp. ultim element) al lui A daca a x (resp. x a) oricare ar fi x IA. Elementul a I A se zice maximal (resp. minimal) daca din a x (resp. x a) rezulta a = x. Fie B A; un element a I A se zice majorant (resp. minorant) al lui B daca x a (resp. a x) oricare ar fi x I B.



Elementul a I A se numeste superiorul (resp. inferiorul) multimii B, daca x a oricare ar fi x I B si daca exista un a' I A cu proprietatea ca x a', atunci a a' (resp. a x xIB si daca a' x x I B, atunci a' a). Elementul a (daca exista) se noteaza cu sup(B) (resp. inf (B)).

O multime (A, ) se zice inductiva daca orice submultime a lui A care este un lant are un majorant. Foarte important este urmatorul rezultat:


Lema lui Zorn. Orice multime ordonata nevida care este inductiva are cel putin un element maximal.


O multime ordonata (A, ) se zice bine ordonata daca orice submultime nevida a sa are un prim element. Evident, orice multime bine ordonata este total ordonata. In plus, se vede usor ca (A, ) este bine ordonata daca si numai daca (A, ) este total ordonata si orice lant descendent de elemente al lui A este stationar. Un exemplu de multime bine ordonata este multimea N cu relatia de ordine obisnuita.


In teoria multimilor se demonstreaza


Teorema lui Zermelo. Daca A este o multime nevida, atunci exista o relatie de ordine ,, ' astfel incat (A, ) este o multime bine ordonata.


De asemenea, se demonstreaza ca Axioma alegerii, Lema lui Zorn si Teorema lui Zermelo sunt afirmatii echivalente.

O multime ordonata (A, ) se numeste latice daca pentru orice doua elemente a, b I A exista superiorul si inferiorul. Vom nota cu a b = sup si a b = inf.

Evident ca o multime total ordonata este o latice.

O latice A se zice completa daca orice submultime nevida a lui A are superior si inferior in A.

O latice (A, ) se numeste modulara daca pentru orice a, b, c I A cu proprietatea b a sa avem egalitatea a (b c) = b (a c).

Daca (A, ) si (B, ) sunt doua latice, o functie f: A B se numeste morfism de latice (sau simplu morfism) daca pentru orice a, b I A

f(a b) = f(a) f(b) si f(a b) = f(a) f(b).

Este clar ca orice morfism de latice este o aplicatie crescatoare. Un morfism de latice care este bijectiv se numeste izomorfism de latice.


6. NUMERE CARDINALE


Doua multimi A si B se zic cardinal echivalente sau echipotente daca exista o bijectie de la A la B. Aceasta relatie este o relatie de echivalenta in clasa tuturor multimilor. Clasele de echivalenta se numesc numere cardinale. Cardinalul multimii A se noteaza cu card A sau | A |. Numerele cardinale se noteaza cu literele m, n, p, .

Daca A este o multime finita avand n elemente, atunci o multime B este cardinal echivalenta cu A daca si numai daca B are n elemente. Deci numarul cardinal | A | este perfect determinat de numarul de elemente al multimii A. Din aceste motive | A | se identifica cu numarul de elemente din A, adica | A | = n. Vom nota | | = 0. Daca A si B sunt doua multimi, atunci vom scrie

| A | | B | daca A este cardinal echivalenta cu o submultime a lui B.

Relatia ,, 'este independenta de alegerea reprezentantilor A si B si se verifica faptul ca este o relatie de ordine totala in clasa tuturor numerelor cardinale.

Se noteaza | N | = (alef zero). Orice multime cardinal echivalenta cu N se numeste numarabila. Daca multimea A este finita (resp. infinita) cardinalul sau | A | se zice finit (resp. infinit).

Daca (mi)iII este o familie de numere cardinale cu mi = | Ai |, atunci se definesc operatiile aritmetice:

S mi (Ai x ) | , P mi = | Ai | , mn = | AB | ,

iII iII iII iII

unde m = | A | si n = | B |. Este bine stiut ca operatiile definite nu depind de alegerea reprezentantilor. Daca I = scriem

S mi = m1 + m2 + + mn si P mi = m1m2 . mn.

iII iII



Exercitiu. Fie m, n, p trei numere cardinale. Atunci au loc relatiile:

1) Daca m este infinit, atunci m + n = sup (m, n);

2) Daca m este infinit si n 0, atunci m n = sup (m, n);

3) Daca n 2, atunci m < nm;

4) (mn)p = mnp si (mn)p = mp np.




loading...



Nu se poate descarca referatul
Acest referat nu se poate descarca

E posibil sa te intereseze alte referate despre:


Copyright © 2020 - Toate drepturile rezervate QReferat.ro Folositi referatele, proiectele sau lucrarile afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul referat pe baza referatelor de pe site.
{ Home } { Contact } { Termeni si conditii }