29
$\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.

  • 0
    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).2012-11-24
  • 1
    I'm really having a hard time believing such a bijection exists.2012-11-24
  • 0
    @Samuel now give me an injection $f: \mathbb{R^N} \rightarrow \mathbb R$2012-11-24
  • 6
    @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)2012-11-24
  • 0
    So perhaps I am wrong when I say $x < y$ implies $x^k < y^k$? Hm. Yes, I am definitely wrong ; I just tried with $x = 2$ and $y = 3$. Facepalm. I'll delete my answer.2012-11-24
  • 0
    @fhyve : The fact that you needed so many $\cong$'s suggests that composing the bijections given at each step will give you a very ugly map.2012-11-24
  • 0
    @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.2012-11-24
  • 0
    @Samuel Isn't that basically what I tried in my answer?2012-11-24
  • 0
    It's similar. I only create an injection though, not a bijection. Note that my function is an injection because it can't map to something with an infinite tail of $9$s as long as we agree not to write any of the $x_i$s with an infinite tail of $9$s.2012-11-24
  • 0
    @fhyve: Your comment gives a perfectly good explicit bijection. Just write down a bijection for each step and compose them.2012-11-24

2 Answers 2

28

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.
  • 2
    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$2012-11-24
  • 0
    @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!2012-11-24
  • 0
    @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.2012-11-24
  • 0
    @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.2012-11-24
  • 0
    @commenter: Hmm, yes I see your point. I'll make an adjustment.2012-11-24
  • 1
    If you want to do it completely explicitly, you can use the [Calkin-Wilf tree](http://en.wikipedia.org/wiki/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](http://www.cut-the-knot.org/blue/Fusc.shtml). But that's probably overkill :-)2012-11-24
  • 0
    @commenter: I don't suppose you know a nice encoding of $2\times\mathbb{N^N}$ into $\mathbb{N^N}$, then? (All these years of shrugging this aside are taking their toll... :-)) **Edit:** Right, silly me, even and odds. :-)2012-11-24
  • 0
    Ugh. This is taking too long, and I had to go 20 minutes ago. I'll finish this when I return.2012-11-24
  • 0
    @commenter: Now it works just fine.2012-11-24
6

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...).

  • 0
    It isn't necessarily a bijection since it might map $x$ to $0.5000...$ and also map $y$ to $0.4999...$.2012-11-24
  • 1
    In the first step I map to all irrationals so we don't have either 0.50000 or 0.49992012-11-24
  • 0
    What about the co-domain?2012-11-24
  • 0
    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 bijections2012-11-24
  • 0
    I see, but I don't understand how this construction avoids rational values. Also there is the issue of making the bijection between $(0,1) \setminus \mathbb{Q}$ and $\mathbb{R}$ explicit. Sorry to be so critical instead of constructive but I don't know how to do it myself. :(2012-11-24
  • 0
    $(0,1)\backslash \mathbb Q$ is the set of irrationals, ie, the set of all real numbers that don't have a repeating decimal expansion. The bijection from $(0,1)\backslash \mathbb Q$ to $(0,1)$ is simply taking any sequence $\{s_n\}$ in $(0,1)\backslash \mathbb Q$ and mapping all $s_n$ with odd n to an enumeration of the rationals $q_n$ and all the $s_n$ with even n to all $s_n$. Then you map (0,1) to R by $(1-2x)/x(x-1)$ It is discussed in that first link: http://math.stackexchange.com/questions/220640/constructing-a-bijection-from-0-1-to-the-irrationals-in-0-12012-11-24
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6501/discussion-between-dan-brumleve-and-fhyve)2012-11-24
  • 0
    Actually, the argument is valid. Just map $\Bbb R$ to $(0,1)$, never mind the rationals. Then build your lists of *binary* digits, with the convention that when you have the choice, you write an infinity of successive "1" (to avoid such cases as 0.1=.0111...). Now, the resulting "merged" number has an infinity of successive "1" iff the original are all so. Thus you won't omit any number.2013-12-19