Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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). –  Samuel Nov 24 '12 at 9:49
    
I'm really having a hard time believing such a bijection exists. –  Patrick Da Silva Nov 24 '12 at 9:50
    
@Samuel now give me an injection $f: \mathbb{R^N} \rightarrow \mathbb R$ –  fhyve Nov 24 '12 at 9:53
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) –  fhyve Nov 24 '12 at 9:57
    
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. –  Patrick Da Silva Nov 24 '12 at 9:59

3 Answers 3

up vote 9 down vote accepted

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.
share|improve this answer
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$ –  Henning Makholm Nov 24 '12 at 12:44
    
@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! –  Asaf Karagila Nov 24 '12 at 12:47
    
@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. –  Asaf Karagila Nov 24 '12 at 13:04
    
@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. –  Henning Makholm Nov 24 '12 at 13:17
1  
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 :-) –  commenter Nov 24 '12 at 13:35

Its enough to setting up injection $\mathbb{R}^2 \to \mathbb{R}$. Rest other job will be done by inclusion map and Cantor Berstein Schoredor Theorem. Also since $(0,1)$ is homeomorphic to $\mathbb{R}$ its just enough to show injection $(0,1)^2 \to (0,1)$. Now every number except of form $\frac{m}{2^n}$ has a unique binary representation since those can't be represented in finite way. Now let some $x=\frac{n}{2^m}$ in decimal is of form $x=.a_1a_2....a_n000000......$. And so its binary expansion ends only with zeroes. Now consider binary expansion of $x=.a_1a_2...(a_n-1)99999.....$ it never ends in only zeroes. Now following this method send some $(x,y)\in (0,1)^2 \to [x,y]\in (0,1)$ as follows. First change binary expansion of both $x,y$ into the expansion which never ends in zeroes (if it needs). Now if $x=.x_1x_2......,y=.y_2y_2.....$ then define $[x,y]=.x_1y_1x_2y_2.....$. First of all $[x,y]$ is unique since as per sending $[x,y]$ is never of from $\frac{n}{2^m}$, and uniqueness proves well defindness and injection of $f$ which sends $(x,y) \to [x,y]$

share|improve this answer
    
Why is it enough? Because you can use induction to extend this? Induction will only give you a map from each $\Bbb R^n\to\Bbb R$ which you can then combine to a map from $\Bbb R^{<\omega}\to\Bbb R$. But induction does not stretch beyond the finite case, so you don't yet have a bijection from $\Bbb{R^N\to R}$. –  Asaf Karagila Aug 14 at 11:56
    
Ohh I didn't notice the actual problem, I thought it was $\mathbb{R}^{N}\to \mathbb{R}$ for some finite $N$, ok lets see if I can extend for $\mathbb{R}^{\mathbb{N}}$ –  dragoboy Aug 14 at 11:59

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

share|improve this answer
    
It isn't necessarily a bijection since it might map $x$ to $0.5000...$ and also map $y$ to $0.4999...$. –  Dan Brumleve Nov 24 '12 at 8:38
1  
In the first step I map to all irrationals so we don't have either 0.50000 or 0.4999 –  fhyve Nov 24 '12 at 8:44
    
What about the co-domain? –  Dan Brumleve Nov 24 '12 at 8:45
    
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 –  fhyve Nov 24 '12 at 8:50
    
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. :( –  Dan Brumleve Nov 24 '12 at 8:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.