Assignment 2 Solutions

This is the second of two assignments and is worth 15% of the total grade. The assignment is due Sunday 6th April 2025, 2359. Submit your solutions digitally on Canvas, a submission box will be open under “Assignments > Assignment 2”.

There are 4 questions for a total of 30 marks.

Please make sure your handwriting is legible. You may scan/take a picture of handwritten solutions, you may also type your solutions. We are not particular about the symbol use if you cannot type out the symbols but please make it clear to us what symbol you were intending to use.

How to submit:

• Submit online on Canvas. There is a submission box on Canvas for you to submit your document. Either .docx, .pdf, or a picture of your written solutions are acceptable as long as we can read your attempts.

• Official due date for submission : Sunday 6th April 2025, 2359

Collaboration Policy:

• You may discuss high-level ideas with your classmates or friends. You should list your collaborators if you do so.
• Do not share your solutions.
• ChatGPT (and other LLMs) are not allowed.
• Your submission must be of your own write-up.

Late Policy:

• No late submissions for the assignment allowed.

---

Question 1 [6 marks]

Given sets $A=\{1,2,3,4,5\}$, $B=\{2,4,6,8\}$, $C=\{x\in \mathbb{Z}:\exists k\in \mathbb{Z}[x=2k]\}$.

Write in set roster notation the following sets:

1. $A\cap B$
2. $A\setminus (B\setminus C)$
3. $A\cap (B\setminus C)$

Solutions

1. $A\cap B=\{2,4\}$
2. $A\setminus (B\setminus C)=A\setminus \varnothing =\{1,2,3,4,5\}$
3. $A\cap (B\setminus C)=A\cap \varnothing =\varnothing$

---

Question 2 [6 marks]

For the following sets, state whether the equality holds or not. If they are equal stating so suffices. If they are not equal, give an example of sets to justify it.

Example question: For example, given the following: $(A\setminus A)\setminus A\stackrel{?}{=}A\setminus (A\setminus A)$

Example answer: This equality does not hold. Consider $A=\{1\}$, then the LHS is $\varnothing$, and the RHS is $A$. Since $\varnothing \ne A$, the equality does not hold.

1. $(A\cup A)\cap (B\setminus A)\stackrel{?}{=}(B\setminus A)$
2. $\{x\in \mathbb{Z}:x^2\le 4\}\stackrel{?}{=}\{x\in \mathbb{Z}:x\le 2\}$

Solutions

1. False. Consider $A=\varnothing$ and $B=\{1\}$. Then, $(A\cup A)\cap (B\setminus A)=\varnothing \cap \{1\}=\varnothing \ne \{1\}=B\setminus A$.
2. False. $-3\in \{x\in \mathbb{Z}:x\le 2\}$ since $-3\le 2$, but $-3\notin \{x\in \mathbb{Z}:x^2\le 4\}$ since $(-3{)}^2=9>4$.

---

Question 3

Consider the following predicate:

$$divides(a,b)\equiv \exists k\in \mathbb{N}[a\cdot k=b]$$

We will relate two numbers $x,y\in \mathbb{N}$, in the following way:

$$R=\{(x,y)\in \mathbb{N}\times \mathbb{N}:\exists k\in \mathbb{N}[k\ne 1\wedge divides(k,x)\wedge divides(k,y)\left]\right\}$$

For example: $(15,10)\in R$, because both $divides(5,10)$ and $divides(5,15)$ are true, and $5\in \mathbb{N}$. Whereas $(2,3)\notin R$, because no such natural number $k\in \mathbb{N}$ besides $1$ satisfies both $divides(k,2)$ and $divides(k,3)$.

Sub-question 1: [6 Marks]

Is $R$ reflexive? In other words, is it true that

$$\forall x\in \mathbb{N}[(x,x)\in R]$$

If it is not true, state that it is false, and give an example value $x$ for which $(x,x)\notin R$. If it is true, prove it.

Sub-question 2: [6 Marks]

Is $R$ anti-symmetric? In other words, is it true that

$$\forall x\in \mathbb{N},\forall y\in \mathbb{N}[(x,y)\in R\wedge (y,x)\in R\to x=y]$$

If it is not true, state that it is false, and give an example values $x,y$ for which $(x,y)\in R$ and $(y,x)\in R$, but $x\ne y$. If it is true, prove it.

