Set of all Subsets of Natural Numbers

[PingPong]

Homework Statement

Prove that the set of all subsets of the natural numbers is uncountable.

Homework Equations

All of the countability stuff - including Cantor's diagonal argument

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!

 

[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?

 

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

 

[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?

 

[Dick]

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?

Exactly.