Introducción

Ahora que hemos desarrollado una herramienta para comparar conjuntos que tienen más elementos que otros y hemos trabajado con conjuntos finitos e infinitos, hablaremos un poco más acerca de estos últimos, en especifico de aquellos que tienen la misma cantidad de elementos que el conjunto de los números naturales. En esta entrada nos enfocaremos principalmente en exhibir un par de ejemplos de conjuntos numerables dando una función biyectiva explícita en cada caso.

Conjuntos numerables

Definición. Sea $A$ un conjunto, decimos que $A$ es numerable si es equipotente a $\mathbb{N}$, es decir, si existe una función biyectiva $f:\mathbb{N}\to A$. De ser así, lo denotaremos con $|A|=|\mathbb{N}|$.

Ejemplo.

En la entrada de equipotencia vimos que existe una función biyectiva entre el conjunto de los números pares y los números naturales, por lo que podemos concluir que $$|\{2k:k\in \mathbb{N}\}|=|\mathbb{N}|.$$

$\square$

Ejemplo.

El conjunto $\mathbb{Z}$ de los números enteros es un conjunto numberable. (Puedes revisar la construcción del conjunto de los números enteros en el siguiente enlace: Álgebra Superior II: Construcción de los enteros y su suma).

Consideremos $f:\mathbb{N}\to \mathbb{Z}$ dada por:

