Explicit bijection between the set of binary sequences and $\mathbb{R}$? I know there is a standard proof (Cantor’s diagonalization argument) to show that the set of infinite binary sequences, call it $\Omega := \{0,1\}^\mathbb{N}$, is uncountable.
However, I would like to describe an explicit bijection between $\mathbb{R}$ and $\Omega$ to show that they are equipotent. Is there a direct way to do this? Or is my best bet to find a bijection between $\Omega$ and $(0,1)$ (or something) and compose it with a bijection from $(0,1)$ to $\mathbb{R}$?
On that note, is there a "standard" bijection between $\Omega$ and $(0,1)$?
Many thanks.
 A: There's not really a 'standard' one but here's a simple construction (from $\Omega$ to $(0,1)$; bijecting $(0,1)$ and $\mathbb{R}$ is easy as you can just take something continuous like $f(x) = \frac{2x-1}{x(1-x)}$):
Let $A$ be the set of dyadic rational numbers in $(0,1)$, and let $B$ be the set of binary sequences that have only finitely many $0$'s or have only finitely many $1$'s. The binary expansion gives a bijection from $\Omega\setminus B$ to $(0,1)\setminus A$. Both $A$ and $B$ are countable so it should be straightforward to define a bijection between them, for example, we can enumerate them in parallel like so
\begin{eqnarray}
n &\hspace{25pt} A \hspace{25pt}& B\\
1 & \frac12& 1\color{gray}{00000...}\\
2 & \frac14& 0\color{gray}{11111...}\\
3 & \frac34& 01\color{gray}{0000...}\\
4 & \frac18& 10\color{gray}{1111...}\\
5 & \frac38& 11\color{gray}{0000...}\\
6 & \frac58& 00\color{gray}{1111...}\\
7 & \frac78& 001\color{gray}{000...}\\
8 & \frac1{16}& 110\color{gray}{111...}\\
9 & \frac3{16}& 011\color{gray}{000...}\\
10& \frac5{16}& 100\color{gray}{111...}\\
11&\frac{7}{16}& 101\color{gray}{000...}\\
12&\frac{9}{16}& 010\color{gray}{111...}\\
13&\frac{11}{16}& 111\color{gray}{000...}\\
14&\frac{13}{16}& 000\color{gray}{111...}\\
\vdots&\vdots&\vdots
\end{eqnarray}
Hopefully the pattern is clear at this point.
A: The Cantor-Bernstein Theorem (aka Cantor-Schröder-Bernstein Theorem and Schröder-Bernstein Theorem) provides a "sort of" constructive proof that given injections $f\colon A\to B$ and $g\colon B\to A$, there exists a bijection $h\colon A\to B$. It's "sort of" constructive because it requires you to know whether a given element can be traced back "infinitely", and that may not be immediately apparent.
So my answer would involve several steps.
First, there is a standard bijection from $(0,1)$ to $\mathbb{R}$; there are several ways of doing so: one is given by Dark Malthorp. I usually like to take the bijection between $(-\frac{\pi}{2},\frac{\pi}{2})$ and $\mathbb{R}$ given by $\arctan(x)$, and of course the interval $(0,1)$ can be bijection with $(-\frac{\pi}{2},\frac{\pi}{2})$ given by $f(t) = -\frac{\pi}{2}+t\pi$.
Now, we can embedd $(0,1)$ into the set of binary sequences using the base-2 expansion, with the convention that for numbers with two expansions, we always pick the one with a tail of $1$s (you can pick whichever you want). So $\frac{1}{2}$ is $0.011111\ldots$, rather than $0.1$. Then $g\colon (0,1)\to 2^{\omega}$ is given by letting $g(t)(n)$ be the $n$th digit in the expansion.
And we can embedd $f\colon 2^{\omega}\to (0,1)$ as follows: given a sequence $(a_n)$ of $0$s and $1$s, we let $f((a_n))$ be
$$\frac{1}{10} + \sum_{n=0}^{\infty}\frac{5+a_n}{10^{n+2}}.$$
That is: the decimal expansion of the number $f((a_n))$ has a $5$ in position $n+1$ after the decimal digit if $a_n$ is $0$, and has $6$ in that position if $a_n=1$. And it has a $1$ in the first position after the decimal point. The latter is to ensure we are in $(0,1)$ even if we take the sequence of zeros. And I use $5$ and $6$ to avoid the problem of multiple expansions for the same number.
Then we use Cantor-Bernstein to construct a bijection $h\colon 2^{\omega}\to(0,1)$ using $f$ and $g$. The construction runs as follows:
We say an element $(a_n)$ of $2^{\omega}$ has a "parent" if there exists $x\in(0,1)$ such that $g(x)=(a_n)$. Similarly, an element $t\in (0,1)$ has a "parent" if there exists $(b_n)\in 2^{\omega}$ such that $f((b_n))=t$.
Given an element $(a_n)\in 2^{\omega}$, we have two possibilities: either we can use the "parent" relation to bounce back and forth between $(0,1)$ and $2^{\omega}$ infinitely many times, or else there comes a point where the process stops (by reaching either a $t\in (0,1)$ that is not in the image of $f$, or a $(b_n)$ in $2^{\omega}$ that is not in the image of $g$).
We can partition $2^{\omega}$ into three sets: $A_1$, the elements where the process stops in an element of $2^{\omega}$; $A_2$, the elements where the process stops in an element of $(0,1)$; and $A_{\infty}$, the elements where the process continues indefinitely without stopping.
Similarly, we can partition $(0,1)$ into three sets: $B_1$, the elements where the process stops in an element of $2^{\omega}$; $B_2$, the elements where the process stops in an element of $(0,1)$; and $B_{\infty}$, the elements where the process continues indefinitely without stopping.
Now, if $(a_n)\in A_1$, then $f((a_n))\in B_1$; if $(a_n)\in A_2$, then there exists a unique $t\in B_2$ such that $g(t)=(a_n)$; if $(a_n)\in A_{\infty}$, then $f((a_n))\in B_{\infty}$. Moreover, every element in $B_1$ is the image of someone in $A_1$; every element in $B_{\infty}$ is the image of someone in $A_{\infty}$. Thus, we define $h\colon 2^{\omega}\to(0,1)$ by
$$h((a_n)) = \left\{\begin{array}{lll}
f(a_n)&\quad&\text{if }(a_n)\in A_1;\\
g^{-1}(a_n)&&\text{if }(a_n)\in A_2;\\
f(a_n)&&\text{if }(a_n)\in A_{\infty}.
\end{array}\right.$$
So, composing $h$ with the bijection of $(0,1)$ to $(-\frac{\pi}{2},\frac{\pi}{2})$, and then using $\arctan(x)$ to biject with $\mathbb{R}$ would give you an "explicit} bijection between $2^{\omega}$ and $\mathbb{R}$.
To be honest, one almost never actually does this. Instead, we rely on knowing that such bijections exist. So I would usually explicitly use $\arctan(x)$ to see $\mathbb{R}$ and $(-\frac{\pi}{2},\frac{\pi}{2})$ can be bijected. Then have a general result about how any two finite open intervals can be bijected (to biject $(a,b)$ and $(c,d)$, use $g(t) = c + \left(\frac{t-a}{b-a}\right)(d-c)$). Then define the two injections above, and invoke Cantor-Schröder-Bernstein.
