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...

• You've only considered finite numbers, and all finite sequences of elements of $\mathbb N$ (in your case, sequences of $0$'s and $1$'s) are indeed a countable set. However, $P(\mathbb N)$ also contains infinite sequences (much more of them, than of finite ones!)
– Ilya
May 23, 2012 at 14:11
• Why is this called "Troll Maths"? May 23, 2012 at 14:14
• @JonasMeyer It's a reference to an internet meme, where what appear to be proofs of false statements are given. May 23, 2012 at 14:17
• This question is substantially similar to Cardinality of the power set of the set of all primes.
– MJD
May 23, 2012 at 14:24
• May 23, 2012 at 14:26

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?
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$.
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.