Introdução às relações

Estamos muito acostumados a utilizar as relações em nosso cotidiano, tais como "maior que", "menor que", entre outras. Essas relações são responsáveis pela existência ou inexistência de conexão entre pares de objetos.

Seguindo a definição, o termo relação deve significar relação binária.

Imagem ilustrativa, não refere-se ao exemplo abaixo.
Wikipédia.

Como um exemplo de relação, temos que A=(1,2,3) e B={x,y,z}, sendo R={(1,y),(1,z),(3,y)}.

-R é uma relação de A em B, sendo R um subconjunto de AxB.

-O domínio de R é {1,3} e a imagem é {y,z}.

Relação inversa:

Utilizando o mesmo exemplo citado acima, podemos determinar a inversa de R, denotada por. Fazendo a inversa da função R={(1,y),(1,z),(3,y)}, temos como resultado:

O domínio e a imagem de  são iguais ao domínio e imagem de R, pois se R é qualquer relação, então (R^-1)^-1=R.

Referência bibliográfica:

LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta. 3. ed. Porto Alegre: Bookman, 2013. xi, 471p. (Coleção Schaum). ISBN 9788565837736.

Representações pictóricas de Relações

Podemos representar as relações pictoricamente, ou seja, com elementos que representam a escrita.

Temos um conjunto S, que tem relação sobre o conjunto dos números reais R, ou seja, S é subconjunto de R² = R x R. S consiste em todos os pares ordenados do conjunto dos reais, que satisfazem alguma equação, como por exemplo x² + y² = 25.

A representação pictórica da relação é chamada, em alguns casos, de gráfico ou grafo da relação.

O gráfico da relação x² + y² = 25  é um círculo com centro na origem e raio 5.

Grafos orientados de relações sobre conjuntos:

Podemos visualizar uma relação R em um conjunto finito, em um diagrama chamado grafo orientado da relação. É feito do seguinte modo: escrevemos os elementos do conjunto, em seguida, puxamos uma flecha de cada elemento x para cada elemento y, quando x se relacionar com y. 

Como exemplo, podemos citar um grafo orientado da seguinte relação R sobre o conjunto A={5,6,7,8}:

R={(5,6),(6,6),(6,8),(7,6),(7,8),(8,5),(8,7)}

O exemplo acima, fica do seguinte modo na forma de grafo:

Representações pictóricas de relações sobre conjuntos finitos:

 Há duas maneiras de relacionar conjuntos finitos. Se tivermos A e B, dois conjuntos finitos, podemos relaciona-los formando uma matriz ou um diagrama de flechas da relação.

No caso de uma matriz, as linhas serão compostas pelos elementos de A e as colunas por elementos de B. 1 e 0 são inseridos nas posições, dependendo se os elementos de A estão ou não relacionados com os elementos de B. 

Matriz dos conjuntos A e B.

Em um diagrama de flechas, os elementos de A ficam em um disco e os de B em outro, então são feitas flechas sempre que algum elemento de A se relaciona com algum elemento de B.

Diagrama de flechas dos conjuntos A e B.

Nos dois casos acima, R={(1,y),(1,z),(3,y)}.

Referência bibliográfica:

LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta. 3. ed. Porto Alegre: Bookman, 2013. xi, 471p. (Coleção Schaum). ISBN 9788565837736.

Composição de relações

Existem algumas maneiras de relacionarmos mais de dois conjuntos. Se tivermos, por exemplo, três conjuntos, A, B e C, sendo que R é uma relação de A em B e S é uma relação de B em C. Por fim, R e S dão origem a uma relação de A em C, que podemos denotar por RoS.
A relação de R e S é chamada de composição de R e S, algumas vezes, podemos denota-la apenas por RS.
Se tivermos, por exemplo, um conjunto B com relação sobre ele mesmo, então podemos denotar por RoR ou R².
Como vimos na postagem anterior, podemos representar as relações com diagramas de flechas e com matriz da relação. Vejamos o exemplo abaixo:

Temos um conjunto A={1,2,3,4}, um conjunto B={a,b,c,d} e um outro conjunto C={x,y,z}, em que R={(1,a),(2,d),(3,a),(3,b),(3,d)} e S={(b,x),(b,z),(c,y),(d,z)}.
Podemos construir o seguinte diagrama de flechas com o exemplo:

Podemos concluir desse diagrama, que há um caminho que liga 2 a z, do 2 vai para d e de d vai para z, nesse caso podemos dizer que 2(RoS)z. Vemos também que há 3(RoS)x e 3(RoS)z. Esses são os elementos de A que se relacionam com algum elemento de C. Nesse caso, concluirmos: RoS={(2,z),(3,x),(3,z)}. 

