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 D_A = 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, (a_i)_­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, a_i ρ a_j .

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

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 a_i .

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

Daca (a_i)_iII este un sistem de reprezentanti relativ la relatia ', din teorema 4.2 rezulta ca A = [a_i] iar multimile [a_i], 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 (m_i)_iII este o familie de numere cardinale cu m_i = | A_i |, atunci se definesc operatiile aritmetice:

S m_i (A_i x ) | , P m_i = | A_i | , mⁿ = | A^B | ,

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 m_i = m₁ + m₂ + + m_n    si P m_i = m₁m₂ . m_n.

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 < n^m;

4) (mⁿ)^p = m^np si (mn)^p = m^p n^p.