6.3: Conjuntos incontables

En esta sección demostramos uno de los resultados más notables de las matemáticas modernas. Hay conjuntos que no son contables. Cuando este resultado fue comunicado por primera vez en 1878 por Georg Cantor, asombró al mundo matemático. De este resultado se deduce que, en el sentido más significativo, existen diferentes tamaños de infinito. Supongamos que no\(X\) es un conjunto contable. Por teorema 6.6,\(\mathbb{N} \preceq X\). Por el Teorema de Schröder-Bernstein\(X \preceq \mathbb{N}\), si\(|\mathbb{N}|=|X|\), entonces, y\(X\) sería contable. Entonces si no\(X\) es contable,\(X \npreceq \mathbb{N}\), y\(\mathbb{N} \prec X\). Es decir,\[\aleph_{0}<|X| \text {. }\] DEFINICIÓN. Incontable Un conjunto que no es contable se llama incontable.

Por supuesto, todavía tenemos que demostrar que hay conjuntos incontables.

NOTACIÓN. \(\prec\)Dejar\(X\) y\(Y\) ser conjuntos. Entonces\(X \prec Y\) siempre que\[X \preceq Y\] y\[|X| \neq|Y| .\] escribimos\(|X| \leq|Y|\) si\(X \preceq Y\), y\(|X|<|Y|\) si\(X \prec Y\).

Definición. Power set,\(P(X)\) Let\(X\) be a set. Entonces\[P(X)=\{Y \mid Y \subseteq X\} .\]\(P(X)\) se llama el conjunto de poder de\(X\). Es el conjunto de todos los subconjuntos de\(X\).

El siguiente teorema, debido a G. Cantor, es uno de los resultados más notables de las matemáticas. No sólo prueba la existencia de un conjunto incontable, implica que el conjunto de poder genera necesariamente conjuntos de cardinalidad mayor y con ello proporciona un medio para construir infinitamente muchas cardinalidades infinitas diferentes. TEOREMA 6.7. Que\(X\) sea un conjunto. Después\[|X|<|P(X)| .\] Discusión. Para probar este resultado necesitamos demostrar que una bijección entre un conjunto y su conjunto de potencia es imposible. ¿Cómo se muestra la imposibilidad de tal función? Podemos suponer que tal bijección existe y derivar una contradicción. Alternativamente, podemos demostrar que cualquier función, desde un conjunto hasta su conjunto de potencia, necesariamente falla en ser una suryección, que es casi lo mismo, y más elegante. Necesitamos demostrar que cualquier función de un conjunto a su conjunto de potencia “echa de menos” algunos elementos del conjunto de potencia. Utilizaremos una técnica conocida como argumento diagonal para construir un elemento del conjunto de potencia que no esté en el rango de la función. El dominio,\(X\), actúa como un índice para realizar un seguimiento de los elementos del rango de la función (este es otro uso para las funciones). Construimos un elemento que\(Y \in P(X)\) no está en el rango de la función agregando\(x \in X\) a\(Y\) iff no\(x\) está en el elemento de\(P(X)\) indexado por\(x\) (es decir, no\(x\) está en el imagen de\(x\) debajo de la función). Es fácil demostrar que este subconjunto\(Y\) de no\(X\) está en el rango de la función y, por lo tanto, la función no logra ser una sobreyección sobre\(P(X)\).

Prueba. Observamos que la función\(g: X \rightarrow P(X)\) definida por\[g(x)=\{x\}\] es una inyección. En el caso el\(X=\emptyset, g\) es la función vacía es decir, la función cuya gráfica es la\(\emptyset\). (Debe verificar que la función vacía es una inyección). Por lo tanto,\[|X| \leq|P(X)| \text {. }\]\[f: X \rightarrow P(X)\] vamos a definir\[Y:=\{x \in X \mid x \notin f(x)\} .\] Discusión. Recordemos que para cada uno\(x \in X, f(x)\) es un subconjunto de\(X\). Por lo tanto, tiene sentido considerar si\(x\) es un elemento de\(f(x)\). ¡El sabor autorreferencial de este argumento lo hace desafiante en la primera lectura!

Claramente,\[Y \subseteq X\] ¿es\(Y \in f[X]\)? Supongamos que lo fuera, así que\(Y=f\left(x_{0}\right)\) para algunos\(x_{0}\) en\(X\). Pero entonces,\(x_{0}\) estaría en\(Y\) iff no\(x_{0}\) estaban en\(f\left(x_{0}\right)=Y\). Esto es imposible, contradiciendo la suposición en la que\(Y\) se encuentra\(f[X]\).

Podrías intentar reparar\(f\) modificándolo para incluir en su rango el conjunto diagonal que construimos. Al aplicar nuevamente el argumento diagonal, se identificará un nuevo elemento que falta en el rango de la función modificada. De hecho, la mayoría de los elementos del codominio faltan en el rango de la función, aunque esto no es inmediatamente obvio a partir de la prueba.

