Showing that addition is associative and commutative using Mathematical Induction

I recently found a book left on the AMRC coffee table “Fundamental Concepts of Mathematics” by R.L. Goodstein. Inside his book Goodstein propose to use mathematical induction to show that addition is commutative.

————————————————————–

We first need to define the addition of two number as satisfying the following property: $m+(n+1)=(m+n)+1$ (this is associativity with $1$ under addition). Let us refer this property as $A_0$.

————————————————————–

We can first show that associativity is always true. We write $A_1$ the property $m+(n+p)=(m+n)+p$.

The proof by induction is:

1) we know $A_1$ to be true for $p=1$ as it give $A_0$

2) let us assume it exists an integers $k$ satisfying $A_1$ so that we can write $m+(n+k)=(m+n)+k$.

It follows that:

using $A_0$    $m+(n+(k+1))=m+((n+k)+1)$

using $A_0$    $m+(n+(k+1))=(m+(n+k))+1$

since $A_1$ is true for $k$    $m+(n+(k+1))=((m+n)+k)+1$

using $A_0$    $m+(n+(k+1))=(m+n)+(k+1)$

We now see that if $k$ satisfies $A_1$ then the next integer $k+1$ satisfies $A_1$. Since $A_1$  is true for $k=1$ it is true for all positive integers.

————————————————————–

From here we can show commutativity with $1$. We refer to this property as $C_0$: $a+1=1+a$ for all $a$ (positive) integers.

The proof by induction is the following:

1) we know that $C_0$ is true for $a=1$, as we simply have $1+1=1+1$

2) let us assume that it exists an integer $k$ for which $C_0$ is true. Then we can write $k+1=1+k$.

Since $k$ satisfies $C_0$    $(k+1)+1=(1+k)+1$

using $A_0$    $(k+1)+1=1+(k+1)$

We now see that if $k$ satisfy $C_0$ then the next integer $k+1$ satisfy $C_0$. Since $C_0$  is true for $k=1$ it is true for all positive integers.

————————————————————–

Next we can show the property $C_1$: commutativity with any integer $a+b=b+a$.

The proof by induction is:

1) we know $C_1$ is true for $b=1$ as it gives $a+1=1+a$ which simply is $C_0$ which we now know to be true.

2) let us assume that $C_1$ is true for some integer $k$ then we can write $a+k=k+a$.

It follows that

using $A_0$   $a+(k+1)=(a+k)+1$

since $C_1$ is true for $k$    $a+(k+1)=(k+a)+1$

using $A_0$    $a+(k+1)=k+(a+1)$

using $C_0$    $a+(k+1)=k+(1+a)$

using $A_1$    $a+(k+1)=(k+1)+a$

So that we see that if $k$ satisfy $C_1$ then the next integer $k+1$ satisfy $C_1$. Therefore $C_1$ is true for all integers.