Skip to main content

Section B.11 A 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{.}\)

Proof.
\(\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{.}\)

Proof.
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{.}\)

Proof.
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.

Proof.
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{.}\)

Proof.
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{.}\)
You have attempted of activities on this page.
PrevTopNext