Bijection between $\mathbb N \times \mathbb N$ and $\mathbb N$ Show that $\mathbb{N} \times \mathbb{N} \sim\mathbb{N}$.
I found a bijection such that $g(k,l): \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ by 
$$g(k,l) = {(k+l)(k+l-1) \over 2} - (l-1)$$
But I am having trouble showing that it is 1-1 and onto.  First I said let 
$${(k_1+l_1)(k_1+l_1-1) \over 2} = {(k_2+l_2)(k_2+l_2-1) \over 2}$$
and I was trying to use that to show $k_1 + l_1 = k_2 + l_2$ but I don't know how to do that, and once I get there I'm not sure how to show that $l_1=l_2$ or $k_1=k_2$
for onto I said let $y \in k+l$.  Then $${y(y-1) \over 2} = y$$ so therefore $g(k,l)$ is onto.
therefore g is a bijection.
 A: The part on surjection is not quite it (A natural number can't be an element of another natural number unless you use a special, unhandy construction wich would then say $y<k+l$) Given $y\in\mathbb N$ you must show that there is a way to chose $k, l$ such that
$$y = \frac{(k+l)(k+l-1)}{2} - (l-1)$$
A way to chose this is given in this article and a construction on wikipedia. (Thanks to @LuizCordeiro for finding the former link)
For injectivity you need to show that
$$\frac12 (k+l)(k+l-1) - (l-1) = \frac12 (k'+l')(k'+l'-1) - (l'-1)$$
for $k,k',l,l' \in\mathbb N$ implies $k=k', l=l'$. This can be done in two steps.


*

*Show $g(k,l) = g(k',l') \Rightarrow k+l = k'+l'$ by contradiction. (Assume $k+l = k'+l'$ and $g(k,l) \ne g(k',l')$ and derive a contradiction)  

*Use this to form $g(k,l) = g(k',l') \Rightarrow l-1 = l'-1$ and conclude.

A: Here's a one-to-one function from $\{1,2,3,\ldots\}\times\{1,2,3,\ldots\}$ to $\{1,2,3,\ldots\}{:}$
$$
\begin{array}{c|cccccccccc}
& 1 & 2 & 3 & 4 & 5 & 6 & 7 & \cdots \\
\hline
1 & 1 & 2 & 4 & 7 & 11 & 16 & 22 \\
2 & 3 & 5 & 8 & 12 & 17 & 23 \\
3 & 6 & 9 & 13 & 18 & 24 \\
4 & 10 & 14 & 19 & 25 \\
5 & 15 & 20 & 26 \\
6 & 21 & 27 \\
7 & 28 \\
\vdots
\end{array}
$$
If the pattern is not clear, consider this:
$$
\begin{array}{c|cccccccccc}
& 1 & 2 & 3 & 4 & 5 & 6 & 7 & \cdots \\
\hline
1 & & & & & & & 22 \\
2 & & & & & & 23 \\
3 & & & & & 24 \\
4 & & & & 25 \\
5 & & & 26 \\
6 & & 27 \\
7 & 28 \\
\vdots
\end{array}
$$
