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?


marked as duplicate by Ayman Hourieh, M.H, user63181, Adriano, Ross Millikan Jul 15 '13 at 20:01

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.

  • $\begingroup$ Draw the coordinate axes and mark all the natural pairs. Then you can count them by starting at (0,0) then going with a zig-zag: (0,0)->(1,0)->(0,1)->(0,2)->(1,1)->(2,0)->(3,0) etc. An explicit formula for this will produce something similar to one given by Asaf Karagila, if I remember right. $\endgroup$ – Spine Feast Jul 15 '13 at 19:58

I found such bijection when I was a freshman. Cantor found it, but I don't know how he came to notice it.


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.

  • 2
    $\begingroup$ Let's call $f$ the first function. If $m+n=k$, then $f(m,n)=k(k+1)/2 + m$. So $f(0,0)=0$, $f(0,1)=1$, $f(1,0)=2$; $f(0,2)=3$, $f(1,1)=4$, $f(2,0)=5$; and so on. So we're counting the points on the lattice going through the diagonals. And we're lucky, because the $k$-th diagonal contains exactly $k+1$ points. $\endgroup$ – egreg Jul 15 '13 at 20:00

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:

  1. 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.
  2. 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}
  3. 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 ;-)

  • 2
    $\begingroup$ Is $0,50$ sent to $500$ or $50,0$ sent to $500$? $\endgroup$ – Asaf Karagila Jul 15 '13 at 19:54
  • 2
    $\begingroup$ @AsafKaragila: $(\color{red}{0},\color{blue}{50})=(\color{red}{00},\color{blue}{50})$ is sent to $\color{blue}5\color{red}0\color{blue}0\color{red}0$. I would have defined the bijection the other way, though. $\endgroup$ – celtschk Jul 15 '13 at 19:56
  • $\begingroup$ Thank you celtschk. You are right, maybe the other way would be more intuitive, but as long as we are consistent it does not matter. $\endgroup$ – dtldarek Jul 15 '13 at 19:58
  • 1
    $\begingroup$ @Asaf: I take it that $\langle1,11\rangle\mapsto1011$ and $\langle11,1\rangle\mapsto0111$. $\endgroup$ – Brian M. Scott Jul 15 '13 at 20:13
  • 1
    $\begingroup$ @AsafKaragila Let's treat a number as a polynomial in $b$, its base, that is, $123 = 1b^2+2b^1+3b^0$. Then $f(n,m) = n(b^2)+bm(b^2)$. $\endgroup$ – dtldarek Jul 15 '13 at 20:15

Assuming than $\mathbb N$ contains $0$, then


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


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