9.6: Conjuntos incontables

La sección anterior mostró que muchos conjuntos (incluyendo\(\mathbb{N}\)\(\mathbb{Z}\),, y\(\mathbb{Q}\)) son contables. Ahora veremos que algunos conjuntos no son contables.

9.6A. Los reales son incontables.

Aquí está quizás el ejemplo más importante de un conjunto incontable:

Teorema\(9.6.1\).

El conjunto\(\mathbb{R}\) de números reales es incontable.

Si\(\mathbb{R}\) fueran contables, entonces todos sus subconjuntos serían contables. Así, para establecer el Teorema\(9.6.1\), basta con encontrar un subconjunto incontable de\(\mathbb{R}\). Aquí hay algunos ejemplos bien conocidos de subconjuntos:

Notación\(9.6.2\).

Para\(a, b \in \mathbb{R}\) con\(a < b\):

• intervalo abierto:\((a, b)=\{x \in \mathbb{R} \mid a<x<b\}\).
• intervalo cerrado:\([a, b]=\{x \in \mathbb{R} \mid a \leq x \leq b\}\).
• intervalo medio abierto:\([a, b)=\{x \in \mathbb{R} \mid a \leq x<b\}\) o\((a, b]=\{x \in \mathbb{R} \mid a<x \leq b\}\).

Veremos que todos estos intervalos son incontables. Aquí hay un ejemplo:

Teorema\(9.6.3\).

El intervalo\([0, 1)\) es incontable.

Prueba

POR CONTRADICCIÓN.

Supongamos que\([0, 1)\) es contable. (Esto conducirá a una contradicción.) Esto significa que hay una lista\(x_{1}\),\(x_{2}\),\(x_{3}\),... de todos los números en\([0, 1)\). Para obtener una contradicción, utilizaremos un método llamado Argumento de Diagonalización Cantor. Fue descubierto por el matemático Georg Cantor en el siglo XIX.

Cada número en se\([0, 1)\) puede escribir como decimal de la forma 0. \(d_{1}d_{2}d_{3}\).., donde cada uno\(d_{k}\) es un dígito (0, 1, 2, 3, 4, 5, 6, 7, 8 o 9). En particular, podemos escribir cada uno\(x_{i}\) en este formulario:\[x_{i}=0 . x_{i, 1} x_{i, 2} x_{i, 3} x_{i, 4} x_{i, 5} \ldots\]

Entonces podemos hacer una lista de todos estos decimales (omitiendo el 0 a la izquierda en cada uno):\ [\ begin {alineado}
x_ {1} =&. x_ {1,1} x_ {1,2} x_ {1,3} x_ {1,4} x_ {1,5}\ cdots\\ x_ {2} =&. x_ {2,1}
x_ {2,2} x_ {2,3} x_ {2,3} x_ {2,3} x_ {2,3} x_ {2,3} x_ {2,4} x_ {2,5}\ cdots\\
x_ {3} =&. x_ {3,1} x_ {3,2} x_ {3,3 } x_ {3,4} x_ {3,5}\ cdots\\
x_ {4} =&. x_ {4,1} x_ {4,2} x_ {4,3} x_ {4,4} x_ {4,5}\ cdots\\
x_ {5} =&. x_ {5,1} x_ {5,2} x_ {5,3} x_ {5,4} x_ {5,5}\ puntos\\
\ vdots &\ vdots
\ end {alineado}\]

El lado derecho se puede considerar como una matriz de dígitos, y ahora nos enfocamos en las entradas diagonales\(x_{i,i}\) de esta matriz, que están en un círculo en la siguiente imagen:

Forman una secuencia\(x_{1,1}, x_{2,2}, x_{3,3}, \ldots\).

La clave de la prueba es hacer una nueva secuencia\(d_{1}, d_{2}, d_{3}, \ldots\) de dígitos, de tal manera que\[d_{1} \neq x_{1,1}, \quad d_{2} \neq x_{2,2}, \quad d_{3} \neq x_{3,3}, \text { etc. }\]

