Cantor ' Teorema de s $\Bbb N$.

Question

Hola me gustaría probar esta pregunta, pero estoy un poco estancado.

Muestran que no hay una correspondencia uno a uno de el conjunto de enteros positivos para el juego de poder de la serie de los enteros positivos.

[Sugerencia: Suponer que existe una correspondencia uno a uno. Representan un subconjunto del conjunto de enteros positivos como una infinita cadena de bits con on el bit 1 si i pertenece al subconjunto y 0 en caso contrario. Supongamos que usted puede obtener una lista de estas infinitas cadenas de caracteres en una secuencia indexados por el los enteros positivos. La construcción de una nueva cadena de bits con su ith bits igual al complemento de la i-ésima poco de la i-ésima cadena en la lista. Mostrar que esta nueva cadena de bits no puede aparecer en la lista.]

Answer 1

Deje $S$ el conjunto de los enteros positivos. Supongamos que hay un bijection $f : S \to P(S)$. Entonces todo subconjunto de a $S$ es igual a $f(s)$ algunos $s \in S$. Para cualquier $s\in S$, $f(s)$ es un subconjunto de a $S$, y es ciertamente el caso de que cualquiera de las $s\in f(s)$ o $s\notin f(s)$. [Existe, por ejemplo, $s_1$ tal que $f(s_1)= S$, and then $s_1 \in f(s_1)$; likewise, there exists $s_2$ such that $f(s_2) = \emptyset$, and then $s_2 \noen f(s_2)$.] Define $$ to be the set of all elements $s$ of $S$ such that $s \noen f(s)$; symbolically, $$A = \{s\in S\,|\,s \notin f(s)\}.$$

(En la anterior notación, $s_1 \notin A$ pero $s_2 \in A$.)
Ciertamente, $A$ es un subconjunto de a $S$; es decir, $A\in P(S)$. Por lo tanto, como $f$ es un bijection, $A = f(a)$ algunos $a \in S$.
Ahora la pregunta: ¿$a$pertenecen a $A$?
Si $a \notin A$,$a \notin f(a)$, por lo que, por definición, de $A$,$a \in A$. Esta es una contradicción. Y si $a \in A$$a \in f(a)$, por lo que, por definición, de $A$ tenemos $a \notin A$, de nuevo una contradicción.
Así hemos llegado a una contradicción, en cualquier caso. Así llegamos a la conclusión de que no puede haber un bijection de$S$$P(S)$.

Answer 2

Sugerencia: Dejar $(b_1,b_2,...,b_i,...)$ denota una nueva cadena de bits. Y que $(a_{i1},a_{i2},...,a_{ii},...)$ denota la cadena de th de $i$ que corresponde al entero de th de $i$. Tomar $b_1 \neq a_{11}$, $b_2 \neq a_{22}$,..., $b_i \neq a_{ii}$ y así sucesivamente. Se llama argumento diagonal de Cantor.