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.

Funciones y biyecciones: qué significa "el mismo tamaño"

Antes de comparar infinitos hay que precisar "mismo tamaño". Una función $f : A \to B$ asigna a cada $a \in A$ un único $f(a)$ ; su imagen es $f(A) = \{f(a) : a \in A\}$ . Decimos que $f$ es:

inyectiva si elementos distintos van a imágenes distintas ( $f(a_1) = f(a_2) \Rightarrow a_1 = a_2$ ): no colapsa puntos;
sobreyectiva si $f(A) = B$ : alcanza todo $B$ ;
biyectiva si es ambas —un emparejamiento perfecto, sin que sobre ni falte nada.

Dos conjuntos tienen el mismo cardinal, $A \sim B$ , si existe una biyección entre ellos. Se exige biyección, y no solo inyección, para que "mismo tamaño" sea simétrico y transitivo: hay que poder ir y volver.

Lo contraintuitivo del infinito: un conjunto infinito puede tener el mismo tamaño que una parte propia de sí mismo. $\mathbb{N} \sim 2\mathbb{N}$ vía $n \mapsto 2n$ , aunque los pares parezcan "la mitad". Eso es, de hecho, la definición de infinito (Dedekind) —imposible para los finitos.

Contar lo infinito

Un conjunto es numerable si tiene el mismo cardinal que $\mathbb{N}$ : se puede poner en una lista $x_1, x_2, x_3, \dots$ sin que falte ninguno. 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: poné cada fracción $p/q$ en una grilla (fila $p$ , columna $q$ ) y recorrela por antidiagonales —los grupos con $p + q = 2, 3, 4, \dots$ , cada uno finito—, salteando las fracciones no reducidas ya vistas. Como cada antidiagonal se agota en finitos pasos, todo racional aparece tarde o temprano. Es decir:

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

Densidad $\neq$ cardinalidad. Que entre dos racionales haya infinitos más no hace a $\mathbb{Q}$ más grande que $\mathbb{N}$ : es denso y numerable. Cuán apretado está un conjunto y cuántos puntos tiene son preguntas independientes.

Uno esperaría que $\mathbb{R}$ también entre en una lista. 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.

Esto anticipa la integral de Lebesgue: por ser numerable, $\mathbb{Q}$ tendrá medida cero —cero longitud total—, y toda la "masa" de la recta vivirá en los irracionales. Que un conjunto infinito pueda medir cero es la primera señal de que cuántos puntos hay y cuánto miden son cosas distintas.

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.