> Conjuntos

Conjuntos

Construcciones básicas

Comenzaremos dando una noción intuitiva de uno de los conceptos matemáticos más utilizados: el de conjunto. Sin embargo no daremos una definición rigurosa. ¿Sabes por qué?

Definición

Un conjunto es una colección de elementos. Normalmente están caracterizados por compartir alguna propiedad. Para que un conjunto esté bien definido debe ser posible discernir si un elemento arbitrario está o no en él.

Los conjuntos pueden definirse de manera explícita, citando todos los elementos de los que consta entre llaves,

$A = \{ 1,2,3,4,5 \},$

o implícita, dando una o varias características que determinen si un elemento dado está o no en el conjunto,

$A = \{ \text{números naturales del }1\text{ al }5\}.$

Los elementos de un conjunto no están ordenados, aunque vengan especificados como una lista, por tanto $A=\{3,1,2,5,4\}$ . En una definición explícita no se pueden repetir elementos, así que $\{1,1,2,3,4,5\}$ sería una manera incorrecta de expresar el conjunto $A$ .

Conjuntos de números

$\mathbb{N}$ , los números naturales: 1, 2, 3, …
$\mathbb{N}_0$ , los números naturales más el cero: 0, 1, 2, 3, …
$\mathbb{Z}$ , los números enteros: …, -2, -1, 0, 1, 2, …
$\mathbb{Q}$ , los números racionales: $\frac{p}{q}$ .
$\mathbb{R}$ , los números reales.
$\mathbb{C}$ , los números complejos.

Definición

Dado un conjunto $A$ , decimos que el elemento $a$ pertenece a $A$ , y lo denotamos $a\in A$ , si $a$ es un elemento del conjunto $A$ .

Muchos símbolos matemáticos son reversibles, por ejemplo, $A\ni a$ significa lo mismo que $a\in A$ . También muchos son negables, así $a\notin A$ significa que $a$ no pertenece a $A$ .

Por ejemplo, si $A = \{ 1,2,3,4,5 \}$ entonces $1 \in A$ pero $6\notin A$ . Otra manera implícita de expresar este conjunto $A$ es la siguiente:

$A = \{n|n\in\mathbb{N} \wedge 1\leq n\leq 5\}.$

Se lee del siguiente modo: “ $A$ es el conjunto formado por los elementos $n$ tales que $n$ pertenece al conjunto los números naturales, $n$ es mayor o igual que 1 y $n$ es menor o igual que 5.”

Definición

Dos conjuntos $A$ y $B$ son iguales $A=B$ cuando poseen los mismos elementos, es decir, cuando $x\in A\Leftrightarrow x\in B$ .

Deducimos que dos conjuntos $A$ y $B$ son distintos $A\neq B$ si bien existe $x\in A$ tal que $x\notin B$ o bien existe $x\in B$ tal que $x\notin A$ . En notación matemática: $A\neq B\Leftrightarrow(\exists x\in A|x\notin B)\vee(\exists x\in B|x\notin A).$

Definición

El conjunto vacío $\varnothing$ es el que carece de elementos, es decir $\varnothing=\{\}$ , o bien $\forall x, x\notin \varnothing$ .

Un conjunto es unitario si contiene un único elemento, como por ejemplo $\{0\}$ , $\{1\}$ , $\{a\}$ , $\{$ cartón de leche $\}$ , $\{\mathbb{N}\}$ , …

¡Ojo! $x\in\{x\}$ , pero $x\neq\{x\}$ , de hecho, como demuestra la paradoja de Russell, es imposible que un conjunto pertenezca a sí mismo.

Definición

Dados dos conjuntos $A$ y $B$ , decimos que $A$ está contenido o incluído en $B$ o que $A$ es un subconjunto de $B$ , y lo denotamos $A\subset B$ , si todo elemento de $A$ pertenece a $B$ , es decir $x\in A \Rightarrow x\in B$ .

También se puede denotar $A\subset B$ como $A\subseteq B$ . Hay que tener cuidado con la negación de estos dos símbolos. Tanto $A\not\subset B$ como $A\not\subseteq B$ significan que $A$ no está contenido en $B$ , o no es un subconjunto de $B$ . Sin embargo $A\subsetneq B$ solo niega la igualdad, por lo que significa que $A$ es un subconjunto de $B$ pero que $A$ no es igual a $B$ , es decir, la contención es estricta. Por ejemplo, $\{2,3,5\}\subsetneq\{1,2,3,4,5\}$ .

La contención es transitiva, $A\subset B\subset C\Rightarrow A\subset C$ . También es reflexiva, $A\subset A$ . Además, el vacío está contenido en cualquier conjunto $\varnothing\subset A$ . Los subconjuntos de $A$ distintos de $\varnothing$ y $A$ se denominan subconjuntos propios de $A$ .

El siguiente resultado caracteriza la igualdad entre dos conjuntos en términos de contenciones. Es la base de una técnica de prueba conocida como doble inclusión, que aplicaremos con frecuencia.

Proposición

$A=B$ $\Leftrightarrow$ $A\subset B$ y $A\supset B$ .

Prueba

$A\subset B$ es lo mismo que $x\in A \Rightarrow x\in B$ y $A\supset B$ equivale a $x\in A \Leftarrow x\in B$ , por tanto ambas simultáneamente significan $x\in A \Leftrightarrow x\in B$ , que es lo mismo que $A=B$ .

Cualquier enunciado matemático debe venir seguido de una prueba. Se usan diversos términos para denominar a los enunciados matemáticos, de acuerdo con la percepción que tengamos de su importancia o dificultad. De mayor a menor:

Teorema.
Proposición.
Lema.
Corolario.

Los lemas suelen tener un carácter técnico y presentarse como pasos intermedios en la demostración de un resultado de mayor envergadura. Los corolarios se enuncian habitualmente después de un resultado más importante y su prueba suele ser obvia y omitirse.

Definición

Dados dos conjuntos $A$ y $B$ la intersección $A \cap B$ es el conjunto formado por aquellos elementos que pertenecen a ambos conjuntos, $A \cap B = \{ x | x \in A \wedge x \in B \}$ .

Si $C\subset A$ y $C\subset B$ entonces $C\subset A\cap B$ .

Teorema

La intersección de conjuntos verifica las siguientes propiedades, donde $A$ , $B$ y $C$ son conjuntos cualesquiera:

