Paper 4, Section II, E

Numbers and Sets | Part IA, 2014

(i) What does it mean to say that a set XX is countable? Show directly that the set of sequences (xn)nN\left(x_{n}\right)_{n \in \mathbb{N}}, with xn{0,1}x_{n} \in\{0,1\} for all nn, is uncountable.

(ii) Let SS be any subset of N\mathbb{N}. Show that there exists a bijection f:NNf: \mathbb{N} \rightarrow \mathbb{N} such that f(S)=2Nf(S)=2 \mathbb{N} (the set of even natural numbers) if and only if both SS and its complement are infinite.

(iii) Let 2=1a1a2a3\sqrt{2}=1 \cdot a_{1} a_{2} a_{3} \ldots be the binary expansion of 2\sqrt{2}. Let XX be the set of all sequences (xn)\left(x_{n}\right) with xn{0,1}x_{n} \in\{0,1\} such that for infinitely many n,xn=0n, x_{n}=0. Let YY be the set of all (xn)X\left(x_{n}\right) \in X such that for infinitely many n,xn=ann, x_{n}=a_{n}. Show that YY is uncountable.

Typos? Please submit corrections to this page on GitHub.