(a) Prove that a countable union of countable sets is countable.

(b) (i) Show that the set $\mathbb{N}^{\mathbb{N}}$ of all functions $\mathbb{N} \rightarrow \mathbb{N}$ is uncountable.

(ii) Determine the countability or otherwise of each of the two sets

$$\begin{aligned} &A=\left\{f \in \mathbb{N}^{\mathbb{N}}: f(n) \leqslant f(n+1) \text { for all } n \in \mathbb{N}\right\}, \\ &B=\left\{f \in \mathbb{N}^{\mathbb{N}}: f(n) \geqslant f(n+1) \text { for all } n \in \mathbb{N}\right\} \end{aligned}$$

Justify your answers.

(c) A permutation $\sigma$ of the natural numbers $\mathbb{N}$ is a mapping $\sigma \in \mathbb{N}^{\mathbb{N}}$ that is bijective. Determine the countability or otherwise of each of the two sets $C$ and $D$ of permutations, justifying your answers:

(i) $C$ is the set of all permutations $\sigma$ of $\mathbb{N}$ such that $\sigma(j)=j$ for all sufficiently large $j$.

(ii) $D$ is the set all permutations $\sigma$ of $\mathbb{N}$ such that

$$\sigma(j)=j-1 \text { or } j \text { or } j+1$$

for each $j$.