MathLabs

第4問

非負整数全体からそれ自身への関数 ff で、すべての非負整数 nn に対して f(f(n))=n+1987f(f(n)) = n + 1987 を満たすものが存在しないことを証明せよ。
ステップ 2/5: 像に入らない元とその像を分ける
ざっくり言うと

AA は ff の像が残した『穴』を記録し、BB はその穴に ff を一度適用したときの行き先である。

A=N0∖f(N0),B=f(A)A=\mathbb N_0\setminus f(\mathbb N_0),\qquad B=f(A)
詳しい解説

A=N0∖f(N0)A=\mathbb N_0\setminus f(\mathbb N_0) を逆像をもたない元の集合とし、B=f(A)B=f(A) とおく。ff は単射なので ∣B∣=∣A∣|B|=|A| である(この段階では両者は有限または可算無限かもしれない)。