Relação binária

Na matemática e na lógica, uma relação binária ou 2-ária é uma relação entre dois elementos, sendo um conjunto de pares ordenados. As relações binárias são comuns em muitas áreas da matemática para definir conceitos como, por exemplo: "é múltiplo" e "maior que" da aritmética; "é congruente" da geometria; e outros.

uma Função (matemática) é um tipo especial de relação binária^[1].

As relações binárias são utilizadas em vários campos da Matemática e na Ciência da computação.

Definição

Uma relação binária é uma comparação entre dois objetos tomados em uma ordem definida. Os objetos podem estar ou não relacionados de acordo com alguma regra. Toda relação é um conjunto de pares ordenados onde o primeiro elemento pertence ao conjunto de partida, e o segundo elemento pertence ao conjunto de chegada.

Uma relação binária r sobre dois conjuntos A e B é:

r\subseteq A\times B

Em outras palavras, uma relação binária é definida como sendo um subconjunto do produto cartesiano entre os conjuntos A e conjunto B. Isto é, uma relação R é um conjunto de pares ordenados. Um subconjunto de A x A pode ser chamado simplesmente de relação binária em A.

Suponha que R é uma relação de A para B. Então R é um conjunto de pares ordenados onde cada primeiro elemento pertence a A e cada segundo elemento pertence a B. Isto é, para cada par (a,b), a ∈ A e b ∈ B. Então uma das seguintes afirmativas é verdadeira:

(a,b) ∈ R: dizemos que “a é R-relacionado a b”, escrevendo aRb.
(a,b) ∈ R: dizemos que “a não é R-relacionado a b”, escrevendo aRb.

O domínio de uma relação R é o conjunto de todos os primeiros elementos de um par ordenado que pertence a R. A imagem de R é o conjunto dos segundos elementos. No caso descrito acima, o domínio é um subconjunto de A e a imagem é um subconjunto de B.

Exemplos:

Sejam A = {1, 2, 3} e B = { x, y, z} , e seja R = {(1,y), (1,z), (3,y)}. Então R é uma relação de A para B, uma vez que R é um subconjunto de A x B. Com respeito a esta relação, 1Ry, 1Rz, 3Ry, mas 1Rx, 2Rx, 2Ry, 2Rz, 3Rx, 3Rz. O domínio de R é {1,3} e a imagem é {y,z}.
Seja A um conjunto qualquer. Uma relação importante em A é a relação de igualdade, {(a,a); a ∈ A}, que é usualmente denotada por =. Essa relação é também chamada de identidade ou relação diagonal em A e será também denotado por δ.

Endorrelação

Se R é uma relação de um conjunto A para si mesmo, do tipo R : A → A, então dizemos que R é uma “endorrelação” ou “auto-relação”. Considerando o mesmo conjunto A e a mesma relação R : A → A, podemos escrever a endorrelação como ⟨A, R⟩, sendo esta outra forma de notação.

Podemos tomar como exemplos de endorrelações, as relações abaixo:

Se A = {0, 1, 2}, a relação “menor que” de A em A será R = {(0, 1), (0, 2), (1, 2)}.
Se B = {1, 2}, a relação R = {(x,y) $\in$ B $\times$ B | x + y = ímpar} será R = {(1, 2), (2, 1)}.
Se C = {a, b}, a relação ⟨C, =⟩ será um conjunto R = {(a, a), (b, b)}.
Se D = {1, 2, 3}, a relação $\geq :$ D $\longrightarrow$ D será um conjunto R = {(1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)}.

Grafos

O grafo é um ramo importante da matemática discreta (ver Teoria dos grafos). Podemos observar os grafos de maneira clara a partir de endorrelações. Dessa maneira, toda relação R: A $\longrightarrow$ A pode ser representada como um grafo com arestas ligando cada par ordenado (a,b) com origem em a destino em b. Assim:

Cada elemento do conjunto A é representado por um vértice do grafo.
Cada par ordenado (a,b) no grafo é representado por uma aresta (setas) de a para b.

Tomemos como exemplo o primeiro exemplo dado em endorrelações. Se A = {0, 1, 2}, a relação “menor que” de A em A será R = {(0, 1), (0, 2), (1, 2)}. Logo, teremos um grafo configurado da seguinte maneira (ver figura 1).

Outra definição

Uma relação binária R também pode ser definida como um trio ordenado (A, B, G) onde A e B são conjuntos arbitrários, e G é um subconjunto do produto cartesiano A×B. Os conjuntos A e B são chamados de domínio e codomínio da relação, respectivamente, e G é chamado de grafo.

