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