Finding injection from $[0,1]$ to $P(\mathbb{N})$

Question

I'm using Schröder-Bernstein to prove that $\mathbb{R}$ is equinumerous to $P(\mathbb{N})$, the power set of the naturals. Part of my proof requires that I find an injection from $[0,1]$ (which is equinumerous with $\mathbb{R}$) to $P(\mathbb{N})$. I already found the reverse injection by encoding membership of $n$ as the $n$th bit in a binary sequence following the decimal point.

Hints appreciated!

Edit: Thanks for all the suggestions. For those interested, I concluded that the following would be the most accessible and elegant way for me to prove $[0,1]$ is equinumerous with $P(\mathbb{N})$.

Let $f: [0,1] \rightarrow P(\mathbb{N})$ be defined as follows. Each $c \in [0,1]$ can be written in binary uniquely as $a_1.a_2a_3...$ by choosing the canonical representation of nonterminating $0$s rather than nonterminating $1$s when there is a choice. Then $f(c) = \{k: a_k = 1\}$ gives an injection.

Let $g : P(\mathbb{N})\rightarrow [0,1]$ work as follows. For any $A \in P(\mathbb{N})$, $g(A)$ is the decimal, rather than binary, representation $0.a_1a_2\ldots$, where for each $k \in \mathbb{N}$, $a_k = 1$ if $k \in A$ and $0$ otherwise. Note that we ensure injectivity because, in decimal, a number of the form $0.a_1a_2\ldots$ will only have multiple representations if one of them has a nonterminating tail of $9s$.

By Schröder-Bernstein, we have $\mathbb{R}$ is equinumerous to $P(\mathbb{N})$.

Answer 1

An idea is to consider numbers in $[0,1]$ expanded in their binary representation $a_0.a_1a_2\dots$, where $a_n\in\{0,1\}$ and, for any $n>0$, there exists $m>n$ with $a_m=0$ (which excludes representations that are “eventually $1$”.

Each number in $[0,1]$ has exactly one representation of this type; for $x\in[0,1]$, call $x_n$ the $n$-th digit and define $$ f(x)=\{n\in\mathbb{N}:x_n=1\} $$ For instance $f(1)={0}$ and $f(0)=\emptyset$, whereas $f(1/2)=\{1\}$. If $x\ne y$, then $x_n\ne y_n$ for at least one $n$, so either $n\in f(x)$ and $n\notin f(y)$ or $n\notin f(x)$ and $n\in f(y)$. In particular, $f(x)\ne f(y)$.

For the converse injection, given $A\subseteq\mathbb{N}$, consider the binary alignment defined by $$ 0.a_10a_30a_50\dots $$ where $a_{2n+1}=1$ if $n\in A$ and $a_{2n+1}=0$ if $n\notin A$.

Different sets define different numbers in $[0,1]$; the inserted zeros in even positions ensure that no alignment is “eventually $1$”.

Answer 2

For each real number, choose a decimal representation $a=0.a_1a_2\dots$ in binary, and define $f:\mathbb{R}\to P(\mathbb{N})$ by noting that since $\mathbb{N}$ is equinumerous to $\mathbb{N}\times \{0, 1\}$, we have a bijection, $h:P(\mathbb{N}\times\{0, 1\})\to P(\mathbb{N})$, so we may define $g(a)=\{(i, a_i)|i\in\mathbb{N}\}$, and letting $f=hg$ we obtain the desired injection.

Answer 3

Define $f: [0, 1] \to P(\mathbb{N})$ to be $f(x) = \{ 2^i 3^{a_i} | i = 1, 2, \ldots \}$ where $a_i$ are the decimal expansion of $x = \sum_{i = 1}^\infty \frac{a_i}{10^i}$, $a_i \in \{0, 1, \ldots, 9\}$. Show that this is injection.

Answer 4

Your function $P(\mathbb N)\to[0,1]$ is not an injection. For example, $\{1\}$ and $\mathbb N\setminus \{1\}$ map to $0.1$ and $0.0111\dots$, which are the same number $1/2$.

In fact, if you use the same trick in the opposite direction then you do get an injection $[0,1]\to P(\mathbb N)$, encoding a real number as a set of natural numbers using some chosen 'canonical' binary expansion for each number. For example, given the choice, you could always choose the non-terminating binary expansion.

Therefore, the question you should be asking is: 'How do I find an injection from $P(\mathbb N)$ to $[0,1]$?' You will probably have to do this in a slightly clumsy way.

As an idea, let $P_{\inf}(\mathbb N)$ denote the set of infinite subsets of $\mathbb N$. These subsets correspond to non-terminating binary expansions, and this gives us an injection $P_{\inf}(\mathbb N)\to[0,1]$. Now there is an injection $[0,1]\to[0,1]$ sending $0.a_1a_2a_3\dots$ to $0.0a_10a_20a_3\dots$. Composing this with our injection gives us an injection $P_{\inf}(\mathbb N)\to[0,1]$ that is very far from being surjective, and now there are plenty of spare elements of $[0,1]$ that we can map the finite subsets of $P(\mathbb N)$, giving us an injection $P(\mathbb N)\to[0,1]$.

Answer 5

You can define an injection $g:\mathbb R\to P(\mathbb Q)$ by setting $g(x)=\{q\in\mathbb Q:q\lt x\}$ (the lower Dedekind cut). Now restrict $g$ to $[0,1]$ and compose it with a bijection from $P(\mathbb Q)$ to $P(\mathbb N)$ to get your injection $f:[0,1]\to P(\mathbb N).$

For the other direction, you can get an injection $h:P(\mathbb N)\to\mathbb R$ by simply defining $$h(S)=\sum_{n\in S}10^{-n}.$$