Problem 4

Prove that there is no function

f

from the set of non-negative integers into itself such that

f(f(n)) = n + 1987

for every non-negative integer

n

Step 2 of 5: Separate the missing inputs from their images

Previous step Next step

In plain words

$A$ records the holes left by the image of $f$ ; $B$ is what those holes map to when $f$ is applied once.

A=\mathbb N_0\setminus f(\mathbb N_0),\qquad B=f(A)

Detailed analysis

Let $A=\mathbb N_0\setminus f(\mathbb N_0)$ be the set of elements with no preimage, and let $B=f(A)$ . Since $f$ is injective, $|B|=|A|$ (both may be viewed as finite or countably infinite at this stage).