Estoy tratando de averiguar si la clase de subconjuntos de números enteros es infinita numerable o no. Sé que una colección de todos los subconjuntos finitos de números enteros es contable. Creo necesario utilizar diagonalización para probar si su verdadero o no pero im no está seguro de cómo abordarlo.
Toda ayuda es muy apreciada!
Gracias
No, el conjunto de todos los subconjuntos de los enteros no es contable. Desde $\mathbb{Z}$ tiene la misma cardinalidad como $\mathbb{N}$, es suficiente para considerar todos los subconjuntos de a $\mathbb{N}$.
Para cada subconjunto $X$ $\mathbb{N}$ considera la función característica $\chi_X$ definido por
$\chi_X(z) = \begin{cases} 1 & \quad z \in X \\ 0 & \quad z \notin X \end{casos}$
En esta forma de asociar injectively y subjetivamente cada subconjunto $X$ $\mathbb{N}$ con una función en $2^{\mathbb{N}}$. $2^\mathbb{N}$ tiene cardinalidad estrictamente mayor que $\mathbb{N}$. Esto está demostrado por el típico diagonalización de Cantor argumento.
También, Diagonalización de Cantor y la función que escribí anteriormente puede ser utilizado para mostrar de manera más general que el conjunto de todos los subconjuntos de un conjunto dado tiene cardinalidad estrictamente mayor que el conjunto dado.
En respuesta al comentario :
Usted puede pensar en una función de $\mathbb{N} \rightarrow 2$ un infinito de cadenas binarias de $0$'s y $1$'s. Suponga que $2^{\mathbb{N}}$ es contable. Que es que hay un bijection $\sigma$$\mathbb{N}$$2^\mathbb{N}$. A continuación, defina la función $h : \mathbb{N} \rightarrow 2$ como sigue
$h(n) = \begin{cases} 1 & \quad (\sigma(n))(n) = 0 \\ 0 & \quad (\sigma(n))(n) = 1 \end{casos}$
De manera informal, es el conocido argumento, formar una nueva cadena binaria por la diagonal y de conmutación $0$$1$$1$$0$. Ahora, esta es una perfecta cadena binaria de ahí abajo aparecen como $\sigma(k)$ algunos $k$ si $\sigma$ es de hecho un bijection. Sin embargo, puede no ser $\sigma(k)$ cualquier $k$ ya que difiere de las $\sigma(k)$ en al menos el $k^\text{th}$ entrada.
Espero que esto ayude.
No es. Para cualquier familia $\mathscr A=(A_x)$ de los subconjuntos de un conjunto dado $X$, indexado por $x$$X$, considerar el subconjunto $B$ $X$ define de la siguiente manera: $B$ es el conjunto de elementos de la $x$ $X$ tal que $x\notin A_x$. A continuación, $B$ no puede ser cualquiera de los conjuntos de $A_x$, por lo que cualquier familia $\mathscr A$ indexados por $X$ no puede contener cada subconjunto de $X$.
Este argumento se llama diagonal de Cantor argumento (donde la diagonal se refiere a la diagonal de un hipotético matriz cuyas líneas será indexado por $X$ y columnas será indexado por $\mathscr A$). Demuestra que el conjunto de todos los subconjuntos de a $X$ tiene cardinalidad mayor que $X$, para cualquier conjunto de $X$.
Edit. He reescrito esta respuesta, ya había un pequeño, pero significativo, inexactitud en mi anterior sugerencia. Gracias a GEdgar por señalar el error, y a ambos GEdgar y Henning Makholm sugerencias para correcciones.
En primer lugar, tenga en cuenta que William Chan demuestra un bijection desde el poder establecido de $\mathbb N$ para el conjunto de infinitamente larga $0$-$1$ cadenas (llamada1 este conjunto $Z$). Esto no es nada, pero el mapa enviar a $S \subseteq \mathbb N$ a sus vectores característicos (función).
Ahora, dado un infinito $0$-$1$ cadena, podemos transformar a un número real mediante la colocación de un binario punto en el principio, y interpretting como un binario de expansión de un número real; este número será claramente mentira en $[0,1]$. (Si esto parece demasiado informal, ver a leo la respuesta para una definición formal.) Así que tenemos un mapa de $Z$ a los reales en $[0,1]$.
Este mapa es, sin duda no es inyectiva, ya que $0.00111\ldots_{2}$ $0.01000\ldots_{2}$ representan el mismo número real. (Este fue, de hecho, el error en la anterior sugerencia.) Sin embargo, es surjective, básicamente porque todos los números reales (en $[0,1]$) tienen un binario de expansión (con nada antes de que el binario de punto). Y sólo necesitamos surjectivity para esta idea ir a través de.
Ahora, desde la $[0,1]$ es incontable, se puede ver que $Z$ también es incontable? ¿Qué puede usted concluir acerca de la cardinalidad de a $2^{\mathbb N}$? Para la primera parte, será necesario que el hecho de que no existe ningún surjective asignación de un contable ajustado a una multitud innumerable.
1Edición. Por Zhen Lin comentario, he cambiado de $\lbrace 0,1 \rbrace^\omega$$\lbrace 0,1 \rbrace^{\mathbb N}$. Decidí llamar a este conjunto, simplemente,$Z$, en lugar de $\lbrace 0,1 \rbrace^{\omega}$ o $\lbrace 0,1 \rbrace^{\mathbb N}$. Ver los comentarios de abajo. Gracias a Asaf por la aclaración, de todas formas.
La respuesta es no. Creo que la mejor forma de ver esto es la @Didier Piau la respuesta. Ahora, a otro, el problema puede reducirse a demostrar que la clase de los subconjuntos de los números naturales es que no contables, como William Chan decir. Te voy a mostrar que clase de infinitos subconjuntos de números naturales no es numerable. Esto es sólo un pequeño cambio de la Srivatsan del argumento.
Decimos que un conjunto a $A$ es numerable, si es equipotente al conjunto $\mathbb{N}$ de los números naturales. Decimos que $A$ es contable, si es finito o numerable.
Lema. Si $A\subseteq B$ $B$ contables, a continuación, $A$ es contable.
Ahora, considere la clase de los infinitos subconjuntos de números naturales $\mathfrak{I}$. Definir $\psi:\mathfrak{I}\to ]0,1]$ $$\psi(A)=\sum_{n\in \mathbb{N}}\frac{\chi_A(n)}{2^n},$$ donde $\chi$ es como en el William Chan respuesta. La función de $\psi$ está bien definida debido a la singularidad de la infinita expansión en base a $2$ de los números en $]0,1]$. Desde una infinita cadena de 0-1s (que no siempre es $0$ a partir de un momento) corresponde a un subconjunto infinito de $\mathbb{N}$, $\psi$ es un bijection y por lo tanto desde $]0,1]$ no es numerable, llegamos a la conclusión de que $\mathfrak{I}$ es no numerable. Entonces, por el lema de la clase de los subconjuntos de a $\mathbb{N}$ no contables.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
