9.5: Conjuntos incontables

Recordemos de la Definición 9.37 que un conjunto\(A\) es incontable si no\(A\) es contable. Como todos los conjuntos finitos son contables, la única forma en que un conjunto podría ser incontable es si es infinito. De ello se deduce que un conjunto\(A\) es incontable si y sólo si nunca hay una biyección entre\(\mathbb{N}\) y\(A\). ¡No está claro que incluso existan conjuntos incontables! Resulta que existen conjuntos incontables y en esta sección, descubriremos algunos de ellos.

Nuestra primera tarea es demostrar que el intervalo\((0,1)\) es incontable. Por Problema 9.35 (8), sabemos que\((0,1)\) es un conjunto infinito, por lo que es al menos plausible que\((0,1)\) sea incontable. El siguiente problema esboza la prueba del Teorema 9.52. Nuestro enfoque a menudo se conoce como el argumento de diagonalización de Cantor, llamado así por el matemático alemán Georg Cantor (1845—1918).

Antes de comenzar, recordemos que cada número en se\((0,1)\) puede escribir en forma decimal. Sin embargo, puede haber más de una manera de escribir un número dado en forma decimal. Por ejemplo,\(0.2\) es igual\(0.1\overline{99}\). Se dice que un número\(0.a_1a_2a_3\ldots\) en\((0,1)\) está en forma decimal estándar si no hay\(k\) tal que para todos\(i>k\),\(a_i=9\). Es decir, un número está en forma decimal estándar si y sólo si su expansión decimal no termina con una secuencia repetitiva de 9's. Por ejemplo,\(0.2\) está en forma decimal estándar mientras que no lo\(0.1\overline{99}\) es, aunque ambos representan el mismo número. Resulta que cada número real se puede expresar de manera única en forma decimal estándar. Daremos por sentado este hecho.

Problema 9.51. En aras de una contradicción, supongamos que el intervalo\((0,1)\) es contable. Entonces existe una biyección\(f:\mathbb{N}\to (0,1)\). Para cada uno\(n\in\mathbb{N}\), su imagen debajo\(f\) es algún número en\((0,1)\). Escribe\(f(n)=0.a_{1n}a_{2n}a_{3n}\ldots\), donde\(a_{1n}\) está el primer dígito en la forma decimal estándar para la imagen de\(n\),\(a_{2n}\) es el segundo dígito, y así sucesivamente. Si\(f(n)\) termina después de\(k\) dígitos, entonces nuestra convención será continuar la expansión decimal con 0's. Ahora, defina\(b=0.b_1b_2b_3\ldots\), dónde\[b_i=\begin{cases} 2, & \text{if }a_{ii}\neq 2\\ 3, & \text{if }a_{ii}=2. \end{cases}\]

1. Demostrar que la expansión decimal que define\(b\) arriba está en forma decimal estándar.
2. Demuéstralo para todos\(n\in\mathbb{N}\),\(f(n)\neq b\).
3. Explique por qué\(f\) no puede ser surytivo y por qué esto es una contradicción.

¡Acabas de demostrar que el intervalo\((0,1)\) no puede ser contable!

El problema anterior prueba el siguiente teorema.

Teorema 9.52. El intervalo abierto\((0,1)\) es incontable.

Hablando vagamente, lo que dice el Teorema 9.52 es que el intervalo abierto\((0,1)\) es “mayor” en términos del número de elementos que contiene que los números naturales e incluso los números racionales. ¡Esto demuestra que hay infinitos conjuntos de diferentes tamaños! Ahora sabemos que hay al menos un conjunto incontable, es decir, el intervalo\((0,1)\). Los siguientes tres resultados son útiles para encontrar otros conjuntos incontables. Para el primer teorema, pruebe una prueba por contradicción y eche un vistazo al Teorema 9.41.

Teorema 9.53. Si\(A\) y\(B\) son conjuntos tales que\(A\subseteq B\) y\(A\) es incontable, entonces\(B\) es incontable.

Corolario 9.54. Si\(A\) y\(B\) son conjuntos tales que\(A\) es incontable y\(B\) es contable, entonces\(A\setminus B\) es incontable.

Teorema 9.55. Si\(f:A\to B\) es una función inyectora y\(A\) es incontable, entonces\(B\) es incontable.

Dado que el intervalo\((0,1)\) es incontable y\((0,1)\subseteq \mathbb{R}\), se desprende inmediatamente del Teorema 9.53 que también\(\mathbb{R}\) es incontable. El siguiente teorema dice eso\((0,1)\) y\(\mathbb{R}\) en realidad tienen la misma cardinalidad! Para probarlo, considere la función\(f:(0,1)\to \mathbb{R}\) definida vía\(f(x)=\tan(\pi x-\frac{\pi}{2})\).

Teorema 9.56. El conjunto de números reales es incontable. En particular,\(card((0,1))=card(\mathbb{R})\).

