(a) Define what it means for a set to be countable. Prove that is countable, and that the power set of is uncountable.
(b) Let be a bijection. Show that if and are related by then they have the same number of fixed points.
[A fixed point of is an element such that .]
(c) Let be the set of bijections with the property that no iterate of has a fixed point.
[The iterate of is the map obtained by successive applications of .]
(i) Write down an explicit element of .
(ii) Determine whether is countable or uncountable.