Past exam of the mathematics course of the University of Cambridge / 2004 / ia / Paper 4 / 5E / Solution

Number the natural numbers from one. If the power set could be enumerated as $A_1,A_2,\dots$, form $D=\{j:j\notin A_j\}$. For each $j$, membership of $j$ in $D$ is opposite to its membership in $A_j$, so $D\ne A_j$. This contradicts completeness of the enumeration. Thus the Cantor diagonal argument proves that the power set is an uncountable set.

For a finite subset $A$, define $b(A)={\sum }_{j\in A}{2}^{j-1}$. This is a nonnegative integer and the map is injective: if two finite subsets differ, let $k$ be their largest differing element. Its contribution $2^{k-1}$ exceeds the sum $1+2+\cdots +2^{k-2}$ of all smaller possible contributions, so their codes differ. There are infinitely many singleton subsets. Hence the countability of finite subsets of a countable set here is countable infinitude.

To treat all bijections, associate to every subset $A\subseteq \mathbb{N}$ the permutation that swaps $2j-1$ and $2j$ when $j\in A$, and fixes both when $j\notin A$. These disjoint pair swaps define a bijection of $\mathbb{N}$. Different subsets give different permutations, so the map from the power set into $X$ is injective. Therefore $X$ is an uncountable set.

Every finitely supported permutation fixes all elements above some $k$. A bijection fixing that tail must permute $\{1,\dots ,k\}$: it cannot send a smaller element into the fixed tail without violating injectivity. There are exactly $k!$ such permutations. Thusis a countable union of finite sets. Enumerate first by $k$, then by one of the finitely many permutations at that $k$; duplicates can be omitted. Infinitely many distinct pair swaps belong to $Y$, so $Y$ is countably infinite. The full family is uncountable, while the finitely supported family is countably infinite.