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

Missing step in standard proof of |P(N)|=|R|

  1. Mar 13, 2014 #1
    There are several ways to show the one-to-one correspondence between P(N) (= the power set of the natural numbers) and the set of the reals (or, equivalently, the set of reals in the interval [0,1).) Continued fractions, and all that. However, one argument is the following (sorry, this argument is from memory, and so I looked for a source; I don't know if the following is a valid source to cite, but if not, please ignore: http://scientiststhesis.tumblr.com/post/52431140481/powersets-infinities-and-the-diagonal-argument): one uses the binary expansion of a real number between 0 and 1 to encode a subset of N (via: construct set S such that: if nth place in expansion =0, then n not in S; nth place in expansion =1, then n is in S.) However, this encoding actually only makes a correspondence between ordered subsets of N and [0,1). Since there are many elements in the set of ordered subsets of N for every element in P(N), this only proves that |P(N)| ≤ |R|. So, how does one then make the correspondence between the set of ordered subsets of N and P(N)?
    (The source cited above starts with the classical diagonal argument about |N|≤|R| before stating the above attempt at |P(N)| = |R|.)
    Thanks for any feedback.
     
  2. jcsd
  3. Mar 13, 2014 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The link you provided seems to make a bijection between ##\mathbb{R}## and ##\{0,1\}^\mathbb{N}## (= the set of all functions ##\mathbb{N}\rightarrow \mathbb{R}##, or equivalently, the set of all infinite binary sequences).

    You are correct that you still have to make a bijection between ##\mathcal{P}(\mathbb{N})## and ##\{0,1\}^\mathbb{N}##. The idea is to take an element
    [tex](x_1,x_2,x_3,x_4,...)\in \{0,1\}^\mathbb{N}[/tex]
    So we have a sequence of zeroes and ones. We now construct a subset ##A## of ##\mathbb{N}## using the rule that ##n\in A## if and only if ##x_n=1##.

    For example,
    [tex](1,1,0,0,0,0,0,0,...)[/tex]
    gives us ##\{1,2\}##. While
    [tex](1,0,1,0,1,0,1,0,1,0,....)[/tex]
    gives us the odd numbers.

    I leave it to you to verify this is a bijection.
     
  4. Mar 13, 2014 #3
    Thanks, micromass. Everything is clear now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Missing step in standard proof of |P(N)|=|R|
  1. Proof for n (Replies: 5)

Loading...