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?

  • 3
    $\begingroup$ What does it mean "canonical well ordering"? $\endgroup$ – Asaf Karagila Dec 4 '13 at 20:00
  • 1
    $\begingroup$ @Asaf: I was just about to post the well-ordering, which can be inferred from the definition of $f$, but the OP beat me to it. $\endgroup$ – Brian M. Scott Dec 4 '13 at 20:19

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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.