なぜ数学的帰納法が成り立つのか
数学的帰納法は高校数学で教わる証明方法です。
自然数に関する命題 P(n) が全ての自然数 n に対して成り立つ事を証明するために、次のような手続きを行う。
①P(1) が成り立つ事を示す。
②任意の自然数 k に対して、「P(k) ⇒ P(k + 1)」が成り立つ事を示す。
③1と2の議論から任意の自然数 n について P(n) が成り立つ事を結論づける。
直観的には「ドミノ倒し」の例えによる説明が有名です。
P(1)が成り立つ→P(2)が成り立つ→P(3)が成り立つ→……
のように連鎖的に命題が正しいことを確認できるので、これをドミノに例えて説明するものです。
では数学的帰納法が成り立つことを証明することはできるのでしょうか？
結論から言うと、数学的帰納法を他の定理や公理から証明することはできません。
まず、自然数はペアノの公理で定義されてます。
ペアノの公理
①0は自然数である。
②任意の自然数 a にはその後者 (successor)、suc(a) が存在する（suc(a) は a + 1 の "意味"）。
③0 はいかなる自然数の後者でもない（0 より前の自然数は存在しない）。
④異なる自然数は異なる後者を持つ：a ≠ b のとき suc(a) ≠ suc(b) となる。
⑤0 がある性質を満たし、a がある性質を満たせばその後者 suc(a) もその性質を満たすとき、すべての自然数はその性質を満たす。
なんだか自然数について当たり前のことが書いてあるように見えますが、これで自然数が定義できています。つまり、「自然数はこの定義を満たしている」かつ「この定義を満たすものは自然数しかない」ということです。
ペアノの公理の５つ目を見ると、数学的帰納法と全く同じであることが分かります。つまり、数学的帰納法は成り立つのは、それが自然数の定義に書いてあるからです。
うーーん。納得できません。「そう決めたから」というのはなんだか釈然としないし、数学的帰納法を他の定理から示すことはできないのでしょうか。
もし他の自然数の定理を用いて数学的帰納法が成り立つことを示すことができるなら、ペアノの公理の①～④で数学的帰納法で示すことができるはずです。
ペアノの公理を理解するために、より厳密にペアノの公理を書くことを考えましょう。数学の命題を記述するためによく使われるものとして、一階述語論理というものがあります。
一階述語論理とは、簡単に言うと２つの量化記号$${\forall, \exist}$$を用いて命題を書く方法です（詳しくはwikiを参照）。多くの数学的な命題はこの方法で書くことができます。
$${\forall ○○(■■)}$$は「任意の（すべての）○○について■■が成り立つ」という意味です。
$${\forall x \in \mathbb{N} ((n+1)^2=n^2+2n+1)}$$と書いたら、
「全ての自然数$${x}$$で$${(n+1)^2=n^2+2n+1}$$が成り立つ」という意味になります。
$${\exist ○○(■■)}$$は「ある○○が存在して■■が成り立つ（■■が成り立つような○○が存在する）」という意味です。
$${\exist x \in \mathbb{N}(x^3=27)}$$なら、
「ある自然数$${x}$$が存在して、$${x^3=27}$$が成り立つ」という意味です。
たとえば、２次方程式の実数解の存在は次のように書けます。
$${\forall a,b,c \in\mathbb{R}(b^2-4ac\geq 0)\rightarrow\exist x\in\mathbb{R}(ax^2+bx+c=0)}$$
そして、重要な約束事として、一階述語論理では「量化していいのは変数だけ」です。例えば、「全ての集合について」とか「ある命題が存在して」のような量化は許されていません。
さて、ようやくペアノの公理のお話です。
ペアノの公理は一階述語論理で次のように書けます。
先ほど紹介した公理をそのまま一階述語論理に変えただけです。
ただし、「自然数がある性質を満たす」を「自然数がある集合の元である」に言い換えています。
$${0∈N}$$
$${\forall n \in\mathbb{N} \exist m\in\mathbb{N}(n+1=m)}$$
$${∀n∈\mathbb{N}(n+1≠0)}$$
$${∀m, n∈N (m+1=n+1⇒m=n)}$$
$${∀A⊆N ((O∈A∧(∀n∈A(n+1)∈A))⇒A=N)}$$
さて、何かがおかしいのに気づきますか？
ペアノの公理の５番目の公理は「全ての自然数の集合について」と主張しています。つまり集合を量化しているのです。
え？さっき集合は量化してはダメって言ってなかった？
その通りです。ダメなのです。
じつは５番目の公理を集合を量化せずに書く方法はあります。全ての集合について、別々に５を書けばいいのです。そうすれば、「全ての集合について」と言わなくてもよくなりますよね。ただ、自然数の集合は無限にあるので、書きだすことができません。
つまり、一階述語論理だと無限に論理式を書かないといけなくなるので便宜的に集合を量化しているのが５番目の公理なのです。じつは、ペアノの公理は無限個の公理から成り立っていると言えます。
１番目から４番目の公理は一階述語論理の範囲に収まっていましたが、５番目だけその範囲からははみ出しています。つまり、１番目から４番目の公理を使っても数学的帰納法が成り立つことは示せません。
ようやく結論が出ましたね。めでたしめでたし。
ここまで読んで「数学的帰納法は間違っているのか？」と思ったかもしれません。正しいことが示せないなら間違っていると思うのは自然です。しかし、数学的帰納法は間違っているという命題もまた、一階述語論理の範囲を超えています。つまり数学的帰納法は他の公理からは正しいことも間違っていることも示せません。別の言い方をすると、数学的帰納法は正しくても間違っていても他の公理とは矛盾しません。これを他の公理からは独立であるといいます。
「どっちでもいいなら、僕らの思っている自然数の性質に従っている方がいいよね。それなら、数学的帰納法が成り立つとしよう。」ということで、自然数の定義には「数学的帰納法が成り立つ」と明言されています。
余談ですが、数学的帰納法のように操作が無限に続くような命題は他の公理から独立になりがちです。選択公理や決定性公理がZFCから独立なのもおなじですね。
まとめ
数学的帰納法が成り立つのは、自然数の定義でそう定められているから
数学的帰納法は他の公理と独立で、他の公理からは示せない。
この記事が参加している募集
この記事が気に入ったらサポートをしてみませんか？