4.3 TIPOS DE RELAÇÕES

4.3.1 Relação binária.

Definição 4.8 Relação binária.

Seja A=B dizemos relação binária, a toda relação entre elementos de A.

Segundo nossa definição R é uma relação binária sobre A, se R  A  A .

4.3.2 Relação reflexiva.

Definição 4.9 Relação reflexiva.

Seja R uma relação binária definida do conjunto A ; dizemos que R é reflexiva se, qualquer que seja o elemento x  A , o par (x, y) verifica a relação x = y .

Isto é, R é reflexiva se, e somente se,  x  A, (x, x)  R

Exemplo 4.15

Seja A = N e R a relação “. . . tem como quadrado a . . . “.

Esta relação não é reflexiva, observe que os únicos pares ordenados que satisfazem a relação são (0, 0) e (1, 1)

Exemplo 4.16

Seja A = N e R a relação x = y, x, y  N.

Os pares ordenados (0, 0), (1, 1) e (2, 2) , pertencem ao gráfico da relação R , então para todo x  N, (x, y)  R ; isto é R é reflexiva.

O gráfico de R contém os pares (x, x) , que é a diagonal do conjunto A2 .

Então R é reflexiva se, e somente se,  A2  G_ R .

Exemplo 4.17

Seja A um conjunto, consideramos o conjunto de partes P(A) , então a inclusão e a igualdade em P(A) são reflexivas.

Exemplo 4.18

1. Suponha o conjunto B = { x /. x é uma reta do plano } e a relação definida por:

R1 = { (x, y)  B  B /. x é paralela a y }

ela é reflexiva em B , pois toda reta é paralela consigo mesma; cumpre que (x, x)  R1  x  B .

2. Suponha o conjunto B = { x /. x é uma reta do plano } e a relação definida por:

R2 = { (x, y) B  B /. x é perpendicular a y }

ela não é reflexiva em B , pois toda reta não é perpendicular consigo mesma; não cumpre que (x, x)  R2  x  B .

4.3.3 Relação simétrica.

Definição 4.10 Relação simétrica.

Uma relação binária R , definida de um conjunto A , é simétrica se qualquer que seja o par (x, y)  R que verifica a relação, então o par (y, x) também verifica a relação.

De outro modo; uma relação R  A  A é simétrica se, e somente se, (x, y)  R  (y, x)  R,  (x, y)  R .

Exemplo 4.19

Sejam A = { x /. x é uma reta do plano } e a relação R = { (x, y)  A2 /. x é perpendicular a y } é simétrica em A , pois toda reta x que seja perpendicular a y , cumpre que y é perpendicular a x ; isto é, cumpre que (y, x)  R  (x, y)  R .

Exemplo 4.20

Em N a relação x = y é simétrica; isto do fato y = x .

Exemplo 4.21

Em N a relação “ . . . têm por quadrado a . . . “ não é simétrica, é suficiente observar que o par (3, 9) verifica, porém o par (9, 3) não satisfaz a relação.

4.3.4 Relação anti-simétrica.

Definição 4.11 Relação anti-simétrica.

Dizemos que uma relação binária R sobre A é anti-simétrica, se para todo (x, y)  R e (y, x)  R ; verifica a relação x = y

Isto é, R  A  A é anti-simétrica se, e somente se, [(x, y)  R  (y, x)  R ]  x = y

Exemplo 4.22

Seja P(A) o conjunto potência de A , a relação R = { (A, B)  P(A)2 /. A  B } é anti-simétrica.

Com efeito:

1. A  B e B  A  A = B . . . def. de 

2. Logo, (A, B)  R  (B, A)  R  A = B . . ( 1 ), def. de =

Portanto de ( 2 ), R é anti-simétrica.

Exemplo 4.23

A relação R = { (a, b)  R2 /. a  b } é anti-simétrica. Com efeito:

1. a  b e b  a  a = b . . . def. de 

2. Logo, (a, b)  R  (b, a)  R  a = b . . ( 1 ), def. de =

Portanto de ( 2 ), R é anti-simétrica.

Exemplo 4.24

Seja A = N e R a relação “. . . divide a . . . “.

Esta relação é anti-simétrica, observe que se x divide y e y divide x então, x = y .

4.3.5 Relação transitiva.

Definição 4.12 Relação transitiva.

