Prove that $ | \mathcal {P} (\mathbb N) | \le | \mathbb R | $.

Question

Define $\Phi: \mathcal {P} (\mathbb N) \to \mathbb R$ by

$$ \Phi (S) = \sum_ {k \in S} 10 ^ {- k}. $$

How to prove that $\Phi$ is injective?

I assumed that $\Phi(S) = \sum_ {k \in S} 10 ^ {-k} = \sum_ {k \in S'} 10 ^ {- k} = \Phi(S')$ and tried deriving that $S = S'$, but could not make this approach work.

Answer 1

For every $S \in \mathcal{P}(\mathbb{N})$, $\Phi(S)$ has a unique decimal representation consisting of $0$s and $1$s.

Suppose $k \in S$ and $k \notin S'$. Then $\Phi(S)$ has a $1$ at the $k$th position to the right of the decimal point while $\Phi(S')$ has a $0$. Therefore, $\Phi(S) \ne \Phi(S')$.

Similarly if $k \in S'$ and $k \notin S$.

We conclude that $\Phi$ is injective.

Answer 2

If the two sets differ, then they differ at a least element $n$.

Suppose $n$ is in $S$ but not in $S'$. Then $\Phi(S) - \Phi(S') = 10^{-n} - (\sum_ {n < k \in S'} 10 ^ {- k} - \sum_ {n < k \in S} 10 ^ {- k})$.

Can you bound $\sum_ {n < k \in S'} 10 ^ {- k} - \sum_ {n < k \in S} 10 ^ {- k}$ and show that it is less than $10^{-n}$? This proves that the two outputs are different.