Archivo de la etiqueta: relación inversa

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

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

  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_{Dom\ 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

Estudiaremos un tipo especial de relaciones, llamadas relaciones de equivalencia, las cuales nos permitirán estudiar con mayor facilidad a un nuevo conjunto pues lo dividiremos en partes que cumplan ciertas características.

Enlaces

En el siguiente enlace podrás encontrar más información referente al tema de composición de funciones:

Teoría de los Conjuntos I: Relaciones

Introducción

En esta nueva entrada vamos a ver el concepto de relación, para definirla es necesario tener fresco el concepto de producto cartesiano. Así mismo, definiremos nuevos conjuntos a partir de una relación, como lo son el dominio, la imagen de una relación, la imagen de un conjunto bajo una relación. Concluiremos esta sección definiendo a la relación inversa.

Relación

Definición: Sean $A$ y $B$ conjuntos, definimos $r$ una relación de $A$ en $B$ si y sólo si $r\subseteq A\times B$.

Si $A=B$ diremos que $r\subseteq A\times A$ es una relación en $A$.

Ejemplo 1:

Sea $A=\set{\emptyset,\set{\emptyset}}$ y $B=\set{\emptyset, \set{\set{\emptyset}}}$ y definimos $r$ como:

$r=\set{(\emptyset, \emptyset), (\emptyset, \set{\set{\emptyset}})}$.

Dado que $A\times B=\set{(\emptyset,\emptyset), (\emptyset, \set{\set{\emptyset}}), (\set{\emptyset}, \emptyset), (\set{\emptyset}, \set{\set{\emptyset}})}$ y $r\subseteq A\times B$ decimos que $r$ es una relación de $A\times B$.

$\square$

Ejemplo 2:

Sea $A=\set{1,2}$ y $B=\set{1,2,3}$. Definimos $R=\set{(1,1), (1,2), (1,3)}$ y decimos que $R$ es una relación.

En efecto, pues $R=\set{(1,1), (1,2), (1,3)}\subseteq A\times B$, donde $A\times B=\set{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)}$.

Si representamos a $R$, podemos verlo como sigue:

Imagen de relación del ejemplo 2

$\square$

Definición: Si $(x,y)\in r$ con $r$ relación, decimos que $x$ está relacionado con $y$ y lo denotaremos como $xRy$.

Si retomamos el ejemplo 1 podemos decir que $\emptyset r\emptyset$ y $\emptyset r\set{\set{\emptyset}}$.

A partir del ejemplo 2 podemos decir que $1R1$, $1R2$ y $1R3$.

Relaciones relevantes

A continuación hablaremos de algunas relaciones que se pueden definir. Dichas relaciones serán de gran utilidad más adelante, por lo que incluso tienen nombre.

  1. Relación vacía
    Si $r=\emptyset$, entonces $r$ será llamada relación vacía. Esto tiene sentido pues $\emptyset\subseteq A\times B$ para cualesquiera $A$ y $B$ conjuntos, debido a que el conjunto vacío está contenido en cualquier conjunto y $A\times B$ es un conjunto.
  2. Relación identidad
    Sea $A$ un conjunto cualquiera, definimos la relación identidad en $A$ como:
    $Id_{A}=\set{(a,a):a\in A}$.
    Notamos que $Id_{A}\subseteq A$ pues para cualquier $(x,y)\in Id_{A}$ se tiene que $x=y$ tal que $x,y\in A$, lo que significa que $(x,y)\in A\times A$.
  3. Relación inclusión
    Sea $X$ un conjunto cualquiera, definimos a la relación inclusión en $\mathcal{P}(X)$ como el siguiente conjunto:
    $\set{(A, B): A,B\in \mathcal{P}(X)\ y\ A\subseteq B}$.
  4. Relación de pertenencia
    Sea $A$ un conjunto, definimos a la relación de pertenencia en $A$ como el siguiente conjunto:
    $\in_{A}=\set{(a,b): a\in A,\ b\in A,\ a\in b}$.
  5. Relación de contención
    Sea $A$ un conjunto, definimos a la relación de pertenencia en $A$ como el siguiente conjunto:
    $\subseteq_{A}=\set{(a,b): a\in A,\ b\in A,\ a\subseteq b}$.

Dominio de una relación

Ya que hemos definido el concepto de relación, a continuación definiremos al dominio de una relación:

Definición: Sea $r$ una relación de $A$ en $B$, definimos el dominio de la relación como:

