Paper 4, Section II, E

(a) Let $S$ be a set. Show that there is no bijective map from $S$ to the power set of $S$. Let $\mathcal{T}=\left\{\left(x_{n}\right) \mid x_{i} \in\{0,1\}\right.$ for all $\left.i \in \mathbb{N}\right\}$ be the set of sequences with entries in $\{0,1\} .$ Show that $\mathcal{T}$ is uncountable.

(b) Let $A$ be a finite set with more than one element, and let $B$ be a countably infinite set. Determine whether each of the following sets is countable. Justify your answers.

(i) $S_{1}=\{f: A \rightarrow B \mid f$ is injective $\}$.

(ii) $S_{2}=\{g: B \rightarrow A \mid g$ is surjective $\}$.

(iii) $S_{3}=\{h: B \rightarrow B \mid h$ is bijective $\}$.

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