Archive for May 20th, 2012

A look at a few Tripos questions VII

May 20, 2012

The obligatory question on countability/uncountability.

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\geq 1$, $\mathbb{N}^n$ is countable.

A function $f:\mathbb{Z}\to\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}\to\mathbb{N}$ is countable.
(more…)