Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice
Acasa » referate » matematica
Relatii binare pe o multime

Relatii binare pe o multime




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 DM (numita si diagonala produsului cartezian MM), ca si M = MM fac parte din Rel (M); orice relatie din Rel (M) diferita de DM 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 DM r~ nu este inversul lui r fata de compunerea relatiilor binare

Pentru Rel(M) si nZ definim:

daca  n>0

 

daca  n<0

 

daca  n=0

 

Daca m, n I si r I Rel (M) atunci ( rm)n = rm·n iar rm rn rm+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 DM r

ii) simetrica daca r r

iii) antisimetrica daca r r DM

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 (ri)iII este o familie de relatii de echivalenta de pe M, atunci ri 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 DM r si DM r deducem ca DM 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 r2 = ρ .

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 DM 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 DM 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 rm si (y, z) I rn. 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







Politica de confidentialitate







creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.