Prove $(\mathbb{N}\times\mathbb{N},\in_{cw}) \cong (\mathbb{N},<)$

Question

Note that $\in_{cw}$ is the canonical well-ordering of $\mathbb{N}\times\mathbb{N}$.
That is, $(m_1,n_1)\in_{cw}(m_2,n_2)$ if and only if
either $\max\{m_1,n_1\}<\max\{m_2,n_2\}$,
or $\max\{m_1,n_1\}=\max\{m_2,n_2\}$ and $m_1<m_2$,
or $\max\{m_1,n_1\}=\max\{m_2,n_2\}$ and $m_1\le m_2$ and $n_1<n_2$.

I'm trying to prove it in this way:

Define $f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ by:

$f(m,n)=m^2+m+n$ if $n\leq m$

$f(m,n)=n^2+m$ if $m<n$

Clearly, f is a bijection. It remains to show that $(m_1,n_1)\in_{cw}(m_2,n_2)$ if and only if $f(m_1,n_1)<f(m_2,n_2)$. How to do this?

Answer 1

Suppose that $a=\max\{m_1,n_1\}<\max\{m_2,n_2\}$; then

$$f(m_1,n_1)\le a^2+2a<(a+1)^2\le\big(\max\{m_2,n_2\}\big)^2\le f(m_2,n_2)\;.$$

Now suppose that $a=\max\{m_1,n_1\}=\max\{m_2,n_2\}$ and $m_1<m_2$. Then $n_1=a$, so

$$f(m_1,n_1)=a^2+m_1<a^2+m_2\le f(m_2,n_2)\;.$$

Finally, suppose that $a=\max\{m_1,n_1\}=\max\{m_2,n_2\}$, $m_1=m_2$, and $n_1<n_2$. Then $m_1=m_2=a$, and

$$f(m_1,n_1)=a^2+a+n_1<a^2+a+n_2=f(m_2,n_2)\;.$$

Thus, $f(m_1,n_1)<f(m_2,n_2)$ whenever $\langle m_1,n_1\rangle\in_{cw}\langle m_2,n_2\rangle$. It’s clear that $\in_{cw}$ is a strict linear order, so the result follows from the fact that $f$ is a bijection.