Todavía podría estar confundido por el motivo por el que esto se llama argumento diagonal. Esto será obvio cuando apliquemos la técnica a secuencias binarias infinitas.

Si\(X\) es finito el teorema es obvio. En efecto, si hay\(n \in \mathbb{N}\) tal que\(|X|=n\), entonces\(|P(X)|=2^{n}\). El teorema\(6.7\) implica que cualquier conjunto, incluido un conjunto infinito, es estrictamente más pequeño que su conjunto de potencia. De hecho, al iterar las aplicaciones de la función power set to\(\mathbb{N}\), se ve fácilmente que hay infinitamente muchos conjuntos infinitos de cardinalidad distinta en la secuencia de conjuntos\[\langle\mathbb{N}, P(\mathbb{N}), P(P(\mathbb{N})), \ldots\rangle\] (¿Cuál es la cardinalidad de la unión sobre esta secuencia? ¿Cuál es la cardinalidad del conjunto de poder de esa unión?)

Demostraremos que dos conjuntos más son incontables. Ambos son conjuntos de interés matemático. Primero mostraremos que las secuencias binarias infinitas son incontables. Las secuencias binarias infinitas son funciones de\(\mathbb{N}\) a\(\ulcorner 2\urcorner\). Como veremos, existe una relación muy estrecha entre secuencias binarias infinitas y el conjunto de potencias de\(\mathbb{N}\). De manera más general, la colección de todas las funciones de un conjunto a otro puede ser de interés matemático. Introducimos una notación para tales colecciones.

NOTACIÓN. \(Y^{X}\)Dejar\(X\) y\(Y\) ser conjuntos. Se escribe el conjunto de todas las funciones con dominio\(X\) y codominio\(Y\)\(Y^{X}\).

No confundas esto con exponenciación. Sin embargo si\(X\) y\(Y\) son finitos,\[\left|Y^{X}\right|=|Y|^{|X|} .\] El conjunto de todas las funciones de algún conjunto\(X\) en\(\ulcorner 2\urcorner\) está en correspondencia biyectiva con\(P(X)\):

Proposición 6.8. Dejar\(X\) ser un conjunto, y definir\(F:\ulcorner 2\urcorner X \rightarrow P(X)\) por: para\(\chi \in\ulcorner 2\urcorner X\),\[F(\chi)=\chi^{-1}(1) .\] Eso es\(F(\chi)=\{x \in X \mid \chi(x)=1\}\). Entonces\(F:\ulcorner 2\urcorner^{X} \rightarrow P(X)\) es una biyección.

PRUEBA. La prueba se deja como ejercicio.

La existencia de esta biyección nos permite probar fácilmente el siguiente teorema.

TEOREMA 6.9. El conjunto de secuencias binarias infinitas es biyective con\(P(\mathbb{N})\) y por lo tanto es incontable.

PRUEBA. Por Proposición\(6.8\)\[\left|\ulcorner 2\urcorner^{\mathbb{N}}\right|=|P(\mathbb{N})| .\] Por Teorema 6.7,\[|\mathbb{N}| \prec|P(\mathbb{N})| .\] Por lo tanto\(\ulcorner 2\urcorner^{\mathbb{N}}\) es incontable.

Notación. \(2^{\mathbb{N}_{0}}\)Utilizamos\(2^{\mathbb{N}_{0}}\) para la cardinalidad de\(\left\ulcorner 22^{\mathbb{N}}\right.\). Vale la pena ilustrar mediante una aplicación a infinitas secuencias binarias por qué la técnica utilizada para probar el Teorema\(6.7\) se denomina argumento diagonal (a veces llamado el segundo argumento diagonal, para distinguirlo del “primer argumento diagonal” en la Sección 6.4). Vamos\(f: \mathbb{N} \rightarrow\ulcorner 2\urcorner \mathbb{N}\). Demostramos que no\(f\) es una sobreyección por aplicación directa del argumento diagonal en la prueba del Teorema 6.7. Enumeramos todos los elementos en el rango de\(f\); cada uno es una secuencia de 0 y 1. Ahora\[\begin{aligned} & f(0)=a_{00} \quad a_{01} \quad a_{02} \quad a_{03} \quad \ldots \quad a_{0 j} \ldots \\ & f(1)=a_{10} \quad a_{11} \quad a_{12} \quad a_{13} \quad \ldots \quad a_{1 j} \quad \ldots \\ & f(2)=a_{20} \quad a_{21} \quad a_{22} \quad a_{23} \quad \ldots \quad a_{2 j} \quad \ldots \\ & f(3)=a_{30} \quad a_{31} \quad a_{32} \quad a_{33} \quad \ldots \quad a_{3 j} \quad \ldots \end{aligned}\] creamos una secuencia alterando los elementos diagonales de esta matriz infinita. Dejar\(s\) ser la secuencia de elementos diagonales\[\left\langle 1-a_{00}, 1-a_{11}, \ldots, 1-a_{i i}, \ldots\right\rangle .\]

