Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Set of all Subsets of Natural Numbers

  1. Feb 14, 2008 #1
    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 [tex]f:A\rightarrow \{s_k\}[/tex], where [tex]s_k=1[/tex] if [tex]k\in A[/tex] and 0 if [tex]k\notin A[/tex] (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. jcsd
  3. Feb 14, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    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?
  4. Feb 15, 2008 #3
    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.
  5. Feb 16, 2008 #4
    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?
  6. Feb 16, 2008 #5


    User Avatar
    Science Advisor
    Homework Helper

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook