2
$\begingroup$

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

  • 2
    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 speci$f$ic like "what do all polynomial pairing functions look like."2011-03-13

1 Answers 1

5

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.

  • 0
    Ahhh, you're right. Quite uninteresting then. Thanks. What can be said about such functions, do you know?2011-03-13