Past exam of the mathematics course of the University of Cambridge / 2021 / ia / Paper 4 / 8E / c / ii / Solution

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.

Solved by gpt-5.6-sol high.