Archivo de la etiqueta: relación identidad

Teoría de los Conjuntos I: Composición de relaciones

Por Gabriela Hernández Aguilar

Introducción

En esta entrada retomaremos el tema de relaciones que vimos anteriormente. Esta vez definiremos una nueva relación a partir de dos relaciones: la composición. Veremos si la composición de dos relaciones 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 $C$ en $D$ 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\ tal\ que\ (a,b)\in R_1\ y\ (b,c)\in R_2}$.

En otros símbolos, si $a,b,c$ son elementos tales que $aR_1b$ y $bR_2c$, entonces se cumplirá que $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)}$.

Podemos hacer diagramas de ambas relaciones en una misma figura como sigue:

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)}$.

Para leerlo en el diagrama, podemos ver que hay un «camino» de $0$ a $3$ que usa las flechas de $0$ a $1$, y de $1$ a $3$. También hay un «camino» de $0$ a $4$ que usa las flechas de $0$ a $1$, y de $1$ a $4$.

Además de notarlo en el diagrama, podemos verificar mediante la definición. La pareja $(0,3)$ está pues $1\in Y$ tal que $(0,1)\in R_1$ y $(1,3)\in R_2$. Por su parte, la pareja $(0,4)$ está pues existe $1\in Y$ tal que $(0,1)\in R_1$ y $(1,4)\in R_2$.

$\square$

Algunos resultados

A continuación hablaremos de algunos resultados 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$ 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$ 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. Si $R$ es una relación de $A$ en $B$, entonces $Id_{Im\ R}\subseteq R\circ R^{-1}$.

Demostración.

Sea $y\in Im(R)$. 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}$.

Encontramos $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 ello, podemos preguntarnos qué pasa con la conmutatividad y la asociatividad de dicha operación.

En general, no es cierto que $R_1\circ R_2=R_2\circ R_1$, es decir, la composición no es conmutativa.

Ejemplo.

Consideremos $X=\set{1,2}$. Sean $R_1=\set{(1,1), (1,2)}$ y $R_2=\set{(1,2),(2,1)}$ relaciones en $X$.

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$.

$\square$

El segundo resultado que tenemos es que la asociatividad siempre se cumple.

Proposición. Si $R_1$, $R_2$ y $R_3$ son relaciones, entonces, $(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, tenemos que $(x,z)\in (R_3\circ R_2)\circ R_1$ si y sólo si existe $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$ tal que $(y,w)\in R_2$ y $(w,z)\in R_3$ para algún $y$ si y sólo si existe $w$ tal que $(x,w)\in R_2\circ R_1$ y $(w,z)\in R_3$ si y 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

  1. Demuestra que si $R$ es una relación arbitraria, $R\circ \emptyset=\emptyset=\emptyset\circ R$.
  2. Prueba que si $R$ es una relación en $A$, entonces $R=Id_{A}\circ R$.
  3. Sea $R$ una relación de $A$ en $B$. Demuestra que $Id_{\text{DomAct} R}\subseteq R^{-1}\circ R$.
  4. 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…

Ya hemos hablado de relaciones en general, y de cómo componerlas. A partir de ahora comenzaremos a pedirle más propiedades a nuestras relaciones para que se conviertan en algunos tipos de relaciones muy especiales: funciones, relaciones de equivalencia, órdenes, etc. Comenzaremos a hacer esto en la siguiente entrada, en donde veremos qué se le debe pedir a una relación para que sea una función. Así, todas las funciones son relaciones, sin embargo, no toda relación será función.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»