$A \cap B = B \cap A$ (conmutativa).
$(A \cap B) \cap C = A \cap (B \cap C)$ (asociativa).
$A \cap B \subset A$ .
$A \cap B \subset B$ .
$\varnothing \cap A = \varnothing$ .
$A \subset B\Leftrightarrow A \cap B = A.$

Prueba

Los elementos de $A \cap B$ son los que pertenecen a $A$ y a $B$ , que son los mismos que pertenecen a $B$ y a $A$ .

Las dos intersecciones triples son el mismo conjunto porque representan a los elementos que están en $A$ , $B$ y $C$ .

Los elementos que están en $A$ y en $B$ están, en particular, en $A$ . También en $B$ .

La quinta igualdad la demostramos por doble inclusión. La inclusión $\supset$ es siempre cierta y $\subset$ es consecuencia de un apartado anterior.

Demostremos la equivalencia del último apartado. Probemos primero $\Rightarrow$ . Supongamos pues que $A\subset B$ . Demostraremos la igualdad de la derecha por doble inclusión. La inclusión $\subset$ es siempre cierta. Veamos $\supset$ . Como $A\subset B$ , todo elemento de $A$ está también en $B$ , y por tanto en la intersección. Probemos ahora $\Leftarrow$ . Esto es consecuencia de que $A\cap B\subset B$ .

Estas propiedades nos permiten definir inductivamente la intersección de una cantidad finita de conjuntos $A_1\cap\cdots\cap A_n$ . Consiste en los elementos que están en todos ellos.

Veamos el caso posiblemente infinito.

Definición

Dado un conjunto $I$ , una familia de conjuntos indexada por $I$ consiste en dar un conjunto $A_i$ para cada $i\in I$ . Se denota como $\{ A_i \}_{i\in I}$ .

La intersección de una familia de conjuntos se define como $\bigcap_{i\in I}A_i=\{x|\forall i\in I, x\in A_i\}$ .

Si $I$ es finito, esta definición coincide con la anterior, basta enumerar los elementos de $I$ para comprobarlo. Esta definición es también válida para $I$ infinito.

Una intersección infinita

Consideramos el conjunto de índices $I=\mathbb{N}$ y la familia de conjuntos $\{A_n\}_{n\in\mathbb{N}}$ dada por los intervalos $A_n=[0,\frac{1}{2^n})$ . Todos estos intervalos contienen una cantidad infinita de números, pero su intersección es simplemente $\bigcap_{n\in\mathbb{N}}[0,\frac{1}{2^n})=\{0\}$ . En efecto, la inclusión $\supset$ es obvia porque $0\in [0,\frac{1}{2^n})$ para todo $n\in\mathbb{N}$ . Por otro lado, ningún número real positivo $x\in (0,\infty)$ puede pertenecer a la intersección ya que $x\notin [0,\frac{1}{2^n})$ para $n$ suficientemente grande. Esto prueba $\subset$ .

Definición

Dos conjuntos $A$ y $B$ son disjuntos si $A \cap B = \varnothing$ .

Definición

Dados dos conjuntos $A$ y $B$ la unión $A \cup B$ es el conjunto formado por aquellos elementos que pertenecen al menos a uno de estos dos conjuntos, $A \cup B = \{ x | x \in A \vee x \in B \}$ .

Observa que $A\cap B\subset A\cup B$ .

Si $A\subset C$ y $B\subset C$ entonces $A\cup B\subset C$ .

Teorema

La unión de conjuntos verifica las siguientes propiedades, donde $A$ , $B$ y $C$ son conjuntos cualesquiera:

$A \cup B = B \cup A$ (conmutativa).
$(A \cup B) \cup C = A \cup (B \cup C)$ (asociativa).
$\varnothing \cup A = A$ (elemento neutro).
$A \subset A \cup B$ .
$B \subset A \cup B$ .
$A \subset B\Leftrightarrow B=A \cup B$ .

Prueba

Los elementos de $A \cup B$ son los que pertenecen a $A$ o a $B$ , que son los mismos que pertenecen a $B$ o a $A$ .

Los dos uniones triples coinciden porque ambas representan el conjunto de elementos que pertenecen a $A$ , a $B$ o a $C$ .

Como el vacío no tiene elementos, los elementos que pertenecen al vacío o a $A$ son los que pertenecen a $A$ .

Es obvio, por la propia definición, que tanto los elementos de $A$ como los de $B$ pertenecen a la unión.

Probemos la última equivalencia. Comenzamos demostrando $\Leftarrow$ . Esto es una simple consecuencia de la inclusión $A\subset A\cup B$ . Probemos ahora $\Rightarrow$ . Supongamos pues que $A \subset B$ . Tenemos que demostrar que $B=A \cup B$ y lo haremos por doble inclusión. La inclusión $\subset$ es cierta por el apartado anterior. Probemos la otra. Un elemento que está en $A$ o en $B$ ha de estar necesariamente en $B$ ya que $A\subset B$ .

Estas propiedades nos permiten definir inductivamente la unión de una cantidad finita de conjuntos $A_1\cup\cdots\cup A_n$ . Consiste en los elementos que están en alguno de ellos.

Veamos ahora el caso posiblemente infinito.

Definición

La unión de una familia de conjuntos $\{ A_i \}_{i\in I}$ se define como $\bigcup_{i\in I}A_i=\{x\;|\;\exists i\in I| x\in A_i\}$ .

Igual que antes, si $I$ es finito, esta definición coincide con la anterior, pero es también válida para $I$ infinito.

Una unión infinita

Si consideramos la familia $\{[0,\frac{1}{2^n})\}_{n\in\mathbb{N}}$ del ejemplo de intersección infinita, tenemos que $\bigcup_{n\in\mathbb{N}}[0,\frac{1}{2^n})=[0,\frac{1}{2})$ ya que $[0,\frac{1}{2})$ es uno de los conjuntos de esta familia y todos los demás $[0,\frac{1}{2^n})$ están contenidos en él.

Definición

Dados dos conjuntos $A$ y $B$ se define la diferencia $A \setminus B$ , como el conjunto formado por los elementos de $A$ que no están en $B$ , $A \setminus B = \{ x | x \in A \wedge x \notin B \}$ .

Observa que $A\setminus B\neq B\setminus A$ . De hecho ambos conjuntos son disjuntos.

Definición

La diferencia simétrica $A\triangle B$ de dos conjuntos $A$ y $B$ se define como $A\triangle B=(A\setminus B)\cup(B\setminus A)=(A\cup B)\setminus (A\cap B)$ .

