強帰納法の原理と論理的同値性

通常の帰納法への帰着： $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$ について成り立つ。