数学的帰納法

$P(1)$ と含意 $P(1) \Rightarrow P(2)$ から $P(2)$ が得られ、$P(2)$ と $P(2) \Rightarrow P(3)$ から $P(3)$ が得られる。これを繰り返せば、任意の整数 $n$ に有限ステップで到達できる。公理的算術（ペアノの公理系）において、帰納法は自然数を特徴づける公理の一つである。

$P(1)$ が成り立ち、すべての整数 $k \ge 1$ に対して含意 $P(k) \Rightarrow P(k+1)$ が成り立つと仮定する。すべての $n \ge 1$ について $P(n)$ が成り立つことを示すため、背理法により反例の集合 $S = \{n \in \mathbb{Z}_{\ge 1} : P(n) \text{ is false}\}$ が空でないと仮定する。

正の整数全体の集合 $\mathbb{Z}_{\ge 1}$ の整列原理により、空でない部分集合 $S$ は最小元 $m = \min S \ge 1$ をもつ。基底段階の仮定より $P(1)$ は真であるから $1 \notin S$ であり、したがって $m \ge 2$ すなわち $m - 1 \ge 1$ となる。

$m - 1 < m$ であり $m$ は $S$ の最小元なので $m - 1 \notin S$、すなわち $P(m-1)$ は真でなければならない。$k = m - 1 \ge 1$ に対して帰納段階を適用すると $P(m-1) \Rightarrow P(m)$ が得られ、$P(m)$ も真となる。これは $m \in S$ に矛盾するため $S = \varnothing$ が示され、すべての $n \ge 1$ に対して $P(n)$ が成り立つ。

強帰納法を用いれば、通常の帰納法以外の新たな公理を追加することなく、$P(j)$（ただし $n_0 \le j \le k$）という過去のすべての段階（例えば $k+1 = a b$ の因数 $a, b \le k$ やフィボナッチ漸化式の $P(k-1)$ と $P(k)$）を自由に利用できる。

通常の帰納法への帰着： $n \ge n_0$ に対する命題 $P(n)$ に対し、累積連言命題 $Q(n) \equiv P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$ を定める。基底 $n = n_0$ において $Q(n_0)$ は単一の項 $P(n_0)$ に一致し、強帰納法の基底仮定により成り立つ。

**$Q(k)$ に対する帰納段階：** 整数 $k \ge n_0$ を固定し、$Q(k)$ が真であると仮定する。$Q(k)$ の定義により $P(n_0), P(n_0+1), \dots, P(k)$ はすべて真である。したがって強帰納段階の仮定 $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ から $P(k+1)$ も真となる。

結論： $Q(k)$ と $P(k+1)$ を合わせることで $Q(k+1) \equiv Q(k) \wedge P(k+1)$ が成り立つ。命題 $Q(n)$ に通常の数学的帰納法を適用すれば、すべての整数 $n \ge n_0$ に対して $Q(n)$ が成り立ち、特にその最後の項である $P(n)$ もすべての $n \ge n_0$ について成り立つ。