Esto significa que cada término de la nueva secuencia es diferente del término correspondiente de la secuencia diagonal. (Esta idea de elegir una secuencia que es completamente diferente a la diagonal se llama diagonalización Cantor, porque fue inventada por el matemático Georg Cantor.) Además, para evitar problemas derivados del hecho de que\(.999 \cdots=1.000 \cdots\), no se deben usar los dígitos 0 y 9. La secuencia se\(\left\{d_{i}\right\}\) puede construir de muchas maneras: solo asegúrate de elegir cada una\(d_{i}\) para que sea un dígito que no sea\(x_{i,i}\) (y no sea 0 o 9). Por ejemplo, podríamos dejar\[d_{i}= \begin{cases}1 & \text { if } x_{i, i} \neq 1 \\ 5 & \text { if } x_{i, i}=1\end{cases}\]

Ahora, vamos\[d=0 . d_{1} d_{2} d_{3} \ldots \in[0,1).\]

Para cada uno\(i\), nos aseguramos de eso\(d_{i} \neq x_{i, i}\), lo que significa que el dígito\(i\) th de d es diferente del dígito\(i\) th de\(x_{i}\). Por lo tanto, para cada uno\(i\), tenemos\(d \neq x_{i} \text { * }\). Entonces\(d\) es un elemento de\([0, 1)\) que no está en la lista\(x_{1}, x_{2}, x_{3}, \ldots\). Esto contradice el hecho de que\(x_{1}, x_{2}, x_{3}, \ldots\) es una lista de todos los números en\([0, 1)\).

Ejercicio\(9.6.4\).

1. Mostrar que el intervalo\((0, 1)\) es incontable. [Pista:\ ([0,1) =( 0,1)\ copa\ {0\}) es incontable.]
2. Supongamos\(a, b \in \mathbb{R}\). Mostrar que si\(a < b\), entonces el intervalo\((a, b)\) tiene la misma cardinalidad que\((0, 1)\). [Pista: Definir\(f:(0,1) \rightarrow(a, b)\) por\(f(x)=a+(b-a) x\).]
3. Supongamos\(a \in \mathbb{R}\). Mostrar que el intervalo\((a, \infty)\) tiene la misma cardinalidad que\((0, 1)\). [Pista: Definir\ (f: (0,1)\ fila derecha (a,\ infty)) por\ (f (x) =( 1/x) +a-1).]

Corolario\(9.6.5\).

Si\(a, b \in \mathbb{R}\) y\(a < b\), entonces los intervalos\((a, b)\)\([a, b]\),\([a, b)\),, y\((a, b]\) son incontables.

Ejercicio\(9.6.6\).

Decidir cuáles de los siguientes conjuntos son contables y cuáles son incontables. (No es necesario que justifique sus respuestas.)

1. El intervalo cerrado\([3,3.1]\)
2. \(\{1,2,3, \ldots, 1000\}\)
3. \(\mathbb{Z} \times \mathbb{Z}\)
4. \(\mathbb{Z} \times \mathbb{Q}\)
5. \(\mathbb{R} \times \mathbb{N}\)
6. \(\mathbb{R} \backslash \mathbb{Q}\)
7. \(\mathbb{Q} \backslash \mathbb{R}\)
8. \((\mathbb{R} \backslash \mathbb{Q}) \cap(\mathbb{Q} \backslash \mathbb{R})\)
9. \((\mathbb{R} \backslash \mathbb{Q}) \cup(\mathbb{Q} \backslash \mathbb{R})\)
10. \((\mathbb{R} \backslash \mathbb{Q}) \times(\mathbb{Q} \backslash \mathbb{R})\)
11. \(\{x \in \mathbb{R} \mid 2<x<3\}\)
12. \(\left\{x \in \mathbb{R} \mid x^{2}=3\right\}\)
13. \(\left\{x \in \mathbb{R} \mid x^{2}+12<3\right\}\)
14. \(\left\{x \in \mathbb{R} \mid x^{2}+3<12\right\}\)
15. \ (\ izquierda\ {x\ in\ mathbb {Q}\ mediados x^ {2} +3<12\ derecha\})
16. \ (\ {(x, y)\ in\ mathbb {R}\ veces\ mathbb {R}\ mediados x-y=1\})
17. \(\{(x, y) \in \mathbb{R} \times \mathbb{R} \mid x-y \in \mathbb{Z}\}\)
18. \(\{(x, y) \in \mathbb{Z} \times \mathbb{R} \mid x-y \in \mathbb{Q}\}\)
19. \ (\ izquierda\ {(x, y)\ in\ mathbb {R} ^ {2}\ mediados x^ {2} +y^ {2} =1\ derecha\})
20. \ (\ izquierda\ {(x, y)\ in\ mathbb {R} ^ {2}\ mediados x^ {2} +y^ {2} =-1\ derecha\})

