第4题

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

f

,使得对每个非负整数

n

都有

f(f(n)) = n + 1987

。

第 3/5 步：把 B 识别为两个像集之差

上一步下一步

通俗地说

单射性保证一个元素不可能既是不在像集中的输入的像,又是已在像集中的输入的像。

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

详细分析

显然 $B\subseteq f(\mathbb N_0)$ 。若 $b=f(a)$ 且 $a\in A$ 还属于 $f(f(\mathbb N_0))$ ,则存在 $t$ 使 $b=f(f(t))$ ;由 $f$ 的单射性得 $a=f(t)$ ,这与 $a\in A$ 矛盾。反之,若 $b=f(t)$ 不属于 $f(f(\mathbb N_0))$ ,则 $t$ 不属于 $f(\mathbb N_0)$ ,故 $t\in A$ 且 $b\in B$ 。所以 $B=f(\mathbb N_0)\setminus f(f(\mathbb N_0))$ 。