Relación binaria

Unha relación binaria R é o subconxunto dos elementos do produto cartesiano ${\displaystyle A_{1}\times A_{2}\ }$que cumpren a condición:

${\displaystyle R=\{(a_{1},a_{2}):\;(a_{1},a_{2})\in A_{1}\times A_{2}\;\land \;R(a_{1},a_{2})=Verdadeiro\}}$

Relacións binarias transitivas v c e
Simétrica Antisimétrica Conexa Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica Relación de equivalencia  Si  Non  Non  Non  Non  Non  Si  Non  Non Preorde (Cuasiorde)  Non  Non  Non  Non  Non  Non  Si  Non  Non Orde parcial  Non  Si  Non  Non  Non  Non  Si  Non  Non Preorde total  Non  Non  Si  Non  Non  Non  Si  Non  Non Orde total  Non  Si  Si  Non  Non  Non  Si  Non  Non Pre-Ben ordenada  Non  Non  Si  Si  Non  Non  Si  Non  Non Cuasi-Ben ordenada  Non  Non  Non  Si  Non  Non  Si  Non  Non Ben ordenada  Non  Si  Si  Si  Non  Non  Si  Non  Non Retícula  Non  Si  Non  Non  Si  Si  Si  Non  Non Semiretícula superior (join)  Non  Si  Non  Non  Si  Non  Si  Non  Non Semiretícula inferior (meet)  Non  Si  Non  Non  Non  Si  Si  Non  Non Orde estrita parcial  Non  Si  Non  Non  Non  Non  Non  Si  Si Orde estrita feble  Non  Si  Non  Non  Non  Non  Non  Si  Si Orde estrita total  Non  Si  Si  Non  Non  Non  Non  Si  Si Simétrica Antisimétrica Conexa Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica Definicións, para todo ${\displaystyle a,b}$ e ${\displaystyle S\neq \varnothing$ :} ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ e }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ ou }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{non }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{non }}bRa\end{aligned}}}$
Si indica que a columna da propiedade é sempre verdadeira no termo da fila (na esquerda de todo), mentres que  Non indica que a propiedade non está garantida en xeral (pode cumprirse ou non). Por exemplo, toda relación de equivalencia é simétrica, mais non necesariamente antisimétrica, está indicada por  Si na columna "Simétrica" e  Non na columna "Antisimétrica". Todas as definicións requiren tacitamente que a relación homoxénea ${\displaystyle R}$ sexa transitiva: para todo ${\displaystyle a,b,c,}$ se ${\displaystyle aRb}$ e ${\displaystyle bRc}$ entón ${\displaystyle aRc.}$ Algunha definición dalgún termo pode requerir propiedades adicionais non recollidas na táboa.

Clasificación das relacións binarias

borde

No esquema pódese ver algunhas estruturas alxébricas ou subtipos de relación binaria. Empregaremos este esquema para ver estes casos.

En primeiro lugar diferenciamos as relacións binarias homoxéneas, das heteroxéneas. Nas primeiras, a relación binaria establécese entre os elementos dun único conxunto, mentres que nas segundas establécense relacións entre dous conxuntos distintos. Unha relación homoxénea pode ser tratada como heteroxénea cos mesmos subtipos, mais non ao contrario.

Relación homoxénea

Unha relación binaria R é homoxénea se os dous conxuntos implicados son o mesmo:

${\displaystyle R(a_{1},a_{2}):\;(a_{1},a_{2})\in A_{1}\times A_{2}\land A_{1}=A_{2}}$

Dado que ${\displaystyle A_{1}}$ e ${\displaystyle A_{2}}$ son o mesmo conxunto, pode representarse como:

${\displaystyle R(a_{1},a_{2}):\;(a_{1},a_{2})\in A\times A}$ ou tamén como

${\displaystyle R(a_{1},a_{2}):\;(a_{1},a_{2})\in A^{2}}$

Relación heteroxénea

Unha relación binaria R é heteroxénea se os dous conxuntos implicados non son iguais:

${\displaystyle R(a_{1},a_{2}):(a_{1},a_{2})\in A_{1}\times A_{2}\land A_{1}\neq A_{2}}$

Conceptos previos

Par ordenado

Se temos os conxuntos ${\displaystyle A_{1}}$ e ${\displaystyle A_{2}}$ descríbese o par ordenado ${\displaystyle (a_{1},a_{2})}$ que cumpre ${\displaystyle a_{1}\in A_{1}}$ e ${\displaystyle a_{2}\in A_{2}}$.

Represéntase como:

${\displaystyle A_{1}\times A_{2}=\{(a_{1},a_{2})\;:a_{1}\in A_{1}\land a_{2}\in A_{2}\}}$

Produto cartesiano

${\displaystyle {\begin{array}{|r|ccc|}\hline a&(1,a)&(2,a)&(3,a)\\b&(1,b)&(2,b)&(3,b)\\c&(1,c)&(2,c)&(3,c)\\\hline A_{1}\times A_{2}&1&2&3\\\hline \end{array}}}$

