## 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{.}$$