高校で学ぶ帰納法から大学で使う帰納法へ ～数学的帰納法～

注：証明は後回しにしてクイズなどをたのしんでください。

自然数 $\mathbb{N}=\{1, \: 2, \:3, ...\}$ は大小 ≦ に関して $a\geqq b$ または $a\leqq b$ $(a, \: b \in \mathbb{N})$が成り立ちます(※1)。さらに次が成り立ちます：

命題１　$\mathbb{N}$ の任意の空でない部分集合は最小元をもつ。▮(※2)

$W$ が全順序集合であって、その任意の空でない部分集合が常に最小元をもつとき、$W$ を整列集合といいます。もちろん、$\mathbb{N}$ は整列集合であり、有限な全順序集合も整列集合です。理解を深めるために次のクイズを考えてみてください。

　　　クイズ　次の集合のうち整列集合をすべて挙げてください。（答えは ※3）
　　　　　　(1) $W=\{a \in \mathbb{Q} \mid a \geqq -5 \}$
　　　　　　(2) $W=\{-2, \: -1, \: 0, \:1, \:2 \}$
　　　　　　(3) $W=\{\frac{1}{\:2\:}, \: \frac{2}{\:3\:}, \: \frac{3}{\:4\:}, \dots , \: \frac{n}{\:n+1\:}, \dots \}$
　　　　　　(4) $W=\{a \in \mathbb{Q} \mid -1 \leqq a \leqq 1 \}$
　　　　　　(5) $W=\{p \in \mathbb{N} \mid p は素数 \}$

いま、$W$ を１つの整列集合とします。$a \in W$ に対して

$$W[a]:=\{x \in W \mid x < a \}$$  

とおきます。もし $a=\text{min} W$ ならば $W[a]=\varnothing$ であり、このときに限ります。

命題２　$V \subset W$ とする。任意の $a \in W$ に対して

$$W[a] \subset V \: \Longrightarrow \: a \in V$$

ならば、$V=W$ である。▮

実際、もし $V\neq W$ ならば $W \setminus V \neq \varnothing$ なので、整列集合の定義から最小元 $a \in W \setminus V$ が存在します。このとき $W[a] \cap (W \setminus V)=\varnothing$ であるから $W[a] \subset V$. したがって仮定から $a \in V$ となります。ところが これは $a$ の取り方 $a \in W \setminus V$ に矛盾します。▮

※ $W \setminus V$ は差集合を表しています：
$$W \setminus V=\{x \in W \mid x \notin V \}.$$

このことから次が言えます：

命題３　整列集合 $W$ の元に関する命題 $P$ があって、それについて次の(♪)が示されたら、$P$ は $W$ のすべての元に対して成り立つ。

(♪) 　任意に $a \in W$ をとる。$x < a$ である各 $x \in W$ に対して $P$ が成り立つと仮定すれば、$P$ は $a$ についても成り立つ。▮

実際、$P$ が成り立つような $W$ の元全体を $V$ とすれば (♪) によって $V$ は命題２の条件をもつからです。▮

この命題３は超限帰納法と呼ばれるものです。つまりクイズの答えの整列集合に関する命題に使えるということです。クイズの(5)の素数に関する証明があったと記憶するのですが、その例が見つけられませんでした。
ちなみに、授業で超限帰納法を学ばなくても証明では帰納法として使われます。確かに帰納法の原理が分かってしまえば受け入れられるように思うし、各自で調べるかレポート問題にすれば十分に思います(※4)。

　　クイズ２　次の証明に誤りがあればそれを指摘してください。（答えは ※5）

　　　　「碁石ｎ個の集合があれば、その構成要素の碁石はすべて同色である」

証明　$n=1$ の場合は１個の碁石だからすべて同色である。そこで $n>1$ とし $n$ 個より少ない碁石の場合については正しいと仮定し、$n$ 個の場合を示す。