Definidos os conxuntos:

${\displaystyle A_{1}=\{1,2,3\}}$

${\displaystyle A_{2}=\{a,b,c\}}$

O produto cartesiano ${\displaystyle A_{1}\times A_{2}}$ descríbese na táboa anterior.

A relación binaria ${\displaystyle R(a_{1},a_{2})}$ fica definida como

${\displaystyle A_{1}\times A_{2}=\{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)\}.}$

Operacións con relacións binarias

Unión

Se R e S son relacións binarias sobre os conxuntos X e Y, entón ${\displaystyle R\cup S=\{(x,y):xRy{\text{ ou }}xSy\}}$ é a relación de unión de R e S sobre X e Y.

Por exemplo, ${\displaystyle \,\leq \,}$ é a unión de < e =.

Intersección

Se R e S son relacións binarias sobre os conxuntos X e Y entón ${\displaystyle R\cap S=\{(x,y):xRy{\text{ e }}xSy\}}$ é a relación de intersección de R e S sobre X e Y.

Por exemplo, a relación "é divisible por 6" é a intersección das relacións "é divisible por 3" e "é divisible por 2".

Composición

Se R é unha relación binaria sobre os conxuntos X e Y, e S é unha relación binaria sobre os conxuntos Y e Z entón ${\displaystyle S\circ R=\{(x,z):{\text{ existe }}y\in Y{\text{ tal que }}xRy{\text{ e }}ySz\}}$ (tamén denotado como R; S) é a relación de composición de R e S sobre X e Z.

A orde de R e S na notación ${\displaystyle S\circ R,}$ usada aquí concorda coa orde de notación estándar para composición de funcións. Por exemplo, a composición (é o pai de)${\displaystyle \,\circ \,}$(é a nai de) produce (é o avó materno de).

Inversa

Se R é unha relación binaria sobre os conxuntos X e Y, entón ${\displaystyle R^{\textsf {T}}=\{(y,x):xRy\}}$ é a relación inversa,^{[1] [2]} de R sobre Y e X. Tamén se pode representar como ${\displaystyle R^{-1}}$.

Por exemplo, ${\displaystyle \,=\,}$ é a inversa de si mesmo, e ${\displaystyle \,<\,}$ e ${\displaystyle \,>\,}$ son o inverso do outro.

Complementario

Se R é unha relación binaria sobre os conxuntos X e Y entón ${\displaystyle {\bar {R}}=\{(x,y):{\text{ non }}xRy\}}$ (tamén denotada por R ou ¬ R) é a relación complementaria de R sobre X e Y.

Por exemplo, ${\displaystyle \,=\,}$ e ${\displaystyle \,\neq \,}$ son complementarios mutuos.

O complemento da relación inversa ${\displaystyle R^{\textsf {T}}}$ é a inversa do complemento: ${\displaystyle {\overline {R^{\mathsf {T}}}}={\bar {R}}^{\mathsf {T}}.}$

Restrición

Se R é unha relación homoxénea binaria sobre un conxunto X e S é un subconxunto de X entón ${\displaystyle R_{\vert S}=\{(x,y)\mid xRy{\text{ e }}x\in S{\text{ e }}y\in S\}}$ é a relación de restrición de R a S sobre X.

Relación binaria homoxénea

Unha relación binaria estabelécese entre os elementos dun único conxunto.

Exemplo

Se temos un único conxunto ${\displaystyle A=\{a,b,c,d\}}$, podemos definir unha relación binaria R como un conxunto de pares ordenados:

${\displaystyle R\subset A^{2}}$ ou ${\displaystyle R:A\rightarrow A}$,

${\displaystyle R=\{(a,b),(b,a),(b,c),(c,d),(d,b),(d,d)\}.}$

Se o elemento inicial está relacionado co elemento final, non implica necesariamente que haxa unha relación desde o elemento final ata o elemento inicial. Por iso é importante que sexan pares ordenados.

Imos representar agora esa mesma relación binaria como un subconxunto do produto cartesiano:

d	(a, d)	(b, d)	(c, d)	(d, d)
c	(a, c)	(b, c)	(c, c)	(d, c)
b	(a, b)	(b, b)	(c, b)	(d, b)
a	(a, a)	(b, a)	(c, a)	(d, a)
A×A	a	b	c	d

O subconxunto R da relación binaria son os pares en letra grosa e o podemos representar tamén como:

${\displaystyle R=\{(a,b),(b,c),(b,a),(c,d),(d,b),(d,d)\}\,}$

Propiedades da relación binaria homoxénea

Propiedade reflexiva

Artigo principal: Relación reflexiva.

Dicimos que unha relación ten a propiedade reflexiva, se todo elemento está relacionado consigo mesmo.

Isto é, para todo elemento e pertencente ao conxunto A, o par ordenado (e,e) pertence á relación binaria R.

