# Produce an explicit bijection between rationals and naturals?

I remember my professor in college challenging me with this question, which I failed to answer satisfactorily: I know there exists a bijection between the rational numbers and the natural numbers, but can anyone produce an explicit formula for such a bijection?

-
Do you need a formula or does the picture and explanation in en.wikipedia.org/wiki/… suffice? See also en.wikipedia.org/wiki/… – lhf Oct 24 '10 at 3:10
I wasn't familiar with pairing functions, so let me look at that more closely. My professor insisted, though, that I come up with a formula, and of course that would also require that equivalent pairs (in the rational number sense) shouldn't get counted more than once. – Alex Basson Oct 24 '10 at 4:55
@lhf. Maybe you should post your comment as an answer; otherwise, it's not unlikey that this question remains unanswered. – Agustí Roig Oct 24 '10 at 5:21
Could you provide a list of features that you consider legitimate to include in your formula? Often when these questions are posed, responses are met with "that doesn't count as a formula." – Douglas S. Stones Oct 24 '10 at 5:43
Don't know if it would count as "explicit" but every rational number occurs exactly one in the Calkin-Wilf sequence en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree – Jyotirmoy Bhattacharya Oct 24 '10 at 6:42
 Am I missing something or is the Cantor pairing function is not a bijection between the rationals and the naturals? It seems to, at best, reduce our problem to finding a bijection between $\mathbb{Q}$ and $\mathbb{N} \times \mathbb{N}$ – nham Apr 30 at 5:14