Archivo de la etiqueta: teoría de conjuntos

Teoría de los Conjuntos: Órdenes parciales y órdenes parciales estrictos

Introducción

En esta sección hablaremos de relaciones, sin embargo a partir de este momento le otorgaremos un orden a sus elementos. En esta sección comenzaremos definiendo a los órdenes parciales y a los órdenes parciales estrictos.

Orden parcial

Definición: Sea $R$ una relación sobre un conjunto $A$. Decimos que $R$ es una relación antisimétrica si y sólo si para cualesquiera $a,b\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$ implica que $a=b$.

Ejemplo:

Sea $A$ un conjunto y sea $R$ una relación definida como:

$aRb\ \text{si y sólo si} \ a\subseteq b$.

Veamos que $R$ es antisimétrica. En efecto, sean $a, b\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$, entonces por definición de $R$ tenemos que $a\subseteq b$ y $b\subseteq a$. Por lo tanto, $a=b$.

$\square$

Ejemplo:

Sea $A=\set{1,2,3,4}$ un conjunto y sea $R$ una relación definida como:

$R=\set{(1,1), (2,2), (3,3), (4,4)}$.

Tenemos que $R$ es una relación antisimétrica pues en este ejemplo cada elemento de $A$ se relaciona consigo mismo y sabemos que $1=1$, $2=2$, $3=3$ y $4=4$.

$\square$

Para la siguiente definición es necesario recordar el concepto de relación reflexiva y transitiva que puedes encontrar en el siguiente enlace: Teoría de los Conjuntos I: Relaciones de equivalencias.

Definición: Sea $R$ una relación en $A$, si $R$ es una relación reflexiva, antisimétrica y transitiva decimos que $(A, R)$ es un conjunto parcialmente ordenado.

Ejemplo:

Si $A=\emptyset$, entonces la relación $\emptyset$ es un orden parcial.

  1. Sea $a\in A$, entonces $(a, a)\in \emptyset$ se cumple por vacuidad. Por lo tanto, $\emptyset$ es una relación reflexiva.
  2. Sean $a,b\in A$ tales que $(a,b)\in \emptyset$ y $(b,a)\in \emptyset$, entonces $a=b$. Por lo tanto, $\emptyset$ es una relación antisimétrica.
  3. Sean $a,b,c\in A$ tales que $(a,b)\in \emptyset$ y $(b,a)\in \emptyset$, entonces $a=b$. Por lo tanto, $\emptyset$ es una relación antisimétrica.

$\square$

Ejemplo:

Si $A$ un conjunto y sea $R$ una relación en $A$ definida como sigue:

$aRb\ \text{si y sólo si} \ a\subseteq b$,

entonces la relación $R$ es un orden parcial.

  1. Sea $a\in A$, entonces $(a, a)\in R$ pues $a\subseteq a$ para cualquier conjunto $a$. Por lo tanto, $R$ es una relación reflexiva.
  2. Sean $a,b\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$, ya probamos que $a=b$. Por lo tanto, $R$ es una relación antisimétrica.
  3. Sean $a,b,c\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$, entonces $a\subseteq b$ y $b\subseteq c$ respectivamente. Luego, $a\subseteq b$ y $b\subseteq c$ implican que $a\subseteq c$. Por lo tanto, $(a,c)\in R$ y así, $R$ es una relación transitiva.

Por lo tanto, $R$ es un orden parcial.

$\square$

Dado que estamos ordenando elementos de un conjunto, usualmente usaremos $\leq$ para denotar a la relación de orden parcial, pues esta relación nos permite decir cuando un elemento es menor o igual que otro.

Orden parcial estricto

Definición: Sea $R$ una relación sobre un conjunto $A$. Decimos que $R$ es una relación asimétrica si y sólo si para cualesquiera $a,b\in A$ tales que $(a,b)\in R$ entonces no es cierto que $(b,a)\in R$.

Ejemplo:

Sea $A=\set{1,2,3}$ un conjunto y sea $R=\set{(1,2), (1,3)}$ es una relación asimétrica. En efecto, $(1,2)\in R$ pero $(2,1)\notin R$ y $(1,3)\in R$ pero $(3,1)\notin R$.

$\square$

Definición: Sea $R$ una relación sobre un conjunto $A$. Decimos que $R$ es una relación irreflexiva si y sólo si para cualquier $a\in A$ se tiene que $(a,a)\notin R$.

Ejemplo:

Sea $A=\set{1,2,3}$ un conjunto y sea $R=\set{(1,2), (1,3)}$ es una relación irreflexiva. En efecto, pues para cualquier elemento en $A$ en este caso $1, 2$ y $3$ se cumple que $(1,1)\notin R$, $(2,2)\notin R$ y $(3,3)\notin R$.

$\square$

Del ejemplo anterior podemos inferir que si $R$ es una relación asimétrica, entonces $R$ es irreflexiva. Vamos a demostrar esto último en la siguiente proposición.

Proposición: Sea $A$ un conjunto y $R$ una relación en $A$. Si $R$ es asimétrica, entonces $R$ es irreflexiva.

Demostración:

Supongamos que $R$ es una relación asimétrica, es decir, para cualesquiera $a,b\in A$ tales que $(a,b)\in R$ entonces $(b,a)\notin R$. Luego, sea $a\in A$ arbitrario. Veamos que $(a,a)\notin R$, supongamos por el contrario que $(a,a)\in R$ en busca de una contradicción. De aquí se tiene que existe $a\in A$ tal que $(a,a)\in R$ y $(a,a)\in R$ lo que contradice la asimetría de $R$. Por lo tanto, $(a,a)\notin R$ y así $R$ es irreflexiva.

$\square$

Definición: Sea $R$ una relación en $A$, si $R$ es una relación asimétrica y transitiva decimos que $(A, R)$ es un conjunto estrictamente ordenado.

