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$).
Rules of Addition:
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.

Comments - Andrew Furash
There are a few small typos in your proof and your base cases are not always proven. For 21, you do not prove that R is an equivalence relation. You do not mention the parts of the partition and do not prove that the equivalence classes are the parts of the partition.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License