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

Exercise 2.2.3

Prove Proposition 2.2.12.

Proposition 2.2.12 (basic properties of order for natural numbers):

Let $a, b, c$ be natural numbers. Then

(a) (Order is reflexive) $a\ge a$.

(b) (Order is transitive) If $a\ge b$ and $b\ge c$, then $a\ge c$.

(c) (Order is antisymmetric) If $a\ge b$ and $b\ge a$, then $a=b$.

(d) (Addition preserves order) $a\ge b$ if and only if $a+c\ge b+c$.

(e) $a<b$ if and only if $a++\le b$.

(f ) $a<b$ if and only if $b=a+d$ for some positive number $d$.

(a) By Definition 2.2.11 (ordering of the natural numbers) we have $a\ge a$ if and only if $a=a+x$ for some natural number $x$. 

To show $a\ge a$, it is sufficient to show $a=a+x$ is true for some natural number $x$. Choosing $x=0$ gives $a=a+0$. By the symmetry axiom of equality this is $a+0=a$, which is indeed true by Lemma 2.2.2. 

We have shown $a=a+x$ is true for some natural number $x$, and so by Definition 2.2.11 we conclude $a\ge a$. 

(b) By Definition 2.2.11 (ordering of the natural numbers) we have $a\ge b$ if and only if $a=b+x$ for some natural number $x$, and $b\ge c$ if and only if $b=c+y$ for some natural number $y$. 

Together we have $a=(c+y)+x$ for some natural numbers $x,y$. By Proposition 2.2.5 (addition is associative), we have $a=c+(y+x)$. The sum of two natural numbers, $x$ and $y$, is also a natural number $x+y$. By Definition 2.2.11 this means $a\ge c$. 

For completeness we should prove the sum of two natural numbers is a natural number. We'll use induction. Let $P(a)$ be the statement that the sum $a+b$ of natural numbers $a$ and $b$ is also a natural number. We need to show the base case $P(0)$, and the inductive step $P(a)\implies P(a++)$. The base case $P(0)$ states $0+b$ is a natural number. Definition 2.2.1 (addition of natural numbers) tells us $0+b:=b$ where $b$ is a natural number, and so the base case is true. For the inductive step we need to show $P(a++)$, assuming $P(a)$. That is, we want to show $(a++)+b$ is a natural number. Again by Definition 2.2.1, we have $(a++)+b:=(a+b)++$. The assumption $P(a)$ tells us $(a+b)$ is a natural number, and Axiom 2.2 tells us $(a+b)++$ is a natural number, proving the inductive step. So by induction we have shown the sum of two natural numbers is a natural number.

(c) By Definition 2.2.11 (ordering of the natural numbers) we have $a\ge b$ if and only if $a=b+x$ for some natural number $x$. By the same definition we have $b\ge a$ if and only if $b=a+y$ for some natural number $y$. 

Together this means $a=(a+y)+x$ for some natural numbers $x,y$. By Proposition 2.2.5 (addition is associative), we have $a=a+(y+x)$. Intuitively we can see $x$ and $y$ must both be zero. Let's show this.

By Proposition 2.2.6 (cancellation law) this gives $0=y+x$. The symmetry axiom of equality gives us $y+x=0$. Corollary 2.2.9 tells us that both $x=0$ and $y=0$.

Substituting $x=0$ into $a=b+x$ gives us $a=b+0$. Lemma 2.2.2 tells us $b+0=b$ which finally gives us $a=b$.

(d) We need to show both $a\ge b\implies a+c\ge b+c$ and $a\ge b\impliedby a+c\ge b+c$.

$(\implies)$

By Definition 2.2.11 (ordering of the natural numbers) we have $a\ge b\implies a=b+x$ for some natural number $x$.

By the substitution axiom of equality, $a=b+x$ means $a+c=(b+x)+c$, for some natural number $c$. By Proposition 2.2.5 (addition is associative) we have $a+c=b+(x+c)$. Proposition 2.2.4 (addition is commutative) gives us $a+c=b+(c+x)$. Applying Proposition 2.2.5 again gives us $a+c=(b+c)+x$. By Definition 2.2.11 this means $a+c\ge b+c$, and so we have shown $a\ge b\implies a+c\ge b+c$.

$(\impliedby)$

By Definition 2.2.11 (ordering of the natural numbers) we have $a+c\ge b+c\implies a+c=(b+c)+y$ for some natural number $y$. Proposition 2.2.4 (addition is commutative) we have $c+a=(c+b)+y$. Proposition 2.2.5 (addition is associative) then gives us $c+a=c+(b+y)$. The Proposition 2.2.6 (cancellation law) reduces this to $a=b+y$, which by Definition 2.2.11 means $a\ge b$, and so we have shown $a+c\ge b+c\implies a\ge b$.