Teorema (Leyes distributivas)

Dados tres conjuntos $A$ , $B$ y $C$ :

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ .
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ .

Prueba

Probamos la primera por doble inclusión. La segunda la dejamos como ejercicio.

Comenzamos demostrando $\supset$ . Sabemos que $A\cap B\subset A$ y $A\cap B\subset B\subset B\cup C$ , por tanto $A\cap B\subset A\cap (B\cup C)$ . También sabemos que $A\cap C\subset A$ y $A\cap C\subset C\subset B\cup C$ , por tanto $A\cap C\subset A\cap (B\cup C)$ . De aquí se deduce $\supset$ .

Veamos ahora $\subset$ . Dado $x\in A\cap (B\cup C)$ tenemos que $x\in A$ y $x\in B\cup C$ . Por un lado, si $x\in B$ entonces $x\in A\cap B\subset (A \cap B) \cup (A \cap C)$ . Por otro lado, si $x\in C$ entonces $x\in A\cap C\subset (A \cap B) \cup (A \cap C)$ . De esto se sigue $\subset$ .

Los siguientes diagramas ilustran las leyes distributivas.

Teorema (Leyes de De Morgan)

Dados tres conjuntos $A$ , $B$ y $C$ :

$C \setminus (A \cup B) = (C \setminus A) \cap (C \setminus B)$ .
$C \setminus (A \cap B) = (C \setminus A) \cup (C \setminus B)$ .

Prueba

Probaremos la segunda ley de De Morgan por doble inclusión. La primera queda como ejercicio.

Comenzamos con $\supset$ . Sea $x\in C\setminus A$ . Tenemos entonces que $x\in C$ pero $x\notin A$ , por tanto $x\notin A\cap B$ ya que $A\cap B\subset A$ . Esto demuestra que $x\in C \setminus (A \cap B)$ , por tanto $C\setminus A\subset C \setminus (A \cap B)$ . Los papeles de $A$ y $B$ son intercambiables, así que también $C\setminus B\subset C \setminus (A \cap B)$ . Esto demuestra $\supset$ .

Para probar $\subset$ , tomamos $x\in C \setminus (A \cap B)$ . Esto quiere decir que $x\in C$ pero $x\notin A\cap B$ . Esto último equivale a que bien $x\notin A$ o bien $x\notin B$ . Si $x\notin A$ entonces $x\in C\setminus A$ y si $x\notin B$ entonces $x\in C\setminus B$ . Por tanto $x\in (C \setminus A) \cup (C \setminus B)$ . Esto prueba $\subset$ .

Las leyes de De Morgan quedan mejor explicadas por los siguientes diagramas.

Definición

El producto cartesiano de dos conjuntos $A$ y $B$ es el conjunto $A\times B$ cuyos elementos son los pares ordenados $(a,b)$ cuya primera coordenada está en $A$ , $a\in A$ , y la segunda en $B$ , $b\in B$ , es decir $A \times B = \{ (a,b) | a \in A \wedge b \in B \}$ .

Un producto cartesiano

Si $A= \{ 1,2,3 \}$ y $B=\{a,b\}$ entonces $A \times B=\{(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)\}$ .

El vacío hace el papel de cero con respecto al producto cartesiano $A \times \varnothing = \varnothing = \varnothing \times B$ .

En general, el producto cartesiano no es conmutativo $A\times B\neq B\times A$ .

Si $A$ y $B$ son finitos, ¿cuántos elementos tiene $A\times B$ ?

Análogamente, podemos definir el producto cartesiano de una cantidad finita de conjuntos $A_1\times\cdots\times A_n$ como el formado por las $n$ -uplas $(a_1,\dots, a_n)$ tales que $a_i\in A_i$ . Más generalmente, podemos definir el producto cartesiano de una familia arbitraria de conjuntos $\{A_i\}_{i\in I}$ , $\prod_{i\in I}A_i=\{(a_i)_{i\in I}|a_i\in A_i\}$ .

Un producto infinito

El producto infinito $\prod_{n\in\mathbb{N}}[0,\frac{1}{2^n})$ está formado por todas las sucesiones $(a_n)_{n\in\mathbb{N}}$ de números reales tales que $0\leq a_n<\frac{1}{2^n}$ para todo $n\in\mathbb{N}$ .

Definición

Dado un conjunto $A$ , el conjunto de las partes de $A$ es $\mathcal{P}(A)=\{$ subconjuntos de $A\}$ .

$B\subset A\Leftrightarrow B\in\mathcal{P}(A)$ .

Las partes de

A = \{ 1,2,3 \}

$\mathcal{P}(A) = \{\varnothing, \{ 1 \}, \{ 2 \}, \{ 3 \}, \{1,2\}, \{1,3\}, \{2,3\}, A \}$ .

Si $A$ es un conjunto con $n$ elementos, ¿cuántos elementos tiene $\mathcal{P}(A)$ ? ¿Qué ocurre si $A$ es infinito? ¿Es posible que $\mathcal{P}(A)$ sea vacío? ¿Y unitario?

Definición

En una situación concreta, un conjunto universal $U$ es el que contiene a todos los posibles conjuntos del problema que tratamos.

Definición

Fijado un conjunto universal $U$ , el complementario de un conjunto $A$ se denota $\bar{A}$ o $A^c$ y se define como $\bar{A} = U\setminus A$ .

Proposición

Si tenemos fijado un conjunto universal $U$ entonces $A \setminus B = A \cap \bar{B}$ .

Prueba

Como $A,B\subset U$ , $\begin{array}{rcl} A \setminus B&=&\{x | x \in A \wedge x \notin B\} \cr &=&\{x | x \in A \wedge (x\in U \wedge x \notin B)\} \cr &=&\{x | x \in A \wedge x\in \bar B\} \cr &=&A \cap \bar{B}. \end{array}$

Proposición

Dado un conjunto universal $U$ :

$\bar{\bar{A}}=A$ .
$\bar U=\varnothing$ .
$\bar{\varnothing}=U$ .

Prueba

Como $A\subset U$ , $\begin{array}{rcl} \bar{\bar{A}} &=& U\setminus \bar{A}\cr &=&\{ x | x \in U \wedge x \notin \bar{A} \} \cr &=& \{ x | x \in U \wedge (x\notin U \vee x\in A) \} \cr &=& \{ x | x \in U \wedge x\in A \} \cr &=& \{ x | x\in A \} \cr &=& A. \end{array}$