$f(n)= \left\{ \begin{array}{lcc}
             \overline{(k,0)} &   si  & n=2k\ \text{para algún}\ k\in \mathbb{N} \\
             \\ \overline{(0,k+1)} &  si & n=2k+1\ \text{para algún}\ k\in\mathbb{N}
             \end{array}
   \right.$

Resulta que $f$ es biyectiva. En efecto, veamos primero que $f$ es inyectiva.

Sean $x_1, x_2\in \mathbb{N}$ tales que $f(x_1)=f(x_2)$. Tenemos los siguientes casos:

Caso 1. Si $x_1=2k$ y $x_2=2m$ para algunos $k,m\in \mathbb{N}$, entonces $f(x_1)=\overline{(k,0)}$ y $f(x_2)=\overline{(m,0)}$ y así, $\overline{(k,0)}=\overline{(m,0)}$, por lo que $k+0=m+0$, es decir, $k=m$ y por lo tanto, $x_1=2k=2m=x_2$.

Caso 2. Si $x_1=2k+1$ y $x_2=2m+1$ para algunos $k,m\in \mathbb{N}$, entonces $f(x_1)=\overline{(0,k+1)}$ y $f(x_2)=\overline{(0,m+1)}$ y así, $\overline{(0,k+1)}=\overline{(0,m+1)}$, por lo que $0+(m+1)=0+(k+1)$ y así $m=k$. Por tanto, $x_1=2k+1=2m+1=x_2$.

El caso en el que $x_1=2k$ y $x_2=2m+1$ no puede ocurrir, pues de lo contrario se tendría que $\overline{(k,0)}=\overline{(0,m+1)}$ por lo que $k+(m+1)=0+0=0$, lo cual es imposible. De manera análoga, no puede ocurrir que $x_1=2m+1$ y $x_2=2k$ para algunos $m,k\in\mathbb{N}$.

Por lo tanto, $f$ es inyectiva.

Ahora veamos que $f$ es suprayectiva. Sea $y\in \mathbb{Z}$, tenemos los siguientes casos:

Caso 1. Si $y\in \mathbb{Z}^+\cup\set{\overline{(0,0)}}$, entonces $y=\overline{(k,0)}$ para algún $k\in\mathbb{N}$. Así, para $x=2k\in\mathbb{N}$ se tiene $f(x)=y$.

Caso 2: Si $y\in \mathbb{Z}^{-}$, entonces $y=\overline{(0,k)}$ para algún $k\in\mathbb{N}\setminus\{0\}$. Luego, existe $k’\in\mathbb{N}$ tal que $s(k’)=k$, es decir, $k’+1=k$. Luego, tomando $x=2k’+1$ se tiene $f(x)=\overline{(0,k’+1)}=\overline{(0,k)}=y$.

Concluimos que $f$ es suprayectiva.

Por lo tanto $f$ es biyectiva y así, $|\mathbb{N}|=|\mathbb{Z}|$.

$\square$

Antes de pasar al siguiente ejemplo vale la pena introducir la siguiente proposición que nos da una condición suficiente para que un conjunto sea numerable.

Proposición. Sea $A$ un conjunto. Si $f:\mathbb{N}\to A$ es una función sobreyectiva, entonces, $A$ es finito o numerable.

Demostración.

Sea $f:\mathbb{N}\to A$ una función sobreyectiva. Supongamos que $A$ no es finito y veamos que entonces debe ser numerable. Para cada $n\in\mathbb{N}$ definamos el conjunto $A_n:=\{k\in\mathbb{N}:f(k)\not=f(m)\ \textnormal{para cada}\ m\leq n\}$. Dado que $A$ no es finito, $A_n\not=\emptyset$ para cada $n\in\mathbb{N}$ y, por tanto, existe $\textnormal{min}(A_n)$. Definamos $g:\mathbb{N}\to\mathbb{N}$ por medio de $g(n)=\textnormal{min}(A_n)$. Por el teorema de recursión, existe una única función $h:\mathbb{N}\to\mathbb{N}$ tal que $h(0)=0$ y $h(n+1)=g(h(n))$ para cada $n\in\mathbb{N}$. Lo que vamos a probar ahora es que $F:=f\circ h:\mathbb{N}\to A$ es una biyección. Para ello notemos primero que $h(n)<h(n+1)$ para cada $n\in\mathbb{N}$. En efecto, si $n\in\mathbb{N}$, entonces, $h(n+1)=g(h(n))=\textnormal{min}(A_{h(n)})$ y así, en particular, $h(n+1)\in A_{h(n)}=\{k\in\mathbb{N}:f(k)\not=f(m)\ \textnormal{para cada}\ m\leq h(n)\}$, por lo que $h(n)<h(n+1)$. Consecuentemente, $h(m)<h(n)$ si y sólo si $m<n$. Esto último trae como consecuencia también que $n\leq h(n)$ para cada $n\in\mathbb{N}$ y se puede dar una prueba de ello por inducción, pues para $n=0$ se tiene que $h(0)=0\geq0$ y si suponemos que $h(n)\geq n$ para algún $n\in\mathbb{N}$, entonces, $h(n+1)>h(n)\geq n$ y así $h(n+1)\geq n+1$, pues de lo contrario tendríamos que $n+1>h(n+1)>n$ lo cual es imposible.
Una vez mencionado esto, veamos que $F$ es inyectiva. Para ello es suficiente mostrar que para cada $n\in\mathbb{N}$, $F(n+1)\not=F(k)$ para cada $k\leq n$. En efecto, si probamos esto último, y $m,n\in\mathbb{N}$ son naturales tales que $F(n)=F(m)$, entonces, $n=m$, ya que de lo contrario podemos suponer que $m<n$ y así $0<n$ por lo que existe un único $k\in\mathbb{N}$ tal que $k+1=n$; luego, $m\leq k$ y dado que $F(n)=F(k+1)\not=F(s)$ para cada $s\leq k$, en particular $F(n)\not=F(m)$ lo cual contradice la hipótesis de que $F(n)=F(m)$. Por tanto $F$ es inyectiva.
Sea pues $n\in\mathbb{N}$ y veamos que $F(n+1)\not=F(k)$ para cada $k\in\mathbb{N}$ tal que $k\leq n$. Por lo que hemos probado, si $k\leq n$, entonces $h(k)\leq h(n)$. Luego, como $h(n+1)=g(h(n))=\textnormal{min}(A_{h(n)})$, entonces, $f(h(n+1))\not=f(k)$ para cada $k\leq h(n)$; en particular, $f(h(n+1))\not=f(h(k))$ para cada $k\leq n$, es decir, $F(n+1)\not=F(k)$ para cada $k\leq n$. Lo anterior, como lo habíamos mencionado, nos permite concluir que $F$ es inyectiva.

Resta mostrar que $F$ es sobreyectiva. Para ello, veamos por inducción que para cada $n\in\mathbb{N}$ existe $k_n\in\mathbb{N}$ tal que $F(k_n)=f(n)$. Si $n=0$, entonces, para $k_0=0$ tenemos que $F(k_0)=f(0)$. Supongamos que para cada $m\leq n$, con $n\in\mathbb{N}$, existe $k_m\in\mathbb{N}$ tal que $F(k_m)=f(m)$. Veamos que para $n+1$ existe $k_{n+1}\in\mathbb{N}$ tal que $F(k_{n+1})=f(n+1)$. Si $f(n+1)=f(m)$ para algún $m\leq n$, entonces, por hipótesis, $f(n+1)=f(m)=F(k_m)$ para algún $k_m\in\mathbb{N}$. Supongamos ahora que $f(n+1)\not=f(k)$ para cada $k\leq n$. Dado que $n+1\leq h(n+1)$, podemos asegurar que el conjunto $B=\{k\in\mathbb{N}:n+1\leq h(k)\}$ es no vacío y, por consiguiente, existe $m=\textnormal{min}(B)$. Más aún, como $n+1\in B$ tenemos que $m\leq n+1$. Si $n+1=h(m)$, entonces, $F(m)=f(h(m))=f(n+1)$. Supongamos ahora que $n+1<h(m)$. Observemos que esta última desigualdad implica que $m\not=0$, de modo que existe $s\in\mathbb{N}$ tal que $s+1=m$ y dado que $m\leq n+1$, se sigue que $s\leq n$. Ahora bien, por la minimalidad de $m$ en el conjunto $B$, debe ocurrir que $h(s)<n+1$ y por ende $h(s)\leq n$. Finalmente, como $n+1<h(m)$ y $h(m)=h(s+1)=g(h(s))=\textnormal{min}(A_{h(s)})$, donde recordemos que $A_{h(s)}=\{k\in\mathbb{N}:f(k)\not=f(t)\ \textnormal{para cada}\ t\leq h(s)\}$, entonces, existe $t\leq h(s)$ tal que $f(t)=f(n+1)$. Esto muestra que existe $t\leq n$, ya que $t\leq h(s)\leq n$, tal que $f(t)=f(n+1)$ pero esto contradice que $f(n+1)\not=f(t)$ para cada $t\leq n$. De modo que necesariamente debe ocurrir que $n+1=h(m)$. Por tanto, para cada $n\in\mathbb{N}$ existe $k_n\in\mathbb{N}$ tal que $F(k_n)=f(n)$. Como $f$ es sobreyectiva se sigue que $F$ es sobreyectiva.
Por lo tanto, $F$ es una función biyectiva y, consecuentemente, $A$ es numerable.

$\square$

La proposición anterior, además de ser una propiedad interesante de los conjuntos numerables, nos ayuda a obtener una gran cantidad de este tipo de conjuntos. Por ejemplo, si $A\subseteq\mathbb{N}$ es cualquier conjunto infinito, entonces, podemos denotar $a_0=\textnormal{min}(A)$ y definir $g:\mathbb{N}\to A$ por medio de la siguiente regla \[g(n)=\left\{\begin{array}{lcc}
n & \textnormal{si}\ n\in A\\
n_0 & \textnormal{si}\ n\notin A
\end{array}
\right.\]

Ciertamente la función anterior es sobreyectiva y, por tanto, debido a que $A$ no es finito, $A$ es numerable. Más adelante daremos otra prueba de este hecho utilizando resultados distintos.
Otro ejemplo interesante de conjunto numerable que podemos obtener con la proposición anterior lo veremos después de la siguientes observaciones.

En los ejercicios de esta entrada mostrarás que el conjunto $\mathbb{N}\times\mathbb{N}$ es numerable dando una función biyectiva explícita entre $\mathbb{N}\times\mathbb{N}$ y $\mathbb{N}$. Utilizando este hecho y que $\mathbb{Z}$ es numerable, lo cual probamos en el ejemplo precedente, podemos concluir que $\mathbb{Z}\times\mathbb{Z}$ es numerable. En efecto, si $f:\mathbb{N}\to\mathbb{Z}$ es la biyección que dimos en el ejemplo anterior, entonces, $F:\mathbb{N}\times\mathbb{N}\to\mathbb{Z}\times\mathbb{Z}$ definida por medio de $F(n,m)=(f(n),f(m))$ es una biyección y, por tanto, $\mathbb{Z}\times\mathbb{Z}$ es numerable. Este último hecho puede ser generalizado, es decir, es posible demostrar que si $A$ y $B$ son conjuntos numerables, entonces, $A\times B$ es numerable. Tendrás oportunidad de demostrar esto en los ejercicios de esta sección. Una vez mencionado esto pasamos al siguiente ejemplo.

Ejemplo.

El conjunto de números racionales $\mathbb{Q}$ es numerable.

Demostración.

Puedes revisar la construcción del conjunto de los números racionales en el siguiente enlace: Álgebra Superior II: Esbozo de construcción de los números racionales y reales. Como podemos observar en dicho enlace, los números racionales se definen como el conjunto de clases de equivalencia de una relación de equivalencia, $\sim$, definida sobre el conjunto $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$, y sus elementos son de la forma $\overline{(a,b)}$ con $a\in\mathbb{Z}$ y $b\in\mathbb{Z}\setminus\{0\}$. Tal relación se define como sigue: diremos que $(a,b)\sim(c,d)$ si y sólo si $a\cdot d=c\cdot b$, donde este último producto es el producto de los números enteros. Así, $\mathbb{Q}=\{\overline{(a,b)}:a\in\mathbb{Z},b\in\mathbb{Z}\setminus\{0\}\}$ donde $\overline{(a,b)}=\{(c,d)\in\mathbb{Z}\times(\mathbb{Z}\setminus\{0\}):(c,d)\sim(a,b)\}$. Observemos que $\mathbb{Q}$ no es finito, pues contiene al conjunto $\{\overline{(z,1)}:z\in\mathbb{Z}\}$, el cual es infinito.

Para mostrar que $\mathbb{Q}$ es numerable definamos $g:\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})\to\mathbb{Q}$ por medio de $g(a,b)=\overline{(a,b)}$. La función $g$ es sobreyectiva. Luego, como $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ es numerable, existe una función biyectiva $h:\mathbb{N}\to\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ y así $g\circ h:\mathbb{N}\to \mathbb{Q}$ es una función sobreyectiva y por tanto como $\mathbb{Q}$ no es finito debe ser numerable.

