数学的帰納法

数学的帰納法

数学的帰納法にはいろいろなバリエーションがあるので,使い方に慣れる必要がある.


目次

  1. 数学的帰納法
  2. 整列集合
  3. 2重帰納法
  4. ネーター帰納法

まず,数学的帰納法の基本型を思い出しておこう.

数学的帰納法(その1)

自然数 n を含んだ命題 P(n) を証明するには

  1. P(1) は正しい.
  2. すべての自然数 k について,P(k) が正しいとすれば,P(k + 1) も正しい.
という2つのことを証明すればよい.

帰納法の仮定の部分は次のようにすることも多い.

2') 2 以上のすべての自然数 n について,P(n - 1) が正しいとすれば,P(n) も正しい.

問題 任意の自然数 n について,{n, n + 1, ..., 2n} の中に必ず平方数(ある自然数の 2 乗になる数)が存在することを証明せよ.

帰納法の仮定の部分を次のような形にすることもできる.仮定が多い分,元の形より証明が容易になることがある.

数学的帰納法(その2)

自然数 n を含んだ命題 P(n) を証明するには

  1. P(1) は正しい.
  2. すべての自然数 k について,P(1), ..., P(k) が正しいとすれば,P(k + 1) も正しい.
という2つのことを証明すればよい.

整列集合

数学的帰納法の原理を次のように述べることもできる.

自然数の集合 N整列集合である.すなわち,N の任意の空でない部分集合には最小の自然数が存在する

自然数の素因数分解の存在証明を数学的帰納法(その2)と自然数が整列集合であるという原理の両方で述べてみる.

定理(素因数分解の存在定理 任意の自然数 n ≧ 2は素数の積に分解する.

数学的帰納法(その2)による証明 n に関する帰納法を用いる.n = 2 は素数であるから,そのままでよい.n > 2 として,n より小さい自然数(≧ 2)は素数の積に分解することを仮定する.n が素数であれば,そのままでよいので,n は合成数であって,

n = ab   (1 < a < n, 1 < b < n)

となるような a,b が存在する.このとき,帰納法の仮定により, a,b は素数の積に分解するので,n も素数の積に分解する.

整列集合の原理による証明 素数の積に分解しない 2 以上の自然数があると仮定し,その中で最小の自然数を n とする(整列集合の原理).このとき,n は素数ではないので,

n = ab   (1 < a < n, 1 < b < n)

となるような a,b が存在する.このとき,n のとり方から,a,b は素数の積に分解する.その結果,n も素数の積に分解することになり,元々の仮定に反する.

この証明は次のようにも述べることもできる.この証明法を無限降下法という.

無限降下法による証明 n を 2 以上の自然数とする.n が素数のときは何もすることはない.n が合成数のとき,n の最小の因数(≧ 2)を p1 とすれば,p1 は素数である.そこで,n = p1n1 とする.n1 が素数のときには,n は素数の積で表される.n1 が合成数であれば,ふたたび,n1 = p1n2 となる素数 p1 がある.この操作を続けることにより,自然数の列,

n > n1 > n2 > ... > 1

が得られる.したがって,有限回の操作の後,nk-1 は素数 pkになる.このとき,n = p1... pkと素数の積に分解する.

数学的帰納法の拡張に2重数学的帰納法(2重帰納法)がある.

2重帰納法

自然数 n と自然数 m を含んだ命題 P(n, m) を証明するには

  1. すべての m について,P(1, m) は正しい.
  2.  
  3. すべての m について,P(k, m) が正しいとすれば,P(k + 1, m) も正しい.

という2つのことを証明すればよい.

2重帰納法は次のような対称な形でも述べられる.

2重帰納法(その2)

命題 P(n, m) が正しいことを証明するには,

  1. すべての n, m について,P(n, 1) および P(1, m) は正しい.
  2. すべての k, j について,P(k + 1, j) および P(k, j + 1) が正しいとすれば,P(k + 1, j + 1) も正しい.

を証明すればよい.

もっと一般な帰納法について言及しておく.

ネーター帰納法

A を極小条件を満たす半順序集合とする.A の各元 a に命題 P(a) が対応しているとき,A のすべての元 a について,P(a) を証明するには

  1. A のすべての極小元 b について,P(b) は正しい.
  2. b > a となるすべての元 a について,P(a) が正しいとすれば,P(b) も正しい.

を証明すればよい.


トップへ
酒井文雄記(2000年4月)