Por otro lado,

$\bar U=U\setminus U=\varnothing,$

así que $U=\bar{\bar{U}}=\bar\varnothing$ .

Aplicaciones

Definición

Dados dos conjuntos $A$ y $B$ , una aplicación $f$ de $A$ en $B$ , que se denota $f\colon A\rightarrow B$ , es una regla que asocia a cada $a\in A$ un único elemento $f(a)\in B$ , denominado imagen de $a$ por $f$ . También diremos que $f(a)$ es el valor de $f$ en $a$ . Esto se denota también como $a\mapsto f(a)$ , especialmente en diagramas como el siguiente,

$\begin{array}{rcl} f\colon A & \longrightarrow & B,\cr a & \mapsto & f(a). \end{array}$

También se puede colocar el nombre de la aplicación encima de la flecha,

$A\stackrel{f}{\longrightarrow} B.$

El siguiente diagrama ilustra una aplicación

que se puede definir también del siguiente modo:

$\begin{array}{rcl} A&\stackrel{f}\longrightarrow& B,\cr 1&\mapsto&a,\cr 2&\mapsto&b,\cr 3&\mapsto&b,\cr 4&\mapsto&b. \end{array}$

Sin embargo el diagrama siguiente no es una aplicación ya que la definición no se cumple por varias razones, ¿sabrías decir cuáles?

Para definir una aplicación hay que especificar lo siguiente:

El conjunto de partida, también llamado dominio.
El de llegada, o codominio.
La imagen de cada elemento del conjunto de partida.

Si dos aplicaciones difieren en alguno de estos tres puntos se consideran diferentes.

Aplicaciones parecidas pero diferentes

La aplicación $f\colon \mathbb{N}\rightarrow \mathbb{N}$ definida como $f(n)=n$ es diferente de la aplicación $g\colon \mathbb{N}\rightarrow \mathbb{Z}$ definida como $g(n)=n$ .

Algunas aplicaciones importantes

La identidad $1_A\colon A\rightarrow A$ se define como $1_A(a)=a$ para todo $a\in A$ . Esta aplicación está definida para cualquier conjunto $A$ .
Dado un subconjunto $B\subset A$ , la inclusión $i\colon B\rightarrow A$ se definie como $i(b)=b$ para todo $b\in B$ .
Dados dos conjuntos $A$ y $B$ y un elemento $b\in B$ , la aplicación constante $c_b\colon A\rightarrow B$ se define como $c_b(a)=b$ para todo $a\in A$ .

Dado un conjunto $A$ , ¿hay algun aplicación $\varnothing\rightarrow A$ ? ¿Y $A\rightarrow\varnothing$ ?.

Definición

Dadas dos aplicaciones

$A\stackrel{f}\longrightarrow B\stackrel{g}\longrightarrow C$

su composición $g\circ f\colon A\rightarrow C$ es la aplicación definida como $(g\circ f)(a)=g(f(a))$ .

Proposición

La composición de aplicaciones satisface las propiedades siguientes:

Dadas tres aplicaciones $A\stackrel{f}\longrightarrow B\stackrel{g}\longrightarrow C\stackrel{h}\longrightarrow D$ se verifica que $h\circ (g\circ f)=(h\circ g)\circ f$ (asociativa).
Dada una aplicación $f\colon A\rightarrow B$ , se tiene que $f\circ 1_A=f=1_B\circ f$ (elemento neutro).

Prueba

Las aplicaciones cuya igualdad se plantea tienen el mismo dominio y codominio, por tanto bastará comprobar que las imágenes de los elementos del dominio coinciden.

Dado $a\in A$ , por un lado $\begin{array}{rcl} (h\circ (g\circ f))(a)&=&h((g\circ f)(a))\cr &=&h(g(f(a)),\cr ((h\circ g)\circ f)(a)&=&(h\circ g)(f(a))\cr &=&h(g(f(a)). \end{array}$

Por otro lado

$\begin{array}{rcl} (f\circ 1_A)(a)&=&f(1_A(a))\cr &=&f(a)\cr &=&1_B(f(a))\cr &=&(1_B\circ f)(a). \end{array}$

Definición

Una aplicación $f \colon A \rightarrow B$ es invertible si existe $g \colon B \rightarrow A$ tal que $g \circ f = 1_A$ y $f \circ g = 1_B$ ,

${}_{1_A}\!\!\circlearrowright A\mathop{\rightleftarrows}\limits^f_g B\circlearrowleft_{1_B}$

Proposición

La aplicación $g$ de la definición anterior, si existe, es única.

Prueba

Si hubiera otra $g' \colon B \rightarrow A$ tal que $g' \circ f = 1_A$ y $f \circ g' = 1_B$ , entonces $\begin{array}{rcl} g&=&g\circ 1_B\cr &=&g\circ (f\circ g')\cr &=&(g\circ f)\circ g'\cr &=&1_A\circ g'=g'. \end{array}$

Definición

Si $f \colon A \rightarrow B$ es invertible su aplicación inversa $f^{-1} \colon B \rightarrow A$ es la única que satisface $f^{-1} \circ f = 1_A$ y $f \circ f^{-1} = 1_B$ ,

${}_{1_A}\!\!\circlearrowright A\mathop{\rightleftarrows}\limits^f_{f^{-1}} B\circlearrowleft_{1_B}$

La identidad $1_A\colon A\rightarrow A$ es invertible y $1_A^{-1}=1_A$ . Si $f\colon A\rightarrow B$ es invertible entonces $f^{-1} \colon B \rightarrow A$ también y $(f^{-1})^{-1}=f$ .

Proposición

Si tenemos dos aplicaciones invertibles

$A\stackrel{f}\longrightarrow B\stackrel{g}\longrightarrow C$

entonces $g\circ f$ es invertible y $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ .

Prueba

Basta observar que

$\begin{array}{rcl} (g\circ f)\circ (f^{-1}\circ g^{-1}) &=& g\circ (f\circ f^{-1})\circ g^{-1}\cr &=& g\circ 1_B\circ g^{-1}\cr &=& g\circ g^{-1}\cr &=& 1_C, \end{array}$

y que

$\begin{array}{rcl} (f^{-1}\circ g^{-1})\circ (g\circ f) &=& f^{-1}\circ (g^{-1}\circ g)\circ f\cr &=& f^{-1}\circ 1_B\circ f\cr &=& f^{-1}\circ f\cr &=& 1_A. \end{array}$

Nos disponemos a dar una caracterización más asequible de las aplicaciones invertibles.

Definición

Sea $f\colon A \rightarrow B$ una aplicación.

$f$ es inyectiva o uno-a-uno si no existen dos elementos diferentes de $A$ con la misma imagen.
$f$ es sobreyectiva si todo elemento de $B$ es la imagen de algún elemento de $A$ .
$f$ es biyectiva si es inyectiva y sobreyectiva.

En una aplicación inyectiva no puede ocurrir los siguiente:

En una sobreyectiva está prohibida la siguiente situación:

En notación matemática, $f\colon A\rightarrow B$ es inyectiva si, dados $a,a'\in A$ , $f(a)=f(a')\Rightarrow a=a'$ , y $f$ es sobreyectiva si $\forall b\in B\;\exists a\in A|f(a)=b$ . Las flechas de las aplicaciones inyectivas se denotan $f\colon A\hookrightarrow B$ y las de las sobreyectivas $f\colon A\twoheadrightarrow B$ .

