数学的帰納法

数学的帰納法（すうがくてききのうほう、mathematical induction）は、自然数に関する命題を証明するための数学の論法の一つである。自然数 n に関する条件 P(n) がすべての自然数 n に対して成り立つことを、次のような手順で証明する方法をいう。

1. P(0) が成り立つ。
2. 任意の自然数 k に対して、P(k) ⇒ P(k + 1) が成り立つ。

よって任意の自然数 n について P(n) が成り立つ。

イメージとしては、2. により次々と命題の正しさが"伝播"されていくことになる。つまり、1. によりまず P(0) は正しく、これと 2. により P(1) は正しく、これと再び 2. により P(2) は正しく、これと...、のように以下これが無限に続いていく。このことによって任意の自然数 n について P(n) が成り立つことが直観的に確かめられる。ただし、これは数学的帰納法を正当化するための厳密な議論ではない。正式には、数学的帰納法の正しさは自然数の性質の一つである数学的帰納法の原理によって示される。

なお、数学的「帰納法」という名前がつけられているが、数学的帰納法を用いた証明は帰納法ではなく演繹法である。先に述べた 2. により次々と命題の正しさが"伝播"されていき、すべての自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられたにすぎない。

数学的帰納法の原理

数学的帰納法の正しさは数学的帰納法の原理により示される。数学的帰納法の原理とは次のような命題である。

次の条件をみたす自然数の集合 A は、自然数全体の集合 N と等しい：

1. 0 ∈ A 。
2. A は S(n) = n + 1 で定義される写像 S : N → N に関して閉じている。

この原理を用いて、数学的帰納法の正しさは次のようにして示すことができる。すべての自然数 n に対して P(n) が成り立つことを示したいとする。いま、

1. P(0) が成り立つ。
2. 任意の自然数 k に対して、P(k) ⇒ P(k + 1) が成り立つ。

が示されたとしよう。ここで A = { n ∈ N | P(n) } とおけば、この 1. と 2. はまさに A が 0 を要素に持ち、S に関して閉じているということに他ならないので、数学的帰納法の原理より A = N である。したがって、すべての自然数 n に対して n ∈ A、つまり P(n) が成り立つことが示された。

自然数を他の対象（集合、実数など）を用いて定義する立場では、自然数全体の集合は、 0 を要素に持ち、後続者演算（"+1" をする演算）に関して閉じているような最小の集合として定義されるので、数学的帰納法の原理は定理として証明される。一方、自然数を公理的に扱う立場（ペアノの公理など）では、自然数に関する公理の一つとして数学的帰納法の原理が採用される。

なお、自然数全体の集合は無限集合ではあっても「無限大」そのものを含んでおらず、数学的帰納法によって「すべての自然数 n に対して」示せたからといって、P(n) が n の無限大の極限をとっても成り立つとは限らない。

数学的帰納法の例

任意の自然数 n について、0 + 1 + 2 + … + n = n(n + 1)/2 であることを証明する。自然数 n に関する命題 P(n) を 「0 + 1 + … + n = n(n + 1)/2 である」 とすればよい。

まず、P(0)、つまり「0 = 0(0+1)/2」は正しい。次に、任意の自然数 k をとる。今、P(k) が正しいと仮定すると P(k + 1) も正しい。実際、P(k) より

$0 + 1 + \dots + k + (k+1) = (0 + 1 + \dots + k) + (k+1) = \frac{k(k+1)}{2} + (k+1)$

となり、更にこれは

