Thread: Proof of the cancellativity of multiplication using the Peano axioms

1. Proof of the cancellativity of multiplication using the Peano axioms

I'm using the five Peano axioms, using 0 as the first natural number. I need to prove the following law:

M x s(P) = N x s(P) ==> M = N for all m, n, p.

Where s() is the successor function. I started like this:

Basis: M x s(0) = N x s(0) = m x 1 = n x 1 ==> m = n by the identity law for multiplication (which I proved earlier in the exercise).

Inductive hypothesis: M x s(K) = N x s(K) ==> M = N for some K.

Inductive step: Assume: M x s(s(K)) = N x s(s(K))

==> M + M x s(K) = N + N x s(K) by the definition of multiplication
==> M + (M + M x K) = N + (N + N x K) by the definition of multiplication

I'm not sure where to go from here.

2. You can prove $\displaystyle \forall m,n,p.\,m+p = n+p\to m=n$ by induction on p. After that, you can prove $\displaystyle \forall m,n,p.\,m\cdot s(p)=n\cdot s(p)\to m=n$ by induction on m and a nested induction on n.

The idea is in the in the nested induction step you assume s(m) * s(p) = s(n) * s(p), i.e., m * s(p) + s(p) = n * s(p) + s(p), so s(p) can be canceled and the claim follows by the induction hypothesis for m.