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?
$\endgroup$1 Answer
$\begingroup$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.
$\endgroup$
