## SectionB.11A Total Order on Natural Numbers

Let $m,n\in \nonnegints\text{.}$ Define a binary relation $\le$ on $\nonnegints$ by setting $m\le n$ if and only if there exists a natural number $p$ so that $m+p=n\text{.}$

$\le$ is reflexive since $n+0=n$ and therefore $n\le n\text{,}$ for all $n\in \nonnegints\text{.}$ Next, we show that $\le$ is antisymmetric. Let $m,n\in\nonnegints$ and suppose that $m\le n$ and $n\le m\text{.}$ Then there exist natural numbers $p$ and $q$ so that $m+p=n$ and $n+q=m\text{.}$ It follows that

\begin{equation*} m+(p+q)= (m+p)+q=n+q =m=m+0 \end{equation*}

Therefore $p+q=0\text{,}$ which implies that $p=q=0\text{.}$ Thus $m+p=m+0=m=n\text{.}$

Next, we show that $\le$ is transitive. Suppose that $m,n,p\in \nonnegints\text{,}$ $m\le n$ and $n\le p\text{.}$ Then there exist natural numbers $q$ and $r$ so that $m+q=n$ and $n+r=p\text{.}$ Then

\begin{equation*} m+(q+r)=(m+q)+r=n+r=p. \end{equation*}

Thus $m\le p\text{,}$ and we have now shown that $\le$ is a partial order on $\nonnegints\text{.}$

Finally, we show that $\le$ is a total order. To accomplish this, we choose an arbitrary element $m\in\nonnegints$ and show that for every $n\in\nonnegints\text{,}$ either $m\le n$ or $n\le m\text{.}$ We do this by induction on $n\text{.}$ Suppose first that $n=0\text{.}$ Since $0+m=m\text{,}$ we conclude that $0\le m\text{.}$ Now suppose that for some $k\in\nonnegints\text{,}$ we have $m\le k\text{.}$ Then there is a natural number $p$ so that $m+p=k\text{.}$ Then $m+(p+1) =(m+p)+1=k+1\text{,}$ so $m\le k+1\text{.}$

On the other hand, suppose that for some $k\in\nonnegints\text{,}$ we have $k\le m\text{.}$ If $k=m\text{,}$ then $m\le k$ and $m\le k+1$ as above. Now suppose that $k\le m$ and $k\neq m\text{.}$ Since $k\le m\text{,}$ there exists a natural number $p$ so that $k+p=m\text{.}$ Since $k\neq m\text{,}$ we know $p\neq 0\text{.}$ Therefore, there is a natural number $q$ so that $p=q+1\text{.}$ Then $m=k+p=k+(q+1)=(k+1)+q$ which shows that $k+1\le m\text{.}$

Note that if $m,n\in\nonnegints\text{,}$ then $m\lt n$ if and only if there exists a natural number $p\neq 0$ so that $m+p=n\text{.}$

It suffices to prove that if $m,n\in \nonnegints$ with $m\lt n\text{,}$ then $m+p\lt n+p$ for every $p\in\nonnegints\text{.}$ Let $q\neq0$ be the natural number so that $m+q =n\text{.}$ Now let $p\in \nonnegints\text{.}$ Then $(m+p)+q=(m+q)+p=n+p\text{,}$ so $m+p \lt n+p\text{.}$

Assume to the contrary, that $m,n\in \nonnegints\text{,}$ $m\neq0\text{,}$ $n\neq0$ and $mn=0\text{.}$ Let $n=s(p)\text{.}$ Then $0=mn= ms(p)+m$ which requires $m=0\text{.}$ This is a contradiction.

Only the last statement requires proof. Let $m,n\in\nonnegints$ with $m\lt n\text{.}$ Then $m+q=n$ for some $q\neq0\text{.}$ Then $np=(m+q)p=mp+pq\text{.}$ Since $pq\neq0\text{,}$ we conclude $mp\lt np\text{.}$

If $m\lt n\text{,}$ then $mp\lt np\text{,}$ and if $n\lt m\text{,}$ then $np\lt mp\text{.}$ We conclude that $m=n\text{.}$