18 and 21 Finalized Problems 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)$.

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.

page revision: 3, last edited: 20 Mar 2018 22:00