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 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 é: 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: 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.
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:
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 ⟶ {\displaystyle \longrightarrow } A pode ser representada como um grafo com arestas ligando cada par ordenado (a,b) com origem em a destino em b. Assim: 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
ou seja, P = {(2,0), (1, 1), (0, 2)}, P(0,2) é verdadeiro, já P(-1,3) é falso;
Dada uma relação R ⊆ A×B, podemos classificá-la como: Ou seja, todo elemento de A se relaciona com algum de B. É o inverso da total, todo elemento de B é relacionado com algum de A. Ou seja, um elemento de A não pode se relacionar com mais de um elemento de B. 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”.
Relações inversas
Seja R uma relação qualquer A×B. A inversa de R, denotada por R−1, é a relação de B×A consiste nos pares ordenados que, quando têm sua ordem revertida, pertencem a R, isto é, Por exemplo, a inversa da relação R = {(1, y), (1, z), (3, y)} é a seguinte: R−1 = {(y, 1), (z, 1), (y, 3)}. Claramente, (R−1)−1 = R. Além disso o domínio e a imagem de R−1 são, respectivamente, iguais à imagem e ao domínio de R. Ademais, se R é uma relação em A, então R−1 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 ⟶ {\displaystyle \longrightarrow } B e S: B ⟶ {\displaystyle \longrightarrow } C, a composição de R e S (que pode ser denotada por R ∘ {\displaystyle \circ } S: A ⟶ {\displaystyle \longrightarrow } C) será tal que ( ∀ {\displaystyle \forall } a ∈ {\displaystyle \in } A)( ∀ {\displaystyle \forall } b ∈ {\displaystyle \in } B)( ∀ {\displaystyle \forall } c ∈ {\displaystyle \in } C)[aRb ∧ {\displaystyle \land } bSc ⟶ {\displaystyle \longrightarrow } a(R ∘ {\displaystyle \circ } S)c]. Ou seja, composição de R e S será um conjunto R ∘ {\displaystyle \circ } S tal que os pares ordenados de R ∘ {\displaystyle \circ } S serão pares (a,c) desde que a esteja relacionado com b e b esteja relacionado com c.
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}:
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. 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 R2 e a relação universal R5 são reflexivas. Note que R1 , R3 e R4 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 2n² relações binárias, das quais 2n²-n são reflexivas.
Simetria
Uma relação binária é simétrica se a relação de a com b implica a relação de b com a. 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 n 2 + n 2 {\displaystyle 2^{\frac {n^{2}+n}{2}}} relações simétricas. R1 não é simétrica já que (1,2) ∈ R1 mas (2,1) ∉ R1. R3 não é simétrica já que (1,3) ∈ R3 mas (3,1) ∉ R3 . As outras relações são simétricas. Uma relação anti-simétrica é tal que se aRb e bRa então a=b. R2 não é anti-simétrica, já que (1,2) e (2,1) pertencem a R2 , mas 1 ≠ 2. Assimétrica é uma relação em que aRb implica que não bRa.
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 R3 não é transitiva porque (2,1) e (1,3) ∈ R3, mas (2,3) ∉ R3 . 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, Rn = Rn-1⋅R, para n inteiro maior do que 1. Teorema: a relação R é transitiva se e somente se , Rn ⊆ R para n ≥ 1.
Algumas outras propriedades
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).