$\square$

Si bien hemos mostrado que $\mathbb{Q}$ es numerable, no tenemos aún una función biyectiva explícita de $\mathbb{N}$ en $\mathbb{Q}$. Lo que haremos para finalizar con esta entrada es intentar determinar una función biyectiva explícita entre $\mathbb{N}$ y $\mathbb{Q}$.

A continuación añadiremos un par de definiciones que involucran el concepto de multiplicación de naturales que vimos en la entrada Teoría de los Conjuntos I: Producto en los naturales.

Definición. Dados dos naturales $n$ y $m$, diremos que $m$ divide a $n$ si existe $k\in\mathbb{N}$ tal que $m\cdot k=n$ y lo denotaremos por $m\mid n$.

El algoritmo de la división en $\mathbb{Z}$, cuyo enunciado y demostración se puede consultar en el enlace: Álgebra Superior II: Algoritmo de la división en los enteros, nos permite concluir que, para cualesquiera naturales $n$ y $m$, con $m\not=0$, existen únicos naturales $q$ y $r$ tales que $n=mq+r$, con $0\leq r<m$. Este hecho será utilizado más adelante para probar la sobreyectividad de una función que va de $(\mathbb{N}\setminus\{0\})\times\mathbb{N}$ a un subconjunto de los números racionales.

