We now move on to multiplication. Similar to addition, multiplication can be defined recursively, but now in terms of addition instead of incrementation
Definition 1.3.1 (Multiplication)
Multiplication has a starting point
$$n \times 0 := 0$$
and is defined recursively in terms of addition
$$ n \times (m++) := (n \times m) + n$$
with $m, n \in \mathbb{N}$.
Similar to addition, we will some algebraic properties of multiplication.
Property 5 (Multiplicative closure)
If $m, n \in \mathbb{N}$, then $n \times m \in \mathbb{N}$.
Proof
We will induct on $m$. For the base case $m=1$, we have
$$n \times 1 := n \in \mathbb{N}$$
Now, assume the claim is proven for $m$, we will show that it is also true for $m++$.
$$n \times (m++) := (n \times m) + n$$
By induction hypothesis, $(n \times m)$ is a natural number, and we assume $n$ to be natural. And by the additive closure, we know that sum of two natural numbers are a natural number. Thus, $(n \times m) + n$ is natural, and the claim is proven.
Property 6 (Multiplicative identity) $ n \times 1 = 1 \times n = n$
Proof
We can easily verify from the definition that $ n \times 1 = n \times (0++) := n \times 0 + n = n$, so we only need to show $1 \times n = n$. First, we will show that
$$n+1 = n++$$
This is because of the definition of addition,
$$n+(0++) := (n+0)++ := n++$$
Now, induct on $n$. For the base case $n=0$, we know from the definition of multiplication,
$$1 \times 0 := 0$$
Now, assume the claim is proven for $n$, we will show that it is also true for $n++$. That is
$$1 \times (n++) = n++$$
The left hand side is equal to
$$1 \times (n++) := (1 \times n) + 1$$
By the induction hypothesis, we know that $(1 \times n) = n$. And we also already show that $n + 1 = n++$. Therefore, the left hand side is equal to the right hand side. Induction is done.
Property 7 (Multiplication is commutative) $ n \times m = m \times n$
Proof
The proof for multiplication is very similar to that of addition. First, we want to show that
$$(m++) \times n = m \times n + n$$
We will proceed by induction on $n$. For the base case $n=0$, we need to show that
$$(m++) \times 1 = m \times 0 + 0$$
The left-hand side is equal to
$$(m++) \times 1 = (m++) \times (0 ++) := (m++) \times 0 + (m++)$$
By the additive identity,
$$(m++) \times 0 + (m++) = m++$$
By the multiplicative identity,
$$= m++ = m + 1 = m \times 1 + 1$$
So the base case is proven. Now, we assume the claim holds for $n$ and extends it to $n++$. That is we want to show that
$$(m++) \times (n++) = m \times (n++) + (n++)$$
The left hand is equal to
$$(m++) \times (n++) := (m++) \times n + m$$
By the induction hypothesis, this is equal to
$$ (m++) \times n + m = m \times n + n + m := (m++) \times n + m$$
The left-hand side is now equal to the right hand side, and our induction is complete.
We will now show that multiplication is commutative by induction on m. For the base case $m=1$, we already have the multiplicative identity that $m \times 1 = 1 \times m = m$. We assume the claim is true for $m$ and will extend it to $m++$. We need to show that
$$n \times (m++) = (m++) \times n$$
The left hand side is
$$n \times (m++) := n \times m + n$$
By the induction hypothesis,
$$n \times m + n = m \times n + n$$
This is equal to the right-hand side as proven above. This concludes our induction.
As we can see, the multiplicative commutativity is proven similarly to the way we prove additive multiplicative. We might expect to prove multiplicative associativity similarly to the way we prove additive associativity. As it turns out, we need distributivity before associativity.
Property 8 (Distributivity) $( b + c) \times a = b \times a + c \times a$
Proof
We will induct on $a$. For the base case $a=0$, we know that
$$(b+c) \times 0 := 0$$
and
$$b \times 0 + c \times 0 := 0 + 0 = 0$$
So the base case is proven. Now, assume the claim holds for $a$, we will prove that
$$( b + c) \times (a++) = b \times (a++) + c \times (a++)$$
The left-hand side is equal to
$$( b + c) \times (a++) := (b+c) \times a + (b+c)$$
By the induction hypothesis, this is equal to
$$= b \times a + c \times a + (b + c)$$
Addition is associative so we can move terms around
$$= (b \times a + b) + (c \times a + c) := b \times (a++) + c \times (a++)$$
The left-hand side is now equal to the right-hand side, and our induction is complete.
Property 9 (Multiplication is associative) $ a \times (b \times c ) = (a \times b) \times c$
Proof
We will induct on $c$. For the base case $c=1$, we know by the multiplicative identity that
$$a \times ( b \times 1) = a \times b = (a \times b) \times 1$$
Now, we assume the claim holds for $c$ and extends it to $c++$. That is we want to show that
$$a \times (b \times (c++) ) = (a \times b) \times (c++)$$
The left hand side is equal to
$$a \times (b \times (c++) ) := a \times (b \times c + b)$$
Using the distributive law, we have
$$= a \times (b \times c) + a \times b $$
By the induction hypothesis, we have
$$= (a \times b) \times c + (a \times b) := (a \times b) \times (c++)$$
The left-hand side is now equal to the right-hand side, and our induction is complete.
No comments:
Post a Comment