Questions 18 & 21 Post Write

18. a. Prove by induction that $+:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is commutative ($\forall m,n, \, \,\, m+n=n+m$) and satisfies cancellation ($\forall m,n,p, \,\,\, m+p=n+p$ if and only if $m=n$).
n+0=n, given n+m, n+succ(m)=succ(n+m)

To prove that $+:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is commutative, we begin by inducting on n. To show the base case, m+0=0+m we induct on m.
For the base case on m+0=0+m, 0+0=0+0 is true. We then assume that m+0=0+m for all m and show that it holds for succ(m)+0=0+succ(m).
0+succ(m)=
succ(0+m)= from 1 by the recursive step of addition
succ(m+0)= from 2 by the inductive hypothesis
succ(m)+0 from 3 by the recursive step of addition
As the base case m+0=0+m has been proven, we assume that m+n=n+m holds for all n and show that it holds for m+succ(n)=succ(n)+m. We do this by inducting on m.
We have already proved the additive property of zero so the base case, 0+succ(n)=succ(n)+0, is true. We then assume m+succ(n)=succ(n)+m holds for all m and prove that it is true for succ(m)+succ(n)=succ(n)+succ(m).
succ(m)+succ(n)=
succ(succ(m)+n))= from 1 by the recursive step of addition
succ(n+succ(m))= from 2 by the inductive hypothesis
succ(succ(n+m))= from 3 by the recursive step
succ(succ(m+n))= from 4 by the inductive hypothesis
succ(n)+succ(m)= from 5 by the recursive step

To prove that $+:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ satisfies cancellation, we begin by induction on p. The base case, m+0=0+n, is proven by the additive property of 0. Thus m=n. We then assume m+p=n+p is true and show m+succ(p)=n+succ(p).
succ(m+p)=succ(n+p)
m+p=n+p
m=n

b. Prove by induction that $\cdot :\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is associative ($\forall m,n,p, \, \,\, m \cdot (n\cdot p) =(m\cdot n)\cdot p$), commutative ($\forall m,n,\,\, \, m \cdot n=n \cdot m$), satisfies cancellation for nonzero values ($\forall m,n,p, \,\,\, m\cdot p=n \cdot p$ implies that $m=n$ if $p\neq 0$), and distributes over addition
($\forall m,n,p,\,\, \, m\cdot (n+p) = m\cdot n + m\cdot p$).
Lemma1:
Statement: succ(n)=n+1
Proof: By definition, succ(0)=1 and n+succ(0)=succ(n+0) by the recursive step of addition. n+0=n and n+1=succ(n).
To prove that $\cdot :\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is commutative we begin by inducting on n. We can prove the base case m⋅0=0⋅m by inducting on m.
0⋅0=0⋅0
We then assume it holds for m⋅0=0⋅m and show it holds for succ(m)⋅0=0⋅succ(m).
succ(m)⋅0=0 by definition
0⋅succ(m)=0⋅m+0 by the recursive definition of multiplication
m⋅0+0=0+0 by the inductive hypothesis
0=0
We can now assume that m⋅n=n⋅m and prove that m⋅succ(n)=succ(n)+m. We do this by once again inducting on m.
The base case, 0⋅succ(n)+succ(n)⋅0 is true by the zero identity. We then assume that m⋅succ(n)=succ(n)+m holds and show that succ(m)⋅succ(n)=succ(n)⋅succ(m) is true.
succ(n)⋅succ(m)=succ(n)⋅m+succ(n) by the recursive step of multiplication
=m⋅succ(n)+succ(n) by the inductive hypothesis
=m⋅n+m+succ(n) by the recursive step of multiplication
=m⋅n+m+n+1 by Lemma1

m⋅n+n+succ(m) by Lemma1

=n⋅succ(m)+succ(m) by the recursive step of multiplication
=succ(m)+succ(n) by the recursive step of multiplication

To prove that $\cdot :\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ distributes over addition we begin by inducting on m. For the base case, we must show that 0∙(n+p)=0∙n+0∙p.
0∙(n+p)=0 by the zero identity
0∙n=0 by the zero identity
0∙p=0 by the zero identity
0+0=0
0=0
We then assume m∙(n+p)=m∙n+m∙p for all m and show that it holds for succ(m)∙(n+p)=succ(m)∙n+succ(m)∙p.
(n+p)∙succ(m)=n∙succ(m)+p∙succ(m) from 1 by the commutative property of multiplication
(n+p)∙m+(n+p)=n∙m+n+p∙m+p from 2 by the recursive step of multiplication
m∙(n+p)+(n+p)=(n∙m)+(p∙m)+(n+p) from 3 by the commutative property
(m∙n)+(m∙p)+(n+p)=(n∙m)+(p∙m)+(n+p) from 4 by the inductive hypothesis
(n∙m)+(p∙m)+(n+p)= (n∙m)+(p∙m)+(n+p) from 5 by the commutative property of multiplication

To prove that $\cdot :\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is associative we begin by inducting on p. For the base case, we must show that (m∙n)∙0=m∙(n∙0).
n∙0=0
m∙(n∙0)=0
m∙(0)=0
(m∙n)∙0=0
0=0
We then assume that (m∙n)∙p=m∙(n∙p) holds for any p and show that it is true for (m∙n)∙succ(p)=m∙(n∙succ(p)).
(m∙n)∙p+(m∙n)=m∙(n∙p+n) by the recursive step of multiplication
m∙(n∙p+n)=m∙(n∙p)+(m∙n) from 1 by the fact that multiplication distributes over addition
m∙(n∙p)+(m∙n)= (m∙n)∙p+(m∙n) from 2 by the inductive hypothesis

Lemma2
Statement: n⋅1=n
Proof: By definition, succ(0)=1 and n⋅succ(0)=n⋅0+n by the recursive step of addition. n⋅0=0 and n⋅1=n.
To prove that $\cdot :\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ satisfies cancellation for nonzero values we begin by inducting on p. We prove the base case p=1 for m⋅1=n⋅1.
m⋅1=m by Lemma2
n⋅1=n by Lemma2
m=n
We then assume m⋅p=n⋅p holds and prove m⋅succ(p)=n⋅succ(p).
m⋅p+m=n⋅p+n by the recursive step of multiplication
m⋅p+m=n⋅p+m by the inductive hypothesis
n⋅p+m=n⋅p+n
m=n

21. Given a partition $\{X_{\alpha}\}_{\alpha\in I}$ of $X$, show that the relation $R\subseteq X\times X$ defined by $((a,b)\in R \Leftrightarrow \exists \alpha\in I \text{ such that both } a,b\in X_{\alpha})$ is an equivalence relation on $X$ whose equivalence classes are precisely the sets $X_{\alpha}$ of the partition.

Consider a set S and an equivalence relation ∼ on S such that the equivalence classes are [a]={x∈S:x∼a}. By definition, these are subsets of S. Their union is S because, by reflexivity, a∈[a] for every a∈S. Finally, they are disjoint because if x∈[a] and x∈[b], then x∼a and a∼x(by symmetry). By transitivity, it follows that a∼b and so a∈[b]. Every y∈[a] is also in [b] (by transitivity). This means that [a]⊆[b]. Swapping a and b, we conclude [a]=[b]. All this means that the equivalence classes form a partition of S.
To show it holds for the other direction, given a partition of S in subsets Cλ, an equivalence relation in S by a∼b exists if and only if there is a λ such that a and b are both in Cλ. Since Cλ covers the partition in S, every a∈S is in one of those and so ∼ is reflexive. By definition, ∼ is symmetric. Since the Cλ are disjoint, ∼ is transitive.