I am familiar with the proof that shows the powerset of the naturals is of the same cardinality as the reals using binary representation. Here's a quick rundown of the proof:
Showing that $f:(-1, 1) \rightarrow \mathbb R$ where $f(x) = \frac {x}{1-x^2}$ (or any other suitable function) is bijective.
Showing that there exists $g:(-1,1) \rightarrow (0,1)$ and $h:[0, 1] \rightarrow (0,1)$ such that g and h are bijective .
Establishing a bijection from $\mathcal P(\mathbb N)$ to $[0, 1]$. For $A \in \mathcal P(\mathbb N)$, $$f(A) = \sum_{a \in A} \frac{1}{2^a} $$ (or through the use of an indicator function) This function is supposed to be bijective. In every similar proof I have seen using this method, in the third step, they recognise that there are double representations for multiples of $\frac{1}{2^a}$ from the image in the pre-image thus making the function non-bijective. For example: $\frac{1}{2}$ has the representation: {1} and {2, 3, 4, 5, 6, 7,...} in the pre-image. Let's call the set of the second representations (the non-terminating ones for example), M.
They address this issue by separating this set from the powerset, noting that the set, M has the cardinality of the Naturals. They then say a bijection between $\mathcal P(\mathbb N)$/$M$ and [0, 1] is easy to see They then use the fact that if $|A| = |\mathbb R|$ and $|B| = |\mathbb N|$ then $|A \cup B| = |\mathbb R|$ to see that adding M back does not change the bijection. My problem is with the boldened statement. How can we be sure that we do not have another exception? The proof doesn't seem complete except the function is explicitly shown to be bijective.
I started by showing that f is surjective. I made use of a function, g, defining it recursively as follows:
$$A_1 = \begin{cases} {1}, \frac{1}{2^1} \le y < \frac{1}{2^0} \\ \emptyset, otherwise \end{cases}$$
and,
$$A_n = \begin{cases} A_{n-1} \cup \{ n \}, \frac{1}{2^n} \le y - \sum_{a \in A_{n-1}} \frac{1}{2^a} < \frac{1}{2^{n-1}} \\ A_{n-1}, otherwise \end{cases}$$
$g(y) = \lim_{n \to \infty} A_n$ Let A = g(y).
Next step I believe is to prove that $f(A) = y.$
Let m = sup($A_n$). By construction, m has to be less than or equal to n. $\forall \epsilon > 0$, by the Archimedean property, we can choose n s.t. $\frac{1}{2^m} < \epsilon$. Since $m \in A_m$,
$$\frac{1}{2^m} \le y - \sum_{a \in A_{m-1}} \frac{1}{2^a} < \frac{1}{2^{m-1}}$$
$$y - \sum_{a \in A_{m-1}} \frac{1}{2^a} < \frac{1}{2^{m-1}}$$
$$y - \sum_{a \in A_{m-1}} \frac{1}{2^a} - \frac{1}{2^m} < \frac{1}{2^{m-1}}-\frac{1}{2^m}$$
$$y - \sum_{a \in A_{m}} \frac{1}{2^a} < \frac{1}{2^{m}}$$
Because of the nestedness of the sets, $A_m = A_n$. If that were not the case, then there exists m < p < n s.t. p is in $A_n$ which is a contradiction. Therefore;
$$y - \sum_{a \in A_{n}} \frac{1}{2^a} < \frac{1}{2^{m}} < \epsilon$$
$$y - f(A_n) < \epsilon$$
Since y is always greater than $f(A_n)$,
$$| y - f(A_n) | < \epsilon$$ $$\lim_{n \to \infty} f(A_n) = y$$
Since $A$ is the limit of a monotonically increasing sequence of sets indexed by a subset of the naturals, thus making the limit a union also indexed by a subset of the naturals, we can bring the limit into the function. Thus;
$$\lim_{n \to \infty} f(A_n) = f(\lim_{n \to \infty} A_n) = y$$ $$\implies f(A) = y$$
So, $\forall y \in [0,1], \exists A,$ defined by g(y), $A \in$ $\mathcal P(\mathbb N)$/$M$ s.t. $f(A) = y$ proving that f is surjective.
Now, I have two questions:
- Is the proof adequate and complete? I am especially sceptical of the italicised paragraph I used to justify bringing the limit into the function. The actual statement was that the union of the function on sets is equivalent to the function of the union of sets provided the sets can be indexed by a subset of the naturals. I don't think it translates properly to our specific case but I cannot find a better justification. If I do (or I disprove the assertion), I will edit it out.
- How can I show that f is also injective? And is there an easier way to show that f is surjective?
I'm not completely sure I understand your question, but it seems your concern centres on the fact that if you define a function $f\colon \mathcal P(\mathbb N) \to [0,1]$ by $f(A) = \sum_{k} \chi_A(k)2^{-k}$ where $\chi_A$ is the characteristic function of $A$, then $f$ is not injective because, say $\{1\}$ and $\{n\geq 2\}$ both get mapped to $1/2$, thus one cannot immediately conclude that $\mathcal P(\mathbb N)$ and $[0,1]$ have the same cardinality.
The additional arguments needed to compensate for the failure of injectivity rely on the fact that if $S$ is infinite , then $S$ and $S\sqcup C$ have the same cardinality if $C$ is a finite or countable set: In the case of $f$ as defined above, the binary expansion is unique save for the "recurring $1$s" phenomenon, thus although $f$ is surjective, it fails to be injective. However, this only happens on subsets that are either finite or have finite complement. By standard arguments the set of finite subsets of $\mathbb N$ is countable (e.g. if $p_k$ is the $k$th prime then the map sending a finite set $A$ to $\prod_{k \in A} p_k$ gives a injective map from the set of finite subsets of $\mathbb N$ to $\mathbb N$) and hence the set consisting of all finite subsets and their complements is countable.
It follows that $f$ gives a bijection between $f_{|F^c}\colon \mathcal P(\mathbb N)\backslash F\to [0,1]\backslash f(F)$, hence these two sets have the same cardinality. Thus to produce a bijection between $\mathcal P(\mathbb N)$ and $[0,1]$ one can simply take bijections $a\colon \mathbb N \to F$ and $b\colon \mathbb N \to f(F)$ (note in this case both $F$ and $f(F)$ are infinite and hence countable) and then define $$ g\colon \mathcal P(\mathbb N) \to [0,1], \quad g(A) =\left\{\begin{array}{cc} f(A), & \text{if } A\notin F,\\ b\circ a^{-1}(A), & \text{if } A \in F \end{array}\right. $$ Alternatively, one can argue that if $E$ is an infinite set, then the cardinalities of $E$ and $E\backslash C$ where $C$ is a countable set are equal provided both $E$ and $E\backslash C$ are infinite. Indeed if $E\backslash C$ is infinite, there is an injective function $\iota \colon \mathbb N \to E\backslash C$. Moreover, since $C$ is countable, there is a bijection $a\colon \mathbb N \to C$. Then defining $\phi\colon E \to E\backslash C$ by $$ \phi(x)=\left\{ \begin{array}{cc} x, & \text{ if } x\notin \iota(\mathbb N) \cup E\\ \iota(2n+1) & \text{ if } x=\iota(n) \in \text{im}(\iota);\\ \iota(2n) & \text{ if } x=a(n) \in C. \end{array}\right. $$
It follows that establishing that the cardinalities of two sets $X$ and $Y$ are equal if there is a bijection between $X\backslash X_1$ and $Y\backslash Y_1$ where $X_1$ and $Y_1$ are subsets of $X$ and $Y$ respectively which are at most countable and their complements are also infinite.
Update: I asserted without proof that the map $f$ is surjective and that $f(A) = \sum_{k} \chi_A(k)2^{-k}$ has $f(A)=f(B)$ when $A\neq B$ only if $A$ and $B$ are either finite or have finite complement.
Claim 1: If $f(A)=f(B)$ and $A\neq B$ then either $A$ or $A^c$ is finite.
Proof: Indeed if $A$ is any set such that $A$ and $A^c$ are both infinite, then $\chi_A$ takes the values $1$ and $0$ infinitely often. We claim this implies that $f(A)=f(B)$ if and only if $B=A$. Indeed if $B \neq A$, then let $k= \min((A\cap B)^c \cap(A\cup B))$. Since $f(A^c) = 1-f(A)$ it follows that $f(A)=f(B)$ if and only if $f(A^c)=f(B^c)$, hence interchanging the pair $(A,B)$ with $(A^c,B^c)$ if necessary, we may assume that $k \in B\cap A^c$, so that $\chi_A(i)=\chi_B(i)$ for $1\leq i <k$ and $\chi_B(k)=1$, $\chi_A(k)=0$. Thus setting $q = \sum_{i=1}^{k-1} \chi_A(i)2^{-i}$ we have $$ f(B) = q+ 2^{-k} + \sum_{i=k+1}^\infty \chi_B(i)2^{-i}\geq q+2^{-k} $$ On the other hand, since $A^c$ is infinite, there is some $\ell>k$ such that $\ell \notin A$ since $A^c$ is not finite. Thus $$ \begin{split} f(A) &= q +\sum_{i=k+1}^{\ell-1}\chi_A(i)2^{-i} + \sum_{i\geq \ell+1} \chi_A(i)2^{-i} \leq q+\sum_{i=k+1}^{\ell-1} \chi_A(i)2^{-i} + 2^{-\ell} \\ &\leq q+ \sum_{i=k+1}^{\ell} 2^{-i}= q+2^{-k}-2^{-\ell} <q+2^{-k}. \end{split} $$ and so $f(A)<f(B)$. This suffices to show that the set $\{A \subseteq \mathbb N: \exists B, B\neq A, f(A)=f(B)\}\subseteq \{A\subseteq \mathbb N: |A|<\infty \text{ or } |A^c|<\infty\}$ and hence $f$ is injective outside of a countable set. With a bit more care it follows that $f(A)=f(B)$ if and only if this occurs because of recurring $1$s, but that is not necessary for the proof that $\mathcal P(\mathbb N)$ and $[0,1]$ have the same cardinality.
Claim 2: $f$ is surjective.
Proof: To see that $f$ is surjective, one just needs to know that any $x \in [0,1]$ is the limit of a series of the form $\sum_{i=1}^\infty a_i.2^{-i}$. For this, set $a_0=0$ and by induction assume that $a_0,\ldots,a_k\in \{0,1\}$ have been obtained such that $0\leq x-\sum_{i=0}^{k}a_i 2^{-i}<2^{-k}$. Then let $a_{k+1} = 1$ if $x-\sum_{i=0}^{k}a_i 2^{-i} \geq 2^{-(k+1)}$ and $0$ otherwise, so that clearly $x-\sum_{i=0}^{k+1}a_i 2^{-i}<2^{-(k+1)}$. Now since $s_N=\sum_{i=1}^N a_i.2^{-i} \leq \sum_{i=1}^N 2^{-i} = 1-2^{-N-1}\leq 1$, the partial sums $(s_N)$ of the series are (weakly) increasing and bounded above, hence they converge (to their supremum). But then since $0<x-s_n<2^{-n}\to 0 $ as $n\to \infty$ it follows $s_n\to x$ as required.
[Note that the binary expansion one obtains using the procedure described above, because it demands that $0<x-s_n<2^{-n}$ will yield the expansion which will use only recurring $0$s.]