Past exam of the mathematics course of the University of Cambridge / 2020 / ia / Paper 2 / 8D / a / Solution

A set is countable when it is finite or admits a bijection with a subset of $\mathbb{N}$; equivalently, its elements can be listed in a sequence. The integers are countable, for example in the order $0,1,-1,2,-2,\dots$. Enumerating pairs by diagonals, or applying the Cantor pairing function, then shows that $\mathbb{N}\times \mathbb{Z}$ is countable.

Suppose instead that the power set $\mathcal{P}(\mathbb{N})$ had an enumeration $A_1,A_2,\dots$. The Cantor diagonal argument formsFor every $n$, the set $D$ differs from $A_n$ at the element $n$, so it is absent from the alleged enumeration. Therefore