Take the 2-minute tour ×
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.

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?

share|improve this question
    
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
    

2 Answers 2

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’s 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=a-(p+q)$, 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).

share|improve this answer
    
I wish I could accept this for my question here. –  Rudy the Reindeer Oct 28 '12 at 11:14

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

share|improve this answer
    
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

Your Answer

 
discard

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.