7.3 Workshop 3 (Construction)

In this workshop, work on solving all of the following seven problems. You are encouraged to discuss the problems with those in your group but DO NOT work on writing the proofs up together.

•

Your assessed problem H04 is Question 7. You must solve this problem, write up its proof and submit it on Gradescope as part of your portfolio assessment by the deadline stated below. Your write-up of the assessed proof must be your OWN work.
•

More guidance on submitting and resubmitting your proofs can be found on IMU Learn $\rightarrow$ Assessment.
•

You will be expected to talk and answer questions about your solutions to the remaining problems with your group in the Communication workshop next week.
•

You are free to use any of the results in the summary notes in your proofs if they are relevant to your solution.

Important Dates

•

DEADLINE FOR ASSESSED PROOF H04: 10:00AM Tuesday 4th November 2025
•

H04 Feedback returned: 10:00AM Monday 10th November 2025
•

H04 Resubmission deadline: 10:00AM Tuesday 18th November 2025 (Remember to include your reflection!)
•

H04 Final deadline: 10:00AM Friday 28th November 2025
•

H04 RESIT DEADLINE: 10:00AM Friday 24th April 2026

7.3.1 Problems

1.

Suppose $R$ is a symmetric and transitive relation on a set $X$ and, for all $y\in X$ , there is an element $x\in X$ such that $xRy$ . Prove that $R$ is an equivalence relation.
2.

Consider the relation $\sim$ on $\mathbb{R}$ where, for every $x,y\in\mathbb{R}$ , $x\sim y$ if $\cos(x)=\cos(y)$ . Show that $\sim$ is an equivalence relation with an uncountable number of equivalence classes.

You may use standard properties of the function $\cos(x)$ without proof.
3.

Prove that the set $\{5n+3:n\in\mathbb{N}\}$ does not contain a square number.
4.

H04 Resit: Let $\mathbb{P}$ denote the set of all prime numbers and define the relation

$T=\{(x,y)\in\mathbb{P}^{2}:xy=m^{2}\text{ for some }m\in\mathbb{Z}\}$

on $\mathbb{P}$ . Is $T$ reflexive, symmetric or transitive? Prove your claims.
5.

Let $R$ be an equivalence relation on $\mathbb{Z}$ with the property that for all $y\in\mathbb{Z}$ , $yR(y+5)$ and $yR(y+8)$ . Prove that $[m]=\mathbb{Z}$ for every $m\in\mathbb{Z}$ .
6.

Let $n$ be an integer with $n\geq 2$ . Show that, if $x\in\mathbb{Z}/n$ , then either there exists $y\in\mathbb{Z}/n$ such that $xy=1\mod n$ or there exists $y\in\mathbb{Z}/n\setminus\{0\}$ such that $xy=0\mod n$ .
7.

H04: Let $R$ and $S$ be equivalence relations on a set $X$ . Prove that $R\cap S$ is an equivalence relation on $X$ whose equivalence classes are of the form $[x]=[x]_{R}\cap[x]_{S}$ where $[x]_{R}$ and $[x]_{S}$ denote the equivalence class of $x\in X$ with respect to $R$ and $S$ respectively.