Propiedade antirreflexiva

Unha relación binaria ten a propiedade antirreflexiva, ou irreflexiva, se ningún elemento do conxunto está relacionado consigo mesmo:

${\displaystyle \forall a\in A:\;(a,a)\notin R}$

isto é, non existe ningún elemento a no conxunto A que cumpra que: (a,a) pertence a R.

Propiedade simétrica

Artigo principal: Relación simétrica.

Dicimos que unha relación binaria ten a propiedade simétrica cando se se cumpre que un par ordenado (a,b) pertence á relación entón o par (b,a) tamén pertence a esa relación:

${\displaystyle \forall a,b\in A:\;(a,b)\in R\quad \longrightarrow \quad (b,a)\in R}$

Propiedade antisimétrica

Dise que unha relación binaria ten a propiedade antisimétrica se os pares ordenados (a,b) e (b,a) pertencen á relación, entón a = b: ${\displaystyle \forall a,b\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,a)\in R{\Big )}\quad \longrightarrow \quad a=b}$

Isto é, non hai ningún par de elementos distintos relacionados entre si en ambos os sentidos.

Propiedade transitiva

Artigo principal: Relación transitiva.

Unha relación binaria ten a propiedade transitiva cando, dados os elementos a, b, c do conxunto, se a está relacionado con b e b está relacionado con c, entón a está relacionado con c:

${\displaystyle \forall a,b,c\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,c)\in R{\Big )}\longrightarrow \quad (a,c)\in R}$

Propiedade intransitiva

Unha relación binaria ten a propiedade intransitiva cando, dados os elementos a, b, c do conxunto, se a está relacionado con b e b está relacionado con c, entón a non está relacionado con c:

${\displaystyle \forall a,b,c\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,c)\in R{\Big )}\quad \longrightarrow \quad (a,c)\notin R}$

Propiedade total

Artigo principal: Relación conexa.

Dicimos que unha relación binaria é total: se para todo elemento do conxunto: a, b; ou a está relacionado con b ou b está relacionado con a, isto é, o grafo da relación é conexo:

${\displaystyle \forall a,b\in A:\;(a,b)\in R\quad \lor \quad (b,a)\in R}$

Relacións homoxéneas particulares

Algunhas relacións homoxéneas particulares sobre un conxunto X (con elementos arbitrarios x₁, x₂) son:

• Relación baleira

  E = ∅;
  isto é, x₁E x₂ non acontece nunca;

• Relación universal

  U = X × X;
  isto é, x₁U x₂ sempre acontece (están relacionados todos con todos);

• Relación identidade (ver tamén Función identidade)

  I = {(x, x) | x ∈ X};
  isto é, x₁I x₂ cúmprese se e só se x₁ = x₂.

Clases das relacións binarias homoxéneas

Relación reflexiva

As relacións reflexivas son as definidas do seguinte modo:

Dado un conxunto A, e unha relación binaria R entre os sus elementos: ${\displaystyle R=\{(a,b)\in \;A^{2}:\quad R(a,b)\}}$ Dise que R é unha relación reflexiva, se cumpre: 1.- A propiedade reflexiva: ${\displaystyle \forall a\in A:\;(a,a)\in R}$ Todo elemento a de A está relacionado consigo mesmo.

O caso máis claro de propiedade reflexiva é o de igualdade matemática.

Vemos un exemplo:

Temos un conxunto A, formado polos seguintes elementos:

${\displaystyle A=\{a,b,c,d\}\,}$

E temos unha relación R entre os elementos do conxunto, definida así:

${\displaystyle \mathbb {R} ={\Big \{}(a,a),(a,b),(b,b),(b,c),(c,c),(d,b),(d,d){\Big \}}}$

Pódese ver que os pares ordenados que teñen os seus dous termos iguais pertencen á relación definida:

${\displaystyle \forall a,b\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,a)\in R{\Big )}\longrightarrow \quad a=b}$

Daquela a relación R é reflexiva.

Relación non reflexiva

Se non todos os elementos están relacionados consigo mesmos a relación é non reflexiva.

Temos dous tipos:

• Se algún elemento, mais non todos, é reflexivo a relación é arreflexiva
• Se ningún elemento é reflexivo a relación é antirreflexiva (ou irreflexiva)

Podemos ver que:

${\displaystyle (a,a)\notin R\quad (b,b)\notin R\quad (c,c)\notin R\quad (d,d)\notin R}$

Relación de dependencia

Unha relación binaria é unha relación de dependencia se é reflexiva e simétrica:

Dado un conxunto A, e unha relación binaria R entre os seus elementos: ${\displaystyle R=\{(a,b)\in \;A^{2}:\quad R(a,b)\}}$ Dise que R é unha relación de dependencia, se cumpre: 1.- A propiedade é reflexiva: ${\displaystyle \forall a\in A:\;(a,a)\in R}$ Todo elemento a de A está relacionado consigo mesmo. 2.- A propiedade é simétrica: ${\displaystyle \forall a,b\in A:\;(a,b)\in R\quad \longrightarrow \quad (b,a)\in R}$ Se un elemento a está relacionado con outro b, daquela o elemento b tamén está relacionado co elemento a.

