- まとめ
- 具体例
「数学的帰納法」とは
自然数に関する命題が、すべての自然数について成り立つことを証明するための手法のこと。
準備
自然数 $n$ に関する命題を $P(n)$ とする
A. 数学的帰納法
以下が成り立つならば, 任意の $n \in \mathbb{N}$ について, $P(n)$ が真である;
- $P(1)$ が真である
- $n \in \mathbb{N}$ について, $P(n)$ が真ならば, $P(n+1)$ も真である
B. 完全帰納法
以下が成り立つならば, 任意の $n \in \mathbb{N}$ について, $P(n)$ が真である;
- $P(1)$ が真である
- $n \in \mathbb{N}$ について, $P(1)$, $\cdots$, $P(n)$ がすべて真ならば, $P(n+1)$ も真である
C. ペアノの公理の第五公準
ペアノの公理の第五公準は, 集合 $\mathbb{N}$ と 数 $0$, 関数 $S$ について, $\forall E \subset \mathbb{N}$, $\forall n \in \mathbb{N}$; '$0 \in E$' $\land$ '$n \in E$ $\Rightarrow$ $S(n) \in E$' $\Rightarrow E = \mathbb{N}$.
ポイント解説
例
$\displaystyle P(n): \sum_{a=1}^n a = \frac{1}{2}n(n+1)$
- $n=1$ のとき, $1=1$ より, $P(1)$ は真である
- $n=k$ のとき $P(k)$ が真であると仮定する. $n=k+1$ のとき
$\sum_{a=1}^n a = 1+\cdots + n$
$=1+\cdots + k + (k+1)$ $=\frac{1}{2}k(k+1) + (k+1)$ $=\frac{1}{2}n(n+1)$
であり, $P(k+1)$ も真である. - 数学的帰納法により, すべての自然数 $n$ について, $P(n)$ は真である
C
ペアノの公理は数学的帰納法を保証する:
$E = \{ n \in \mathbb{N} \mid P(n) =\top \}$
,
$S(n) = n+1$
とすると, 第五公準はA(2)と一致する.
発展
整列集合 $(S, \leq )$では数学的帰納法をより一般化した超限帰納法が成り立つ:
- $P(\min M)$ が真である
- 任意の $\lambda < \mu$ $(\lambda \in S)$ について, $P(\lambda)$ が真ならば, $P(\mu)$ も真である
このとき, $\forall \mu \in M$; $P(\mu) = \top$ である.
具体例
パラドックス
禿げ頭
髪の毛が1本もない頭はハゲである。
ハゲ頭に一本毛が増えてもハゲである。
ゆえに、何本毛が生えていてもハゲである。
砂山
大量の砂は砂山をなす。
砂山から1粒取り除いても砂山である。
ゆえに、どれだけ砂を取り除いても砂山である。
極限でのふるまい
数学的帰納法は全ての $n$ で $P(n)$ が真であることを示すが, 極限での真偽は言及できない.
(例) $\frac{n+1}{n} > 1$ は任意の自然数 $n$ で真だが, $n \to \infty$ では偽である.
