El argumento diagonal de Cantor es un método matemático inventado por Georg Cantor que se usa para comparar cardinalidades de conjuntos, y en particular para demostrar que no todos los infinitos tienen la misma tamaño. Cantor publicó trabajos relevantes en 1877, 1891 y 1899; su formulación clásica del argumento diagonal apareció en 1890 en la revista de la Sociedad Matemática Alemana (Deutsche Mathematiker-Vereinigung). Según Cantor, dos conjuntos tienen la misma cardinalidad si es posible asociar un elemento del segundo conjunto a cada elemento del primer conjunto, y asociar un elemento del primer conjunto a cada elemento del segundo conjunto (es decir, existe una biyección entre ellos). Esta definición funciona bien para conjuntos con un número finito de elementos y también para algunos infinitos; sin embargo, el argumento diagonal muestra que hay infinitos de diferentes tamaños y que esa intuición debe afinarse.

Idea básica

El argumento diagonal es una construcción que, a partir de una lista supuesta que contiene todos los elementos de cierto conjunto, produce un elemento que no está en la lista. Esa contradicción prueba que la lista completa no existe, es decir, que el conjunto no es numerable (no tiene la misma cardinalidad que el conjunto de los números naturales).

Cardinalidades habituales y ejemplos

  • Numerable (o contable): un conjunto es numerable si se puede poner en correspondencia uno a uno con los naturales. El conjunto de los números naturales, enteros y racionales es numerable. A la cardinalidad de un conjunto numerable infinito se le suele llamar aleph-cero (ℵ0).
  • No numerable (o incontable): el ejemplo clásico es el conjunto de los números reales. Su cardinalidad es mayor que la de los naturales y se denomina continuo (c).

Ejemplo: los racionales son numerables

Aunque parezca que hay “muchísimos” racionales, se puede enumerar todos los números racionales positivos p/q recorriendo la tabla de pares (p,q) en forma diagonal (por ejemplo, por sumas p+q crecientes) y evitando repeticiones. Con un pequeño truco también se incluye 0 y los racionales negativos. Por eso los racionales son numerables: existe una biyección con los naturales.

Demostración de la no numerabilidad de los reales — argumento diagonal clásico

Una versión habitual del argumento muestra que no existe una lista que contenga todos los números reales del intervalo (0,1). Supongamos, para obtener una contradicción, que sí existe una lista que agrupa todos esos números:
r1 = 0.d11 d12 d13 d14 ...
r2 = 0.d21 d22 d23 d24 ...
r3 = 0.d31 d32 d33 d34 ...
donde dij es la j-ésima cifra decimal del número ri.

Construimos ahora un nuevo número r = 0.c1 c2 c3 c4 ... de la siguiente manera: para cada n, elegimos cn distinto de dnn (la cifra en la diagonal). Por ejemplo, si dnn ≠ 1 elegimos cn = 1; si dnn = 1 elegimos cn = 2. De este modo r difiere de r1 en la primera cifra, de r2 en la segunda cifra, de r3 en la tercera, y así sucesivamente. Por tanto r no puede aparecer en la lista, contradicción. Concluimos que no existe una lista que contenga todos los reales del intervalo (0,1); el conjunto de los reales es, por tanto, no numerable.

Nota sobre representaciones decimales: hay números con dos representaciones decimales (por ejemplo 0.24999... = 0.25). Para evitar este problema se puede forzar la construcción a evitar construir un número que termine en repetición de 9, eligiendo por ejemplo cn = 1 si dnn ≠ 1, y cn = 2 si dnn = 1. Así nunca obtenemos la representación con infinitos 9 y la construcción es válida.

Argumento diagonal en la forma de conjuntos (teorema de Cantor)

Cantor dio también una forma más general del argumento que prueba que ningún conjunto A puede estar en correspondencia biunívoca con su conjunto de partes P(A) (el conjunto de todos los subconjuntos de A). La demostración es la siguiente:

  1. Supongamos que existe una función f: A → P(A) que es sobreyectiva (cada subconjunto de A es f(a) para algún a).
  2. Consideremos el subconjunto D = {x ∈ A : x ∉ f(x)}. Es decir, D contiene exactamente los elementos de A que no pertenecen a su propia imagen bajo f.
  3. Si existiera a0 ∈ A tal que f(a0) = D, entonces preguntaríamos si a0 ∈ D. Si a0 ∈ D entonces por definición de D debe cumplirse a0 ∉ f(a0) = D, contradicción. Si a0 ∉ D entonces por definición debe cumplirse a0 ∈ f(a0) = D, otra contradicción.
  4. Por tanto no existe a0 con f(a0) = D y la función f no puede ser sobreyectiva. En consecuencia |P(A)| > |A|: el conjunto de partes de A tiene cardinal estrictamente mayor que A.

Consecuencias e implicaciones

  • Existe una jerarquía de infinitos: A, P(A), P(P(A)), ... producen tamaños cada vez mayores. El argumento diagonal es la herramienta esencial para demostrar esto.
  • La cardinalidad de los naturales (y de los enteros y racionales) es ℵ0; la de los reales es c y satisface c = |P(N)| (el conjunto de partes de los naturales tiene la cardinalidad del continuo).
  • La famosa Hipótesis del Continuo pregunta si existe alguna cardinalidad intermedia entre ℵ0 y c. Esta hipótesis es independiente del axioma de Zermelo–Fraenkel con el Axioma de Elección (ZFC): ni puede demostrarse ni refutarse a partir de ZFC.

Resumen

El argumento diagonal de Cantor es una construcción muy simple y poderosa que permite:

  • probar que algunos conjuntos infinitos (como los reales) no son numerables;
  • demostrar que el conjunto de partes de cualquier conjunto tiene cardinal mayor que el conjunto original;
  • establecer la existencia de distintos “tamaños” de infinito y abrir la puerta a una teoría fina de cardinalidades.