Dizemos que uma relação binária R sobre A é transitiva, se para todo (x, y)  R e (y, z)  R verifica-se que (x, z)  R .

Isto é, R  A  A é transitiva se, e somente se, [(x, y)  R  (y, z)  R ]  (x, z)  R .

Exemplo 4.25

A relação R = { (a, b)  R2 /. a < b } é transitiva.

Com efeito:

1. a < b e b < c  a < c . . . def. de <

2. Logo, (a, b)  R  (b, c)  R  (a, c)  R . . . ( 1 ), def. de R

Portanto de ( 2 ), R é transitiva.

Exemplo 4.26

1. A relação de inclusão  é transitiva; isto do fato que se A  B  B  C  A  C

2. A relação de igualdade = em P(A) é transitiva.

3. Se R = { (2, 1), (1, 2), (1, 1), (1, 3), (4, 4) } , então R não é transitiva. Isto pelo fato (2, 1 )  R  (1, 3)  R , não implica que (2, 3)  R

4.3.6 Relação de equivalência.

Definição 4.13 Relação de equivalência.

Uma relação binária, definida em um conjunto A  , é relação de equivalência se, e somente se, ela é reflexiva, simétrica e transitiva.

Isto é; diz-se que um subconjunto R de A  A define uma relação de equivalência sobre A , se satisfaz as seguintes condições:

1. (a, a)  R para todo a  A .

2. (a, b)  R implica que, (b, a)  R .

3. (a, b)  R e (b, c)  R então (a, c)  R

Ao invés de falar de subconjuntos de A  A podemos falar de uma relação binária  (relação entre dois elementos de A ) sobre o próprio A , definindo que b esta relacionado com a se (a, b)  R .

Exemplo 4.27

Seja Z o conjunto de números inteiros. Dados a, b  A definamos ab se a-b for um número inteiro par. Verifiquemos que  define uma relação de equivalência em Z  Z.

Solução.

1. Do fato 0 = a - a é par, segue que a  a .

2. Para a  b tem-se que a - b é par, do fato b-a = -(a-b) tem-se que a - b também é par, portanto cumpre que b r a (é bem definido).

3. Se a  b e b  c , então tanto a - b e b-c são pares, logo a - c = (a - b) + (b - c) é par, assim a  c é bem definido.

Portanto,  define uma relação de equivalência em Z  Z .

Nossa definição de relação de equivalência podemos escrever na forma: 

Definição 4.14

A relação binária,  sobre A é dita uma relação de equivalência sobre A , se para qualquer elemento a, b, c  A tem-se que:

1. a  a .

2. a  b implica que, b  a .

3. a  b e b  c implica a  c .

A primeira destas relações é a reflexibilidade, a segunda simetria e a terceira transitividade.

O conceito de relação de equivalência é bastante importante e desempenha um papel central em toda a matemática.

Exemplo 4.28

A semelhança de triângulos é um exemplo de relação de equivalência

Isto significa que, se a, b e c são três triângulos semelhantes quaisquer, então verificam as três seguintes condições:

1. a é semelhante com a .

2. Se a é semelhante com b , então b é semelhante com a .

3. Se a é semelhante com b e, se b é semelhante com c , então a é semelhante com c .

Exemplo 4.29

