Una falsa prueba de contables poder establecer

Question

Sé que $2^\mathbb{N}$ no es contable, pero lo que está mal con la siguiente "prueba"?

Considere el siguiente mapa de $f: \mathbb{N} \to 2^\mathbb{N}$, el cual se asigna un número natural $n$ a un conjunto de números enteros que corresponden a el índice de no-bits cero en $n$'s representación binaria:

$$f(n)=\{i ~|~ n = \sum_{i=0} k_i2^i \land k_i=1\}$$

$f(n)$ es claramente "a", ya que para cualquier $S\in 2^\mathbb{N}$, existe un número natural $n = \sum_{i\in S} 2^i$ s.t. $f(n)=S$.

Sin embargo, si $f(n)$ es sobre, entonces este es efectivamente demuestra que el $2^\mathbb{N}$ es contable, que es, por supuesto, falso. Donde fue el error?

Answer 1

El rango de la función incluye sólo los subconjuntos finitos de $\Bbb N$. Si $S$ es un subconjunto infinito de $\Bbb N$, $\sum_{i\in S}2^i$ no está definido.

Answer 2

El error es que usted asuma que usted asumió $S \in 2^{\Bbb N}$ es un conjunto finito. De hecho, su declaración, constituye una prueba válida de que hay countably muchos subconjuntos finitos de $\Bbb N$, que es sin duda útil de los bits de información.

Tenga en cuenta que si usted mira infinitas sumas de la forma $\sum_{i} k_i2^{-i+1}$, usted termina con un surjective mapa a $[0,1]$.

Answer 3

Es tal vez la pena señalar que este no dar una prueba de un bijection $\mathbb{Z}_2 \to 2^{\mathbb{N}}$ entre el $2$-ádico enteros, y los subconjuntos de a $\mathbb{N}$, puesto que el $2$-ádico enteros están en una correspondencia uno a uno con tal binario nmerals.