9.6B. La cardinalidad de los conjuntos de poder.

Si\(A\) es un conjunto finito, entonces el conjunto\(\mathcal{P}(A)\) de todos los subconjuntos de también\(A\) es finito. (En efecto,\(\# \mathcal{P}(A)=2^{\# A}\).) Sin embargo, esta afirmación no permanece cierta cuando la palabra “finito” se sustituye por “contable”:

Ejercicio\(9.6.7\).

Demostrar que\(\mathcal{P}\left(\mathbb{N}^{+}\right)\) es incontable. [Pista: Para cualquiera\(f: \mathbb{N}^{+} \rightarrow \mathcal{P}\left(\mathbb{N}^{+}\right)\), el conjunto no\(\left\{i \in \mathbb{N}^{+} \mid i \notin f(i)\right\}\) está en la imagen de\(f\).]

Por cada conjunto\(A\), no sólo los contables, el mismo argumento muestra que la cardinalidad de\(\mathcal{P}(A)\) es mayor que la cardinalidad de\(A\). Así, no hay un conjunto infinito “más grande”. Por cada conjunto, siempre hay algún conjunto que tenga una cardinalidad mucho mayor.

Ejercicio\(9.6.8\).

Para cada conjunto\(A\), show no existe una función onto\(f: A \rightarrow \mathcal{P}(A)\). [Pista: El conjunto no\(\{a \in A \mid a \notin f(a)\}\) está en la imagen de\(f\).]

Los ejercicios anteriores están muy estrechamente relacionados con una paradoja clásica:

Ejemplo\(9.6.9\) ("Barber Paradox").

Supongamos que hay un pueblo con un solo barbero, y ese barbero es un hombre. Además, supongamos que el barbero afeita precisamente a aquellos hombres del pueblo que no se afeitan a sí mismos. Más precisamente, si\(B\) es el Barbero, y\(M\) es cualquier hombre en el pueblo, entonces\[B \text { shaves } M \quad \text { iff } \quad M \text { does not shave } M\]

Ahora, preguntamos:\[\text { Does the barber shave himself? }\]

Solución

Esta pregunta es una paradoja:

• Si la respuesta es sí, entonces el barbero se afeita. Pero el barbero no afeita a los hombres que se afeitan a sí mismos, por lo que esto significa que el barbero no se afeita a sí mismo. Pero ya dijimos que el barbero sí se afeita, así que esto es una tontería.
• Si la respuesta es no, entonces el barbero no se afeita. Pero el barbero sí afeita a cualquier hombre que no se afeite, así que esto quiere decir que el barbero sí se afeita a sí mismo. Pero ya dijimos que el barbero no se afeita, así que esto es una tontería.

El resultado de esta discusión es que la situación hipotética lleva a una contradicción, por lo que es imposible.

El mismo razonamiento muestra que no hay conjunto que contenga precisamente los conjuntos que no se contienen a sí mismos. (De lo contrario, la pregunta “¿El conjunto se contiene a sí mismo?” sería una paradoja. ¿Ves por qué?) Las soluciones de Ejercicios\(9.6.7\) y\(9.6.8\) se basan en la misma idea.

_________________
\(\text { * }\) Los dígitos de\(d\) son sólo 1's y 5's, por lo que no es un problema que los números que terminan en 000.. también se puede expresar como un decimal diferente que termina 999...