Tutorial 2 Solutions

How to submit:

• Submit before actual tutorial time for it to be graded. There are 2 ways to do this:
  1. 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.
  2. Submit your written attempts in-person during our tutorial.

• Official due date for submission : 04-Mar-2025, 23:59 or during tutorial itself.

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:

• < 1 week after submission deadline: 50% penalty
• < 2 weeks after submission deadline: 75% penalty
• No submissions after 2 weeks.

Overview

This tutorial gives practice questions to be discussed during the relevant tutorial in person. This particular tutorial sheet corresponds to Unit 2 and Unit 3. It is recommended to either watch the lectures or read the notes for each respective parts before attempting the tutorial sheet.

1. Questions 1 through 4 are related to set theory.
2. Questions 5 through 8 are related to relations.

After week 5’s content, you should be able to attempt questions 1 through 4. After week 6’s content, you should be able to attempt questions 5 through 8.

Questions 2, 4, 5, 7 are graded for participation.

That said, we encourage you to try all the questions, this way when you come for tutorial we can best make use of your time since you can either verify your solutions, or understand the discussions when our tutors go through the solutions.

---

Question 1

Let $A=\{0\}$, and $B=\mathcal{P}(\{0,1\})$.

Find $\mathcal{P}(A)$ and $\mathcal{P}(B)$.

Solutions:

$\mathcal{P}(A)=\{\varnothing ,\{0\}\}$. Observe that $\mathcal{P}(A)$ has $2^{|A|}=2^1=2$ elements.

$\mathcal{P}(\{0,1\})=\{\varnothing ,\{0\},\{1\},\{0,1\}\}$, so:

$$\begin{array}{rl}\mathcal{P}(B)=\{& \\ & \varnothing ,\\ & \\ & \{\varnothing \},\{\{0\}\},\{\{1\}\},\{\{0,1\}\},\\ & \\ & \{\varnothing ,\{0\}\},\{\varnothing ,\{1\}\},\{\varnothing ,\{0,1\}\},\{\{0\},\{1\}\},\{\{0\},\{0,1\}\},\{\{1\},\{0,1\}\},\\ & \\ & \{\varnothing ,\{0\},\{1\}\},\{\varnothing ,\{0\},\{0,1\}\},\{\varnothing ,\{1\},\{0,1\}\},\{\{0\},\{1\},\{0,1\}\},\\ & \\ & \{\varnothing ,\{0\},\{1\},\{0,1\}\}\\ \}& \end{array}$$

Observe that $\mathcal{P}(B)$ has $2^{|B|}=2^4=16$ elements.

---

Question 2 [Graded for Participation]

Consider the sets $A=\{x\in \mathbb{Z}:x^2\le 16\}$ and $B=\{x\in \mathbb{N}:(x\ge 1)\wedge (\exists k\in \mathbb{Z}[x=3k+1]\left)\right\}$, $C=\{1,2\}$.

Find the following sets:

1. $A\cap B$
2. $A\cup B$
3. $A\setminus C$
4. $A\times C$

Note: Some of these can be written using Set Roster Notation, these are the ones where you can list them out one by one. For the rest, you can write them using set builder notation.

Solutions:

First, we write out $A$ in set-roster notation: $A=\{-4,-3,-2,-1,0,1,2,3,4\}$.

Next, set $B$ is simply all the positive natural numbers that are $1$ greater than a multiple of $3$.

Then, we have the following sets:

