(a) Define what it means for a set to be countable. Prove that $\mathbb{N} \times \mathbb{Z}$ is countable, and that the power set of $\mathbb{N}$ is uncountable.

(b) Let $\sigma: X \rightarrow Y$ be a bijection. Show that if $f: X \rightarrow X$ and $g: Y \rightarrow Y$ are related by $g=\sigma f \sigma^{-1}$ then they have the same number of fixed points.

[A fixed point of $f$ is an element $x \in X$ such that $f(x)=x$.]

(c) Let $T$ be the set of bijections $f: \mathbb{N} \rightarrow \mathbb{N}$ with the property that no iterate of $f$ has a fixed point.

[The $k^{\text {th }}$iterate of $f$ is the map obtained by $k$ successive applications of $f$.]

(i) Write down an explicit element of $T$.

(ii) Determine whether $T$ is countable or uncountable.