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.

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

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 .

| cite | 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.

| cite | improve this answer | |
  • $\begingroup$ Relevance of "teddy bear"? $\endgroup$ – Karthik C Oct 28 '12 at 10:45
  • 2
    $\begingroup$ @Aneesh: See Matt's user page. $\endgroup$ – joriki Oct 28 '12 at 10:46
  • $\begingroup$ Dear @joriki, thank you very much for your empathy! $\endgroup$ – 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.