A Bijection from N to Q: Explicit Formula for Rational Numbers

[phoenixthoth]

I am bored and feel like doing something useless today so I'm going to try to give an explicit formula that maps N to Q that is a one-to-one correspondence. If you want to waste some time, too, then feel free to post your functions or ideas towards that goal.

Something that might be very useful is a formula I found a while back for this integer sequence (a Smarandache crescendo sequence):
S={1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, ...} .
Right now, I'm thinking this formula could be used to specify the denominators of the rational numbers mapped to by the desired function. This would give us the positive rationals and then compose it with another function that will give us all rationals, not forgetting zero of course.

Of course, redundancy (like 1/1=2/2=3/3...) will have to be dealt with to ensure that the result is one-to-one.

I'll give a formula that maps N to S (where N starts at 1 in this case):
[tex]a_{n}=\frac{1}{2}\left( 2n+\left[ \sqrt{2n}\right] -\left[ \sqrt{2n}\right]
^{2}\right) [/tex]
where [x] is the closest integer to x.

I haven't proved that this formula works for all n yet but I'm fairly sure it does. I (meaning Mathematica) have checked for the first 400,000 natural numbers that
[tex]a_{n}>1\rightarrow a_{n}=a_{n-1}+1[/tex]
where the arrow is logical implication,
and that
[tex]a_{r\left( n\right) }=1[/tex] where [tex]r\left( n\right) =\frac{1}{2}\left( n^{2}-n+2\right) [/tex].
Incidentally, for all n>1,
[tex]a_{r\left( n\right) -1}=n-1[/tex]

 

[Kummer]

Preform the following steps to show:
[tex]|\mathbb{Q}^+ | = |\mathbb{N}|[/tex].

Any element in Q can be written in reduced form as m/n.

Now we exploit the fundmental theorem of arithmetic.

Either:
a)m=1 or [tex]m = p_1^{a_1} ... p_k^{a_k}[/tex].
b)n=1 or [tex]n=q_1^{b_1}... q_s^{a_s}[/tex].

Define [tex]f:\mathbb{Q}^+ \mapsto \mathbb{N}[/tex] as follows:
1)f(1) = 1
2)[tex]f(m/n) = p_1^{2a_1}...p_k^{2a_k}[/tex] if n=1 and m!=1
3)[tex]f(m/n) = q_1^{2b_1-1}...q_s^{2a_s-1}[/tex] if n!=1 and m=1
4)[tex]f(m/n) = p_1^{2a_1}...p_k^{2a_k}q_1^{2b_1-1}...q_s^{2a_s-1}[/tex] if n!=1 and m!=1

Now show that f is a bijection.

 

[phoenixthoth]

As I said initially,

I'm going to try to give an explicit formula that maps N to Q.

So your map might be helpful if you can exhibit its inverse.

 

[phoenixthoth]

I think I found a map from N onto Q which satisfies me enough for now...It's pretty obvious that |N| <= |Q| via the identity map and the interesting thing would be that |N| >= |Q| via the exhibition of a map from N onto Q.

First some definitions ([x] still means the integer closest to x...the case
where x=z+1/2 for a whole number z doesn't occur in the formulas below):

[tex]s\left( n\right) =\frac{1}{2}\left( 2n+\left[ \sqrt{2n}\right] -\left[
\sqrt{2n}\right] ^{2}\right) [/tex]

[tex]t\left( n\right) =\frac{1}{2}\left( 2-2n+\left[ \sqrt{2n}\right] +\left[
\sqrt{2n}\right] ^{2}\right) [/tex]

[tex]f\left( n\right) =\frac{s\left( n\right) }{t\left( n\right) }[/tex]

The outputs of s start with 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, ...
and the outputs of t start with
1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1,... .

The intuition behind this whole idea is the array that is often used to
visualize the bijection between N and Q+; you have in the ith row and jth
column the rational number i/j and then "count" the array by going
diagonally: (1,1)-->1, (1,2)-->2, (2,1)-->3, (1,3)-->4, (2,2)-->5, (3,1)-->6, etc. Note that the pattern is ( s(n) , t(n) ) --> n.

This f seems very likely to map N onto Q+ but is definitely not injective.
To show that it is onto, first define a function from NxN to N:
[tex]I\left( p,q\right) =\frac{1}{2}\left( p^{2}+q^{2}+2pg-p-3q+2\right) [/tex]

I've checked for p and q up to 200 (40,000 cases) that
[tex]f\left( I\left( p,q\right) \right) =p/q[/tex]

though it will take some more work to show that this is always true. If it
is true, then the element mapped to p/q in Q+ is I(p,q).

The next idea is to map N onto the set of nonnegative rationals via g where
g(1)=0 and g(n)=f(n-1) for n>1.

Finally, N will be mapped to Q via h where
[tex]h\left( n\right) =\left( -1\right) ^{n}g\left( \left\lfloor
n/2\right\rfloor +1\right) [/tex]

where [tex]\left\lfloor x\right\rfloor [/tex] is the greatest integer less than or
equal to x. Thus the outputs of h look like this:
-g(1), g(2), -g(2), g(3), -g(3), ... which is the same as
0, f(1), -f(1), f(2), -f(2), ... .

Now if for some reason you just want to have s and t in the answer, then
here is (very likely to be) an onto map from N to Q:
[tex]1\mapsto 0[/tex] and for n>1,

[tex]n\mapsto \left( -1\right) ^{n}\frac{s\left( \left\lfloor n/2\right\rfloor
\right) }{t\left( \left\lfloor n/2\right\rfloor \right) }[/tex] so in other words
for n>1, n gets mapped to

[tex]\left( -1\right) ^{n}\frac{2\left\lfloor n/2\right\rfloor +\left[ \sqrt{
2\left\lfloor n/2\right\rfloor }\right] -\left[ \sqrt{2\left\lfloor
n/2\right\rfloor }\right] ^{2}}{2-2\left\lfloor n/2\right\rfloor +\left[
\sqrt{2\left\lfloor n/2\right\rfloor }\right] +\left[ \sqrt{2\left\lfloor
n/2\right\rfloor }\right] ^{2}}[/tex]

This last map seems to have an interesting graph. I'll give some sketches for some domains of increasing magnitude:
http://img267.imageshack.us/img267/885/index51wy2.gif
http://img411.imageshack.us/img411/5536/index53fp3.gif
http://img267.imageshack.us/img267/8630/index55hh2.gif
http://img528.imageshack.us/img528/7324/index57dw7.gif


Now the same graphs but all cropped to a range of [-7,7]:
http://img517.imageshack.us/img517/1176/index64ap2.gif
http://img517.imageshack.us/img517/6554/index66cy5.gif
http://img267.imageshack.us/img267/1227/index68rt8.gif
http://img517.imageshack.us/img517/7633/index70gv4.gif
It seems like some kind of fractal...

 

[phoenixthoth]

I believe I have a function from N onto Z^2... Z^2 has obvious connections to Q.

This is how it looks
And the formulas along with the mathematica code I used is .[/URL]

 

[phoenixthoth]

I found some simpler formulas as well as a "many-valued" inverse.

http://www.alphaomegadimension.info/media/N_onto_Q.pdf

In this animation, the point (x,y) is identified with the rational number x/y; the map is onto but not even close to 1-1.

Yeah, so the title of this thread is a misnomer...these are not bijections, just surjections.