Ejemplo:

Sea $A$ un conjunto cualquiera, la relación $\emptyset$ es un orden parcial estricto.

Si $A=\emptyset$ se cumple por vacuidad que $\emptyset$ es una relación asimétrica y transitiva. Por lo tanto, $\emptyset$ es un orden parcial estricto.

Supongamos ahora que $A\not=\emptyset$, verifiquemos las propiedades de asimetría y transitividad.

  1. Sean $a,b\in A$ tales que $(a,b)\in \emptyset$ entonces $(b,a)\notin \emptyset$ se satisface por vacuidad. Por lo tanto, $\emptyset$ es una relación asimétrica.
  2. Sean $a,b,c\in A$ tales que $(a,b)\in \emptyset$ y $(b,a)\in \emptyset$, entonces $a=b$. Por lo tanto, $\emptyset$ es una relación antisimétrica.

$\square$

Dado que estamos ordenando elementos de un conjunto, usualmente usaremos $<$ para denotar a la relación de orden parcial estricto, pues esta relación nos permite decir cuando un elemento es menor estricto que otro.

Tarea moral

La siguiente lista de ejercicios fortalecera el tema de ordenes parciales y el de órdenes parciales estrictos.

  • Si $A \not=\emptyset$, prueba que la pareja $(A,\emptyset)$ no es un orden parcial.
  • Demuestra que si $A$ es un conjunto y $R$ es la relación $\subset$ en $A$, entonces $(A, R)$ es un orden parcial estricto.
  • Argumenta porqué el concepto de no reflexividad es distinto al de irreflexividad.

Más adelante

En la siguiente sección estudiaremos a los órdenes totales, para hablar de tales órdenes retomaremos a los órdenes parciales y órdenes parciales estrictos. Además veremos el orden lexicográfico horizontal y vertical, tales ordenes se definen en el producto cartesiano de dos conjuntos ordenados.

Enlaces

En la siguiente entrada podrás encontrar más contenido acerca de órdenes parciales:

Álgebra Superior I: Órdenes parciales y totales

Teoría de los Conjuntos I: Conjunto cociente

Introducción

En esta entrada definiremos al conjunto cociente, dicho conjunto tendrá como elementos a las clases de equivalencia de una relación. Además probaremos que toda relación de equivalencia induce una partición y viceversa.

Concepto

Definición: Sea $R$ una relación de equivalencia en $A$, definimos al conjunto cociente por la relación $R$ como el conjunto:

$R\diagup A=\set{[a]_R: a\in A}$.

Ejemplo:

Sea $A=\set{1,2,3,4}$ y $R$ la relación identidad en $A$. Sabemos que $R$ es de equivalencia en $A$. Luego, siguiendo la definición de conjunto cociente tenemos que $R\diagup A=\set{[1]_R, [2]_R, [3]_R, [4]_R}$, donde $[1]_R=\set{1}$, $[2]_R=\set{2}$, $[3]_R=\set{3}$, $[4]_R=\set{4}$.

$\square$

Ejemplo:

Sea $A=\set{1,2,3,4}$ y $R=\set{(1,1), (2,2), (3,3), (4,4), (1,4), (4,1)}$ una relación de equivalencia en $A$. Luego, tenemos que

$R\diagup A=\set{[1]_R, [2]_R, [3]_R, [4]_R}$,

donde

  • $[1]_R=\set{1,4}$,
  • $[2]_R=\set{2}$,
  • $[3]_R=\set{3}$,
  • $[4]_R=\set{4,1}$.

Por lo tanto, $R\diagup A=\set{[1]_R, [2]_R, [3]_R}$

$\square$

Cada relación de equivalencia induce una partición

Teorema: Sea $R$ una relación de equivalencia en $A$, entonces el conjunto cociente $A\diagup R$ es una partición de $A$.

Demostración:

Supongamos que $R$ es una relación de equivalencia en $A$. Veamos que $A\diagup R$ es una partición de $A$.

  1. Sea $a\in A$, vimos en la entrada de particiones que $[a]_R\not=\emptyset$.
  2. Sean $[a]_R,[b]_R\in A\diagup R$ tales que $[a]_R\not=[b]_R$ y veamos que $[a]_R\cap [b]_R=\emptyset$. Supongamos que no ocurre que $[a]_R\cap [b]_R=\emptyset$, es decir, $[a]_R\cap [b]_R\not=\emptyset$ lo que es equivalente a que $[a]_R=[b]_R$
  3. Por último, $\bigcup_{a\in A} [a]_R= A$ pues para cada $a\in A$, $a\in [a]_R$.

$\square$

Este último teorema demuestra que toda relación de equivalencia induce una partición.

Las particiones inducen una relación de equivalencia

El teorema anterior nos permitió probar que cada relación de equivalencia induce una partición y de hecho, esta partición será el conjunto cociente, por lo que es válido preguntarnos si el resultado se cumple de regreso, es decir, dada una partición podemos inducir una relación de equivalencia. Veamos el siguiente ejemplo.

Ejemplo:

Sea $A=\set{0,1,2, 3, \cdots}$ y sean $A_1=\set{0,2,4,\cdots}$ y $A_2=\set{1,3, 5,\cdots}$. Resulta que $\mathcal{P}$ es una partición de $A$ pues tanto $A_1$ y $A_2$ son conjuntos no vacíos, además $A_1\cap A_2=\emptyset$ y $A_1\cup A_2=A$.

Queremos ver si existe la manera de relacionar a los elementos de $A$ tal que la relación que resulte sea de equivalencia. Consideremos la siguiente relación definida como sigue:

$R_\mathcal{P}=\set{(a,b)\in A^2: \exists A_i\in \mathcal{P}\ \text{tales que}\ a,b\in A_i}$.

Notemos que la relación $R_\mathcal{P}$ es una relación en $A$ y además relaciona a los elementos si pertenece a un mismo conjunto de la partición.

