Applied Combinatorics

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

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