Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 2

up vote 15 down vote accepted

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

share|improve this answer
    
Thanks a lot for your responses !!! –  Dan 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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