A bogus proof of countable power set

Question

I know that $2^\mathbb{N}$ is not countable but what is wrong with the following "proof"?

Consider the following map $f: \mathbb{N} \to 2^\mathbb{N}$, which maps a natural number $n$ to a set of integers which correspond to the index of non-zero bits in $n$'s binary representation:

$$f(n)=\{i ~|~ n = \sum_{j=0}^\infty k_j2^j \text{ and } k_i=1\}$$

$f(n)$ is clearly "onto" since for any $S\in 2^\mathbb{N}$, there exists a natural number $n = \sum_{i\in S} 2^i$ s.t. $f(n)=S$.

However, if $f(n)$ is onto, then this is effectively proving that $2^\mathbb{N}$ is countable, which is, of course, false. Where was the mistake?

Answer 1

The range of the function includes only the finite subsets of $\Bbb N$. If $S$ is an infinite subset of $\Bbb N$, then $\sum_{i\in S}2^i$ is not defined.

Answer 2

The mistake is that you assume that you assumed $S \in 2^{\Bbb N}$ is a finite set. In fact, your statement constitutes a valid proof that there are countably many finite subsets of $\Bbb N$, which is certainly a useful bit of information.

Note that if you look at infinite sums of the form $\sum_{i} k_i2^{-i+1}$, you end up with a surjective map to $[0,1]$.

Answer 3

It's maybe worth noting that this does give a proof of a bijection $\mathbb{Z}_2 \to 2^{\mathbb{N}}$ between the $2$-adic integers and the subsets of $\mathbb{N}$, since the $2$-adic integers are in one-to-one correspondence with such binary nmerals.