Countability of cartesian product of $\mathbb{N} \times \mathbb{N}$ 
Possible Duplicate:
How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$? 

I have seen analysis books that show  $\mathbb{N}\times \mathbb{N}$ is countable by "walking along the diagonals" argument. But I was never quite sure why is this enough, as this does not give a specific rule (or formula) for each element in $\mathbb{N}\times \mathbb{N}$  (which certainly can be constructed in the first place). I hope this question makes some sense..
 A: Actually, there is an explicit formula for a "walking" function. For some of the details, see the Wikipedia article on the Cantor pairing function.
There is a small thing to remember when reading that article. There, as is traditional in logic, one is mapping the set of ordered pairs $(a,b)$ of non-negative integers to the non-negative integers. If you want to map pairs of positive integers to the positive integers, that is, if by $\mathbb{N}$ you mean the set of positive integers, let $\pi$ be the pairing function of the Wikipedia article, and define $g(x,y)$ by
$$g(x,y)=\pi(x-1,y-1)+1.$$
We end up with the function
$$g(x,y)=\frac{1}{2}(x+y-2)(x+y-1)+y.$$
Surprise, a quadratic polynomial!  The fact that it is a polynomial is of some mild usefulness in logic.
A: The triangular numbers $T(n)$ are the numbers that count how many objects there are in "triangular arrays", arrays like $\bullet$, or
$$\begin{array}{ccc}
&\bullet\\
\bullet&&\bullet
\end{array}$$
or
$$\begin{array}{cccccccc}
&&\bullet\\
&\bullet &&\bullet\\
\bullet & &\bullet && \bullet\end{array}$$.
The numbers are:
$$\begin{align*}
T(1) &= 1\\
T(2) &= 1+2 = \frac{2\times 3}{2}\\
T(3) &= 1+2+3 = \frac{3\times 4}{2}\\
&\vdots\\
T(n) &= 1+2+\cdots+n = \frac{n(n+1)}{2}.
\end{align*}$$
Given a natural number $k$, there is a largest $m$ such that $T(m)\leq k$, and in that case we have that $k-T(m)\leq m$, since $T(m+1)=T(m)+m+1$.
Going down the diagonals counts triangular numbers. The first diagonal (the top corner) is $T(1)$. If you now add the second diagonal (the pairs $(1,2)$ and $(2,1)$) you get $T(2)$; add the third diagonal (consisting of pairs $(1,3)$, $(2,2)$, and $(3,1)$) you get $T(3)$. Etc.
So, given $k\in\mathbb{N}$, let $m$ be the largest integer such that $T(m)\leq k$. Then we are in the $k$th diagonal. If $r=k-T(m)$, then we've moved $k$ steps down and left. So we define
$$f(k) = \Bigl( r, T(m)-r\Bigr) = \Bigl( k-T(m), 2T(m)-k\Bigr),$$
where $m$ is the largest integer with $T(m)\leq k$. 
A: If you let $k(n) = \lceil \frac{\sqrt{1+8n}-1}{2} \rceil$, and $j(n,k) = \frac{k (k+1)}{2}-n+1$,
then $\beta:\mathbb{N} \rightarrow \mathbb{N}\times \mathbb{N}$ defined by
$$\beta(n) = (j(n,k(n)), k(n)-j(n,k(n))+1)$$
 is a bijection and 'walks the diagonal'. The inverse $\beta^{-1}: \mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}$ is given by:
$$ \beta^{-1}(j, l) = \frac{(l+j-1)(l+j)}{2}-j+1$$
