# Proving That $\mathbb{N} \cong \mathbb{N}^2$

這邊的同構是指存在雙射。想要找出一個$f$並不難，難的是證明他是onto及1-1的。


## Lemma: Suppose $a,b \in \mathbb{N}, a>b$. Then ${a(a+1) \over 2}-{b(b+1) \over 2} \ge a$
This lemma can be proven by the use of simple algebraic operation and the fact that $a,b \in \mathbb{N}$.

Note that:

$$
\begin{aligned}
& {a(a+1) \over 2}-{b(b+1) \over 2} \ge a \\
\iff &{a(a+1) - b(b+1)} \ge 2a \\
\iff &{a^2+a - b^2-b} \ge 2a \\
\iff &{a^2-a - b^2-b} \ge 0 \\
\iff &{a^2-b^2 - (a+b)} \ge 0 \\
\iff &{(a+b)(a-b) - (a+b)} \ge 0 \\
\iff &{(a+b)(a-b) - (a+b)} \ge 0 \\
\iff &{(a+b)(a-b-1)} \ge 0 \\
\end{aligned}
$$

Moreover, $a+b \ge 0$ is evident. $a-b \ge 1$ is also true by that $a \gt b, a,b \in \mathbb{N}$
Hence we have the last equation: ${(a+b)(a-b-1)} \ge 0$ hold true.

## Theorem: $\mathbb{N} \cong \mathbb{N}^2$
Let $f:\mathbb{N}^2 \rightarrow \mathbb{N}$ be a mapping, such that $f(a,b) = {(a+b-1)(a+b-2) \over 2}+a$

### $f$ is 1-1
Let any $(a,b),(c,d) \in \mathbb{N}^2, f(a,b)=f(c,d)$.

Then we have
$${(a+b-1)(a+b-2) \over 2} - {(c+d-1)(c+d-2) \over 2} = c-a$$
If $a+b=c+d$, then clearly we have $c-a=0$, which leads to $(a,b)=(c,d)$

If not, we can assume WLOG that $a+b \gt c+d$.

Moreover, by lemma, since $a+b-2 > c+d-2$,
$$ c-a = {(a+b-1)(a+b-2) \over 2} - {(c+d-1)(c+d-2) \over 2} \ge a+b-2$$

From $a+b>c+d$, and the inequality above we also get

$$a+b-2 \le c-a < b-d$$

This is so $a+d < 2$, which is absurd as $a,b\in \mathbb N$.

This shows $a+b=c+d$ is the only possiblility, in which case $f$ is 1-1. Hence $f$ is indeed 1-1.

### $f$ is onto

Suppose some $n \in \mathbb{N}$ is chosen.

Let $S = \{ t \in \mathbb{N} : {t(t+1) \over 2} \ge n \}$. Because we can choose $t$ large enough (for example, $t=n$) such that $t \in S$, $S$ is nonempty and we may let $t_0 \in S$ be the minimal element by the [well ordering principle](https://en.wikipedia.org/wiki/Well-ordering_principle).

Now, choose $$\begin{cases} a=n-{t_0(t_0-1) \over 2} \\ b=t_0+1-a \end{cases}$$

Noticing $a+b = t_0+1$, we can easily verify that
$$f(a,b) = {t_0(t_0-1) \over 2} - \left(n-{t_0(t_0-1) \over 2}\right) = n$$

We are left to check that $a,b \in \mathbb{N}$.

Because $t_0$ is the minimal element in S, we have $t_0-1 \notin S$, i.e. ${t_0(t_0-1) \over 2} \lt n$
Hence $a = n - {t_0(t_0-1) \over 2} \gt 0$. Then $a \in \mathbb{N}$.
As for $b$, note that
$$\begin{align}
b &= t_0 + 1 - a \\
&= t_0 + 1 - n + {t_0(t_0-1) \over 2} \\
&= 1 + \left({t_0(t_0+1) \over 2} - n\right) \gt 0 \\
\end{align}$$, for that ${t_0(t_0+1) \over 2} \ge n$. Then $b \in \mathbb{N}$.

That's everything needed to show.