Numbers and Sets | Part IA, 2003

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

Show that N×N\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 n1,Nnn \geqslant 1, \mathbb{N}^{n} is countable.

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

Typos? Please submit corrections to this page on GitHub.