FIGURA 6.10. El segundo argumento diagonal

La secuencia\(s\) es un elemento de\(\ulcorner 2\urcorner^{\mathbb{N}}\), y difiere de cada elemento en el rango de\(f\): de hecho,\(s\) difiere de\(f(i)\) en al menos la\(i^{\text {th }}\) ranura. De ahí,\[s \notin f[\mathbb{N}],\] y así no\(f\) es una sobrejección. Lo dejamos como un ejercicio para mostrar que\(s\) es el conjunto diagonal\(Y\) construido en la prueba del Teorema 6.7, donde\(X=\mathbb{N}\). Más precisamente,\(s\) es la imagen de\(Y\) bajo la bijección natural de\(P(\mathbb{N})\) a\(\ulcorner 2\urcorner^{\mathbb{N}}\) de la Proposición 6.8.

Consideramos otro conjunto de interés matemático, el conjunto de todas las secuencias decimales infinitas. Este conjunto tiene una estrecha relación con el intervalo cerrado\([0,1]\). Comprender esta relación requiere una comprensión más profunda y formal de los números reales de lo que la mayoría de los estudiantes han estado expuestos en el cálculo, y posponemos la discusión detallada de esta relación hasta la Sección 8.9. Con algunas modificaciones, el siguiente teorema demostrará que\([0,1]\) es incontable, y por lo tanto\(\mathbb{R}\) es incontable (ver Sección 8.9).

TEOREMA 6.11. El conjunto de expansiones decimales infinitas es incontable. De hecho,\[\left|\ulcorner 10\urcorner^{\mathbb{N}}\right|=2^{\aleph_{0}} .\] DISCUSIÓN. La función de identidad en las secuencias binarias infinitas en las secuencias decimales infinitas es claramente una inyección. Construiremos una inyección de las secuencias decimales infinitas a secuencias binarias infinitas. El teorema seguirá del Teorema de Schröder-Bernstein.

PRUEBA. Es obvio que\[\left|\ulcorner 2\urcorner^{\mathbb{N}}\right| \leq\left|\ulcorner 10\urcorner^{\mathbb{N}}\right| .\] (¿Por qué?) Definiremos una inyección\[f:\ulcorner 10\urcorner^{\mathbb{N}} \rightarrow\ulcorner 2\urcorner^{\mathbb{N}} .\] Let\(x \in\ulcorner 10\urcorner^{\mathbb{N}}\). Entonces,\[x=\left\langle x_{j} \mid j \in \mathbb{N}\right\rangle\] ¿dónde\(x_{j}\) está el\(j^{t h}\) miembro de la secuencia\(x\) y\[0 \leq x_{j} \leq 9 .\] queremos definir una secuencia binaria\(s(x)\) que “codifique”\(x\). Hay muchas maneras de hacerlo. Una es mirar bloques de 10 bits (abreviatura de “dígitos binarios”), y, en\(j^{\text {th }}\) dicho bloque, tener nueve de los bits 0, y poner un 1 en la\(x_{j}^{\text {th }}\) ranura. Formalmente, dada una secuencia decimal infinita\(x\), definimos una secuencia binaria\[f(x)=\left\langle y_{i} \mid i \in \mathbb{N}\right\rangle\] para que\(y_{i}=1\) si hay\(j \in \mathbb{N}\) tal que\[i=10 j+x_{j} .\] De lo contrario\(y_{i}=0\). Con ello definimos una función\[f:\ulcorner 10\urcorner \rightarrow\ulcorner 2\urcorner .\] Demostramos que\(f\) es una inyección. Dejar\(x\) y\(y\) ser elementos distintos de\(\ulcorner 10\urcorner^{\mathbb{N}}\). Entonces hay algunos\(j \in \mathbb{N}\) tales que\[x_{j} \neq y_{j} .\] Entonces\[10 j+x_{j} \neq 10 j+y_{j} .\] Vamos\(i=10 j+x_{j}\). Entonces\(f(x)\) y\(f(y)\) difieren en el\(i^{\text {th }}\) componente. Es decir,\[(f(x))_{i}=1 \neq 0=(f(y))_{i} .\] Por lo tanto\(f\) es una inyección y\[\left|\ulcorner 10\urcorner^{\mathbb{N}}\right| \preceq\left|\ulcorner 2\urcorner^{\mathbb{N}}\right| .\] Por el Teorema de Schröder-Bernstein, (6.12) y (6.13) rendimiento\[\left|\ulcorner 10\urcorner^{\mathbb{N}}\right|=2^{\aleph_{0}} .\] Demostramos en Sección\(8.9\) que\[|[0,1]|=\left|\ulcorner 10\urcorner^{\mathbb{N}}\right|,\] esencialmente identificando un real número con su expansión decimal. Si asumimos este resultado, podemos probar fácilmente que los números reales son incontables. COROLARIO 6.14. \(\mathbb{R}\)es incontable.