4
$\begingroup$

This question already has an answer here:

I know that is possible to build a bijection between the set of natural numbers $\mathbb{N}$ and the natural plane (the cartesian product of $\mathbb{N}$ by itself, $\mathbb{N} \times \mathbb{N} = \mathbb{N}^2$. This is done by diagonally traversing the plane from zero upwards with triangles of growing size.

Is there a simple algebraic form for that bijection? That is, is it possible to write explicitly some invertible $f(i, j): \mathbb{N} \times \mathbb{N} \leftrightarrow \mathbb{N}$?

I need to index in a simple way couples of natural numbers.

$\endgroup$

marked as duplicate by Martin Sleziak, Asaf Karagila, Peter Taylor, Surb, Willie Wong Mar 31 '15 at 13:54

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.

3
$\begingroup$

A bijection is:

$$f(m,n)=2^m(2n+1)-1$$

$\endgroup$
  • $\begingroup$ Why doesn't just $2^m(2n+1)$ work? $\endgroup$ – Nishant Aug 6 '14 at 4:45
  • 1
    $\begingroup$ I assume that $0\in \mathbb{N}$ $\endgroup$ – AsdrubalBeltran Aug 6 '14 at 4:48
  • $\begingroup$ Yeah, and if $0\notin\mathbb N$, then the RHS won't hit half the positive integers. $\endgroup$ – Nishant Aug 6 '14 at 13:20

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