Bijection between $\mathbb N \times \mathbb N$ and $\mathbb N$

Question

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.

Answer 1

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.

1. 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)
2. Use this to form $g(k,l) = g(k',l') \Rightarrow l-1 = l'-1$ and conclude.

Answer 2

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} $$