Definición. Dados dos naturales $n$ y $m$, no ambos cero, diremos que el natural $d$ es máximo común divisor de $n$ y $m$ si se satisface lo siguiente:

1. $d\mid n$ y $d\mid m$.
2. si $d’$ es otro natural tal que $d’\mid n$ y $d’\mid m$, entonces, $d’\leq d$.

Para una prueba de que el máximo común divisor de dos naturales $n$ y $m$, no ambos cero, siempre existe y además es único, puede consultar el enlace Álgebra Superior II: Máximo común divisor. Debido a esto, es posible otorgar una notación al máximo común divisor de dos naturales $n$ y $m$; tal notación será la siguiente, si $d$ es el máximo común divisor de $n$ y $m$, escribiremos $d:=(n,m)$. Diremos además que $n,m\in\mathbb{N}$ son primos relativos si $(n,m)=1$.

Para finalizar con esta serie de definiciones y observaciones añadimos lo siguiente:

Notación. Dado un natural $n$ distinto de $0$, denotaremos por $E_n$ al conjunto $\{m\in\mathbb{N}:m\leq n\ y\ (m,n)=1\}$. Observemos que dicho conjunto es un subconjunto del número natural $s(n)=n+1$ y, por tanto, es finito, es decir, existe un único natural, que denotaremos por $\varphi(n)$, tal que $E_n\sim\varphi(n)$. Además, para cada $n\in\mathbb{N}$, con $n\not=0$, se tiene que $E_n\not=\emptyset$ pues $1\in E_n$, de modo que $\varphi(n)\not=0$.

