Prove that a x m = m x a for natural numbers a and m.
LEMMAS:
- $n+0=n$
- $n+m++=(n+m)++$
- $a++=a +1$ (True since $a++$ is counting forward one step)
- Addition is commutative
By induction Base step: Let m be an arbitrary natural number, and a be 0. Then by definition a x m =0. Since m is a natural number, then m is obtained by counting forward from 0. Hence a x m becomes a x (n0++) = a x n0 (by lemma 1), which can be represented as a x (n1++) = a x n1 and so on until 0 x m=0. We know that this can be done since a is obtained by counting forward from 0. Hence m x a =0= a x m. Inductive step: Assume a x m= m x a. Then a++ x m is (a x m) + m = (m x a)+m = m+ (m x a). We can constantly count backwards instead of forwards, shifting “a”s from m x a to m. Since a is natural and can be obtained from counting forwards by 1 , similarly, 0 can be obtained by counting backwards from a by repeatedly deducting 1. We eventually obtain (1+a) x m +0 = (a++) x m.