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

1. Mar 13, 2014

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. Mar 13, 2014

### micromass

Staff Emeritus
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
$$(x_1,x_2,x_3,x_4,...)\in \{0,1\}^\mathbb{N}$$
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,
$$(1,1,0,0,0,0,0,0,...)$$
gives us $\{1,2\}$. While
$$(1,0,1,0,1,0,1,0,1,0,....)$$
gives us the odd numbers.

I leave it to you to verify this is a bijection.

3. Mar 13, 2014