Introducción
En esta sección retomaremos el tema de relaciones que vimos en la entrada anterior. Esta vez definiremos una nueva relación a partir de dos relaciones con ciertas características y una operación a la que llamaremos composición. Veremos si la operación composición tiene propiedades como la conmutatividad o la asociatividad.
Definamos la composición
Definición: Sean $r_1$ y $r_2$ relaciones de $A$ en $B$ y de $B$ en $C$ respectivamente. Definimos a la composición de $r_1$ con $r_2$ como el siguiente conjunto:
$r_2\circ r_1=\set{(a,c): \exists b\in B\ tal\ que\ (a,b)\in r_1\ y\ (b,c)\in r_2}$.
Notemos que $r_1$ debe satisfacer que $Im(r_1)\subseteq B$ y $r_2$ es tal que $Dom(r_2)\subseteq B$, debido a que la definición nos pide que exista un puente entre los elementos de $A$ y $C$. El puente que necesitamos que exista para hablar de la composición de relaciones nos lo da el conjunto $B$ ya que algunos de los elementos de $A$ estarán relacionados con elementos de $B$ y los elementos de $B$ están relacionados con algunos de los elementos de $C$.
Aquellos elementos $a$ que satisfagan estar relacionados con algún elemento de $B$, digamos $b$, esto es $ar_1b$ y a su vez $b$ este relacionado con $c$, $br_2c$, serán aquellos que conformen a los elementos de $r_2\circ r_1$ y serán de la forma $a\ r_2\circ r_1\ c$.
Ejemplo:
Sean $X=\set{0,1}$ y $Y=\set{1,2}$ y $Z=\set{1,2,3,4}$ conjuntos. Sean $r_1$ y $r_2$ relaciones de $X$ en $Y$ y de $Y$ en $Z$ definidas como sigue:
$r_1=\set{(0,1), (0,2)}\ y\ r_2=\set{(1,3), (1,4)}$.
Representaremos ambas relaciones de las siguiente formas:
Luego, la composición de $r_2\circ r_1$ resulta ser el siguiente conjunto:
$r_2\circ r_1=\set{(0, 3), (0,4)}$.
Además de notarlo en la imagen anterior, verificamos esto pues para la pareja $(0,3)\in r_2\circ r_1$ existe $1\in Y$ tal que $(0,1)\in r_1$ y $(1,3)\in r_2$. Por su parte, para la pareja $(0,4)\in r_2\circ r_1$ existe $1\in B$ tal que $(0,1)\in r_1$ y $(1,4)\in r_2$.
$\square$
Algunos resultados
A continuación hablaremos acerca de algunos resultados acerca de la composición, la relación inversa y la relación identidad:
Proposición: Si $R$ es una relación en $A$, entonces $R\circ Id_{A}=R$.
Demostración:
Sea $R$ una relación en $A$. Veamos que $R\circ Id_{A}=R$.
$\subseteq$] Sea $(x,z)\in R\circ Id_{A}$, entonces existe $y\in A$ tal que $(x,y)\in Id_{A}$ y $(y,z)\in R$.
Luego, como $(x,y)\in Id_{A}$ se sigue que $x=y$ y así $(y,z)=(x,z)\in R$.
$\supseteq$] Sea $(a,c)\in R$. Como $a,c\in A$, se sigue que $(a,a)\in Id_{A}$. Por lo que existe $a\in A$ tal que $(a,a)\in Id_{A}$ y $(a,c)\in R$. Por lo tanto, $(a,c)\in R\circ Id_{A}$.
Por lo tanto, $R\circ Id_{A}=R$.
$\square$
Proposición: Sea $R$ una relación de $A$ en $B$. Demuestra que $Id_{Im\ R}\subseteq R\circ R^{-1}$.
Demostración:
Sea $(x,y)\in Id_{Im\ R}$, entonces $x,y\in Im\ R$ y son tales que $x=y$. Luego, como $y\in Im\ R$ existe $a\in A$ tal que $(a,y)\in R$, y por definición de relación inversa tenemos que $(y,a)\in R^{-1}$.
Por lo tanto, existe $a\in A$ tal que $(y,a)\in R^{-1}$ y $(a,y)\in R$, esto es $(y,y)\in R\circ R^{-1}$. Así, $Id_{Im\ R}\subseteq R\circ R^{-1}$.
$\square$
Propiedades de la composición
Hemos dicho hasta ahora que la composición es una operación entre dos conjuntos que son relaciones. Por lo que podemos preguntarnos que pasa con la conmutatividad y la asociatividad de la operación. A continuación veremos dos proposiciones que nos dan respuestas a dichas preguntas.
Proposición: Sean $r_1$ y $r_2$ relaciones de $X$ en $Y$ y de $Y$ en $Z$ respectivamente. Muestra que no siempre es posible que $r_1\circ r_2=r_2\circ r_1$.
Demostración:
Consideremos $X=\set{1,2}$, $Y=\set{1,2,3}$ y $Z=\set{1,2,3}$. Sean $r_1=\set{(1,1), (1,2)}$ y $r_2=\set{(1,2),(2,1)}$ relaciones de $X$ en $Y$ y de $Y$ en $Z$ respectivamente.
Por un lado tenemos que
$r_1\circ r_2=\set{(2,1), (2,2)}$
y por otro lado
$r_2\circ r_1=\set{(1,2),(1,1)}$
De modo que $r_1\circ r_2\not=r_2\circ r_1$.
Proposición: Sean $r_1$, $r_2$ y $r_3$ relaciones de $X$ en $Y$, de $Y$ en $W$ y de $W$ en $Z$ respectivamente. Muestra que $(r_3\circ r_2)\circ r_1=r_3\circ (r_2\circ r_1)$.
Demostración:
Sean $r_1$, $r_2$ y $r_3$ relaciones de $X$ en $Y$, de $Y$ en $W$ y de $W$ en $Z$ respectivamente. Tenemos que
$(x,z)\in (r_3\circ r_2)\circ r_1$ si y sólo si
existe $y\in Y$ tal que $(x,y)\in r_1$ y $(y,z)\in r_3\circ r_2 si y sólo si
$(x,y)\in r_1$ y existe $w\in W$ tal que $(y,w)\in r_2$ y $(w,z)\in r_3$ para algún $y\in Y$ si y sólo si
existe $w\in W$ tal que $(x,w)\in r_2\circ r_1$ y $(w,z)\in r_3$ si sólo si
$(x,z)\in r_3\circ(r_2\circ r_1)$.
Por lo tanto, $(r_3\circ r_2)\circ r_1=r_3\circ (r_2\circ r_1)$.
$\square$
Hemos probado que la composición de relaciones es asociativa y a su vez concluimos que en general no conmuta.
Tarea moral
- Demuestra que si $R$ es una relación arbitraria, $R\circ \emptyset=\emptyset=\emptyset\circ R$.
- Prueba que si $R$ es una relación en $A$, entonces $R=Id_{A}\circ R$.
- Sea $R$ una relación de $A$ en $B$. Demuestra que $Id_{Dom\ R}\subseteq R^{-1}\circ R$.
- Sean $A= \set{1,2,3}$, $B=\set{1,2}$ y $C=\set{1,2,3,4}$. Sean $r_1=\set{(1,2), (3,1)}$ y $r_2=\set{(1,4), (2,1), (2,3)}$ relaciones de $A$ en $B$ y de $B$ en $C$ respectivamente. Calcula $r_2\circ r_1$.
Más adelante…
En la siguiente entrada estudiaremos a un tipo especial de relaciones, a las que llamaremos funciones. Veremos que todas las funciones son relaciones, sin embargo, no toda relación será función.
Enlaces
- Entrada relacionada: Álgebra Superior I: Relaciones en conjuntos: dominio, codominio y composición
- Entrada anterior: Teoría de los Conjuntos I: Relaciones
- Siguiente entrada: Teoría de los Conjuntos I: Funciones