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