4.4 CLASSES DE EQUIVALÊNCIA

Se R é uma relação de equivalência em A e a  A , chamamos classe de equivalência de a por intermédio de R ao conjunto de todos os elementos de A que estão relacionados com a . A classe de a denotamos por cl(a) e se lê “classe de equivalência de a”..

Em forma simbólica: cl(a) = { x  A /. x  a mod R }

Exemplo 4.38

Seja A={ 1, 2, 3 } e R uma relação de equivalência em A definida por R={ (1, 1), (1, 2), (2, 2), (2, 1), (3, 3) } , temos que as classes de equivalência de 1 e 3 são respectivamente: cl(1) = { 1, 2 } e cl(3) = { 3 } . Note que a classe de equivalência do 2 é cl(2) ={ 1, 2 } , isto é cl(2)= cl(1)

Exemplo 4.39

Seja R a relação definida pelos inteiros x  b mod 5 ; isto é `` x é congruente com y módulo 5 ''. Determine todas as classes de equivalência.

Solução.

Temos que R é uma relação de equivalência, e como todo inteiro podemos expressar na forma x = 5q + r onde 0  r < 5 existem cinco classes cl(0), cl(1), cl(2), cl(3) e cl(4) ; estas classes são:

cl(0) = { . . . , -10, -5, 0, 5, 10,. . . }

cl(1) = { . . . , -9, -4, 1, 6, 11, . . . }

cl(2) = { . . . , -8, -3, 2, 7, 12, . . . }

cl(3) = { . . . ,-7, -2, 3, 8, 13, . . . }

cl(4) = { . . . , -6, -1, 4, 9, 14, . . . }

4.4.1 Conjunto quociente.

É uma família de elementos formada por todas as classes distintas de uma relação de equivalência. Se a relação de equivalência é R está definida no conjunto A , denotamos A/ R e se lê “conjunto quociente de A pela relação R”.

Exemplo 4.40

Para o Exemplo (4.38) temos que A/R = { cl(1), cl(3) }

Exemplo 4.41

Determine o conjunto quociente para as classes do Exemplo (4.39).

Solução.

O conjunto quociente é: Z/R = { cl(0), cl(1), cl(2), cl(3), cl(4) }

4.4.2 Partição de um conjunto.

Consideremos o conjunto A = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } e os subconjuntos B1 = { 7, 8, 10 }, B2 = { 2, 5, 6 }, B3 = { 4, 9 }, B4 = { 3, 1 } observe que a família de conjuntos B = { B1, B2, B3, B4 } tem as seguintes propriedades:

1. O conjunto A é a união de todos os elementos de B ; isto é A = B1  B2  B3  B4

2. Para qualquer dos conjuntos Bi e Bj tem-se que Bi  Bj = Bi ou Bi  Bj = 

Definição 4.16 Partição de um conjunto.

Dada uma família não vazia {Bi}i  I de subconjuntos de A ; dizemos que {Bi}i  I é uma partição de A se satisfaz:

1. Bi = A

2. Bi  Bj = Bi ou Bi  Bj =  para todo i, j  I .

Cada um dos Bi é chamado de uma partição de A .

Exemplo 4.42

• Sejam A= { números naturais pares } e B = {números naturais ímpares }. Então { A, B } é uma partição para N

• Sejam P = { 1, 2, 3, 4, 5, 6, 7, 8, 9 , 10 }, A = { 2 , 6, 10 }, B = { 3, 5 , 6 , 8 }, C = { 1, 3 , 5 , 7 , 9 } . Observe que { A, B, C } não é uma partição de P ; aqui A  B   , e A  B .

Propriedade 4.3

Toda relação de equivalência R em A , determina uma partição em A . Esta partição é precisamente o conjunto quociente A/ R .

Demonstração.

Seja R uma relação de equivalência em A, e para cada   A consideremos o conjunto B = { x /. (x, )  R } , então a família B é uma partição de A .

A mostrar que na verdade, B é uma partição de A .

Como R é reflexiva, isto é cada elemento está relacionado consigo mesmo, então a  Ba para todo a  A . Logo A = B.

Suponhamos que Br  Bs  , e consideremos a  Br  Bs, então (a, r)  R e (a, s)  R. Seja x  Br então (x, r)  R mas pela simetria (r, a)  R, assim (x, r)  R  (r, a)  R  (x, a)  R isto pela transitividade; do mesmo modo (x, a)  R  (a, s)  R  (x, s)  R . Logo x  Bs ; sendo x elemento quaisquer de Br então Br  Bs de modo análogo mostra-se que Bs  Br de onde Br = Bs.

Conseqüentemente {B}  A é uma partição de A , esta partição podemos denotar com A/R .

Exemplo 4.43

Seja A = { 0, 1, 2, 3, 4, 5 } e a relação R = { (a, b)  A2 /. a  b mod 4 } . Determine uma partição em A mediante R.

Solução.

Temos que R = { (0, 0), (0, 4), (4, 4), (4, 0), (1, 1), (1, 5), (5, 5), (5, 1), (2, 2), (3, 3) } de onde podemos obter as seguintes classes de equivalências diferentes:

cl(0) = { 0, 4 }, cl(1) = { 1, 5 },

cl(2) = { 2 }, cl(3) = { 3 } .

O conjunto quociente é A/ R = { { 0, 4 }, { 1, 5 }, { 2 }, { 3 } } , que é precisamente a partição de A mediante a relação R .

Logo uma partição de A determinada por R é; { cl(0), cl(1) , cl(2), cl(3) }

Propriedade 4.4

Toda partição de A determina uma relação de equivalência em A .

Demonstração.

Seja  um conjunto de índices e suponhamos que A = A, onde A são mutuamente disjuntos e não vazios. Dado um elemento a  A, então ele está exatamente em algum A , onde   .

Figura 4.6:

Definimos para a, b  A a relação a  b se os elementos estão no mesmo A. É suficiente mostrar que a relação  é de equivalência. (Exercício para o leitor)

Exemplo 4.44

Seja A = { a, b, c, d, e } e uma partição de A o conjunto { {a, b}, {c, e}, {d} } e seu diagrama mostra-se na Figura (4.6)

A relação de equivalência em A determinado por R é { (a, a), (a, b), (b, a), (b, b), (c, c),(c, e), (e, c), (e, e), (d, d) } que obtemos relacionando os elementos em sua respectiva parte, naturalmente:

A/ R = { {a, b}, {c, e}, {d} } .