a. Prove by induction that +:ℕ×ℕ→ℕ is commutative (∀m,n,m+n=n+m) and satisfies cancellation (∀m,n,p,m+p=n+p if and only if m=n).

*Commutative: m+n=n+m*

Let us first define two rules. 1: n+0=n. 2: n+succ(m)=succ(n+m).

We proceed by induction on n.

m+n=n+m

BC: m+0=0+m

We induct further on m.

BC: 0+0=0+0

IH: assume m+0=0+m

succ(m)+0=0+succ(m)

=succ(0+m)

=succ(m+0)

succ(m)+0=succ(m+0)

IH: assume m+n=n+m

IS: m+succ(n)=succ(n)+m

We induct further on m.

BC: 0+succ(n)=succ(n)+0

IH: Assume m+succ(n)=succ(n)+0

IS: succ(m)+succ(n)=succ(n)+succ(m)

succ(succ(m)+n))

succ(n+succ(m))

succ(succ(n+m))

succ(succ(m+n))=succ(n)+succ(m)

succ(succ(m+n))=succ(n+succ(m))

succ(succ(m+n))=succ(succ(m)+n)

succ(succ(m+n))=succ(succ(m+n))

succ(m+n)=succ(m+n)

m+n=m+n

*Cancellation: m+p=n+p if and only if n=m*

We proceed by induction on p.

BC: m+0=0+n iff. n=m.

m=n

IH: assume m+p=n+p iff. n=m

m+succ(p)=n+succ(p)

succ(m+p)=succ(n+p)

m+p=n+p

m=n

James Lynch