By showing both $a\ge b\implies a+c\ge b+c$ and $a+c\ge b+c\implies a\ge b$, we have shown $a\ge b\iff a+c\ge b+c$.

(e) We need to show both $a<b\implies a++\le b$ and $a<b\impliedby a++\le b$.

$(\implies)$

By Definition 2.2.11 (ordering of the natural numbers) $a<b$ implies both $b=a+x$ for some natural number $x$, and $b\ne a$. 

For the purpose of contradiction let's assume $x=0$. This would mean $b=a+0$, which by Lemma 2.2.2 gives $b=a$. This contradicts $b\ne a$. And so $x\ne0$, that is, $x$ is a positive number.

By Lemma 2.2.10 there exists a unique natural number $y$ such that $y++=x$. This gives us $b=a+(y++)$. By Lemma 2.2.3 this is $b=(a+y)++$, and by Definition 2.2.1 (addition of natural numbers) this is $b=(a++)+y$. By Definition 2.2.11 this means $a++\le b$, and so we have shown $a<b\implies a++\le b$.

$(\impliedby)$

By Definition 2.2.11 (ordering of the natural numbers) $a++\le b$ implies $b=(a++)+x$ for some natural number $x$. 

Definition 2.2.1 gives us $b=(a+x)++$, and by Lemma 2.2.3 this is $b=a+(x++)$. 

For the purpose of contradiction let's assume $a=b$. This would mean $b=b+(x++)$, and by Definition 2.2.1 this is $0+b=b+(x++)$. The symmetry axiom of equality gives us $b+0=b+(x++)$. Proposition 2.2.6 (cancellation law) then gives us $0=x++$. This contradicts Axiom 2.3, and so $a\ne b$. 

By Definition 2.2.11, having both $b=a+(x++)$ and $a\ne b$ means $a<b$, and so we have shown $a++\le b\implies a<c$.

By showing both $a<b\implies a++\le b$ and $a++\le b\implies a<c$, we have shown $a<b\iff a++\le b$.

(f) We need to show both $a<b\implies b=a+d$ and $a<b\impliedby b=a+d$, where $d$ is a positive number.

$(\implies)$

By Definition 2.2.11 (ordering of the natural numbers) $a<b$ implies both $b=a+d$ for some natural number $d$, and $b\ne a$. 

For the purpose of contradiction let's assume $d=0$. This would mean $b=a+0$, which by Lemma 2.2.2 gives $b=a$. This contradicts $b\ne a$. And so $d\ne0$, that is, $d$ is a positive number.

We have shown that $a<b\implies b=a+d$, where $d$ is a positive number.

$(\impliedby)$

For the purpose of contradiction let's assume $b=a$. This would mean $a=a+d$, which by Definition 2.2.1 (addition of natural numbers) is gives $0+a=a+d$. By the symmetry axiom of equality, this is $a+0=a+d$. Applying Proposition 2.2.6 (cancellation law) then gives $0=d$, which is $d=0$ by the symmetry axiom of equality. This contradicts $d$ being a positive number. And so $b\ne a$. 

Applying Definition 2.2.1 to $b=a+d$ and $b\ne a$ gives us $a<b$, and so we have shown $b=a+d\implies a<c$, where $d$ is a positive number.

By showing both $a<b\implies b=a+d$ and $b=a+d\implies a<c$, where $d$ is a positive number, we have shown $a<b\iff b=a+d$.

Exercise 2.2.2

Prove Proposition 2.2.10.

Lemma 2.2.10:: 

Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b++=a$.

Let $S(a)$ be the statement "if $a$ is a positive number then there exists exactly one natural number $b$ such that $b++=a$". We will use induction on $a$.

We need to show the base case $S(0)$, and the inductive step $S(a)\implies S(a++)$.

Base Case

We need to show that if $0$ is a positive number then there exists exactly one natural number $b$ such that $b++=0$.

However, 0 is not a positive number, and so the base case is vacuously true.

Inductive Step

We assume $S(a)$ and aim to show $S(a++)$, if $a++$ is a positive number then there exists exactly one natural number $b$ such that $b++=(a++)$. We need to show both the existence and uniqueness of $b$.

Since $a++$ exists so does $a$. We set $b=a$. By the substitution axiom of equality, we have $b++=a++$. And so at least one $b$ exists such that $b++=a++$. 

For the purpose of contradiction, let's assume a natural number $b'$, distinct from $b$, also satisfies $b'++=a++$. By Axiom 2.4 this would mean $b'=a$, contradicting that $b'$ is distinct from $b$. This means there is at most one natural number $b$, specifically $b=a$, such that $b++=(a++)$.

By showing there is at least one $b$, and at most one $b$, that satisfies $b++=a++$, we have shown there is exactly one $b$ such that $b++=a++$, proving the inductive step.

Note that we didn't require the induction hypothesis, $S(a)$.

