Relatii binare pe o multime

Definitia 2.1. Numim relatie binara pe multimea M orice submultime a produsului cartezian M M.

Vom nota prin Rel (M) multimea relatiilor binare ale lui M.

Relatiile D_M (numita si diagonala produsului cartezian MM), ca si _M = MM fac parte din Rel (M); orice relatie din Rel (M) diferita de D_M si _M se zice netriviala.

Pentru r I Rel (M) definim :

r si

r r (r r se zice compunerea relatiilor r si r ). Se verifica imediat ca (Rel(M), ) este monoid in care elementul neutru este D_M r~ nu este inversul lui r fata de compunerea relatiilor binare

Pentru Rel(M) si nZ definim:

Daca m, n I si r I Rel (M) atunci ( r^m)ⁿ = r^m·n iar r^m rⁿ r^m+n. De asemenea, daca r r I Rel (M) si r r , atunci r r )~ si r d r d pentru orice d I Rel (M) iar (r d d p

Definitia 2.2. Fie r I Rel (M). Vom spune despre r ca este:

i) reflexiva daca D_M r

ii) simetrica daca r r

iii) antisimetrica daca r r D_M

iv) tranzitiva daca r r

v) totala daca r r _M

O relatie r IRel (M) care este simultan reflexiva, simetrica si tranzitiva se zice relatie de echivalenta pe M. Vom nota prin Echiv(M) multimea relatiilor de echivalenta de pe M; evident Echiv (M) Rel (M).

Daca r IEchiv (M), atunci r r si r = r iar daca (r_i)_iII este o familie de relatii de echivalenta de pe M, atunci r_i IEchiv (M).

Propozitia 2.3. Fie r, rI Echiv (M). Atunci:

i) r r I Echiv(M) daca si numai daca r r = r r

ii) r r I Echiv (M) daca si numai daca rr, rr r r  Demonstratie:

i) Daca r r IEchiv (M), atunci (r r r r si cum (r r r ◦ r = r r deducem ca r r r r Reciproc, sa presupunem ca r r r r . Cum D_M r si D_M r deducem ca D_M r r , adica r r este reflexiva.

Din r r r r deducem ca (r r r r r r r r adica r r este simetrica.

De asemenea, (r r r r r r r r r r r r adica r r este si tranzitiva, deci r r I Echiv (M).

Sa remarcam ca in acest caz r r₂ = ρ^′ .

ii) Totul rezulta din observatia ca daca r r I Rel (M), atunci

r r ) ² = r r r r r r g

Propozitia 2.4. Fie r I Rel (M) si q D_M r r . Atunci :

i) q este cea mai mica relatie reflexiva si simetrica ce contine pe r

ii) = q este cea mai mica relatie de echivalenta ce contine pe r

(deci este relatia de echivalenta generata de r

Demonstratie:

i) Evident r q iar daca r este o alta relatie reflexiva si simetrica astfel incat r r atunci, cum D_M r si r r r deducem ca q r

ii) Din i) deducem ca q este reflexiva si simetrica. Cum (q) q)= q deducem ca pentru orice nIN q este simetrica. Atunci rezulta imediat ca si este simetrica.

Pentru tranzivitate, fie (x, y), (y, z) I. Exista deci m, n I N astfel incat (x, y) I r^m si (y, z) I rⁿ. Atunci (x, y) I r r r si acum totul este clar. g

Definitia 2.5. Fie rIEchiv (M) si x I M. Multimea x r poarta numele de clasa de echivalenta a lui x relativa la r (sau modulo r), iar M r poarta numele de multimea cat (sau factor) a lui M prin r

Propozitia 2.6. Fie r I Echiv (M). Atunci:

i) x I x r

ii)    (x r M

iii)  x r y r daca si numai daca (x, y) Ir

iv)   Daca x yIM, atunci x r y r sau (x r (y r

Aplicatia p : M M r p x x r pentru orice xIM poarta numele de surjectia canonica a lui M pe multimea factor M r