問題3.nを3以上の自然数とする. このとき、以下の問いに答えよ.
(1) {1,2,3,....n} から {1,2} への全射写像が2"2個であることを証明せよ。
(2) {1,2.3.....n} から{1.2.3} への全射写像が3" -3-2" +3個であることを数学的帰納法を用い
て証明せよ。
(ヒント: (1) 全射ではない写像は像が1だけか, 2だけということになります。 (2) 数学的帰納法を用
いずとも証明はできますが、ここでは解き方を制限します。 写像 f: {1.2.3.....nn+1}
{1,2,3}
において,fの定義域を {1.2.3..... n} に制限することによりf': {1.2.3....,n} {1,2,3}が定まり
ます(要するに, n +1の部分を忘れてしまう)。 ここで,f': {1,2,3....,n} {1,2,3}が全射であっ
たものはf(n+1) の像はなんでも考えられます. f': {1,2,3,....n}{1,2,3} が定値写像ではない
が全射でなかった場合はn+1の像はf' の写像の像に属していない元が対応していなくてはなりま
せん。 例えば, Im (f') = {1,2}だったとすればf(n+1)=3でなくてはなりません。 それぞれの場合
の数を数えます。 後者は (1) も使います.)