A Relação final corresponde a visualizar R como uma Função indicadora do conjunto de pares G. A ordem de cada par de G é importante: se a ? b, então aRb pode ser verdadeiro ou falso independentemente de bRa o ser.

Exemplos

Numa relação P definida por:

P=\lbrace (a,b)\in \mathbb {N} ^{2}:a+b=2\rbrace

ou seja, P = {(2,0), (1, 1), (0, 2)}, P(0,2) é verdadeiro, já P(-1,3) é falso;

As relações de igualdade e diferença: a = a e b ? c;
Suponha que existam 4 objetos: {carro, bola, boneca, bala} e quatro pessoas {João, Maria, Marcos, Pedro}.

Suponha que João tem a bola, Maria tem a boneca, e Pedro tem o carro. Ninguém tem a bala e Marcos não tem nada.

Então a relação binária R "pertence a" é dada como R = ({bola, carro, boneca, bala}, {João, Maria, Marcos, Pedro}, {(bola, João), (boneca, Maria), (carro, Pedro)}).

Tipos de relações binárias

Dada uma relação R ⊆ A×B, podemos classificá-la como:

Relação total

(\forall a\in A)\;(\exists b\in B),\;aRb

Ou seja, todo elemento de A se relaciona com algum de B.

Relação sobrejetora

(\forall b\in B)\;(\exists a\in A),\;aRb

É o inverso da total, todo elemento de B é relacionado com algum de A.

Relação funcional

(\forall a\in A)\;(\forall b_{1},\;b_{2}\;\in \;B),\;aRb_{1}\;\land aRb_{2}\to \;(b_{1}=b_{2})

Ou seja, um elemento de A não pode se relacionar com mais de um elemento de B.

Relação injetora:

$(\forall a_{1},\;a_{2}\in A)\;(\forall b\in B),\;a_{1}Rb\land a_{2}Rb\to (a_{1}=a_{2})$

O contrário da funcional: um elemento de B não pode ser relacionado com dois ou mais elementos de A diferentes.

Uma relação é dita um monomorfismo se ela é total e injetora. Uma relação é dita um epimorfismo se ela é funcional e sobrejetora. Uma relação é dita um isomorfismo se ela é um monomorfismo e um epimorfismo.

Se existir um isomorfismo entre dois conjuntos, podemos chamá-los de “conjuntos isomorfos”.

Operações em relações binárias

Relações inversas

Seja R uma relação qualquer A×B. A inversa de R, denotada por R⁻¹, é a relação de B×A consiste nos pares ordenados que, quando têm sua ordem revertida, pertencem a R, isto é,

R^{-1}=\{(b,a):(a,b)\in R\}

Por exemplo, a inversa da relação R = {(1, y), (1, z), (3, y)} é a seguinte: R⁻¹ = {(y, 1), (z, 1), (y, 3)}.

Claramente, (R⁻¹)⁻¹ = R. Além disso o domínio e a imagem de R⁻¹ são, respectivamente, iguais à imagem e ao domínio de R. Ademais, se R é uma relação em A, então R⁻¹ também é uma relação em A.

Composição de relações

Se considerarmos A, B e C conjuntos e as relações R: A $\longrightarrow$ B e S: B $\longrightarrow$ C, a composição de R e S (que pode ser denotada por R $\circ$ S: A $\longrightarrow$ C) será tal que ( $\forall$ a $\in$ A)( $\forall$ b $\in$ B)( $\forall$ c $\in$ C)[aRb $\land$ bSc $\longrightarrow$ a(R $\circ$ S)c]. Ou seja, composição de R e S será um conjunto R $\circ$ S tal que os pares ordenados de R $\circ$ S serão pares (a,c) desde que a esteja relacionado com b e b esteja relacionado com c.

A melhor maneira de observarmos uma composição de relações é através do diagrama de setas ou de matrizes.

Tomemos como exemplo os conjuntos A = {1,2,3,4}, B = {a,b,c,d} e C = {x, y, z} e as relações R = {(1, a), (2, d), (3, a), (3, b), (3, d)} de A para B e S = {(b, x), (b,z), (c, y), (d,z)} de B para C. A composição de R e S será, com o auxílio do diagrama de setas (ver figura 2) R $\circ$ S = {(3, x), (3,z), (2,z)}.

Matricialmente teremos a matriz de R como sendo $M_{R}$ = ${\begin{pmatrix}1&0&0&0\\0&0&0&1\\1&1&0&1\\0&0&0&0\end{pmatrix}}$ e a matriz de S como sendo $M_{S}$ = ${\begin{pmatrix}0&0&0\\1&0&1\\0&1&0\\0&0&1\end{pmatrix}}$ . A relação R $\circ$ S será a multiplicação entre as matrizes. Logo $M_{R}$ x $M_{S}$ = ${\begin{pmatrix}0&0&0\\0&0&1\\1&0&2\\0&0&0\end{pmatrix}}$