La hipótesis del continuum —originalmente propuesta por Cantor en 1878— establece que no existe un conjunto cuya cardinalidad esté estrictamente entre la de los números naturales y los números reales. Cantor intentó sin éxito probar la hipótesis del continuo durante varios años. De la obra de Paul Cohen (1934—2007) y Kurt Gödel (1906—1978) se deduce que la hipótesis del continuum y su negación son independientes de los axiomas Zermelo-Fraenkel de la teoría de conjuntos (brevemente discutidos al final de la Sección 3.2). Es decir, ya sea la hipótesis del continuum o su negación pueden agregarse como axioma a la teoría de conjuntos de ZFC, siendo la teoría resultante consistente si y solo si ZFC es consistente (es decir, no se producen contradicciones). Hoy en día, la mayoría de los teóricos establecidos creen que la hipótesis del continuo debe ser falsa.

Teorema 9.57. Si\(a,b\in\mathbb{R}\) con\(a<b\), entonces\((a,b)\),\([a,b]\)\((a,b]\),, y\([a,b)\) son todos incontables.

Teorema 9.58. El conjunto de números irracionales es incontable.

Teorema 9.59. El conjunto\(\mathbb{C}\) de números complejos es incontable.

Problema 9.60. Determinar si cada una de las siguientes afirmaciones es verdadera o falsa. Si una afirmación es cierta, demuéstrala. De lo contrario, proporcione un contraejemplo.

1. Si\(A\) y\(B\) son conjuntos tales que\(A\) es incontable, entonces\(A\cup B\) es incontable.
2. Si\(A\) y\(B\) son conjuntos tales que\(A\) es incontable, entonces\(A\cap B\) es incontable.
3. Si\(A\) y\(B\) son conjuntos tales que\(A\) es incontable, entonces\(A\times B\) es incontable.
4. Si\(A\) y\(B\) son conjuntos tales que\(A\) es incontable, entonces\(A\setminus B\) es incontable.

Un enfoque similar al Argumento de diagonalización de Cantor será útil a la hora de abordar el siguiente problema.

Problema 9.61. \(S\)Sea el conjunto de secuencias infinitas de 0's y 1's Determina si\(S\) es contable o incontable y prueba que tu respuesta es correcta.

Teorema 9.62. Si\(S\) es el conjunto de Problema 9.61, entonces\(card(\mathcal{P}(\mathbb{N}))=card(S)\).

Corolario 9.63. El conjunto de potencias de los números naturales es incontable.

Observe que\(\mathbb{N}\) es contable mientras que\(\mathcal{P}(\mathbb{N})\) es incontable. Es decir, el conjunto de poder de los números naturales tiene cardinalidad estrictamente mayor que los números naturales. Generalizamos este fenómeno en el siguiente teorema.

Según el Teorema 9.56 y el Corolario 9.63,\(\mathbb{R}\) y ambos\(\mathcal{P}(\mathbb{N})\) son incontables. De hecho,\(card(\mathcal{P}(\mathbb{N}))=card(\mathbb{R})\), que declaramos sin pruebas. No obstante, resulta que los dos conjuntos incontables pueden o no tener la misma cardinalidad. Quizás sorprendentemente, hay conjuntos que son incluso “más grandes” que el conjunto de números reales. El siguiente teorema lleva el nombre de Georg Cantor, quien primero lo declaró y demostró a finales del siglo XIX. El teorema afirma que dado cualquier conjunto, siempre podemos incrementar la cardinalidad considerando su conjunto de poder. Es decir, si\(A\) es un conjunto,\(\mathcal{P}(A)\) tiene una cardinalidad estrictamente mayor que\(A\) él mismo. Para conjuntos finitos, el teorema de Cantor se desprende de los teoremas 4.11 y 4.12 (ambos de los cuales probamos por inducción). Quizás mucho más sorprendente es que Cantor descubrió un argumento elegante que es aplicable a cualquier conjunto, ya sea finito o infinito. Para probar el teorema de Cantor, primero exhibir una función inyectiva de\(A\) a\(\mathcal{P}(A)\). Esto lo demuestra\(card(A)\leq \space card(\mathcal{P}(A))\). Para demostrarlo\(card(A)< card(\mathcal{P}(A))\), intente una prueba por contradicción. Es decir, supongamos que existe una función biyectiva\(f:A\to\mathcal{P}(A))\). Derivar una contradicción considerando el conjunto\(B=\{x\in A\mid x\notin f(x)\}\).

Teorema 9.64. Si\(A\) es un conjunto, entonces\(card(A)<card(\mathcal{P}(A))\).

Recordemos que la cardinalidad proporciona una manera de hablar de “lo grande” que es un conjunto. El hecho de que los números naturales y los números reales tengan diferente cardinalidad (uno contable, el otro incontable), nos dice que hay al menos dos “tamaños de infinito” diferentes. Al tomar iterativamente el conjunto de poder de un conjunto infinito y aplicar el Teorema de Cantor obtenemos una jerarquía interminable de cardinalidades, cada una estrictamente mayor que la anterior. Coloquialmente, esto implica que hay “infinitamente muchos tamaños de infinito” y no hay “el infinito más grande”.