Relações de equivalência. Digrafos. Classes de equivalência PDF

Preview

Summary

Relações de equivalência. Digrafos. Classes de equivalência, Prof. Teresa Almada...

Description

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

Matemática Discreta Teresa Almada

Aula 7- Relações de equivalência. Digrafos. Classes de equivalência e conjunto quociente.

Na aula passada vimos as relações kernel associadas a funções. Se f : A  B é uma função, a relação kerf é uma relação binária definida no conjunto A, domínio da função f , que relaciona

os objectos que têm a mesma imagem.

Dizemos por isso que a relação kerf é a relação “igualdade de imagem”, isto é, a kerf a’ se, e só se f(a) = f (a’). Estas relações têm propriedades interessantes que permitem, em geral, dividir o conjunto, em que estão definidas, em subconjuntos não vazios, disjuntos dois a dois e cuja união é esse conjunto. Os subconjuntos em que o domínio de uma função é dividido pela relação kernel são as classes de equivalência e o conjunto cujos elementos são esses subconjuntos é o conjunto quociente do domínio da função pela respectiva relação kernel. Comecemos por estudar as propriedades de relações binárias que fazem das relações kernel relações especiais: relações de equivalência.

1. Consideremos no conjunto N dos números naturais a relação binária definida por n m se, e só se, m é múltiplo de n, isto é, n  m se, e só se  p N : m = np

1/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

Cada número natural n está relacionado, por  , com ele mesmo, pois n = 1.n, ou seja,

 n  N, n  n . Dizemos por isso que a relação  é reflexiva.

2 A relação  é o subconjunto de N definido por

 = { (n, pn) : n, p  N}. Como  é reflexiva, o conjunto  N diagonal de N, definido por  N = {(n, n): n  N } é subconjunto de  , ou seja,

N   . 2. A relação  definida em N por n  m se, e só se n é um divisor de m, ou seja, n  m se, e só se,  q N : m = nq e n ≠ 0. A relação  não é reflexiva apesar de todo o natural diferente de zero estar em relação consigo próprio. De facto se n ≠ 0, n  n, já que n = n.1. No entanto, por definição de divisor, 0  0.

A próxima definição generaliza o que vimos nos exemplos anteriores Definição. Seja  é uma relação binária definida num conjunto A. Dizemos que

 é reflexiva quando

 x  N, x x.

3. A relação  definida no conjunto R dos números reais por x  y se, e só, se,  x =  y  é uma relação reflexiva, pois  x  R , x  =  x .

2/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

Recordamos que dado um número real x, designamos por característica de x o número inteiro definido por

 x = max

{ z Z : z ≤ x }, isto é, a característica de

um número real é o maior dos números inteiros que não o excede. Observamos que característica de um número inteiro é o próprio número inteiro. Apresentamos de seguida a característica de alguns números reais:

 2  3  3  = -1 =  1 ;  5  = 0=  0 e    

e = 2 =  2 ,

onde e representa o número de Neper.

4. A relação  definida no conjunto Z dos números inteiros por x  y se, e só se, x e 2y têm a mesma paridade não é reflexiva, pois 1  1.

Para que uma relação binária  , definida num certo conjunto A, não seja reflexiva, basta que exista algum elemento em A que não esteja relacionado, por

 , com ele próprio.

5. Consideremos no conjunto Z dos números inteiros a relação binária  definida por x  y se, e só se, x 2 = y 2 . Esta relação binária é simétrica na medida em que se x se relaciona com y, então y também se relaciona com x. Repare que a relação binária  também poderia ser definida por x  y se, e só se, │x│=│y│, ou ainda como a relação kerf, onde f : Z N é definida por f (z) = z . 2

3/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

Qualquer que seja a definição que adoptemos para esta relação binária, verificamos que a relação  e a sua relação inversa, a relação 

1

, coincidem, ou

seja, são exactamente o mesmo conjunto, isto é x y se, e só se, x 

1

y.

Esta relação além de simétrica, é também reflexiva.

A relação do exemplo 1 é, como vimos reflexiva mas não é simétrica, pois, 1  2 e no entanto 2  1 já que 2 é múltiplo de 1, mas 1 não é múltiplo de 2.

A relação  definida no conjunto dos números reais e apresentada no exemplo 3 como sendo a relação “igualdade da característica” é simultaneamente reflexiva e simétrica. A relação binária  definida no conjunto Z dos números inteiros por x  y se, e só se, x e 2y têm a mesma paridade não é nem reflexiva nem simétrica.

Formalizamos de seguida a definição de relação simétrica. Definição. Seja  é uma relação binária definida num determinado conjunto A. Dizemos que a relação  é simétrica quando y  x, sempre que x y, isto é,

 x, y  A (x y y  x).

Seja  uma qualquer relação binária definida num determinado conjunto A e admitamos que  é simétrica. Seja 

1

a relação inversa de  . Se b

1

a, então,

4/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

por definição de relação inversa resulta que a  b. Como  é simétrica, então b a, o que significa que todos os elementos de 

 Reciprocamente se a  b, então b

