Archivo de la etiqueta: Transitividad

Álgebra Superior I: Tipos de relaciones en conjuntos

Introducción

Hemos hablado ya de relaciones entre conjuntos, sobre imagen, dominio y composición. Ahora vamos a ver algunas relaciones especiales entre conjuntos, que son la inyectividad, la suprayectividad y relaciones de un conjunto en sí mismo.

Inyectividad de una relación

Las ideas de los dos tipos de relación que vamos a exponer son inyectividad y suprayactividad. La inyectividad es una idea que nos va a hablar de cómo podemos relacionar un elemento de la imagen de una relación con un elemento del dominio. En pocas palabras lo que nos dirá la inyectividad es: Una relación inyectiva es aquella en la que los distintos elementos del dominio van a elementos de la imagen distintos. Veamos esto con calma con un ejemplo.

Supongamos que a nosotros nos interesa recuperar los elementos del dominio con los de la imagen, es decir, quisiéramos ver para cada pareja $y$ de la imagen, de qué $x$ proviene. En el caso de que haya dos relaciones distintas $(x,y),(z,y)$ nos causaría conflicto, pues podríamos decir que $y$ «viene» de dos distintos elementos del dominio.

Una relación inyectiva es aquella en donde para cada elemento de la imagen, existe un único elemento del dominio que se relaciona con esta. Es decir, una relación inyectiva $R$ será aquella en donde para cada $y \in Im(R)$, solo existe un elemento $x \in Dom(R)$ tal que $(x,y) \in R$. Otra forma de verlo es con la siguiente definición:

Definición. Sean $X,Y$ dos conjuntos y $R$ una relación de $X$ en $Y$. Diremos que $R$ es inyectiva si $$\forall y \in Im(R) (\exists ! x \in X:(x,y) \in R)$$

Observa ahora que esto significa que si $R$ es una relación inyectiva y dos parejas $(x,y),(z,y)$ pertenecen a la relación $R$, entonces no les queda de otra que ser la misma pareja, esto implica que $x=z$.

Proposición. Sea $R$ una relación entre dos conjuntos $X$ y $Y$. Entonces son equivalentes:

  1. $R$ es una relación inyectiva.
  2. Si $(x,y) \in R$ y $(w,y) \in R$ entonces $x=w$.

Demostración.

$1) \Rightarrow 2)$. Consideremos $(x,y) \in R$ y $(w,y) \in R$. Lo que queremos demostrar es que $x=w$, para ello notemos que $R$ es inyectiva, lo que quiere decir que existe una única pareja $(x,y) \in R$. Esto quiere decir que $(x,y)=(w,y)$ y esto solo sucede si $y=y$ y $x=w$. Siendo la segunda igualdad la buscada.

$2) \Rightarrow 1)$. Ahora supongamos que si $(x’,y’) \in R$ y $(w’,y’) \in R$ entonces $x’=w’$. Y supongamos que $y$ es un elemento de la imagen de $R$. Demostremos ahora que existe un único elemento $x$ tal que $(x,y) \in R$. Para ello mostraremos que existe al menos un elemento $x$ tal que $(x,y)$ y cualquier otro elemento $w$ no cumple tal propiedad. Para demostrar lo primero, notemos que $y$ es un elemento del contradominio, lo que quiere decir que existe al menos un elemento $x \in X$ tal que $(x,y) \in R$. Y finalmente para demostrar que $x$ es único, supongamos existe un elemento $w \in X$ distinto a $x$ tal que $(w,y) \in R$. Pero por hipótesis, si pasa esto entonces $x=w$, lo cual es una contradicción pues hemos dicho que $x$ es distinto a $w$. De esta manera, $x$ sí es único.

$\square$

También es análogo pensar que si una relación $R$ es inyectiva, entonces para cada elemento de la imagen $y$, sucede que $Im^{-1}[\{y\}]$ tiene un único elemento, pues la definición nos dice que solo existe un elemento $x$ del dominio que se relaciona con $y$.

Ahora observa por ejemplo a los conjuntos de animales $X$ y el tipo de animales $Y$. Podríamos decir que en tipos de animales, tenemos aquellos que viven en la tierra (terrestres) y los que viven en el agua (acuáticos). Entonces una parte de la relación $R$ que relaciona el animal con el hábitat que tiene, se vería de la siguiente manera:

