1
$\begingroup$

Possible Duplicate:
How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$?

I have seen analysis books that show $\mathbb{N}\times \mathbb{N}$ is countable by "walking along the diagonals" argument. But I was never quite sure why is this enough, as this does not give a specific rule (or formula) for each element in $\mathbb{N}\times \mathbb{N}$ (which certainly can be constructed in the first place). I hope this question makes some sense..

  • 0
    Interpreted properly, "walking along the diagonals" is certainly a good argument. Of course, one needs to formally define a function, but that can be done easily from the idea of "walking along the diagonal." One very easy way of doing this is defining the function recursively.2012-04-17
  • 1
    It shows that there is a surjection $\mathbb{N}\to\mathbb{N}\times\mathbb{N}$. In any case, the "walking along diagonals" is easy to write as an explicit formula, e.g., using triangular numbers.2012-04-17
  • 2
    Duplicates at: [this thread](http://math.stackexchange.com/questions/16611/bijecting-a-countably-infinite-set-s-and-its-cartesian-product-s-times-s), and [this](http://math.stackexchange.com/questions/29420/how-does-one-get-the-formula-for-this-bijection-from-mathbbn-times-mathbbn) and [this](http://math.stackexchange.com/questions/54158/the-cartesian-product-mathbbn-times-mathbbn-is-countable) and [that](http://math.stackexchange.com/questions/91318/proving-the-cantor-pairing-function-bijective).2012-04-17
  • 0
    If you want a specific rule $f(x,y)=\frac{1}{2}[(x+y)^2 + 3x + y] $2012-04-17
  • 0
    Thanks for the comments! I just want to make sure I understand this. The picture of "walking along the diagonals" is just motivation for the construction of the pairing function, but by itself does not constitute a proof, right? It is just that I rememmber seeing books that show only the picture and leave it as is, as if the construction of the pairing functions arises trivially to the reader with no second thought..2012-04-17
  • 0
    Polynomials are nice for some purposes, but there are other ways. There are two interpretations of $\mathbb{N}$, with $0$ and without. Assume without. Then we can map $(x,y)$ to $2^{x-1}(2y-1)$.2013-02-03

3 Answers 3

2

Actually, there is an explicit formula for a "walking" function. For some of the details, see the Wikipedia article on the Cantor pairing function.

There is a small thing to remember when reading that article. There, as is traditional in logic, one is mapping the set of ordered pairs $(a,b)$ of non-negative integers to the non-negative integers. If you want to map pairs of positive integers to the positive integers, that is, if by $\mathbb{N}$ you mean the set of positive integers, let $\pi$ be the pairing function of the Wikipedia article, and define $g(x,y)$ by $$g(x,y)=\pi(x-1,y-1)+1.$$ We end up with the function $$g(x,y)=\frac{1}{2}(x+y-2)(x+y-1)+y.$$ Surprise, a quadratic polynomial! The fact that it is a polynomial is of some mild usefulness in logic.

1

The triangular numbers $T(n)$ are the numbers that count how many objects there are in "triangular arrays", arrays like $\bullet$, or $$\begin{array}{ccc} &\bullet\\ \bullet&&\bullet \end{array}$$ or $$\begin{array}{cccccccc} &&\bullet\\ &\bullet &&\bullet\\ \bullet & &\bullet && \bullet\end{array}$$.

The numbers are: $$\begin{align*} T(1) &= 1\\ T(2) &= 1+2 = \frac{2\times 3}{2}\\ T(3) &= 1+2+3 = \frac{3\times 4}{2}\\ &\vdots\\ T(n) &= 1+2+\cdots+n = \frac{n(n+1)}{2}. \end{align*}$$

Given a natural number $k$, there is a largest $m$ such that $T(m)\leq k$, and in that case we have that $k-T(m)\leq m$, since $T(m+1)=T(m)+m+1$.

Going down the diagonals counts triangular numbers. The first diagonal (the top corner) is $T(1)$. If you now add the second diagonal (the pairs $(1,2)$ and $(2,1)$) you get $T(2)$; add the third diagonal (consisting of pairs $(1,3)$, $(2,2)$, and $(3,1)$) you get $T(3)$. Etc.

So, given $k\in\mathbb{N}$, let $m$ be the largest integer such that $T(m)\leq k$. Then we are in the $k$th diagonal. If $r=k-T(m)$, then we've moved $k$ steps down and left. So we define $$f(k) = \Bigl( r, T(m)-r\Bigr) = \Bigl( k-T(m), 2T(m)-k\Bigr),$$ where $m$ is the largest integer with $T(m)\leq k$.

0

If you let $k(n) = \lceil \frac{\sqrt{1+8n}-1}{2} \rceil$, and $j(n,k) = \frac{k (k+1)}{2}-n+1$, then $\beta:\mathbb{N} \rightarrow \mathbb{N}\times \mathbb{N}$ defined by $$\beta(n) = (j(n,k(n)), k(n)-j(n,k(n))+1)$$ is a bijection and 'walks the diagonal'. The inverse $\beta^{-1}: \mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}$ is given by: $$ \beta^{-1}(j, l) = \frac{(l+j-1)(l+j)}{2}-j+1$$