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?

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.

