# Proving the Cantor Pairing Function Bijective

How would you prove the Cantor Pairing Function bijective? I only know how to prove a bijection by showing (1) If $f(x) = f(y)$, then $x=y$ and (2) There exists an $x$ such that $f(x) = y$

How would you show that for a function like the Cantor pairing function?

-
The cited article shows you an alternative way in its proof of the fact: construct the inverse function. – Brian M. Scott Dec 14 '11 at 2:54

It can be done exactly as you suggest: by proving (1) that if $\pi(m,n)=\pi(p,q)$, then $\langle m,n\rangle=\langle p,q\rangle$, and (2) that for each $m\in\mathbb{N}$ there is a pair $\langle p,q\rangle\in\mathbb{N}\times\mathbb{N}$ such that $\pi(p,q)=m$, where $$\pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}:\langle m,n\rangle\mapsto \frac12(m+n)(m+n+1)+n$$ (where I’m using the version of the pairing function given in the Wikipedia article that you cite).

(1) Suppose that $\pi(m,n)=\pi(p,q)$, i.e., that $$\frac12(m+n)(m+n+1)+n=\frac12(p+q)(p+q+1)+q\;.\tag{1}$$ The first step is to show that $m+n=p+q$, so suppose not. We may as well assume that $m+n<p+q$. For convenience let $a=m+n$ and $d=(p+q)-a$, so that $(1)$ becomes $$\frac{a(a+1)}2+n=\frac{(a+d)(a+d+1)}2+q\;.$$

Then \begin{align*} n-q&=\frac{(a+d)(a+d+1)}2-\frac{a(a+1)}2\\ &=ad+\frac{d(d+1)}2\\ &\ge a+1\;, \end{align*}

so $n>a+q\ge a=m+n\ge n$, which is absurd. Thus, $m+n=p+q$, and $(1)$ immediately implies that $n=q$ and hence also $m=p$. This establishes that $\pi$ is injective.

(2) This is exactly the calculation given here. The article doesn’t prove (1) explicitly because in the process of uniquely reconstructing $\langle x,y\rangle$ from $z=\pi(x,y)$ it implicitly shows (1).

-
I wish I could accept this for my question here. – Rudy the Reindeer Oct 28 '12 at 11:14
I am not sure the the way you show the contradiction is correct: in $ad + \frac{d(d+1)}{2}$, we have that $a>0$ and $d<0$, which follows from $m,n \in \mathbb{N}$, your definition of $d$, and the assumption $m+n < p+q$. Take $d=-1$, then $ad + \frac{d(d+1)}{2} = -a < a$. Or do I maybe have a mistake somewhere? – mSSM Apr 21 '15 at 12:01
@mSSM: It was a typo: the subtraction in the definition of $d$ was backwards. I’ve fixed it now. (I’m surprised that no one caught it before!) – Brian M. Scott Apr 21 '15 at 16:42
Hey Brian, I think there's a typo in the definition of $d$. You defined it as $d=(p+q)-d$, I think you meant to write $d=(p+q)-a$. – Guilherme Salomé Jul 17 '15 at 21:31
@Guilherme: You’re absolutely right; fixed now. Thanks! – Brian M. Scott Jul 17 '15 at 21:33

Claim: $f: (m,n) \mapsto n + \frac12 (m+n)(m+n+1)$ is bijective.

Proof: It's enough to show that $f$ is invertible because if there is an inverse function $g$ then injectivity and surjectivity both directly follow from $f \circ g = \mathrm{id}$.

To invert $f$ we introduce the following variables: $$z = f(m,n) = n + \frac12 (m+n)(m+n+1)$$

$$w = m + n$$

so that $z = n + \frac{w^2 + w}{2}$. Next we also introduce $$t = \frac{w^2 + w}{2}$$

It is not clear to me how we figured out what we introduce. But after we introduce $t$ and $w$ it is clear that $n = z -t$ and $m = w-n$ where $z$ is known so that if we can write $w$ and $t$ as functions of $z$ we are done.

We observer that from $t = \frac{w^2 + w}{2}$ we get $w^2 + w - 2t = 0$ from which we obtain $w = \frac{-1 \pm \sqrt{1 + 8t}}{2}$ and since $w \in \mathbb N$ it is clear that only $$w = \frac{-1 + \sqrt{1 + 8t}}{2}$$ is a solution. Now we have $w$ as a function of $t$. From this we can reach our goal of writing $w$ as a function of $z$. To this end, we introduce $h(t) = w = \frac{-1 + \sqrt{1 + 8t}}{2}$ and observe that $h$ is strictly increasing on $\mathbb R_{\geq 0}$ with $h^{-1}(\omega) = t = \frac{w^2 + w}{2}$.

Also, $t \leq t + n < t + w + 1$ which is the same as $\frac{w^2 + w}{2} \leq z < \frac{(w+1)^2 + (w+1)}{2}$. Which is the same as $$h^{-1}(w) \leq z < h^{-1}(w+1)$$

From which we get $$w \leq h(z) < w+1$$

which is the same as $$w \leq \frac{-1 + \sqrt{1 + 8z}}{2} < w + 1$$ Now we're almost there. We know that $w \in \mathbb N$ hence $$w = \left \lfloor \frac{-1 + \sqrt{1 + 8z}}{2} \right \rfloor$$

Now we have $w$ as a function of $z$ which is what we wanted. From this we get $n$ and $m$ (as functions of $z$).

-
I am posting this answer here because I can't post in this thread anymore. – Rudy the Reindeer Oct 30 '12 at 18:37
The Wikipedia article about the pairing function also mentions continuity of $h$ but I don't think that's needed. – Rudy the Reindeer Oct 30 '12 at 18:37

I will denote the pairing function by $f$. We will show that pairs $(x,y)$ with a particular value of the sum $x+y$ is mapped bijectively to a certain interval, and then that the intervals for different value of the sum do not overlap, and that their union is everything.

Let $m$ be a natural number and suppose $m=x+y$. The least value that $f(x,y)$ can take is $\frac{m(m+1)}{2}$ (if $x=m$) and the largest value it can take is $\frac{m(m+1)}{2}+m$ (if $y=m$). It can also take all values in between. It is thus easy to see that the $m+1$ pairs $(x,y)$ with sum $m$ are mapped bijectively to an interval.

If $x+y=m+1$ then the least possible value of $f(x,y)$ is $\frac{(m+1)(m+2)}{2}$. We can check that $\frac{(m+1)(m+2)}{2} - (\frac{m(m+1)}{2}+m)=1$ so the intervals for the different value of the sum do not overlap and it is easy to see that their union is $\mathbb{N}$.

-