Relação de Equivalência

Prévia do material em texto

RELAÇÃO DE EQUIVALÊNCIA
Uma relação binária em A é de equivalência se é reflexiva, simétrica e transitiva.
Exemplos
R = { (x , y) : o resto de x/3 é igual ao resto de y/3 }
R = { (6 , 3) : o resto de 6/3 é igual ao resto de 9/3 }
R é reflexiva?
Sim, pois o resto de x/3 é igual ao resto de y/3. Então (x , y) ϵ R, \/ ϵ N.
R é simétrica?
Se (a , b) ϵ R, então o resto de b/3, sim, pois, é igual ao resto de a/3 logo (b , a) ϵ R.
R é transitiva?
Sim, pois, se (a , b) , (b , c) ϵ R, então o resto de a/3 é igual ao resto de b/3, que é igual ao resto de c/3. Portanto, o resto de a/3 é igual ao de c/3 logo (a , c) ϵ R.
R é uma relação de equivalência.
Classes de Equivalência
Se R é uma relação de equivalência em um conjunto A e a pertence a A, então a classe de equivalência de a módulo R é o conjunto [a]R = {a’ ϵ A : (a , a’) ϵ R}
O conjunto de todas as lasses de equivalência do A módulo R é
A/R = { [a]R : a ϵ A }
Lema: Dada uma relação de equivalência R em A e dados a,a’ ϵ A, temos que:
• ( a , a’) ϵ R se e só se [a]R = [a’]R
• (a , a’) ϵ R se e só se [a]R N [a’]R = Ø
Prova: (a =>)
Se x ϵ [a]R, então (x , a) e (x , a) ϵ R.
Se (a , a’) ϵ R, então (x , a’) e (a’ , x) ϵ R.
Logo, x ϵ [a’]R por definição.
Logo [a]R C [a’]R. Argumento idêntico prova que [a’]R C [a]R.
Portanto [a]R = [a’]R