$\frac{k(k+1)+2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$

と等しいので P(k + 1) が成立する。

以上から、数学的帰納法により、任意の自然数 n について命題 P(n) が成立する。（証明終）

バリエーション

数学的帰納法には次のようなバリエーションもあり、場合によってはこちらを用いた方が議論が容易になる。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。

0 以外から始める

ある（0 でないかもしれない）整数 m から議論を始める。すなわち、次の2つを確かめることにより m 以上の任意の整数 n について P(n) が成立することを示す。

1. P(m) が成り立つ。
2. m 以上の任意の整数 k に対して、P(k) ⇒ P(k + 1) が成り立つ。

よって m 以上の任意の整数 n について P(n) が成り立つ。

m = 1 の場合が特に頻繁に用いられる。

対偶論法を組み合わせたもの

対偶ともとの命題は同値であるという事実を組み合わせて、次のような証明ができる。

1. P(0) は真である。
2. P(k + 1) が偽であれば、P(k) も偽である。

よって任意の自然数 n について P(n) は真である。

【補足】2. において、対偶を取ることで、 P(k) が真であれば、P(k + 1) も真である。 という結果が得られるから、前記と同様になる。

背理法を組み合わせたもの

次の証明は、無限降下法と呼ばれる証明とほぼ同等である。

P(n) が成立しないような自然数 n が存在すると仮定し、その中で最小のものを k とする。このとき P(k - 1) も成り立たないことを示す。

これは矛盾であるから P(n) が成立しないような自然数 n は存在しない。すなわち、すべての自然数 n に対して P(n) が成り立つ。

この議論と次に述べる「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 N が通常の大小関係 < によって整列されていることによる。< が N 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。

先立つすべての結果を用いる

仮定として P(k) だけでなく P(0) から P(k - 1) までのすべて（もしくは一部）を用いる。

任意の自然数 k をとったとき、k より小さなすべての自然数 m に対して P(m) が真であれば、P(k) も真である。

よって任意の自然数 n について P(n) は真である。

超限帰納法

自然数について定義された数学的帰納法は、任意の整列集合に対して次の 命題 のように一般化される。この一般化を超限帰納法 (ちょうげんきのうほう、英: transfinite induction)という。任意濃度の集合は選択公理と同値な整列可能定理により整列順序を持つとすることができるので、選択公理を含む公理系であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。

命題 : (A , ≤ ) を整列集合とし、P (x ) を A の元 x に関する命題とする。 A は整列集合であるから "≤" について最小元を持つ。これを 、a₀ とする。もし次の2つの条件が成立するならば、任意の x ∈ A について P (x ) が成り立つ。

条件 1 : P (a₀ ) は真である。

条件 2 : a を A の任意の元とする。 x < a を満たす A の全ての元 x について P (x ) が真ならば、P (a ) も真である。

ただし、"<" は a < b ⇔ ( a ≤ b ∧ a ≠ b) で定義される順序関係とする。

証明

(1) 命題 が偽と仮定する。これは 条件 1 、条件 2 が満たされても P (x ) が偽となる x ∈ A の元が存在することを意味する。そのような元の全ての集合を A_a とする。A は整列集合であるからその部分集合である A_a も最小元を持つ。これを b とする。

(2) 条件 1 から b は A の最小元ではあり得ない。従って、A_b = {x | x ∈ A ∧ x < b } と置けば、A_b は空ではない (少なくとも a₀ を含む)。

(3) b の作り方から明らかなように、x ∈ A_b であれば、P (x ) は真である。従って、条件 2 により P (b ) は真となるが、(1) における b の定義から P (b ) は偽であり、矛盾である。従って命題 は真である。

補足 ： 本当は 条件 1 は不要である。なぜなら、条件 2 において a = a₀ と置けば、x < a を満たす A の元は存在しないので、「x < a を満たす A の全ての元 x について P (x ) が真」という命題は無条件に真であり、従って、P (a₀ ) が真となることが要求されるからである。つまり 条件 1 の要求は 条件 2 に含まれてしまうのである。上の説明では分かりやすいように自然数についての数学的帰納法と整合を取った 。

整礎帰納法

無限下降列が存在しない二項関係を整礎関係という。整礎関係が定義された集合に対して次が成り立つ。これを整礎帰納法という。

R を集合 A 上の整礎関係とし、P(x) を A の元 x に関する命題とする。もし次が成立するならば、任意の x ∈ A について P(x) は真である。

任意の a ∈ A をとる。x R a なる任意の A の元 x について P(x) が真ならば、P(a) も真である。

超限帰納法は整礎帰納法の特殊な場合である。特に、超限帰納法においては、任意の空でない部分集合に最小元が存在する、という性質が、整礎帰納法においては、任意の空でない部分集合に極小元が存在する、という性質に対応している。

ハゲ頭のパラドックス

数学的帰納法を意図的に誤用したジョークとして、次のようなものがある：

髪の毛が一本もない人はハゲである。ハゲの人に髪の毛を一本足してもやっぱりハゲである。よって数学的帰納法により、全ての人はハゲている。

以上のような論法の起源は、古代ギリシャの哲学者ミレトスのエウブリデス (en) が作ったとされるハゲ頭のパラドックス (Paradox of the Bald Man)に帰せられる。これは砂山のパラドックスの起源としても知られる。

前述のジョークにはさまざまなバリエーションがあるが、いずれも「少量の増加程度では大差ない。よって数学的帰納法より沢山の増加でも差はない」という誤謬を利用している。

関連項目

• 帰納
• 演繹
• 自然数
• 整列集合
• 整礎関係
• 無限降下法
• 再帰