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

Numbers and Sets | Part IA, 2013

(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 XX be either Z\mathbb{Z} or Q\mathbb{Q}. A function f:XZf: X \rightarrow \mathbb{Z} is said to be periodic if there exists a positive integer nn such that for every xX,f(x+n)=f(x)x \in X, f(x+n)=f(x). Show that the set of periodic functions from Z\mathbb{Z} to itself is countable. Is the set of periodic functions f:QZf: \mathbb{Q} \rightarrow \mathbb{Z} countable? Justify your answer.

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

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

Typos? Please submit corrections to this page on GitHub.