(D2.3.1) Multiplication of natural numbers. Let \(m\) be a natural number. We define \(0\times m=0\). Now if we know \(n\times m\), we define \((n\+)\times m=(n\times m)+m\).
(L2.3.2): Multiplication is commutative: \(m\times n=n\times m\)
Proof:
First, let’s show that \(m\times0=0\) via induction. It is easily true for \(m=0\). Let it be true for \(m\). Then \((\m+)\times0=(m\times0)+0=0+0=0\)
Another lemma: Let’s show that \(n\times(m\+)=(n\times m)+n\). Via induction: Fix \(m\) and induct on \(n\). Let \(n=0\). Then \(0\times(m\+)=0=(0\times m)+0\).
Let it be true for \(n\). Then \((n\+)\times(m\+)=(n\times(m\+))+(m\+)=((n\times m)+n)+(\m+)\). This equals \((n\times m)+(n+(m\+))=(n\times m)+(n+m)\+=(n\times m)+((n\+)+m)\) Use commutation of addition and associativity to get \(((n\times m)+m)+(n\+)=(n\+)\times m+(n\+)\).
Finally, getting to the commutation theorem. Fix \(m\) and induct on \(n\). The base case (\(n=0\)) is straightforward. Let it be true for \(n\). Then \((n\+)\times m=(n\times m)+m=(m\times n)+m=m\times(n\+)\)
(L2.3.3): Positive natural numbers have no zero divisors. If \(n,m\) are natural numbers, then \(n\times m=0\) iff at least one of them is equal to 0. If both are positive, then so is \(nm\).
Proof:
Fix \(m\) and induct on \(n\). For the base case, \(n=0\), the theorem is trivially true. Let it be true for a given \(n\) (i.e. \(nm=0\) implies one of them is 0). Consider \(((n\+)m)=0\). Then \(nm+m=0\). From C2.2.9, we know that \(nm=0\) and \(m=0\). We are done.
For the converse, if one of them is 0, then using commutation and the definition of multiplication, so is the product.
Let \(m,n\) be positive. We must have \(nm\) be positive as if it were 0, then one of them would be 0. A contradiction.
(P2.3.4). Let \(a,b,c\) be natural numbers. Then \(a(b+c)=ab+ac\) and \((b+c)a=ba+ca\).
Proof.
The second one follows from the first via commutativity of addition and multiplication. To prove the former, induct on \(a\). The case \(a=0\) is clear. Assume it is true that \(a(b+c)=ab+ac\). Then:
Use the induction hypothesis and rearrange terms (associativity and commutativity of addition) to get:
(P2.3.5): Multiplication is associative. Let \(a,b,c\) be natural numbers. Then \((ab)c=a(bc)\)
Proof.
Induct on \(c\). When \(c=0\), we have \(a(b\times 0)=a(0\times b)=a\times0=0\times a=0=0\times(ab)=(ab)\times0\).
Let it be true for \(c\). Evaluate \(a(b(c\+))\) and rearrange terms to get \((ab)c\+\).
(P2.3.6): Multiplication preserves order. If \(a,b\) are natural numbers and \(a<b\), and \(c\) is positive, then \(ac<ab\).
Proof:
\(a<b\) means \(b=a+d\) where \(d\ne0\). Then \(bc=(a+d)c=ac+dc\). Now \(dc\) cannot be 0 as neither is 0. Thus \(bc\ne ac\) and \(bc>ac\).
(C2.3.7): Cancellation Law: If \(a,b,c\) are natural numbers and \(c\ne0\), then \(ac=bc\) implies \(a=c\)
Proof:
Either \(a<b,a=b,a>b\). If \(a<b\), then \(ac<bc\) and \(ac\ne bc\). Likewise for \(a>b\). Thus \(a=b\).
(P2.3.9): Euclidean Algorithm. Let \(n\) be a natural number, and \(q\) be positive. There exist natural numbers \(m,r\) such that \(0\le r<q\) and \(n=mq+r\).
Proof:
Induct on \(n\). If \(n=0\), then \(m=r=0\). If it is true for \(n\), then \(n=mq+r\). Then \(n\+=(mq+r)\+=mq+(r\+)\). Now we know that if \(r<q\) then \(r\+\le q\). If \(r\+<q\) then we are done. If \(r++=q\) then \(n\+=mq+q=(m\+)q=(m\+)q+0\) and so \(r=0\).
(D2.3.11): Exponentiation. Let \(m\) be a natural number. Define \(m^{0}\) to be 1 (even when \(m=0\)). If \(m^{n}\) have been defined, recursively define \(m^{n\+}=m^{n}\times m\)
Finally, let’s prove a basic fact: \(n\times1=1\times n=n\)
Proof: \(1\times n=(0\+)\times n=0\times n+n=0+n=n\)
Let’s also prove that \((a+b)^{2}=a^{2}+2ab+b^{2}\)
Proof:
\((a+b)^{2}=(a+b)^{1}(a+b)=(a+b)^{0}(a+b)(a+b)=1\cdot(a+b)(a+b)=(a+b)(a+b)\)
We expand this out and manipulate to get the desired result.