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: |P(N)| = |Reals|

  1. Feb 13, 2009 #1
    1. The problem statement, all variables and given/known data

    Show that |P(N)|=|R|. (R=reals, |X| is the cardinality of X).

    2. Relevant equations



    3. The attempt at a solution

    #1.) P(N) --> R

    Given any element, A, of P(N), construct a decimal expansion .x1x2x3x4... by the rule that x_i=1 (if i is in A) and x_i=0 (if i is not in A).

    So the element {1,7} would give .1000001

    This map is 1-1 but not onto the Reals.

    #2.) R --> P(N)

    If I can show this direction then #3 follows. I know a little about the mapping of [0,1] onto the Reals. I cannot determine if that helps here.

    #3.) Using the Cantor-Schroeder-Bernstein Theorem, |P(N)|=|R|.
     
  2. jcsd
  3. Feb 13, 2009 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    For #1, instead of a decimal expansion make it a binary expansion. In fact I think you can show this to give a bijection between [0, 1] and P(N). Then use (or prove) the "famous" result that | [0, 1] | = |R|.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook