11
$\begingroup$

When showing that $\mathbb{N}\times\mathbb{N}$ is in bijection with $\mathbb{N}$, it seems standard to give a proof by picture that shows a way to systematically weave through all the points in $\mathbb{N}\times\mathbb{N}$ and label each one as you go.

enter image description here

I know there is a polynomial expression for this method, given by $ J(m,n)=[1+2+\cdots+(m+n)]+m=\frac{1}{2}[(m+n)^2+3m+n] $ where $m$ is the usual $x$-coordinate and $n$ the usual $y$-coordinate.

But how does one "see" how this formula is arrived at? I know how to manipulate the middle expression to arrive at the rightmost expression, but how does the middle expression relate to the weaving pattern through $\mathbb{N}\times\mathbb{N}$? Thank you.

  • 0
    Perhaps it's worth mentioning that this function is called *Cantor pairing function*. http://en.wikipedia.org/wiki/Pairing_function2011-07-28

4 Answers 4

3

To weave all the way to $(m,n)$, you first have $m+n$ complete top-left to bottom-right passes, of which the first contains 1 point $(0,0)$, the second two points $(0,1)$ and $(1,0)$, ..., the $m+n$'th $m+n$ points $(0,m+n-1)$ to $(m+n-1,0)$, and then the $m+1$'th point on the next pass is $(m,n)$.

2

Looking at the diagram, the order is lexicographic, first in $m+n$, then in $m$. The motivation is that it is easy to see you get all the points of $\mathbb{N} \times \mathbb{N}$, so now you just need to figure out what $J(m,n)$ is.

  • 0
    There is a triangle with side $(m+n)$ all filled up-that is $(m+n)(m+n+1)/2$ points before you start the down-right diagonal, which you travel $m+1$ steps on. So I would claim $J(m,n)=(m+n)(m+n+1)/2+m+1$, slightly different from yours.2011-03-28
2

$J(m,n)$ is just the number of points that are before $(m, n)$ in this order. These are the points $(x,y)$ with $x+y < m+n$, and the points $(x,y)$ with $x + y = m + n$ and $x < m$.

The first type of points can be broken down into those with $x+y = 0$ (of which there is $1$), those with $x+y = 1$ (of which there are $2$), and so on up to those with $x +y = m+n-1$, of which there are $m+n$. These are $(m+n-1, 0), (m+n-2, 1), \cdots, (0, m+n-1)$. So there are $1 + 2 + \cdots + (m+n)$ of these.

The second type are just the points $(0,n), (1,n-1), \cdots, (m-1, m+n-1)$. There are $m$ of these.

So the total number of points preceding $(m,n)$ in this order is $ [1 + 2 + \cdots + (m+n)] + m $ which is what you wanted.

1

Say $m$ is the column, $n$ is the row. You want to know how many points you have already counted by the time you get to $(m,n)$, using the picture.

If you go up $n$ rows, you will have counted the first $n$ diagonals in full (since the count starts with $0$). These give you $1+2+3+\cdots+n$ points, since the $n$th downward diagonal has $n$ points in it.

Now, each step you move to the right to get to $(m,n)$ will add another full diagonal that you must have already "added up". This will give you the diagonals with $n+1$, $n+2,\ldots,n+m$ points. This means that, counting only downward diagonals that you have completely counted, you have $1 + 2 + 3 + \cdots + n + (n+1) + \cdots + (m+n) = \frac{(m+n)(m+n+1)}{2}$ points.

In addition, you have some points in the diagonal you are on that have been counted. How many? One for each column you moved to the right; there are $m$ of those. So in addition to the points you already added, there are the first $m$ points on the diagonal you are on. So once you get to that point, you have counted $(1+2+3+\cdots+(n+m) + m = \frac{(m+n)(m+n+1)}{2}+m = \frac{1}{2}\left((m+n)^2+(m+n) + 2m\right)$ points, which gives the formula.