Prelim Problems 18 a&b J.O.

**18. a. 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).
$n+m=m+n$
Induct on $n$.
Base case:
$0+m = m+0$.
Induct on m.
Base Case:
$0+0=0+0$
Inductive Hypothesis: $0+K = K+0$
Inductive Step: $0+ Succ(K) = Succ(K) + 0$
$\Longrightarrow = Succ(K+0)$
$\Longrightarrow = Succ(K)$
Inductive Hypothesis: $K+ m = m + K$
Inductive Step for original:
$Succ(K) + m = m+ Succ(K)$
Base case for this:
$Succ(K) + 0 = 0 + Succ(K)$ which holds because of past induction.
Inductive Hypothesis:
$Succ(K) + j = j+ Succ(K)$
Inductive Step:
$Succ(K) + Succ(j) = Succ(j) + Succ(K)$
$\Longrightarrow Succ(K+j) = Succ(j) + Succ(K)$
$\Longrightarrow Succ(j+K) = Succ(j)+Succ(K)$.

b. Prove by induction that ⋅: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).**
Associativity:
$m\times (n\times p) = (m\times n)\times p)$
Induce on p
Obviously true for p=0
$m\times (n\times j) = (m\times n)\times j$
$m\times (n\times Succ(j) = (m\times n) \times Succ(j)$
$m\times (n\times j + n) = (m\times n)\times j + m\times n$
$m\times (n\times j + n) = m\times(n\times j) + m\times n$
$(m\times n)\times j + m\times n = (m\times n)\times j + m\times n$

Commutativity:
$m\times n = n\times m$
Induct on n:
$m\times 0 = 0\times m$
Induct on m:
Obviously true for m=0
$j\times 0 = 0\times j$
$Succ(j) \times 0 = 0\times Succ(j)$
$\Longrightarrow Succ(j)\times 0 = 0\times j + 0$
$0 = 0$
Back to original:
$m\times 0 = 0\times m$
$\Longrightarrow m\times K = K\times m$
$m\times Succ(K) = Succ(K) \times m$
$m\times K +m = Succ(K) \times m$
Using inductive hypothesis:
$K\times m +m = Succ(K) \times m$

Cancellation over nonzero values:
$m\times p = n\times p$ implies that $m=n$.
Induct on m
$0\times p = n\times p$
$p\times 0 = n\times p$
$0= n\times p$
If $p \neq 0, then n=0 when m=0$
$K\times p = n\times p$
Suppose K=n,
$Succ(K)\times p = Succ(n) \times p$
$p\times Succ(K) = Succ(n) \times p$
$p\times K +p = Succ(n \times p$
$n\times p + p = Succ(n) \times p$

Distributive:
$m\times (n\times p)=m\times n +m\times p$
Induct on p
The statement is true for p=0.
$m\times (n+K) = m\times n + m\times K$
$m\times (n+ Succ(K)) = m\times n + m\times Succ(K)$
$m\times Succ(n+K) = m\times n + m\times K +m$
$m\times (n+K) +m = m\times n + m\times K + m$
$m\times n + m\times K + m = m\times n + m\times K + m$

page revision: 6, last edited: 14 Mar 2018 22:47