4.II.8E

Explain what it means for a set to be countable. Prove that a countable union of countable sets is countable, and that the set of all subsets of $\mathbb{N}$ is uncountable.

A function $f: \mathbb{N} \rightarrow \mathbb{N}$ is said to be increasing if $f(m) \leqslant f(n)$ whenever $m \leqslant n$, and decreasing if $f(m) \geqslant f(n)$ whenever $m \leqslant n$. Show that the set of all increasing functions $\mathbb{N} \rightarrow \mathbb{N}$ is uncountable, but that the set of decreasing functions is countable.

[Standard results on countability, other than those you are asked to prove, may be assumed.]

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