Paper 4, Section II, E

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

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

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

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