Troll Maths : Bijection between P(N) and N?

Question

I just wanted to know what's wrong in the following argument:

Say I take a number and rewrite as a binary. e.g 155 = 10011011

Then I can relate the number with a subset of N, which contains the exponents of 2 where the 1's appear in binary form.

So

$155 = 2^0 + 2^1 + 2^3 + 2^4 + 2^7 \Rightarrow \{0,1,3,4,7\}$

$64 = 2^6 \Rightarrow \{6\}$

$122 = 2^4 + 2^5 + 2^6 \Rightarrow \{4,5,6\}$

$0 \Rightarrow \{\} $

Now since every number has unique binary decomposition, and the map is a surjection, it is a bijection between the power set of N and N...

Answer 1

All this shows is that there is a bijection between $\mathbb{N}$ and its finite subsets. What number corresponds to the set of odd numbers?

---

Here's a proof that shows why this can't work.

Assume that $f : \mathbb{N} \rightarrow \mathcal{P}(\mathbb{N})$ is a surjection. Let $Z = \left\{ x : x \in \mathbb{N} \wedge x \not\in f(x) \right\}$. Clearly $Z$ must be in the range of $f$, so there must be some $y \in \mathbb{N}$ such that $f(y) = Z$. Suppose that $y \in Z$. But by the definition of $Z$, $y \not\in Z$. So alternatively suppose that $y \not\in Z$. But again by the definition $y \in Z$. Either way we have a contradiction. So there can be no such $f$.

Answer 2

One problem is that $\mathbb{N} \in P(\mathbb{N})$ and there is no natural number that's mapped to $\mathbb{N}$, thus your function is not a surjection. Maybe there are other probelms aswell, I'm not entierly sure.

Edit: As Ilya points out in the comments, before I managed to post my answer, there are ofcourse many other infinite subsets of $\mathbb{N}$ that aren't in the range of this function.