Exercise 2.3.5
Prove Proposition 2.3.9. (Hint: fix q and induct on n.)
Let's write out Proposition 2.3.9.
Proposition 2.3.9 (Euclid’s division lemma). Let $n$ be a natural number, and let $q$ be a positive number. Then there exist natural numbers $m$, $r$ such that $0 \leq r < q$ and $n = mq + r$.
Let's follow the hint and prove this by induction. Before we dive in, it is worth noting the point of the proof is to show existence, which can make the proof easier.
Let the proposal $P(n)$ tate that there exist natural numbers $m$, $r$ such that $0 \leq r < q$ and $n = mq + r$.
The inductive hypothesis is that $P(n)$ is true.
The base case is $P(0)$. That is, there exist natural numbers $m$, $r$ for
$$0 = mq + r$$
where $0 \leq r < q$.
One solution is $m=0$ and $r=0$. The existence of one solution is all we need to show the base case is true. As it happens, it is the only possible solution, but that is not required here.
The inductive step requires us to show that $P(n++)$ is true. That is, there exist natural numbers $m'$, $r'$ for
$$n++ = m'q + r'$$
where $0 \leq r < q'$.
Let's start with the inductive hypothesis.
$$n = mq + r$$
Incrementing both sides,
$$\begin{align} n++ &= (mq + r)++ \\ \\ &= mq + (r++) \\ \\ &= m'q + r' \end{align}$$
The simplest case is where $m'=m$ and $r'=r++$, as long as $r' < q$, that is $r++ < q$.
However, since $r < q$ means $r++ \leq q$ by Proposition 2.2.12, it is possible that $r++ = q$. In this case, using the distributivity of multiplication Proposition 2.3.4,
$$\begin{align} n++ &= mq + q \\ \\ &= (m+1)q + 0\\ \\ &= m'q + r' \end{align}$$
where $m'=m+1$ and $q=0$.
We have shown that $m'$ and $r'$ can always exist for $n++ = m'q + r'$, where $0 \leq r' < q$. This completes the induction step.
By showing the base case $P(0)$ is true, and that $P(n) \implies P(n++)$, by induction we have shown $P(n)$ holds for all natural numbers $n$. That is there exist natural numbers $m$, $r$ such that $0 \leq r < q$ and $n = mq + r$. $\square$
No comments:
Post a Comment