4.II.5C

Define what is meant by the term countable. Show directly from your definition that if $X$ is countable, then so is any subset of $X$.

Show that $\mathbb{N} \times \mathbb{N}$ is countable. Hence or otherwise, show that a countable union of countable sets is countable. Show also that for any $n \geqslant 1, \mathbb{N}^{n}$ is countable.

A function $f: \mathbb{Z} \rightarrow \mathbb{N}$ is periodic if there exists a positive integer $m$ such that, for every $x \in \mathbb{Z}, f(x+m)=f(x)$. Show that the set of periodic functions $f: \mathbb{Z} \rightarrow \mathbb{N}$ is countable.

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