Questions 18 Pre-Write

18. a) Statement: +: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).
Proof: For +:N×N→N to be commutative, ∀m,n,m+n=n+m. We can prove this by inducting on n.
Base case: n=0
m+0=0+m //can be proven by induction on m
Base case: m=0
0+0=0+0 this is true as something always equals itself
We then assume that for some arbitrary k, k+0=0+k holds and show that it is still true for succ(k), succ(k)+0=0+succ(k).
succ(k)+0=succ(k+0) by the recursive step in the definition of +
=succ(0+k) by our initial inductive hypothesis
=0+succ(k) by recursion
After proving the base case for induction on n, we can assume that the commutative property holds for some j=n(m+j=j+m) and prove it holds for m+succ(j)=succ(j)+m. We can do this by inducting on m.
Base case: m=0
succ(j)+0=0+succ(j).
succ(j)+0=succ(j+0) by the recursive step in the definition of +
=succ(0+j) by our initial inductive hypothesis
=0+succ(j) by recursion
We then assume that for some arbitrary h, h+succ(j)=succ(j)+h holds and show that it is still true for succ(h), succ(h)+succ(j)=succ(j)+succ(h).
succ(j)+succ(h)=succ(j+succ(h)) by the recursive step in the definition of +
=succ(succ(h)+j) by our initial inductive hypothesis
=succ(h)+succ(j) by recursion
Hence, +:N×N→N is commutative. +:N×N→N satisifies cancelation if and only if m=n.
m+p=n+p if m=n, we can replace all instances of m with n
n+p=n+p which is true by definition.
b) Statement: ⋅:N×N→N is associative (∀m,n,p,m⋅(n⋅p)=(m⋅n)⋅p), commutative (∀m,n,m⋅n=n⋅m), satisfies cancellation for nonzero values (∀m,n,p,m⋅p=n⋅p implies that m=n if p≠0), and distributes over addition (∀m,n,p,m⋅(n+p)=m⋅n+m⋅p).
Proof: We prove ⋅:N×N→N is commutative by performing induction on n and first showing the base case. If n=0, m⋅(0⋅p)=(m⋅0)⋅p:
m⋅(0⋅p)=m⋅p by the multiplicative identity of 0
(m⋅0)⋅p=m⋅p by the multiplicative identity of 0
We can then assume that m⋅n=n⋅m holds for some arbitrary value n=p (m⋅p=p⋅m). We then show the statement holds for succ(p) and m⋅succ(p)=succ(p)⋅m.
m ⋅ succ(p) = (succ(m) ⋅ p) + succ(m) by the recursive step in the definition of ⋅

(p ⋅ succ(m)) + succ(m) by hypothesis

((p ⋅ m) + p) + succ(m) by the recursive step in the definition of ⋅

((m ⋅ p) + p) + succ(m) by hypothesis

(m ⋅ p) + (p + succ(m)) by the associative property of +

(m ⋅ p) + succ(p + m) by the recursive step in the definition of +

succ((m ⋅ p) + (p + m)) by the recursive step in the definition of ⋅

succ(((m ⋅ p) + p) + m) by the associative property of +

succ(((p ⋅ m) + p) + m) by the commutative property of +

succ((p ⋅ succ(m)) + m) by the recursive step in the definition of ⋅

(p ⋅ succ(m)) + succ(m) by the recursive step in the definition of +

succ(p) ⋅ succ(m) by the recursive step in the definition of ⋅

page revision: 6, last edited: 01 Mar 2018 15:25