Introducción
En la entrada anterior hemos mostrado algunos ejemplos de conjuntos equipotentes al conjunto de los números naturales. En algunos casos exhibimos funciones biyectivas del conjunto de los números naturales en cada uno de los respectivos conjuntos. Sin embargo, esta labor puede resultar complicada, en muchas ocasiones exhibir funciones biyectivas de un conjunto en otro presenta diversas dificultades. Debido a esto, en varias situaciones resulta muy útil aplicar el teorema de Cantor-Schröder-Bernstein para mostrar que dos conjuntos son equipotentes sin necesidad de proporcionar una biyección. En esta entrada añadiremos otro par de ejemplos de conjuntos equipotentes al conjunto de los números naturales, pero haremos uso del teorema de Cantor-Schröder-Bernstein para mostrar tal equipotencia.
Conjuntos numerables.
En el siguiente ejemplo aparece un conjunto que ya conocíamos y que de hecho se encuentra en la entrada anterior, se trata del conjunto de números racionales, para el cual dimos dos maneras de mostrar que es numerable.
Ejemplo.
$\mathbb{Q}$ es numerable, es decir, equipotente a $\mathbb{N}$.
Lo que haremos será mostrar que $\mathbb{Q}^{+}\cup\{0\}$ y $\mathbb{N}$ son equipotentes con ayuda del teorema de Cantor-Schröder-Bernstein. Luego, como $\mathbb{Q}^{-}$ y $\mathbb{Q}^{+}$ son equipotentes podremos concluir que $\mathbb{Q}$ es la unión de dos conjuntos ajenos numerables y, por tanto, que $\mathbb{Q}$ es numerable.
Ante un claro abuso de notación en lo que sigue, definamos $f:\mathbb{N}\to\mathbb{Q}^{+}\cup\{0\}$ por medio de $f(n)=\frac{n}{1}$. Luego, $f$ es una función inyectiva de $\mathbb{N}$ en $\mathbb{Q}^{+}\cup\{0\}$, pues si $f(n)=f(m)$, entonces, $\frac{n}{1}=\frac{m}{1}$ lo cual implica que $n\cdot 1=m\cdot1$, es decir, $n=m$. Ahora, tenemos que exhibir una función inyectiva de $\mathbb{Q}^{+}\cup\{0\}$ en $\mathbb{N}$. Definamos $g:\mathbb{Q}^{+}\cup\{0\}\to\mathbb{N}\times\mathbb{N}$ por medio de $$g\left(\frac{p}{q}\right)=\left\{\begin{array}{lcc}
(p,q) & \textnormal{si}\ \frac{p}{q}\in\mathbb{Q}^{+}\ \textnormal{y}\ p\ \textnormal{y}\ q\ \textnormal{son primos relativos}\\
(0,0) & \textnormal{si}\ \frac{p}{q}=0
\end{array}
\right.$$
Debido a que cada racional en $\mathbb{Q}^{+}$ tiene una expresión única de la forma $\frac{p}{q}$ con $p$ y $q$ primos relativos, entonces, $g$ está bien definida. Veamos que $g$ es inyectiva. Supongamos que $\frac{p}{q},\frac{s}{t}\in\mathbb{Q}^{+}\cup\{0\}$ son tales que $g(\frac{p}{q})=g(\frac{s}{t})$. Si $\frac{p}{q}=0$, entonces, $g(\frac{p}{q})=(0,0)$ y así $g(\frac{s}{t})=(0,0)$; luego, $\frac{s}{t}=0$, pues en caso contrario, podríamos asumir que $s$ y $t$ son primos relativos y por tanto $g(\frac{s}{t})=(s,t)\not=(0,0)$ ya que $s\not=0$. Así pues, si $\frac{p}{q}=0$, entonces, $\frac{s}{t}=0$. Análogamente, si $\frac{s}{t}=0$, entonces, $\frac{p}{q}=0$. Supongamos ahora que $\frac{p}{q}\not=0\not=\frac{s}{t}$ y que tanto $p$ y $q$ como $s$ y $t$, son primos relativos. Así, $g(\frac{p}{q})=(p,q)$ y $g(\frac{s}{t})=(s,t)$ y por consiguiente, $(p,q)=(s,t)$, de modo que $s=p$ y $q=t$, lo que demuestra que $\frac{p}{q}=\frac{s}{t}$. Por tanto, $g$ es una función inyectiva. Finalmente, si consideramos la función inyectiva $h:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ definida por medio de $h(n,m)=2^n(2m+1)$, la cual aparece en los ejercicios de la sección anterior, tendremos que $h\circ g:\mathbb{Q}^{+}\cup\{0\}\to\mathbb{N}$ es una función inyectiva. Por el teorema de Cantor-Schröder-Bernstein concluimos que $\mathbb{Q}^{+}\cup\{0\}$ es numerable y, consecuentemente, $\mathbb{Q}$ es numerable.
$\square$
El siguiente ejemplo también aparece en la entrada anterior, pero ahora utilizaremos el teorema de Cantor-Schröder-Bernstein. Como bien lo vimos, dicho ejemplo nos proporciona una gran cantidad de conjuntos numerables y, al mismo tiempo, muestra una propiedad interesante del conjunto de números naturales.
Ejemplo.
Si $A\subseteq\mathbb{N}$ es un conjunto infinito, entonces, $A$ es numerable.
Demostración.
Sea $A\subseteq\mathbb{N}$ un conjunto infinito. La función $\iota:A\to\mathbb{N}$ definida por medio de $\iota(n)=n$ para cada $n\in\mathbb{N}$ es una función inyectiva. Ahora vamos a exhibir una función inyectiva de $\mathbb{N}$ en $A$.
Para cada $n\in A$ definamos $n^{\uparrow}:=\{m\in A:n<m\}$. Notemos que para cada $n\in A$, $n^{\uparrow}\not=\emptyset$, pues en caso contrario existiría $n\in A$ tal que para cada $m\in A$, $m\leq n$ y en consecuencia, $A\subseteq s(n)=n\cup\{n\}$, lo cual implicaría que $A$ es finito, contradiciendo la hipótesis sobre $A$. Así pues, por el buen orden de $\mathbb{N}$, para cada $n\in A$ existe $min(n^{\uparrow})$. Una vez hecho lo anterior elijamos $n_0=min(A)$ y definamos $g:A\to A$ por medio de $g(n)=min(n^{\uparrow})$. Por el teorema de recursión, existe una única función $f:\mathbb{N}\to A$ tal que $f(0)=n_0$ y $f(n+1)=g(f(n))$ para cada $n\in\mathbb{N}$. Veamos que $f$ es una función inyectiva. Para ello, veamos que $f(n)<f(n+1)$ para cada $n\in\mathbb{N}$. Sea $n\in\mathbb{N}$. Luego, $f(n+1)=g(f(n))=min(f(n)^{\uparrow})$ por lo que $f(n+1)\in f(n)^{\uparrow}$ y así $f(n)<f(n+1)$. Por lo tanto $f$ es una función inyectiva de $\mathbb{N}$ en $A$. Por el teorema de Cantor-Schröder-Bernstein podemos concluir que $\mathbb{N}$ y $A$ son equipotentes.
$\square$
Como probarás en los ejercicios de esta entrada, la función $f:\mathbb{N}\to A$ que aparece en el ejemplo precedente es de hecho biyectiva. Por otro lado, como lo habíamos mencionado previo al ejemplo, éste nos proporciona una gran cantidad de conjuntos numerables; por mencionar algunos tenemos los conjuntos $A_n:=\{m\in\mathbb{N}:n<m\}$ para cada $n\in\mathbb{N}$, o también algunos que ya conocíamos como el conjunto de números pares $\{2k:k\in\mathbb{N}\}$, el cual ya sabíamos que era equipotente a $\mathbb{N}$, y algunos otros más interesantes, como el conjunto de números primos pues dicho conjunto es infinito. Para conocer la definición de número primo puedes consultar el siguiente enlace Álgebra Superior II: Números primos y sus propiedades.
Otra consecuencia del ejemplo anterior es el siguiente corolario.
Corolario. Si $B$ es un conjunto numerable y $A\subseteq B$ es un conjunto inifinito, entonces, $A$ es un conjunto numerable.
Demostración.
Dado que $B$ es numerable, existe una función biyectiva $g:B\to\mathbb{N}$. Luego, la restricción de $g$ al conjunto $A$, $g\upharpoonright_{A}:A\to\mathbb{N}$, es una función inyectiva y, más aún, es una biyección entre $A$ y $g[A]\subseteq\mathbb{N}$. Dado que $A$ es infinito, también lo es $g[A]$, pero por el ejemplo anterior sabemos que $g[A]$ es numerable y, en consecuencia, $A$ es numerable.
$\square$
Hasta ahora, en los dos ejemplos que hemos visto, si bien hicimos uso del teorema de Cantor-Schröder-Bernstein y nos facilitó probar la equipotencia de tales conjuntos con $\mathbb{N}$, también es factible exhibir o mostrar directamente la existencia de una función biyectiva. En los ejemplos subsecuentes será más clara la utilidad e importancia del teorema de Cantor-Schröder-Bernstein, y además un tanto más interesantes, pues sin dicho teorema probar la equipotencia con $\mathbb{N}$ es bastante más complicado.
Para introducir el siguiente ejemplo es necesario mencionar un resultado importante del conjunto de números enteros, conocido como el teorema fundamental de la aritmética. Tal teorema asegura que dado cualquier número entero positivo mayor a 1, éste tiene una expresión única como producto de números primos, es decir, si $z\in\mathbb{Z}^{+}$ es cualquier entero positivo mayor a 1, existen únicos números primos $p_1,\ldots,p_n$ y únicos números naturales distintos de cero $\alpha_1,\ldots,\alpha_n$ tales que $z=p_1^{\alpha_1}\cdots p_n^{\alpha_n}=\Pi_{i=1}^{n}p_i^{\alpha_i}$. Puedes consultar el teorema fundamental de la aritmética y su prueba en el siguiente enlace Álgebra Superior II: Teorema fundamental de la aritmética e infinidad de números primos; más aún, en dicho enlace puedes encontrar la prueba de que el conjunto de números primos es inifinito y, de acuerdo al último ejemplo que enunciamos, éste conjunto es numerable.
Ejemplo.
$[\mathbb{N}]^{<\mathbb{N}}:=\{A\subseteq\mathbb{N}:A\ \textnormal{es finito}\}$ es numerable.
Demostración.
Notemos que la función $f:\mathbb{N}\to[\mathbb{N}]^{<\mathbb{N}}$ definida por medio de $f(n)=\{n\}$ es una función inyectiva, de modo que para aplicar el teorema de Cantor-Schröder-Bernstein hace falta exhibir una función inyectiva de $[\mathbb{N}]^{<\mathbb{N}}$ en $\mathbb{N}$.
Para construir tal función inyectiva, consideremos en primer lugar al conjunto de números primos $\mathbb{P}:=\{p\in\mathbb{Z}^{+}:p\ \textnormal{es primo}\}$. Dado que $\mathbb{P}$ puede ser visto como un subconjunto de $\mathbb{N}$, sabemos, por el ejemplo anterior, que existe una función (biyectiva) $f:\mathbb{N}\to \mathbb{P}$ tal que $f(0)=min(\mathbb{P})$ y tal que $f(n)<f(n+1)$ para cada $n\in\mathbb{N}$. Así, si denotamos como $p_n:=f(n)$ para cada $n\in\mathbb{N}$, podemos escribir $\mathbb{P}=\{p_n:n\in\mathbb{N}\}$ y se satisface que $p_n<p_{n+1}$ para cada $n\in\mathbb{N}$. Vamos a considerar para el resto de la prueba que $\mathbb{P}$ está enumerado de esta manera.
Ahora bien, si $A\subseteq\mathbb{N}$ es un conjunto finito y no vacío, digamos $|A|=n+1$ con $n\in\mathbb{N}$, entonces, $A$ puede ser enumerado de manera similar a como lo hicimos con $\mathbb{P}$; esto es, existe una función biyectiva (de hecho única) $f_A:n+1\to A$ tal que $f_A(0)=min(A)$ y $f_A(k)<f_A(m)$ si y sólo si $k<m$. Así, si denotamos como $a_k:=f_A(k)$ para cada $k\in n+1$, tenemos que $A=\{a_k:k\in n+1\}$ y que $a_k<a_m$ si y sólo si $k<m$. Para el resto de la prueba utilizaremos estas enumeraciones con cualquier subconjunto finito no vacío de $\mathbb{N}$, es decir, dado $A\subseteq\mathbb{N}$ no vacío, con $|A|=n+1$, escribiremos $A=\{a_k:k\in n+1\}$ y se entenderá que $a_k<a_m$ si y sólo si $k<m$.
Una vez mencionado lo anterior definamos $F:[\mathbb{N}]^{<\mathbb{N}}\setminus\{\emptyset\}\to\mathbb{Z}^{+}$ por medio de $F(A)=\Pi_{k=0}^{n}p_k^{a_k}$ si $A=\{a_k:k\in n+1\}$, para cada $A\in[\mathbb{N}]^{<\mathbb{N}}\setminus\{\emptyset\}$. Veamos que tal función es inyectiva. Supongamos que $A,B\in[\mathbb{N}]^{<\mathbb{N}}\setminus\{\emptyset\}$ son conjuntos tales que $F(A)=F(B)$. Si $|A|=n+1$ y $|B|=m+1$ con $n,m\in\mathbb{N}$, y además $A=\{a_k:k\in n+1\}$ y $B=\{b_k:k\in m+1\}$, entonces, $F(A)=\Pi_{k=0}^{n}p_k^{a_k}$ mientras que $F(B)=\Pi_{k=0}^{m}p_k^{b_k}$; luego, como $\Pi_{k=0}^{n}p_k^{a_k}=\Pi_{k=0}^{m}p_k^{b_k}$ se tiene $n=m$, pues si $n<m$, entonces, $m>0$ y $b_m>0$, ya que $b_m>b_0$ y $b_0\geq0$, por lo que $p_m^{b_m}$ es una potencia positiva del primo $p_m$ que no aparece en el producto $\Pi_{k=0}^{n}p_k^{a_k}$, pero que sí aparece en el producto $\Pi_{k=0}^{m}p_k^{b_k}$, lo cual contradice el teorema fundamental de la aritmética. Análogamente, no puede ocurrir que $m<n$. Por tanto, $n=m$ y, por consiguiente, $a_k=b_k$ para cada $k\in n+1$. En consecuencia, $A=B$. Por tanto, $F$ es una función inyectiva. Finalmente, como $\mathbb{Z}^{+}$ es numerable, existe $G:\mathbb{Z}^{+}\to\mathbb{N}\setminus\set{0}$ función biyectiva y así $G\circ F:[\mathbb{N}]^{<\mathbb{N}}\setminus\set{\emptyset}\to\mathbb{N}\setminus\set{0}$ es una función inyectiva. Por consiguiente, la función $\tilde{F}:[\mathbb{N}]^{<\mathbb{N}}\to\mathbb{N}$ definida por medio de $$\tilde{F}(A)=\left\{ \begin{array}{lcc}
0 & \textnormal{si}\ A=\emptyset \\
(G\circ F)(A) & \textnormal{si}\ A\not=\emptyset
\end{array}
\right.$$
es inyectiva. El teorema de Cantor-Schröder-Bernstein nos permite concluir que $[\mathbb{N}]^{<\mathbb{N}}$ es numerable.
$\square$
Para el último ejemplo que trataremos en esta entrada vamos a definir lo que es una sucesión.
Definición. Si $A$ es un conjunto y $f:\mathbb{N}\to A$ es una función, diremos que $f$ es una sucesión en $A$. Por otro lado, si $n\in\mathbb{N}$ y $g:n\to A$ es una función, diremos que $g$ es una sucesión finita de longitud $n$ en $A$.
Dado un conjunto $A$ vamos a denotar como $^nA$ al conjunto de todas las sucesiones finitas de longitud $n$ en $A$.
Ejemplo.
El conjunto $\mathbb{N}^{<\mathbb{N}}:=\cup_{n\in \mathbb{N}}\ ^n\mathbb{N}$ es numerable.
Demostración.
Primero vamos a dar una función inyectiva de $\mathbb{N}$ en $\mathbb{N}^{<\mathbb{N}}$. Para cada $n\in\mathbb{N}\setminus\{0\}$ definamos $x_n:1\to\mathbb{N}$ como $x_n(0)=n$. Si $n\in\mathbb{N}\setminus\{0\}$, $x_n$ es una sucesión finita de longitud $1$ en $\mathbb{N}$, es decir, $x_n\in{^1\mathbb{N}}$. Ahora, para $n=0$ definamos $x_0:=\emptyset:0\to\mathbb{N}$ la función vacía, es decir, la única sucesión finita de longitud $0$ en $\mathbb{N}$, de modo que $x_0\in{^0\mathbb{N}}$. Una vez definidas estas sucesiones finitas vamos a considerar la función $f:\mathbb{N}\to\mathbb{N}^{<\mathbb{N}}$ dada por $f(n)=x_n$ para cada $n\in\mathbb{N}$. Notemos que $f$ es inyectiva, pues si $n,m\in\mathbb{N}$ son naturales distintos podemos suponer que $n<m$; luego, si $n=0$, entonces $f(n)=f(0)=x_0=\emptyset$ mientras que $m>0$ y $f(m)=x_m=\{(0,m)\}$, de modo que $f(n)\not=f(m)$. Si ahora $0<n$, entonces también $0<m$ y $f(n)=x_n=\{(0,n)\}$ mientras que $f(m)=x_m=\{(0,m)\}$, pero dado que $(0,n)\not=(0,m)$ pues $n\not=m$, concluimos que $f(n)\not=f(m)$. Por tanto $f$ es inyectiva.
Ahora vamos a dar una función inyectiva de $\mathbb{N}^{<\mathbb{N}}$ en $\mathbb{N}$. En el penúltimo ejemplo consideramos al conjunto de números primos enumerado como $\mathbb{P}=\{p_n:n\in\mathbb{N}\}$ de tal manera que $p_n<p_{n+1}$ para cada $n\in\mathbb{N}$. Retomando dicha enumeración del conjunto de números primos definamos $g:\mathbb{N}^{<\mathbb{N}}\to\mathbb{N}\times\mathbb{Z}$ por medio de $$g(x)=\left\{\begin{array}{lcc}
(n+1,\Pi_{k=0}^{n}p_k^{x(k)}) & \textnormal{si}\ x\in{^{n+1}\mathbb{N}} \\
(0,0) & \textnormal{si}\ x=\emptyset
\end{array}
\right.
$$
Probar que la función $g$ es inyectiva requiere, esencialmente, del teorema fundamental de la aritmética; si $x\in{^{n+1}\mathbb{N}}$ y $y\in{^{m+1}\mathbb{N}}$ con $n\not=m$, entonces, $n+1\not=m+1$ y por ende $g(x)=(n+1,\Pi_{k=0}^{n}p_k^{x(k)})\not=(m+1,\Pi_{k=0}^{m}p_k^{y(k)})=g(y)$. Si $x=\emptyset$ y $y\in{^{n+1}\mathbb{N}}$ con $n\in\mathbb{N}$, entonces $g(y)=(n+1,\Pi_{k=0}^{n}p_k^{y(k)})\not=(0,0)=g(x)$. Por tanto, para concluir que $g$ es inyectiva, basta comprobar que si $n\in\mathbb{N}$ y $x,y\in{^{n+1}\mathbb{N}}$ son elementos distintos, entonces $g(x)\not=g(y)$, lo cual dejamos como un ejercicio al final de esta entrada.
Por el teorema de Cantor-Schröder-Bernstein, $\mathbb{N}^{<\mathbb{N}}$ es numerable.
$\square$
Tarea moral
- Sea $A\subseteq\mathbb{N}$ conjunto inifinito. Para cada $n\in A$ definimos $n^{\uparrow}:=\{m\in A:n<m\}$. Definimos $g:A\to A$ por medio de $g(n)=\textnormal{min}(n^{\uparrow})$ y consideremos la única función $f:\mathbb{N}\to A$ tal que $f(0)=\textnormal{min}(A)$ y $f(n+1)=g(f(n))$ para cada $n\in\mathbb{N}$. Demuestra que $f$ es una biyección.
- Prueba que la función $g:\mathbb{N}^{<\mathbb{N}}\to\mathbb{N}\times\mathbb{Z}$ definida por medio de $g(x)=\left\{\begin{array}{lcc} (n+1,\Pi_{k=0}^{n}p_k^{x(k)}) & \textnormal{si}\ x\in^{n+1}\mathbb{N} \\ (0,0) & \textnormal{si}\ x=\emptyset
\end{array}
\right.$ es inyectiva.
- Demuestra lo siguiente:
$(a)$ Si $A\subseteq\mathbb{N}$ es un conjunto finito no vacío con $|A|=n+1$, $n\in\mathbb{N}$, existe una única función biyectiva $f_A:n+1\to A$ tal que $f_A(0)=\textnormal{min}(A)$ y que $f_A(m)<f_A(k)$ si y sólo si $m<k$ para cualesquiera $m,k\in n+1$.
$(b)$ Utilizando el hecho de que $\mathbb{N}^{<\mathbb{N}}$ es numerable muestra que $[\mathbb{N}]^{<\mathbb{N}}$ es numerable. Puede que te ayude de algo el inciso $(a)$.
- Demuestra que si $B\subseteq A$ son conjuntos tales que $B$ es numerable pero $A$ no, entonces, $A\setminus B$ no es numerable.
- Diremos que una sucesión $x$ en $\mathbb{N}$ es semiconstante si existe $n_0\in\mathbb{N}$ tal que para cada $n\geq n_0$, $x(n)=x(n_0)$. Demuestra que si $\mathcal{S}$ es el conjunto de todas las sucesiones semiconstantes en $\mathbb{N}$, entonces $\mathcal{S}$ es numerable.
Más adelante…
En la siguiente entrada concluiremos el contenido acerca de conjuntos infinitos y veremos ejemplos de conjuntos no numerables.
Entradas relacionadas
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»