Propriedades das relações binárias

Dada uma relação binária R sobre um conjunto A.

Considere a serviço de exemplo as seguintes cinco relações em um conjunto A = { 1, 2, 3, 4}:

R₁ = {(1,1), (1,2), (2,3), (1,3), (4,4)};
R₂ = {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)};
R₃ = {(1,3), (2,1)};
R₄ = ∅, a relação vazia;
R₅ = A×A, a relação universal.

Reflexividade

A relação R é dita reflexiva se todos os elementos se relacionam com si próprios.

Uma relação é irreflexiva se nenhum elemento se relaciona com si próprio.

Exemplos:

A relação "ter o mesmo pai que" é reflexiva (pois todo mundo é filho de seu próprio pai).
A relação "ser irmão de" é irreflexiva (pois ninguém é irmão de si próprio).

Dos exemplos citados, como A contém os quatro elementos, 1, 2, 3 e 4, uma relação R em A é reflexiva se contém os quatro pares (1,1), (2.2), (3.3), (4,4). Portanto, apenas R₂ e a relação universal R₅ são reflexivas. Note que R₁ , R₃ e R₄ não são reflexivas, uma vez que, por exemplo, (2,2) não pertence a nenhuma delas.

Formalmente, a relação R é dita reflexiva se aRa para todo a ∈ A, isto é, se (a,a) ∈ R para todo a ∈ A.

Em um conjunto finito com n elementos existem 2^n² relações binárias, das quais 2^n²-n são reflexivas.

A matriz de uma relação reflexiva: a diagonal principal contém somente o valor verdadeiro (1). Grafo de uma relação reflexiva: em cada vértice do grafo deve haver um laço, Na matriz de uma relação irreflexiva a diagonal principal contém apenas o valor falso (0). Grafo de uma relação irreflexiva: em nenhum vértice do grafo pode haver um laço.

Simetria

Relação binária simétrica

Uma relação binária é simétrica se a relação de a com b implica a relação de b com a^[2].

Exemplo: A relação "a é irmão de b" é simétrica, pois, se a é irmão de b, então b é irmão de a.

Formalmente, uma relação binária é simétrica se qualquer aRb implica bRa. Em um conjunto finito com n elementos, há $2^{\frac {n^{2}+n}{2}}$ relações simétricas.

R₁ não é simétrica já que (1,2) ∈ R₁ mas (2,1) ∉ R₁. R₃ não é simétrica já que (1,3) ∈ R₃ mas (3,1) ∉ R₃ . As outras relações são simétricas.

Matriz de uma relação simétrica: a matriz é simétrica (MR = MT R ). Grafo de uma relação simétrica: entre dois vértices quaisquer, ou não existe aresta, ou existem duas arestas, uma em cada sentido

Relação binária anti-simétrica

Uma relação anti-simétrica é tal que se aRb e bRa então a=b.

R₂ não é anti-simétrica, já que (1,2) e (2,1) pertencem a R₂ , mas 1 ≠ 2.

A matriz de uma relação anti-simétrica para qualquer célula verdadeira (1) em uma das metades da matriz, em relação à diagonal, a correspondente célula na outra metade é falsa (0). Grafo de uma relação anti-simétrica: entre dois vértices quaisquer, não há arestas nos dois sentidos.

Relação binária assimétrica

Assimétrica é uma relação em que aRb implica que não bRa.

Analogamente, a relação universal R₅ não é anti-simétrica. Todas as outras são anti-simétricas.

Note que as propriedades de simetria e anti-simetria não são mutuamente excludentes. Por exemplo, a relação R = {(1,3), (3,1), (2,3)} não é nem simétrica nem anti-simétrica. Por outro lado, a relação R' = {(1,1), (2,2)} é simétrica e anti-simétrica.
Uma relação R que é simétrica e anti-simétrica ao mesmo tempo tem a propriedade que se xRy então x = y. Em um conjunto finito com n elementos existem apenas $2^{n}$ dessa relação.

Transitividade

Em uma relação transitiva, se a implica b, e b implica c, então a implica c.

Exemplo: Se a é irmão de b, e b é irmão de c, então a é irmão de c.

Formalmente, uma relação é dita transitiva se aRb e bRc implicam aRc. Se a relação for antitransitiva então aRb e bRc implicam que não é verdade aRc.

A relação R₃ não é transitiva porque (2,1) e (1,3) ∈ R₃, mas (2,3) ∉ R₃ . Todas as outras relações são transitivas.

