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

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.