Proposisi B.29.
\(\le\) merupakan urutan total pada \(\nonnegints\text{.}\)
Subbab B.11 Urutan Total pada Bilangan Asli
Misalkan \(m,n\in \nonnegints\text{.}\) Definisikan relasi biner \(\le\) pada \(\nonnegints\) dengan menetapkan bahwa \(m\le n\) jika dan hanya jika terdapat bilangan asli \(p\) sedemikian sehingga \(m+p=n\text{.}\)
Bukti.
\(\le\) bersifat refleksif karena \(n+0=n\text{,}\) sehingga \(n\le n\) untuk semua \(n\in \nonnegints\text{.}\) Selanjutnya, kita tunjukkan bahwa \(\le\) bersifat antisimetris. Misalkan \(m,n\in\nonnegints\) dan andaikan \(m\le n\) serta \(n\le m\text{.}\) Maka terdapat bilangan asli \(p\) dan \(q\) sedemikian sehingga \(m+p=n\) dan \(n+q=m\text{.}\) Akibatnya,
\begin{equation*}
m+(p+q)= (m+p)+q=n+q =m=m+0
\end{equation*}
Oleh karena itu, \(p+q=0\text{,}\) yang mengakibatkan \(p=q=0\text{.}\) Jadi, \(m+p=m+0=m=n\text{.}\)
Selanjutnya, kita tunjukkan bahwa \(\le\) bersifat transitif. Andaikan \(m,n,p\in \nonnegints\text{,}\) \(m\le n\text{,}\) dan \(n\le p\text{.}\) Maka terdapat bilangan asli \(q\) dan \(r\) sedemikian sehingga \(m+q=n\) dan \(n+r=p\text{.}\) Dengan demikian,
\begin{equation*}
m+(q+r)=(m+q)+r=n+r=p.
\end{equation*}
Jadi, \(m\le p\text{,}\) dan kita telah menunjukkan bahwa \(\le\) merupakan urutan parsial pada \(\nonnegints\text{.}\)
Terakhir, kita tunjukkan bahwa \(\le\) merupakan urutan total. Untuk itu, pilih sebarang unsur \(m\in\nonnegints\) dan tunjukkan bahwa untuk setiap \(n\in\nonnegints\text{,}\) berlaku \(m\le n\) atau \(n\le m\text{.}\) Kita menggunakan induksi pada \(n\text{.}\) Pertama, andaikan \(n=0\text{.}\) Karena \(0+m=m\text{,}\) kita menyimpulkan bahwa \(0\le m\text{.}\) Sekarang andaikan bahwa untuk suatu \(k\in\nonnegints\text{,}\) berlaku \(m\le k\text{.}\) Maka terdapat bilangan asli \(p\) sedemikian sehingga \(m+p=k\text{.}\) Jadi, \(m+(p+1) =(m+p)+1=k+1\text{,}\) sehingga \(m\le k+1\text{.}\)
Di sisi lain, andaikan bahwa untuk suatu \(k\in\nonnegints\text{,}\) berlaku \(k\le m\text{.}\) Jika \(k=m\text{,}\) maka \(m\le k\) dan, seperti di atas, \(m\le k+1\text{.}\) Sekarang andaikan bahwa \(k\le m\) dan \(k\neq m\text{.}\) Karena \(k\le m\text{,}\) terdapat bilangan asli \(p\) sedemikian sehingga \(k+p=m\text{.}\) Karena \(k\neq m\text{,}\) kita mengetahui bahwa \(p\neq 0\text{.}\) Oleh karena itu, terdapat bilangan asli \(q\) sedemikian sehingga \(p=q+1\text{.}\) Maka \(m=k+p=k+(q+1)=(k+1)+q\text{,}\) yang menunjukkan bahwa \(k+1\le m\text{.}\)
Perhatikan bahwa jika \(m,n\in\nonnegints\text{,}\) maka \(m\lt n\) jika dan hanya jika terdapat bilangan asli \(p\neq 0\) sedemikian sehingga \(m+p=n\text{.}\)
Teorema B.30. Hukum Kemonotonan Penjumlahan.
Misalkan \(m,n,p\in \nonnegints\text{.}\) Jika \(m\le n\text{,}\) maka \(m+p\le n+p\text{.}\) Selain itu, jika \(m\lt n\text{,}\) maka \(m+p\lt n+p\text{.}\)
Bukti.
Cukup dibuktikan bahwa jika \(m,n\in \nonnegints\) dengan \(m\lt n\text{,}\) maka \(m+p\lt n+p\) untuk setiap \(p\in\nonnegints\text{.}\) Misalkan \(q\neq0\) adalah bilangan asli yang memenuhi \(m+q =n\text{.}\) Sekarang misalkan \(p\in \nonnegints\text{.}\) Maka \((m+p)+q=(m+q)+p=n+p\text{,}\) sehingga \(m+p \lt n+p\text{.}\)
Lema B.31.
Jika \(m,n\in \nonnegints\text{,}\) \(m\neq0\text{,}\) dan \(n\neq0\text{,}\) maka \(mn\neq0\text{.}\)
Bukti.
Andaikan sebaliknya bahwa \(m,n\in \nonnegints\text{,}\) \(m\neq0\text{,}\) \(n\neq0\text{,}\) dan \(mn=0\text{.}\) Misalkan \(n=s(p)\text{.}\) Maka \(0=mn= ms(p)+m\text{,}\) yang mengharuskan \(m=0\text{.}\) Ini sebuah kontradiksi.
Teorema B.32. Hukum Kemonotonan Perkalian.
Misalkan \(m,n,p\in \nonnegints\text{.}\) Jika \(m\le n\text{,}\) maka \(mp\le np\text{.}\) Selain itu, jika \(m\lt n\) dan \(p\neq0\text{,}\) maka \(mp\lt np\text{.}\)
Bukti.
Hanya pernyataan terakhir yang perlu dibuktikan. Misalkan \(m,n\in\nonnegints\) dengan \(m\lt n\text{.}\) Maka \(m+q=n\) untuk suatu \(q\neq0\text{.}\) Dengan demikian, \(np=(m+q)p=mp+pq\text{.}\) Karena \(pq\neq0\text{,}\) kita menyimpulkan bahwa \(mp\lt np\text{.}\)
Akibat B.33. Hukum Pembatalan Perkalian.
Jika \(m,n,p\in \nonnegints\text{,}\) \(mp=np\text{,}\) dan \(p\neq 0\text{,}\) maka \(m=n\text{.}\)
Bukti.
Jika \(m\lt n\text{,}\) maka \(mp\lt np\text{,}\) dan jika \(n\lt m\text{,}\) maka \(np\lt mp\text{.}\) Kita menyimpulkan bahwa \(m=n\text{.}\)