Sub-question 1

No, $R$ is not reflexive. Consider $x=1\in \mathbb{N}$. Now, we prove that $(1,1)\notin R$.

Proof:

1. Suppose, for the sake of contradiction, that $(1,1)\in R$.
2. $\exists k\in \mathbb{N}[k\ne 1\wedge divides(k,1)\wedge divides(k,1)]$ [Definition of $R$]
3. Let $n\in \mathbb{N}$ be such that $n\ne 1\wedge divides(n,1)$. [Existential instantiation on line 2]
4. $divides(n,1)$ [Specialisation on line 3]
5. $\exists k\in \mathbb{N}[k\cdot n=1]$ [Definition of $divides$]
6. Let $m\in \mathbb{N}$ be such that $m\cdot n=1$. [Existential instantiation on line 5]
7. $n\ne 1$ [Specialisation on line 3]
8. $n=0\vee n>1$ [Basic algebra]
9. Case 1: $n=0$. Then, $m\cdot n=m\cdot 0=0\ne 1$. [Basic algebra]
10. Case 2: $n>1$. Then, $n\ge 2$, so $m\cdot n\ge 2m\ne 1$. [Basic algebra]
11. Either way, $\neg (m\cdot n=1)$. [Proof by cases on lines 8, 9, 10]
12. $(m\cdot n=1)\wedge \neg (m\cdot n=1)$ [Conjunction on lines 6, 11]
13. $\perp$. [Contradiction rule on line 12]
14. $(1,1)\notin R$. [Proof by contradiction on line 13]

Sub-question 2

No, $R$ is not anti-symmetric. Consider $x=8\in \mathbb{N}$ and $y=10\in \mathbb{N}$.

Proof:

1. $2,4,5\in \mathbb{N}$. [Basic algebra]
2. $(2\cdot 4=8)\wedge (2\cdot 5=10)$ [Basic algebra]
3. $(\exists k\in \mathbb{N}[2\cdot k=8])\wedge (\exists k\in \mathbb{N}[2\cdot k=10])$ [Existential generalisation on lines 1, 2]
4. $divides(2,8)\wedge divides(2,10)$ [Definition of $divides$]
5. $2\ne 1$. [Basic algebra]
6. $\exists k\in \mathbb{N}[k\ne 1\wedge divides(k,8)\wedge divides(k,10)]$ [Existential generalisation on lines 4, 5]
7. $(8,10)\in R$. [Definition of $R$]
8. $divides(2,10)\wedge divides(2,8)$ [Logically equivalent to line 4]
9. $\exists k\in \mathbb{N}[k\ne 1\wedge divides(k,10)\wedge divides(k,8)]$ [Existential generalisation on lines 5, 8]
10. $(10,8)\in R$. [Definition of $R$]
11. $8\ne 10$. [Basic algebra]
12. $R$ is not anti-symmetric. [Definition of anti-symmetry, from lines 7, 10, 11]

---

Question 4: [6 Marks]

Prove via mathematical induction that for all $n\ge 1$:

$$\sum _{r=1}^n\frac{1}{r(r+1)}=\frac{n}{n+1}$$

Solution

Proof:

1. (Base case) Let $n=1$. Then, ${\sum }_{r=1}^1\frac{1}{r(r+1)}=\frac{1}{1(2)}=\frac{1}{2}=\frac{1}{1+1}$.
2. (Inductive step) Assume that for some $n=k$, where $k\ge 1$, we have ${\sum }_{r=1}^k\frac{1}{r(r+1)}=\frac{k}{k+1}$.
3. ${\sum }_{r=1}^{k+1}\frac{1}{r(r+1)}$
4. $=\left({\sum }_{r=1}^k\frac{1}{r(r+1)}\right)+\frac{1}{(k+1)(k+2)}$
5. $=\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}$ [By assumption on line 2]
6. $=\frac{k(k+2)+1}{(k+1)(k+2)}$
7. $=\frac{(k+1{)}^2}{(k+1)(k+2)}$
8. $=\frac{k+1}{(k+1)+1}$
9. $\forall n\ge 1[{\sum }_{r=1}^n\frac{1}{r(r+1)}=\frac{n}{n+1}]$ [Principle of mathematical induction]