The proposition 2.2.5 and also exercise 2.2.1 of Analysis by Terence Tao is as below:
Show for any natural numbers $a, b, c$, we have $(a+b)+c = a+(b+c)$ the associative rule
The proof should use induction.
What we already know is:
Definition: $0 + n = n$ for $n$ is a natural number ($0$ is also natural number)
Addition definition: $(n++)+m = (n+m)++$ where $n++$ is increment in n
Lemma 2.2.2: $n + 0 = n$
Lemma 2.2.3: $n+(m++)=(n+m)++$
Proposition 2.2.4: $n+m = m+n$
So my humble attempt is (as I am not really good at math..)
Proof:
To show $(a+b)+c = a+(b+c)$
For case = $0$ and if we fix $a$ and $b$ and increment $c$
(1) We want to show: $(a+b)+0 = a+(b+0)$.
The left hand side is $(a+b)+0 = a+b$ using Lemma 2.2.2 and view $(a+b)$ as an entity | Right hand side is $a+(b+0) = a + b$ also using Lemma 2.2.2 in the fact that $(b+0) = b$
So case $0$ is proved.
(2) Use induction to show for case $n$ this is true
For case = $1$: Show $(a+b)+1 = a+(b+1)$
Left hand side is $(a+b)+1 = (a+b)++$ by definition of Natural Numbers increment if we view $(a+b)$ as an entity and $(a+b)+1$ is $1$ increment of it
Right hand side is $a + (b+1) = a + (b++) \dfrac{=}{Lemma 2.2.3} (a+b)++$
So $(a+b)+1 = (a+b)++ = a+(b+1)$
For case = $2$: Show $(a+b)+2 = a+(b+2)$
Left hand side is $(a+b)+2 = ((a+b)++)++$ by definition of Natural Numbers increment if we view $(a+b)$ as an entity and $(a+b)+2$ is $2$ increments of it
Right hand side is $a + (b+2) = a + (b+1)++ = (a+b+1)++ = (a+b++)++ = ((a+b)++)++$ if keep applying Lemma 2.2.3
So $(a+b)+2 = ((a+b)++)++ = a+(b+2)$
$\vdots$
For case = $n$: Show $(a+b)+n = a+(b+n)$
Left hand side is $(a+b)+n = (((a+b)++)++)\cdots)++$ by definition of Natural Numbers increment if we view $(a+b)$ as an entity and $(a+b)+n$ is $n$ increments of it where there are $n$ signs of $++$
Right hand side is $a + (b+n) = a + (b+(n-1)++) = a + (b+n-1)++ = a + (b+ (n-2)++)++ = a + ((b + (n-2))++)++ = \cdots = ((((a + b)++)++)\cdots)++$ if keep applying Lemma 2.2.3, and there are $n$ signs of $++$
So $(a+b)+n = ((((a + b)++)++)\cdots)++ = a+(b+n)$
So we know for case = $n$ this is also True
(3) Now we only need to show for case = $n+1$ is True to complete the induction.
We show: $(a + b) + n + 1 = a + (b + n + 1)$ By:
Left hand side $(a + b) + n + 1 = (a + b) + (n++) = (a + b + n) ++$ Using Lemma 2.2.3
Right hand side $a + (b + n + 1) = a + (b + (n++)) = a + ((b+n)++) = (a + b + n)++$ Keep applying *Lemma 2.2.3**
Thus $(a + b) + n + 1 = (a + b + n)++ = a + (b + n + 1)$
Thus the proof is complete.
** Could somebody help me check if the above is a rigorous proof of the associative rule for natural numbers? **