A propriedade de transitividade também pode ser expressa em termos da composição de relações. Para uma relação R em A, definimos R² = R⋅R e, mais geralmente, Rⁿ = R^n-1⋅R, para n inteiro maior do que 1.

Teorema: a relação R é transitiva se e somente se , Rⁿ ⊆ R para n ≥ 1.

Uma matriz de uma relação transitiva: matricialmente não se verifica nenhuma estrutura específica. Grafo de uma relação transitiva: sempre que uma aresta ligar um vértice A a um vértice B e o vértice B a um vértice C, então deve haver uma aresta de A para C.

Algumas outras propriedades

Relação total (ou linear, ou completa^[3]): para todo a e b em A é verdade que aRb ou bRa (ou ambos).
Relação euclidiana: para todo a, b e c em A, é verdade que se aRb e aRc então bRc.
Relação extensível (ou serial): para todo a em A, existe um b em A tal que aRb ou bRa. "Maior que” é uma relação extensível nos inteiros. Mas não é um relação extensível nos inteiros positivos, porque não existe um x nos inteiros positivos tal que 1>x.

Uma relação que é simétrica, transitiva e extensível é também reflexiva, consequentemente, também é uma relação de equivalência. Uma relação que é reflexiva, anti-simétrica e transitiva é chamada de ordem parcial. Uma ordem parcial que é total é chamada de relação de ordem total ou uma ordem linear ou uma chain. Uma ordem linear na qual todo conjunto não vazio tem um menor elemento é chamada bem ordenada.

Para que a relação inversa de uma função parcial seja também uma função parcial (relação funcional), ela deve ser uma função parcial injetora(cada elemento do conjunto de chegada está relacionado com, no máximo, um elemento do conjunto de partida), Para que a relação inversa de uma função seja também uma função (relação funcional e total), ela deve ser uma função bijetora (injetora(cada elemento do conjunto de chegada está relacionado com, no máximo, um elemento do conjunto de partida) + sobrejetora( todos os elementos do conjunto de chegada (imagem) devem estar relacionados a pelo menos um elemento do conjunto de partida (domínio).

Exemplo:

Seja Z* o conjunto dos inteiros não nulos e seja ≡ a relação em Z*×Z* definida por (a,b)≡(c,d) sempre que ad = bc. Demonstra-se que ≡ é uma relação de equivalência:

Reflexividade: temos (a,b)≡(a,b), já que ab = ba. Portanto, ≡ é reflexiva.
Simetria: temos (a,b)≡(c,d). Então ad = bc. Por conseguinte, cb = da e, portanto, (c,d)≡(a,b). Assim, ≡ é simétrica.
Transitividade: suponha (a,b)≡(c,d) e (c,d)≡(e,f). Então, ad = bc e cf = de. A multiplicação dos termos correspondentes da equação leva a (ad)(cf) = (bc)(de). Cancelando c ≠ 0 e d ≠ 0 dos dois lados da equação, obtém-se af = be, e portanto (a,b)≡(e,f). Logo, ≡ é transitiva.

Consequentemente, ≡ é uma relação de equivalência.

Obs.: Do ponto de vista gráfico, uma relação é reflexiva se para todo vértice existir uma aresta ligando-o a ele mesmo. A estas arestas dá-se o nome de lacetes. A relação será simétrica se sempre que ao existir uma aresta de a para b também exista uma aresta de b para a e será transitiva sempre que ao existir uma aresta da a para b e outra de b para c, também exista uma aresta de a para c.

Referências

↑ Nykamp DQ. «Relation definition». Math Insight. Consultado em 16 de agosto de 2020
↑ «Binary relations» (PDF). Stanford University. Consultado em 16 de agosto de 2020
↑ Walker, Mark. «Binary reflexions» (PDF). University of Arizona. Consultado em 16 de agosto de 2020

Bibliografia

SCHEINERMAN, Edward R. Matemática Discreta - Uma Introdução. São Paulo: Thomson, 2003. ISBN 8522102910.
LIPSCHUTZ, Seymour; LIPSON, Marc. Teorias e Problemas de Matemática Discreta, 2ª edição. São Paulo: Bookman, 2004. ISBN 0070380457.
Matemática Discreta(arquivo em pdf), por Márcia Rodrigues Notare.
Relação(arquivo em pdf), por Leonardo Dagnino Chiwiacowsky.

Ver também

[1] Nykamp DQ. «Relation definition». Math Insight. Consultado em 16 de agosto de 2020

[2] «Binary relations» (PDF). Stanford University. Consultado em 16 de agosto de 2020

[3] Walker, Mark. «Binary reflexions» (PDF). University of Arizona. Consultado em 16 de agosto de 2020

[1]

[2]

[3]