Es un error tristemente común el confundir la caracterización anterior de la inyectividad con la implicación $\Leftarrow$ . En realidad esta impliciación es cierta para cualquier aplicación por la propia definición.

Lema

Una aplicación $f\colon A \rightarrow B$ es biyectiva $\Leftrightarrow$ $\forall b\in B\;\exists! a\in A|f(a)=b$ .

Prueba

Veamos $\Rightarrow$ . Supongamos pues que $f$ es biyectiva. Si excluimos la condición de unicidad, el enunciado de la derecha es cierto por ser $f$ sobreyectiva. La unicidad se deduce de ser $f$ inyectiva, pues si existieran $a,a'\in A$ tales que $f(a)=b=f(a')$ entonces tendríamos que $a=a'$ .

Veamos ahora $\Leftarrow$ . Como ya hemos comentado, el enunciado de la derecha implicia la sobreyectividad de $f$ ya que incluso la condición de unicidad no sería necesaria para esto. Para ver que $f$ es inyectiva tomamos $a,a'\in A$ y suponemos que $f(a)=f(a')$ . Tomando $b=f(a)$ tenemos que $f(a)=b$ y $f(a')=b$ , así que por la unicidad $a=a'$ , que es lo que teníamos que probar.

Si $f\colon A\rightarrow B$ es biyectiva y $A$ es finito, ¿qué podemos decir de $B$ ? ¿Y si $f$ es inyectiva? ¿Y si es sobreyectiva?

El siguiente tema versará en buena parte sobre el estudio de las aplicaciones biyectivas de un conjunto finito en sí mismo.

Teorema

Una aplicación $f\colon A \rightarrow B$ es invertible $\Leftrightarrow$ es biyectiva.

Prueba

Supongamos que $f$ es invertible. Veamos que es sobreyectiva. Dado $b\in B$ tenemos que $f(f^{-1}(b))=(f\circ f^{-1})(b)=1_B(b)=b$ , con lo que $f$ es sobreyectiva. Si, dados $a,a'\in A$ , $f(a)=f(a')$ , entonces $f^{-1}(f(a))=f^{-1}(f(a'))$ . Como $f^{-1}\circ f=1_A$ deducimos que $a=a'$ , luego $f$ es inyectiva.

Supongamos ahora que $f$ es biyectiva. Definimos $g\colon B\rightarrow A$ del siguiente modo. Dado $b\in B$ , definimos $g(b)\in A$ como el único elemento tal que $f(g(b))=b$ , que está bien definido por el lema anterior. Esto implica que $f\circ g=1_B$ . Veamos que $g\circ f=1_A$ . Ambas aplicaciones tienen a $A$ como dominio y codominio, así que basta ver que toman los mismos valores, es decir que para todo $a\in A$ , $(g\circ f)(a)=1_A(a)=a$ . Como $f$ es inyectiva, esto equivale a probar que $f((g\circ f)(a))=f(a)$ . Tenemos también que $f((g\circ f)(a))=(f\circ(g\circ f))(a)$ . Usando la asociatividad de la composición y la identidad ya probada deducimos que en efecto

$\begin{array}{rcl} f\circ(g\circ f)&=&(f\circ g)\circ f\cr &=&1_B\circ f\cr &=&f. \end{array}$

Las aplicaciones invertibles juegan en el ámbito de los conjuntos el mismo papel que las igualdades en el campo de los números, es por eso que se denotan

$f\colon A\stackrel{\cong}\longrightarrow B$

o simplemente $f\colon A\cong B$ . Por ejemplo, el producto cartesiano $A\times B$ no es conmutativo estrictamente hablando, pero hay una biyección

$\begin{array}{rcl} A\times B&\cong &B\times A,\cr (a,b)&\mapsto &(b,a). \end{array}$

Decimos pues que el producto cartesiano no es conmutativo salvo biyección. Lo mismo ocurre con la asociatividad del producto cartesiano,

$\begin{array}{rcl} (A\times B)\times C&\cong &A\times(B\times C),\cr ((a,b),c)&\mapsto &(a,(b,c)). \end{array}$

Es más, ambos están en biyección con el producto triple, por ejemplo

$\begin{array}{rcl} (A\times B)\times C&\cong &A\times B\times C,\cr ((a,b),c)&\mapsto &(a,b,c). \end{array}$

Definición

Sea $f \colon A \rightarrow B$ una aplicación.

La imagen directa de un subconjunto del dominio $U\subset A$ es el subconjunto del codominio $f(U)=\{b\in B\;|\;\exists a\in U|f(a)=b\}\subset B$ .
La imagen inversa de un subconjunto del codominio $V\subset B$ es subconjunto del dominio $f^{-1}(V)=\{a\in A| f(a)\in V\}\subset A$ .

La imagen de la aplicación $A$ se define como $\operatorname{im}f=f(A)$ .

La imagen inversa recible otros nombres como contraimagen, preimagen o anti-imagen. La imagen directa también se denomina simplemente imagen.

Dada una aplicación $f\colon A\rightarrow B$ , conviene no confundir la imagen de un elemento de $A$ con la imagen directa de un subconjunto de $A$ , aunque obviamente son conceptos relacionados, $f(\{a\})=\{ f(a) \}$ .

¿Cuál es la imagen directa del subconjunto vacío? ¿Y su imagen inversa? ¿Dependen las respuestas a estas preguntas de quién sea $f\colon A\rightarrow B$ ?

La notación $f^{-1}(V)$ para la imagen inversa es confusa porque incorpora la notación usada para la inversa de la aplicación $f$ , cuando esta existe. La imagen inversa está siempre definida, aun cuando $f$ no es invertible y por tanto $f^{-1}$ no existe. Si $f$ es invertible, no hay ambigüedad ya que en este caso la imagen inversa $f^{-1}(V)$ de $V$ a través de $f$ coincide con la imagen directa de $V$ a través de $f^{-1}\colon B \rightarrow A$ . Para añadir aún más confusión, es habitual abusar de la terminología y denotar al subconjunto $f^{-1}(\{b\})\subset A$ simplemente por $f^{-1}(b)$ . El significado de esta expresión en cada caso se deducirá del contexto.

Una aplicación $f\colon A\rightarrow B$ es sobreyectiva si y solo si $\operatorname{im}f=f(A)=B$ .
Para toda aplicación $f\colon A\rightarrow B$ , $f^{-1}(B)=A$ .
A partir de cualquier aplicación $f\colon A\to B$ podemos definir una sobreyectiva $\overline{f}\colon A \to \operatorname{im}(f)$ como $\overline{f}(a)=f(a)$ . ¿En qué se diferencia de la anterior?
Las imágenes directa e inversa preservan inclusiones, es decir, dada una aplicación $f\colon A\rightarrow B$ :
- $U\subset U'\subset A\Rightarrow f(U)\subset f(U')\subset B$
- $V \subset V'\subset B\Rightarrow f^{-1}(V)\subset f^{-1}(V')\subset A$ .

