Paper 4, Section II, E

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

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

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

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

(i) if $X$ and $Y$ are countable, then so is $X \times Y$;

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

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

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