Paper 4, Section II, E

Numbers and Sets
Part IA, 2015

What does it mean for a set to be countable? Prove that

(a) if BB is countable and f:ABf: A \rightarrow B is injective, then AA is countable;

(b) if AA is countable and f:ABf: A \rightarrow B is surjective, then BB is countable.

Prove that N×N\mathbb{N} \times \mathbb{N} is countable, and deduce that

(i) if XX and YY are countable, then so is X×YX \times Y;

(ii) Q\mathbb{Q} is countable.

Let C\mathcal{C} be a collection of circles in the plane such that for each point aa on the xx-axis, there is a circle in C\mathcal{C} passing through the point aa which has the xx-axis tangent to the circle at aa. Show that C\mathcal{C} contains a pair of circles that intersect.