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.

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

share|improve this question

marked as duplicate by Beni Bogosel, Martin Sleziak, Asaf Karagila, Alex Becker, Zhen Lin Apr 17 '12 at 7:26

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.

    
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. –  Isaac Solomon Apr 17 '12 at 6:01
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. –  Arturo Magidin Apr 17 '12 at 6:01
2  
Duplicates at: this thread, and this and this and that. –  Asaf Karagila Apr 17 '12 at 6:10
    
If you want a specific rule $f(x,y)=\frac{1}{2}[(x+y)^2 + 3x + y] $ –  leo Apr 17 '12 at 6:10
    
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.. –  Daniel Apr 17 '12 at 8:10

4 Answers 4

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.

share|improve this answer

If you really want an "explicit" bijection, take $\alpha(m,n) = {(m+n+1)(m+n) \over 2} + n$. It's easy to check that this is the same bijection that "walks around the diagonals". The first part doesn't change when $m+n$ is constant (ie on a diagonal), and the second part is here because we take the diagonals from lower right to upper left.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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