Proving that $mp=np$ implies $m=n$ 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
 A: 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$.
A: You're correct that you can't do that. In the induction step, what you know is
$$
m\cdot p = n\cdot p\Rightarrow m=n
$$
And what you're trying to prove is
$$
m\cdot (p+1) = n\cdot (p+1)\Rightarrow m=n
$$
So, okay. Let's prove that statement.
Before we do, I'm going to introduce another two things that you know. First, for every $a \in {\mathbb N}$, either $a = 1$ or there exists some $\hat{a}\in{\mathbb N}$ such that $a = \hat{a} + 1$. Second:
$$
a + b \neq a \quad \forall a,b \in {\mathbb N}
$$
(Since you're obviously using a version of the naturals that excludes $0$). If you haven't proved this yet, it's pretty straightforward: you likely have it as an axiom for $a=1$ (that is, that $1$ is not the successor of any natural) and for $a = \hat{a}+1$, you can do a straightforward proof by contradiction leveraging your sum cancellation law.
As you said,
\begin{align}
 m\cdot (p+1) = n\cdot (p+1) &\iff m \cdot p + m = n \cdot p + n
\end{align}
So the statement you need to prove is
\begin{align}
 m \cdot p + m = n \cdot p + n\Rightarrow m=n\quad \forall m,n \in {\mathbb N}\tag{1}
\end{align}
Let's prove $(1)$ by induction on $m$.
If $m = 1$, then we have:
$$
p + 1 = n \cdot p + n
$$
Split this into two cases: either $n = 1$, or there exists an $\hat{n}$ such that $n = \hat{n} + 1$. In the case $n = 1$, we have $m=n$ and $(1)$ holds. In the case where $n = \hat{n} + 1$, we have:
\begin{align}
p + 1 &= (\hat{n} + 1) \cdot p + (\hat{n} + 1) \\
      &= \hat{n} \cdot p + p + \hat{n} + 1 \\
      &= (\hat{n} \cdot p + \hat{n}) + (p + 1)
\end{align}
This is a contradiction (using the $a + b \neq a$ known above), so we have proved $(1)$ for the case $m=1$.
Now, attacking $(1)$ for the case when $m = \hat{m}+1$, the induction hypothesis is:
$$
\hat{m}\cdot p + \hat{m} = n \cdot p + n \Rightarrow \hat{m} = n \quad \forall n \in {\mathbb N}
$$
Then:
\begin{align}
m \cdot p+ m &= n \cdot p + n \\
\hat{m} \cdot p + \hat{m} + p + 1 &= n \cdot p + n \\
\end{align}
Again, two cases for $n$: either $n=1$ or $n = \hat{n} + 1$ for some $\hat{n} \in {\mathbb N}$. Taking the case $n=1$:
$$
\hat{m} \cdot p + \hat{m} + p + 1 = p + 1
$$
That's a contradiction. (again, to $a + b \neq a$) Therefore, taking the case $n = \hat{n} + 1$:
\begin{align}
\hat{m} \cdot p + \hat{m} + p + 1 &= \hat{n} \cdot p + \hat{n} + p + 1 \\
\hat{m} \cdot p + \hat{m} &= \hat{n} \cdot p + \hat{n}
\end{align}
By the induction hypothesis, this gives $\hat{m} = \hat{n}$, and therefore $m = n$.
This completes the proof of $(1)$.