Veamos que $R_\mathcal{P}$ es una relación de equivalencia, para ello verifiquemos si es una relación reflexiva, simétrica y transitiva.

  1. Sea $a\in A$, si $a$ es un número par (existe $k$ tal que $a= 2k$), entonces $a\in A_1$ y por lo tanto, existe $A_1\in \mathcal{F}$ tal que $a\in A_1$ y así $(a,a)\in R_\mathcal{P}$.
    Si $a$ es un número impar (existe $k$ tal que $a= 2k+1$), entonces $a\in A_2$ y por lo tanto, existe $A_2\in \mathcal{P}$ tal que $a\in A_2$ y así $(a,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación reflexiva.
  2. Supongamos que $(a,b)\in R_\mathcal{P}$ y veamos que $(b,a)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ con $i\in \set{1,2}$ tal que $a, b\in A_i$. Lo que es equivalente a decir que existe $A_i\in \mathcal{P}$ con $i\in\set{1,2}$ tal que $b,a\in A_i$, es decir, $(b,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación simétrica.
  3. Supongamos que $(a,b)\in R_\mathcal{P}$ y $(b,c)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ con $i\in \set{1,2}$ tal que $a, b\in A_i$. Luego, como $(b,c)\in R_\mathcal{P}$ entonces existe $A_j\in \mathcal{P}$ con $j\in \set{1, 2}$ tal que $b,c\in A_j$. Luego $A_i=A_j$ pues de lo contrario $A_i\not= A_j$ y $b\in A_1$ al mismo tiempo que $b\in A_2$ y así, $b$ es par e impar, lo cuál no puede ocurrir. Por lo tanto, existe $A_i\in \mathcal{P}$ con $i\in \set{1,2}$ tal que $a,c\in A_i$ y así, $(a,c)\in R_\mathcal{P}$. Por lo tanto, $R_\mathcal{P}$ es una relación transitiva.

Por lo tanto, $R_\mathcal{P}$ es una relación de equivalencia.

$\square$

Podemos demostrar que esto ocurre para cualquier conjunto y cualquier partición. Veamos el siguiente teorema.

Teorema: Toda partición induce una relación de equivalencia.

Demostración:

Sea $A$ un conjunto y $\mathcal{P}=\set{A_i:i\in I}$ una partición de $A$. Defimos a $R_\mathcal{E}$ como el siguiente conjunto:

$R_\mathcal{P}=\set{(a,b)\in A\times A: \exists A_i\in \mathcal{P}\ \text{tal que}\ a,b\in A_i}$.

Notemos que $R_\mathcal{P}$ es una relación en $A$ pues es un subconjunto de $A\times A$. Veamos que $R$ es de equivalencia, es decir, $R$ es reflexiva, simétrica y transitiva.

  1. Sea $a\in A$, dado que $\mathcal{P}$ es una partición de $A$, entonces $A=\bigcup_{i\in I}A_i$. Entonces existe $j\in I$ tal que $a\in A_j$, de donde $(a,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación reflexiva.
  2. Supongamos que $(a,b)\in R_\mathcal{P}$ y veamos que $(b,a)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ tal que $a, b\in A_i$. Lo que es equivalente a decir que existe $A_i\in \mathcal{P}$ tal que $b,a\in A_i$, es decir, $(b,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación simétrica.
  3. Supongamos que $(a,b)\in R_\mathcal{P}$ y $(b,c)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ tal que $a, b\in A_i$. Luego, como $(b,c)\in R_\mathcal{P}$ entonces existe $A_j\in \mathcal{P}$ tal que $b,c\in A_j$. Además $A_i=A_j$ pues de lo contrario, $A_i\not= A_j$ y $b\in A_i$ al mismo tiempo que $b\in A_j$ y así, $b\in A_i\cap A_j=\emptyset$ lo cual es una contradicción. Por lo tanto, existe $A_i\in \mathcal{P}$ tal que $a,c\in A_i$ y así, $(a,c)\in R_\mathcal{P}$. Por lo tanto, $R_\mathcal{P}$ es una relación transitiva.

Por lo tanto, $R_\mathcal{P}$ es una relación de equivalencia en $A$.

$\square$

Con este último teorema hemos probado que en efecto, así como cada relación de equivalencia induce una partición, se cumple que cada partición induce una relación de equivalencia.

Tarea moral

La siguiente lista de ejercicios te ayudará a reforzar el contenido de esta entrada:

  • Demuestra que si $A$ es un conjunto y $R$ es una relación de equivalencia en $A$, entonces $A\diagup R$ es un conjunto.
  • Sea $A=\set{1,2,3,4,5,6}$ y $R=\set{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (5,6), (6,5), (4,6), (6,4), (4,5), (5,4)}$ relación de equivalencia en $A$. Determina al conjunto cociente de $A$ respecto de $R$.

Más adelante

En la siguiente sección continuaremos con algunos teoremas del conjunto cociente, dichos teoremas involucraran funciones.

Enlaces

Más sobre relaciones de equivalencia y clases de equivalencia:

Álgebra Superior I: Relaciones de equivalencia y clases de equivalencia

Teoría de los Conjuntos I: Funciones sobreyectivas y biyectivas

Introducción

En esta entrada hablaremos acerca de funciones sobreyectivas, este tipo de funciones serán aquellas cuya imagen sea todo el codominio. Tras definir este concepto podremos definir el concepto de función biyectiva, este último será de gran utilidad pues haremos uso de él cuando queramos estudiar conjunto a traves de otros conjuntos que tengan la misma cantidad de elementos.

Función sobreyectiva

Definición: Sea $f:X\to Y$ una función. Si $f[X]=Y$, entonces decimos que $f$ es sobreyectiva.

$\square$

Teorema: Sea $f:X\to Y$ una función. Entonces los siguientes enunciados son equivalentes:

  1. $f$ es sobreyectiva.
  2. Para cualquier $y\in Y$, existe $x\in X$ tal que $f(x)=y$.
  3. Para cualesquiera $h,k:Y\to Z$ tales que si $h\circ f= k\circ f$, entonces $h=k$.

Demostración:

$1)\rightarrow 2)$

Supongamos que $f$ es sobreyectiva, es decir que $f[X]=Y$. Sea $y\in Y$, entonces $y\in f[X]$ por lo que existe $x\in X$ tal que $f(x)=y$. Por lo tanto, para cualquier $y\in Y$ existe $x\in X$ tal que $f(x)=y$.

$2)\rightarrow 3)$

