El infinito de ℝ: la diagonal de Cantor

En la lección anterior vimos que $\mathbb{R}$ llena los huecos que $\mathbb{Q}$ deja. Queda una pregunta enorme: $\mathbb{Q}$ y $\mathbb{R}$ son ambos infinitos — ¿son el mismo infinito? Cantor probó que no. Y la herramienta es tan simple que parece trampa.

Contar lo infinito

Un conjunto es numerable si se puede poner en una lista $x_1, x_2, x_3, \dots$ sin que falte ninguno — formalmente, si existe una biyección $f : \mathbb{N} \to S$ . Numerable no quiere decir finito: quiere decir enumerable.

Sorprende cuánto entra en una lista. $\mathbb{Z}$ es numerable ( $0, 1, -1, 2, -2, \dots$ ). Y $\mathbb{Q}$ también: acomodás las fracciones $p/q$ en una grilla y las recorrés en zig-zag por diagonales, salteando las repetidas. Cada racional aparece en algún momento. Es decir:

\mathbb{N}, \;\mathbb{Z}, \;\mathbb{Q} \quad \text{son todos numerables.}

Uno esperaría que $\mathbb{R}$ también. La intuición falla.

El teorema

Teorema (Cantor, 1891). El intervalo $[0,1]$ no es numerable. Por lo tanto $\mathbb{R}$ tampoco.

Alcanza con $[0,1]$ : si ni siquiera ese pedacito entra en una lista, $\mathbb{R}$ completo menos todavía.

La demostración

Es por contradicción. Supongamos que $[0,1]$ sí fuera numerable. Entonces podríamos listar todos sus elementos, cada uno por su expansión decimal:

\begin{aligned} x_1 &= 0.\,d_{11}\,d_{12}\,d_{13}\,\dots \\ x_2 &= 0.\,d_{21}\,d_{22}\,d_{23}\,\dots \\ x_3 &= 0.\,d_{31}\,d_{32}\,d_{33}\,\dots \\ &\;\;\vdots \end{aligned}

Ahora fabricamos un número $d = 0.\,e_1 e_2 e_3 \dots$ mirando solo la diagonal: para cada $n$ elegimos $e_n$ distinto de $d_{nn}$ . Probalo — cada vez que regenerás la lista, $d$ se las arregla para no estar en ella:

La diagonal de Cantor — interactivo

Supongamos que toda la lista de reales de [0,1] cupiera acá:

x10.31415926

x20.27182818

x30.14142135

x40.57721566

x50.60221409

x60.89384627

x70.94592307

x80.41693993

d0.55555555

Construimos d recorriendo la diagonal y cambiando cada dígito (regla: si es 5 ponemos 6, si no ponemos 5). Por construcción, d difiere de x₁ en el dígito 1, de x₂ en el dígito 2, de xₙ en el dígito n — de cada número de la lista en al menos un lugar. Entonces d no está en la lista… pero d ∈ [0,1]. La lista nunca pudo ser completa. [0,1] no es numerable.Probá “Regenerar”: pase lo que pase en la lista, d siempre se escapa.

¿Por qué funciona? Por construcción, $e_n \neq d_{nn}$ para todo $n$ . Entonces:

d \neq x_1 \;(\text{difieren en el dígito 1}),\quad d \neq x_2 \;(\text{en el 2}),\quad \dots,\quad d \neq x_n \;(\text{en el } n),\;\dots

$d$ difiere de todos los números de la lista en al menos una posición. Pero $d$ es un número de $[0,1]$ perfectamente legítimo. Conclusión: $d$ no estaba en la lista, aunque la lista supuestamente los tenía a todos. Contradicción. La lista nunca pudo existir. $\;\blacksquare$

Un detalle fino: para evitar la ambigüedad $0.4999\ldots = 0.5$ , elegimos los dígitos $e_n$ sin usar nunca $0$ ni $9$ (en el interactivo, la regla manda a $5$ o $6$ ). Así la expansión de $d$ es única y la comparación dígito a dígito es legítima.

La consecuencia

Hay (al menos) dos tamaños de infinito:

|\mathbb{N}| \;<\; |\mathbb{R}|.

Y acá viene el golpe. $\mathbb{Q}$ es numerable; $\mathbb{R}$ no. Si los irracionales $\mathbb{R} \setminus \mathbb{Q}$ también fueran numerables, entonces $\mathbb{R} = \mathbb{Q} \cup (\mathbb{R}\setminus\mathbb{Q})$ sería unión de dos numerables — y por lo tanto numerable. Absurdo. Luego:

\mathbb{R} \setminus \mathbb{Q} \;\text{ no es numerable.}

Los irracionales no son un puñado de rarezas como $\sqrt{2}$ , $e$ o $\pi$ : son la mayoría aplastante de la recta. Los racionales, con todo lo densos que son (están entre dos reales cualesquiera), forman apenas un polvo numerable sobre un continuo que no lo es. Los huecos que tapamos para construir $\mathbb{R}$ eran, de hecho, casi todo.

El argumento de la diagonal no termina acá: es la misma maquinaria detrás del teorema de Cantor ( $|P(A)| > |A|$ ), de la incompletitud de Gödel y del problema de la parada de Turing. Aprendiste un truco que reaparece en toda la matemática del siglo XX.