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.


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

  • 13
    $\begingroup$ 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!) $\endgroup$ – Ilya May 23 '12 at 14:11
  • $\begingroup$ Why is this called "Troll Maths"? $\endgroup$ – Jonas Meyer May 23 '12 at 14:14
  • $\begingroup$ @JonasMeyer It's a reference to an internet meme, where what appear to be proofs of false statements are given. $\endgroup$ – Alex Becker May 23 '12 at 14:17
  • 1
    $\begingroup$ This question is substantially similar to Cardinality of the power set of the set of all primes. $\endgroup$ – MJD May 23 '12 at 14:24
  • 1
    $\begingroup$ See also math.stackexchange.com/questions/97509/… $\endgroup$ – Jonas Meyer May 23 '12 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?

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

| cite | improve this answer | |
  • $\begingroup$ Thanks a lot for your responses !!! $\endgroup$ – A. Napster May 23 '12 at 16:39

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.