第4题

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

f

,使得对每个非负整数

n

都有

f(f(n)) = n + 1987

。

第 5/5 步：奇数基数产生矛盾

通俗地说

奇数不可能被分成两个等大的不相交集合;假设的函数恰好迫使出现这种分割。

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

详细分析

因为 $f$ 是单射, $|B|=|A|$ 。又因 $A$ 、 $B$ 不相交且并集是有限集 $\{0,\ldots,1986\}$ ,二者均有限,所以 $|A\cup B|=|A|+|B|=2|A|$ 必须为偶数。但 $|A\cup B|=1987$ 为奇数,矛盾。因此这样的函数不存在。