18a

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License