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

| cite | improve this answer | |
  • $\begingroup$ I wish I could accept this for my question here. $\endgroup$ – Rudy the Reindeer Oct 28 '12 at 11:14
  • $\begingroup$ 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? $\endgroup$ – mSSM Apr 21 '15 at 12:01
  • $\begingroup$ @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!) $\endgroup$ – Brian M. Scott Apr 21 '15 at 16:42
  • $\begingroup$ 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$. $\endgroup$ – Guilherme Salomé Jul 17 '15 at 21:31
  • $\begingroup$ @Guilherme: You’re absolutely right; fixed now. Thanks! $\endgroup$ – 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$).

| cite | improve this answer | |
  • $\begingroup$ I am posting this answer here because I can't post in this thread anymore. $\endgroup$ – Rudy the Reindeer Oct 30 '12 at 18:37
  • $\begingroup$ The Wikipedia article about the pairing function also mentions continuity of $h$ but I don't think that's needed. $\endgroup$ – 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}$.

| cite | improve this answer | |

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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