# Set of all Subsets of Natural Numbers

1. Feb 14, 2008

### PingPong

1. The problem statement, all variables and given/known data
Prove that the set of all subsets of the natural numbers is uncountable.

2. Relevant equations
All of the countability stuff - including Cantor's diagonal argument

3. The attempt at a solution
I think I have this one figured out, but I was wondering if somebody would be willing to check it for me.

Suppose we have a subset of the natural numbers, A. Then I've defined a bijective function $$f:A\rightarrow \{s_k\}$$, where $$s_k=1$$ if $$k\in A$$ and 0 if $$k\notin A$$ (that is, convert A to a sequence of 0's and 1's, based on whether or not the kth natural number is in the subset A). Using Cantor's diagonal process (Theorem 2.14 in baby Rudin if anybody's interested), we can say that since the set of all sequences whose elements are 0's and 1's are uncountable, A is also uncountable.

Thanks in advance!

2. Feb 14, 2008

### Dick

That works. You knew that didn't you? If you want to test your understanding a little further, tell me why if we take all finite subsets of the naturals, that the Cantor diagonal argument doesn't show that that set is uncountable?

3. Feb 15, 2008

### mathboy

The map f: [0,1) -> P(N) given by
f(0.a1 a2 a3 a4 ...) = {a1, 10+a2, 20+a3, 30+a4, ...}
is one-to-one, so P(N) cannot be countable since [0,1) isn't countable.

4. Feb 16, 2008

### PingPong

Hi Dick and mathboy,

Thanks for your help!

To (maybe) answer Dick's question, is it that, while using the diagonal argument, you may get an infinite sequence of 0's and 1's that isn't in the set of finite subsets?

5. Feb 16, 2008

### Dick

Exactly.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook