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?

Solutions Collecting From Web of "Proving the Cantor Pairing Function Bijective"

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*}
&\ge a+1\;,

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

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