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 5 of 5: Odd cardinality gives the contradiction

Previous step Next step

In plain words

An odd number cannot be split into two equally sized disjoint sets; the assumed function would force exactly such a split.

|A|=|B| \implies |A\cup B|=2|A| \text{ is even, contradicting } |A\cup B|=1987

Detailed analysis

Because $f$ is injective, $|B|=|A|$ . Since $A$ and $B$ are disjoint and their union is the finite set $\{0,\ldots,1986\}$ , both are finite and $|A\cup B|=|A|+|B|=2|A|$ must be even. But $|A\cup B|=1987$ is odd, a contradiction. Hence no such function exists.