Archivo de la etiqueta: relación inversa

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

Por Gabriela Hernández Aguilar

Deja un comentario

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((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. Si $(x,z)\in (R_3\circ R_2)\circ R_1$, existe $y$ tal que $(x,y)\in R_1$ y $(y,z)\in R_3\circ R_2$. Luego, como $(y,z)\in R_3\circ R_2$, existe $w$ tal que $(y,w)\in R_2$ y $(w,z)\in R_3$. Así, dado que $(x,y)\in R_1$ y $(y,w)\in R_2$, $(x,w)\in R_2\circ R_1$, y como $(w,z)\in R_3$ entonces $(x,z)\in R_3\circ(R_2\circ R_1)$. Por tanto, $(R_3\circ R_2)\circ R_1\subseteq R_3\circ(R_2\circ R_1)$.
Ahora, si $(x,z)\in R_3\circ(R_2\circ R_1)$, existe $w$ tal que $(x,w)\in R_2\circ R_1$ y $(w,z)\in R_3$. Luego, existe $y$ tal que $(x,y)\in R_1$ y $(y,w)\in R_2$ y, por tanto, $(x,y)\in R_1$ y $(y,z)\in R_3\circ R_2$, por lo que $(x,z)\in (R_3\circ R_2)\circ R_1$. En consecuencia, $R_3\circ(R_2\circ R_1)\subseteq(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. Si $R$ y $S$ son relaciones, entonces $S\circ R\subseteq dom(R)\times im(S)$.
  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»

Teoría de los Conjuntos I: Relaciones

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta nueva entrada veremos el concepto de relación, para lo cual 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 y el concepto de relación inversa. Concluiremos esta entrada definiendo a la imagen inversa de un conjunto bajo una relación.

Relación

Definición. Sean $A$ y $B$ conjuntos. Una relación $R$ de $A$ en $B$ es un subconjunto de $A\times B$. A $A$ le llamamos el dominio de la relación y a $B$ el codominio.

Si $A=B$ diremos que $R$ 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$ en $B$.

$\square$

Ejemplo 2.

Sea $A=\set{1,2}$ y $B=\set{1,2,3}$. Definimos $S=\set{(1,1), (1,2), (1,3)}$. Tenemos que $S$ es una relación de $A$ en $B$. En efecto, esto sucede pues $S=\set{(1,1), (1,2), (1,3)}\subseteq A\times B$, ya que $A\times B=\set{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)}$.

Podemos representar a $S$ mediante el siguiente diagrama. Del lado izquierdo hemos puesto al dominio $A$. Del lado derecho al codominio $B$. Para cada pareja $(a,b)$ de la relación, hemos puesto una flecha de $a$ a $b$.

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$ mediante $R$ (o simplemente que $x$ está relacionado con $y$ si por el contexto es claro quién es $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 $1S1$, $1S2$ y $1S3$.

Relaciones relevantes

A continuación hablaremos de algunos ejemplos de relaciones que nos serán de utilidad más adelante.

  1. Relación vacía.
    Si $R=\emptyset$, entonces $R$ será llamada la relación vacía. Esto tiene sentido pues $\emptyset\subseteq A\times B$ para cualesquiera $A$ y $B$ conjuntos.
  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\times A$ pues para cualquier $(x,y)\in Id_{A}$ se tiene que $x=y$ con $x,y\in A$, lo que significa que $(x,y)\in A\times A$.
  3. 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}.$$
  4. Relación de contención.
    Sea $A$ un conjunto. Definimos a la relación de contención 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:

$\text{dom}(R)=\set{x\in A:\exists y\in B( (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 $\text{dom}(R)=\set{1,2}$ pues para $1\in A$ existe, digamos, $1\in B$ tal que $(1,1)\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 lo análogo al dominio activo, pero para el codominio. Le daremos un nombre al subconjunto de elementos del codominio que sí participan en la relación.

Definición. Sea $R$ una relación de $A$ en $B$. Definimos la imagen de $R$ como el conjunto

$\text{im}(R)=\set{y\in B:\exists x\in A( (x,y)\in R)}$.

Ejemplo.

Sean $A=B=\set{1,2}$. Definimos $R=\set{(1,2), (2,2)}\subseteq A\times B$.

Tenemos que $\text{im}(R)=\set{2}$ pues para $2\in B$ existe, digamos $2\in A$ tal que $(2,2)\in R$. Sin embargo, $1\not \in \text{im}(R)$ pues $R$ no tiene ninguna pareja de la forma $(x,1)$ con $x\in A$.

$\square$

Imagen de un conjunto bajo una relación

A veces queremos preguntarnos por los elementos del codominio que participan en la relación, pero sólamente con ciertos elementos del dominio. La siguiente definición establece esto.

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 el 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)}$, la cual es una relación de $A$ en $B$. Tomemos $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

Para cerrar esta entrada, introduciremos un concepto más: el de 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$ como la relación $R^{-1}$ de $B$ en $A$ definida como sigue:

$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, 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. Se cumple que $(R^{-1})^{-1}=R$.

Demostració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$

Imagen inversa de un conjunto bajo una relación

Definición. Sea $R$ una relación de $A$ en $B$. Sea $C\subseteq B$. Definimos a la imagen inversa de $C$ bajo $R$ como el el conjunto

$R^{-1}[C]=\set{x\in A: \exists y\in C (xRy)}$.

Ejemplo.

Sean $A=\set{1,2}$ y $B=\set{1,2,3,4}$ conjuntos. Si $R=\set{(1,1), (1,3), (2,1), (2,2), (2,4)}$ es una relación de $A$ en $B$, entonces $R^{-1}=\{(1,1), (1,2), (2,2), (3,1), (4,2)\}$. Tomemos $C=\set{1}\subseteq B$. Tenemos que

$R^{-1}[C]=\set{x\in \{1,2\}:\exists y\in\{1\}(xRy)}= \set{1,2}$.

$\square$

Tarea moral

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

  1. Si $R$ es la relación vacía, encuentra el dominio activo y la imagen de $R$.
  2. Para $R$ es la relación identidad de $A$, encuentra el dominio y la imagen de $R$.
  3. Sea $R=\set{(1,2), (3,4)}$ una 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 quién es $R^{-1}$.

Más adelante…

En la siguiente entrada continuaremos con el tema de relaciones. Esta vez trataremos el tema de composición de relaciones. Definiremos a la composición de relaciones como una relación que se construye a partir de al menos dos relaciones cuyos dominios y codominios tienen ciertas propiedades en comú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»