8.3: Teorema de Cantor
- Page ID
- 114104
Mucha gente cree que el resultado conocido como teorema de Cantor dice que los números reales,\(\mathbb{R}\), tienen una cardinalidad mayor que los números naturales,\(\mathbb{N}\). Eso no está del todo bien. De hecho, el teorema de Cantor es una afirmación mucho más amplia, una de cuyas consecuencias es esa\(|\mathbb{R}| > |\mathbb{N}|\). Antes de continuar discutiendo el teorema de Cantor en plena generalidad, primero lo exploraremos, esencialmente, en esta forma simplificada. Una vez que lo sepamos\(|\mathbb{R}| \neq |\mathbb{N}|\), estaremos en condiciones de explorar muchos temas interesantes relativos al infinito. En particular, este resultado significa que hay al menos dos números cardinales que son infinitos — así la idea de “infinito es infinito” será desacreditada. Una vez que tengamos todo el poder del teorema de Cantor, veremos cuán completamente equivocado es ese concepto.
Para demostrar que algunos pares de conjuntos no son equivalentes es necesario demostrar que no puede haber una correspondencia uno a uno entre ellos. Ordinariamente, se trataría de argumentar por contradicción en tal situación. Eso es lo que tendremos que hacer para demostrar que los reales y los naturales no son equinúmeros. Supondremos que de hecho son del mismo tamaño y trataremos de llegar a una contradicción.
¿Qué significa exactamente la suposición de que\(\mathbb{R}\) y\(\mathbb{N}\) son equivalentes? Significa que hay una correspondencia uno a uno, es decir, una función biyectiva de\(\mathbb{R}\) a\(\mathbb{N}\). En pocas palabras, significa que es posible enumerar todos los números reales en una lista singly-infinite. Ahora, sin duda es posible hacer una lista infinita de números reales (ya que\(\mathbb{N} ⊆ \mathbb{R}\), al enumerar los propios naturales estamos haciendo una lista infinita de reales!). El problema es que tendríamos que estar seguros de que cada número real está en alguna parte de la lista. De hecho, como hemos usado un argumento geométrico para mostrar que el intervalo\((0, 1)\) y el conjunto\(\mathbb{R}\) son equinumeros, bastará con presumir que hay una lista infinita que contiene todos los números del intervalo\((0, 1)\).
Observe que, por ejemplo,\(π − 3\) es un número real en\((0, 1)\). Hacer una lista de números\(10\) reales en el intervalo\((0, 1)\). Asegurarse de que al menos\(5\) de ellos no sean racionales.
En el ejercicio anterior, ya has iniciado el trabajo, pero tenemos que presumir que es realmente posible completar este trabajo. Es decir, debemos presumir que realmente hay una lista infinita que contiene cada número real en el intervalo\((0, 1)\).
Una vez que tenemos una lista infinita que contiene cada número real en el intervalo\((0, 1)\) tenemos que enfrentar a un segundo problema. ¿Qué significa realmente enumerar un número real en particular? Por ejemplo, si\(e − 2\) está en la séptima posición de nuestra lista, ¿está bien escribir “\(e− 2\)” ahí o deberíamos escribir “\(0.7182818284590452354. . .\)”? Claramente, sería más sencillo escribir “\(e − 2\)” pero no necesariamente es posible hacer algo de ese tipo por cada número real —por otro lado, anotar la expansión decimal también es un problema; en cierto sentido, “la mayoría” de los números reales\((0, 1)\) tienen expansiones decimales infinitamente largas. También hay otro problema con las expansiones decimales; no son únicas. Por ejemplo, realmente no hay diferencia entre la expansión finita\(0.5\) y la expansión infinitamente larga\(0.4\overline{9}\).
En lugar de escribir algo como “\(e−2\)\(0.7182818284590452354. . .\)” o “”, de hecho vamos a escribir “\(.1011011111100001010100010110001010001010 . . .\)” En otras palabras, vamos a escribir las\(2\) expansiones base de los números reales en nuestra lista. Ahora bien, el tema de la no singularidad sigue ahí en binario, y de hecho si tuviéramos que quedarnos en base-\(10\) sería posible tapar una cierta brecha en nuestro argumento- pero la versión binaria de este argumento tiene algunas características especialmente agradables. Cada expansión binaria (o para el caso decimal) corresponde a un número real único, pero no funciona tan bien al revés — a veces hay dos expansiones binarias diferentes que corresponden al mismo número real. Hay un hecho encantador que no vamos a probar (es posible que veas este resultado probado en un curso de Análisis Real) que señala el problema. Siempre que dos expansiones binarias diferentes representan el mismo número real, una de ellas es una expansión terminadora (termina en infinitamente muchas\(0\)) y la otra es una expansión infinita (termina en infinitamente muchas\(1\)). No vamos a probar este hecho, pero la esencia del argumento es una prueba por contradicción —es posible que puedas sacar el punto estudiando Figura\(8.3.1\). (Intenta ver cómo sería posible encontrar un número entre dos expansiones binarias que no terminaran en todos ceros y todo-unos).
Entonces, en lugar de mostrar que el conjunto de reales en no se\((0, 1)\) puede poner en correspondencia uno a uno con\(\mathbb{N}\), lo que realmente vamos a hacer es mostrar que sus expansiones binarias no se pueden poner en correspondencia uno a uno con\(\mathbb{N}\). Dado que hay un número infinito de reales que tienen dos expansiones binarias diferentes esto realmente no hace el trabajo como se anunciaba al principio de esta sección. (Quizás ya te estés acostumbrando a nuestras formas astutas — sí, esto significa que te vamos a pedir que hagas la prueba real en los ejercicios). El conjunto de números binarios\(\{0, 1\}\),, es una instancia de una estructura matemática conocida como campo; básicamente, eso significa que es posible sumar, restar, multiplicar y dividir (pero no dividir por\(0\)) con ellos. Sólo estamos mencionando este hecho por lo
que entenderás por qué el conjunto a menudo\(\{0, 1\}\) se conoce como\(F_2\). Solo estamos mencionando ese hecho para que entiendas por qué llamamos al conjunto de toda la expansión binaria posible\(\mathbb{F}^∞_2\). Por último, sólo estamos mencionando ese hecho para que tengamos una forma sucinta de expresar este conjunto. Ahora podemos escribir “\(\mathbb{F}^∞_2\)" en lugar de “el conjunto de todas las secuencias binarias infinitamente largas posibles”.
Supongamos que teníamos una lista de todos los elementos de\(\mathbb{F}^∞_2\). Tendríamos una lista infinita de cosas, cada una de las cuales es en sí misma una lista infinita de\(0\)'s y\(1\)'s.
Entonces, ¿qué? Tenemos que proceder de aquí para encontrar una contradicción.
Este argumento al que nos hemos acercado se conoce como el argumento de diagonalización de Cantor. La razón de este nombre es que nuestro listado de representaciones binarias parece una enorme tabla de dígitos binarios y la contradicción se deduce mirando la diagonal de esta tabla infinito por infinito. La diagonal es en sí misma una cadena binaria infinitamente larga; en otras palabras, la diagonal puede considerarse como una expansión binaria en sí misma. Si tomamos el complemento de la diagonal, (cambiar cada\(0\) a a\(1\) y viceversa) también tendremos algo que puede considerarse como una expansión binaria y esta expansión binaria ¡no puede ser una de las de la lista! Esta versión bit-flipped de la diagonal es diferente de la primera expansión binaria en la primera posición, es diferente de la segunda expansión binaria en la segunda posición, es diferente de la tercera expansión binaria en la tercera posición, y así sucesivamente. ¡La presunción misma de que podríamos enumerar todos los elementos de nos\(\mathbb{F}^∞_2\) permite construir un elemento de\(\mathbb{F}^∞_2\) eso no podría estar en la lista!
Este argumento se ha generalizado muchas veces, por lo que este es el primero de una clase de cosas conocidas como argumentos diagonales. Los argumentos diagonales se han utilizado para resolver varias cuestiones matemáticas importantes. Hay un argumento diagonal válido que incluso hace lo que originalmente nos habíamos propuesto hacer: probarlo\(\mathbb{N}\) y no\(\mathbb{R}\) son equinúmeros. Extrañamente, no se puede hacer que el argumento funcione en binario, y como se te va a pedir que lo escribas en los ejercicios, queremos señalar una de las posibles trampas. Si tuviéramos que usar un argumento diagonal para mostrar que\((0, 1)\) no es contable, comenzaríamos asumiendo que cada elemento de\((0, 1)\) fue escrito en una lista. Para la mayoría de los números reales en\((0, 1)\) podríamos escribir su representación binaria de manera única, pero para algunos tendríamos que hacer una elección: ¿deberíamos escribir la representación que termina, o la que termina en infinitamente muchos\(1\)? Supongamos que elegimos usar las representaciones terminadoras, entonces ninguna de las cadenas binarias infinitas que terminan con\(1\) todos. estará en la lista. Es posible que lo que obtenemos cuando complementamos la diagonal sea una de estas cadenas binarias (no listadas) por lo que no necesariamente tenemos una contradicción. Si hacemos la otra elección —usar la representación binaria infinita cuando tenemos una opción— hay un problema similar. Se puede pensar que nuestro uso de representaciones binarias para números reales fue una tontería a la luz del fracaso del argumento para “pasar” en binario. Sobre todo porque, como hemos aludido, se puede hacer que funcione en decimal. La razón de nuestra aparente terquedad es que estas cadenas binarias infinitas hacen otra cosa que es muy agradable. Una secuencia binaria infinitamente larga puede considerarse como la función indicadora de un subconjunto de\(\text{N}\). Por ejemplo,\(.001101010001\) es el indicador de\(\{2, 3, 5, 7, 11\}\).
Completa la tabla.
| expansión binaria | subconjunto de\(\mathbb{N}\) |
| \(.1\) | \(\{0\}\) |
| \(.0111\) | |
| \(\{2, 4, 6\}\) | |
| \(.\overline{01}\) | |
| \(\{3k + 1 | k ∈ \mathbb{N}\}\) |
El conjunto,\(\mathbb{F}^∞_2\), con el que hemos estado trabajando está en correspondencia uno a uno con el conjunto de poder de los números naturales,\(\mathcal{P}(N)\). Cuando se ve bajo esta luz, la prueba que hicimos anteriormente mostró que el conjunto de poder de\(\mathbb{N}\) tiene una cardinalidad infinita estrictamente mayor que la de\(\mathbb{N}\) sí mismo. En otras palabras,\(\mathcal{P}(N)\) es incontable.
Lo que dice el teorema de Cantor es que esto siempre funciona. Si\(A\) es algún conjunto, y\(\mathcal{P}(A)\) es su potencia establecida entonces\(|A| < |\mathcal{P}(A)|\). En cierto modo, este teorema más general es más fácil de probar que el caso específico que acabamos de manejar.
Para todos los conjuntos\(A\), no\(A\) es equivalente a\(\mathcal{P}(A)\).
- Prueba
-
Supongamos que hay un conjunto\(A\) que se puede colocar en correspondencia uno-toone con su conjunto de potencia. Después hay una función biyectiva\(f : A \implies \mathcal{P}(A)\). Deduciremos una contradicción construyendo un subconjunto de\(A\) (es decir, un miembro de\(\mathcal{P}(A)\)) que no puede estar en el rango de\(f\).
Vamos\(S = \{x ∈ A | x \notin f(x)\}\).
Si\(S is in the range of \(f\), hay una preimagen\(y\) tal que\(S = f(y)\). Pero, si tal\(y\) existe entonces la cuestión de membresía\(y ∈ S\),, debe ser verdadera o falsa. Si\(y ∈ S\), entonces porque\(S = f(y)\), y\(S\) consiste en aquellos elementos que no están en sus imágenes, se deduce de eso\(y \notin S\). Por otra parte, si\(y \notin S\) entonces es\(y \notin f(y)\) así (por la definición de\(S\)) se deduce que\(y ∈ S\). Cualquiera de las dos posibilidades lleva a la otra, lo cual es una contradicción.
Q.E.D.
El teorema de Cantor garantiza que existe una jerarquía infinita de infinitos números cardinales. Digámoslo de otra manera. La gente ha buscado una construcción que, dado un conjunto infinito, pudiera ser utilizada para crear un conjunto estrictamente más grande. Por ejemplo, el producto cartesiano funciona así si nuestros conjuntos son finitos,\(A × A\) es estrictamente más grande que\(A\) cuando\(A\) es un conjunto finito. Pero, como ya hemos visto, esto no es necesariamente así si\(A\) es infinito (recuerda el argumento de la “serpiente” que\(\mathbb{N}\) y\(\mathbb{N}×\mathbb{N}\) son equivalentes). La verdadera importancia del teorema de Cantor es que tomar el conjunto de poder de un conjunto sí crea un conjunto de cardinalidad más grande. Entonces obtenemos una torre infinita de infinitas cardinalidades, empezando por\(ℵ_0 = |\mathbb{N}|\), tomando sucesivamente conjuntos de poder.
\[ℵ_0 = |\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < |\mathcal{P}(\mathcal{P}(\mathcal{P}(\mathbb{N})))| < . . .\]
Ejercicios:
Determinar una regla de sustitución — una forma consistente de reemplazar un dígito por otro a lo largo de la diagonal para que una prueba de diagonalización que muestre que el intervalo\((0, 1)\) es incontable funcione en decimal. Redactar el comprobante.
¿Se puede hacer viable una prueba de diagonalización que muestre que el intervalo\((0, 1)\) es incontable en notación base\(3\) (ternaria)?
En la prueba del teorema de Cantor construimos un conjunto\(S\) que no puede estar en la imagen de una presunta biyección de\(A\) a\(\mathcal{P}(A)\). Supongamos\(A = \{1, 2, 3\}\) y\(f\) determina las siguientes correspondencias:\(1 \iff ∅\),\(2 \iff \{1, 3\}\) y\(3 \iff \{1, 2, 3\}\). ¿Qué es\(S\)?
Un argumento muy similar al encarnado en la prueba del teorema de Cantor se encuentra en la paradoja del Barber. Esta paradoja se introdujo originalmente en la prensa popular con el fin de dar a los laicos una comprensión del teorema de Cantor y de la paradoja de Russell. Suena algo sexista a los oídos modernos. (Por ejemplo, se presume sin comentarios que el Barbero es varón.) En un pueblo pequeño, hay un barbero que afeita a esos hombres (y sólo a esos hombres) que no se afeitan a sí mismos. ¿Quién afeita al barbero? Explicar la similitud con la prueba del teorema de Cantor.
El teorema de Cantor, aplicado al conjunto de todos los conjuntos conduce a una interesante paradoja. El conjunto de potencia del conjunto de todos los conjuntos es una colección de conjuntos, por lo que debe estar contenido en el conjunto de todos los conjuntos. Discutir la paradoja y determinar una forma de resolverla
Verificar que la deducción final en la prueba del teorema de Cantor, “\((y ∈ S \implies y \notin S) ∧ (y \notin S \implies y ∈ S)\),” es verdaderamente una contradicción.