Take the 2-minute tour ×
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.

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
9  
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. –  a.r. 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
3  
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

2 Answers 2

up vote 17 down vote accepted

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

share|improve this answer
3  
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 '13 at 5:14

In order to create this function, one needs to look at this in several parts and then assemble the pieces together to produce the final function.

First you'll need the following series:

0,1,1,2,1,2,3,1,2,3,4,...

0,1,2,1,3,2,1,4,3,2,1,...

One series is the numerator and the other the denominator. An explicit function to generate each series will be needed (try wikipedia or other online math resources to find these)

Then a way to cycle through this a second time so that all values are negative will be needed.

The easiest way to think of assembling all these parts is most likely composite functions.

Use the old (-1)^n trick for switching to negative values.

A professor showed me this function once, I've been trying to look for it in old notes but to no avail. If I remember correctly, it uses composite functions and floors/ceilings.

Sorry if this was not helpful to you in your pursuits.

share|improve this answer

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.