1

1

1

são elemento de  , ou seja,

.

a e por simetria de  obtemos b a, isto é

 

1

.

Acabamos de provar a próxima proposição. Proposição. Se  é uma relação binária definida num determinado conjunto A, então

 é simétrica se, e só se,  = 

1

.

6. Consideremos no conjunto N, dos números naturais, a relação binária  definida por n  m se, e só se, n e m têm a mesma paridade, ou seja, a relação  é a relação igualdade de paridade. Recordamos que dois inteiros z e w têm a mesma paridade se são ambos pares ou se em alternativa são ambos ímpares. Se n  m e m  p, então é porque n tem a mesma paridade de m que por sua vez tem a mesma paridade de p e, portanto n tem a mesma paridade de p, isto é, n p. Dizemos por isso que a relação  é transitiva

Definição. Seja  uma relação binária definida num determinado conjunto A. Dizemos que  é transitiva se

 a, b, c  A ( a  b e b  c  a c). A relação binária   Rel ( N ) definida no exemplo 1 por

5/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

n m se, e só se, m é múltiplo de n, é reflexiva e transitiva, mas não é simétrica, enquanto a relação binária  definida em N por n  m se, e só se n é um divisor de m, ou seja, n  m se, e só se,  q  N : m = nq e n ≠ 0

é transitiva, mas não é nem reflexiva nem simétrica, o que acontece também com a relação binária  apresentada no exemplo 4 e  é definida no conjunto Z dos números inteiros por x  y se, e só se, x e 2y têm a mesma paridade. Com efeito, já foi visto que esta relação não é reflexiva, quanto à simetria, temos que 2  3 já que 2 e 2x3 têm a mesma paridade mas 3  2, pois 3 e 2x2 não têm a mesma paridade. Observemos que se a  b, então a e 2b têm a mesma paridade, logo a tem de ser um número par. Vejamos a transitividade. Se a  b e b  c, claro que a e 2c têm a mesma paridade, pois a  b e, portanto, a é par, donde concluímos que a  c.

As relações binárias apresentadas nos exemplos 3, 5 e 6 gozam das três propriedades: reflexividade, simetria e transitividade. Relações binárias que, como estas, tenham as três propriedades dizem-se relações de equivalência. Mais formalmente temos a seguinte definição. Definição. Seja  uma relação binária definida num conjunto A. Dizemos que  é uma relação de equivalência se  for simultaneamente reflexiva, simétrica e transitiva. Designamos por Eq(A) o conjunto de todas

as relações de

equivalências definidas no conjunto A. 7. As relações kernel são relações de equivalência. De facto se f:A  B é uma qualquer função, a relação kerf é reflexiva, pois se a A, f(a) = f (a), já que sendo f uma função cada objecto tem uma única imagem. Por outro lado,

6/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

se akerf b, então f (a) = f (b), logo b kerf a, já que f (b) =f (a). Analogamente, se f (a) = f (b) e f (b) = f (c), então f (a) = f (c) e, portanto, kerf é também transitiva.

8. Consideremos no conjunto [3] as relações binárias  e  definidas por

 = {(1, 1), (2, 2), (3, 3) }

 = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)} são exemplos de relações de equivalência no conjunto [3]. A relação  é a relação identidade e é usualmente representada por  A , enquanto a relação  coincide com o produto cartesiano [3]x[3] e por isso diz-se a relação universal definida neste conjunto. A relação é chamada de universal, porque no universo onde ela está definida dois quaisquer elementos estão relacionados, isto é, todos os elementos do conjunto se relacionam uns com os outros.

Habitualmente a relação universal definida num qualquer conjunto A é representada por  A .

A relação  definida no conjunto [3] por  = { (1, 1), (1, 2), (2, 2), (3, 3) } é uma relação reflexiva, transitiva mas não é simétrica, enquanto a relação

 = {(1, 1), (1, 2), (2, 1), (3, 3)} é reflexiva, simétrica mas não transitiva, pois2  1, 1  2 e no entanto 2  2.

Da definição de relação binária transitiva, resulta que uma relação  não é transitiva quando existirem elementos a, b e c no conjunto onde a relação estiver definida de tal modo que a b, b c e a c.

7/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

As relações binárias definidas num conjunto finito podem ser representadas por diagramas chamados de grafos orientados ou de digrafos.

Por exemplo, se  é a relação binária definida no conjunto [4] definida por

 = {(1,2) (1, 3), (2, 2), (2, 3), (3, 2), (3, 3), (4, 4)} pode ser representada pelo digrafo ([4],  ) que apresentamos de seguida ([4],  ) 1

2

3

4

O digrafo ([5],  )

1

4

2

3

5

representa a relação  (escreva  em extensão ) definida no conjunto [5]. Esta

relação é uma equivalência no conjunto [5] (Verifique!).

Se  é uma relação binária definida num conjunto finito A, a relação  pode ser definida por um digrafo, também chamado de grafo orientado, cujos vértices são

8/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