Sean $h,k:Y\to Z$ tales que $h\circ f=k\circ f$. Veamos que $h=k$. Sea $y\in Y$, veamos que $h(y)=k(y)$. Dado que $y\in Y$, por hipótesis tenemos que existe $x\in X$ tal que $f(x)=y$, por lo que $h(y)= h(f(x))$ y $k(y)= k(f(x))$. Luego, como $h\circ f(x)= h(f(x))= k(f(x))= k\circ f(x)$, tenemos que $h(y)= k(y)$.

$3)\rightarrow 1)$

Supongamos que $f$ no es sobreyectiva en busca de una contradicción. Sean $h: Y\to \set{\emptyset}$ y $k: Y\to \set{\emptyset, \set{\emptyset}}$ funciones dadas por $h(y)=\emptyset$ para todo $y\in Y$ y

\begin{align*}
k(y) = \left\{ \begin{array}{lcc}
\emptyset &  \text{si} & y\in f(X)\\
\set{\emptyset} &  \text{si}  & y \notin f(X) \\
\end{array}
\right.
\end{align*}

respectivamente. Notemos que $k\not=h$ pues dado que $f$ no es sobreyectiva, entonces existe $y_0\in Y$ tal que $y_0\notin f[X]$. Así, $h(y_0)= \emptyset$ y $k(y_0)=\set{\emptyset}$, por lo tanto, $h\not=k$.

Luego, $h\circ f= k\circ f$. Sea $x\in X$, entonces $f(x)\in Y$ y así, $h\circ f(x)= h(f(x))= \emptyset$ y $k\circ f(x)= k(f(x))= \emptyset$. Por lo tanto, debe ocurrir que $h=k$, lo cuál es una contradicción.

Así, $f$ es sobreyectiva.

$\square$

Algunas funciones sobreyectivas

Ejemplo:

La función identidad es sobreyectiva. En efecto, sea $Id_X:X\to X$ la función identidad y sea $y\in X$, entonces existe $y\in X$ tal que $Id_X(y)= y$.

Por lo tanto, $Id_X$ es sobreyectiva.

$\square$

Ejemplo:

Sea $f:X\to \set{c}$ una función dada por $f(x)=c$ para todo $x\in X$. Tenemos que $f$ es sobreyectiva.

En efecto, sea $y\in \set{c}$. Dado que $y\in \set{c}$, entonces $y=c$. veamos que existe $x\in X$ tal que que $f(x)=c$. Esto último se cumple por como esta definida la función $f$.

$\square$

Ejemplo:

Sea $X$ un conjunto y $A\subseteq X$, la función característica de $A$ es una función sobreyectiva.

Dado que el codominio de la función característica es el conjunto $\set{\emptyset, \set{\emptyset}}$, deseamos ver que para cualquier $y\in \set{\emptyset, \set{\emptyset}}$ existe $x\in X$ tal que $\chi_A(x)=y$.

Caso 1: Si $y=\emptyset$, entonces existe $x\in X$ tal que $x\notin A$, de modo que $\chi_A(x)=\emptyset$.

Caso 2: Si $y=\set{\emptyset}$, entonces existe $x\in X$ tal que $x\in A$, de modo que $\chi_A(x)=\set{\emptyset}$.

Por lo tanto, $\chi_A$ es sobreyectiva.

$\square$

Composición de funciones

Así como lo hicimos en la sección anterior con respecto a la inyectividad, podemos averiguar que pasa con la composición de funciones con respecto a la sobreyectividad. Veamos el siguiente teorema:

Teorema: Sean $f:X\to Y$ y $g:Y\to Z$ funciones sobreyectivas, $g\circ f$ es sobreyectiva.

Demostración:

Sea $z\in Z$, veamos que existe $x\in X$ tal que $g\circ f(x)=z$.
Dado que $g$ es sobreyectiva y $z\in Z$, entonces existe $y\in Y$ tal que $g(y)=z$. Luego, como $f$ es sobreyectiva y $y\in Y$, entonces existe $x\in X$ tal que $f(x)=y$, así $g(y)=g(f(x))= z$. Por lo tanto, $g\circ f$ es sobreyectiva.

$\square$

Funciones biyectivas

Definición: Decimos que $f:X\to Y$ es una función biyectiva si y sólo si $f$ es inyectiva y sobreyectiva.

Ejemplo:

La función identidad es biyectiva.

Verificamos en la sección de funciones inyectivas que la función identidad es una función inyectiva, además de que en esta sección verificamos que es sobreyectiva.

$\square$

Ejemplo:

Sean $X=\set{1,2,3}$ y $Y=\set{2,4,6}$ y sea $f:X\to Y$ una función dada por $f(x)=2x$. Tenemos que $f$ es inyectiva pues es una función uno a uno, es decir, elementos distintos van a dar a elementos distintos. Más explícitamente $1$ va a dar a $2$, $2$ a $4$ y $3$ a $6$.

Además $f$ es sobreyectiva, pues para cualquier $y\in Y$, existe $x\in X$ tal que $f(x)=y$. En efecto, ya que para $2\in Y$ existe $1\in X$ tal que $f(1)=2$; para $4\in Y$ existe $2\in X$ tal que $f(2)=4$ y por último para $6\in Y$ existe $3\in X$ tal que $f(3)=6$.

$\square$

Tarea moral

Realiza la siguiente lista de ejercicios que te ayudara a fortalecer los conceptos de función inyectiva, sobreyectiva y biyectiva:

  1. Sean $f:X\to Y$ y $g:Y\to Z$ funciones. Demuestra que si $g\circ f$ es sobreyectiva, entonces $g$ es sobreyectiva.
  2. Demuestra o da un contraejemplo del siguiente enunciado: Si $f:X\to Y$ y $g:Y\to Z$ son funciones tales que $g\circ f$ es sobreyectiva, entonces $f$ es sobreyectiva.
  3. Sean $X=\set{1,2,3, \cdots}$ y $Y=\set{3,4,5,\cdots}$ y sea $f:X\to Y$ dada por $f(x)=2x+3$. ¿$f$ es sobreyectiva? Argumenta tu repuesta.

Más adelante

Ahora que aprendimos el concepto de función inyectiva y sobreyectiva tenemos las bases suficientes para hablar de funciones invertibles. Veremos funciones invertibles por la derecha e invertibles por la izquierda, cuyos conceptos resultarán equivalentes al de función sobreyectiva y función inyectiva respectivamente.

Enlaces

En el siguiente enlace podrás encontrar más contenido acerca de funciones inyectivas y sobreyectivas:

Funciones inyectivas y sobreyectivas

Teoría de los Conjuntos I: Funciones inyectivas

Introducción

En esta sección abordaremos el concepto de función inyectiva, notaremos que la función inyectiva será aquella que mande elementos distintos a elementos distintos bajo una función.

Función inyectiva

Definición: Sea $f: X \to Y$ una función. Decimos que $f$ es una función inyectiva si para cualesquiera $x_1$, $x_2 \in X$ tales que $x_1\not=x_2$ implica que $f(x_1)\not= f(x_2)$.

Ejemplo:

Sean $X=\set{1,2,3,4}$ y $Y=\set{1,2,3,4,5}$ y sea $f:X\to Y$ una función dada por $f=\set{(1,2), (2,1), (3,3), (4,5)}$. Decimos que $f$ es inyectiva pues cada elemento de $X$ bajo la función va a dar a uno y sólo uno de $Y$, como se muestra en la siguiente imagen:

Ejemplo: La función identidad es una función inyectiva.

En efecto, dado que $Id_X:X\to X$ esta dada por $Id_X(x)=x$, entonces si $x_1,x_2\in X$ son tales que $Id_X(x_1)=x_1=x_2=Id_X(x_2)$, entonces $x_1=x_2$ y por lo tanto, $Id_X$ es inyectiva.

$\square$

Ejemplo: La función constante no es inyectiva.

Consideremos $X=\set{1,2,3}$ y $Y=\set{1}$. Sea $f:X\to Y$ una función dada por $f(x)=1$ para toda $x\in X$. Consideremos $x_1=1$ y $x_2=2$ elementos de $X$, sabemos que $1\not=2$ por lo que para que nuestra función sea inyectiva esperamos que $f(x_1)\not=f(x_2)$, sin embargo, $f(1)=1=f(2)$. Esto demuestra que en general las funciones constantes no son inyectivas.

$\square$

Equivalencias de inyectividad

Teorema: Sea $f:X\to Y$ una función tal que $X\not=\emptyset$. Entonces los siguientes enunciados son equivalentes:

  1. $f$ es inyectiva.
  2. Para cualesquiera $x_1,x_2\in X$ tales que $f(x_1)=f(x_2)$ entonces $x_1=x_2$,
  3. Para cualesquiera $h,k:Z\to X$ tales que si $f\circ h= f\circ k$, entonces $h=k$,
  4. Para cualesquiera $A,B$ subconjuntos de $X$, se cumple que $f[B\setminus A]= f[B]\setminus f[A]$,
  5. Para cualesquiera $A,B$ subconjuntos de $X$ se cumple que $f[A\cap B]= f[A]\cap f[B]$.

Demostración:

$1)\rightarrow 2)$
Supongamos que $f$ es inyectiva, esto es para cualesquiera $x_1, x_2\in X$ tales que $x_1\not=x_2$ implica que $f(x_1)\not=f(x_2)$. Luego, sabemos que la implicación es equivalente a la contrapositiva por lo que podemos concluir que para cualesquiera $x_1, x_2\in X$, si $f(x_1)=f(x_2)$ entonces $x_1=x_2$.

