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?

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