As part of a HW assignment in the course elementary set theory, I was given the following question:
Prove explicitly (don't use any theorems or known facts, but find a bijective function) that $\vert\mathbb R\vert=\vert \mathbb R\times \mathbb R\vert$
I've already encountered with the following suggestion:
for any $(x,y)\in \mathbb R$ with the decimal expansion $x=n_1+0.a_1 a_2 a_3 \ldots$
for some $n_1\in \mathbb Z$ and $0\leq a_i \leq 9$ and $y=n_2+0.b_1 b_2 b_3 \ldots$
for some $n_2\in \mathbb Z$ and $0\leq b_i \leq 9$.
if $x$ or $y$ have two different decimal expansions then take the one that ends with an infinite string of 9's.
then define $f : \mathbb R\times \mathbb R\longrightarrow \mathbb R$ by: $f((x,y))=n_1 +n_2 +0.a_1 b_1 a_2 b_2 a_3 b_3 \ldots$
$f$ is injective (I know that it is not accurate because I can choose $n_1$ and $n_2$ as I wish as long as their sum remains the same but the following was the more important part) but it is not onto $\mathbb R$ because for example: $0.12020202\ldots \in \mathbb R$ but there is no $(x,y)\in \mathbb R\times \mathbb R$ such that $f((x,y))=0.12020202\ldots$
because the only "candidates" are $x=0.10000\ldots$ and $y=0.2222\ldots$ but the number $0.10000\ldots $ does not belong to the representation that we agreed upon.
I feel that it can be fixed somehow but I can't manage to do it.
I would really appreciate if anyone can give me a bijective function that fits.
(also how can I fix $f$ to be injective).
Best Answer
Let's check that $\mathbb{R}\approx\mathbb{R^2}$. First, we have to prove the following
Lemma:$\;\;\mathbb{R}\approx^\mathbb{N}2$
Dem: we shall assume the following (minimal) result about the real numbers:
We shall prove that $(0,1)\preccurlyeq^\mathbb{N}2\,$ and $\,^\mathbb{N}2\preccurlyeq(0,1)$, to then apply the Cantor-Bernstein theorem
For each $x\in(0,1)$, let $(t_n)_{n\in\mathbb{N}}$ the unique sequence of zeroes and ones, that exists according to the previous result, in the case in which $b=2$, such that $\displaystyle x=\sum_{n\in\mathbb{N}}\frac{t_n}{2^{n+1}}$ and $(t_n)_{n\in\mathbb{N}}$ has infinite zeroes. The sequence $(t_n)_{n\in\mathbb{N}}$ is an element of the set of all the functions from $\mathbb{N}$ to $\{0,1\}$, that is, to $^\mathbb{N}2$, and from the uniqueness that is granted from the previous result we can conclude that the function from $(0,1)$ to $^\mathbb{N}2$ that for each $x$ assigns $(t_n)_{n\in\mathbb{N}}$ is injective.
To each sequence $(t_n)_{n\in\mathbb{N}}$ of zeroes and ones, we associate the real number $\displaystyle x=\sum_{n\in\mathbb{N}}\frac{t_n}{3^{n+1}}$, that is the real number $x\in[0,1)$ whose expression in base $3$ is $(t_n)_{n\in\mathbb{N}}$. Since we have that the sequence $(t_n)_{n\in\mathbb{N}}$ has no term equal to $2$, then there are infinite terms different from $2$, and the function is injective.
And since $(0,1)\approx\mathbb{R}$ (for example, via the bijective function $f(x)=\text{tan}\big(\frac{\pi}{2}(2x-1)\big)$), we conclude that $\mathbb{R}\approx^\mathbb{N}2$
Now, since $\mathbb{R}\approx^\mathbb{N}2$, we have that $\mathbb{R}^2=\mathbb{R}\times\mathbb{R}\approx^\mathbb{N}2\times^\mathbb{N}2$, and to demonstrate that $\mathbb{R}\approx\mathbb{R^2}$ its enough to give a bijection between $^\mathbb{N}2$ and $^\mathbb{N}2\times^\mathbb{N}2$.
Let $f:^\mathbb{N}2\times^\mathbb{N}2\longmapsto^\mathbb{N}2$ defined by: for each $f,g\in^\mathbb{N}2,\;F(\langle f,g\rangle)$ is the function $f*g$ from $\mathbb{N}$ to $2$, that assigns each natural number $n$ to:
$$(f*g)(n)=\begin{cases} \displaystyle f(k)\quad \text{if} n=2k \\ g(k)\quad \text{if} n=2k+1 \end{cases}$$
So that $f*g$ takes values $f(0),g(0),f(1),g(1),f(2),g(2),\dots$ and $f$ and $g$ can be recovered from $f*g$. The function $F$ is clearly bijective.