Past exam of the mathematics course of the University of Cambridge / 2016 / ia / Paper 4 / 5E / b

Write $A=\{a_1,\dots ,a_m\}$ and enumerate $B=\{b_1,b_2,\dots \}$. Each injective function $f:A\to B$ is determined by the finite tuple $(f(a_1),\dots ,f(a_m))$. Thus these functions form a subset of the finite Cartesian product $B^m$. A finite Cartesian power of a countable set is countable: for example, group the index tuples by the maximum of their coordinates, obtaining a countable union of countable sets consisting of finite groups.

There are also infinitely many such injective functions, sincedefines pairwise distinct examples. Therefore $S_1$ is a countably infinite set.

Again let $A=\{a_1,\dots ,a_m\}$ with $m>1$, and enumerate $B=\{b_1,b_2,\dots \}$. For each infinite binary sequence $x=(x_j{)}_{j\ge 1}$, define a function $g_x$ byThe first $m$ values make every $g_x$ a surjective function, while the remaining values recover $x$ uniquely. Hence $x\mapsto g_x$ is an injective function from the uncountable set of binary sequences into $S_2$. This proves $S_2$ is an uncountable set, an instance of uncountability of surjections onto a nontrivial finite set.

Partition the enumeration of $B$ into the pairs $\{b_{2j-1},b_{2j}\}$, for $j\ge 1$. An infinite binary sequence $x$ determines a bijection $h_x:B\to B$: leave the $j$th pair fixed when $x_j=0$, and interchange its two elements when $x_j=1$. Each element stays in its own pair, so this function is a bijection, indeed its own inverse.

Different binary sequences give different bijections, since a changed bit changes the action on the corresponding pair. We have therefore embedded an uncountable set into $S_3$. Hence $S_3$ is uncountable, proving uncountability of permutations of a countably infinite set.