¿Son ciertos los recíprocos de estas últimas implicaciones?

Proposición

Dada una aplicación $f\colon A \rightarrow B$ y subconjuntos $U\subset A$ y $V\subset B$ , se verifican las siguientes propiedades:

$U \subset f^{-1}(f(U))$ .
$f(f^{-1}(V)) \subset V$ .

Prueba

Probaremos la segunda propiedad y dejaremos la primera como ejercicio. Dado $y\in f(f^{-1}(V))$ existe $x\in f^{-1}(V)$ tal que $y=f(x)$ . Como $x\in f^{-1}(V)$ , $f(x)\in V$ , así que $y\in V$ . Esto es lo que había que demostrar.

Proposición

Dada una aplicación $f\colon A \rightarrow B$ y subconjuntos $U_1,U_2 \subset A$ y $V_1,V_2 \subset B$ , se verifican las siguientes propiedades:

$f(U_1 \cup U_2) = f(U_1) \cup f(U_2)$ .
$f(U_1 \cap U_2) \subset f(U_1) \cap f(U_2)$ .
$f^{-1} (V_1 \cup V_2) = f^{-1} (V_1) \cup f^{-1} (V_2)$ .
$f^{-1} (V_1 \cap V_2) = f^{-1} (V_1) \cap f^{-1} (V_2)$ .

Prueba

Vamos a probar 2 y 3. Los demás apartados son similares y quedan como ejercicio.

Dado $y \in f(U_1 \cap U_2)$ existe $x \in U_1 \cap U_2$ tal que $y = f(x)$ . Como $x\in U_1$ y $x\in U_2$ deducimos que $y \in f(U_1)$ e $y \in f(U_2)$ , por tanto $y\in f(U_1) \cap f(U_2)$ .

Tenemos que $x\in f^{-1}(V_1 \cup V_2)$ si y solo si $f(x)\in V_1\cup V_2$ . Esto equivale a decir que $f(x)\in V_1$ o $f(x)\in V_2$ , lo que es lo mismo, $x\in f^{-1}(V_1)$ o $x\in f^{-1}(V_2)$ . Esto último es idéntico a afirmar que $x\in f^{-1}(V_1)\cup f^{-1}(V_2)$ .

Definición

La restricción de una aplicación $f\colon A \rightarrow B$ a un subconjunto $U\subset A$ es la aplicación $f|_U\colon U\rightarrow B$ definida como $f|_U(u)=f(u)$ para todo $u\in U$ .

¿En qué se diferencian $f$ y su restricción $f|_U$ ?

Definición

Dados dos conjuntos $A$ y $B$ , el conjunto exponencial es $B^A=\{$ aplicaciones $A\rightarrow B\}$ .

Un conjunto exponencial pequeño

El conjunto exponencial $\{a,b\}^{\{1,2\}}=\{f_1,f_2,f_3,f_4\}$ está formado por las cuatro aplicaciones siguientes:

Si $A$ y $B$ son finitos, ¿cuántos elementos tiene $B^A$ ?
¿Cuántos elementos hay en $A^\varnothing$ ?
Dado un conjunto cualquiera $A$ y otro unitario $\{e\}$ , describe $A^{\{e\}}$ y $\{e\}^A$ .

Definición

El grafo de una aplicación $f\colon A\rightarrow B$ es el conjunto

$G_f=\{(a,b)\in A\times B | b=f(a) \} \subset A\times B$

El grafo de la aplicación

es el conjunto

$G_f=\{(1,a), (4,b), (2,b), (3, b)\}\subset A\times B.$

Las aplicaciones $f\colon A\rightarrow B$ se caracterizan porque para cada $a$ está definido un único $f(a)\in B$ . Por tanto un subconjunto $S\subset A\times B$ es el grafo de una aplicación $f$ si para cada $a\in A$ existe un único $b\in B$ tal que $(a,b)\in S$ . Este $b$ sería $b=f(a)$ .

Conjuntos cociente

Definición

Una relación $R$ en un conjunto $A$ es un subconjunto $R\subset A\times A$ . Si $(x,y)\in R$ diremos que $x$ está relacionado con $y$ y lo denotaremos $xRy$ , o simplemente $x\sim y$ cuando la relación $R$ sea obvia por el contexto.

Una relación $R$ es de equivalencia si satisface las siguientes propiedades:

$xRx$ para todo $x \in A$ (reflexiva).
$xRy\Leftrightarrow yRx$ para $x,y\in A$ cualesquiera (simétrica).
$xRy\wedge yRz\Rightarrow xRz$ para $x,y,z\in A$ (transitiva).

Relaciones de equivalencia

