4.I.2D

Numbers and Sets
Part IA, 2008

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

(b) Let Z+\mathbb{Z}^{+}be the set of all positive integers. Let a relation \sim be defined on Z+\mathbb{Z}^{+}by setting mnm \sim n if and only if m/n=2km / n=2^{k} for some (not necessarily positive) integer kk. Prove that \sim is an equivalence relation, and give an example of a set AZ+A \subset \mathbb{Z}^{+}that contains precisely one element of each equivalence class.