Outro exemplo de relação de equivalência é a congruência de triângulos, as condições do (1), (2) e (3) do Exemplo (4.28) também verificam-se se substituímos a palavra “semelhante” por `”congruente”.

Observação 4.4

Se R é uma relação de equivalência, para traduzir que o par (a, b) verifica a relação R , podemos substituir a notação (a, b)  R por a  b mod R , e se lê `` a é equivalente a b módulo R ''

Logo, se a, b, c são elementos quaisquer de um conjunto A , e se R é relação de equivalência em A , tem-se:

•  a  A, a  a mod R

• a  b mod R  b  a mod R

• a  b mod R  b  c mod R a  c mod R

Exemplo 4.29

Seja A = Z . Considere em A = Z a relação binária R ``. . . a diferença de dois inteiros, é um múltiplo de 3”.

Esta relação é de equivalência pelo seguinte:

•  a A, a  a mod 3 , isto é a - a = 0 = 3k para algum k  N, logo é múltiplo de 3 . . . reflexiva

• a  b mod 3 , isto é a-b = 3r o que podemos escrever b - a = 3(-r) para algum r  N logo, b-a é múltiplo de 3 , assim b  a mod 3 . . . simétrica

• a  b mod 3 , isto é a-b = 3t para algum t  N e de b  c mod 3 , segue que b - c = 3s para algum s  N, logo a - c = (a - b)+ (b - c) = 3(t+s)  a - c = 3(t+s) para algum t+s  N, logo a-c é múltiplo de 3 e, a  c mod 3 . . . transitiva

Exemplo 4.30

Seja P o conjunto de proposições. A relação R = { (p, q)  P  P /. p  q } não é de equivalência.

Com efeito.

A relação é reflexiva; temos que p  p é verdadeira (tautologia)  p  P .

A relação é transitiva; lembre que ( p  q  q  r )  (p  r) é verdadeira (tautologia).

A relação R não é simétrica (p  q)  (q  p) não é tautologia.

Portanto, R não é de equivalência.

Exemplo 4.31

Se A = {, ,  } .

a. Defina em A , uma relação que seja simétrica e não reflexiva.

b. Defina em A , uma relação que seja transitiva e não simétrica.

c. Defina em A , uma relação que seja reflexiva e não seja simétrica nem transitiva.

Solução (a)

R1= { (,), (,), (,), (, ) , (, ), (,) }

Solução (b)

R2= { (i, ), (,), (, ) }

Solução (c)

R3= { (,), (,), (, ), (, ), (,) }

4.3.7 Relação inversa.

Definição 4.15

Seja R  A  B , a relação inversa de R denotada por R* é definida por: R* = { (b, a)  B  A /. (a, b)  A  B }

Exemplo 4.33

Sejam A = { 1, 2, 3 } e B = { a, b } e consideremos a relação R = { (1, a), (1, b), (3, a) } de A em B , logo a relação inversa de R é o conjunto R* ={ (a, 3), (b, 1), (a, 1) }

Exemplo 4.34

Se uma relação R é transitiva, então sua relação inversa R* também é transitiva?

Solução.

Sejam (a, b) e (b, c) elementos de R* , então (b, a)  R e (c, b)  R , como R é transitiva então (c, a)  R ; logo (a, c)  R* .

Portanto mostramos que se, (a, b)  R* e (b, c)  R* então (a, c)  R* ; a relação R* é transitiva.

Exemplo 4.35

Figura 4.5:

Que relação existe entre o domínio e imagem de uma relação R , e o domínio e imagem de sua relação inversa R* ?

Solução.

Como R* tem os mesmos pares que R na ordem inversa (de escrita), cada primeiro elemento de um par em R é o segundo elemento de um par em R* , e cada segundo elemento em R é o primeiro elemento em R* . Conseqüentemente, o domínio de R é a imagem de R* , e a imagem de R é o domínio de R* .

Exemplo 4.36

Seja a relação:

R = { (x, y)  R2 /. 4x2+9y2= 36 } .

Determine: a) O domínio de definição de R ; b) a imagem de definição de R ; c) a relação R*

Solução (a)

O domínio de definição de R é o intervalo [-3, 3] , uma vertical por cada um destes números contém ao menos um ponto de R.

Solução (b)

A imagem é o conjunto [2, 2] , uma horizontal por cada um destes elementos contém ao menos um ponto de R.

Solução (c)

A relação R* encontra-se se intercambiamos x e y no enunciado formal que define R , logo R* = { (x, y) / x  R, y  R, 9x2 + 4y2= 36 }

Exemplo 4.37

Seja R a relação nos números naturais N definida pelo enunciado formal 2x+y = 10 . Determine: a) O domínio e imagem de R. b) A relação R* .

Solução (a)

O domínio D( R) = { 0, 1, 2, 3, 4 } e a imagem Im( R) = { 0, 8, 6, 4, 2 }

Solução (b)

R*= { (x, y) /. x  N, y  N, x + 2y = 10 } ; isto é R* = { (8, 1), (6, 2), (4, 3), (2, 4) }

Exercícios 4-1

1. Determine os valores de x, y, z da seguinte igualdade entre os pares ordenados:

1. (x+1, 2)= (3, y+3) 2.(2x+3y, x-2y)= (1, 2)

3. (x+y, 3)=(5, y-x) 4. (2x+2y+3z, x+y+z ,x-y+z ) =(14, 5, 9)

5.(x+5, 3-y) =(7, 2) 6. ( , , ) = (1, 2, 3)

2. Suponhamos os conjuntos A = {1, 2, 3} e B = { 1, 5 } . Verifique as seguintes proposições:

1. A  B  B  A 2. (A  B)  B  A  (B  A) .

3 A  B = { (1, 1), (1, 5), (2, 1), (2, 5), (3, 1), (3, 5) } .

4. B  A = { (1, 1), (5, 1), (1, 2), (5, 2), (1, 3), (5, 3) } .

5. A^2  B^2 (A^2 = A  A e B^2 = B  B ).

3. Sejam A, B , C e D conjuntos quaisquer. Demonstrar:

1. (A  B)  C = (A  C)  (B  C) 3. (A - B)  C = (A  C) -(B  C)

2. (A  B)  (C  D) = (A  C) (B  D)

4. Mostre que: A  X e B  Y , se, e somente se A  B  X  Y , desde que A  B  .

5. Sejam A, B e C três conjuntos quaisquer. Demonstrar as seguintes proposições:

1. A  B = B  A se, e somente se, A = B ou ao menos um deles é o conjunto vazio.

2. Se (x, y)  A2 , então (y, x)  A2 .

3. A  B = A  C se, e somente se, B = C ou A =  .

4. (A  B)  C = A  (B  C) se, e somente se, ao menos um dos conjuntos A, B ou C é vazio.

6. Sejam os conjuntos A = { 1, 2, 3 } e B = { 2, 4, 5 } , analisar quais dos conjuntos Ri são relações de A em B .

1. R1 = { (1, 4), (1, 5) } 2. R2 = { (1, 4), (1, 7) }

3. R3 = { (1, 4), (1, 5), (3, 5) } 4. R4 = { } = 

5. R5 = { (1, 1), (2, 2), (2, 4) } 6. R6 = A  B

7. Sejam os conjuntos A = { 2, 3, 5 } e B = { 3, 6, 7, 10 } , analisar quais dos conjuntos Ri são relações de A em B .

1. R1 = { (x, y)  A  B /. x = y }

2. R2 = { (x, y)   N /. x = 2y }

3. R3 = { (x, y)  A  B /. x > 5 }

8. Sejam os conjuntos A = {0, 1, 2 } e B = {3, 2, 1 } , escrever em forma de conjuntos a relação de A em B definida por x = y ; para x  A e y  B .

9. Suponha os conjuntos A = { 3, 5, 8, 9 } e B = { 1, 3, 5, 7 } , escrever em forma de conjuntos a relação de A em B definida por:

1. x < y; x A e y  B 2. x  y; x  A e y  B

3. x = y; x  A e y  B 4. y + x = 4; x  A e y  B .

5. x é divisível por y; x  A e y  B .

10. Seja A = N , e a relação a = b , cujo gráfico é G_{A  A} = { (a, b)  N  N /. a = b } , construir uma relação binária definida sobre N .

11. Seja A = { 1, 2, 3 } . O os conjuntos A = { (1, 1), (2, 2), (3, 3) } e K = { (1, 2), (2, 3) } constituem gráficos de relações binárias sobre A , em tanto que o conjunto L = { (1, 5), (2, 3) } não. Por quê?

12. Dados os conjuntos A = { a, b, c } e B = { a, b, d } . Quais dos seguintes conjuntos são gráficos de relação entre elementos x  A e y  B ? Em cada caso dar o domínio e imagem.

1. R1 = { (a, a), (b, b), (c, c) }

2. R2 = { (b, c) }

3. R3 = { (a, d), (b, d), (d, a) }

4. R4 = { (b, a), (a, b), (c, c) }

5. R5 = { (d, a), (d, d), (b, d) }

13. Quais dos conjuntos do exercício anterior são gráficos de relação entre elementos x  B e y  A ?

14. Se A = { (3a+1) /. (a  N  a  3)  (a  Z  0  a <5 } . Calcule a diagonal de A  A . Construir o gráfico.

15. Se A = { x  R /. 2 < x < 5 } e B = { x  R /. 1 < x < 4 } . Construir o gráfico A  B ; logo B  A .

16. Se M = { x  R /. 2  x  5 } e N = { x  R /. 1  x < 4 } . Construir o gráfico de M  N ; logo N  M .

17. Seja R uma relação em A = { 2, 3, 4, 5 } definida pelo enunciado formal “x e y são primos relativos”.

1. Escrever R como conjunto de pares ordenados.

2. Representar R num diagrama de coordenadas A  A .

18. Seja A um conjunto qualquer e seja  A a diagonal de A  A . Que relação existe entre todas as relações reflexivas de A  A e A ?

19. Os enunciados formais que seguem, definem relações no conjunto R. Representar cada relação em um diagrama de coordenadas de R  R .

1. y < x2-4x+2 2. x < y2 3. y  +2 4. x  sen x

20. Seja A = { 1, 2, 3, 4 } e a relação Ri sobre A, para i = 1, 2, 3, 4 . Determine se a relação:

1. R = { (1, 1), (1, 3), (2, 2) , (3, 1), (4, 4) } é reflexiva.

2. R = { (1, 2), (3, 4), (2, 1) , (3, 3) } é simétrica.

3. R = { (1, 2), (3, 4), (2, 2), (3, 3), (2, 1) } é anti-simétrica.

4. R = { (1, 2), (4, 3), (2, 2), (2, 1) , (3, 3) } é transitiva.

21. Dado A = { 1, , 2, 3, 4, 5 } considere as seguintes relações em A :

1. R1 = { (1, 1), (1, 2) } 2. R2 = { (1, 1), (2, 2), (3, 3) }

3. R3 = { (1, 1), (2, 3), (4, 1) } 4. R4 = { (1, 3), (2, 4) }

Determine, quais dessas relações é: Reflexiva, simétrica, anti-simétrica ou transitiva.

22. Existe algum conjunto A no qual toda relação seja simétrica?

23. Mostre que se R e S são relações simétricas em um conjunto A , então R  S é uma relação simétrica em A .

24. Pode uma relação em um conjunto A ser simétrica e anti-simétrica?

25. Seja A = { 1, 2, 3 } . Determine se cada uma das seguintes relações em A é anti-simétrica.

1. R _1 = { (1, 1) } 2. R_2 = { (1, 2) } 3. R _3=A  A

4. R4 = { (1, 2), (2, 1), (2, 2), (3, 2), (2, 3) } 5. R5 = { (1, 1), (2, 3), (3, 2) }

26. Os seguintes enunciados formais definem cada um uma relação R no conjunto de números naturais N . Determine para cada caso se a relação é: a) Reflexiva. b) Simétrica. c) Transitiva. d) Anti-simétrica.

1. x é menor que y 2. x+y = 12 3. x e y são primos relativos.

4. x divide y 5. x + 4y = 12 6. x é menor ou igual que y

7. x é múltiplo de y 8. x vezes y é o quadrado de um número

27. Para cada umas das relações R do exercício anterior, determine um enunciado formal que defina a relação R*

28. Seja R = { (a, b)  R2 /. b  a } mostre que R é anti-simétrica.

29. Prove que em N a relação “x divide a y” é uma relação anti-simétrica.

30. Seja A = { 1, 2, 3 } . Dar um exemplo de uma relação em A que não seja simétrica nem anti-simétrica.

31. Quando uma relação R sobre um conjunto A é:

1. Não reflexiva? 2. Não simétrica?

3. Não anti-simétrica? 4. Não transitiva?

32. Estabelecer a verdade ou falsidade das seguintes proposições, supondo R e R* relações em um mesmo conjunto A .

1. Se R é simétrica, então, R * é simétrica.

2. Se R é anti-simétrica, então, R* é anti-simétrica.

3. Se R é reflexiva, então R  R*  .

4. Se R é simétrica, então R  R*  .

5. Se R é transitiva e R* é transitiva então R  R* é reflexiva.

6. Se R é transitiva e R* é transitiva então R  R* é reflexiva.

7. Se R é reflexiva e R* é reflexiva então R  R* é reflexiva.

8. Se R é anti-simétrica e R ^* é anti-simétrica então R  R ^* é anti-simétrica.

9. Se R é reflexiva e R* é reflexiva então R  R * é reflexiva.

10. Se R é anti-simétrica e R* é anti-simétrica então R  R* é anti-simétrica.