第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$ は奇数であり、矛盾である。したがってそのような関数は存在しない。