Exercise 4.26

Let \(n,m,k\in\mathbb{N}\), prove the following directly from the definitions.

1. \(n+1 = S(n)\).

Proceed via induction on \(n\).

Base case.

\(0 + 1 = 1\) by definition of \(+\), and \(S(0) = 1\) by definition of \(1\).

Induction.

Suppose \(n + 1 = S(n)\), want \(S(n) + 1 = S(S(n))\). \[\begin{align*} S(n) + 1 &= S(n + 1) \tag*{definition of $+$} \\ &= S(S(n)) \tag*{inductive hypothesis \quad$\square$} \end{align*}\]

2. \(n + (m + k) = (n + m) + k\)

Induction on \(n\).

Base case.

\(0 + (m + k) = m + k\) by definition of \(+\). \((0 + m) + k = m + k\) also by definition of \(+\).

Induction.

Suppose \(n + (m + k) = (n + m) + k\), want \(S(n) + (m + k) = (S(n) + m) + k\). We have \[\begin{align*} S(n) + (m + k) &= S(n + (m + k)) \tag*{by definition of $+$} \\ &= S((n + m) + k) \tag*{inductive hypothesis} \\ &= S(n + m) + k \tag*{definition of $+$} \\ &= (S(n) + m) + k \tag*{definition of $+$} \end{align*}\] The induction is complete.

Notation. Brackets can now be liberally omitted for equations containing \(+\).

3. \(n + m = m + n\)

Lemma (plus 0). \(m = m + 0\) for any \(m\in \mathbb{N}\).

Proof. Proceed by induction on \(m\).

Base case.

\(0 + 0 = 0\) by definition of \(+\).

Induction.

Suppose \(m = m + 0\), want \(S(m) = S(m) + 0\).

\(S(m) + 0 = S(m + 0)\) by definition of \(+\), applying induction hypothesis, \(S(m + 0) = S(m)\).

The lemma helps establish base case of part 3.

Addition in \(\mathbb{N}\) is commutative.

Proof. Proceed by induction on \(n\).

Base case.

\(0 + m = m\) by definition of \(+\), and \(m = m + 0\) by (plus 0), this establishes base case.

Induction.

Suppose \(n + m = m + n\), want \(S(n) + m = m + S(n)\). \[\begin{align*} S(n) + m &= S(n + m) \tag*{by definition of $+$} \\ &= S(m + n) \tag*{by inductive hypothesis} \\ &= (m + n) + 1 \tag*{by part 1} \\ &= m + (n + 1) \tag*{by part 2} \\ &= m + S(n) \tag*{by part 1 \quad$\square$} \end{align*}\]

4. \(n + n = 2n\).

\[\begin{align*} 2\cdot n &= S(S(0))\cdot n \tag*{definition of $2$} \\ &= (S(0) \cdot n) + n \tag*{definition of $\cdot$} \\ &= ((0 \cdot n) + n) + n \tag*{definition of $\cdot$} \\ &= (0 + n) + n \tag*{definition of $\cdot$} \\ &= n + n \tag*{definition of $+$ \quad$\square$} \end{align*}\]

5. If \(2n = 2m\), then \(n = m\).

Notation. For this part, let all implicit quantifiers range over \(\mathbb{N}\).

Using part 4, reformulate the statement to prove as \[\forall n \left[ \forall m \left[ n + n = m + m \implies n = m \right] \right]. \] Now we can proceed by induction on \(n\).

Base case.

Let \(m\) be arbitrary, need to show that \(0 + 0 = m + m\) implies \(0 = m\).

Suppose we have \(m\) such that \(0 + 0 = 0 = m + m\). By exercise 4.15, we have either \(m = 0\) or \(\exists k\in m\subseteq\mathbb{N}\left[ S(k) = m \right]\).

• Case \(m = 0\) we are done.

• Case \(\exists k\in\mathbb{N}\left[ S(k) = m \right]\), then \(m + m = S(k) + S(k) = S(k + S(k)) = 0\), contradicting Peano axiom.

Induction step.

Suppose for \(k\), we have \(\forall j \left[ k + k = j + j \implies k = j \right]\). Want to show that \(\forall m\left[ S(k) + S(k) = m + m \implies S(k) = m \right]\).

