13.3: Más información sobre los tamaños relativos de los conjuntos
- Page ID
- 118057
¿Cuál es el “tamaño” de\(\mathbb{R}\text{?}\)
Sabemos\(\mathbb{N}\text{,}\)\(\mathbb{Z}\text{,}\) y\(\mathbb{Q}\) todos tenemos el mismo tamaño (contablemente infinito). Pero\(\mathbb{R}\) es tan grande que no es contable, por lo que parece que\(\mathbb{R}\) debería ser “más grande” que\(\mathbb{N}\text{,}\)\(\mathbb{Z}\text{,}\) y\(\mathbb{Q}\text{.}\)
el conjunto\(B\) es mayor que el establecido\(A\) si
- \(B\)tiene un subconjunto del mismo tamaño que\(A\text{,}\) y
- cada subconjunto de los\(B\) cuales tiene el mismo tamaño que\(A\) es apropiado
si\(B\) es mayor que\(A\text{,}\) entonces\(A\) es menor que\(B\)
- Mostrar que existe una inyección\(A \hookrightarrow B\text{.}\)
- Demostrar que cada inyección\(A \hookrightarrow B\) no puede ser también una sobreyección.
Sin embargo, si uno o ambos\(A,B\) son finitos, uno puede verificar que\(\vert B \vert > \vert A \vert \text{.}\)
- Emparejar las partes de la Prueba con las partes de la definición de conjunto más grande:
- La existencia de una inyección\(f: A \hookrightarrow B\) demuestra que\(B\) tiene un subconjunto que tiene el\(A\text{,}\) mismo tamaño que restringir el codominio para\(f: A \rightarrow f(A)\) crear una biyección.
- Por definición, un subconjunto\(C \subseteq B\) tiene el mismo tamaño que\(A\) cuando existe una biyección\(A \to C\text{.}\) Ampliando el codominio, tal biyección puede ser pensada como una inyección\(A \hookrightarrow B\) cuya imagen es\(C \subseteq B\text{.}\) Si no tal inyección también puede ser suryectiva, entonces\(C\) es\(C \subsetneqq B\text{,}\) decir, es una subconjunto adecuado de\(B\text{.}\)
- En la segunda parte de la prueba, simplemente se puede demostrar que cada función\(A \to B\) no puede ser una sobreyección, en cuyo caso seguramente toda inyección\(A \hookrightarrow B\) no puede ser una sobreyección. Puede parecer que debería ser más difícil probar esta afirmación más general, pero si encuentra que su argumento de que cada inyección no puede ser una sobreyección no se basa realmente en el supuesto de inyección, entonces no hay necesidad de esa suposición.
El juego\(\mathbb{R}\) es más grande que cada uno de los conjuntos\(\mathbb{N}\text{,}\)\(\mathbb{Z}\text{,}\) y\(\mathbb{Q}\text{.}\)
Aquí sigue una comparación importante de tamaños de conjuntos.
Cada conjunto es más pequeño que su propio conjunto de potencia.
- Prueba
-
Vamos a\(A\) representar un conjunto arbitrario. Aplicaremos la prueba de conjunto más grande para demostrar que\(\scr{P}(A)\) es mayor que\(A\text{.}\)
- Existe una inyección natural
\ begin {align*} A &\ hookrightarrow\ mathscr {P} (A),\\ x &\ mapsto\ {x\}. \ end {align*}
(Si\(A\) está vacío, entonces esta es solo la función vacía, que siempre es inyectable por la Sentencia 1 de la Proposición 12.1.1.)- Supongamos que\(f: A \rightarrow \scr{P}(A)\) es una función arbitraria. Usando la Prueba de Función Surjectiva, demostraremos que no puede ser suryectiva exhibiendo un elemento\(X \in \scr{P}(A)\) para el cual ningún elemento\(a \in A\) satisface\(f(a) = X\text{.}\) (No necesitaremos hacer la suposición de que\(f\) es inyectable — ver Declaración 2 de Observación\(\PageIndex{1}\).)
Tenga en cuenta que para cada\(a \in A\text{,}\) elemento de imagen\(f(a) \in \scr{P} (A)\text{,}\) siendo un elemento de conjunto de potencia, es un subconjunto de\(A\text{.}\) Así que para cada uno\(a \in A\) podemos preguntar si\(a\) está contenido en el subconjunto\(f(a)\) o no. Recogiendo juntos las respuestas “o no”, conjunto
\ begin {ecuación*} X =\ {a\ en A: a\ notin f (a)\}. \ end {equation*}
Tenga en cuenta que\(X\) es un subconjunto de\(A\text{,}\) por lo que de nuevo esto significa que también es un elemento de\(\scr{P}(A)\text{.}\)Podría\(f(a) = X\) ser posible para algunos\(a \in A\text{?}\) Ya que\(X \subseteq A\text{,}\) para cada uno\(a \in A\) tenemos cualquiera\(a \in X\) o\(a \notin X\text{.}\)
Caso\(a \in X\).
Entonces por definición de lo\(X\) anterior, tenemos\(a \notin f(a)\text{.}\) Since\(X\) contiene elemento\(a\) pero no\(f(a)\) lo hace, establece\(X\) y\(f(a)\) no puede ser igual.Caso\(a \notin X\).
Entonces por definición de lo\(X\) anterior, debemos tener\(a \in f(a)\text{,}\) ya que de lo contrario\(a\) satisfacería la condición de estar en\(X\text{.}\) Pero ahora\(f(a)\) contiene elemento\(a\) pero no lo\(X\) hace, así que de nuevo establece\(X\) y\(f(a)\) no puede ser igual.Como no\(f(a) = X\) es posible en todos los casos, hemos encontrado un elemento en\(\scr{P}(A)\) que no está en la imagen\(f(A)\text{,}\) como se requiere para demostrar que no\(f\) es suryectiva.
¡El Teorema de Cantor implica que hay un número infinito de “niveles” de infinito! Porque, si\(A\) es un conjunto infinito, entonces\(\scr{P}(A)\) es un conjunto infinito más grande, y\(\scr{P}(\scr{P}(A))\) es un conjunto infinito aún más grande, y\(\scr{P} (\scr{P}(\scr{P}(A )))\) es un conjunto infinito aún más grande,...
El tamaño del conjunto de números naturales\(\mathbb{N}\) parece ser el nivel más bajo posible de infinito, ya que cada subconjunto de\(\mathbb{N}\) es finito o tiene el mismo tamaño que\(\mathbb{N}\text{.}\) (Ver Declaración 1 de la Proposición 13.2.1.) El conjunto de números reales\(\mathbb{R}\) es mayor que\(\mathbb{N}\text{,}\) ya que contiene\(\mathbb{N}\) como un subconjunto propio pero no es en sí mismo del mismo tamaño\(\mathbb{N}\text{.}\) que Así que escribir no\(\vert \mathbb{N} \vert = \infty\) es lo mismo que escribir\(\vert \mathbb{R} \vert = \infty\text{,}\) ya que evidentemente son diferentes niveles de infinito. ¿Hay algún nivel de infinito entre estos dos?
No existe un conjunto mayor que\(\mathbb{N}\) pero menor que\(\mathbb{R}\text{.}\)
¡No se sabe si la Hipótesis del Continuum es cierta! De hecho, ¡se ha demostrado que la Hipótesis del Continuum no puede ser probada ni desmentida en ciertos sistemas axiomáticos comunes para la teoría de conjuntos!
Hemos visto que pueden pasar cosas divertidas con tamaños de conjuntos infinitos — por ejemplo,\(\mathbb{N}\) es un subconjunto adecuado de\(\mathbb{Z}\text{,}\) pero los dos tienen el mismo tamaño! Esto no es un defecto en nuestras definiciones, solo demuestra que para conjuntos infinitos, la relación de subconjunto no es una buena medida de tamaño. Pero también demuestra que debemos estar atentos a otras posibles consecuencias poco intuitivas de nuestras definiciones, porque podrían revelar defectos en nuestras definiciones. Por ejemplo, a partir de nuestras definiciones de conjuntos cada vez más grandes, no hay razón obvia por la que no pueda haber algún extraño ejemplo de un par de conjuntos\(A\) y\(B\) con ambos\(B\) más grandes que\(A\) y más\(A\) grandes que\(B\text{.}\) Afortunadamente, eso no puede suceder gracias a lo siguiente teorema.
Supongamos\(A\) y\(B\) son conjuntos infinitos. Si existe tanto una inyección\(A \hookrightarrow B\) como una inyección\(B \hookrightarrow A\text{,}\) entonces\(A\) y\(B\) tienen el mismo tamaño.
- Prueba
-
Supongamos\(f: A \hookrightarrow B\) y\(g: B \hookrightarrow A\) son inyecciones. Necesitamos exhibir una bijección de\(A\) a\(B\) (o viceversa, pero construiremos una de\(A\) a\(B\)).
Por cada elemento\(a \in A\text{,}\) podemos construir una cadena de elementos alternantes a partir de\(A\) y de la\(B\) siguiente manera. Trabajando hacia adelante desde\(a\text{,}\) los\(f\) mapas de inyección\(a\) a algún elemento de\(B\text{,}\) y la inyección\(g\) mapea ese elemento de\(B\) a algún elemento del\(A\text{,}\) cual es mapeado por\(f\) a algún elemento de\(B\text{,}\) y así sucesivamente.
\ begin {align*} a_0 & = a,\\ b_0 & = f (a_0),\\ a_1 & = g (b_0),\\ b_1 & = f (a_1),\\ a_2 & = g (b_1),\\ &\ vdots\ end {align*}
La cadena seguirá infinitamente porque las funciones\(f\) y\(g\) siempre proporcionan un siguiente elemento.También podemos intentar trazar la cadena hacia atrás: a partir de nuestro elemento original\(a \in A\text{,}\) podemos buscar algún elemento de\(B\) ese\(g\) mapa,\(a\text{,}\) aunque a primera consideración es posible que no exista ninguno. Si encontramos tal elemento de entonces\(B\text{,}\) podemos buscar algún elemento de\(A\) ese\(f\) mapa a él, y así sucesivamente. Si bien la cadena se extiende infinitamente en la dirección hacia adelante, no podemos estar seguros en este punto de que se extenderá infinitamente en la dirección hacia atrás.
Ahora bien, cada elemento de\(A\) puede colocarse en tal cadena, y porque\(f\) y\(g\) son inyectivas la cadena en la que encontramos un elemento\(a\) es siempre la misma: el siguiente elemento en la cadena es siempre\(f(a)\text{,}\) y el elemento anterior\(a\) es siempre el único\(b\) en \(B\)de manera que\(g(b) = a\) (si tal elemento existe). Y los elementos después\(f(a)\) y antes también\(b\) están determinados de manera única por la inyectividad de\(f\) y\(g\text{.}\) Y así sucesivamente.
Así que terminamos encontrando cada elemento de\(A\) en una cadena alterna única, y cada cadena tiene uno de cuatro patrones:
- una cadena con algún elemento repetido, en cuyo caso podríamos obligar a la cadena a dormirse sobre sí misma en la repetición para formar una cadena circular finita;
- una cadena sin repetición y sin fin ni inicio;
- una cadena sin repetición y sin fin, pero el proceso para trazarla hacia atrás falló en algún momento, y el último elemento en la dirección “hacia atrás” (que podríamos ver como el primer elemento de toda la cadena) es un elemento de\(A\text{;}\) y
- una cadena sin repetición y sin fin, sino que comienza con un elemento de\(B\text{.}\)
Ahora que hemos recortado posibles repeticiones creando cadenas circulares, cada elemento de\(A\) aparece exactamente una vez en una cadena única, y por simetría se puede decir lo mismo de\(B\text{.}\) Podemos entonces crear una bijección de\(A\) a\(B\) mapeando cada elemento de\(A\) a la elemento de\(B\) eso lo sigue en la cadena en la que aparece. A excepción de elementos de\(A\) eso aparecen en una cadena que tiene un comienzo con un elemento de partida de\(B\) — en cambio cada uno de esos elementos de\(A\) debe mapearse al elemento de\(B\) que lo precede en su cadena. Esto creará una correspondencia biyectiva entre los elementos de\(A\) y\(B\text{.}\)