Ahora, si nos preguntamos, cuáles son los animales terrestres, deberíamos observar que al menos los animales terrestres son los perros, gatos, camellos, etc. Una relación que no es inyectiva, no nos regresa un único elemento, sino que un subconjunto del dominio de más de un elemento. Así que esta relación no es inyectiva.

Por otro lado, una relación que sí es inyectiva entre los conjuntos $X=\{a,b,c,d,e,f\}$ y $\mathbb{Z}$ es la relación $R$:

$$R=\{(a,y): y \in Z\} $$

Es inyectiva pues los elementos de esta relación se ven como: $R=\{\dots,(a,-1),(a,0),(a,1),(a,2),\dots\}$ Y si agarramos cualquier número en la imagen de la relación, solo vendrá de un elemento, el elemento $a$.

Otros ejemplos de relaciones inyectivas son:

$R = \{(x,y) \in \mathbb{Z}^2:x=y\}$
$R = \{(x,y) \in \mathbb{Z}^2:x=2y\}$
$R = \{(x,y) \in \mathbb{Z}^2:(0,y) \text{ si }y\text{ es par,}(1,y)\text{ en otro caso}\}$

Relaciones suprayectivas

Otro concepto que será interesante es el de la suprayactividad. Este en términos simples nos dice que una relación $R$ es suprayectiva entre dos conjuntos $X,Y$ si cada elemento de $Y$ se relaciona con algún elemento de $X$. Es así como la siguiente definición nos lo menciona:

Definción. Sean $X,Y$ dos conjuntos y $R$ una relación de $X$ en $Y$. Diremos que $R$ es suprayectiva si $Im[Y]=Y$.

Una forma alterna de verlo es como en la siguiente proposición nos lo demuestra, siendo que siempre podremos encontrar una pareja para cada elemento $y$ de $Y$:

Proposición. Una relación $R$ es suprayectiva si y solo si $\forall y\in Y(\exists x \in X:(x,y) \in Y)$

Demostración Sean $X,Y$ dos conjuntos y $R$ una relación de $X$ en $Y$

$\Rightarrow$] Por hipótesis, $R$ es suprayectiva. Para demostrar que $\forall y\in Y(\exists x \in X:(x,y) \in Y)$ consideraremos un elemento $y \in Y$ arbitrario y demostraremos que existe algún elemento $x \in X$ tal que $(x,y)$ sea un elemento de la relación.
Como hipótesis, sabemos que la imagen de $R$ es igual a $Y$, esto quiere decir que:$$Y=Im(R)=\{y \in Y: \exists x \in X \text{ tal que }(x,y)\in R\}.$$ De esta manera, $$y \in \{y \in Y: \exists x \in X \text{ tal que }(x,y)\in R\}.$$ De manera que $\exists x \in X \text{ tal que }(x,y)\in R$. Por lo tanto, $\forall y\in Y(\exists x \in X:(x,y) \in Y)$

$\Leftarrow$]. Ahora supongamos por hipótesis que para cada elemento $y \in Y$, existe un elemento $x \in X$ tal que $(x,y) \in R$. Ahora, demostremos que $R$ es suprayectiva, es decir $Im(R)=Y$. Para esto, tendremos que demostrar que $Y$ está contenido en $Im(R)$ y viceversa. Pero nota que $Im(R)$ siempre es un subconjunto de $Y$ (pues por definición, sus elementos son elementos de $Y$). Así que bastará demostrar que $Y \subset Im[R]$. Para ello, considera un elemento $y \in Y$. Por hipótesis, para aquel elemento, existirá $x \in X$ tal que $(x,y) \in R$. Pero esto significa que $y \in Im[Y]$. Así, $Y \subset Im[R]$.

$\square$

Un ejemplo de una función suprayectiva sobre los conjuntos $X = \{1,2,3\}, Y=\{0\}$ es la relación $R=\{(1,0),(3,0)\}$. Esto puesto que hay solo un elemento en el conjunto $Y$ y hay al menos una relación para cada elemento del conjunto $Y$. Esto quiere decir que «cubrimos» a todo el contradominio. Otros ejemplos de funciones suprayectivas son:
$R = \{(x,y) \in \mathbb{Z}^2:x=y\}$
$R = \{(x,y) \in \mathbb{Z} \times \{0,1,2,3,4\} : x =1 \land y \in \{0,1,2,3,4\}\}$
Si $R$ es una relación entre dos conjuntos, $X,Y$, la relación $R=X \times Y$ es suprayectiva.

