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

[nomadreid]

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.

 

[micromass]

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.

 

[nomadreid]

Thanks, micromass. Everything is clear now.