$2)\rightarrow 3)$
Supongamos que para cualesquiera $x_1, x_2\in X$ tales que $f(x_1)=f(x_2)$ entonces $x_1= x_2$ y supongamos que $h,k:Z\to X$ son funciones tales que $f\circ h= f\circ k$ y veamos que $h=k$.

Sea $z\in Z$, entonces $h(z)\in X$ y $k(z)\in X$, luego como $f\circ h=f\circ k$ tenemos que $f\circ h(z)= f\circ k(z)$, de donde $f(h(z))= f(k(z))$ y como $f$ es inyectiva entonces $h(z)=k(z)$. Por lo tanto, $h=z$.

$3)\rightarrow 4)$

Supongamos que $h,k:Z\to X$ son funciones tales que si $f\circ h= f\circ k$, entonces $h=k$. Supongamos también que para cualesquiera $A,B$ conjuntos tales que $A\subseteq B\subseteq X$ y veamos que $f[B\setminus A]= f[B]\setminus f[A]$.

En la sección de funciones vimos que siempre ocurre que $f[B]\setminus f[A]\subseteq f[B\setminus A]$ por lo que basta ver la otra contención.

Sea $y\in f[B\setminus A]$, entonces existe $x\in B\setminus A$ tal que $f(x)=y$. Luego, $x\in B\setminus A$ por lo que $x\in B$ y $x\notin A$, de modo que $f(x)\in f[B]$. Resta ver que $f(x)\notin f[A]$, supongamos que si ocurre, es decir que $f(x)\in f[A]$. Entonces existe $z\in A$ tal que $f(z)=f(x)$.

