Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

marked as duplicate by Ayman Hourieh, Maisam Hedyelloo, Sami Ben Romdhane, 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.

    
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. –  DepeHb Jul 15 '13 at 19:58
add comment

3 Answers

up vote 16 down vote accepted

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.

share|improve this answer
2  
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. –  egreg Jul 15 '13 at 20:00
add comment

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 ;-)

share|improve this answer
2  
Is $0,50$ sent to $500$ or $50,0$ sent to $500$? –  Asaf Karagila Jul 15 '13 at 19:54
1  
@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. –  celtschk Jul 15 '13 at 19:56
    
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. –  dtldarek Jul 15 '13 at 19:58
1  
@Asaf: I take it that $\langle1,11\rangle\mapsto1011$ and $\langle11,1\rangle\mapsto0111$. –  Brian M. Scott Jul 15 '13 at 20:13
1  
@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)$. –  dtldarek Jul 15 '13 at 20:15
show 16 more comments

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

share|improve this answer
add comment

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