Paper 4, Section II, D

Numbers and Sets | Part IA, 2017

(a) Define what it means for a set to be countable.

(b) Let AA be an infinite subset of the set of natural numbers N={0,1,2,}\mathbb{N}=\{0,1,2, \ldots\}. Prove that there is a bijection f:NAf: \mathbb{N} \rightarrow A.

(c) Let AnA_{n} be the set of natural numbers whose decimal representation ends with exactly n1n-1 zeros. For example, 71A1,70A271 \in A_{1}, 70 \in A_{2} and 15000A415000 \in A_{4}. By applying the result of part (b) with A=AnA=A_{n}, construct a bijection g:N×NNg: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}. Deduce that the set of rationals is countable.

(d) Let AA be an infinite set of positive real numbers. If every sequence (aj)j=1\left(a_{j}\right)_{j=1}^{\infty} of distinct elements with ajAa_{j} \in A for each jj has the property that

limN1Nj=1Naj=0\lim _{N \rightarrow \infty} \frac{1}{N} \sum_{j=1}^{N} a_{j}=0

prove that AA is countable.

[You may assume without proof that a countable union of countable sets is countable.]

Typos? Please submit corrections to this page on GitHub.