Sean $h:X\to X$ dada por $h(a)=x$ para todo $a\in X$ y $k:X\to X$ dada por $k(a)=z$ para todo $a\in X$. Notemos que $h\not=k$ pues $z\not=x$ ya que $z\in A$ y $x\notin A$. Luego, $f\circ h(a)=f(h(a))= f(x)$ y $f\circ k(a)= f(k(a))= f(z)=f(x)$, por lo que $f\circ h=f\circ k$. Así, por hipótesis se sigue que $h=k$ lo cuál es una contradicción, por lo tanto, no debe ocurrir que $f(x)\in f[A]$. Así, $f(x)\in f[B]\setminus f[A]$.

$4)\rightarrow 5)$

Supongamos que para cualesquiera $A, B$ subconjuntos de $X$, se cumple que $f[B\setminus A]=f[B]\setminus f[A]$. Veamos que $f[A\cap B]= f[A]\cap f[B]$.

En la sección de funciones probamos que $f[A\cap B]\subseteq f[A]\cap f[B]$, por lo que basta ver que $f[A]\cap f[B]\subseteq f[A\cap B]$.

Sea $y\in f[A]\cap f[B]$, entonces $y\in f[A]$ y $y\in f[B]$, así existe $x\in A$ tal que $f(x)=y$. Queremos demostrar que $x\in B$, supongamos que no es así, es decir $x\notin B$, entonces existe $x\in A\setminus B$ tal que $f(x)=y$, por lo que $y\in f[A\setminus B]= f[A]\setminus f[B]$.

Se sigue que $y\in f[A]$ y $y\notin f[B]$ lo cual es una contradicción, por lo tanto, debe ocurrir que $x\in B$, así existe $x\in A\cap B$ tal que $f(x)=y$.

Por lo tanto, $f[A]\cap f[B]= f[A\cap B]$.

$5)\rightarrow 1)$

Supongamos que para cualesquiera $A, B\subseteq X$ se cumple que $f[A]\cap f[B]= f[A\cap B]$.

Sean $x_1, x_2\in X$ tales que $x_1\not= x_2$, veamos que $f(x_1)\not= f(x_2)$.

Consideremos $\set{x_1}$ y $\set{x_2}$ subconjuntos de $X$. Luego,

\begin{align*}
f[\set{x_1}\cap \set{x_2}]&=f[\emptyset]\ \text{pues} \ x_1\not=x_2\\
&=f[\set{x_1}]\cap f[\set{x_2}]\ \text{por hipótesis}\\
&=\set{f(x_1)}\cap \set{f(x_2)}
\end{align*}

Luego, como $\set{f(x_1)}\cap \set{f(x_2)}=\emptyset$ entonces $\set{f(x_1)}\not=\set{f(x_2)}$ y por lo tanto, $f(x_1)\not=f(x_2)$.

Por lo tanto, $f$ es inyectiva.

Por lo tanto, todos los enunciados anteriores son equivalentes.

$\square$

Aunque existen muchas equivalencias de función inyectiva para este curso usaremos con mayor frecuencia la equivalencia dos.

¿Qué pasa con la composición?

Anteriormente definimos a la composición de funciones que resulta ser una función, por lo que podemos preguntarnos que ocurre si las funciones que conforman a la composición son inyectivas, es decir si eso implica que la composición es inyectiva, veamos que nos dice el siguiente teorema.

Teorema: Sean $f:X\to Y$ y $g:Y\to Z$ funciones inyectivas. Se cumple que $g\circ f$ es inyectiva.

Demostración:

Sean $f$ y $g$ funciones inyectivas y sean $x_1, x_2\in X$ tales que $g\circ f(x_1)= g(f(x_1))=g(f(x_2))= g\circ f(x_2)$. Dado que $f(x_1), f(x_2)\in Y$ y $g$ es inyectiva, entonces $ g(f(x_1))=g(f(x_2)) $ implica que $f(x_1)=f(x_2)$. Por la inyectividad de $f$ podemos concluir que $x_1=x_2$. Por lo tanto, $g\circ f$ es una función inyectiva.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el tema de funciones inyectivas.

  • Demuestra que la función inclusión es inyectiva.
  • Sean $A=\set{1,2,3}$, $B=\set{1,2}$ y $C=\set{1,2}$ conjuntos. Sean $f:A\to B$ y $g:B\to C$ funciones dadas por $f=\set{(1,1), (2,1), (3,2)}$ y $g=set{(1,2), (2,1)}$ respectivamente. Escribe al conjunto $g\circ f$ y ve si es inyectiva. Argumenta tu respuesta.
  • Si $f\circ g$ es inyectiva, ¿es cierto que $f$ y $g$ son inyectivas?
  • Demuestra que la función $\emptyset$ es inyectiva.
  • Demuestra que $f:X\to Y$ una función constante es inyectiva si y sólo si $X=\set{x}$.

Más adelante

En la siguiente sección abordaremos el tema de funciones sobreyectivas. Con este tema tendremos los conceptos necesarios para comenzar a hablar acerca de funciones biyectivas e invertibles.

Enlaces

En el siguiente enlace podrás encontrar más contenido acerca de funciones inyectivas.

Álgebra Superior I: Funciones inyectivas, suprayectivas y biyectivas

Teoría de los conjuntos I: Funciones (parte II)

Introducción

En esta sección hablaremos acerca de algunas propiedades de la imagen y la imagen inversa de un conjunto bajo una función, dichas propiedades hablan de como se comportan estos conjuntos con respecto a la unión, la intersección y la diferencia.