Por exemplo se temos o conxunto dos números naturais, e definimos a distáncia D entre dous números, como o valor absoluto da súa diferenza.

${\displaystyle \forall a,b\in \mathbb {N} :D=|a-b|}$,

e dicimos que dous números están próximos se

${\displaystyle \forall a\in \mathbb {N}$ :\;|a-b|\leq D}

Daquela para a relación de proximidade dentro dos números naturais é unha relación de dependencia, posto que:

1. Cúmprese a propiedade reflexiva posto que:

${\displaystyle \forall a\in \mathbb {N}$ :\;|a-a|\leq D}

2. Cúmprese a propiedade simétrica:

${\displaystyle \forall a,b\in \mathbb {Z}$ :\;|a-b|\leq D\longrightarrow \quad |b-ba|\leq D}

3. Non se cumpre a propiedade transitiva, dado que:

${\displaystyle \forall a,b,c\in \mathbb {N}$ :\;{\Big (}|a-b|\leq D\quad \land \quad |b-c|\leq D{\Big )}\quad \nrightarrow \quad |a-c|\leq D}

que a distancia entre a e b sexa como máximo D e que a distancia entre b e c non supere D, non implica necesariamente que a distancia entre a e c non sexa maior que D.

Esta relación de dependencia entre os números pola súa distancia non é unha clase de equivalencia, como se verá máis adiante.

Conxunto preordenado

Artigo principal: Preorde.

Unha relación binaria define un conxunto preordenado se é reflexiva e transitiva.

Dado un conxunto A, e unha relación binaria R entre os seus elementos: ${\displaystyle R=\{(a,b)\in \;A^{2}:\quad R(a,b)\}}$ Dise que R define un conxunto preordenado, se cumpre: 1.- A propiedade reflexiva: ${\displaystyle \forall a\in A:\;(a,a)\in R}$ Todo elemento a de A está relacionado consigo mesmo. 2.- A propiedad transitiva: ${\displaystyle \forall a,b,c\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,c)\in R{\Big )}\longrightarrow \quad (a,c)\in R}$ Se un elemento a está relacionado con outro b, e este b con outro c, daquela o elemento a esta tamén relacionado co elemento c.

Relación de equivalencia

Artigo principal: Relación de equivalencia.

Unha relación binaria é unha relación de equivalencia se é reflexiva, simétrica e transitiva:^[3]

Dado un conxunto A, e unha relación binaria R entre os seus elementos: ${\displaystyle R=\{(a,b)\in \;A^{2}:\quad R(a,b)\}}$ Dise que R é unha relación de equivalencia, se cumpre: 1.- A propiedade reflexiva: ${\displaystyle \forall a\in A:\;(a,a)\in R}$ Todo elemento a de A está relacionado consigo mesmo. 2.- A propiedade simétrica: ${\displaystyle \forall a,b\in A:\;(a,b)\in R\longrightarrow \quad (b,a)\in R}$ Se un elemento a está relacionado con outro b, daquela o elemento b tamén está relacionado co elemento a. 3.- A propiedade transitiva: ${\displaystyle \forall a,b,c\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,c)\in R{\Big )}\longrightarrow \quad (a,c)\in R}$ Se un elemento a está relacionado con outro b, e este b con outro c, daquela o elemento a está tamén relacionado co elemento c.

Unha relación de equivalencia define dentro do conxunto A o que se denominan, clases de equivalencia, unha clase de equivalencia é cada un dos subconxuntos nos que a relación de equivalencia divide ao conxunto A, entre eles son disxuntos, e a unión de todos eles é o conxunto A, vexamos un exemplo.

A congruencia módulo n dos números naturais (residuo da división enteira entre n), vemos que é unha relación de equivalencia. Por exemplo,

${\displaystyle 14\equiv 4{\pmod {5}}}$,

${\displaystyle 19\equiv 24{\pmod {5}}}$,

${\displaystyle 14\equiv 24{\pmod {5}}}$.

Formalizamos as condicións:

é reflexiva:

${\displaystyle \forall a\in \mathbb {N}$ :\;a\equiv a{\pmod {n}}}

é simétrica:

${\displaystyle \forall a,b\in \mathbb {N}$ :\;a\equiv b{\pmod {n}}\longrightarrow b\equiv a{\pmod {n}}}

é transitiva

${\displaystyle \forall a,b,c\in \mathbb {N}$ :\;{\Big (}a\equiv b{\pmod {n}}\land b\equiv c{\pmod {n}}{\Big )}\longrightarrow \quad a\equiv c{\pmod {n}}}

Conxunto parcialmente ordenado