1. $A\cap B=\{1,4\}$
2. $A\cup B=\{x\in \mathbb{Z}:(x^2\le 16)\vee ((x\ge 1)\wedge (\exists k\in \mathbb{Z}[x=3k+1])\}$
3. $A\setminus C=\{-4,-3,-2,-1,0,3,4\}$

$$\begin{array}{rl}A\times C=\{& \\ & (-4,1),(-3,1),(-2,1),(-1,1),(0,1),(1,1),(2,1),(3,1),(4,1),\\ & (-4,2),(-3,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(3,2),(4,2)\\ & \}\end{array}$$

---

Question 3

Convert the following from set builder notation to set roster notation:

1. $A=\{x\in \mathbb{Z}:x=5\vee x=10\}$
2. $B=\{x\in \mathbb{N}:(x>1)\wedge (x<10)\wedge even(x)\}$
3. $C=\{x\in \mathbb{Z}:\exists k\in \mathbb{Z}[(x=7k)\wedge (x\ge 0)\wedge (x<60)\}$.
4. $D=\{x\in \mathbb{Z}:\forall a,b\in \mathbb{N}[(x<10)\wedge (x>1)\wedge ((x=ab)\to (a=1\wedge b=x)\vee (a=x\wedge b=1))\left]\right\}$

Hint for $D$: It might be helpful to first think about what it’s trying to do. That might speed things up for you.

Solutions:

1. $A=\{5,10\}$
2. $B=\{2,4,6,8\}$
3. $C=\{0,7,14,21,28,35,42,49,56\}$
4. $D=\{2,3,5,7\}$, i.e., the set of prime numbers between $1$ and $10$

---

Question 4 [Graded for Participation]

Prove the set equality $(A\setminus B)\setminus C=(A\setminus C)\setminus (B\cup C)$.

Prove the set equality $(A\setminus B)\cup C=(A\cup C)\setminus (B\setminus C)$.

Hint: Based on logical equivalences shows a method that is helpful.

Solutions:

The first problem is equivalent to the following: $(a\wedge \neg b)\wedge \neg c\equiv (a\wedge \neg c)\wedge \neg (b\vee c)$

Using a truth table, we see that this equivalence is true:

$a$	$b$	$c$	$\neg b$	$\neg c$	$a\wedge \neg b$	$a\wedge \neg c$	$b\vee c$	$\neg (b\vee c)$	$(a\wedge \neg b)\wedge \neg c$	$(a\wedge \neg c)\wedge \neg (b\vee c)$
$true$	$true$	$true$	$false$	$false$	$false$	$false$	$true$	$false$	$false$	$false$
$true$	$true$	$false$	$false$	$true$	$false$	$true$	$true$	$false$	$false$	$false$
$true$	$false$	$true$	$true$	$false$	$true$	$false$	$true$	$false$	$false$	$false$
$true$	$false$	$false$	$true$	$true$	$true$	$true$	$false$	$true$	$true$	$true$
$false$	$true$	$true$	$false$	$false$	$false$	$false$	$true$	$false$	$false$	$false$
$false$	$true$	$false$	$false$	$true$	$false$	$false$	$true$	$false$	$false$	$false$
$false$	$false$	$true$	$true$	$false$	$false$	$false$	$true$	$false$	$false$	$false$
$false$	$false$	$false$	$true$	$true$	$false$	$false$	$false$	$true$	$false$	$false$

Hence, $(A\setminus B)\setminus C=(A\setminus C)\setminus (B\cup C)$.

The second problem is equivalent to the following: $(a\wedge \neg b)\vee c\equiv (a\vee c)\wedge \neg (b\wedge \neg c)$

Using a truth table, we see that this equivalence is also true:

$a$	$b$	$c$	$\neg b$	$\neg c$	$a\wedge \neg b$	$a\vee c$	$b\wedge \neg c$	$\neg (b\wedge \neg c)$	$(a\wedge \neg b)\vee c$	$(a\vee c)\wedge \neg (b\wedge \neg c)$
$true$	$true$	$true$	$false$	$false$	$false$	$true$	$false$	$true$	$true$	$true$
$true$	$true$	$false$	$false$	$true$	$false$	$true$	$true$	$false$	$false$	$false$
$true$	$false$	$true$	$true$	$false$	$true$	$true$	$false$	$true$	$true$	$true$
$true$	$false$	$false$	$true$	$true$	$true$	$true$	$false$	$true$	$true$	$true$
$false$	$true$	$true$	$false$	$false$	$false$	$true$	$false$	$true$	$true$	$true$
$false$	$true$	$false$	$false$	$true$	$false$	$false$	$true$	$false$	$false$	$false$
$false$	$false$	$true$	$true$	$false$	$false$	$true$	$false$	$true$	$true$	$true$
$false$	$false$	$false$	$true$	$true$	$false$	$false$	$false$	$true$	$false$	$false$

Hence, $(A\setminus B)\cup C=(A\cup C)\setminus (B\setminus C)$.

For those who are interested in reading more rigorous proofs:

Proof: $(A\setminus B)\setminus C=(A\setminus C)\setminus (B\cup C)$

1. $(\subseteq )$ Let $x\in (A\setminus B)\setminus C$ be arbitrarily chosen.
2. $(x\in A\setminus B)\wedge (x\notin C)$ [Definition of set difference]
3. $(x\in A)\wedge (x\notin B)\wedge (x\notin C)$ [Definition of set difference]
   1. $(x\in A)$ [Specialisation on line 1.2]
   2. $(x\notin B)$ [Specialisation on line 1.2]
   3. $(x\notin C)$ [Specialisation on line 1.2]
4. $(x\in A)\wedge (x\notin C)$ [Conjunction on lines 1.2.1, 1.2.3]
5. $x\in A\setminus C$ [Definition of set difference]
6. $(x\notin B)\wedge (x\notin C)$ [Conjunction on lines 1.2.2, 1.2.3]
7. $\neg ((x\in B)\vee (x\in C))$ [Logically equivalent to line 1.5]
8. $\neg (x\in B\cup C)$ [Definition of set union]
9. $x\notin B\cup C$ [Equivalent to line 1.7]
10. $(x\in A\setminus C)\wedge (x\notin B\cup C)$ [Conjunction on lines 1.4, 1.8]
11. $x\in (A\setminus C)\setminus (B\cup C)$ [Definition of set difference]
12. $\forall x\in (A\setminus B)\setminus C[x\in (A\setminus C)\setminus (B\cup C)]$ [Universal generalisation on lines 1, 1.10]
13. $(A\setminus B)\setminus C\subseteq (A\setminus C)\setminus (B\cup C)$ [Definition of subset]
14. $(\supseteq )$ Let $x\in (A\setminus C)\setminus (B\cup C)$ be arbitrarily chosen.
15. $(x\in A\setminus C)\wedge (x\notin B\cup C)$ [Definition of set difference]
16. $(x\in A)\wedge (x\notin C)\wedge (x\notin B\cup C)$ [Definition of set difference]
17. $(x\in A)\wedge (x\notin C)\wedge \neg (x\in B\cup C)$ [Equivalent to line 2.2]
18. $(x\in A)\wedge (x\notin C)\wedge \neg ((x\in B)\vee (x\in C))$ [Definition of set union]
19. $(x\in A)\wedge (x\notin C)\wedge (x\notin B)\wedge (x\notin C)$ [Logically equivalent to line 2.4]
    1. $x\in A$ [Specialisation on line 2.5]
    2. $x\notin B$ [Specialisation on line 2.5]
    3. $x\notin C$ [Specialisation on line 2.5]
20. $(x\in A)\wedge (x\notin B)$ [Conjunction on lines 2.5.1, 2.5.2]
21. $x\in A\setminus B$ [Definition of set difference]
22. $(x\in A\setminus B)\wedge (x\notin C)$ [Conjunction on lines 2.7, 2.5.3]
23. $x\in (A\setminus B)\setminus C$ [Definition of set difference]
24. $\forall x\in (A\setminus C)\setminus (B\cup C)[x\in (A\setminus B)\setminus C]$ [Universal generalisation on lines 2, 2.9]
25. $(A\setminus C)\setminus (B\cup C)\subseteq (A\setminus B)\setminus C$ [Definition of subset]
26. $((A\setminus B)\setminus C\subseteq (A\setminus C)\setminus (B\cup C))\wedge ((A\setminus C)\setminus (B\cup C)\subseteq (A\setminus B)\setminus C)$ [Conjunction on lines 1.12, 2.11]
27. $(A\setminus B)\setminus C=(A\setminus C)\setminus (B\cup C)$ [Definition of set equality]

Proof: $(A\setminus B)\cup C=(A\cup C)\setminus (B\setminus C)$

1. $(\subseteq )$ Let $x\in (A\setminus B)\cup C$ be arbitrarily chosen.
2. $((x\in A)\wedge (x\notin B))\vee (x\in C)$. [Definition of set difference]
3. Case 1: $(x\in A)\wedge (x\notin B)$
   1. $x\in A$ [Specialisation on line 1.2]
   2. $x\notin B$ [Specialisation on line 1.2]
   3. $(x\in A)\vee (x\in C)$ [Generalisation on line 1.2.1]
   4. $x\in A\cup C$ [Definition of set union]
   5. $(x\notin B)\vee (x\in C)$ [Generalisation on line 1.2.2]
   6. $\neg ((x\in B)\wedge (x\notin C))$ [Logically equivalent to line 1.2.5]
   7. $\neg (x\in B\setminus C)$ [Definition of set difference]
   8. $x\notin B\setminus C$ [Equivalent to line 1.2.7]
   9. $(x\in A\cup C)\wedge (x\notin B\setminus C)$ [Conjunction on lines 1.2.4, 1.2.8]
   10. $x\in (A\cup C)\setminus (B\setminus C)$ [Definition of set difference]
4. Case 2: $x\in C$
   1. $(x\in A)\vee (x\in C)$ [Generalisation on line 1.3]
   2. $(x\notin B)\vee (x\in C)$ [Generalisation on line 1.3]
   3. $\neg ((x\in B)\wedge (x\notin C))$ [Logically equivalent to line 1.3.2]
   4. $\neg (x\in B\setminus C)$ [Definition of set difference]
   5. $x\notin B\setminus C$ [Equivalent to line 1.3.4]
   6. $(x\in A\cup C)\wedge (x\notin B\setminus C)$ [Conjunction on lines 1.3.1, 1.3.5]
   7. $x\in (A\cup C)\setminus (B\setminus C)$ [Definition of set difference]
5. $x\in (A\cup C)\setminus (B\setminus C)$ [Proof by cases on lines 1.1, 1.2.10, 1.3.7]
6. $\forall x\in (A\setminus B)\cup C[x\in (A\cup C)\setminus (B\setminus C)]$ [Universal generalisation on lines 1, 1.4]
7. $(A\setminus B)\cup C\subseteq (A\cup C)\setminus (B\setminus C)$ [Definition of subset]
8. $(\supseteq )$ Let $x\in (A\cup C)\setminus (B\setminus C)$ be arbitrarily chosen.
9. $(x\in A\cup C)\wedge (x\notin B\setminus C)$ [Definition of set difference]
10. $((x\in A)\vee (x\in C))\wedge (x\notin B\setminus C)$ [Definition of set union]
11. $((x\in A)\vee (x\in C))\wedge \neg (x\in B\setminus C)$ [Equivalent to line 2.2]
12. $((x\in A)\vee (x\in C))\wedge \neg ((x\in B)\wedge (x\notin C)$ [Definition of set difference]
13. $((x\in A)\vee (x\in C))\wedge ((x\notin B)\vee (x\in C)$ [Logically equivalent to line 2.4]
14. $(x\in C)\vee ((x\in A)\wedge (x\notin B))$ [Logically equivalent to line 2.5]
15. Case 1: $x\in C$
    1. $(x\in A\setminus B)\vee (x\in C)$ [Generalisation on line 2.7]
    2. $x\in (A\setminus B)\cup C$ [Definition of set union]
16. Case 2: $(x\in A)\wedge (x\notin B)$
    1. $x\in A\setminus B$ [Definition of set difference]
    2. $(x\in A\setminus B)\vee (x\in C)$ [Generalisation on line 2.8]
    3. $x\in (A\setminus B)\cup C$ [Definition of set union]
17. $x\in (A\setminus B)\cup C$ [Proof by cases on lines 2.6, 2.7.2, 2.8.3]
18. $\forall x\in (A\cup C)\setminus (B\setminus C)[x\in (A\setminus B)\cup C]$ [Universal generalisation on lines 2, 2.9]
19. $(A\cup C)\setminus (B\setminus C)\subseteq (A\setminus B)\cup C$ [Definition of subset]
20. $((A\setminus B)\cup C\subseteq (A\cup C)\setminus (B\setminus C))\wedge ((A\cup C)\setminus (B\setminus C)\subseteq (A\setminus B)\cup C)$ [Conjunction on lines 1.6, 2.11]
21. $(A\setminus B)\cup C=(A\cup C)\setminus (B\setminus C)$ [Definition of set equality]

---

Question 5 [Graded for Participation]

Let $R$ be the following relation:

$$R=\{(1,2),(3,3),(2,1),(5,6),(6,7),(7,8)\}$$

Compute $R^{-1}$. Compute $R;R$.

It might be helpful to refer to Operations on Relations.

Solution:

Solution

$R^{-1}=\{(2,1),(3,3),(1,2),(6,5),(7,6),(8,7)\}$

$R;R=\{(1,1),(2,2),(3,3),(5,7),(6,8)\}$

---

Question 6

Let $A$ be the following set: $A=\{0,1,2\}$. Let $R=A\times A$.

Sub-part 1

Is the following statement true?

$R$ is reflexive.

If it is true, prove it. Otherwise, prove the negation of the statement. It might be helpful to refer to Reflexivity.

Solutions:

True.

Proof: $R$ is reflexive

1. Let $x\in A$ be arbitrarily chosen.
2. $(x\in A)\wedge (x\in A)$ [Conjunction on line 1]
3. $(x,x)\in A\times A$ [Definition of cartesian product]
4. $(x,x)\in R$ [Definition of $R$]
5. $\forall a\in A[(a,a)\in R]$ [Universal generalisation on lines 1, 4]
6. $R$ is reflexive. [Definition of reflexivity]

Sub-part 2

Is the following statement true?

$R$ is symmetric.

If it is true, prove it. Otherwise, prove the negation of the statement. It might be helpful to refer to Symmetry.

Solutions:

True.

Proof: $R$ is symmetric

1. Let $x\in A$ and $y\in A$ be arbitrarily chosen.
2. Suppose that $(x,y)\in R$.
3. $(y\in A)\wedge (x\in A)$ [Conjunction on line 1]
4. $(y,x)\in A\times A$ [Definition of cartesian product, from line 2.1]
5. $(y,x)\in R$ [Definition of $R$]
6. $(x,y)\in R\to (y,x)\in R$ [Implication introduction on lines 2, 2.3]
7. $\forall a\in A,b\in A[(a,b)\in R\to (b,a)\in R]$ [Universal generalisation on lines 1, 3]
8. $R$ is symmetric. [Definition of symmetry]

Sub-part 3

Is the following statement true?

$R$ is anti-symmetric.

If it is true, prove it. Otherwise, prove the negation of the statement. It might be helpful to refer to Anti-Symmetry.

Solutions:

False.

Proof: $R$ is not antisymmetric

Lets start by taking the negation of the statement for antisymmetry. If we are be able to prove that the negation is true we can prove the the original statement is false. $\neg (\forall a\in A,\forall b\in A[((a,b)\in R\wedge (b,a)\in R)\to a=b])$ $\equiv \exists a\in A,\exists b\in A\neg [((a,b)\in R\wedge (b,a)\in R)\to a=b]$ [Negating universal quantifiers] $\equiv \exists a\in A,\exists b\in A\neg [\neg ((a,b)\in R\wedge (b,a)\in R)\vee a=b]$ [Logically equivalent] $\equiv \exists a\in A,\exists b\in A[((a,b)\in R\wedge (b,a)\in R)\wedge a\ne b]$ [Logically equivalent]

1. $0\in A$
2. $1\in A$.
3. $(0,1)\in A\times A$ [Definition of cartesian product, from line 1]
4. $(0,1)\in R$ [Definition of R]
5. $(1,0)\in A\times A$ [Definition of cartesian product, from line 1]
6. $(1,0)\in R$ [Definition of R]
7. $(0,1)\in R\wedge (1,0)\in R$ [Conjunction on lines 4 and 6]
8. $0\ne 1$ [By basic algebra]
9. $((0,1)\in R\wedge (1,0)\in R)\wedge (0\ne 1)$ [Conjunction on lines 7 and 8]
10. Therefore, $\exists a\in A,b\in A[((a,b)\in R\wedge (b,a)\in R)\wedge a\ne b]$ [Existential generalization]
11. Since the negation of antisymmetry is true for $R$, therefore $R$ is not antisymmetric [Definition of antisymmetry]

Sub-part 4

Is the following statement true?

$R$ is transitive.

If it is true, prove it. Otherwise, prove the negation of the statement. It might be helpful to refer to Transitivity.

Solutions:

True.

Proof: $R$ is transitive

1. Let $x\in A$, $y\in A$ and $z\in A$ be arbitrarily chosen.
2. Suppose that $(x,y)\in R\wedge (y,z)\in R$.
3. Since $(x\in A)\wedge (z\in A)$, $(x,z)\in A\times A$. [Definition of cartesian product, from line 1]
4. $(x,z)\in R$ [Definition of $R$]
5. $((x,y)\in R\wedge (y,z)\in R)\to (x,z)\in R$ [Implication introduction on lines 2, 2.2]
6. $\forall a\in A,b\in A,c\in A[((a,b)\in R\wedge (b,c)\in R)\to (a,c)\in R]$ [Universal generalisation on lines 1, 3]
7. $R$ is transitive. [Definition of transitive]

---

Question 7 [Graded for Participation]

Is the following statement true?

Let $A$ be any set. Let $R\subseteq A\times A$.

If $R$ is symmetric, then $R;R$ is reflexive.

If it is, prove it. If it is not, give examples of $A$ and $R$ such that the $R$ is symmetric, but $R;R$ is not reflexive.

Solutions:

Solution

False.

Consider the set $A=\{1,2\}$. Then $A\times A=\{(1,1),(2,2),(1,2),(2,1)\}$. Let $R=\{(1,1)\}$. Then $R;R=\{(1,1)\}$.

Since $(1,1)\in R$, we need $(1,1)\in R$ for $R$ to be symmetric, which is true.

However, $R;R$ is not reflexive, since $2\in A$ but $(2,2)\notin R;R$.

---

Question 8

Is the following statement true?

Let $A$ be any set. Let $R\subseteq A\times A$.

If $R$ is both reflexive and anti-symmetric, then $R$ is not symmetric.

If it is, prove it. If it is not, give examples of $A$, and $R$ such that the $R$ is both reflexive and anti-symmetric, but $R$ is not symmetric.

Correction:

If it is, prove it. If it is not, give examples of $A$ and $R$ such that the $R$ is both reflexive and anti-symmetric, but $R$ is also symmetric.

Solutions:

Solution

False.

Consider $A=\{1,2\}$. Then $A\times A=\{(1,1),(2,2),(1,2),(2,1)\}$. Let $R=\{(1,1),(2,2)\}\subseteq A\times A$.

Clearly, $R$ is reflexive, since both $(1,1)$ and $(2,2)$ are in $R$.

Next, $R$ is also anti-symmetric. Let’s examine the elements of $R$.

1. For $(1,1)$, we have $(1,1)\in R\wedge (1,1)\in R$, and $1=1$.
2. Similarly, for $(2,2)$, we have $(2,2)\in R\wedge (2,2)\in R$, and $2=2$.

Hence, $R$ is anti-symmetric.

It is easy to check that $R$ is symmetric as well.