En el conjunto de los seres humanos, poseer el mismo grupo sanguíneo, es decir $x\sim y$ si $x$ tiene el mismo grupo sanguíneo que $y$ .
En el conjunto de estudiantes del primer curso del Grado en Matemáticas de la Universidad de Sevilla, estar en el mismo grupo de Álgebra Básica.
En $\mathbb Z$ , tener la misma paridad, o equivalentemente $x\sim_2 y$ si $x-y$ es par.
En $\mathbb Z$ , dado $n\in \mathbb Z$ , podemos definir la relación $\sim_n$ como $x\sim_n y$ si $x-y$ es divisible por $n$ . Observa que $\sim_n=\sim_{-n}$ .
En un conjunto cualquiera $A$ , la relación dada por la igualdad, $x\sim y$ si $x=y$ .
En un conjunto cualquiera $A$ , la relación definida como $x\sim y$ para todo $x,y\in A$ .

Estudia si las siguientes relaciones en el conjunto de los seres humanos son de equivalencia:

Ser hermano de. Es decir, $x\sim y$ si $x$ es hermano de $y$ .
Ser hijo de.
Ser la misma persona.
Tener la misma edad.
Llevarse menos de un año de edad.

Pon más ejemplos, definidos sobre los conjuntos que desees, de relaciones que satisfagan exactamente una o exactamente dos de las propiedades que se le demandan a las relaciones de equivalencia.

Definición

Dada una relación de equivalencia $R$ en un conjunto $A$ , la clase (de equivalencia) de $x \in A$ es el conjunto de los elementos relacionados con $x$ , es decir $R(x)=\{y\in A| xRy\}$ . Los elementos de $R(x)$ se denominan representantes de esta clase. El conjunto cociente de $A$ por $R$ es el formado por las clases de equivalencia de los elementos de $A$ . La proyección canónica es la aplicación sobreyectiva $\pi\colon A \twoheadrightarrow A/R$ definida como $x\mapsto R(x)$ .

Cuando la relación de equivalencia se denota simplemente $\sim$ por ser sobreentendida, la clase de un elemento $x\in A$ se denota simplemente como $[x]$ o $\overline{x}$ . Observa que, en virtud de la reflexividad, $x\in R(x)$ en cualquier relación de equivalencia.

En las relaciones de equivalencia, y por tanto en los cocientes, el problema que más confusión genera es que una misma clase de equivalencia puede tener muchos representantes diferentes. Esto dificulta la definición de aplicaciones que parten de cocientes $f\colon A/R\rightarrow B$ , ya que si quiero definir $f(R(x))$ basándome en la elección de un representante, por ejemplo $x\in R(x)$ , debo comprobar que la definición es independiente de cualquier otra elección posible del representante $y\in R(x)$ .

Conjuntos cociente

Aquí identificamos los conjuntos cociente del ejemplo de arriba, en algunos casos estableciendo una biyección con otro conjunto más sencillo.

$\{$ Seres humanos $\}/$ poseer el mismo grupo sanguíneo $\cong \{0, A,B,AB\}\colon [ x ]\mapsto$ grupo sanguíneo de cualquier representante.
$\{$ Estudiantes de primero de Matemáticas $\}/$ estar en el mismo grupo de Álgebra Básica $\cong \{A,B,C,D,E,F\}\colon [ x ]\mapsto$ grupo al que pertenece un representante cualquiera.
$\mathbb Z/\sim_2\;=\; \{[0],[1]\}$ .
$\mathbb Z/\sim_n\;=\;\{[0],\dots,[n-1]\}$ si $n>0$ .
En este caso la proyección natural es biyectiva $\pi\colon A\cong A/=$ .
$A/\sim$ es unitario.

Los racionales como cociente

Quizá el primer conjunto cociente que uno estudia en matemáticas (sin saberlo) es $\mathbb{Q}$ , que se define como el cociente de $\mathbb{Z}\times (\mathbb{Z}\setminus\{0\})$ por la relación de equivalencia $(a,b)\sim(c,d)\Leftrightarrow ad=bc.$ Es decir, $\mathbb{Q}=\frac{\mathbb{Z}\times (\mathbb{Z}\setminus\{0\})}{\sim}.$ Las clases de equivalencia en este cociente se denotan habitualmente $\frac{a}{b}=[(a,b)].$

Demuestra que la relación $\sim$ del ejemplo anterior es de equivalencia. ¿Te atreverías a definir $\mathbb{R}$ como un cociente?

Definición

Una partición de $A$ es un subconjunto $P \subset \mathcal{P}(A)$ tal que:

Los elementos de $P$ son subconjuntos no vacíos de $A$ .
La unión de todos los elementos de $P$ es $A$ .
Dos elementos distintos de $P$ son siempre disjuntos.

La siguiente es una partición de un conjunto $A$ formada por los subconjuntos $\{E_1, E_2, E_3, E_4, E_5\}$ .

Proposición

Si $R$ es una relación de equivalencia en un conjunto $A$ , $xRy\Leftrightarrow R(x)=R(y)$ .

Prueba

$\Leftarrow$ En este caso $xRy$ pues $y\in R(x)$ .

$\Rightarrow$ Probemos $\subset$ . Si $z\in R(x)$ es porque $xRz$ . Como $yRx$ , por la transitividad tenemos que $yRz$ , así que $z\in R(y)$ . La inclusión $\supset$ también es cierta porque, por la simetría, los papeles de $x$ e $y$ son intercambiables en el argumento anterior.

Teorema

Si $R$ es una relación de equivalencia en $A$ , entonces $A/R$ es una partición de $A$ . Es más, toda partición de $A$ proviene de una relación de equivalencia.

Prueba

Las clases que forman $A/R$ no son vacías porque todas poseen algún representante. La unión de todas las clases es $A$ , porque todo $x\in A$ pertenece a una clase, a la suya propia, $x\in R(x)$ . Supongamos que dos clases $R(x)$ y $R(y)$ no fueran disjuntas. Entonces existe $z\in R(x)\cap R(y)$ . Esto significa que $xRz$ e $yRz$ . Por la simetría y la transitividad, $xRy$ , luego por la proposición anterior $R(x)=R(y)$ .