Artigo principal: Conxunto parcialmente ordenado.

Un conxunto A dise que está parcialmente ordenado respecto a unha relación binaria R se a relación R é reflexiva, transitiva e antisimétrica:

Dado un conxunto A, e unha relación binaria R entre os seus elementos: ${\displaystyle R=\{(a,b)\in \;A^{2}:\quad R(a,b)\}}$ Dise que R define un conxunto parcialmente ordenado, se cumpre: 1.- A propiedade reflexiva: ${\displaystyle \forall a\in A:\;(a,a)\in R}$ Todo elemento a de A está relacionado consigo mesmo. 2.- A propiedade transitiva: ${\displaystyle \forall a,b,c\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,c)\in R{\Big )}\longrightarrow \quad (a,c)\in R}$ Se un elemento a está relacionado con outro b, e este b con outro c, daquela o elemento a esta tamén relacionado co elemento c. 3.- A propiedade antisimétrica: ${\displaystyle \forall a,b\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,a)\in R{\Big )}\longrightarrow \quad a=b}$ Se os pares ordenados (a,b) e (b,a) pertencen .a relación R daquela a e b son iguais.

Tomando un conxunto A, formado, por exemplo, polos elementos:

${\displaystyle A=\{a,b,c\}\;}$

E o seu conxunto de partes

${\displaystyle P(A)={\Big \{}\{\},\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}{\Big \}}}$

Imos chamar a cada un destes subconxuntos:

${\displaystyle A_{1}=\{\}\;}$

${\displaystyle A_{2}=\{a\}\;}$

${\displaystyle A_{3}=\{b\}\;}$

${\displaystyle A_{4}=\{c\}\;}$

${\displaystyle A_{5}=\{a,b\}\;}$

${\displaystyle A_{6}=\{a,c\}\;}$

${\displaystyle A_{7}=\{b,c\}\;}$

${\displaystyle A_{8}=\{a,b,c\}\;}$

E tomando dous destes subconxuntos dicimos que están relacionados por pertenza se o primeiro é subconxunto do segundo:

${\displaystyle R={\Big \{}(A_{i},A_{j})\in \;P(A):\quad A_{i}\subseteq A_{j}{\Big \}}}$

A relación pertenza entre os conxuntos de partes de A, é un conxunto parcialmente ordenado, ao ser:

Reflexiva

${\displaystyle \forall A_{i}\in P(A):\;A_{i}\subseteq A_{i}}$

Transitiva:

${\displaystyle \forall A_{i},A_{j},A_{k}\in P(A):\;{\Big (}A_{i}\subseteq A_{j}\quad \land \quad A_{j}\subseteq A_{k}{\Big )}\longrightarrow \quad A_{i}\subseteq A_{k}}$

Antisimetrica:

${\displaystyle \forall A_{i},A_{j}\in P(A):\;{\Big (}A_{i}\subseteq A_{j}\quad \land \quad A_{j}\subseteq A_{i}{\Big )}\longrightarrow \quad A_{i}=A_{j}}$

Por tanto o conxunto de partes de A, respecto da relación binaria pertenza é un conxunto parcialmente ordenado.

Esta relación non é total dado que:

${\displaystyle \neg \forall (A_{i},A_{j})\in P(A):\;A_{i}\subseteq A_{j}\quad \lor \quad A_{j}\subseteq A_{i}}$

Que se denominan elementos ou pares non comparables. Os pares de conxuntos non comparables son:

${\displaystyle 1.\;{\Big (}\{a\},\{b\}{\Big )}\notin R\;:\quad \{a\}\nsubseteq \{b\}\;\land \;\{b\}\nsubseteq \{a\}}$

${\displaystyle 2.\;{\Big (}\{a\},\{c\}{\Big )}\notin R\;:\quad \{a\}\nsubseteq \{c\}\;\land \;\{c\}\nsubseteq \{a\}}$

${\displaystyle 3.\;{\Big (}\{b\},\{c\}{\Big )}\notin R\;:\quad \{b\}\nsubseteq \{c\}\;\land \;\{c\}\nsubseteq \{b\}}$

${\displaystyle 4.\;{\Big (}\{a\},\{b,c\}{\Big )}\notin R\;:\quad \{a\}\nsubseteq \{b,c\}\;\land \;\{b,c\}\nsubseteq \{a\}}$

${\displaystyle 5.\;{\Big (}\{b\},\{a,c\}{\Big )}\notin R\;:\quad \{b\}\nsubseteq \{a,c\}\;\land \;\{a,c\}\nsubseteq \{b\}}$

${\displaystyle 6.\;{\Big (}\{c\},\{a,b\}{\Big )}\notin R\;:\quad \{c\}\nsubseteq \{a,b\}\;\land \;\{a,b\}\nsubseteq \{c\}}$

${\displaystyle 7.\;{\Big (}\{a,b\},\{a,c\}{\Big )}\notin R\;:\quad \{a,b\}\nsubseteq \{a,c\}\;\land \;\{a,c\}\nsubseteq \{a,b\}}$