Propiedades

Teorema: Sean $X$ y $Y$ conjuntos y sea $f:X\to Y$ una función. Sean $X_1,X_2\subseteq X$ y $Y_1, Y_2\subseteq Y$. Entonces se cumplen las siguientes propiedades:

  1. Si $X_1\subseteq X_2$, entonces $f[X_1]\subseteq f[X_2]$,
  2. $f[X_1\cup X_2]=f[X_1]\cup f[X_2]$,
  3. $f[X_1\cap X_2]\subseteq f[X_1]\cap f[X_2]$,
  4. $f[X_1]\setminus f[X_2]\subseteq f[X_1\setminus X_2]$,
  5. Si $Y_1\subseteq Y_2$, entonces $f^{-1}[Y_1]\subseteq f^{-1}[Y_2]$,
  6. $f^{-1}[Y_1\cup Y_2]=f^{-1}[Y_1]\cup f[Y_2]$,

Demostración:

1) Supongamos que $X_1\subseteq X_2$ y veamos que $f[X_1]\subseteq f[X_2]$.
Sea $y\in f[X_1]$, entonces existe $x\in X_1$ tal que $f(x)=y$. Dado que $X_1\subseteq X_2$, entonces existe $x\in X_2$ tal que $f(x)=y$, esto es $y\in f[X_2]$.
Por lo tanto, $f[X_1]\subseteq f[X_2]$.

2) Veamos que $f[X_1\cup X_2]=f[X_1]\cup f[X_2]$.

$\subseteq$] Sea $y\in f[X_1\cup X_2]$, entonces existe $x\in X_1\cup X_2$ tal que $f(x)= y$. Entonces existe $x\in X_1$ o $x\in X_2$ tal que $f(x)=y$.
Si $x\in X_1$ tal que $f(x)=y$ entonces $y\in f[X_1]$ y por lo tanto $y\in f[X_1]\cup f[X_2]$.
Si $x\in X_2$ tal que $f(x)=y$ entonces $y\in f[X_2]$ y por lo tanto $y\in f[X_1]\cup f[X_2]$.
Por lo tanto, $f[X_1\cup X_2]\subseteq f[X_1]\cup f[X_2]$.

$\supseteq$] Sea $y\in f[X_1]\cup f[X_2]$, entonces $y\in f[X_1]$ o $y\in f[X_2]$.

Si $y\in f[X_1]$, entonces existe $x\in X_1$ tal que $f(x)=y$. Luego, como $X_1\subseteq X_1\cup X_2$, tenemos que $x\in X_1\cup X_2$. Por lo tanto, existe $x\in X_1\cup X_2$ tal que $f(x)=y$, esto es $y\in f[X_1\cup X_2]$.

Si $y\in f[X_2]$, entonces existe $x\in X_2$ tal que $f(x)=y$. Luego, como $X_2\subseteq X_1\cup X_2$, tenemos que $x\in X_1\cup X_2$. Por lo tanto, existe $x\in X_1\cup X_2$ tal que $f(x)=y$, esto es $y\in f[X_1\cup X_2]$.

Por lo tanto, $f[X_1]\cup f[X_2]\subseteq f[X_1\cup X_2]$.

De las contenciones que demostramos tenemos que $f[X_1]\cup f[X_2]=f[X_1\cup X_2]$.

3) Ahora veamos que $f[X_1\cap X_2]\subseteq f[X_1]\cap f[X_2]$.

Sea $y\in f[X_1\cap X_2]$, entonces existe $x\in X_1\cap X_2$ tal que $f(x)= y$. Entonces existe $x\in X_1$ y $x\in X_2$ tal que $f(x)=y$.

Entonces existe $x\in X_1$ tal que $f(x)=y$ y existe $x\in X_2$ tal que $f(x)=y$, de donde $y\in f[X_1]$ y $y\in f[X_2]$. Por lo tanto, $y\in f[X_1]\cap f[X_2]$.

Así, $f[X_1\cap X_2]\subseteq f[X_1]\cap f[X_2]$.

4) A continuación mostraremos que $f[X_1]\setminus f[X_2]\subseteq f[X_1\setminus X_2]$.

Sea $y\in f[X_1]\setminus f[X_2]$, entonces $y\in f[X_1]$ y $y\notin f[X_2]$.

Dado que $y\in f[X_1]$, entonces existe $x\in X_1$ tal que $f(x)=y$. Luego, como $y\notin f[X_2]$ entonces para cualquier $a\in X_2$, $f(a)\not=y$. Resulta que $x\notin X_2$ pues de lo contrario $f(x)\not=y$ lo cual no puede ocurrir.

Por lo tanto, existe $x\in X_1\setminus X_2$ tal que $f(x)=y$, esto es, $y\in f[X_1\setminus X_2]$.

5) Supongamos que $Y_1\subseteq Y_2$ y veamos que $f^{-1}[Y_1]\subseteq f^{-1}[Y_2]$.
Sea $x\in f^{-1}[Y_1]$, entonces existe $y\in Y_1$ tal que $f(x)=y$. Dado que $Y_1\subseteq Y_2$, entonces existe $y\in Y_2$ tal que $f(x)=y$, esto es $x\in f^{-1}[Y_2]$.
Por lo tanto, $f^{-1}[Y_1]\subseteq f^{-1}[Y_2]$.

6) Finalmente veamos que $f^{-1}[Y_1\cup Y_2]=f^{-1}[Y_1]\cup f^{-1}[Y_2]$.

Sea $x\in f^{-1}[Y_1\cup Y_2]$, entonces existe $y\in Y_1\cup Y_2$ tal que $f(x)=y$. Luego, como $y\in Y_1\cup Y_2$ se tiene que $y\in Y_1$ o $y\in Y_2$.

