[Math] Bijection from $\mathbb{R}$ to $\mathbb{R^2}$

set-theory

Importantly, I am looking for a constructive proof (which does not rely on the Cantor–Bernstein–Schroeder theorem). Motivated by this discussion.

Best Answer

Here is a bijection that uses the decimal (or binary, whatever) expansion of reals. (Even though I think the approach using continued fractions is more canonical.)

  • Let $\alpha:\mathbb Z\times \mathbb Z\to \mathbb Z$ and $\beta:[0,1)\times [0,1)\to [0,1)$ be bijections.
  • Let $f:\mathbb R \to \mathbb Z \times [0,1) $ be the natural bijection $x\mapsto (\lfloor x\rfloor, x-\lfloor x\rfloor)$.
  • Together, $f$, $\alpha$, $\beta$ will define bijections $$ \mathbb R\times \mathbb R \to^f (\mathbb Z\times [0,1)) \times (\mathbb Z\times [0,1)) \simeq \mathbb Z^2 \times [0,1)^2 \to ^{\alpha,\beta} \mathbb Z \times [0,1) \to^{f^{-1}}\mathbb R$$

The main part is of course the definition of $\beta$. [EDIT: This is not my construction; I am not sure where I first read it. In his book on the real numbers, Oliver Deiser gives a very similar construction (blocking zeroes instead of nines) and calls this Julius König's trick. König's wikipedia page mentions it but omits the details.]

Represent each real number $x\in [0,1)$ as a sequence of DIGITS, where each DIGIT is either in $\{0,\ldots,8\}$ or is of the form $10*(10^k-1)+i$ with $k\ge 1$ and $i\in \{0,\ldots,8\}$ (i.e., in $\{90,\ldots, 98; 990,\ldots, 998; 9990,\ldots, 9998; \ldots\}$.

For example, the number 0.0129449956$\dots$ would be represented by $(0,1,2,94,4,995,6,\ldots)$.

Given a pair $(x,y)$, $\beta$ interleaves these two representations.

Related Question