Introducción
Ahora que hemos introducido el concepto de contar elementos y hemos hablado acerca de 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. El propósito de esta entrada es ver que existen infinitos más grandes que otros.
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í, diremos que $|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 $$|\set{x\in \mathbb{N}:x=2k\ \text{para algún} \ 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(x)= \left\{ \begin{array}{lcc}
\frac{x}{2} & si & x =2k\ \text{para algún}\ k\in \mathbb{N} \\
\\ -\frac{x+1}{2} & si & x=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 $n,m\in \mathbb{N}$, entonces $f(x_1)=\frac{x_1}{2}$ y $f(x_2)=\frac{x_2}{2}$ y así, $\frac{x_1}{2}=\frac{x_2}{2}$ y por lo tanto, $x_1=x_2$.
Caso 2. Si $x_1=2k+1$ y $x_2=2m+1$ para algunos $n,m\in \mathbb{N}$, entonces $f(x_1)=-\frac{x_1+1}{2}$ y $f(x_2)=-\frac{x_2+1}{2}$ y así, $-\frac{x_1+1}{2}=-\frac{x_2+1}{2}$, entonces $-(x_1+1)=-(x_2+1)$, entonces $x_1+1=x_2+1$ y por lo tanto, $x_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 $\frac{x_1}{2}=-\frac{x_2+1}{2}$ por lo que $x_1=-(x_2+1)$, lo cual es una contradicción pues $x_1\in \mathbb{N}$ y $-(x_2+1)\notin \mathbb{N}$. 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{0}=\set{0,1,2,\dots}$, entonces para $x=2y\in \mathbb{N}$ se tiene que $f(2y)=\frac{2y}{2}=y$.
Caso 2: Si $y\in \mathbb{Z}^-=\set{-1,-2, \dots}$, entonces $x=-2y-1\in \mathbb{N}$ y se tiene que $f(-2y-1)=-\frac{-2y-1+1}{2}=y$.
Concluimos que $f$ es suprayectiva.
Por lo tanto, $f$ es biyectiva y así, $|\mathbb{N}|=|\mathbb{Z}|$.
$\square$
En los ejercicios explorarás algunas propiedades de los conjuntos numerables.
Si recuerdas, en la entrada de conjuntos finitos demostramos que la unión de una cantidad finita de conjuntos finitos es un conjunto finito. Si la familia $A=\{A_n\}_{n\in \mathbb{N}}$ cumple que cada uno de sus conjuntos $A_n$ es numerable, ¿será cierto que la unión de $A$ es numerable? La respuesta es que sí, pero para demostrarlo necesitaremos llegar a la última unidad del curso, pues la prueba que daremos usará el axioma de elección. Como en temas anteriores, la intuición es que para mostrar $|\bigcap A|=\mathbb{N}$, debemos construir una función biyectiva, pero teniendo tantos conjuntos, suena plausible que esta función necesitará que tomemos una infinidad de decisiones.
Conjuntos no numerables
Hasta ahora todos los conjuntos infinitos que nos hemos encontrado son numerables. ¿Habrá algún conjunto infinito que no sea numerable? La respuesta es que sí. La existencia de conjuntos infinitos de «distintos tamaños» fue un resultado muy sorprendente. El ejemplo que veremos a continuación requerirá del argumento de la diagonal de Cantor.
Teorema. Sea $X$ un conjunto. Entonces no existe una biyección $f:\mathbb{N}\to \mathcal{P}(\mathbb{N})$.
Demostración. La demostración es por contradicción. Supongamos que sí existe tal biyección $f$. Construyamos un subconjunto $Y$ de $\mathbb{N}$ como sigue:
$$Y=\{n\in \mathbb{N}: n\not \in f(n)\}.$$
Por definición, $Y\subseteq \mathbb{N}$. Como $f$ es una biyección, debe existir un natural $y$ tal que $f(y)=Y$. Pero, ¿$y$ está en $Y$? Si $y\in Y$, entonces $y\in f(y)$, pero luego $y\not \in Y$, lo cual es una contradicción. Si $y\not \in Y$, entonces $y\not \in f(y)$ y así $y\in Y$, lo cual también es una contradicción. Cualquier opción lleva a una contradicción, que surgió de suponer que existía una biyección $f:\mathbb{N}\to \mathcal{P}(\mathbb{N})$. Por lo tanto, no puede existir dicha biyección.
$\square$
El argumento anterior debe recordarte mucho a la paradoja del barbero con la cual abrimos las primeras discusiones del curso.
Tarea moral
La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada.
- 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?
- 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.
- Utilizando el ejercicio anterior, muestra que si $A$ y $B$ son conjuntos numerables, entonces $A\times B$ también es numerable.
- 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?
- Demuestra que, en general, para ningún conjunto $X$ se cumple que $X\sim \mathcal{P}(X)$.
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»