If $m$, $n$, $p$, $k\in\mathbb{N}$, I'm trying to prove that $m\cdot p = n\cdot p \Rightarrow m = n$.
I want to use induction. And I have the definition of multiplication:
$$
m\cdot 1 = m
$$
$$
m\cdot (n+1) = m\cdot n + m
$$
I also have distributivity $m\cdot(n+p)=m\cdot n+m\cdot p$, associativity $(m\cdot n)\cdot p = m\cdot(n\cdot p)$, and commutativity $m\cdot n = n\cdot m$. For the sum, I also have $m + k = n + k \Rightarrow m=n$.
For $p=1$, I just apply the definition:
$$
m\cdot 1 = n\cdot 1\Rightarrow m=n
$$
Now, I assume the proposition is valid for some $p\in\mathbb{N}$, and for any $m$, $n\in\mathbb{N}$. Then:
$$
m\cdot(p+1) = n\cdot(p+1)\Rightarrow m\cdot p + m = n\cdot p + n
$$
Now, by the induction hypothesis: $m\cdot p = n\cdot p$.
Then:
$$
m\cdot p + m = n\cdot p + n \Rightarrow m\cdot p + m = m\cdot p + n
$$
Finally,
$$
m\cdot p + m = m\cdot p + n \Rightarrow m = n
$$
So, the proposition is valid for all $p\in\mathbb{N}$.
My question is: the induction hypothesis is $m\cdot p = n\cdot p \Rightarrow m = n$. In my demonstration, I just used $m\cdot p = n\cdot p$. Can I do that? Or I'm missing something?
Thanks in advance!
Andre
Best Answer
The induction hypothesis is that if $mp=np$ then $m=n$. You need to be a little more subtle about this. Suppose it is true for $m\le M$. And suppose you have defined the operation of subtracting $1$ from a positive integer to obtain a non-negative integer, then, if $m=M+1$ ...
If $mp=(M+1)p=np$ we have either $n=0$ (which you can deal with) or $n=N+1$ so that $(M+1)p=(N+1)p$ or (from the definition) $Mp+p=Np+p$. We subtract $p$ from each side to get $Mp=Np$ so that $M=N$ and from the properties of addition $m=M+1=N+1=n$.