**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)$.

**Cancellation of addition (∀m,n,p,m+p=n+p if and only if m=n).**

We induct on $p$.

Base Case: $p=0$

$\Longrightarrow m+0=n+0$.

$\Longrightarrow m=n$

Inductive Hypothesis: There is some $k$ such that $m+k=n+k$ is true.

Inductive Step: $m+Succ(k)=n+Succ(k)$

$Succ(k+m) = Succ(k+n)$

$\Longrightarrow Succ(m+k)=Succ(k+n)$ by commutativity.

$\Longrightarrow Succ(n+k)=Succ(k+n)$ by Inductive hypothesis

$\Longrightarrow Succ (n+k)=Succ(n+k)$ .

$\Longrightarrow k+Succ(n)=Succ(n+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$

**21. (Preliminary for T, March 13; finalized Sat, March 17) Given a partition {Xα}α∈I of X, show that the relation R⊆X×X defined by ((a,b)∈R⇔∃α∈I such that both a,b∈Xα) is an equivalence relation on X whose equivalence classes are precisely the sets Xα of the partition.**

**Pf:**

To prove reflexivity: Since $[(a,b)]=[(a,b)], (a,b)\sim (a,b)$ and since $\{X_{\alpha}\}$ is a partition and $\bigcup\{X_{\alpha}\}_{\alpha \in I} = X$, this is true.

To prove symmetry: suppose there is some $(c,d)\in R$ which implies $\exists \alpha \in I$ such that both $c,d\in X_{\alpha}$.

If $[(a,b)]=[(c,d)]$, then $[(c,d)]=[(a,b)]$ which implies that $(a,b)\sim (c,d)$ implies $(c,d)\sim (a,b)$.

To prove transitivity: Suppose there is another element $(e,f)\in R$ which implies $\exists \alpha \in I$ such that both $e,f\in X_{\alpha}$.

If $[(a,b)]=[(c,d)]$ and$[(c,d)]=[(e,f)]$, then it is implied that if $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)$ then $(a,b)\sim (e,f)$ is implied.

Comments - Andrew Furash

18 looks good. For 21, note that things like (a,b) are in X (cross) X and cannot be equivalent. (a,b) \in R means a (is equivalent to) b.