Paper 4, Section II, E

(i) Let $\sim$ be an equivalence relation on a set $X$. What is an equivalence class of $\sim$ ? What is a partition of $X ?$ Prove that the equivalence classes of $\sim$ form a partition of $X$.

(ii) Let $\sim$ be the relation on the natural numbers $\mathbb{N}=\{1,2,3, \ldots\}$ defined by

$m \sim n \Longleftrightarrow \exists a, b \in \mathbb{N} \text { such that } m \text { divides } n^{a} \text { and } n \text { divides } m^{b} .$

Show that $\sim$ is an equivalence relation, and show that it has infinitely many equivalence classes, all but one of which are infinite.

*Typos? Please submit corrections to this page on GitHub.*