Exercise 2.2.1 (Addition is associative)

Question

Prove Proposition 2.2.5. (Hint: fix two of the variables and induct on the third.)\par 

	extbf{Proposition 2.2.5} (Addition is associative) For any natural numbers $a, b, c$, we have $(a + b) + c = a + (b + c)$.

Issa Rice · Accepted Answer

extbf{How to think about the exercise.} This is a simple induction exercise; it just tests your ability to write an induction proof and make use of the definition of addition. This sort of exercise requires no thinking (once you get the hang of things): at each step, you just do the next obvious thing.\par

extbf{Model solution.} We shall fix $b,c$ and induct on $a$. For the base case, we want to show $(0+b)+c = 0 + (b+c)$. By definition of addition, $0+b = b$, so $(0+b)+c = b+c$. Again by definition of addition, $0 + (b+c) = b+c$. Thus, $(0+b)+c = 0 + (b+c)$ as required.

Now suppose inductively that $(a+b)+c = a + (b+c)$. We wish to show that $((a{{+}\!{+}})+b)+c = (a{{+}\!{+}}) + (b+c)$. By definition of addition, $((a{{+}\!{+}}) + b) + c = ((a + b){{+}\!{+}}) + c = ((a+b) + c){{+}\!{+}}$. Similarly, $(a{{+}\!{+}}) + (b+c) = (a + (b+c)){{+}\!{+}}$; by the inductive hypothesis, this is $((a+b)+c){{+}\!{+}}$. In other words, both $((a{{+}\!{+}}) + b)+c$ and $(a{{+}\!{+}}) + (b+c)$ are equal to $((a+b)+c){{+}\!{+}}$. This closes the induction.\par

Source: \href{https://issarice.com/}{Issa Rice's blog}.

Khagan Gulusoy · Answer

\begin{proof}
We induct on $a$ (keeping $b$ and $c$ fixed). First, we check the base case $a = 0, $ i.e.,
$$(0 + b)+c = 0 + (b + c).$$
By Definition 2.2.1, $0 + b=b$; thus, substitution yields $(0 + b)+c = b+c. $ By Definition 2.2.1 again,  $0 + (b + c) = b + c.$ We hence conclude that both sides are equal to each other, which proves the base case.
ewline

Now suppose inductively that $(a + b) + c = a + (b + c)$ for some natural number $a.$ We now prove $P(a++)$, which is $$((a++)+b)+c = (a++)+(b + c).$$
By Definition 2.2.1,
$$((a++)+b)+c =((a+b)++)+c=((a + b) + c)++.$$
By the induction hypothesis,
$$((a + b) + c)++=(a + (b + c))++.$$
By Definition 2.2.1 again,
$$(a + (b + c))++=(a++)+(b + c).$$
This closes the induction. In other words, $(a + b) + c = a + (b + c)$ for any natural $a$.
ewline
Since our choice of $b$ and $c$ was arbitrary, the assertion follows for all natural numbers $b$ and $c$, as well.
\end{proof}

Exercise 2.2.1 (Addition is associative)

Answers

Comments

Comments

Exercise 2.2.1 (Addition is associative)

Answers

Comments

Comments

Add answer