Relaciones de un conjunto en sí mismo

Hemos estado hablando ya de un conjunto muy particular, $\mathbb{Z}^2$ que lo definimos como $\mathbb{Z} \times \mathbb{Z}$, es decir de relaciones en el conjunto de los números enteros en sí mismo. Este tipo de relaciones, como ya lo hemos mencionado, se les acostumbra a poner un subíndice $^2$ para indicar que estamos hablando del producto cartesiano de un conjunto sobre él mismo. Por ejemplo si $X$ es un conjunto, entonces $X^2=X \times X$. Vamos a concentrarnos ahora en algunas relaciones especiales de un conjunto en sí mismo.

La primera relación que veremos será la reflexividad, y esto se da cuando un elemento está relacionado consigo mismo. Por ejemplo, en $\mathbb{Z}^2$, la relación cuyos elementos son de la forma $(x,x)$ siempre será reflexiva, pues cada elemento $x$ está relacionado consigo mismo.

La segunda relación se llama la simetría, que nos indica que para cada pareja $(x,y)$ de la relación, sucederá que igual $(y,x)$ estará en la relación. Si te das cuenta, algo que nos dice esta relación es que el orden «no importa», pues da igual cuál elemento escribamos del lado izquierdo y del lado derecho, pues su homónimo simétrico estará igual en la relación.

La tercera es un concepto similar al segundo pero en su antónimo. Diremos que una relación es antisimétrica si para cada pareja que tengamos en la relación $(x,y) \in R$, no sucederá que $(y,x) \in R$ a menos que $x=y$. Piensa por ejemplo para esto, en la relación «ser menor o igual a un número» $\leq$. Sucede que $1 \leq 2$ pero no que $2 \leq 1$

Finalmente, la cuarta propiedad es llamada la transitividad. Esto lo que nos indica es que la composición de la relación también es parte de la relación. En otras palabras, si $(x,y),(y,z) \in R$ entonces $(x,z) \in R$. Para pensar en un ejemplo, piensa en la igualdad entre números, si $1+1=2$ y $2=4-2$, entonces $1+1=4-2$.

Anotaremos este tipo de relaciones como una definición

Definición. Sea $R$ una relación de un conjunto $X$ en sí mismo. Diremos que:

  • $R$ es reflexiva si $\forall x \in X,(x,x) \in R$
  • $R$ es simétrica si $\forall x \in X \forall y \in X\big( (x,y) \in R \Rightarrow (y,x) \in R \big)$
  • $R$ es antisimétrica si $\forall x \in X \forall y \in X\big( ((x,y) \in R \land (y,x) \in R) \Rightarrow (x=y) \big)$
  • $R$ es transitiva si $\forall x \in X \forall y \in X \forall z \in Z \big( ((x,y) \in R \land (y,z) \in R ) \Rightarrow (x,z) \in R \big)$

Tarea moral

  1. Sean $X,Y$ dos conjuntos y $R$ una relación de $X$ en $Y$.Demuestra que son equivalentes:
    1. $R$ es inyectiva
    2. $\forall y \forall x \big(((x,y)\in R \land (z,y) \in R) \Rightarrow x=z\big)$
    3. $\forall y \in Im(R) \big( Im^{-1}[\{y\}] \text{ tiene un solo elemento}\big)$
  2. Demuestra que las siguientes relaciones son inyectivas:
    • $R = \{(x,y) \in \mathbb{Z}^2:x=y\}$
    • $R = \{(x,y) \in \mathbb{Z}^2:x=2y\}$
    • $R = \{(x,y) \in \mathbb{Z}^2:(0,y) \text{ si }y\text{ es par,}(1,y)\text{ en otro caso}\}$
  3. Sea la relación $R$ sobre el conjunto $X$ de los seres humanos dada por: $$R=\{(x,y) \in X^2:x \text{ tiene el mismo cumpleaños que }y\}.$$ Demuestra que $R$ es una relación reflexiva, simétrica y transitiva.

Más adelante…

En la siguiente entrada entraremos a los ordenes parciales, los cuales son relaciones de un conjunto sobre sí mismo que cumplen algunas de las clases especiales de relaciones que hemos revisado en esta entrada. De hecho quizá ya tengas una idea intuitiva de qué es un orden, concepto que ampliaremos más en lo que sigue.

