Prove that $|\mathbb{N} \times \mathbb{N}| \leq |\mathbb{N}|$ Claim: $|\mathbb{N} \times \mathbb{N}| \leq |\mathbb{N}|$
Proof:
For all  $ x \in \mathbb{N}, y \in \mathbb{N}$, we can define a function $f(x,y) = x + \frac{(x+y-1)(x+y-2)}{2}$ 
We now prove that $f$ is an injection. We will show that if $f(x,y) = f(u,v)$ then $x+y$ = $u+v$ 
Suppose $f(x,y) = f(u,v)$ but $x+y \neq u+v$. Then either $x+y > u+v$ or $u+v > x+y$. 
Case 1: $x+y > u+v$
Then $x+y = u+v + \delta$ for some $\delta > 0$.
$$x + \frac{(x+y -1)(x+y-2)}{2} = u + \frac{(u+v -1)(u+v-2)}{2} + \delta$$
Now, I don't know what to do. 
 A: I'm not sure if you function is an injection, and it's quite an ugly function aswell.
Consider this one:
$$
f(x,y)=2^x\cdot 3^y
$$
Use the uniqueness of the prime factorization to prove this is an injection. 

By the way, with your original argument, you weren't suppose to get that "$x+y=u+v$" but rather $x=u,y=v$: note that if $f(x,y)=x+y$, then certainly $f(x,y)=f(u,v)$ implies $x+y=u+v$, but this is nowhere near an injection.
A: Here's a way of proving that result that's easier to understand:
$$
\begin{array}{cccccccccc}
1,1 & & 1,2 & \rightarrow & 1,3 & & 1,4 & \rightarrow & 1,5 & & 1,6 & \rightarrow \\
\downarrow & \nearrow & & \swarrow & & \nearrow & & \swarrow & & \nearrow \\
2,1 & & 1,1, & & 2,3 & & 2,4 & & 2,5 & & \cdots \\
& \swarrow & & \nearrow & & \swarrow & & \nearrow \\
3,1 & & 3,2 & & 3,3 & & 3,4 & & 3,5 & & \cdots \\
\downarrow & \nearrow & & \swarrow & & \nearrow \\
4,1 & & 4,2 & & 4,3 & & 4,4, & & 4,5 & & \cdots \\
& \swarrow & & \nearrow \\
5,1 & & 5,2 & & 5,3 & & 5,4 & & 5,5 & & \cdots \\
\downarrow & \nearrow \\
6,1 & & \vdots & & \vdots & & \vdots & & \vdots
\end{array}
$$
There's a first member of $\mathbb N\times\mathbb N$, then a second, then a third, and so on.  No matter which member of $\mathbb N\times\mathbb N$ you pick, I know, without knowing which one you picked, that after some finite number of steps, I will reach it by following the arrows.  
A: $x,y,u,v\geq 1$
Suppose $x+y>u+v$:
Then $x+y\geq u+v+1$
So $$\begin{align}
\frac{(x+y-1)(x+y-2)}{2}&\geq \frac{(u+v)(u+v-1)}{2}\\
\frac{(x+y-1)(x+y-2)}{2}&\geq \frac{(u+v-1)(u+v-2)}{2} + u+v-1=f(u,v) + v-1\\
f(x,y)-x &\geq f(u,v)+v-1 \\
v+x-1\leq 0
\end{align}$$
Contradiction. If $x+y<u+v$, do the same thing.
Therefore, $u+v=x+y$
A: Easier, I think, is to consider $\mathbb{N} \times \mathbb{N}$ as a grid/lattice. Then label this lattice by running along the diagonals, ie $(0,0),(1,0),(0,1),(0,2),(1,1),(2,0),(3,0),(3,1),...$.
Also, Omnomnomnom's suggestion is equally as pleasing.
A: Let $p_n$ be the $n$-th odd prime e.g. $3=p_0$ and $5=p_1$. Define 
$$
f(m,n) =
\begin{cases}
p_m p_n & m \leq n\\
2 p_m p_n& n < m \\
\end{cases}
$$
Prove $f(m,n)$ is injective using the fundamental theorem of arithmetic (every natural number has a unique factorization into primes). 
