# 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?

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

Let us begin with a general theorem.

Theorem 1: For each integer $k \ge 0$ let there be given a nonempty finite set $D_k$ that is totally ordered by a relation $\le_k$, and that $D_j \cap D_k = \emptyset$ when $j \ne k$. Then there exists a 'natural' bijective correspondence

$\tag 1 C: \bigcup D_k \to \mathbb N$

Proof We define $C$ recursively on one $D_k$ 'piece' at a time, starting with an increasing order isomorphism $C_0: D_0 \to [0, j_0]$ where $D_0$ has $j_0 + 1$ elements. We can continue in a natural way, extending $C_0$ to a bijective function $C_1: D_0 \cup D_1 \to [0, j_1]$ where the cardinality of $D_0 \cup D_1$ is $j_1 + 1$. We can continue in this way, defining bijective maps $C_k$.

$C$ is the direct limit of the $C_k$ mappings. $\qquad \blacksquare$

For each integer $k \ge 0$ define

$\tag 2 D_k = \{(m,n) \in \mathbb N \times \mathbb N \; | \: m + n = k\}$

It is easy to see that these finite sets partition $\mathbb N \times \mathbb N$. We also have two simple ways of ordering $D_k$. So we insist that $(k,0)$ is the smallest element, followed by $(k-1,1)$, $(k-2,2)$, and so on.

By theorem 1, a bijective correspondence naturally follows between $\mathbb N \times \mathbb N$ and $\mathbb N$. To make it explicit using arithmetic, you need to count things. First you have to know how many elements are in each $D_k$ and then the number of elements $j_k + 1$ in the domain of $C_k$.

If you work this out, you will be looking for a formula to add up $1 + 2 + 3 \dots + n$.

Proposition 2: The Cantor pairing function is a bijection.
Proof
Let $(m,n)$ belong to $D_k$. We already have $C_{k-1}$ (see Theorem 1) mapping $D_0 \cup D_1 \cup D_2 \dots \cup D_{k-1}$ onto an initial segment of $\mathbb N$ with exactly $1 + 2 + \dots + k$ integers. Since $m+n = k$ and $0$ is in the range of $C_{k-1}$, the restriction map $C_{k-1}$ reaches a maximum integer value of

$\tag 3 \frac{(m+n)(m+n+1)}{2} - 1$

Now if $(m,n) = (k,0)$, the first element of $D_k$, we would add $1$ to the expression (3). A moments thought and you can see that moving along $D_k$ in $1 \text{-step}$ increments is exactly defined by the quantity $n$. So

$\tag 4 C_k(m,n) = \frac{(m+n)(m+n+1)}{2} + n$

But this formula does not depend on $k$, so (4) defines the bijective Cantor Pairing Function. $\qquad \blacksquare$

Using this approach, it is not necessary to check for injectivity or surjectivity or to find an inverse function. That is taken care of by the general construction of $C$ in theorem 1.