18a Presentation

Mouctar Diallo

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

Commutativity of Addition:

rules we can use

(#1) n+0=n
(#2) n+succ(m)=succ(n+m)

Proof by induction

induct on n
WTS| m+0=0+m
induct on m
WTS| 0+0=0+0
anything is equal to itself —> statement is true, reflexive property of equality, equal introduction
IS| WTS| succ(m)+0=0+succ(m)
we proved right side is equal to the left side
IS| WTS| m+succ(n)=succ(n)+m
induct on m
basecase: 0+succ(n)=succ(n)+0 —> already proven
IH| m+succ(n)=succ(n)+m
IS| WTS| succ(m)+succ(n) = succ(n)+succ(m)

by showing this we prove that

Cancellation of Addition:

m+p=n+p iff m=n

proof by induction on p

base case m+0=n+0 iff m=n
IH| m+p=n+p iff m=n
IS| m+succ(p)=n+succ(p)
succ(m+p)=succ(n+p) (#2)
m+p=n+p RULE —> successor function is injective

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