Past exam of the mathematics course of the University of Cambridge / 2014 / ia / Paper 4 / 7E / ii

Use $\mathbb{N}=\{1,2,\dots \}$. If a bijection $f:\mathbb{N}\to \mathbb{N}$ maps $S$ onto the even natural numbers, its restriction is a bijection from $S$ onto an infinite set. Moreover, its restriction to the complement of $S$ maps onto the odd natural numbers. Both sets are therefore infinite.

Conversely, suppose that $S$ and its complement are infinite. Applying the increasing enumeration of an infinite subset of natural numbers to each givesFor completeness, successively choose the least unused member. The process never stops because the set is infinite, and it lists every member: an omitted member would have infinitely many selected natural numbers below it, which is impossible. DefineThis is injective on each list, their images are disjoint, and together their images cover $\mathbb{N}$. Thus it is a bijection and maps $S$ onto $2\mathbb{N}$. Both infinitude conditions are necessary and sufficient. If a convention includes zero in $\mathbb{N}$, index each list from zero and use $2j$, $2j+1$ instead.