Paper 4, Section II, $7 \mathrm{E}$

(i) What does it mean to say that a set is countable? Show directly from your definition that any subset of a countable set is countable, and that a countable union of countable sets is countable.

(ii) Let $X$ be either $\mathbb{Z}$ or $\mathbb{Q}$. A function $f: X \rightarrow \mathbb{Z}$ is said to be periodic if there exists a positive integer $n$ such that for every $x \in X, f(x+n)=f(x)$. Show that the set of periodic functions from $\mathbb{Z}$ to itself is countable. Is the set of periodic functions $f: \mathbb{Q} \rightarrow \mathbb{Z}$ countable? Justify your answer.

(iii) Show that $\mathbb{R}^{2}$ is not the union of a countable collection of lines.

[You may assume that $\mathbb{R}$ and the power set of $\mathbb{N}$ are uncountable.]

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