${\displaystyle 8.\;{\Big (}\{a,b\},\{b,c\}{\Big )}\notin R\;:\quad \{a,b\}\nsubseteq \{b,c\}\;\land \;\{b,c\}\nsubseteq \{a,b\}}$

${\displaystyle 9.\;{\Big (}\{a,c\},\{b,c\}{\Big )}\notin R\;:\quad \{a,c\}\nsubseteq \{b,c\}\;\land \;\{b,c\}\nsubseteq \{a,c\}}$

Vendo o diagrama, os conxuntos que se poden alcanzar seguindo o sentido das frechas denomínanse comparables e determinan a estrutura da orde parcial.

Conxunto limitado

Un conxunto de números reais está limitado se e só se ten un límite superior e outro inferior. Esta definición é extensible a subconxuntos de calquera conxunto parcialmente ordenado. Hai que ter en conta que este concepto máis xeral de dimensionamento non se corresponde cunha noción de tamaño. Hai distintos tipos de límites e os seus elementos relacionados en función do tipo de orde, parcial ou total:

• Elemento maior e menor 
• Ínfimo e supremo 
• Elemento maiorante e minorante
• Límite superior e límite inferior

Conxunto con orde total e limitado

Artigo principal: Orde total.

Se temos un conxunto A e unha relación binaria ${\displaystyle \precsim }$ definida entre os elementos de A, que expresaremos ${\displaystyle (A,\precsim )}$ e a relación represéntase:

${\displaystyle a\precsim b}$

Dicimos que se definiu unha orde total no conxunto A, se a relación ${\displaystyle (A,\precsim )}$ cumpre as propiedades:

1. Reflexiva.

2. Antisimétrica.

3. Transitiva.

4. É, ademais, unha relación total, é dicir, cúmprese que todos os elementos dun conxunto con orde total son comparables:

${\displaystyle \forall a,b\in A:\quad a\precsim b\quad \lor \quad b\precsim a}$

Dado un conxunto A no que se definiu unha relación binaria ${\displaystyle \precsim }$, sendo ${\displaystyle (A,\precsim )}$ un conxunto totalmente ordenado, o elemento y de A que cumpre:

${\displaystyle y\in A\;{\text{é maximo se:}}\quad \forall x\in A\;/\quad x\precsim y}$

Denomínase máximo e define un límite superior en A; o elemento máximo é único. Se o conxunto A e a relación binaria é unha orde total e ten máximo, entón é un conxunto con orde total e limitado superiormente.

Do mesmo xeito o elemento z de A que cumpre:

${\displaystyle z\in A\;{\text{é mínimo se:}}\quad \forall x\in A\;/\quad z\precsim x}$

Denomínase mínimo e define un límite inferior en A; o elemento mínimo é único. Se o conxunto A e a relación binaria é unha orde total e ten mínimo, entón é un conxunto con orde total e limitada inferiormente.

Un conxunto con orde total dicimos simplemente que é limitado, se está limitado superior e inferiormente.

Relación heteroxénea

Unha relación binaria entre dous conxuntos A e B, denomínase heteroxénea cando A é distinto de B:

${\displaystyle R(a,b):\;(a,b)\in A\times B\quad \land \quad A\neq B}$

• O conxunto A é o conxunto inicial (dominio).

• O conxunto B é o conxunto final (codominio).

• O subconxunto de A dos elementos a que forman parte dalgunha relación R (a,b) é o conxunto orixe.

• O subconxunto de B dos elementos b que forman parte dalgunha relación R (a,b) é o conxunto imaxe.

Conceptos previos

• A condición de existencia de imaxe garantiza que tomando un elemento calquera a de A ten polo menos unha imaxe b en B.

${\displaystyle \forall a\in A:\;\exists b\in B\quad \land \quad (a,b)\in R.}$

• A condición de existencia de orixe garantiza que todo elemento b de B ten polo menos unha orixe a en A.

${\displaystyle \forall b\in B:\;\exists a\in A\quad \land \quad (a,b)\in R.}$

• A condición de unicidade de imaxe garantiza que os elementos a de A que están relacionados con algún b de B están relacionados con un único elemento b de B, é dicir:

${\displaystyle {\Big (}(a,b_{1})\in R\quad \land \quad (a,b_{2})\in R{\Big )}\longrightarrow \quad b_{1}=b_{2}.}$

• A condición de unicidade de orixe di que os elementos b de B que están relacionados con algún a de A están relacionados só con un único elemento a de A, é dicir:

${\displaystyle {\Big (}(a_{1},b)\in R\quad \land \quad (a_{2},b)\in R{\Big )}\longrightarrow \quad a_{1}=a_{2}.}$

Tipos de relacións binarias heteroxéneas

Partindo das características das relacións binarias heteroxéneas, podemos diferenciar os seguintes casos.

