bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ I understand that both $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ are of the same cardinality by the Shroeder-Bernstein theorem, meaning there exists at least one bijection between them. But I can't figure out what such a bijection would be. The paper that I'm reading gives an example of an injective function $f:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$, $f(n)=(0,n)$, and an injective function $g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, $g(a,b)=2^a3^b$. I was thinking perhaps if there were some way to combine these two, I could find a bijection, but I have no idea how to go about that or if it's even possible.
What is an example of a bijection between these two sets, and please explain the process by which you found it?
 A: The easiest bijection $\mathbb{N}\times\mathbb{N} \to \mathbb{N}$ I know is like this:
$$\color{red}{42},\color{blue}{2013} \to 
\color{blue}{2}\,
\color{red}{0}\,
\color{blue}{0}\,
\color{red}{0}\,
\color{blue}{1}\,
\color{red}{4}\,
\color{blue}{3}\,
\color{red}{2}\,.
$$
The above is for base 10, but it works for any base $b \geq 2$.
Edit: As there was some confusion, some alternative explanations:


*

*To obtain the result, one starts writing digits from the right side in alternating fashion, and if one of the numbers has no more digits, we put zeros.

*Let $\varepsilon$ be the empty string, then
\begin{align}
f(\color{red}{a_ma_{m-1}\ldots a_2a_1},
  \color{blue}{b_nb_{n-1}\ldots b_2b_1}) &= 
f(\color{red}{a_ma_{m-1}\ldots a_2},
  \color{blue}{b_nb_{n-1}\ldots b_2})
    \color{blue}{b_1}\color{red}{a_1} \\
f(\color{red}{\varepsilon},
  \color{blue}{b_nb_{n-1}\ldots b_2b_1}) &= 
f(\color{red}{\varepsilon},
  \color{blue}{b_nb_{n-1}\ldots b_2})
    \color{blue}{b_1}\color{red}{0} \\
f(\color{red}{a_ma_{m-1}\ldots a_2a_1},
  \color{blue}{\varepsilon}) &= 
f(\color{red}{a_ma_{m-1}\ldots a_2a_1},
  \color{blue}{\varepsilon})
    \color{blue}{0}\color{red}{a_1} \\
f(\color{red}{a_1},
  \color{blue}{\varepsilon}) &= 
    \color{blue}{\varepsilon}\color{red}{a_1} \\
f(\color{red}{\varepsilon},
  \color{blue}{\varepsilon}) &= \varepsilon
\end{align}

*Let numbers be treated as polynomials in their base, i.e. $\mathbf{123}(z) = 1z^2+2z^1+3z^0$, then
$$f(\color{red}{\mathbf{a}},
  \color{blue}{\mathbf{b}})(z) = \color{red}{\mathbf{a}}(z^2) + z\color{blue}{\mathbf{b}}(z^2).$$


Some more examples for the first method:
\begin{align}
\color{red}{0},\color{blue}{50}  &\to 
\color{blue}{5}\,
\color{red}{0}\,
\color{blue}{0}\,
\color{red}{0}\,,\\
\color{red}{50},\color{blue}{0}  &\to 
\color{red}{5}\,
\color{blue}{0}\,
\color{red}{0}.
\end{align}
An example for the second method:
\begin{align}
f(\color{red}{42},\color{blue}{2013}) &= f(\color{red}{4},\color{blue}{201})
\,\color{blue}{3}\,\color{red}{2}\, \\
&= f(\color{red}{\varepsilon},\color{blue}{20})
\,\color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, \\
&= f(\color{red}{\varepsilon},\color{blue}{2}) \,
\color{blue}{0}\,\color{red}{0}\,
\color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\,\\
&= f(\color{red}{\varepsilon},\color{blue}{\varepsilon}) \,
\color{blue}{2}\,\color{red}{0}\,\color{blue}{0}\,\color{red}{0}\,
\color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, \\
&= \varepsilon\, \color{blue}{2}\,\color{red}{0}\,\color{blue}{0}\,\color{red}{0}\,
\color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\,
 \\
&= \color{blue}{2}\,\color{red}{0}\,\color{blue}{0}\,\color{red}{0}\,
\color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\,
.
\end{align}
Finally, an example for the third method:
\begin{align}
\color{red}{\mathbf{a}}(x) &= \color{red}{4}x+\color{red}{2} \\
\color{blue}{\mathbf{b}}(y) &= \color{blue}{2}y^3+\color{blue}{0}y^2+\color{blue}{1}y^1+\color{blue}{3}y^0 \\
\color{red}{\mathbf{a}}(z^2) &= 4z^2+2 \\
\color{blue}{\mathbf{b}}(z^2) &= 2z^6+z^2+3 \\
f(\color{red}{\mathbf{a}}, \color{blue}{\mathbf{b}})(z) 
&= \color{red}{\mathbf{a}}(z^2)+z\color{blue}{\mathbf{b}}(z^2) \\
&= 2z^7+z^3+4z^2+3z+2 \\
&= \color{blue}{2}z^7+\color{red}{0}z^6+\color{blue}{0}z^5+\color{red}{0}z^4+\color{blue}{1}z^3+\color{red}{4}z^2+\color{blue}{3}z^1+\color{red}{2}z^0
\end{align}
I hope this helps ;-)
A: I found such bijection when I was a freshman. Cantor found it, but I don't know how he came to notice it.
$$(m,n)\mapsto\frac{(m+n)(m+n+1)}2+m$$
Another function, which is simpler to prove is a bijection is the following, I don't know who came up with that one.
$$(m,n)\mapsto 2^m(2n+1)-1$$
The idea is that every pair encodes a unique number by writing it as an even number times an odd number, and reducing $1$ so we can get $0$ as well.
A: Assuming than $\mathbb N$ contains $0$, then 
$$f(m,n)=2^m(2n+1)-1$$
is a bijection from $\mathbb N \times \mathbb N$ to $\mathbb N$.
The inverse $g: \mathbb N \to \mathbb N \times \mathbb N$ is simple: $g(n)=(a,b)$ where $a$ is the largest power of $2$ dividing $n+1$ and $2b+1$ is the largest odd number dividing $n+1$.
If you don't include $0$ in $\mathbb N$, all you need is replace $m,n$ by $m-1, n-1$.