By showing the base case and the inductive step, we have proved thatfor any positive number $a$, there exists only one natural number $b$ such that $b++=a$.

Exercise 2.2.1

Prove Proposition 2.2.5.

Proposition 2.2.5 (addition is associative). 

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

We will use induction on $a$, keeping $b$ and $c$ fixed. We need to show the base case $(0+b)+c=0+(b+c)$ and the inductive step

$$ (a+b)+c=a+(b+c)\implies((a++)+b)+c=(a++)+(b+c) $$

Base Case

By Definition 2.2.1, we have $0+b:=b$, and also $0+(b+c):=(b+c)$.

And so

$$  (0+b)+c  = b+c  = 0+(b+c) $$

And so we have shown the base case $(0+b)+c=0+(b+c)$.

Inductive Step

We assume $(a+b)+c=a+(b+c)$, and aim to show $((a++)+b)+c=(a++)+(b+c)$.

By Definition 2.2.1, we have $(a++)+b:=(a+b)++$, and $((a+b)++)+c:=((a+b)+c)++$, and also $(a++)+(b+c):=(a+(b+c))++$.

And so

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

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

Exercise A.7.1

Suppose you have four real numbers $a,b,c,d$ and you know that $a=b$ and $c=d$.

Use the above four axioms to deduce that $a+d=b+c$.

The four axioms of equality are

1. Reflexivity. $x=x$
2. Symmetry. $x=y\implies y=x$
3. Transitivity. $x=y\land y=z\implies x=z$
4. Substitution. $x=y\implies f(x)=f(y)$

Since $c=d$, by the axiom of symmetry, we have $d=c$. Let's create a function $f(x)=a+x$. By axiom of substitution, since $d=c$, we have$f(d)=f(c)$, that is, $a+d=a+c$.

Let's create another function $g(x)=x+c$. By the axiom of substitution, since $a=b$, we have $f(a)=f(b)$, that is, $a+c=b+c$.

By the axiom of transitivity, $a+d=a+c$ and $a+c=b+c$ gives us $a+d=b+c$, the desired conclusion.

Exercise A.5.1

What does each of the following statements mean, and which of them are true? Can you find gaming metaphors for each of these statements?

(a) For every positive number $x$, and every positive number $y$, we have $y^{2}=x$.

(b) There exists a positive number $x$ such that for every positive number $y$, we have $y^{2}=x$.

(c) There exists a positive number $x$, and there exists a positive number $y$, such that $y^{2}=x$.

(d) For every positive number $y$, there exists a positive number $x$ such that $y^{2}=x$.

(e) There exists a positive number $y$ such that for every positive number $x$, we have $y^{2}=x$.

(a) The statement means that every positive number is the square of every positive number. This is false. 

In a game, an adversarial opponent picks both $x$ and $y$ from the set of positive numbers, and we have to show that $y^{2}=x$ holds no matter what the opponent chooses. We may be lucky and show that $y^{2}=x$ in some games, but we won't be able to do it for all possible choices for $x$ and $y$.

(b) The statement means that there is a positive number that is the square of every positive number. This is false.

In a game, we first pick a positive number $x$ and the adversarial opponent freely picks $y$ from the set of positive numbers. We can't pick a special $x$ such that $y^{2}=x$ no matter what the opponent chooses for $y$. 

(c) The statement means some positive numbers are the square root of some others. This is true. 

In a game, the adversarial opponent plays no part. We have complete control in picking positive numbers $x$ and $y$ to ensure $y^{2}=x$.

(d) The statement means that every positive number has a square. This is true.

In a game, the adversarial opponent first picks a positive number $y$. We then get to choose a number $x$ that is the square of $y$, to ensure $y^{2}=x$. 

(e) The statement means there is a positive number that is the square root of every positive number. This is false.

In a game, we first choose a positive number $y$, and then an adversarial opponent picks $x$ from the set of positive numbers. We may be lucky and show that $y^{2}=x$ in some games, but we won't be able to do it for all possible choices for $x$ our opponent makes.

Exercise A.1.6

Suppose you know that whenever $X$ is true, then $Y$ is true; that whenever $Y$ is true, then $Z$ is true; and whenever $Z$ is true, then $X$ is true. Is this enough to show that $X,Y,Z$ are all logically equivalent? Explain.

To show that X,Y,Z are all logically equivalent, we need to show logical equivalence between all three variables, X\iff Y, Y\iff Z, X\iff Z.

We are given that whenever $X$ is true, then $Y$ is true. This is $X\implies Y$.

We are given that whenever $Y$ is true, then $Z$ is true. This is $Y\implies Z$.

We are given that whenever $Z$ is true, then $X$ is true. This is $Z\implies X$.