Correspondencia unívoca

Unha correspondencia é unívoca se cumpre a condición de unicidade de imaxe:

Dada unha relación binarias heteroxénea R, entre os conxunto A e B: ${\displaystyle R:A\rightarrow B}$ Esta relación é unha correspondencia unívoca, se cumpre: 1.- Unicidade de imaxe ${\displaystyle {\Big (}(a,b_{1})\in R\quad \land \quad (a,b_{2})\in R{\Big )}\quad \longrightarrow \quad b_{1}=b_{2}.}$

Esta condición é necesaria e suficiente para que unha correspondencia sexa considerada unívoca.

Correspondencia biunívoca

Unha correspondencia é biunívoca se cumpre as condicións de unicidade de imaxe e unicidade de orixe:

Dada unha relación binaria heteroxénea R, entre os conxunto A e B: ${\displaystyle R:A\rightarrow B}$ Esta relación é unha correspondencia biunívoca, se cumpre: 1.- Unicidade de imaxe: ${\displaystyle {\Big (}(a,b_{1})\in R\quad \land \quad (a,b_{2})\in R{\Big )}\quad \longrightarrow \quad b_{1}=b_{2}.}$ 2.- Unicidade de orixe: ${\displaystyle {\Big (}(a_{1},b)\in R\quad \land \quad (a_{2},b)\in R{\Big )}\quad \longrightarrow \quad a_{1}=a_{2}.}$

Aplicación

Unha correspondencia ${\displaystyle R:A\to B}$ denomínase aplicación se todo elemento de A admite unha única imaxe en B., ^{[4] [5] [6]} isto é se cumpre a condición de unicidade de imaxe e de existencia de imaxe.

Unha aplicación f de A en B, sendo A e B dous conxuntos calquera, é unha correspondencia entre A e B, total e unívoca.^[7]

Se a aplicación representámola como R, teremos:

${\displaystyle {\begin{array}{rcl}R:\;A&\longrightarrow &B\\a&\longmapsto &b=R(a)\end{array}}}$

pola que definimos unha aplicación que a cada elemento a de A asígnaselle un único b de B.

${\displaystyle \forall a\in A\,:\quad \exists !b\in B\;/\quad b=R(a)}$

Para todo a de A, cúmprese que existe un único b de B, tal que b é o resultado R(a).

Dada unha relación binaria heteroxénea R, entre os conxuntos A e B: ${\displaystyle R:A\rightarrow B}$ Esta relación é unha aplicación, se cumpre: 1.- Unicidade de imaxe: ${\displaystyle {\Big (}(a,b_{1})\in R\quad \land \quad (a,b_{2})\in R{\Big )}\quad \longrightarrow \quad b_{1}=b_{2}.}$ 2.- Existencia de imaxe: ${\displaystyle \forall a\in A:\;\exists b\in B\quad \land \quad (a,b)\in R.}$

Se unha correspondencia cumpre estas dúas condicións denomínase aplicación.

Aplicación inxectiva

Artigo principal: inxectiva.

Unha correspondencia é unha aplicación inxectiva se cumpre a condición de unicidade de imaxe, existencia de imaxe e unicidade de orixe.

Dada unha relación binaria heteroxénea R, entre os conxuntos A e B: ${\displaystyle R:A\rightarrow B}$ Esta relación é unha aplicación inxectiva, se cumpre: 1.- Unicidade de imaxe: ${\displaystyle {\Big (}(a,b_{1})\in R\quad \land \quad (a,b_{2})\in R{\Big )}\quad \longrightarrow \quad b_{1}=b_{2}.}$ 2.- Existencia de imaxe: ${\displaystyle \forall a\in A:\;\exists b\in B\quad \land \quad (a,b)\in R.}$ 3.- Unicidade de orixe: ${\displaystyle {\Big (}(a_{1},b)\in R\quad \land \quad (a_{2},b)\in R{\Big )}\quad \longrightarrow \quad a_{1}=a_{2}.}$

Aplicación sobrexectiva

Artigo principal: sobrexectiva.

Unha correspondencia chámase Aplicación sobrexectiva se cumpre a condición de unicidade de imaxe, existencia de imaxe e existencia de orixe:

Dada unha relación binarias heteroxénea R, entre os conxunto A e B: ${\displaystyle R:A\rightarrow B}$ Esta relación é unha aplicación sobrexectiva, se cumpre: 1.- Unicidade de imaxe: ${\displaystyle {\Big (}(a,b_{1})\in R\quad \land \quad (a,b_{2})\in R{\Big )}\quad \longrightarrow \quad b_{1}=b_{2}.}$ 2.- Existencia de imaxe: ${\displaystyle \forall a\in A:\;\exists b\in B\quad \land \quad (a,b)\in R.}$ 3.- Existencia de orixe: ${\displaystyle \forall b\in B:\;\exists a\in A\quad \land \quad (a,b)\in R.}$

Aplicación bixectiva

