第4题

证明:不存在从非负整数集到其自身的函数

f

,使得对每个非负整数

n

都有

f(f(n)) = n + 1987

。

第 2/5 步：分离不在像集中的元素及其像

通俗地说

$A$ 记录 $f$ 的像集留下的“空洞”;对这些空洞再应用一次 $f$ ,所得位置就是 $B$ 。

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

详细分析

令 $A=\mathbb N_0\setminus f(\mathbb N_0)$ 为没有原像的元素集,令 $B=f(A)$ 。因为 $f$ 是单射,所以 $|B|=|A|$ (此时两者可能有限,也可能可数无限)。