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.