Artigo principal: bixectiva.

Unha correspondencia é unha aplicación bixectiva se cumpre as condicións de unicidade de imaxe, existencia de imaxe, unicidade de orixe e existencia de orixe:

Dada unha relación binaria heteroxénea R, entre os conxuntos A e B: ${\displaystyle R:A\rightarrow B}$ Esta relación é unha aplicación bixectiva, se cumpre: 1.- Unicidade de imaxe: ${\displaystyle {\Big (}(a,b_{1})\in R\quad \land \quad (a,b_{2})\in R{\Big )}\quad \longrightarrow \quad b_{1}=b_{2}.}$ 2.- Existencia de imaxe: ${\displaystyle \forall a\in A:\;\exists b\in B\quad \land \quad (a,b)\in R.}$ 3.- Unicidade de orixe: ${\displaystyle {\Big (}(a_{1},b)\in R\quad \land \quad (a_{2},b)\in R{\Big )}\quad \longrightarrow \quad a_{1}=a_{2}.}$ 4.- Existencia de orixe: ${\displaystyle \forall b\in B:\;\exists a\in A\quad \land \quad (a,b)\in R.}$

Unha Aplicación é bixectiva, se é inxectiva e sobrexectiva.

Outros tipos de relación

Se se permiten relacións sobre clases propias:

• Tipo Conxunto (tamén chamado local): para todas as ${\displaystyle x\in X}$, a clase de tódalas ${\displaystyle y\in Y}$ tal que ${\displaystyle yRx}$, é dicir, ${\displaystyle \{y\in Y,yRx\}}$, é un conxunto. Por exemplo, a relación ${\displaystyle \in }$ é de tipo conxunto, e todas as relacións de dous conxuntos son de tipo conxunto.^[8]

Notas

1. Garrett Birkhoff & Thomas Bartee (1970) Álxebra aplicada moderna, páxina 35, McGraw-Hill
2. Mary P. Dolciani (1962) Modern Algebra: Structure and Method, Libro 2, páxina 339, Houghton Mifflin
3. Gutiérrez Gómez, Andrés; García Castro, Fernando (1981). "2.3. Relaciones de equivalencia". Álgebra lineal (1 ed.). Ediciones Pirámide, S.A. p. 74. ISBN 978-84-368-0174-3.
4. José Juan Carreño Carreño (2008). "ÁLXEBRA Curso 2008/09" (pdf). p. 13.^{[Ligazón morta]}
5. Mario López Gómez (2005). "Algebra I" (pdf). p. 5 />.^{[Ligazón morta]}Gregori Gregori, Valentín; Ferrando, J. C. (2011). Matemática discreta (8 ed.). Editorial Reverté, S.A. p. 48. ISBN 978-84-291-5179-4.
6. Ayres, Frank (1992). Álxebra moderna (1 ed.). McGraw-Hill. p. 6. ISBN 968-422-917-8.
7. Gran enciclopedia temática Praza. Matemáticas (2 ed.). Praza & Janés Editores, S.A. 1993. p. 400. ISBN 978-84-01-61659-4. segundo outra nomenclatura.
8. Kunen, Kenneth (1980). Set theory: an introduction to independence proofs. North-Holland. p. 102. ISBN 0-444-85401-0. Zbl 0443.03021.

Véxase tamén

Wikimedia Commons ten máis contidos multimedia na categoría:  Relación binaria

Bibliografía

1. González Gómez, Antonia (2009). Álgebra lineal. Fundación Conde del Valle de Salazar. ISBN 978-84-96442-28-3.
2. Baquerizo Azofra, Clara (2008). Matemática discreta y álgebra lineal (1 ed.). Martín Gómez, Emilia. ISBN 978-84-612-3787-6.
3. Hortalá González, María Teresa (2001). Matemática discreta y lógica matemática (2 ed.). Editorial Complutense, S.A. ISBN 978-84-7491-650-8.
4. Climent Coloma, Joan Josep (2001). Álgebra. Teoría de conjuntos y estructuras algebraicas (1 ed.). Editorial Club Universitario. ISBN 978-84-8454-081-6.
5. Gutiérrez Gómez, Andrés; García Castro, Fernando (1981). Álgebra lineal (1 ed.). Ediciones Pirámide, S.A. ISBN 978-84-368-0174-3.
6. Losada Rodríguez, Ramón (1978). Análisis matemático. Ediciones Pirámide, S.A. ISBN 978-84-368-0096-8.
7. Losada Rodríguez, Ramón (1973). Conjuntos Álgebra Lineal (2 ed.). ISBN 978-84-400-6592-6.

Outros artigos

• Teoría da orde.
• Teoría de conxuntos.

Ligazóns externas

• Relaciones binarias
• Relaciones binarias
• Conjuntos, aplicaciones y relaciones binarias.
• Relaciones binarias y grafos
• ^{[Ligazón morta]}
• Introducción a las estructuras algebraicas