　$n$ 個の碁石を横一列に並べ、右端の碁石を１個取り除く。すると残りの碁石は $n-1$ 個なので帰納法の仮定から同色である。次に、取り除いた１個を元に戻して左端の１個を取り除く。残った $n-1$ 個の碁石は帰納法の仮定から同色である。したがって $n$ 個の碁石はすべて同色である。▮

余話
大学数学でも帰納法を使います。線形代数が最初だったと記憶しています。その後も代数ではよく出てきます。さて、数学者たちはだいたい次のように帰納法を使います。

「$n$ が１のときは明らかなので、$n$ より小さいときに成り立つと仮定し $n$ のときに成り立つことを示します。･･･」

高校で学んだ帰納法の証明と違ったことに困惑しました。$n=1$ のときを示して、$n=k$ を仮定し $n=k+1$ のときを確認するものと思っているのだから疑問符しか出てきません。学生の反応に「各自であとで確かめてください」と言って先に進んでしまいました。数学のできる人たちにはちょっとした表現の違いは何てことないのかと思いました。

と学生の頃は感じていましたが、こういう帰納法にいつの間にか慣れていました。▢

※１　全順序であるということを軽めにいいました。正しくは 集合Mが全順序であるとは
　　順序 ≦ に関して次の３条件＋１を満たすことです。

　　(1) $a \in M$　 ⇒ 　$a \leqq a$,
　　(2) $a \leqq b$ かつ $b \leqq a$　 ⇒　 $a=b$,
　　(3) $a \leqq b$ かつ $b \leqq c$ 　⇒ 　$a \leqq c$,
　　(4) $a, \: b \in M$　 ⇒ 　$a \leqq b$ または $b \leqq a$.

　　(1)~(3) だけの場合は、Mは順序集合と呼ばれます。

※２　命題１  $\mathbb{N}$ の任意の空でない部分集合は最小元をもつ。

　　実際、帰納法によって次のように示せます。
　　$M \subset \mathbb{N}, \: \neq \varnothing$ とすると、$M$ は少なくとも１つの自然数を含む。もし $1 \in M$ ならば 1 が $M$ の最小元なので、$M$ が $n$ 以下の自然数を含む場合にはこの定理が成り立つと仮定します。このとき $n+1 \in M$ の場合にも成り立つことを示します。

　もし $M$ が $n$ 以下の自然数を含む場合は帰納法の仮定から $M$ は最小元をもちます。$M$ が $n$ 以下のどの自然数も含まないならば、$n+1 \in M$ が $M$ の最小元になります。▮

※３　(2), (3), (5) 　注：任意の部分集合が最小元をもつかを確認する。例えば

　　(1) $\{a \in \mathbb{Q} \mid a > -5 \}\subset W$
　　(4) $\{a \in \mathbb{Q} \mid -1 < a < 1 \}\subset W$

　は最小元が存在しません。

※４　大学の授業だけですべてをカバーすることはできません。興味のある数学は独学するか、友だち同士でセミナーを開くことをします。先輩や大学院生と繋がりをもてると独自研究が捗ります。

※5　$n=2$ として読んでみると、１個を取り除いた残りの碁石は１個なので同色なのですが、その色が取り除いた碁石と同色とは言っていません。取り除いた碁石と残りの碁石が同色という場合には３個以上なければなりません。したがって、もしもこれを帰納法で証明する場合には $n=1$ および $n=2$ の場合を示しておく必要があります。その上で３以上の任意の $n$ に対して、$n$ 個より少ない場合は正しいと仮定することになります。
でも既に気づいている通り $n=2$ の場合に正しいとは言えないので命題は偽です。

これは『代数学入門』の p117 に書かれている誤用例です。２個の場合に成り立たないというのはすぐに気づくのですが、誤りを指摘するとなるとかんたんではありませんね。

参考文献
松坂 和夫 著『集合･位相入門』（岩波書店）　第３章 順序集合　特に、pp99-101.
永田雅宜･吉田憲一 共著『代数学入門』（培風館）　８章 順序集合の利用 pp111-117.
G.チャートランド, A.D.ポリメニ, P.チャン 共著『証明の楽しみ 基礎編』　第９章 帰納法