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.

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 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 numeració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)}\}$ asumiremos que se cumple $n_1<n_2<\ldots<n_{\varphi(n)}$.

Ahora podemos pasar al siguiente ejemplo.

Ejemplo.

El conjunto $\mathbb{N}$ es equipotente al conjunto de los números racionales $\mathbb{Q}$.

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 las clases de equivalencia de una relación de equivalencia, $\sim$, 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. Por comodidad denotaremos al elemento $\overline{(a,b)}$ 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 numeración del conjunto $E_{k}=\{k_1,\ldots,k_i,\ldots,k_{\varphi(k)}\}$, numeració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 $(\mathbb{N}\setminus\set{0})\times\mathbb{N}$ es equipotente a $\mathbb{N}\times\mathbb{N}$ (basta definir $f:\mathbb{N}\times\mathbb{N}\to(\mathbb{N}\setminus\set{0})\times\mathbb{N}$ por medio de $f(n,m)=(s(n),m)$ para obtener la biyección entre estos conjuntos) y $\mathbb{N}\times\mathbb{N}$ es equipotente a $\mathbb{N}$ (lo cual probarás en los ejercicios de esta entrada), se sigue $\mathbb{Q}^{+}\cup\{0\}$ es numerable. 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$

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»