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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was working through Pugh's Real Mathematical Analysis when I came across this proof:

Theorem $\mathbb{N} \times \mathbb{N}$ is denumerable.

Proof Think of $\mathbb{N} \times \mathbb{N}$ as an $\infty \times \infty$ matrix and walk along the successive counter-diagonals. This gives a list $$(1, 1), (2, 1), (1, 2), (3, 1), (2, 2), (1, 3), (4, 1) (3, 2) (2, 3) (1, 4) (5, 1)...$$ of $\mathbb{N} \times \mathbb{N}$ and proves that $\mathbb{N} \times \mathbb{N}$ is denumerable.

The proof is accompanied by a visual diagram showing successive diagonals crossed out where for each $a_{ij} \in \mathbb{N} \times \mathbb{N}$, $i + j = d$, $d$ fixed.

Now from the diagram, it is visually easy to see that the graph of the function given is surjective. And I understand "intuitively" why the graph is injective; we can just list the ordered pairs out as "1, 2, 3...", where each one is different. However, it was quite frustrating to explicitly come up with a function and check it was injective to my satisfaction. The book gives hints in the exercises so you can eventually come up with the function $2^{i}(2j + 1)$, which I verified was injective. Since primes seem to be "fundamental" when discussing the natural numbers, I thought all Cantor pairing functions might be of the form $p^{i}(pj + k)$ where $0 < k < p$, and $p$ is prime.

Looking it up, however, Wikipedia informs me that this is not so as, $$n = f(i, j) = \dfrac{(i + j)(i + j + 1)}{2} + j$$

is a bijection from $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$, which I again verified. So my question is, what do these Cantor pairing functions generally look like? Is there a sufficiency criterion?

EDIT: Zev's answer below convinces me that the general question I asked above is very uninteresting. Can something more interesting be said if one requires the function to be continuous on $\mathbb{R^2}$, and still send $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$? I think that's was what was intuitively coming to my mind when I was thinking about "an explicit form."

share|cite|improve this question
I wanted to post the diagram from the book directly into this post as shown here, but was unable to locate the clip tool for Google Books that I'd thought would be present. If anyone could edit and paste that diagram into the picture, it'd be appreciated. – Uticensis Mar 13 '11 at 21:22
Any function $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ can be extended to a continuous function on $\mathbb{R}^2$ (say, piecewise linearly). – Qiaochu Yuan Mar 13 '11 at 23:07
@Qiaochu Yuan Do you mind if I refer to you by your first name from now on? Anyway, you're right, it's trivial as written, continuity is obviously not the only condition I wanted to impose. I've been searching and I came across something that describes a "generalized Cantor pairing polynomial", but I don't think that's what I want either, since the $2^{i}(2j + 1)$ is sufficiently "nice" for my purposes though contains an exponential term. – Uticensis Mar 13 '11 at 23:28
@Qiaochu Yuan (cont'd) I want it to be a "nice" expression somehow, but maybe there are terse expressions with non-elementary functions that interpolate through the required points, I don't know. Do you understand what I'm struggling to say, or am I speaking nonsense? – Uticensis Mar 13 '11 at 23:29
I understand what you think you're trying to say, but I don't see any sensible way to make this question precise other than something very specific like "what do all polynomial pairing functions look like." – Qiaochu Yuan Mar 13 '11 at 23:58
up vote 5 down vote accepted

I don't see how there could possibly any sort of "characterization" - the bijections from $\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}$ are just the bijections from $\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}$, whether or not there's a "formula" for them is irrelevant.

Or, if you like, take any bijection $f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ that is given by a "formula", and compose it with any permutation $\sigma:\mathbb{N}\rightarrow\mathbb{N}$. That's a new bijection from $\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}$ (in fact they can all be gotten this way), and there's no reason why $\sigma$ should preserve the form of the "formula" for $f$, it could do anything.

share|cite|improve this answer
Ahhh, you're right. Quite uninteresting then. Thanks. What can be said about such functions, do you know? – Uticensis Mar 13 '11 at 21:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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