Tao Analysis: Exercise 2.2.1

This is a proof of the associative property of natural number addition. We will show that for any natural numbers $$a, b, and\, c$$ , we have $$(a+b)+c = a+(b+c)$$ .

To show this, let's induct on $$c$$ . First, let's deal with the base case where $$c=0$$ :

$$c=0$$	Assumed
$$b+0=b$$	Lemma 2.2.2
$$(a+b)+c=(a+b)+0$$	Substitution
$$=a+b$$	Lemma 2.2.2
$$=a+(b+0)$$	Substitution

Therefore, $$(a+b)+0=a+(b+0)$$ , proving the base case.

Now, the inductive case. Here we are assuming that $$(a+b)+c=a+(b+c)$$ for some natural number $$c$$ .

$$(a+b)+(c++)=(c++)+(a+b)$$	Commutative property
$$=(c+(a+b))++$$	Definition of addition
$$=((a+b)+c)++$$	Commutative property
$$=(a+(b+c))++$$	Inductive hypothesis
$$=((b+c)+a)++$$	Commutative property
$$=((b+c)++)+a$$	Definition of addition
$$=((c+b)++)+a$$	Commutative property
$$=((c++)+b)+a$$	Definition of addition
$$=a+(b+(c++))$$	Commutative property x2

The induction is closed. Therefore, $$(a+b)+c=a+(b+c)$$ for all natural numbers $$a, b, and\,c$$ .