Entradas relacionadas

Cálculo Diferencial e Integral I: Propiedades de orden de los números reales

Introducción

Comenzaremos a revisar un conjunto de propiedades muy particular que éstas nos permitirán ordenar a los números reales. De acuerdo a este orden podremos decir para un par de números reales, quién es mayor o menor que otro. Así a la lista de propiedades vista previamente le agregaremos las siguientes.

Noción de orden en $\r$

O1.-Existe un subconjunto $P\subseteq \r$ tal que para todo $a\in\r$ ocurre una y sólo una de las siguientes afirmaciones:

  • $a=0$
  • $a\in P$
  • $-a\in P$

O2.-Si $a,b \in P$ entonces $a+b \in P$.

O3.-Si $a,b \in P$ entonces $a\cdot b \in P$.

Observación: Notemos que $P$ esta conformado por los números reales positivos.

Definición: Decimos que:

  • $a>b$ si $a-b \in P$.
  • $a<b$ si $b>a$.
  • $a\geq b$ si $a-b \in P$ o $a=b$.
  • $a\leq b$ si $b-a \in P$ o $a=b$.

Tricotomía

Proposición (Tricotomía): Para cuales quiera $a,b \in \r$. Tenemos que cumple una y sólo una de la siguientes afirmaciones:

  1. $a=b$
  2. $a>b$
  3. $b>a$

Demostración:

Sean $a,b\in\r$. Como por la cerradura de la suma S1 tenemos que: $$a+(-b)= a-b\in\r$$

Por O1 se cumple una y sólo una de las siguientes afirmaciones:

  • $a-b=0$
  • $a-b\in P$
  • $-(a-b)\in P$

Aplicando las definiciones anteriores nos quedaría:

  • $a-b=0 \Rightarrow a=b$
  • $a-b\in P \Rightarrow a>b$
  • $-(a-b)\in P\Rightarrow b-a\in P \Rightarrow b>a$

$\square$

Leyes de los signos

Definición: Diremos que $a$ es positivo si $a\in P$ y que es negativo si $-a\in P$.

Proposición(Leyes de los signos): Sean $a,b\in\r$. Se cumplen las siguientes afirmaciones:

  1. Si $a,b >0$ entonces $a\cdot b >0$.
  2. Si $a,b < 0$ entonces $a\cdot b >0$
  3. Si $a>0$, $b<0$ entonces $a\cdot b < 0$.
  4. Si $a<0$, $b>0$ entonces $a\cdot b < 0$.

Demostración:

  1. Consideremos $a>0$ y $b>0$. Así tenemos que $a\in P$ y $b\in P$ entonces por O3 $a\cdot b \in P$
    $$\therefore a\cdot b > 0$$
  2. Ahora tomemos $a< 0$ y $b<0$. Por lo que $-a\in P$ y $-b\in P$ entonces por O3 $(-a)\cdot( -b) \in P$
    $$\therefore a\cdot b > 0$$

$\square$

Algunos resultados importantes

Proposición: Sean $a,b,c,d \in \r$. Tenemos que se cumplen los siguientes resultados:

  1. Si $a>b$ entonces $a+c>b+c$.
  2. Si $a<b$ y $c<0$ entonces $ac>bc$.
  3. Si $a<b$ y $c>0$ entonces $ac<bc$.
  4. Si $a<b$ y $c<d$ entonces $a+c<b+d$.
  5. Si $a<b$ y $c>d$ entonces $a-c<b-d$.
  6. Si $a<b$ entonces $-b<-a$.

