46
$\begingroup$

How does one create an explicit bijection from the reals to the set of all sequences of reals? I know how to make a bijection from $\mathbb R$ to $\mathbb {R \times R}$.

I have an idea but I am not sure if it will work. I will post it as my own answer because I don't want to anchor your answers and I want to see what other possible ways of doing this are.

$\endgroup$
10
  • $\begingroup$ You can take any injections $f:\mathbb R^{\mathbb N}\to \mathbb R$ and $g:\mathbb R\to\mathbb R^{\mathbb N}$, and then get an explicit bijection from the proof of the Cantor-Schröder-Bernstein theorem (see Wikipedia). $\endgroup$
    – Samuel
    Nov 24, 2012 at 9:49
  • 2
    $\begingroup$ I'm really having a hard time believing such a bijection exists. $\endgroup$
    – Patrick Da Silva
    Nov 24, 2012 at 9:50
  • $\begingroup$ @Samuel now give me an injection $f: \mathbb{R^N} \rightarrow \mathbb R$ $\endgroup$
    – fhyve
    Nov 24, 2012 at 9:53
  • 8
    $\begingroup$ @PatrickDaSilva Since the sets have the same cardinality (according to wikipedia), there has to be some bijection. $\mathbb{R^N} \cong \mathbb{(2^N)^N} \cong \mathbb{2^{(N \times N)}} \cong \mathbb{2^N} \cong \mathbb{R}$ (I think) $\endgroup$
    – fhyve
    Nov 24, 2012 at 9:57
  • 1
    $\begingroup$ @fhyve: An injection from $(0,1)^{\mathbb N}\to [0,1]$ can be given using the digit interleaving trick. Map $(x_1,x_2,\ldots)$ to the real number which starts with the first digit of $x_1$, then the first two digits of $x_1$ and $x_2$, then the first three digits of $x_1$, $x_2$, $x_3$, and so on. $\endgroup$
    – Samuel
    Nov 24, 2012 at 10:05

2 Answers 2

Reset to default
48
$\begingroup$

The nicest trick in the book is to find a bijection between $\mathbb R$ and $\mathbb{N^N}$, in this case we are practically done. Why?

$$\mathbb{(N^N)^N\sim N^{N\times N}\sim N^N}$$

And the bijections above are easy to calculate (I will leave those to you, the first bijection is a simple Currying, and for the second you can use Cantor's pairing function).

So if we can find a nice bijection between the real numbers the infinite sequences of natural numbers we are about done. Now, we know that $\mathbb{N^N}$ can be identified with the real numbers, in fact continued fractions form a bijection between the irrationals and $\mathbb{N^N}$.

We first need to handle the rational numbers, but that much is not very difficult. Take an enumeration of the rationals (e.g. Calkin-Wilf tree) in $(0,1)$, suppose $q_i$ is the $i$-th rational in the enumeration; now we take a sequence of irrationals, e.g. $r_n = \frac1{\sqrt{n^2+1}}$, and we define the following function:

$$h(x)=\begin{cases} r_{2n} & \exists n: x=r_n\\ r_{2n+1} & \exists n: x=q_n \\ x &\text{otherwise}\end{cases}$$

Now we can finally describe a list of bijections which, when composed, give us a bijection between $\mathbb R$ and $\mathbb{R^N}$.

  1. $\mathbb{R^N\to (0,1)^N}$ by any bijection of this sort.
  2. $\mathbb{(0,1)^N\to \left((0,1)\setminus Q\right)^N}$ by the encoding given by $h$.
  3. $\mathbb{\left((0,1)\setminus Q\right)^N\to \left(N^N\right)^N}$ by continued fractions.
  4. $\mathbb{\left(N^N\right)^N\to N^{N\times N}}$ by Currying.
  5. $\mathbb{N^{N\times N}\to N^N}$ by a pairing function.
  6. $\mathbb{N^N\to (0,1)\setminus Q}$ by decoding the continued fractions.
  7. $\mathbb{(0,1)\setminus Q\to (0,1)}$ by the decoding of $h$, i.e. $h^{-1}$.
  8. $\mathbb{(0,1)\to R}$ by any bijection of this sort, e.g. the inverse of the bijection used for the first step.
$\endgroup$
9
  • 5
    $\begingroup$ Nice. One can do the same thing with $\mathbb R\sim 2^{\mathbb N}$, namely: $\mathbb R^{\mathbb N}\to(2^{\mathbb N})^{\mathbb N}\to 2^{\mathbb N\times \mathbb N}\to 2^{\mathbb N}\to \mathbb R$ $\endgroup$
    – hmakholm left over Monica
    Nov 24, 2012 at 12:44
  • $\begingroup$ @HenningMakholm: Yeah, that would work just fine as well. I just immediately thought about Baire space rather than Cantor space. Which is weird because the Cantor space has been a lot on my mind lately! $\endgroup$
    – Asaf Karagila ♦
    Nov 24, 2012 at 12:47
  • $\begingroup$ @Henning: Also, it's less trivial to just say what is the bijection between $\mathbb R$ and the Cantor space, while the Baire space has this very nice continued fractions to help. $\endgroup$
    – Asaf Karagila ♦
    Nov 24, 2012 at 13:04
  • $\begingroup$ @Asaf: Hmm, not sure. I think the amount of special pleading one needs in order to cater for terminating continued fractions is roughly the same as what one has to do to cater for binary fractions that end in repeating 1s. $\endgroup$
    – hmakholm left over Monica
    Nov 24, 2012 at 13:17
  • 1
    $\begingroup$ If you want to do it completely explicitly, you can use the Calkin-Wilf tree which gives you an explicit enumeration of the rational numbers in $(0,1)$ using Dijkstra's fusc function. See also the Cut-The-Knot page. But that's probably overkill :-) $\endgroup$
    – commenter
    Nov 24, 2012 at 13:35
