Exercise 2.3.4

Prove the identity $(a+b)^{2}=a^{2}+2ab+b^{2}$ for all natural numbers $a,b$.

The following derivation aims to justify every step and avoid seemingly obvious jumps.

$$ \begin{alignat*}{3} (a+b)^{2} & =(a+b)^{1++} & \hspace{4cm} & & {1++=2}\\ \\ & =(a+b)^{1}\times(a+b) & \hspace{4cm} & & \text{Definition 2.3.11}\\ \\ & =(a+b)^{0++}\times(a+b) & \hspace{4cm} & & {0++=1}\\ \\ & =(a+b)^{0}\times(a+b)\times(a+b) & \hspace{4cm} & & \text{Definition 2.3.11}\\ \\ & =1\times(a+b)\times(a+b) & \hspace{4cm} & & \text{Definition 2.3.11}\\ \\ & =(0++)\times(a+b)\times(a+b) & \hspace{4cm} & & {0++=1}\\ \\ & =((0\times(a+b)\times(a+b))+(a+b)\times(a+b) & \hspace{4cm} & & \text{Definition 2.3.1}\\ \\ & =(a+b)\times(a+b) & \hspace{4cm} & & \text{Definition 2.3.1}\\ \\ & =a\times(a+b)+b\times(a+b) & \hspace{4cm} & & \text{Proposition 2.3.4}\\ \\ & =a\times a+a\times b+b\times a+b\times b & \hspace{4cm} & & \text{Proposition 2.3.4}\\ \\ & =a\times a+a\times b+a\times b+b\times b & \hspace{4cm} & & \text{Lemma 2.3.2}\\ \\ & =a^{2}+(a\times b)+(a\times b)+b^{2} & \hspace{4cm} & & \text{Definition 2.3.11}\\ \\ & =a^{2}+(ab)+(ab)+b^{2} & \hspace{4cm} & & {a\times b=ab}\\ \\ & =a^{2}+(0+ab)+ab+b^{2} & \hspace{4cm} & & \text{Definition 2.2.1}\\ \\ & =a^{2}+(0\times ab+ab)+ab+b^{2} & \hspace{4cm} & & \text{Definition 2.3.1}\\ \\ & =a^{2}+((0++)\times ab)+ab+b^{2} & \hspace{4cm} & & \text{Definition 2.3.1}\\ \\ & =a^{2}+(1\times ab+ab)+b^{2} & \hspace{4cm} & & {0++=1}\\ \\ & =a^{2}+((1++)\times ab)+b^{2} & \hspace{4cm} & & \text{Definition 2.3.1}\\ \\ & =a^{2}+2ab+b^{2} & \hspace{4cm} & & {1++=2}\end{alignat*} $$

Exercise 2.3.3

Prove Proposition 2.3.5.

Proposition 2.3.5 (multiplication is associative). 

For any natural numbers $a$, $b$, $c$, we have $(a\times b)\times c=a\times(b\times c)$.

We will prove this by induction on $a$, holding $b$ and $c$ fixed. Let $S(a)$ be the statement that $(a\times b)\times c=a\times(b\times c)$ for any natural numbers $a$, $b$, $c$. We need to prove the base

case $S(0)$ and the implication step $S(a)\implies S(a++)$.

Base Case

The base case $S(0)$ states that $(0\times b)\times c=0\times(b\times c)$. By Definition 2.3.1, the expression $0\times(b\times c)$ is identically zero. Definition 2.3.1 also gives $(0\times b)=0$, which means $(0\times b)\times c=0\times c=0$. And so the base case is true.

Induction Step

We need to show $S(a++)$, that is, $((a++)\times b)\times c=(a++)\times(b\times c)$. We assume $S(a),$ that is, $(a\times b)\times c=a\times(b\times c)$. We proceed as follows

$$\begin{alignat*}{3} ((a++)\times b)\times c & =((a\times b)+b)\times c & \hspace{4cm} & & \text{Definition 2.3.1}\\ \\  & =((a\times b)\times c)+(b\times c) & \hspace{4cm} & & \text{Proposition 2.3.4}\\ \\ & =(a\times(b\times c))+(b\times c) & \hspace{4cm} & & \text{induction hypothesis}\\ \\  & =(a++)\times(b\times c) & \hspace{4cm} & & \text{Definition 2.3.1} \end{alignat*}$$

By showing the base case and the induction step, we have proved that $(a\times b)\times c=a\times(b\times c)$ for any natural numbers.

Exercise 2.3.2

Prove Lemma 2.3.3.

Lemma 2.3.3 (positive natural numbers have no zero divisors):

Let $n$, $m$ be natural numbers. Then $n\times m=0$ if and only if at least one of $n$, $m$ is equal to zero. In particular, if $n$ and $m$ are both positive, then $nm$ is also positive.

We need to prove both implications:

• if $n\times m=0$ then at least one of $n,m$ is zero
• if at least one of $n,m$ is zero then $n\times m=0$

$(\implies)$

We will prove the logically equivalent contrapositive ``if $n$ and $m$ are both positive, then $nm$ is also positive''. 

Since $n$ is positive, by Lemma 2.2.10 there exists a unique natural number $x$ such at that $x++=n$. And so $nm=(x++)\times m$. By Definition 2.3.1 (multiplication of natural numbers) this is $nm=(x\times m)+m$. By Proposition 2.2.8, since $m$ is a positive number, then the sum $nm=(x\times m)+m$ is also positive. 

By proving the contrapositive, we have proven the implication that if $n\times m=0$ then at least one of $n,m$ is zero.

$(\impliedby)$

There are two cases to consider, $n=0$ and $m=0$. In the first case $n=0$, Definition 2.3.1 immediately gives us $0\times m=0$. In the second case $m=0$, by Lemma 2.3.2 (multiplication is commutative) and Definition 2.3.1 we have $n\times0=0\times n=0$. 

In both cases $nm=0$, proving the implication that if at least one of $n,m$ is zero then $n\times m=0$.

By showing both implications, we have proved that $n\times m=0$ if and only if at least one of $n, m$ is equal to zero, for natural numbers $m, n$.

Exercise 2.3.1

Prove Lemma 2.3.2. 

Lemma 2.3.2 (multiplication is commutative):

Let $n,m$ be natural numbers. Then $n\times m=m\times n$.

We will prove this by inducting on $n$, keeping $m$ fixed. Let $S(n)$ be the statement that $n\times m=m\times n$ for natural numbers $n,m$. We need to show the base case $S(0)$ and the induction step $S(n)\implies S(n++)$.

Our proof will require two useful results, which we'll prove first.

Lemma A. $m\times0=0$ for any natural number $m$. We will prove this by induction on $m$. Let $A(m)$ be the statement $m\times0=0$. We need to prove the base case $A(0)$ and the induction step $A(m)\implies A(m++)$. The base case $0\times0=0$ is true by Definition 2.3.1 (multiplication of natural numbers). For the induction step we assume $m\times0=0$, and aim to show $(m++)\times0=0$. Also by Definition 2.3.1 $(m++)\times0=(m\times0)+0$. The induction hypothesis gives us is $(m++)\times0=(0)+0=0$, and so the induction step is true. By induction we have shown $m\times0=0$ for any natural number $m$.

 

Lemma B. $m\times(n++)=(m\times n)+m$ for natural numbers $m,n$. We will prove this by induction on $m$, keeping $n$ fixed. Let $B(m)$ be the statement $m\times(n++)=(m\times n)+m$. We need to prove the base case $B(0)$ and the induction step $B(m)\implies B(m++)$. The base case states $0\times(n++)=(0\times n)+0$. By Definition 2.3.1, $0\times(n++)=0$. By the same definition, $(0\times n)+0=(0)+0=0$. So the base case is true. For the induction step we assume $m\times(n++)=(m\times n)+m$, and aim to show $(m++)\times(n++)=((m++)\times n)+(m++)$. We proceed as follows

$$\begin{alignat*}{3} (m++)\times(n++) & =(m\times(n++))+(n++) & \hspace{4cm} &  & \text{Definition 2.3.1}\\ & =((m\times n)+m)+(n++) & \hspace{4cm} &  & \text{induction hypothesis}\\ & =((m\times n)+(m+(n++)) & \hspace{4cm} &  & \text{Proposition 2.2.5}\\ & =((m\times n)+((m+n)++) & \hspace{4cm} &  & \text{Lemma 2.2.3}\\ & =((m\times n)+((n+m)++) & \hspace{4cm} &  & \text{Proposition 2.2.4}\\ & =(m\times n)+(n+(m++)) & \hspace{4cm} &  & \text{Lemma 2.2.3}\\ & =((m\times n)+n)+(m++) & \hspace{4cm} &  & \text{Proposition 2.2.5}\\ & =((m++)\times n)+(m++) & \hspace{4cm} &  & \text{Definition 2.3.1} \end{alignat*}$$

By induction we have shown $m\times(n++)=(m\times n)+m$ for natural numbers $m,n$.

Base Case

The base case $S(0)$ states that $0\times m=m\times0$. By Definition 2.3.1 (multiplication of natural numbers) $0\times m:=0$. By Lemma A, which we just proved, $m\times0=0$. And so the base case is true.

Induction Step

The induction step is $S(n)\implies S(n++)$. We assume $n\times m=m\times n$ and aim to show $(n++)\times m=m\times(n++)$. 

We proceed as follows

$$  \begin{alignat*}{3} (n++)\times m & =(n\times m)+m & \hspace{4cm} &  & \text{Definition 2.3.1} \\ \\  & =(m\times n)+m  & \hspace{4cm} &  & \text{induction hypothesis} \\ \\   &=m\times(n++)  & \hspace{4cm} &  & \text{Lemma B} \end{alignat*}$$ 

By showing the base case and the induction step, we have shown that $n\times m=m\times n$ for natural numbers $m,n$.

Exercise 2.2.6

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $m\le n$; this is known as the principle of backwards induction.

We will prove the principle of backwards induction using simple induction. Let $Q(n)$ be the statement that $P(m)$ is true for all natural numbers $m\le n$ if $P(n)$ is true. We need to prove the base case $Q(0)$ and the induction step $Q(n)\implies Q(n++)$.

Base Case

The base case $Q(0)$ is the statement that $P(0)$ is true for all natural numbers $m\le0$ if $P(0)$ is true. Here $m=0$ is only one natural number less than or equal to zero. By assumption $P(0)$ is true, and so the base case $Q(0)$ is true.

Induction Step

We aim to show $Q(n++)$, that $P(m)$ is true for all $m\le n++$ if $P(n++)$ is true. The induction hypothesis is $Q(n)$, that $P(m)$ is true for all $m\le n$ if $P(n)$ is true.

A property of $P$ is that $P(n++)\implies P(n)$, and since $P(n++)$ is true by assumption, then $P(n)$ is true. By the induction hypothesis $P(n)$ is true for all $m\le n$. 

In total we have $P(n)$ true for $m\le n$ and $m=n++$. That is, $P(m)$ is true for $m\le n++$. This is $Q(n++)$, and so the induction step is true.

By proving the base case and the induction step, we have proved by simple induction $Q(n)$ is true for all natural numbers $n$. That is, $P(m)$ is true for all $m\le n$ if $P(n)$ is true.

Exercise 2.2.5

Prove Proposition 2.2.14.

Hint: define $Q(n)$ to be the property that $P(m)$ is true for all $m_{0}\le m<n$; note that $Q(n)$ is vacuously true when $n\le m_{0}$.

Proposition 2.2.14 (strong principle of induction).

Let $m_{0}$ be a natural number, and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m\ge m_{0}$, we have the following implication: if $P(m\prime)$ is true for all natural numbers $m_{0}\le m\prime<m$, then $P(m)$ is also true. (In particular, this means that $P(m_{0})$ is true, since in this case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m\ge m_{0}$.

Let $Q(n)$ be the statement that $P(m)$ is true for all $m_{0}\le m<n$. The figure below illustrates the relationship between $Q(n)$ and $P(m)$.

If we can prove that $Q(n)$ is true for all natural numbers $n$, that would mean $P(m)$ is true for all natural numbers $m\ge m_{0}$.

We'll use induction to show $Q(n)$ is true for all natural numbers $n$. We need to prove the base case $Q(0)$ and the induction step $Q(n)\implies Q(n++)$. 

Before proceeding, we'll note the following property of $P$ assumed by Proposition 2.2.14.

$$ P(m')\text{ where }m_{0}\le m'<m\implies P(m) \tag{i} $$

Base Case

The base case $Q(0)$ is the statement that $P(m)$ is true for all $m_{0}\le m<0$. This is vacuously true since there are no natural numbers less than 0.

Induction Step

We assume $Q(n)$ as the induction hypothesis, and aim to show $Q(n++)$.

$Q(n)$ true means $P(m)$ is true for all $m_{0}\le m<n$. By assumption (i) this means $P(n)$ is also true. And so we have $P(m)$ is true for $m_{0}\le m\le n$. This means $P(m)$ is true for $m_{0}\le m<n++$. This is equivalent to $Q(n++)$.

By showing the base case and the induction step, we have shown that $Q(n)$ is true for all natural numbers $n$. That is, $P(m)$ is true for all natural numbers $m\ge m_{0}$.

We should justify $m\le n\implies m<n++$. By Definition 2.2.11, $m\le n$ means $n=m+x$ for some natural number $x$. By the substitution axiom of equality $n++=(m+x)++$, which by Lemma 2.2.3 is $n++=m+(x++)$. For the purpose of contradiction let's assume $n++=m$. Definition 2.2.1 gives us $m+0=m+(x++)$. By Proposition 2.2.6 (cancellation law) we have $0=x++$, which contradicts Axiom 2.3. And so $n++\ne m$. By Definition 2.2.11, both $n++=m+(x++)$ and $n++\ne m$ means $m<n++$.

Exercise 2.2.4

Justify the three statements marked (why?) in the proof of Proposition 2.2.13.

Proposition 2.2.13 (trichotomy of order for natural numbers). 

Let $a$ and $b$ be natural numbers. Then exactly one of the following statements is true: $a<b$, $a=b$, or $a>b$.

The given proof first establishes that no more than one of the three statements can be true. It then shows at least one must be true, by inducting on $a$, keeping $b$ fixed.

First (why?)

For the first (why?) we need to show that $0\le b$ for all $b$.

By Definition 2.2.1 (addition of natural numbers) $0+b=b$. By the symmetry axiom of equality this is $b=0+b$. By Definition 2.2.11 (ordering of the natural numbers) this immediately gives $0\le b$. 

Second (why?)

For the second (why?) we need to show that if $a>b$ then $a++>b$. 

By Proposition 2.2.12(f) $a>b\iff a=b+x$ for some positive $x$. This means $a++=(b+x)++$. By Lemma 2.2.3 we have $a++=b+(x++)$. By Axiom 2.3 $x++\ne0$ is not 0, and so by Definition 2.2.7 (positive natural numbers) $x++$ is positive. 

Again by Proposition 2.2.12(f) $a++=b+(x++)$ where $x++$ is positive means $a++>b$.

Third (why?)

For the third (why?) we need to show that if $a=b$ then $a++>b$.

By the substitution axiom of equality $a=b$ means $a++=b++$. Using $b++=b+1$, this means $a++=b+1$. 

By Proposition 2.212(f) $a++=b+1$, noting that 1 is positive by Definition 2.2.7 because it is not 0, means $a++>b$.

We should justify $b++=b+1$. Definition 2.2.1 gives us $0+b=b$, which by the symmetry axiom of equality is $b=0+b$, and by Proposition 2.2.4 becomes $b=b+0$. By the substitution axiom of equality, $b++=(b+0)++$. By Lemma 2.2.3, $b++=b+(0++)$. Now, by definition $0++:=1$, and so we finally have $b++=b+1$.