os elementos do conjunto A e as arestas são os pares ordenados que constituem a relação  . Mais formalmente apresentamos a seguinte definição.

Definição.

Um digrafo, também chamado de grafo orientado, é um terno

D graf o= (V, A, i), onde: 

V é um conjunto a cujos elementos chamamos vértices (do digrafo);



A é um conjunto a cujos elementos chamamos arestas (do digrafo);



i: A  V x V é uma função i: A  V x V a  (i 1 (a), i 2 (a) )

chamada função incidência. Se a é uma aresta, a i 1 (a) chamamos origem ou extremidade inicial, enquanto a i 2 (a) chamamos alvo ou extremidade final da aresta a.

Se considerarmos o último digrafo ( [5],  ) que apresentámos e que voltamos a escrevê-lo aqui

1 2

4

3

5 ,

verificamos que a relação  divide o conjunto [5] em três subconjuntos todos não vazios, disjuntos entre si e cuja união é o conjunto [5] onde a relação  está definida: {1}, {2, 3}, {4, 5}.

9/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

A relação  é claramente reflexiva, pois cada vértice tem uma aresta com origem e alvo nesse vértice. Às arestas cuja origem coincide com o seu alvo, chamamos lacete. É também simétrica, pois para cada aresta com origem distinta do seu alvo é representada por uma bisseta o que significa que para cada aresta de extremidades distintas ( (i 1 (a), i 2 (a) ) há uma aresta de sentido contrário, isto é cujas extremidades são (i 2 (a), i 1 (a) ). Além disso, sempre que haja duas arestas consecutivas, há uma aresta com origem na origem da primeira aresta e cujo alvo coincide com o alvo da segunda aresta, o que garante que a relação  é também transitiva, isto é,  é uma relação de equivalência no conjunto [5].

Reparamos ainda que cada um dos subconjuntos referidos acima, são constituídos pelos elementos que se relacionam um com os outros. Por exemplo, no conjunto {1} estão os elementos que estão em relação com o elemento 1; no conjunto {2, 3} estão os elementos que se relacionam com o elemento 2 e no conjunto {4,5} estão os elementos que se relacionam com o elemento 4. A estes subconjuntos, chamamos as classes de equivalência pela relação de equivalência

 . Escrevemos [1]  , [2]  e [4]  e dizemos classe de equivalência-  do 1, 2 e 4 respectivamente.

Por inspecção directa verificamos que [2]  = [3]  e [4]  = [5]  . O conjunto das classes de equivalência-  , {[1]  , [2]  , [4]  } é o conjunto quociente do conjunto [5] pela equivalência  ; designamo-lo por [5]/  .

Mais formalmente apresentamos a seguinte definição

10/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

Definição. Sejam 

uma relação de equivalência definida num qualquer

conjunto A e a um elemento deste conjunto. 

Chamamos classe de equivalência-

de a ao subconjunto de A

designado por [a]  definido por [a]  = {x A : x a }; 

O conjunto quociente de A por  é o conjunto representado por A/ cujos elementos são as classes de equivalência-  , isto é, A/ = { [a]  : a  A }.

A próxima proposição sumariza as principais propriedades das classes de equivalência. Proposição. Sejam   Eq(A) e a, b  A. 

[a]  ≠ Ø;



[a]  = [b]  se, e só se, a  b;



[a]  ≠ [b]  se, e só se [a]   [b]  = Ø;



[a]  = A. a A

Para terminamos vejamos alguns exemplos.

1. Se   Eq(Z) é definida por z  w se, e só se, z e w têm a mesma paridade, há apenas duas classes de equivalência, a saber: [0]  = { x  Z : x é par } e [-1] = { x  Z : x é ímpar }. O conjunto quociente Z/  é finito e tem cardinal dois, pois Z/  ={[0]  , [-1]  }.

2. Se   Eq(Z) é a equivalência definida por z w se, e só se, z 2 = w 2 o conjunto Z/ é infinito, mais concretamente este conjunto é equipotente ao conjunto N

11/ 12

DEISI - Departamento de Engenharia Informática e Sistemas de Informação

dos números naturais. Com efeito, se z é um inteiro, então [z]  = {z, -z} e, portanto, dado que um dos inteiros z ou –z é um natural, então [z]  =[│z│] . A função f:N  Z/ definida por f(n)= [n]  é claramente bijectiva.

3. Se   Eq(R) é a relação equivalência “igualdade de característica” isto é,  é definida por x  y se, e só se,  x =  y  . O conjunto quociente R/ é infinito, mais concretamente este conjunto é equipotente ao conjunto Z dos números inteiros. De facto, dado um número real, a sua característica representada por z =  x é um número inteiro e

 x = [z, z+1[,

portanto R/ = { [z]  : z  Z } (Porquê? Pense nisto . Não fique

indiferente a este desafio). A função f:Z  R/ definida por f ( z ) = [z]



é obviamente uma bijecção. A

bijectividade desta função é óbvia para si? Se não for, peça ajuda aos seus Professores.

12/ 12...