Há um teorema, o qual diz que composição de relações é associativa.

Composição de relações e matrizes:

Podemos determinar RoS através de matrizes. Onde as relações R e S, são representadas nas matrizes com MR e MS.

Quando multiplicamos uma matriz pela outra, obteremos quais elementos estão relacionados por RoS:

Referência bibliográfica:

LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta. 3. ed. Porto Alegre: Bookman, 2013. xi, 471p. (Coleção Schaum). ISBN 9788565837736.

Tipos de Relação

Relação reflexiva:

Em um conjunto qualquer, podemos dizer que existe relação reflexiva se os subconjuntos deste conjunto possuírem os mesmos elementos, por exemplo:

Exemplo1:

Conjunto A

A= { a, b, d, z }

Relações:

R₁ = { (a,b), (b,a), (b,z) } Não é reflexiva

R₂ = { (a,b), (b,d), (z,z) } Não é reflexiva

R₃ = { (a,a), (a,b), (b,b), (d,d), (z,z) } É reflexiva

Exemplo 2:

Conjunto K

K= { 1, 4, 10 }

Relações:

R₁ = { (1,1), (1,4), (4,4) } Não é reflexiva

R₂ = { } Não é reflexiva

R₃ = { (1,1), (1,4), (1,10), (4,1), (4,4), (4,10), (10,1), (10,4), (10,10)}

É reflexiva

Podemos dizer que a relação é reflexiva de tal conjunto, se este apresentar os pares de todos os números iguais pertencentes ao conjunto.

Relação simétrica e Anti-simétrica:

Em um conjunto R qualquer dizemos que a relação é simétrica quando (a,b) pertence ao conjunto R e obrigatoriamente o subconjunto (b,a) também pertença ao conjunto R, ao contrário a relação será anti-simétrica.

Exemplo 1:

Conjunto L = { 2, 4, 6, 8 }

Relações:

R₁ = {(2,4), (2,6), (6,8)} É anti-simétrica

R₂ = {(2,4), (2,6), (4,2), (6,8)} É simétrica

R₃ = { (2,4), (2,6), (2,8), (4,2), (8,2), (6,2)} É simétrica

Exemplo 2:

Conjunto K

K= { 1, 4, 10 }

Relações:

R₁ = { (1,1), (1,4), (4,4) } É anti-simétrica

R₂ = { } É anti-simétrica

R₃ = { (1,1), (1,4), (1,10), (4,1), (4,4), (4,10), (10,1), (10,4), (10,10)}

É simétrica

Uma relação R é simétrica se em um conjunto A (a,b) pertence a R implica (b,a) pertença a R. Uma relação R não é simétrica se em um conjunto A (a,b) pertence a R e (b,a) não pertença a R

Relação transitiva:

A relação R é transitiva em um conjunto, se a seguinte relação for satisfeita: (a,b) pertence a R e (b,c) pertence a R implica que (a,c) pertença a R, caso contrário a relação não é transitiva.

Exempo 1:

Conjunto A

A= { a, b, c, d }

Relações:

R₁= { (a,b), (a,d), (b,c), (c,d) } Não é transitiva

R₂= { (a,b), (a,c), (b,c), (a,c) } É transitiva

R₃= a<=b, b<=c então a<=c, É transitiva

R₄= Se a é perpendicular á b e b é perpendicular á c, então a não é perpendicular á c, a relação não é transitiva

Exemplo 2:

           Conjunto B

B= { 2, 10, 200 }

Relações:

R₁= { (2,10), (2,200), (10,2), (10,200), (200,2), (200,10) } É transitiva

R₂= { (2,2), (2,10), (10,10), (200,200) } Não é transitiva 

Uma relação R em um conjunto é transitiva se (a,b) e (b,c) pertencem a R implica (a,c) também pertença a R. Logo não é transitiva se (a,b) e (b,c) pertencem a R e (a,c) não pertença.

Referência bibliográfica:

LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta. 3. ed. Porto Alegre: Bookman, 2013. xi, 471p. (Coleção Schaum). ISBN 9788565837736.

Propriedade de Fecho

Fecho reflexivo e simétrico:

Um fecho é reflexivo quando adicionamos os elementos (a,a), (b,b)... que não pertencem à relação R. E um fecho é simétrico quando adicionamos os elementos (b,a) tais que (a,b) pertence à R.

