Relações Binárias 695h6u

Relações Binárias Considere A um conjunto não vazio. Uma relação binária R sobre o conjunto A ou endorrelação ou auto-relação é qualquer subconjunto do produto cartesiano A × A , isto é, R ⊆ A × A . Um par ordenado (a, b) ∈ A × A satisfaz a relação R quando ( a, b) ∈ R ou aRb , caso contrário, (a, b) ∉ R ou aR/ b .

Exemplo: Considere o conjunto A = {a, b, c} e a relação binária R = {( a, a), (b, a), (c, c)} ⊆ A × A .

A relação R pode ser representada, por exemplo, por:

a

b c

Uma relação R sobre o conjunto A pode ser classificada como: ƒ

Reflexiva quando para todo x ∈ A , ( x, x) ∈ R ou xRx .

ƒ

Simétrica quando para quaisquer x, y ∈ A , se xRy então yRx .

ƒ

Anti-simétrica quando para quaisquer x, y ∈ A , se xRy e yRx então x = y .

(contra-positiva) para quaisquer x, y ∈ A , se x ≠ y então ( x, y ) ∉ R ou ( y, x) ∉ R . ƒ

Transitiva quando para quaisquer x, y, z ∈ A , se xRy e yRz então xRz .

Exemplos: Considere o conjunto Z dos números inteiros. xRy x é múltiplo de y x=y x≤ y x< y

reflexiva 9 9 9

simétrica

anti-simétrica

9 9 9

transitiva 9 9 9 9

1

Relação de Ordem Uma relação binária R sobre um conjunto A é denominada uma relação de ordem A quando for reflexiva, anti-simétrica e transitiva. Notação: R:  Uma relação de ordem  sobre o conjunto A é total quando para quaisquer x, y ∈ A , x  y ou y  x. Quando não é possível comparar quaisquer dois elementos a relação é denominada um ordem parcial. Exemplos: 1) Considere o conjunto A = {a, b, c} . Os diagramas abaixo representam relações de ordem.

a

a

b

a

b

c

c

b c

O diagrama de uma relação de ordem pode ser simplificado e é denominado diagrama de Hasse. c b

b a

b

c

a

c

a

2) A relação ≤ em Z é relação de ordem total. 3) Seja 2 A o conjunto das partes de um conjunto A não vazio. A relação ⊆ em 2 A é uma relação de ordem parcial.

{1,2}

4) Considere A = {1,2} , 2 A e a relação de inclusão. Seu diagrama de Hasse é: {1}

{2}

∅

2

A Relação de Divisibilidade em Z

Sejam x, y ∈ Z . Se existir k ∈ Z tal que y = k ⋅ x , diz-se que x divide y ou x é um divisor de y ou x é um fator de y ou y é múltiplo de x ou y é divisível por x. Desta forma, fica definida a relação binária de divisibilidade em Z. Notação: x | y

TeoRD: Sejam x, y, z , t , y1 ,..., y n , k ∈ Z , k ≠ 0 . Então: i) ii) iii) iv) v) vi) vii) viii) ix)

x | 0. A relação de divisibilidade é reflexiva. ±1| x . A relação de divisibilidade é transitiva. Se x | y e z | t então x ⋅ z | y ⋅ t . Se x | y + z e x | y então x | z . Se x | y1 ,..., x | yn então x | k1 ⋅ y1 + ... + kn ⋅ yn , para quaisquer k1 ,..., kn ∈ Z . x | y se e somente se x ⋅ k | y ⋅ k . Se x | y e y | x então x = y ou x = − y .

A relação de divisibilidade não é simétrica nem anti-simétrica. O número p ∈ Z , p ≠ ±1 é denominado número primo quando seus divisores são ± 1 e ± p . Caso contrário é denominado número composto.

Observe que se considerarmos o conjunto de números inteiros positivos Z + , a divisibilidade é uma relação de ordem parcial. Exemplo: Considere A = {1,2,3,5,6,10,15,30} e a relação |. O diagrama de Hasse é:

30

6

10

15

2

3

5

1

3

Relação de Equivalência Uma relação binária R sobre um conjunto A é denominada uma relação de equivalência em A quando for reflexiva, simétrica e transitiva.

−, ≅, ≈,. ≡ Notação: R : ~

