部分集合への単射に関する性質

【演習】\(f\)は集合\(A\)からその部分集合\(B\)への単射であるとする。このとき、任意の自然数\(m,n\)(ただし\(m\neq n\))について\(f^m[A\backslash B]\cap f^n[A\backslash B]=\varnothing\)となることを示せ。

【解答】\(m > n\)としても一般性を失わない。\(m\)についての条件
   \(n < m\)なる任意の自然数\(n\)について\(f^{m}[A\backslash B]\cap f^{n}[A\backslash B]=\varnothing\)
を\(P(m)\)と書く。\(m\geq 1\)なる任意の自然数\(m\)が\(P(m)\)を満たすことを、数学的帰納法により示す。
\(f[A\backslash B]\subset B\)から\(f[A\backslash B]\cap (A\backslash B)=\varnothing\)であるので、\(P(1)\)は成立する。
\(P(m)\)(ただし\(m\geq 1\))を仮定し、\(P(m+1)\)を導く。まず、上と同様に\(f^{m+1}[A\backslash B]\cap (A\backslash B)=\varnothing\)である。次に、交わらない集合の単射による像同士はやはり交わらないから、\(f^{m+1}[A\backslash B]\)は\(f^1[A\backslash B]\)から\(f^m[A\backslash B]\)までのいずれとも交わらない。したがって\(P(m+1)\)が成り立つ。■