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.(adsbygoogle = window.adsbygoogle || []).push({});

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]

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Bijection from N to Q

Loading...

Similar Threads - Bijection | Date |
---|---|

I Bijective function from naturals to primes | Aug 26, 2017 |

Constructive bijection between [0,1] and R? | Apr 30, 2015 |

(Terminology) bijective correspondence between proper classes? | Mar 10, 2014 |

Thoughts on this Inverse Bijection Proof | Jan 20, 2013 |

Discrete mathematics, bijections between disjoint unions | Oct 24, 2012 |

**Physics Forums - The Fusion of Science and Community**