Demostración:

  1. Cómo $a>b$ esto significa que $a-b \in P$.
    Así se sigue que:
    \begin{align*}
    a-b &= a +0 -b\\
    &= a + (c -c)-b\\
    &= (a +c) – (c+b)\\
    \end{align*}
    De lo anterior concluimos que $(a +c) – (c+b) \in P$, es decir, $a +c > c+b$
  2. Tarea moral
  3. Por hipótesis tenemos que $a<b$ y $c>0$ por lo que ocurre: $b-a \in P$ y $c \in P$.
    Por O3 afirmamos que $c (b-a) \in P$. Observemos que: $c (b-a) = cb – ca = bc – ac$.
    $$\therefore bc – ac \in P$$
    $$\therefore bc>ac $$
  4. Ya que $a<b$ y $c<d$ se sigue que $b-a \in P$ y $d-c \in P$. Así por O2 tenemos:
    $$(b-a)+(d-c) \in P$$
    Notemos que:
    \begin{align*}
    (b-a)+(d-c) &= b-a+d-c\\
    &= b+d -a-c\\
    &= (b+d) – (a+c)\\
    \end{align*}
    $$\therefore (b+d) – (a+c) \in P$$
    $$\therefore b+d > a+c$$
  5. Tenemos que $a<b$ y $c>d$ $\Rightarrow b-a \in P$ y $c-d \in P$.
    Por O2 se sigue que $(b-a) + (c-d) \in P$. Y como tenemos lo siguiente:
    \begin{align*}
    (b-a) + (c-d)&= b-a + c-d\\
    &= (b-d) + (-a +c)\\
    &= (b-d) – (a-c)\\
    \end{align*}
    Así concluimos que: $(b-d) – (a-c)\in P$.
    $$ \therefore b-d > a-c$$
  6. Tarea moral

$\square$

Transitividad

Proposición (Transitividad): Para $a,b \in \r$ se cumplen las siguientes propiedades:

  1. Si $a>b$ y $b>c \Rightarrow a>c$.
  2. Si $a< b$ y $b<c \Rightarrow a<c$.

Demostración:

  1. Cómo $a>b$ y $b>c$ sabemos que $a-b \in P$ y $b-c \in P$.
    Entonces tenemos por O2 $(a-b)+(b-c)\in P$. Y cómo:
    $$(a-b)+(b-c) = a+(-b+b)-c = a-c$$
    Así $a-c \in P$ y por lo tanto $a>c$.
  2. Ya qué $b>a$ y $c>b$. Aplicando el punto anterior se sigue que:
    $$c> a \Rightarrow a < c$$

$\square$

El cuadrado de un número real

Proposición: Para todo $a\in \r$ se cumple lo siguiente:

$$a^{2} \geq 0$$

Demostración: Tomemos $a\in \r$. Por la propiedad O1 debemos considerar los siguientes tres casos.

  • Caso $a =0$:
    Cómo $a=0$, al multiplicar por $a$ en ambos lados de la igualdad tenemos:
    \begin{align*}
    a\cdot a &= 0\cdot a\\
    a\cdot a &= 0\cdot 0\\
    a^{2} &= 0\\
    \end{align*}
    Concluimos así $a^{2} \geq 0$.
  • Caso $a>0$
    Así $a\in P$ y por O3 tenemos que $a \cdot a \in P$. Por lo que $a^{2} \in P$, es decir, $a^{2}> 0$. Se concluye $a^{2} \geq 0$.
  • Caso $a< 0$
    Ahora tenemos que $-a\in P$ y por O3 que $-a \cdot -a \in P$. Así $a^{2}= (-a)(-a) \in P$, por lo que $a^{2} \geq 0$.

De los casos anteriores probamos $a^{2} \geq 0$ para todo $a\in \r$

$\square$

Tarea moral

Demuestra los puntos 3 y 4 de las Leyes de los signos.

  • Si $a>0$, $b<0$ entonces $a\cdot b < 0$.
    • Hint: Prueba $a\cdot (-b)$ es inverso aditivo de $ab$, es decir, $ab + a\cdot (-b) =0$
  • Si $a<0$, $b>0$ entonces $a\cdot b < 0$.
    • Hint: Aplica o prueba el resultado $(-a)(b)=-(ab)$.

Prueba los puntos 2 y 6 de la sección Algunos resultados…

  • Si $a<b$ y $c<0$ entonces $ac>bc$.
  • Si $a<b$ entonces $-b<-a$.

Muestre que para $a,b \in \r$ se cumplen las siguientes propiedades:

  • Si $a>1$ entonces $a^{2} > a$.
  • Si $0<a<1$ entonces $a^{2} < a$.
  • $$a< \sqrt{ab}< \frac{a+b}{2} <b$$

Más adelante

Ya que hemos definido las propiedades de orden y varios de sus resultados más importantes. En la siguiente entrada comenzaremos por definir a los intervalos en los reales y a resolver desigualdades apoyándonos en todo lo visto en esta entrada.

Entradas relacionadas