Si tenemos una partición $P$ de $A$ , podemos definir la relación de equivalencia $x\sim_Py$ si $x$ e $y$ pertenecen al mismo elemento de la partición. Es obvio que esta relación es simétrica. Es reflexiva porque, en virtud de la segunda propiedad de las particiones, todo elemento de $A$ pertenece a alguno de $P$ . Veamos la transitividad. Si $x\sim_Py\sim_Pz$ entonces existen $U,V\in P$ tales que $x,y\in U$ y $y,z\in V$ . Como $y\in U\cap V$ la tercera propiedad de las particiones nos asegura que $U=V$ , así que $x\sim_Pz$ . Esta relación de equivalencia satisface $A/\sim_P=P$ por su propia definición, ya que el vacío no está en $P$ .

Factorización canónica de una aplicación

Teorema (Propiedad universal de la proyección canónica)

Si $f\colon A\rightarrow B$ es una aplicación y $R$ es una relación de equivalencia en $A$ tal que $xRy \Rightarrow f(x) =f(y)$ , entonces existe una única aplicación $\overline{f}\colon A/R\to B$ tal que $f=\overline{f}\circ\pi$ ,

$f\colon A\stackrel{\pi}\longrightarrow A/R\stackrel{\overline{f}}\longrightarrow B.$

Prueba

Vamos a suponer que $\overline{f}$ existe y cumple las propiedades indicadas. De ahí deduciremos una fórmula forzosa para $\overline{f}$ , con lo cual de existir será única. Luego veremos que la fórmula tiene sentido, luego $\overline{f}$ existirá.

Si $f=\overline{f}\circ\pi$ entonces dado $x\in A$ , $\begin{array}{rcl} f(x)&=&(\overline{f}\circ\pi)(x)\cr &=&\overline{f}(\pi(x))\cr &=&\overline{f}(R(x)). \end{array}$ Definimos pues $\overline{f}$ mediante la fórmula $\overline{f}(R(x))=f(x)$ . Veamos que $\overline{f}$ está bien definida así. Para ello hemos de comprobar que si $R(x)=R(y)$ entonces $f(x)=f(y)$ . Esto se deduce de la hipótesis ya que $R(x)=R(y)$ si y solo si $xRy$ .

Definición

Dada una aplicación $f\colon A\to B$ , podemos definir relación de equivalencia $\sim_f$ en $A$ asociada a $f$ como $x\sim_f y$ si $f(x)=f(y)$ .

Prueba que $\sim_f$ es en efecto una relación de equivalencia. Describe el conjunto cociente y la partición asociada. Demuestra también que si $R$ es una relación de equivalencia en $A$ y $\pi\colon A\rightarrow A/R$ es la proyección natural entonces $\sim_\pi=R$ .

Teorema (Factorización canónica)

Dada una aplicación $f\colon A\to B$ , existe una única aplicación $\overline{f}\colon A/\sim_f\;\rightarrow \operatorname{im} f$ tal que el siguiente diagrama es conmutativo

es decir, $f=i\circ\overline{f}\circ\pi$ . Aquí $\pi$ es la proyección canónica e $i$ es la inclusión. Además, la aplicación $\overline{f}$ es biyectiva.

Prueba

Hemos visto con anterioridad que podemos definir una aplicación sobreyectiva $f'\colon A\twoheadrightarrow\operatorname{im} f$ como $f'(x)=f(x)$ . Está claro que $f=i\circ f'$ ya que ambas posee el mismo dominio y codominio e $(i\circ f')(x)=i(f'(x))=f(x)$ para todo $x\in A$ . Es más, como $f$ y $f'$ toman los mismos valores, $\sim_f=\sim_{f'}$ .

El teorema anterior se puede aplicar a $f'\colon A\rightarrow\operatorname{im} f$ y a $\sim_{f}$ . Esto da lugar a una aplicación $\overline{f}\colon A/\sim_f\rightarrow \operatorname{im} f$ que satisface $f'=\overline{f}\circ\pi$ , así que $f=i\circ f'=i\circ(\overline{f}\circ\pi)$ . La aplicación $\overline{f}$ es la única que se descompone de este modo, ya que la propia descomposición fuerza una fórmula para su definición. En efecto, dado $x\in A$ , $\begin{array}{rcl} f(x)&=&(i\circ\overline{f}\circ\pi)(x)\cr &=&i(\overline{f}(\pi(x)))\cr &=&i(\overline{f}([x]))\cr &=&\overline{f}([x]). \end{array}$

Veamos que $\overline{f}$ es biyectiva. Comenzamos por la sobreyectividad. Dado $b\in\operatorname{im} f$ , como $f'$ es sobreyectiva, existe $a\in A$ tal que $b=f(a)=\overline{f}([a])$ . Esto prueba que $\overline{f}$ es sobreyectiva. Comprobemos ahora la inyectividad. Dados $[x],[y]\in A/\sim_f$ , usando la anterior fórmula para $\overline{f}$ vemos que $\overline{f}([x])=\overline{f}([y])$ si y solo si $f(x)=f(y)$ , lo cual equivale a que $x\sim_f y$ , que es lo mismo que decir $[x]=[y]$ . Esto concluye la prueba.

Este teorema nos proporciona un método muy eficiente para establecen una biyección de un conjunto cociente en otro.

\mathbb{Z}

módulo

n

Vamos a dar una demostración rigurosa de que $\mathbb{Z}/\sim_n$ posee $n$ elementos para $n>0$ . Para ello definimos la aplicación $f\colon \mathbb Z\rightarrow \mathbb Z$ tal que $f(m)$ es el resto no negativo de dividir $m$ entre $n$ .

La imagen de $f$ es $\operatorname{im} f=\{0,\dots, n-1\}$ . En efecto, el resto de la división es $\geq 0$ y $<n$ , lo cual demuestra $\subset$ . Además, para $0\leq m<n$ , el cociente de la división es $0$ y el resto es el propio $m$ , por tanto también tenemos $\subset$ .

Veamos ahora que $\sim_f=\sim_n$ . Sean $m,m'\in\mathbb Z$ . Dividimos ambos números entre $n$ , $m=c\cdot n+f(m)$ y $m'=c'\cdot n+f(m')$ . Tenemos que $m-m'=(c-c')\cdot n+(f(m)-f(m'))$ es también una división, porque $|f(m)-f(m')|<n$ . Por tanto $f(m)=f(m')$ si y solo si $m-m'$ es divisible por $n$ . Esto demuestra que ambas relaciones coinciden.

Aplicando el teorema de factorización, deducimos que hay una biyección $\overline{f}\colon \mathbb Z/\sim_n\cong \{0,\dots, n-1\}$ definida por $\overline{f}([m])=f(m)$ .