Tell me more ×
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.
up vote 9 down vote favorite
2

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?

share|improve this question
8  
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
1  
@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
2  
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
show 2 more comments

1 Answer

up vote 12 down vote accepted

Wikipedia contains several explicit examples: Cantor pairing function, Stern–Brocot tree, Calkin–Wilf tree.

share|improve this answer
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

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.