3
$\begingroup$

NOTE: This doesn't work

First, map all the $\mathbb R$s to $(0,1)\backslash \mathbb Q$. Then, for each sequence of irrationals from 0 to 1, set it up in a grid with as such:

$$s_1 = 0.d_{11}d_{12}d_{13}d_{14}d_{15}... \\ s_2 = 0.d_{21}d_{22}d_{23}d_{24}d_{25}... \\ s_3 = 0.d_{31}d_{32}d_{33}d_{34}d_{35}... \\...$$

And take the new irrational number by taking each diagonal similarly to how you create a bijection from the rationals to the naturals. That is:

$$r = 0.d_{11} \; d_{21}d_{12}\; d_{31}d_{22}d_{13} \; d_{41}d_{32}d_{23}d_{14}...$$

Now, does this map to every irrational? Not sure. Does this map to any rationals, I am pretty sure not. If r was repeating, I think that that would make the top row repeating. Not sure how to prove this though.

Why this doesn't work: Consider $r= 0.101001000100001....$. This is irrational and is only mapped to by $s_1 = 0.111111$ and $s_n = 0.0000...$ for all other n (and 0 isn't even in our set to begin with...).

$\endgroup$
9
  • $\begingroup$ It isn't necessarily a bijection since it might map $x$ to $0.5000...$ and also map $y$ to $0.4999...$. $\endgroup$
    – Dan Brumleve
    Nov 24, 2012 at 8:38
  • 1
    $\begingroup$ In the first step I map to all irrationals so we don't have either 0.50000 or 0.4999 $\endgroup$
    – fhyve
    Nov 24, 2012 at 8:44
  • $\begingroup$ What about the co-domain? $\endgroup$
    – Dan Brumleve
    Nov 24, 2012 at 8:45
  • $\begingroup$ I guess I wasn't clear in that first line, but basically I want to map each R in the sequence and the R in the codomain both to the irrationals. Basically I would have $$\mathbb{R^N} \rightarrow ((0,1)\backslash \mathbb Q )^{\mathbb N} \rightarrow (0,1)\backslash \mathbb Q \rightarrow \mathbb R$$ All bijections $\endgroup$
    – fhyve
    Nov 24, 2012 at 8:50
  • 3
    $\begingroup$ If it doesn't work then u posted it? Lmao $\endgroup$
    – Cloud JR K
    Sep 1, 2019 at 17:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .