Thursday, February 21, 2013

Multiplication

After explaining addition and its properties, it’s time to explain another operation: multiplication.

It can be defined by repeated addition:

image

Or recursively by:

0*n = 0

S(m)*n = (m*n) + n

Once again we’ll use mathematical induction to prove what we want.

First of all, I will prove that both definitions are equivalent. We know that

image

Therefore:

image

Now let’s define the properties of multiplication.

Commutativity

First, as before, we need to prove that numbers commute with 0.

Commutativity with 0

It is evident that 0*0 = 0 = 0*0, so that property is valid at 0. If we can prove that being valid at k implies being valid at S(k), then it will be valid for all natural numbers. Thus, we need k*0 = 0*k to imply S(k)*0 = 0*S(k)

1. S(k)*0 = (k*0) + 0 [Definition of multiplication]

2. (k*0) + 0 = k*0 [Definition of addition]

3. k*0 = 0*k [Premise]

4. 0*k = 0 [Definition of multiplication]

5. 0*S(k) = 0 [Definition of multiplication]

And so it’s verified that multiplication commutes with 0.

Commutativity with Successor

Now let’s move on to prove that k*S(n) = k + (k*n). First, by definition 0*S(n) = 0 = 0 + (0*n) so that’s valid at k = 0. Now let’s find out whether validity at k implies validity at S(k).

1. S(k)*S(n) = (k*S(n))+S(n) [Definition of multiplication]

2. (k*S(n))+S(n) = k + (k*n) + S(n) [Premise]

3. k + (k*n) + S(n) = (k*n) + k + S(n) [Commutativity of addition]

4. (k*n) + k + S(n) = (k*n) + S(k + n) [Definition of addition]

5. (k*n) + S(k + n) = (k*n) + S(n + k) [Commutativity of addition]

6. (k*n) + S(n + k) = (k*n) + n + S(k) [Definition of addition]

7. (k*n) + n + S(k) = (S(k)*n) + S(k) [Definition of multiplication]

8. (S(k)*n) + S(k) = S(k) + (S(k)*n) [Commutativity of addition]

Since the property is valid at 0 and validity at k implies validity at S(k), the property is valid for all natural numbers.

Commutativity

Now we’re ready to prove commutativity in general using Peano’s Axioms and the definition of multiplication. We already know that 0*m = 0 = m*0, so we want to prove that if k*m = m*k then S(k)*m = m*S(k).

1. S(k)*m = (k*m) + m [Definition of multiplication]

2. (k*m) + m = (m*k) + m [Premise]

3. (m*k) + m = m + (m*k) [Commutativity of addition]

4. m + (m*k) = m*S(k) [Commutativity with Successor]

So Commutativity is proved for all natural numbers. Q.E.D.

Distributivity over Addition

We are now going to prove that k*(m+n) = k*m + k*n. First, for k = 0 that is trivially true:

1. 0*(m+n) = 0 [Definition of multiplication]

2. 0*m + 0*n = 0 + 0 = 0 [Definitions of multiplication and addition]

Now let’s prove that k*(m + n) = k*m + k*n implies S(k)*(m + n) = S(k)*m + S(k)*n.

1. S(k)*(m+n) = k*(m + n) + (m + n) [Definition of multiplication]

2. k*(m + n) + (m + n) = (k*m) + (k*n) + (m + n) [Premise]

3. (k*m) + (k*n) + (m + n) = (k*m + m) + (k*n + n) [Commutativity and associativity of addition]

4. (k*m + m) + (k*n + n) = S(k)*m + S(k)*n [Definition of addition]

So multiplication distributes over addition for all natural numbers. Q.E.D.

Associativity

We mean to prove that (m*n)*p = m*(n*p).

Associativity with 0

First we prove that (m*n)*0 = m*(n*0).

1. (m*n)*0 = 0*(m*n) [Commutativity]

2. 0*(m*n) = 0 [Definition of multiplication]

3. m*(n*0) = m*(0*n) [Commutativity]

4. m*(0*n) = m*0 [Definition of multiplication]

5. m*0 = 0*m [Commutativity]

6. 0*m = 0 [Definition of multiplication]

Since (m*n)*0 = 0 = m*(n*0), commutativity will guarantee that multiplication always associates with 0.

Associativity

Now we need (m*n)*p = m*(n*p) to imply (m*n)*S(p) = m*(n*S(p)).

1. (m*n)*S(p) = (m*n)*p + (m*n) [Definition of multiplication and commutativity]

2. (m*n)*p + (m*n) = m*(n*p) + (m*n) [Premise]

3. m*(n*p) + (m*n) = m*(n*p + n) [Distributivity over addition]

4. m*(n*p + n) = m*(n*S(p)) [Definition of multiplication and commutativity]

And so multiplication is associative for all natural numbers. Q.E.D.