$dom(r)=\set{x\in A:\exists y\in B\ tal\ que\ (x,y)\in r}$.

Ejemplo:

Sean $A=B=\set{1,2}$, definimos $R=\set{(1,2), (1,1), (2,2)}\subseteq A\times B$. Tenemos que:

$dom(R)=\set{1,2}$

pues para $1\in A$ existe $1,2\in B$ tales que $(1,1),(1,2)\in R$ y para $2\in A$ existe $2\in B$ tal que $(2,2)\in R$.

$\square$

Imagen de una relación

A continuación vamos a definir la imagen de una relación:

Definición: Sea $r$ una relación de $A$ en $B$, definimos la imagen de la relación $r$ como:

$im(r)=\set{y\in B:\exists x\in B\ tal\ que\ (x,y)\in r}$.

Ejemplo:

Sean $A=B=\set{1,2}$, definimos $R=\set{(1,2), (1,1), (2,2)}\subseteq A\times B$. Tenemos que:

$im(R)=\set{1,2}$

pues para $1\in B$ existe $1\in A$ tal que $(1,1)\in R$ y para $2\in B$ existe $1,2\in A$ tal que $(1,2), (2,2)\in R$.

$\square$

Imagen de un conjunto bajo una relación

Definición: Sea $R$ una relación de $A$ en $B$. Sea $C\subseteq A$, definimos a la imagen de $C$ bajo $R$ como el siguiente conjunto:

$R(C)=\set{y\in B: \exists x\in C (xRy)}$.

Ejemplo:

Sean $A=\set{1,2}$ y $B=\set{1,2,3,4}$ conjuntos. Sea $r=\set{(1,1), (1,3), (2,1), (2,2), (2,4)}$ una relación de $A$ en $B$ y sea $C=\set{1}\subseteq A$, tenemos que

$R(C)=\set{y\in {1,2,3,4}:\exists x\in{1}(xRy)}= \set{1,3}$.

$\square$

Relación inversa

Definición: Sean $A$ y $B$ conjuntos. Sea $r$ una relación de $A$ en $B$, definimos la relación inversa de $r$ de $B$ en $A$ como:

$r^{-1}=\set{(b,a): (a,b)\in r}$.

Notemos que la relación inversa intercambia el orden de las entradas de las parejas ordenadas que son elementos de la relación $r$.

Ejemplo:

Sea $A=\set{\emptyset}$ y $B=\set{\emptyset, \set{\emptyset}}$ y definimos $r$ como:

$r=\set{(\emptyset, \emptyset), (\emptyset,\set{\emptyset})}$

tenemos que

$r^{-1}=\set{(\emptyset, \emptyset), (\set{\emptyset}, \emptyset)}$.

En efecto, pues como $(\emptyset, \emptyset)\in r$ tendremos que $(\emptyset, emptyset)\in r^{-1}$ y como $(\set{\emptyset}, \emptyset)\in r$ tendremos que $(\emptyset, \set{\emptyset})\in r^{-1}$.

$\square$

Proposición: Sea $R$ una relación, demuestra que $(R^{-1})^{-1}=R$.

Demostración:

Sea $R$ una relación, tenemos que

\begin{align*}
(R^{-1})^{-1}&=\set{(x,y): (y,x)\in R^{-1}}\\
&= \set{(x,y): (x,y)\in R}\\
&= R.
\end{align*}

$\square$

Tarea moral

La siguiente lista de ejercicios te permitira reforzar los conceptos de relación, dominio e imagen.

  1. Si $r$ es la relación vacía, encuentra el dominio y la imagen de $r$.
  2. Si $R$ es la relación identidad de $A$, encuentra el dominio y la imagen de $R$.
  3. Sea $R=\set{(1,2), (3,4)}$ relación de $A=\set{1,2,3}$ en $B=\set{1,2,3,4}$. Encuentra el dominio y la imagen de $R$. Además escribe al conjunto $R^{-1}$.
  4. Si $R$ es la relación identidad de $A$, describe a $R^{-1}$.

Más adelante

En la siguiente sección continuaremos con el tema de relaciones, trataremos la composición de relaciones.

Enlaces

En los siguientes enlaces podrás encontrar contenido relacionado a relaciones:

Álgebra Superior I: Relaciones en conjuntos: dominio, codominio y composición

Álgebra Superior I: Tipos de relaciones en conjuntos