: 2022年5月14日
: 2022年5月22日

様々な帰納法

: 基礎数学
: 自然数; 帰納法; 累積帰納法
対象: 大学2.0年
前提知識: 集合の基礎

$P (n)$ を $n \in N$ についての命題とします．

ベースケースが1以上の帰納法

$n = 2$ のとき成り立ち， $\forall n ≧ 2 P (n) ⟹ P (n + 1)$ が成り立てば，任意の $n ≧ 2$ に対し $P (n)$ は成り立ちます．一応証明しましょう．

命題

$b \in N, b > 0$ とする．以下が成り立つとき， $\forall n ≧ b P (n)$ ：

$P (b)$ ，
$\forall n ≧ b P (n) ⟹ P (n + 1)$ ．

$S (n)$ は切片を表すものとします．つまり， $S (n) = {m \in N ∣ m < n}$ です．

証明

$M = S (b) \cup {n \in N ∣ P (n)}$ とおき， $M = N$ を示せばよい． $b > 0$ より $0 \in S (b)$ ．ゆえに $0 \in M$ ． $n \in M$ を任意にとる． $n < b - 1$ のとき， $n + 1 < b$ だから $n + 1 \in S (b)$ ． $∴ n + 1 \in M$ ． $n = b - 1$ のとき，(1) より $P (b)$ は成り立ち $n + 1 = b \in M$ ． $n > b - 1$ のとき， $n + 1 > b$ ，i.e.， $n ≧ b$ だから，(2) より $P (n + 1)$ は成り立ち， $n + 1 \in M$ ．ペアノの公理系 (P3) より $M = N$ ．

累積帰納法

普通の帰納法は $n = 0$ のとき成り立つことを仮定し， $n$ のとき成り立つとすると $n + 1$ のときも成り立つことを主張し，任意の $n \in N$ で成り立つことを帰結する証明法です．大学以降でしばしば使われる累積帰納法は， $n = 0$ のとき正しいことと， $0, 1, \dots, n$ のとき成り立つことを仮定して $n + 1$ のとき成り立つことを示し，任意の $n \in N$ で成り立つことを帰結する証明法です． $n + 1$ のとき正しいことを示す材料が増えるのでかなり便利です．

例えば， $1$ より大きい $n$ が1つ以上の素数の積で表せる（つまり，素数 $p$ はそれ自身が素数の積とみなす）ことは，累積帰納法で簡単に示せます．

命題

素因数分解の可能性

$n \in N, n ≧ 2$ のとき， $n$ は素数の積で表せる．

素数の定義などはまたしてませんが，既知のものとします．

証明

（累積）帰納法． $2$ は素数だから $n = 2$ のとき成り立つ． $2, \dots, n$ は素数の積で表せると仮定する． $n + 1$ が素数のとき，主張は成り立つ． $n + 1$ が素数でないとき， $n + 1$ は $1$ より大きい正の約数 $d$ をもち，ある $k > 1$ を用いて $n + 1 = k d$ と表せる． $k ≦ n, d ≦ n$ だから，帰納法の仮定より $k, d$ は素数の積で表せる．よって $n + 1$ も素数の積で表せる．

累積帰納法の正しさを証明しましょう．

命題

累積帰納法

$P (n)$ を $n \in N$ についての論理式とする．以下を満たすとき， $\forall n \in N P (n)$ ．

$P (0)$ ．
$\forall m ≦ n P (m) ⟹ P (n + 1)$

証明

$n \in N$ についての命題 $Q (n)$ を $\forall m ≦ n P (m)$ で定義する． $n = 0$ のとき， $m ≦ n$ を満たす $m$ は $0$ だけで，(1)より $Q (0)$ が成り立つ． $Q (n)$ を仮定すると，(2) より $P (n + 1)$ が成り立つ．よって $Q (n + 1)$ ，すなわち $\forall m ≦ n + 1 P (m)$ が成り立つ．帰納法により $\forall n \in N Q (n)$ ． $Q (n)$ が成り立つならば $P (n)$ も成り立つので題意を得る．

命題

累積帰納法2

$P (n)$ を $n \in N$ についての論理式とする．以下を満たすとき， $\forall n \in N P (n)$ ．

$P (0)$ ．
$\forall n > 0 \forall m < n P (m) ⟹ P (n)$

こちらの方が最終的に示すべき命題が $P (n)$ となるので，気持ちよく証明を終えることができます．

ちなみに累積帰納法は，以下の形で紹介されることがあります．

命題

コンパクトな累積帰納法

$P (n)$ を $n \in N$ についての論理式とする．以下を満たすとき， $\forall n \in N P (n)$ ． $\forall n \forall m < n P (m) ⟹ P (n)$

$n = 0$ のときは示さなくていい，という錯覚をしてしまいそうですが，そんなことはありません． $n$ についての論理式 $\forall n \forall m < n P (m) ⟹ P (n)$ を示す際， $n = 0$ のときは $[\forall m < 0 P (m)] ⟹ P (0)$ を示すことになるのですが， $[]$ の部分が常に成り立つので，仮定なしで $P (0)$ を示さなければならないからです．

累積帰納法2の使用例

命題

商と余りの存在

任意の $a \in N, b \in N, b > 0$ に対し，ある $q, r \in N$ が一意的に存在し以下が成り立つ： $a = b q + r, 0 ≦ r < b ．$

証明

(存在性) $b$ を固定し， $a$ についての帰納法で示す． $q, r \in N$ に対し $0 = b q + r$ とすると，いつしか証明した補題より， $b q = r = 0$ で， $b > 0$ だから $q = 0$ ．よって， $a = 0$ のとき，商と余りはともに $0$ に限る． $a$ 未満で成立すると仮定し． $q, r \in N$ に対し $a = b q + r, 0 ≦ r < b (⋆)$ とする． $a < b$ のとき， $q ≧ 1$ を仮定すると $b q ≧ b$ ゆえに $a ≧ b$ となり矛盾．ゆえに $q = 0$ ，そして $r = a$ ．つまり，商は $0$ ，余りは $a$ に限る． $a ≧ b$ のとき， $0 ≦ a - b < a$ で， $(⋆)$ より $a - b ∴ a - b = (b q + r) - b = (r + b q) - b = r + (b q - b) = r + b (q - 1) ． = b (q - 1) + r ． (∵ 減法の結合法則) (∵ 減法の分配法則)$ 帰納法の仮定より， $a - b$ に商 $q^{'}$ と余り $r^{'}$ が存在し，それらは一意的だから $q - 1 = q^{'}, r = r^{'} ．$ つまり， $a$ に対し商は $q^{'} + 1$ ，余りは $r^{'}$ に限る．よって $a$ のときも成立．

$N$ は減法について閉じていないので，減法が面倒です．