Paper 4, Section I, E

Numbers and Sets
Part IA, 2011

What is an equivalence relation on a set X?X ? If \sim is an equivalence relation on XX, what is an equivalence class of \sim ? Prove that the equivalence classes of \sim form a partition of XX.

Let \sim be the relation on the positive integers defined by xyx \sim y if either xx divides yy or yy divides xx. Is \sim an equivalence relation? Justify your answer.

Write down an equivalence relation on the positive integers that has exactly four equivalence classes, of which two are infinite and two are finite.