Cardinales · Definición

Teorema diagonal de Cantor

teoría de conjuntoscardinales

Antes de empezar necesitas conocer

Este teorema muestra que hay conjuntos infinitos que no pueden listarse, y es la base de la prueba de que \(\mathbb{R}\) no es numerable.

Definición

Teorema que prueba que el conjunto \(\{0,1\}^{\mathbb{N}}\) de sucesiones de ceros y unos no es numerable, construyendo una sucesión que no está en ninguna lista.

\[t(n)=1-s_n(n)\]

Sea \(s_1,s_2,s_3,\dots\) una lista cualquiera de sucesiones binarias, y sea \(s_n(n)\) el \(n\)-ésimo término de \(s_n\). Se define \(t(n)=1-s_n(n)\), es decir, el término diagonal cambiado de 0 a 1 o de 1 a 0. Como \(t(n)\neq s_n(n)\), la sucesión \(t\) difiere de \(s_n\) en la posición \(n\), así que no aparece en la lista.

Por tanto ninguna lista agota \(\{0,1\}^{\mathbb{N}}\), y no existe una función sobreyectiva de \(\mathbb{N}\) en \(\{0,1\}^{\mathbb{N}}\): el conjunto no es numerable. El mismo argumento, con expansiones binarias o decimales, muestra que \(\mathbb{R}\) tampoco lo es.

Ejemplo: con \(s_1=000\ldots\), \(s_2=111\ldots\) y \(s_3=0101\ldots\), la diagonal da \(t(1)=1\), \(t(2)=0\) y \(t(3)=1\), así que \(t\) empieza por \(101\ldots\). Error típico: pensar que la prueba depende de la lista concreta; sirve para cualquier lista, porque la construcción de \(t\) siempre funciona.

Para pensar

Para pensar: ¿por qué la construcción de \(t\) funciona con cualquier lista?

Porque \(t\) difiere de cada \(s_n\) en la posición \(n\), así que nunca coincide con ninguna.

Ejercicios 10

  1. ¿Qué afirma el teorema diagonal de Cantor?
  2. ¿Qué sucesión construye la demostración diagonal para escapar de una lista?
  3. ¿Es \(\mathbb{N}\) numerable?
  4. ¿Cuál de estos conjuntos es no numerable?
  5. Con \(s_1=000\ldots\), \(s_2=111\ldots\) y \(s_3=0101\ldots\), ¿cuáles son los tres primeros términos de la sucesión diagonal \(t\), con \(t(n)=1-s_n(n)\)?
  6. ¿Por qué la sucesión diagonal \(t\) no puede aparecer en una lista \(s_1,s_2,\dots\)?
  7. ¿Qué se concluye del argumento diagonal para \(\mathbb{R}\)?
  8. ¿Cuál de estas afirmaciones es verdadera?
  9. Sea \(A\) el conjunto de sucesiones binarias con finitos unos. ¿Es \(A\) numerable?
  10. Sea \(f\colon\mathbb{N}\to\{0,1\}^{\mathbb{N}}\) cualquier función. ¿Cuál de estas sucesiones no está en la imagen de \(f\) para toda \(f\)?

Referencias

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.