Past exam of the mathematics course of the University of Cambridge / 2023 / ia / Paper 4 / 8D (Numbers & Sets)

If $A_n$ are countable, choose enumerations and map each element of ${\bigcup }_n{A}_n$ to the first pair $(n,k)$ at which it occurs. Since ${\mathbb{N}}^2$ is countable, the union is countable.

A periodic function of period $k$ is determined by its $k$ values on a complete residue system. Thus all periodic functions form a countable union over $k$ of the countable sets ${\mathbb{N}}^k$, and are countable.

The set of bijections $\mathbb{N}\to \mathbb{N}$ is uncountable. Indeed, each binary sequence determines a bijection that swaps $2j-1$ and $2j$ exactly when its $j$th bit is one. This is an injection from the uncountable set of binary sequences.

The set is uncountable by Cantor's diagonal argument: from any proposed list, form a sequence whose $n$th bit differs from the $n$th bit of the $n$th listed sequence.

Sequences with finitely many ones correspond to finite subsets of $\mathbb{N}$, a countable union of the countable sets of $k$-element subsets. Complementation gives the same result for finitely many zeros. Their union is therefore countable.

All binary sequences are uncountable, while part (ii) accounts for the sequences which fail to have infinitely many symbols of both kinds and is countable. Removing that countable subset leaves an uncountable set.