Paper 4, Section II, E

Numbers and Sets | Part IA, 2016

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

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

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

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

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

Typos? Please submit corrections to this page on GitHub.