Understanding a proof that $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|$ I'm trying to understand a specific proof that $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|$. I'm paraphrasing it below. The proof relies on the Schroder-Bernstein theorem.

For each $A \subset \mathbb{N}$, we associate a real number $x_A$ in base $2$ by
$$
x_A = x_0. x_1 x_2 x_3 \ldots 
$$
where for every $n \in \mathbb{N}$, we let $x_n = 1$ if $n \in A$ and $0$ otherwise. As this $x_A$ is unique, this map from $\mathcal{P}(\mathbb{N})$ to $\mathbb{R}$ is unique. On the flip side, every real number is uniquely determined by the set
$$ 
A_x = \{y \in \mathbb{Q} : y < x\} \subset \mathbb{Q}. 
$$
So
$$
|\mathcal{P}(\mathbb{N})| \leq |\mathbb{R}| \leq |\mathcal{P}(\mathbb{Q})| = |\mathcal{P}(\mathbb{N})|.
$$

Here are the questions I have on this proof.

*

*Why is this base $2$ representation unique? If $A = \{0\}$, then $x_0 = 1$ and $x_n = 0$ for every $n \geq 1$. But in base $2$, $1.000 \ldots$ and $0.111 \ldots$ are the same number. I'm not fully sure I understand why it is helpful to use binary here or how to treat this issue where the binary expansion, defined as above, is not unique.


*I assume the set $A_x$ is a Dedekind cut associated to $x$. Is there another way to see that this set is unique other than by acknowledging the construction of the real line? For example, if $x$ and $y$ are real numbers with $A_x = A_y$, then
$$
\{a \in \mathbb{Q} \mid a < x\} = \{b \in \mathbb{Q} \mid b < y\}. 
$$
If $x \neq y$, then without loss of generality, $x > y$. Then I can find a rational $q$ such that $y < q < x$ by density. Then $q \in A_x$ but $q \not \in A_y$, which is a contradiction. Does this proof work?
 A: *

*You are correct that this runs into a standard technical problem of non-unique representation. An easy way to fix this is to take the digits two at a time; I would set $x_0=0$ always, and then let $x_{2k+1}x_{2k+2}$ be the sequence $01$ if $k\in A$, and let it be the sequence $10$ if $k\notin A$. This will guarantee the numbers you construct are all ones that have unique representation, giving you an embedding from $\mathcal{P}(A)$ to the interval $(0,1)$ (which we know can be bijected with $\mathbb{R}$). The spirit is the same, with the technical issue dealt with. When I do this is base 10, I let $x_k=5$ if $k\in A$, and $x_k=6$ if $k\notin A$, to make sure the number has a unique decimal expression.


*Whether $A_x$ "is" the Dedekind cut associated to $x$ depends on your precise definition of a Dedekind cut (sometimes that refers to the two sets, not just the left or right set), but essentially yes. Your argument to show that $x\neq y$ implies $A_x\neq A_y$ is correct; it does not require a "construction" of the reals per se, just the fact that rationals are dense in the reals: between any two distinct reals, there is always a rational.
A: *

*You are right, the map $A \in \mathcal P(\mathbb N) \mapsto x_A\in\mathbb R$ which they define is not injective, which is a flaw in the proof. To fix it, we could to the same in base $3$ and get an injective map (because a recurring last digit like $0,01111111\ldots = 0,020000\ldots$ gives a $2$ and does not collide with the image of another subset of $\mathbb N$)


*Yes, your proof is correct
A: Your function is surjective but not injective. To have an injective one, we could use the simple continued fraction representation of real numbers (but this one isn't surjective).
