Mixing
Bijection from $mathbb R$ to $mathbb {R^N}$
$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.
real-analysis elementary-set-theory
edited Apr 13 '17 at 12:21
Community♦
1
asked Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
$endgroup$
|
show 5 more comments
$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.
real-analysis elementary-set-theory
edited Apr 13 '17 at 12:21
Community♦
1
asked Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
$endgroup$
$begingroup$
You can take any injections $f:mathbb R^{mathbb N}to mathbb R$ and $g:mathbb Rtomathbb 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 '12 at 9:49
1
$begingroup$
I'm really having a hard time believing such a bijection exists.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:50
$begingroup$
@Samuel now give me an injection $f: mathbb{R^N} rightarrow mathbb R$
$endgroup$
– fhyve
Nov 24 '12 at 9:53
6
$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 '12 at 9:57
$begingroup$
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.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:59
|
show 5 more comments
$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.
real-analysis elementary-set-theory
edited Apr 13 '17 at 12:21
Community♦
1
asked Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
$endgroup$
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.
real-analysis elementary-set-theory
real-analysis elementary-set-theory
edited Apr 13 '17 at 12:21
Community♦
1
asked Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
edited Apr 13 '17 at 12:21
Community♦
1
asked Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
edited Apr 13 '17 at 12:21
Community♦
1
edited Apr 13 '17 at 12:21
Community♦
1
edited Apr 13 '17 at 12:21
Community♦
1
1
asked Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
asked Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
asked Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
1,24511631
$begingroup$
You can take any injections $f:mathbb R^{mathbb N}to mathbb R$ and $g:mathbb Rtomathbb 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 '12 at 9:49
1
$begingroup$
I'm really having a hard time believing such a bijection exists.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:50
$begingroup$
@Samuel now give me an injection $f: mathbb{R^N} rightarrow mathbb R$
$endgroup$
– fhyve
Nov 24 '12 at 9:53
6
$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 '12 at 9:57
$begingroup$
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.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:59
|
show 5 more comments
$begingroup$
You can take any injections $f:mathbb R^{mathbb N}to mathbb R$ and $g:mathbb Rtomathbb 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 '12 at 9:49
1
$begingroup$
I'm really having a hard time believing such a bijection exists.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:50
$begingroup$
@Samuel now give me an injection $f: mathbb{R^N} rightarrow mathbb R$
$endgroup$
– fhyve
Nov 24 '12 at 9:53
6
$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 '12 at 9:57
$begingroup$
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.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:59
$begingroup$
You can take any injections $f:mathbb R^{mathbb N}to mathbb R$ and $g:mathbb Rtomathbb 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 '12 at 9:49
$begingroup$
You can take any injections $f:mathbb R^{mathbb N}to mathbb R$ and $g:mathbb Rtomathbb 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 '12 at 9:49
1
1
$begingroup$
I'm really having a hard time believing such a bijection exists.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:50
$begingroup$
I'm really having a hard time believing such a bijection exists.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:50
$begingroup$
@Samuel now give me an injection $f: mathbb{R^N} rightarrow mathbb R$
$endgroup$
– fhyve
Nov 24 '12 at 9:53
$begingroup$
@Samuel now give me an injection $f: mathbb{R^N} rightarrow mathbb R$
$endgroup$
– fhyve
Nov 24 '12 at 9:53
6
6
$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 '12 at 9:57
$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 '12 at 9:57
$begingroup$
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.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:59
$begingroup$
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.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:59
|
show 5 more comments
3 Answers
3
active
oldest
votes
$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)^Nsim N^{Ntimes 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}$.
- $mathbb{R^Nto (0,1)^N}$ by any bijection of this sort.
- $mathbb{(0,1)^Nto left((0,1)setminus Qright)^N}$ by the encoding given by $h$.
- $mathbb{left((0,1)setminus Qright)^Nto left(N^Nright)^N}$ by continued fractions.
- $mathbb{left(N^Nright)^Nto N^{Ntimes N}}$ by Currying.
- $mathbb{N^{Ntimes N}to N^N}$ by a pairing function.
- $mathbb{N^Nto (0,1)setminus Q}$ by decoding the continued fractions.
- $mathbb{(0,1)setminus Qto (0,1)}$ by the decoding of $h$, i.e. $h^{-1}$.
- $mathbb{(0,1)to R}$ by any bijection of this sort, e.g. the inverse of the bijection used for the first step.
answered Nov 24 '12 at 12:23
Asaf Karagila♦Asaf Karagila
303k32429760
$endgroup$
2
$begingroup$
Nice. One can do the same thing with $mathbb Rsim 2^{mathbb N}$, namely: $mathbb R^{mathbb N}to(2^{mathbb N})^{mathbb N}to 2^{mathbb Ntimes mathbb N}to 2^{mathbb N}to mathbb R$
$endgroup$
– Henning Makholm
Nov 24 '12 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 '12 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 '12 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$
– Henning Makholm
Nov 24 '12 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'sfuscfunction. See also the Cut-The-Knot page. But that's probably overkill :-)
$endgroup$
– commenter
Nov 24 '12 at 13:35
|
show 4 more comments
$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...).
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
$endgroup$
$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 '12 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 '12 at 8:44
$begingroup$
What about the co-domain?
$endgroup$
– Dan Brumleve
Nov 24 '12 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 '12 at 8:50
$begingroup$
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. :(
$endgroup$
– Dan Brumleve
Nov 24 '12 at 8:54
|
show 3 more comments
$begingroup$
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]$
answered Aug 14 '14 at 11:31
dragoboydragoboy
784517
$endgroup$
$begingroup$
Why is it enough? Because you can use induction to extend this? Induction will only give you a map from each $Bbb R^ntoBbb R$ which you can then combine to a map from $Bbb R^{<omega}toBbb R$. But induction does not stretch beyond the finite case, so you don't yet have a bijection from $Bbb{R^Nto R}$.
$endgroup$
– Asaf Karagila♦
Aug 14 '14 at 11:56
$begingroup$
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}}$
$endgroup$
– dragoboy
Aug 14 '14 at 11:59
$begingroup$
Delete your answer,it was misleading
$endgroup$
– Cloud JR
Sep 2 '18 at 14:01
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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)^Nsim N^{Ntimes 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}$.
- $mathbb{R^Nto (0,1)^N}$ by any bijection of this sort.
- $mathbb{(0,1)^Nto left((0,1)setminus Qright)^N}$ by the encoding given by $h$.
- $mathbb{left((0,1)setminus Qright)^Nto left(N^Nright)^N}$ by continued fractions.
- $mathbb{left(N^Nright)^Nto N^{Ntimes N}}$ by Currying.
- $mathbb{N^{Ntimes N}to N^N}$ by a pairing function.
- $mathbb{N^Nto (0,1)setminus Q}$ by decoding the continued fractions.
- $mathbb{(0,1)setminus Qto (0,1)}$ by the decoding of $h$, i.e. $h^{-1}$.
- $mathbb{(0,1)to R}$ by any bijection of this sort, e.g. the inverse of the bijection used for the first step.
answered Nov 24 '12 at 12:23
Asaf Karagila♦Asaf Karagila
303k32429760
$endgroup$
2
$begingroup$
Nice. One can do the same thing with $mathbb Rsim 2^{mathbb N}$, namely: $mathbb R^{mathbb N}to(2^{mathbb N})^{mathbb N}to 2^{mathbb Ntimes mathbb N}to 2^{mathbb N}to mathbb R$
$endgroup$
– Henning Makholm
Nov 24 '12 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 '12 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 '12 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$
– Henning Makholm
Nov 24 '12 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'sfuscfunction. See also the Cut-The-Knot page. But that's probably overkill :-)
$endgroup$
– commenter
Nov 24 '12 at 13:35
|
show 4 more comments
$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)^Nsim N^{Ntimes 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}$.
- $mathbb{R^Nto (0,1)^N}$ by any bijection of this sort.
- $mathbb{(0,1)^Nto left((0,1)setminus Qright)^N}$ by the encoding given by $h$.
- $mathbb{left((0,1)setminus Qright)^Nto left(N^Nright)^N}$ by continued fractions.
- $mathbb{left(N^Nright)^Nto N^{Ntimes N}}$ by Currying.
- $mathbb{N^{Ntimes N}to N^N}$ by a pairing function.
- $mathbb{N^Nto (0,1)setminus Q}$ by decoding the continued fractions.
- $mathbb{(0,1)setminus Qto (0,1)}$ by the decoding of $h$, i.e. $h^{-1}$.
- $mathbb{(0,1)to R}$ by any bijection of this sort, e.g. the inverse of the bijection used for the first step.
answered Nov 24 '12 at 12:23
Asaf Karagila♦Asaf Karagila
303k32429760
$endgroup$
2
$begingroup$
Nice. One can do the same thing with $mathbb Rsim 2^{mathbb N}$, namely: $mathbb R^{mathbb N}to(2^{mathbb N})^{mathbb N}to 2^{mathbb Ntimes mathbb N}to 2^{mathbb N}to mathbb R$
$endgroup$
– Henning Makholm
Nov 24 '12 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 '12 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 '12 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$
– Henning Makholm
Nov 24 '12 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'sfuscfunction. See also the Cut-The-Knot page. But that's probably overkill :-)
$endgroup$
– commenter
Nov 24 '12 at 13:35
|
show 4 more comments
$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)^Nsim N^{Ntimes 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}$.
- $mathbb{R^Nto (0,1)^N}$ by any bijection of this sort.
- $mathbb{(0,1)^Nto left((0,1)setminus Qright)^N}$ by the encoding given by $h$.
- $mathbb{left((0,1)setminus Qright)^Nto left(N^Nright)^N}$ by continued fractions.
- $mathbb{left(N^Nright)^Nto N^{Ntimes N}}$ by Currying.
- $mathbb{N^{Ntimes N}to N^N}$ by a pairing function.
- $mathbb{N^Nto (0,1)setminus Q}$ by decoding the continued fractions.
- $mathbb{(0,1)setminus Qto (0,1)}$ by the decoding of $h$, i.e. $h^{-1}$.
- $mathbb{(0,1)to R}$ by any bijection of this sort, e.g. the inverse of the bijection used for the first step.
answered Nov 24 '12 at 12:23
Asaf Karagila♦Asaf Karagila
303k32429760
$endgroup$
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)^Nsim N^{Ntimes 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}$.
- $mathbb{R^Nto (0,1)^N}$ by any bijection of this sort.
- $mathbb{(0,1)^Nto left((0,1)setminus Qright)^N}$ by the encoding given by $h$.
- $mathbb{left((0,1)setminus Qright)^Nto left(N^Nright)^N}$ by continued fractions.
- $mathbb{left(N^Nright)^Nto N^{Ntimes N}}$ by Currying.
- $mathbb{N^{Ntimes N}to N^N}$ by a pairing function.
- $mathbb{N^Nto (0,1)setminus Q}$ by decoding the continued fractions.
- $mathbb{(0,1)setminus Qto (0,1)}$ by the decoding of $h$, i.e. $h^{-1}$.
- $mathbb{(0,1)to R}$ by any bijection of this sort, e.g. the inverse of the bijection used for the first step.
answered Nov 24 '12 at 12:23
Asaf Karagila♦Asaf Karagila
303k32429760
edited Nov 24 '12 at 16:35
answered Nov 24 '12 at 12:23
Asaf Karagila♦Asaf Karagila
303k32429760
answered Nov 24 '12 at 12:23
Asaf Karagila♦Asaf Karagila
303k32429760
answered Nov 24 '12 at 12:23
Asaf Karagila♦Asaf Karagila
303k32429760
303k32429760
2
$begingroup$
Nice. One can do the same thing with $mathbb Rsim 2^{mathbb N}$, namely: $mathbb R^{mathbb N}to(2^{mathbb N})^{mathbb N}to 2^{mathbb Ntimes mathbb N}to 2^{mathbb N}to mathbb R$
$endgroup$
– Henning Makholm
Nov 24 '12 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 '12 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 '12 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$
– Henning Makholm
Nov 24 '12 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'sfuscfunction. See also the Cut-The-Knot page. But that's probably overkill :-)
$endgroup$
– commenter
Nov 24 '12 at 13:35
|
show 4 more comments
2
$begingroup$
Nice. One can do the same thing with $mathbb Rsim 2^{mathbb N}$, namely: $mathbb R^{mathbb N}to(2^{mathbb N})^{mathbb N}to 2^{mathbb Ntimes mathbb N}to 2^{mathbb N}to mathbb R$
$endgroup$
– Henning Makholm
Nov 24 '12 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 '12 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 '12 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$
– Henning Makholm
Nov 24 '12 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'sfuscfunction. See also the Cut-The-Knot page. But that's probably overkill :-)
$endgroup$
– commenter
Nov 24 '12 at 13:35
2
2
$begingroup$
Nice. One can do the same thing with $mathbb Rsim 2^{mathbb N}$, namely: $mathbb R^{mathbb N}to(2^{mathbb N})^{mathbb N}to 2^{mathbb Ntimes mathbb N}to 2^{mathbb N}to mathbb R$
$endgroup$
– Henning Makholm
Nov 24 '12 at 12:44
$begingroup$
Nice. One can do the same thing with $mathbb Rsim 2^{mathbb N}$, namely: $mathbb R^{mathbb N}to(2^{mathbb N})^{mathbb N}to 2^{mathbb Ntimes mathbb N}to 2^{mathbb N}to mathbb R$
$endgroup$
– Henning Makholm
Nov 24 '12 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 '12 at 12:47
$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 '12 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 '12 at 13:04
$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 '12 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$
– Henning Makholm
Nov 24 '12 at 13:17
$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$
– Henning Makholm
Nov 24 '12 at 13:17
1
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 '12 at 13:35
$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 '12 at 13:35
|
show 4 more comments
$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...).
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
$endgroup$
$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 '12 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 '12 at 8:44
$begingroup$
What about the co-domain?
$endgroup$
– Dan Brumleve
Nov 24 '12 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 '12 at 8:50
$begingroup$
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. :(
$endgroup$
– Dan Brumleve
Nov 24 '12 at 8:54
|
show 3 more comments
$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...).
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
$endgroup$
$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 '12 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 '12 at 8:44
$begingroup$
What about the co-domain?
$endgroup$
– Dan Brumleve
Nov 24 '12 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 '12 at 8:50
$begingroup$
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. :(
$endgroup$
– Dan Brumleve
Nov 24 '12 at 8:54
|
show 3 more comments
$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...).
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
$endgroup$
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...).
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
answered Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
answered Nov 24 '12 at 7:55
fhyvefhyve
1,24511631
1,24511631
$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 '12 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 '12 at 8:44
$begingroup$
What about the co-domain?
$endgroup$
– Dan Brumleve
Nov 24 '12 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 '12 at 8:50
$begingroup$
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. :(
$endgroup$
– Dan Brumleve
Nov 24 '12 at 8:54
|
show 3 more comments
$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 '12 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 '12 at 8:44
$begingroup$
What about the co-domain?
$endgroup$
– Dan Brumleve
Nov 24 '12 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 '12 at 8:50
$begingroup$
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. :(
$endgroup$
– Dan Brumleve
Nov 24 '12 at 8:54
$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 '12 at 8:38
$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 '12 at 8:38
1
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 '12 at 8:44
$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 '12 at 8:44
$begingroup$
What about the co-domain?
$endgroup$
– Dan Brumleve
Nov 24 '12 at 8:45
$begingroup$
What about the co-domain?
$endgroup$
– Dan Brumleve
Nov 24 '12 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 '12 at 8:50
$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 '12 at 8:50
$begingroup$
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. :(
$endgroup$
– Dan Brumleve
Nov 24 '12 at 8:54
$begingroup$
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. :(
$endgroup$
– Dan Brumleve
Nov 24 '12 at 8:54
|
show 3 more comments
$begingroup$
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]$
answered Aug 14 '14 at 11:31
dragoboydragoboy
784517
$endgroup$
$begingroup$
Why is it enough? Because you can use induction to extend this? Induction will only give you a map from each $Bbb R^ntoBbb R$ which you can then combine to a map from $Bbb R^{<omega}toBbb R$. But induction does not stretch beyond the finite case, so you don't yet have a bijection from $Bbb{R^Nto R}$.
$endgroup$
– Asaf Karagila♦
Aug 14 '14 at 11:56
$begingroup$
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}}$
$endgroup$
– dragoboy
Aug 14 '14 at 11:59
$begingroup$
Delete your answer,it was misleading
$endgroup$
– Cloud JR
Sep 2 '18 at 14:01
add a comment |
$begingroup$
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]$
answered Aug 14 '14 at 11:31
dragoboydragoboy
784517
$endgroup$
$begingroup$
Why is it enough? Because you can use induction to extend this? Induction will only give you a map from each $Bbb R^ntoBbb R$ which you can then combine to a map from $Bbb R^{<omega}toBbb R$. But induction does not stretch beyond the finite case, so you don't yet have a bijection from $Bbb{R^Nto R}$.
$endgroup$
– Asaf Karagila♦
Aug 14 '14 at 11:56
$begingroup$
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}}$
$endgroup$
– dragoboy
Aug 14 '14 at 11:59
$begingroup$
Delete your answer,it was misleading
$endgroup$
– Cloud JR
Sep 2 '18 at 14:01
add a comment |
$begingroup$
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]$
answered Aug 14 '14 at 11:31
dragoboydragoboy
784517
$endgroup$
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]$
answered Aug 14 '14 at 11:31
dragoboydragoboy
784517
answered Aug 14 '14 at 11:31
dragoboydragoboy
784517
answered Aug 14 '14 at 11:31
dragoboydragoboy
784517
answered Aug 14 '14 at 11:31
dragoboydragoboy
784517
784517
$begingroup$
Why is it enough? Because you can use induction to extend this? Induction will only give you a map from each $Bbb R^ntoBbb R$ which you can then combine to a map from $Bbb R^{<omega}toBbb R$. But induction does not stretch beyond the finite case, so you don't yet have a bijection from $Bbb{R^Nto R}$.
$endgroup$
– Asaf Karagila♦
Aug 14 '14 at 11:56
$begingroup$
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}}$
$endgroup$
– dragoboy
Aug 14 '14 at 11:59
$begingroup$
Delete your answer,it was misleading
$endgroup$
– Cloud JR
Sep 2 '18 at 14:01
add a comment |
$begingroup$
Why is it enough? Because you can use induction to extend this? Induction will only give you a map from each $Bbb R^ntoBbb R$ which you can then combine to a map from $Bbb R^{<omega}toBbb R$. But induction does not stretch beyond the finite case, so you don't yet have a bijection from $Bbb{R^Nto R}$.
$endgroup$
– Asaf Karagila♦
Aug 14 '14 at 11:56
$begingroup$
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}}$
$endgroup$
– dragoboy
Aug 14 '14 at 11:59
$begingroup$
Delete your answer,it was misleading
$endgroup$
– Cloud JR
Sep 2 '18 at 14:01
$begingroup$
Why is it enough? Because you can use induction to extend this? Induction will only give you a map from each $Bbb R^ntoBbb R$ which you can then combine to a map from $Bbb R^{<omega}toBbb R$. But induction does not stretch beyond the finite case, so you don't yet have a bijection from $Bbb{R^Nto R}$.
$endgroup$
– Asaf Karagila♦
Aug 14 '14 at 11:56
$begingroup$
Why is it enough? Because you can use induction to extend this? Induction will only give you a map from each $Bbb R^ntoBbb R$ which you can then combine to a map from $Bbb R^{<omega}toBbb R$. But induction does not stretch beyond the finite case, so you don't yet have a bijection from $Bbb{R^Nto R}$.
$endgroup$
– Asaf Karagila♦
Aug 14 '14 at 11:56
$begingroup$
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}}$
$endgroup$
– dragoboy
Aug 14 '14 at 11:59
$begingroup$
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}}$
$endgroup$
– dragoboy
Aug 14 '14 at 11:59
$begingroup$
Delete your answer,it was misleading
$endgroup$
– Cloud JR
Sep 2 '18 at 14:01
$begingroup$
Delete your answer,it was misleading
$endgroup$
– Cloud JR
Sep 2 '18 at 14:01
add a comment |
$begingroup$
You can take any injections $f:mathbb R^{mathbb N}to mathbb R$ and $g:mathbb Rtomathbb 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 '12 at 9:49
1
$begingroup$
I'm really having a hard time believing such a bijection exists.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:50
$begingroup$
@Samuel now give me an injection $f: mathbb{R^N} rightarrow mathbb R$
$endgroup$
– fhyve
Nov 24 '12 at 9:53
6
$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 '12 at 9:57
$begingroup$
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.
$endgroup$
– Patrick Da Silva
Nov 24 '12 at 9:59