Troll Maths : Bijection between P(N) and N? 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...
 A: 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$.
A: 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.