Ahora bien, debido al buen orden de los números naturales, nos es posible dar una enumeración fija a cada conjunto $E_n$, es decir, podemos escribir $E_n=\{n_1,n_2,\ldots,n_{\varphi(n)}\}$ de tal forma que $n_1<n_2<\ldots<n_{\varphi(n)}$. No está de más recordar cómo se define el orden en $\mathbb{N}$, por lo que agregamos el siguiente enlace para que pueda ser consultado: Teoría de los Conjuntos I: Principio de inducción. Así, siempre que escribamos $E_n=\{n_1,n_2,\ldots,n_{\varphi(n)}\}$ supondremos que se cumple $n_1<n_2<\ldots<n_{\varphi(n)}$.

Una vez mencionado esto pasamos a dar otra prueba de que $\mathbb{Q}$ es numerable.

Ejemplo.

$\mathbb{Q}$ es numerable.

Por comodidad, en lo siguiente denotaremos al elemento $\overline{(a,b)}\in\mathbb{Q}$ simplemente como $\frac{a}{b}$.

Lo que haremos será exhibir una función biyectiva del conjunto $(\mathbb{N}\setminus\{0\})\times\mathbb{N}$ en el conjunto $\mathbb{Q}^{+}\cup\{\frac{0}{1}\}$, donde $\mathbb{Q}^{+}$ se puede describir como el conjunto $\mathbb{Q}^{+}=\{\frac{a}{b}:a,b\in\mathbb{Z}^{+}\}$. Si además abusamos de la notación escribiendo $0=\frac{0}{1}$ y $\mathbb{N}\setminus\{0\}=\mathbb{Z}^{+}$ (pues podemos identificar a los números naturales distintos de cero con los enteros positivos mediante la función biyectiva que envía el natural $n$ al entero $\overline{(n,0)}$), podemos escribir $\mathbb{Q}^{+}\cup\{\frac{0}{1}\}=\{\frac{a}{b}:a,b\in\mathbb{N}\setminus\{0\}\}\cup\{0\}$. Además, dado un natural $k\in\mathbb{N}\setminus\{0\}$ escribiremos $k-1$ para denotar al único natural que satisface $s(k-1)=k$.