Exemplo 1:

Conjunto A

A= { a, b, c, d }

Relações:

R₁= { (a,b), (b,b), (a,d), (c,d), (d,d) }

R₁= { (a,a), (a,b), (b,b), (a,d), (c,c), (c,d), (d,d) } Fecho Reflexivo

R₁= { (a,b), (b,a), (b,b), (a,d), (d,a), (c,d), (d,c), (d,d) } Fecho Simétrico

Exemplo 2:

Conjunto B

B= { 2, 10, 12, 200 }

Relações:

R₁= { (2,2), (2,10), (10,12), (12,200) }

R₁= { (2,2), (2,10), (10,10), (10,12), (12,12), (12,200), (200,200) } Fecho Reflexivo

R₁= { (2,2), (2,10), (10,2), (10,12), (12,10), (12,200), (200,12) } Fecho Simétrico

Reflexivo (R) é encontrado adicionando todos os valores (a,a) que não pertencem a relação em questão, e o Simétrico (R) é encontrado adicionando a R todos os valores (b,a) tais que (a,b) pertençam a relação original R.

Fecho Transitivo:

Seja R uma relação em um conjunto A, definimos R²= RxR e Rⁿ= R^n-1xR.

Relações:

1. R^* é o fecho transitivo da relação R. Suponha que A é um conjunto finito de n elementos, então:

R^*= R¹ U R² U ...U Rⁿ

2. Seja R umarelação em um conjunto A, com n elementos, então:

Transitivo(R)= R U R² U ... U Rⁿ

    Exemplo:

    Considere a seguinte relação R em A = (1, 2, 3):

    R= { (1,2), (2,3), (3,3) } Então:

    R² = RxR = { (1,3), (2,3), (3,3) }

    R³ = R²xR = { (1,3), (2,3), (3,3) }

    Coerentemente:

    Transitivo(R) = R U R² U R³ = { (1,2), (2,3), (3,3), (1,3) }

Referência bibliográfica:

LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta. 3. ed. Porto Alegre: Bookman, 2013. xi, 471p. (Coleção Schaum). ISBN 9788565837736.

Relações de Equivalência

Considere um conjunto S não vazio. Uma relação R sobre S é uma relação de equivalência se R é reflexiva, simétrica e transitiva. É uma relação de equivalência sobre S se tiver as três propriedades a seguir:

1. Para todo ,  aRa;

2. Se aRb, então bRa;

3. Se aRb e bRc, então aRc;

A relação de equivalência se trata de uma classificação de objetos que são “semelhantes” de alguma forma.

1. a=a para todo ;
2. Se a=b, logo, b=a;
3. Se a=b, b=c, temos a=c;

Referência bibliográfica:

LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta. 3. ed. Porto Alegre: Bookman, 2013. xi, 471p. (Coleção Schaum). ISBN 9788565837736.

Relações de Ordem Parcial

Uma relação R sobre um conjunto S é chamado de ordem de S se R é reflexiva, antissimétrica e transitiva. Um conjunto S munido de uma relação de ordem parcial R é dito um conjunto parcialmente ordenado.

Exemplo:

a) A relação  de uma inclusão conjuntista é uma ordem parcial sobre qualquer coleção de conjuntos, uma vez que a inclusão conjuntista tem as três propriedades desejadas.

    1)para qualquer conjunto A;

    2) Se  e , então A=B;

    3) Se  e , então ;

b) A relação <= sobre o conjunto R dos números reais é reflexiva, assimétrica e transitiva. Assim <= é uma ordem parcial em R.

c) A relação “a divide b” (a\b)é uma ordem parcial sobre o conjunto N dos números inteiros positivos. Contudo “a divide b” não é uma ordem parcial sobre o conjunto Z dos inteiros, uma vez que a/b e b/a não implica a=b. Exemplo: 3/-3 e -3/3, mas 3 ≠ -3.

Referência bibliográfica:

LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta. 3. ed. Porto Alegre: Bookman, 2013. xi, 471p. (Coleção Schaum). ISBN 9788565837736.

Relações n-Árias

Todas as relações recém-discutidas são binárias por uma relação n-árias, queremos dizer um conjunto de n-uplas ordenadas. Para qualquer conjunto S, um subconjunto do produto cartesiano Sⁿ é dito uma relação n-árias sobre S. 

Referência bibliográfica:

LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta. 3. ed. Porto Alegre: Bookman, 2013. xi, 471p. (Coleção Schaum). ISBN 9788565837736.