Past exam of the mathematics course of the University of Cambridge / 2021 / ia / Paper 4 / 8E (Numbers and Sets)

Write the sets as $A_1,A_2,\dots$, and list each nonempty countable set as $A_i=\{a_{i1},a_{i2},\dots \}$. Enumerate the pairs $(i,j)\in {\mathbb{N}}^2$ along successive diagonals, as in the Cantor pairing function, and output $a_{ij}$ when it has not appeared before. Every member of ${\bigcup }_i{A}_i$ eventually appears, proving that a countable union of countable sets is countable.

Suppose all functions $\mathbb{N}\to \mathbb{N}$ could be listed as $f_1,f_2,\dots$. DefineThen $g$ differs from $f_n$ at $n$ for every $n$, so it is absent from the list. This Cantor's diagonal argument proves that ${\mathbb{N}}^{\mathbb{N}}$ is an uncountable set.

$A$ is uncountable. For each binary sequence $({\epsilon }_j)$, defineThis is a nondecreasing function, and different binary sequences give different functions, so the uncountable set of binary sequences injects into $A$.

$B$ is countable. Every nonincreasing sequence of positive integers can decrease only finitely many times and is therefore eventually constant. Such a sequence is specified by a finite sequence of positive integers, and the set of all finite integer sequences is a countable union of countable sets. Hence $B$ is countable.

For each $N$, only finitely many permutations fix every $j>N$: they are precisely the permutations of $\{1,\dots ,N\}$. Thusis a countable union of finite sets and is countable.

For every binary sequence $({\epsilon }_n)$, independently fix the pair $(2n-1,2n)$ when ${\epsilon }_n=0$ and swap its two entries when ${\epsilon }_n=1$. The resulting map is a permutation with $|\sigma (j)-j|\le 1$, and different binary sequences produce different permutations. Therefore $D$ is uncountable.

In fact these are all the possibilities: if $\sigma (j)=j+1$, bijectivity and the displacement bound force $\sigma (j+1)=j$, while a point not in such an adjacent transposition is fixed.