2
$\begingroup$

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? **

$\endgroup$
  • $\begingroup$ Apologies but...I haven't reached to multiplication part and I just want to make sure if there's any logical issues with my attempt on the addition's associative rule...Not really using answers from others... $\endgroup$ – commentallez-vous May 11 at 16:44
  • $\begingroup$ Base case is correct, but for the Induction step you cannot prove $1,2,\ldots$ exactly because what we have to show is how to formalize the "$\ldots$". Thus, assume $(a+b)+n=a+ (b+n)$ and prove $(a+b)+(n++)=a+(b+(n++))$ $\endgroup$ – Mauro ALLEGRANZA May 11 at 17:01
  • $\begingroup$ Hi Mauro, so for induction, we show case 0 is true. But when we say case n, we are assuming if case n is true, and see if for n+1 is true, and if yes, induction is proved? So we are not really showing for case = 1 ... n is true? $\endgroup$ – commentallez-vous May 11 at 17:02
  • $\begingroup$ Exactly; having case $n=0$ and having the proof for "if case $n$, then case $(n+1)$", we can use it with $n=0$ to prove $n=1$, and so on. $\endgroup$ – Mauro ALLEGRANZA May 11 at 17:04
  • $\begingroup$ Ah I see...sorry I was a bad math student...and definitely didn't catch the logic here. I was wondering why Tao was basically using "Suppose" and "Assume" in case = n in his text and thought maybe he was "lazy" haha. But is my case = n+1 okay after assuming case = n is true? $\endgroup$ – commentallez-vous May 11 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.