Si $y\in Y_1$, entonces existe $y\in Y_1$ tal que $f(x)=y$, es decir, $x\in f^{-1}[Y_1]$. Por lo tanto $x\in f^{-1}[Y_1]\cup f^{-1}[Y_2]$.

Si $y\in Y_2$, entonces existe $y\in Y_2$ tal que $f(x)=y$, es decir, $x\in f^{-1}[Y_2]$. Por lo tanto $x\in f^{-1}[Y_1]\cup f^{-1}[Y_2]$.

$\square$

¿Por qué $f[X_1\cap X_2]\not=f[X_1]\cap f[X_2]$?

Ya vimos que $f[X_1\cap X_2]\subseteq f[X_1]\cap f[X_2]$, por lo que al igual que con la unión podríamos pensar que se da la igualdad entre los conjuntos. Sin embargo, vamos a ver que $f[X_1]\cap f[X_2]\not\subseteq f[X_1\cap X_2]$.

Con el siguiente ejemplo mostraremos que no siempre es posible que $f[X_1]\cap f[X_2]\not\subseteq f[X_1\cap X_2]$.

Ejemplo:

Sean $X=\set{0,1,2}$ y $Y=\set{1,2,3}$ conjuntos y sea $f:X\to Y$ una función dada por el conjunto $f(x)=2$ Sean $X_1=\set{0,1}$ y $X_2=\set{2}$ subconjuntos de $X$.

Por un lado tenemos que $X_1\cap X_2=\set{0,1}\cap \set{2}=\emptyset$, por lo que $f[X_1\cap X_2]=f[\emptyset]= \emptyset$.

Por otro lado, $f[X_1]=f[\set{0,1}]=\set{2}$ y $f[X_2]=f[\set{2}]=\set{2}$. Así, $f[X_1]\cap f[X_2]=\set{2}$.

Por lo tanto, $f[X_1]\cap f[X_2]\not\subseteq f[X_1\cap X_2]$.

$\square$

¿Por qué $f[X_1\setminus X_2]\not=f[X_1]\setminus f[X_2]$?

Ya vimos que $f[X_1]\setminus f[X_2]\subseteq f[X_1\setminus X_2]$, pero va a resultar que la contención de regreso no es posible, es decir, $f[X_1\setminus X_2]\not\subseteq f[X_1]\setminus f[X_2]$.

Con el siguiente ejemplo mostraremos que no siempre es posible que $f[X_1\setminus X_2]\not\subseteq f[X_1]\setminus f[X_2]$.

Ejemplo:

Sean $X=\set{0,1,2}$ y $Y=\set{1,2,3}$ conjuntos y sea $f:X\to Y$ una función dada por el conjunto $f(x)=2$ Sean $X_1=\set{0,1}$ y $X_2=\set{1,2}$ subconjuntos de $X$.

Por un lado tenemos que $X_1\setminus X_2=\set{0,1}\setminus \set{1,2}=\set{0}$, por lo que $f[X_1\setminus X_2]=f[\set{0}]= \set{2}$.

Por otro lado, $f[X_1]=f[\set{0,1}]=\set{2}$ y $f[X_2]=f[\set{1,2}]=\set{2}$. Así, $f[X_1]\setminus f[X_2]=\emptyset$.

Por lo tanto, $f[X_1\setminus X_2]\not\subseteq f[X_1]\setminus f[X_2]$.

$\square$

Composición de funciones

Definición: Sean $f:X\to Y$ y $g:Y\to Z$ funciones. Definimos a la composición de $f$ con $g$ como la función $g\circ f:X\to Z$ dada por $g\circ f(x)= g(f(x))$ para cualquier $x\in X$.

Teorema: Si $f:X\to Y$ y $g:Y\to Z$ son funciones, entonces $g\circ f:X\to Z$ es función.

En la sección de composición de relaciones vimos que si $f$ y $g$ son relaciones, entonces $g\circ f$ es relación, por lo que resta ver que si $(a,b)\in g\circ f$ y $(a,c)\in g\circ f$, entonces $b=c$.

Supongamos que $(a,b)\in g\circ f$ y $(a,c)\in g\circ f$, esto es $b=g(f(a))$ y $c=g(f(a))$ y por lo tanto, $b=c$.

$\square$

Ejemplo:

Sea $f:\set{1,2}\to \set{2,4}$ y $g:\set{2,4}\to \set{3,5}$ funciones dadas por $f(x)= 2x$ y $g(x)=x+1$ respectivamente. Entonces $g\circ f:\set{1,2}\to \set{3,5}$ está dada por:

$g\circ f(x)=g(f(x))=g(2x)=2x+1$

Por lo que,

  • $g\circ f(1)=2(1)+1=2+1=3$,
  • $g\circ f(2)= 2(2)+1=4+1=5$.

De modo que los elementos de $g\circ f$ son $(1,3)$ y $(2,5)$.

$\square$

Tarea moral

a) Demuestra que si $X$ y $Y$ son conjuntos y $f:X\to Y$ una función. Sean $X_1\subseteq X$ y $Y_1, Y_2\subseteq Y$. Entonces se cumplen las siguientes propiedades:

  1. $f^{-1}[Y_1\cap Y_2]=f^{-1}[Y_1]\cap f[Y_2]$,
  2. $f^{-1}[Y_1\setminus Y_2]=f^{-1}[Y_1]\setminus f[Y_2]$,
  3. $X_1\subseteq f^{-1}[f[X_1]]$,
  4. $f[f^{-1}[B_1]]\subseteq B_1$.

b) Demuestra que la composición de funciones es asociativa.

Más adelante

La siguiente sección estará dedicada a funciones inyectivas y sobreyectivas. Este tema será de gran importancia pues en muchas ocasiones tendremos que verificar si se satisfacen estas propiedades.

Enlaces

Álgebra Superior I: Introducción a funciones