数学的帰納法の定理、最小値の定理、累積帰納法の定理 の同値性

数学的帰納法の定理
A(n)を自然数nを変数とする論理式とする。この時次が成り立つ： \begin{array}{l} A(0) \Rightarrow \left[ \forall n \left( A(n) \Rightarrow A(n+1) \right) \Rightarrow \forall n A(n) \right] \end{array}

これから直接次の定理が証明される。

最小値の定理
A(n)を自然数nを変数とする論理式とする。この時次が成り立つ： \begin{array}{l} \exists n A(n) \Rightarrow \exists n \left( A(n) \land \forall m \lt n \neg A(m) \right) \end{array}

---

証明
$B(n) :\equiv \forall m < n \neg A(m)$ と置く。
明らかに$B(0)$なので、数学的帰納法の定理より、$\forall n \left( B(n) \Rightarrow B(n+1) \right) \Rightarrow \forall n B(n)$。
\begin{array}{cl} & \forall n \left( B(n) \Rightarrow B(n+1) \right) \Rightarrow \forall n B(n) \\ \equiv & \neg \forall n B(n) \Rightarrow \neg \forall n \left( B(n) \Rightarrow B(n+1) \right) \\ \equiv & \neg \forall n \forall m \lt n \neg A(m) \Rightarrow \neg \forall n \left( \forall m \lt n \neg A(m) \Rightarrow \forall m \lt n+1 \neg A(m) \right) \\ \equiv & \exists n \exists m \lt n A(m) \Rightarrow \neg \forall n \left( \forall m \lt n \neg A(m) \Rightarrow \neg A(n) \right) \\ \equiv & \exists n A(n) \Rightarrow \exists n \left( \forall m \lt n \neg A(m) \land A(n) \right) \end{array} ここで、$\forall m \lt n \neg A(m) \Rightarrow \forall m \lt n+1 \neg A(m) \equiv \forall m \lt n \neg A(m) \Rightarrow \neg A(n)$と、
$\exists n \exists m \lt n A(m) \equiv \exists n A(n)$を使った。

累積帰納法の定理
A(n)を自然数nを変数とする論理式とする。この時次が成り立つ： \begin{array}{l} \forall n \left( \forall m \lt n A(m) \Rightarrow A(n) \right) \Rightarrow \forall n A(n) \end{array}

---

$B(n) :\equiv \neg A(n)$ と置く。
最小値の定理により、 \begin{array}{cl} & \exists n B(n) \Rightarrow \exists n \left( B(n) \land \forall m \lt n \neg B(m) \right) \\ \equiv & \neg \exists n \left( B(n) \land \forall m \lt n \neg B(m) \right) \Rightarrow \neg \exists n B(n)\\ \equiv & \forall n \left( \neg B(n) \lor \neg \forall m \lt n \neg B(m) \right) \Rightarrow \forall n \neg B(n) \\ \equiv & \forall n \left( \forall m \lt n A(m) \Rightarrow A(n) \right) \Rightarrow \forall n A(n) \end{array}

更に実は以上の3命題は同値でもある：

$A(n)$を自然数$n$を変数とする論理式とする。 この時、累積帰納法の定理から数学的帰納法の定理が示される。

---

\begin{array}{lcl} A(0) & \Rightarrow & \left( \forall m \lt 0 A(m) \Rightarrow A(0) \right) \\ \forall n \left( A(n) \Rightarrow A(n+1) \right) & \Rightarrow & \forall n \left( \forall m \lt n+1 A(m) \Rightarrow A(n+1) \right) \end{array} だから、 \begin{array}{cl} & A(0) \land \forall n \left( A(n) \Rightarrow A(n+1) \right) \Rightarrow \left( \forall m \lt 0 A(m) \Rightarrow A(0) \right) \land \forall n \left( \forall m \lt n+1 A(m) \Rightarrow A(n+1) \right) \\ \equiv & A(0) \land \forall n \left( A(n) \Rightarrow A(n+1) \right) \Rightarrow \forall n \left( \forall m \lt n A(m) \Rightarrow A(n) \right) \end{array} これと、累積帰納法の定理 \begin{array}{c} \forall n \left( \forall m \lt n A(m) \Rightarrow A(n) \right) \Rightarrow \forall n A(n) \end{array} より、 \begin{array}{c} A(0) \land \forall n \left( A(n) \Rightarrow A(n+1) \right) \Rightarrow \forall n A(n) \end{array}