Paper 4, Section II, E

Numbers and Sets | Part IA, 2015

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

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

mna,bN such that m divides na and n divides mb.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.