I am currently working through Abbott's analysis, and am asked to prove the following:

Denote the power set of $\mathbb{N}$ by $\mathcal{P}(\mathbb{N})$. Show that $\mathcal{P}(\mathbb{N})\sim\mathbb{R}$; that is, to show that there exists a bijection $F:\mathcal{P}(\mathbb{N})\rightarrow\mathbb{R}$.

I am quite sure that we have to use Schroder-Bernstein Theorem where we have to injections to show that there is a bijection, but I'm not sure how to find an injection in either direction.

  • 1
    $\begingroup$ The main idea is that it there is a straightforward bijection between $\mathcal{P}(\mathbb{N})$ and binary sequences: $f(S)_n=\begin{cases} 1 & n \in S \\ 0 & n \not \in S \end{cases}$. You then have to clean up the mapping between binary sequences and $\mathbb{R}$, which is always a little messy. $\endgroup$
    – Ian
    May 29, 2018 at 18:33
  • $\begingroup$ In the duplicate thread there is a comment that says that $\mathcal{P}(\mathbb{Q})$ maps bijectively into $\mathcal{P}(\mathbb{N})$. Why is this? $\endgroup$
    – 高田航
    May 29, 2018 at 18:35
  • 1
    $\begingroup$ Send each subset of $\mathbb{Q}$ to a subset of $\mathbb{N}$ by bijecting its elements with the corresponding elements of $\mathbb{N}$. $\endgroup$
    – Ian
    May 29, 2018 at 18:54


Browse other questions tagged .