I am trying to prove cancellation property of multiplication of natural numbers, $xy=xz$ implies $y=z$, with Peano axioms and arithmetic but not using or defining order on natural numbers. It can be done for addition. But for proving multiplication cancellation property one uses order. Why is that so?


1 Answer 1


You do not need to use order. Do it by induction on $y$. Define $M:=\{y \ |yx=zx\Rightarrow y=z \}$.

For $y=1$ we have $1\cdot x=z\cdot x$. If $z=1$ we are done. Suppose $z\neq 1$. Then $z=s(p)$ for some $p$ and hence $$1\cdot x=s(p)\cdot x= px+x=(p\cdot x)+1\cdot x$$ and $$1+(1\cdot x)=1+(p\cdot x)+(1\cdot x).$$ Using cancellation for addition we get $$1=1+(p\cdot x)=(p\cdot x)+1=s(p\cdot x),$$ that is a contradiction. Therefore $z=1$.

Now, let $y=k\in M$, i.e. for any positive integers $z,x$ if $kx=zx$ then $k=z$. Let $t,s \in \mathbb{N}_+$ be such that $s(k)\cdot s=t\cdot s$. We show that $s(k)=t$. Obviously $t\neq 1$. Hence $t=s(m)$ for some $m$ and therefore we get $$s(k)s=s(m)s$$ that is equaivalent to $$ks+s=ms+s$$ from which it follows that $ks=ms$ (cancellation for addition). From the induction hypothesis we have $k=m$, and therefore $s(k)=s(m)=t$.

That means that $n=k+1\in M$ and the proof is completed.

  • $\begingroup$ Your base case does not handle the case where z could be zero. As you assume z = successor(p) for some p, but that doesn't include z = 0 itself. An easy proof is to also show the case where z = 0 results in some contradiction due to axioms of multiplication by zero resulting in zero which is not equivalent to 1. $\endgroup$ Apr 23 at 1:45
  • $\begingroup$ Similarly for inductive step, it's trivial to show it can't be 0 since x is non-zero and can use proof by contradiction and the property that positive is closed under addition to show that it can't be zero as x is positive (non-zero) $\endgroup$ Apr 23 at 3:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .