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 3 of 5: Identify B as the difference of two image sets

Previous step Next step

In plain words

Injectivity prevents an element from being both the image of a missing input and the image of an already-imaged input.

B=f(\mathbb N_0)\setminus f(f(\mathbb N_0))

Detailed analysis

Certainly $B\subseteq f(\mathbb N_0)$ . If $b=f(a)$ with $a\in A$ also belonged to $f(f(\mathbb N_0))$ , then $b=f(f(t))$ for some $t$ , so injectivity of $f$ would give $a=f(t)$ , contradicting $a\in A$ . Conversely, if $b=f(t)$ is not in $f(f(\mathbb N_0))$ , then $t$ cannot lie in $f(\mathbb N_0)$ ; hence $t\in A$ and $b\in B$ . Therefore $B=f(\mathbb N_0)\setminus f(f(\mathbb N_0))$ .