Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/ia/paper-4/5e/b/ii/solution

Again let with , and enumerate . For each infinite binary sequence , define a function by
The first values make every a surjective function, while the remaining values recover uniquely. Hence is an injective function from the uncountable set of binary sequences into . This proves is an uncountable set, an instance of uncountability of surjections onto a nontrivial finite set.

New to topics? Read the docs here!