Let \(m\) be arbitrary, suppose we have \(S(k) + S(k) = m + m\), similarly by exercise 4.15, either \(m = 0\) or \(\exists j\in m\subseteq\mathbb{N}\left[ S(j) = m \right]\). Note that in the case \(m = 0\), we have \(S(k) + S(k) = S(k + S(k)) = 0\) which contradicts Peano axiom, so the latter statement has to hold. Then our assumption could be rewritten as \[\begin{align*} S(k) + S(k) &= S(j) + S(j) \\ S(k + S(k)) &= S(j + S(j)) \tag*{definition of $+$} \\ S(S(k) + k) &= S(S(j) + j) \tag*{part 3} \\ S(S(k + k)) &= S(S(j + j)) \tag*{definition of $+$} \\ k + k &= j + j \tag*{Peano axiom twice} \\ k &= j \tag*{induction hypothesis} \\ S(k) &= S(j) \\ S(k) &= m \end{align*}\] This completes the induction.

6. \(n\cdot(m + k) = n\cdot m + n\cdot k\)

Induction on \(n\).

Base case.

\(0\cdot (m+k) = 0\) by definition of \(\cdot\), and \(0\cdot m + 0\cdot k = 0 + 0 = 0\) by definitions of \(\cdot\) and \(+\).

Induction.

Suppose \(n\cdot(m+k) = n\cdot m + n\cdot k\), want to show \(S(n)\cdot(m+k) = S(n)\cdot m + S(n)\cdot k\).

Evaluating LHS gives \[\begin{align*} S(n) \cdot (m + k) &= n\cdot (m + k) + (m + k) \tag*{definition of $\cdot$} \\ &= n\cdot m + n\cdot k + m + k \tag*{induction hypothesis} \\ &= n\cdot m + m + n\cdot k + k \tag*{part 3} \\ &= S(n)\cdot m + S(n)\cdot k \tag*{definition of $+$ \quad$\square$} \end{align*}\]

Before we proceed, some right-sided properties of \(\cdot\) require demonstration.

Lemma (multiply 0). \(n\cdot 0 = 0\).

Proof. Trivial induction.

Lemma (multiply 1). \(n\cdot 1 = n\).

Proof. Induction on \(n\). Base case \(n = 0\) is trivial, suppose \(n\cdot 1 = n\), then \[\begin{align*} S(n)\cdot 1 &= n\cdot 1 + 1 \tag*{definition of $\cdot$} \\ &= n + 1 \tag*{induction hypothesis} \\ &= S(n) \tag*{part 1 \quad$\square$} \end{align*}\]

Corollary (multiply right successor). \(n\cdot S(m) = n\cdot m + n\).

Proof. \(n\cdot S(m) = n\cdot (m + 1) = n\cdot m + n\cdot 1 = n\cdot m + n\).

7. \(n\cdot (m\cdot k) = (n\cdot m)\cdot k\)

Induction on \(k\).

Base case.

\(n\cdot (m\cdot 0) = 0\) by two applications of (multiply 0), and \((n\cdot m)\cdot k = 0\) by 1 application of the same lemma. This establishes base case.

Induction step.

Suppose \(n\cdot (m\cdot k) = (n\cdot m)\cdot k\), want to show \(n\cdot (m\cdot S(k)) = (n\cdot m)\cdot S(k)\). \[\begin{align*} n\cdot (m\cdot S(k)) &= n\cdot (m\cdot k + m) \tag*{multiply right successor} \\ &= n\cdot (m\cdot k) + n\cdot m \tag*{part 6} \\ &= (n\cdot m)\cdot k + n\cdot m \tag*{induction hypothesis} \\ &= (n\cdot m)\cdot S(k) \tag*{multiply right successor \quad$\square$} \end{align*}\]

8. \(n\cdot m = m\cdot n\)

Induction on \(n\).

Base case.

\(0 \cdot m = 0\) by definition of \(\cdot\), and \(m\cdot 0 = 0\) by multiply 0.

Induction step.

Suppose \(n\cdot m = m\cdot n\), need to show \(S(n)\cdot m = m\cdot S(n)\). \[\begin{align*} S(n) \cdot m &= n\cdot m + m \tag*{definition of $\cdot$} \\ &= m\cdot n + m \tag*{induction hypothesis} \\ &= m\cdot S(n) \tag*{multiply right successor \quad$\square$} \end{align*}\]