En los ejercicios de esta sección probarás que para todo natural $n\in\mathbb{N}\setminus\{0,1\}$ existen únicos $k\in\mathbb{N}\setminus\{0,1\}$ e $i\in\{1,\ldots,\varphi(k)\}$ tales que $n=\sum_{t=1}^{k-1}\varphi(t)+i$. Una vez dicho esto definamos $F^{+}:(\mathbb{N}\setminus\set{0})\times\mathbb{N}\to\mathbb{Q}^{+}\cup\{0\}$ por medio de la siguiente regla:

$F^{+}(n,m)= \left\{ \begin{array}{lcc}
             0 &   si  & n=1,\ m=0 \\
\frac{1}{m} &  si & n=1,\ m\not=0 \\
\frac{k}{km+k_i} & si & n=\sum_{t=1}^{k-1}\varphi(t)+i
             \end{array}
   \right.$

donde en el último renglón, $k$ e $i$ son los únicos naturales que satisfacen la igualdad $n=\sum_{t=1}^{k-1}\varphi(t)+i$, con $i\in\{1,\ldots,\varphi(k)\}$, y $k_i$ es el $i-$ésimo elemento que aparece en la enumeración del conjunto $E_{k}=\{k_1,\ldots,k_i,\ldots,k_{\varphi(k)}\}$, enumeración que acordamos satisface $k_1<k_2<\ldots<k_{\varphi(k)}$.
Debido a la únicidad de los naturales $k$ e $i$ para cada $n\in\mathbb{N}\setminus\{0,1\}$, $F^{+}$ es una función bien definida. Veamos que es biyectiva.

Comprobaremos en primer lugar la inyectividad. Sean $(n,m),(n’,m’)\in(\mathbb{N}\setminus\{0\})\times\mathbb{N}$ elementos distintos. Distinguiremos los siguientes casos:

Caso 1. $n=n’$. Dado que $(n,m)\not=(n’,m’)$ pero $n=n’$, entonces, $m\not=m’$. Sin perder generalidad podemos suponer que $m<m’$. Ahora, podemos considerar los siguientes dos subcasos.
Subcaso 1. $n=1$. Si $m=0$, entonces, $0<m’$ y así $F^{+}(n,m)=0$ mientras que $F^{+}(n’,m’)=\frac{1}{m’}$, por lo que $F^{+}(n,m)\not=F^{+}(n’,m’)$. Si ahora $m\not=0$, entonces, $m’\not=0$ y tenemos que $F^{+}(n,m)=\frac{1}{m}$ y $F^{+}(n’,m’)=\frac{1}{m’}$; luego, $\frac{1}{m}\not=\frac{1}{m’}$, pues $m=1\cdot m\not=1\cdot m’=m’$, de modo que $F^{+}(n,m)\not=F^{+}(n’,m’)$.
Subcaso 2. $n>1$. Sean $k\in\mathbb{N}\setminus\{0,1\}$ e $i\in\{1,\ldots,\varphi(k)\}$ tales que $n’=n=\sum_{t=1}^{k-1}\varphi(t)+i$. Luego, $F^{+}(n,m)=\frac{k}{km+k_i}$ y $F^{+}(n’,m’)=\frac{k}{km’+k_i}$ y como $km’+k_i\not=km+k_i$, pues de lo contrario obtendríamos que $m=m’$, se sigue que $k\cdot(km’+k_i)\not=k\cdot(km+k_i)$, es decir, $F^{+}(n,m)=\frac{k}{km+k_i}\not=\frac{k}{km’+k_i}=F^{+}(n’,m’)$.

Caso 2. $n\not=n’$. Sin pérdida de generalidad podemos suponer $n<n’$. Si $n=1$, entonces, o bien $F^{+}(n,m)=0$ o bien $F^{+}(n,m)=\frac{1}{m}$; por otro lado, como $n’>n=1$, entonces podemos elegir $k\in\mathbb{N}\setminus\set{0,1}$ e $i\in\{1,\ldots,\varphi(k)\}$ tales que $n’=\sum_{t=1}^{k-1}\varphi(t)+i$ y así $F^{+}(n’,m’)=\frac{k}{km’+k_i}$. Luego entonces, $F^{+}(n,m)\not=F^{+}(n’,m’)$ ya que claramente $\frac{k}{km’+k_i}\not=0$, pero también $\frac{k}{km’+k_i}\not=\frac{1}{m}$ pues de darse la igualdad se tendría que $m\cdot k=1\cdot(km’+k_i)$, lo cual implicaría que $k$ divide a $k_i$ y eso es imposible, pues $k>1$ y $(k,k_i)=1$.
Si ahora $n>1$, podemos fijar $k’\in\mathbb{N}\setminus\{0,1\}$ y $j\in\{1,\ldots,\varphi(k’)\}$ tales que $n=\sum_{t=1}^{k’-1}\varphi(t)+j$. Luego, suponiendo también, como en el párrafo anterior, $n’=\sum_{t=1}^{k-1}\varphi(t)+i$, tenemos que $F^{+}(n,m)=\frac{k’}{k’m+k’_j}$ y $F^{+}(n’,m’)=\frac{k}{km’+k_i}$. Si $k=k’$, entonces, $j<i$, pues de lo contrario tendríamos que $\sum_{t=1}^{k-1}\varphi(t)+i=n’\leq\sum_{t=1}^{k-1}\varphi(t)+j=\sum_{t=1}^{k’-1}\varphi(t)+j=n$, lo cual es una contradicción; en consecuencia, $k’_j=k_j<k_i$ y, más aún, $\frac{k’}{k’m+k’_j}=\frac{k}{km+k_j}\not=\frac{k}{km’+k_i}$, pues en caso contrario se seguiría que $k\cdot(km’+k_i)=k\cdot(km+k_j)$ y, por tanto, que $km’+k_i=km+k_j$ lo cual es imposible pues se seguiría que, en $\mathbb{Z}$, $k$ divide a $k_i-k_j$ el cual es un entero que satisface $0<k_i-k_j<k$.
Para concluir el caso $2$ supongamos que $k\not=k’$. Dado que $(k’,k’m+k’_j)=1=(k,km’+k_i)$, pues de lo contrario $k’$ no sería primo relativo con $k’_j$ así como $k$ no lo sería con $k_i$, entonces, $\frac{k’}{k’m+k’_j}\not=\frac{k}{km’+k_i}$, es decir, $F^{+}(n,m)\not=F^{+}(n’,m’)$. Esto demuestra que $F^{+}$ es una función inyectiva.

Probemos ahora que $F^{+}$ es sobreyectiva. Sea $\frac{p}{q}\in\mathbb{Q}^{+}\cup\{0\}$. Si $\frac{p}{q}=0$, entonces, $\frac{p}{q}=F^{+}(1,0)$. Si $\frac{p}{q}=\frac{1}{m}$, entonces, $\frac{p}{q}=F^{+}(1,m)$. Supongamos ahora que $\frac{p}{q}\not=0$ y que $\frac{p}{q}\not=\frac{1}{m}$ para cada $m\in\mathbb{N}\setminus\set{0}$. Podemos suponer que $(p,q)=1$. Luego, existen únicos naturales $m$ y $r$ tales que $q=pm+r$ con $0\leq r<p$. Nótese que $r\not=0$, pues en caso contrario se tendría que $p$ divide a $q$, pero como $(p,q)=1$ se seguiría que $p=1$, lo cual contradice que $\frac{p}{q}\not=\frac{1}{m}$ para cada $m\in\mathbb{N}\setminus\set{0}$. Así pues, $1\leq r<p$. Ahora bien, $(r,p)=1$, pues de lo contrario, $p$ y $q=pm+r$ compartirían un factor distinto de $1$; es decir, existiría un natural $k$ mayor a $1$ tal que $k$ divide a $p$ y $q$, lo cual contradice que $(p,q)=1$. Por tanto, $(r,p)=1$ y, en consecuencia, $r\in E_p=\{p_1,\ldots,p_{\varphi(p)}\}$. Sea $i\in\{1,\ldots,\varphi(p)\}$ tal que $r=p_i$. Luego, $F^{+}(\sum_{t=1}^{p-1}\varphi(t)+i,m)=\frac{p}{pm+p_i}=\frac{p}{pm+r}=\frac{p}{q}$. Por tanto, $F^{+}$ es sobreyectiva.

Lo anterior prueba que $F^{+}$ es una biyección de $(\mathbb{N}\setminus\{0\})\times\mathbb{N}$ en $\mathbb{Q}^{+}\cup\{0\}$. Luego, como la función $f:\mathbb{N}\times\mathbb{N}\to(\mathbb{N}\setminus\set{0})\times\mathbb{N}$ definida por medio de $f(n,m)=(s(n),m)$ es una biyección entre estos conjuntos, y existe $g:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ función biyectiva (como lo comprobarás en los ejercicios de esta sección), concluimos que $F^{+}\circ f\circ g:\mathbb{N}\to\mathbb{Q}^{+}\cup\{0\}$ es una biyección de $\mathbb{N}$ en $\mathbb{Q}^{+}$. Finalmente, como $\mathbb{Q}=\mathbb{Q}^{+}\cup\set{0}\cup\mathbb{Q}^{-}$, donde $\mathbb{Q}^{-}$ puede ser descrito por el conjunto $\{\frac{a}{b}:a\in\mathbb{Z}^{-},b\in\mathbb{Z}^{+}\}$, y $\mathbb{Q}^{-}$ es equipotente a $\mathbb{Q}^{+}$, entonces, $\mathbb{Q}$ es la unión ajena de dos conjuntos numerables; luego, como probarás en los ejercicios de esta entrada, se sigue que $\mathbb{Q}$ es numerable. Por tanto, $\mathbb{N}$ es equipotente a $\mathbb{Q}$.

$\square$

Aún cuando la función biyectiva que dimos en el último ejemplo no posee una regla de correspondencia agradable, sí es explícita, aunque resulte todavía complicado en la práctica calcular la imagen de la mayoría de los números naturales bajo dicha función.

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada.

1. Si un conjunto $A$ es numerable y $x\in A$ es un elemento arbitrario, ¿será cierto que $A\setminus\set{x}$ es también numerable?
2. Sea $\mathbb{N}_0:=\mathbb{N}\setminus\set{0}$. Muestra que $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}_0$ dada por $f(n,m)=2^n(2m+1)$ es una función biyectiva.
3. Utilizando el ejercicio anterior, muestra que si $A$ y $B$ son conjuntos numerables, entonces $A\times B$ también es numerable.
4. Sean $A$ y $B$ conjuntos ajenos y numerables. Muestra que $A\cup B$ es numerable . ¿Y si los conjuntos $A$ y $B$ no son ajenos?
5. Demuestra que para cada $n\in\mathbb{N}\setminus\set{0,1}$, existen únicos $k\in\mathbb{N}\setminus\{0,1\}$ e $i\in\{1,\ldots,\varphi(k)\}$ tales que $n=\sum_{t=1}^{k-1}\varphi(t)+i$.

Más adelante…

En la siguiente entrada concluiremos el contenido acerca de cardinalidad de conjuntos infinitos. Daremos cierre a esta unidad con el tema de aritmética cardinal.

Entradas relacionadas

• Ir a Teoría de los Conjuntos I
• Entrada anterior: Conjuntos infinitos
• Siguiente entrada: Aritmética cardinal

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»