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.

Possible Duplicate:
Proving the Cantor Pairing Function Bijective

Assume I define

$$ f: \mathbb N \times \mathbb N \to \mathbb N, (a,b) \mapsto a + \frac{(a + b ) ( a + b + 1)}{2} $$

How to show that this function is bijective? For injectivity I tried to show that if $f(a,b) = f(n,m) $ then $(a,b) = (n,m)$ but I end up getting something like $3(n-a) + (n+m)^2 -(a+b)^2 + m - b = 0$ and don't see how to proceed from there. There has to be something cleverer than treating all possible cases of $a \leq n, b \leq m$ etc.

For surjectivity I'm just stuck. If I do $f(0,n)$ and $f(n,0)$ it doesn't seem to lead anywhere.

Thanks for your help.

share|improve this question

marked as duplicate by Asaf Karagila, Martin Sleziak, Rudy the Reindeer, joriki, Grigory M Oct 28 '12 at 12:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

You switched from $f$ to $J$ at some point. –  Asaf Karagila Oct 28 '12 at 11:08
@AsafKaragila Fixed. Now that I know what this function is called I could as well have looked up the proof on the internet. –  Rudy the Reindeer Oct 28 '12 at 11:09

2 Answers 2

up vote 1 down vote accepted

Introduce two other functions $$p(z)=z-\frac{n(n+1)}{2}\textrm{ and }q(z)=n-p(z)$$ where $$n=\left\lfloor\frac{\sqrt{8z+1}-1}{2}\right\rfloor$$

You can try to prove $p(f(a,b))=a$ and $q(f(a,b))=b$.

In order to prove this, you can use some 2D diagram for integers because $(f,p,q)$ are actually Pairing functions.

Please refer http://en.wikipedia.org/wiki/Pairing_function .

share|improve this answer

The term $(a+b)(a+b+1)/2$ is the sum of the numbers from $1$ to $a+b$. For a fixed value of $s=a+b$, $a$ ranges from $0$ to $s$, so we need $s+1$ different results for these arguments. Now you can prove by induction that the range from $s(s+1)/2$ to $(s+1)(s+2)/2-1$ contains precisely the images of the pairs with sum $s$.

And I truly empathize with the loss of your teddy bear. My teddy bear would be the first thing I'd save in case of fire.

share|improve this answer
Relevance of "teddy bear"? –  Host-website-on-iPage Oct 28 '12 at 10:45
@Aneesh: See Matt's user page. –  joriki Oct 28 '12 at 10:46
Dear @joriki, thank you very much for your empathy! –  Rudy the Reindeer Oct 28 '12 at 11:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.