To show $X\iff Y$ we need to show both $X\implies Y$ and $Y\implies X$. We are given $X\implies Y$. If $Y$ is true, then by $Y\implies Z$, we know $Z$ is true. Since $Z$ is true, then by $Z\implies X$, we know $X$ is true. From $Y$ we have shown $X$, that is $Y\implies X$. So we have shown $X\iff Y$.

To show $Y\iff Z$ we need to show both $Y\implies Z$ and $Z\implies Y$. We are given $Y\implies Z$. If $Z$ is true, then by $Z\implies X$, we know $X$ is true. Since $X$ is true, then by $X\implies Y$, we know $Y$ is true. From $Z$ we have shown $Y$, that is $Z\implies Y$. So we have shown $Y\iff Z$.

To show $X\iff Z$ we need to show both $X\implies Z$ and $Z\implies X$. We are given $Z\implies X$. If $X$ is true, then by $X\implies Y$, we know $Y$ is true. Since $Y$ is true, then by $Y\implies Z$, we know $Z$ is true. From $X$ we have shown $Z$, that is $X\implies Z$. So we have shown $Y\iff Z$.

By showing all three $X\iff Y$, $Y\iff Z$, and $X\iff Z$, we have shown $X,Y,Z$ are all logically equivalent.

Exercise A.1.5

Suppose you know that $X$ is true if and only if $Y$ is true, and you know that $Y$ is true if and only if $Z$ is true. Is this enough to show that $X,Y,Z$ are all logically equivalent? Explain.

To show that $X,Y,Z$ are all logically equivalent, we need to show logical equivalence between all three variables, $X\iff Y$, $Y\iff Z$, $X\iff Z$.

The first $X\iff Y$ is given to us as $X$ is true if and only if $Y$ is true. 

The second $Y\iff Z$ is given to us as $Y$ is true if and only if $Z$ is true.

The third $X\iff Z$ is not given to us. To show $X\iff Z$ we need to show both $X\implies Z$ and $Z\implies X$.

If $X$ is true, then by $X\iff Y$ we know $Y$ is true. Since $Y$ is true, then by $Y\iff Z$ we know $Z$ is true. From $X$ we have shown $Z$, that is, $X\implies Z$.

If $Z$ is true, then by $Y\iff Z$ we know $Y$ is true. Since $Y$ is true, then by $X\iff Y$ we know $X$ is true. From $Z$ we have shown $X$, that is, $Z\implies X$.

By showing both $X\implies Z$ and $Z\implies X$, we have shown $X\iff Z$, and this completes the requirements to show $X,Y,Z$ are all logically equivalent.

Exercise A.1.4

Suppose that you have shown that whenever $X$ is true, then $Y$ is true, and whenever $Y$ is false, then $X$ is false. Have you now demonstrated that $X$ is true if and only if $Y$ is true? Explain.

To show that $X$ and $Y$ are logically equivalent, $X\iff Y$, we need to show both $X\implies Y$ and $Y\implies X$.

Demonstrating that whenever $X$ is true, then $Y$ is true, is equivalent to demonstrating $X\implies Y$. 

$X\implies Y$ is equivalent to $\neg Y\implies\neg X$. Demonstrating that whenever $Y$ is false, then $X$ is false, is again showing $X\implies Y$, and not the required $Y\implies X$.

So we have not demonstrated that $X$ and $Y$ are logically equivalent.

Exercise A.1.3

Suppose that you have shown that whenever $X$ is true, then $Y$ is true, and whenever $X$ is false, then $Y$ is false. Have you now demonstrated that $X$ and $Y$ are logically equivalent? Explain.

To show that $X$ and $Y$ are logically equivalent, $X\iff Y$, we need to show both $X\implies Y$ and $Y\implies X$.

Demonstrating that whenever $X$ is true, then $Y$ is true, is equivalent to demonstrating $X\implies Y$. 

We're given that whenever $X$ is false, then $Y$ is false. This $\neg X\implies\neg Y$ is logically equivalent to $Y\implies X$.

So we have demonstrated that $X$ and $Y$ are indeed logically equivalent.

Exercise A.1.2

What is the negation of the statement “$X$ is true if and only if $Y$ is true”? (There may be multiple ways to phrase this negation.)

The statement is equivalent to $X\iff Y$, which we have just seen is the negation of “either $X$ is true, or $Y$ is true, but not both”. And so the negation of the given statement is “either $X$ is true, or $Y$ is true, but not both”. Stated more simply, $X\ne Y$.

Exercise A.1.1

What is the negation of the statement “either X is true, or Y is true, but not both”?

When $X$ and $Y$ are both true, the statement is false, so its negation must be true.

When $X$ and $Y$ are both false, the statement is false, so its negation must be true.

When exactly one of $X$ and $Y$ is true, the statement is true, so its negation must be false.

These observations lead us to the negation “either $X$ and $Y$ are both true, or $X$ and $Y$ are both false”. This can be stated more simply as $X=Y$ or $X\iff Y$.