Exemplos: Considere o conjunto Z dos números inteiros. As relações abaixo são de equivalência: 1) x ≈ y se e somente se x = y . 2) x ≈ y se e somente se x − y é múltiplo de 3. 3) Considere o conjunto A = {a, b, c} . Os diagramas abaixo indicam relações de equivalência.

a

b

a

c

b

a

c

b c

Os diagramas acima podem ser simplificados da seguinte forma:

a

b c

a

b

a

c

b c

Seja uma relação de equivalência ≈ sobre um conjunto A. O conjunto a = {x ∈ A | x ≈ a} é denominado a classe de equivalência do elemento a ∈ A relativa à relação ≈ e a família A = {a | a ∈ A} é denominada de conjunto quociente de A pela relação ≈ . ≈

4

Exemplos: 1) Considerando o exemplo 3 anterior, temos: A = {a , b , c } sendo a = {a} , b = {b} e c = {c} , ≈ A = {a , c } com a = b = {a, b} e c = {c} e ≈ A = {a } sendo a = b = c = {a, b, c} . ≈ b

2) Considere o diagrama abaixo da relação de uma equivalência ≈ .

a

A = {a , c } , sendo que a = b = {a, b} e c = d = {c, d } ≈

d c

Propriedades: RE1. Seja A um conjunto e ≈ uma relação de equivalência em A. Para todo a ∈ A , a ≠ ∅ . RE2. Seja A um conjunto, ≈ uma relação de equivalência em A e a, b ∈ A . São equivalentes: i) ii) iii) iv)

a≈b a∈b b∈a a =b

RE3. Seja A um conjunto, ≈ uma relação de equivalência em A e a, b ∈ A . Então: i) a = b ou a ∩ b = ∅ ii) U a = A a∈ A

Considere um conjunto A não vazio e seu conjunto das partes 2 A . Um conjunto não vazio P ⊆ 2 A é uma partição do conjunto A quando: P1. Para quaisquer X , Y ∈ P, X ≠ Y , X ∩ Y = ∅ P2.

UX = A

X ∈P

RE4. Seja P uma partição de A. A relação R sobre o conjunto A tal que xRy se e somente se existe

X ∈ P tal que x, y ∈ X , é uma relação de equivalência no conjunto A.

5

A Relação de Congruência Módulo n Considere o conjunto Z dos números inteiros e n ∈ Z*+ . Define-se a relação binária R ⊆ Z × Z tal que xRy se e somente se n | x − y . Esta relação é denominada congruência módulo n sobre o conjunto Z.

Notação: x ≡ y mod n Exemplo: Seja n = 7 . 0

1

2

3

4

5

6

. -7 0 7 14 21

. -6 1 8 15 22

. -5 2 9 16 23

-10 -4 3 10 17 .

-11 -3 4 11 18 .

-12 -2 5 12 19 .

-13 -1 6 13 20 .

TeoCMn: A relação de congruência módulo n sobre o conjunto Z é de equivalência As classes de equivalências 0,1,K n − 1 , induzidas pela relação de congruência módulo n, são denominadas classes residuais módulo n e tais que 0 = {0,± n,±2n,K} = {kn, k ∈ Z} ,

1 = {kn + 1, k ∈ Z}, K, n − 1 = {kn + (n − 1), k ∈ Z} . = Z n = 0,1,K n − 1 dos inteiros módulo n. Assim, temos o conjunto quociente Z ≡ mod n

{

}

Exercícios 1) Classifique as relações abaixo. a) N : xRy se e somente se x + y = 10 b) N : xRy se e somente se mdc( x, y ) = 1 c) d) Z : xRy quando xy ≠ 0 e) N × N : ( x, y ) R( z, t ) se e somente se x + y = z + t f) Z × Z* : ( x, y ) R( z, t ) se e somente se xt = yz g) Q : xRy se e somente se x − y ∈ Z h) C : x + yiRz + ti se e somente se y = t 2) Faça os diagramas de Hasse. a) A = {1,2,3,12,18,36} e |. b) A = {1,2,3} e ⊆ em 2 A . 3) Para as relações de equivalência do exercício 1, escolha um elemento do conjunto e indique sua classe de equivalência. 4) Seja f : A → B uma função. Considere a relação R sobre o conjunto A tal que xRy se e somente se f ( x) = f ( y ) . Mostre que a relação R é de equivalência. 6